アルゴリズム・パズル

推理判断のプレゼント交換の問題

rsc.hatenablog.comrsc さんのブログから問題を拝借しました。# 問題: A~Eの5人がプレゼント交換をした。5人とも自分以外の人から1つずつプレゼントを受け取ったが、プレゼントを渡した相手からプレゼントを受け取った人はいなかったという。さらに…

「Ruby初心者向けのプログラミング問題」を解いてみる

blog.jnito.comやってみました。 カレンダー作成問題 ここで似たようなことをやっているので省略。(ただし、Date クラスは使っていません。) カラオケマシン問題 class KaraokeMachine Key = %w(C C# D D# E F F# G G# A A# B) def initialize(melody) @sc…

男女平等な席替え(Ruby)

アルゴリズム・パズルです。 男女15人ずつ、計30人のクラスがあります。 横 6、縦 5 の長方形に配置された机に30人が座るとき、どの生徒の席でも前後左右のいずれかに異性の席があるように座るそのしかたは、全部で何とおりになるでしょうか。 ただし、座り…

隣り合わないのがマナー?(Ruby)

アルゴリズム・パズルです。 電車の中に 6人がけのロングシートが向かい合いになって、計12の席があるとします。 すべて空いている状態からすべてが埋まるまで、両隣が空いている空席があるときはそちらから座るというルールで、全部で何通りの席の埋まり方…

4つの数で 10 を作る(Ruby)

テンパズル - Wikipedia 1桁の4つの数と四則演算で、10 を作るコードを Ruby で書いてみました。括弧は使ってもよいことにします。実行例。 $ ruby make_ten.rb [2, 7, 3, 9] で 10 を作る (2 + 3) * (9 - 7) (7 + 9) - (2 * 3) 9 + (7 - (2 * 3)) 9 - ((2 *…

クロスワードパズルを作成せよ!(Ruby)

アルゴリズム・パズルです。 クロスワードを作る場合、空白と黒マスについて次のルールがあります。 黒マスは縦横に連続しない。 黒マスによって盤面が分断されてはいけない。 黒マスルール - Wikipedia これを「黒マスルール」といいます。 さて、縦 5、横 …

「たけしのコマ大数学科」の問題を Ruby で解く

marginalia.hatenablog.com marginalia.hatenablog.com marginalia.hatenablog.comいまこちらの記事で挑戦中です。「たけしのコマ大数学科」については Wikipedia でどうぞ。 問題例です。 10人が円卓に座って1人ずつ握手をするとき、全員の手が交差しないよ…

1時間以内に解けなければプログラマ失格?

blog.kazuhooku.comここで次のような問題を見つけました。 1,2,…,9の数をこの順序で、”+”、”-“、またはなにもせず結果が100となるあらゆる組合せを出力するプログラムを記述せよ。例えば、1 + 2 + 34 – 5 + 67 – 8 + 9 = 100となる。 1時間以内に解けなけれ…

Ruby で関数型プログラミングっぽく(コピペ) + Haskell 版

parrot.hatenadiary.jpここのブログ記事を読んで感銘を受けました。だからこれを読んでもらえればよいのですが、せっかくなのでコピペしておきます。元記事に感謝です。まずは問題。 ある数字にそれを逆に並べた数字を足すという計算を、 回文数(上から読ん…

交差せずに一筆書き(Ruby)

問題: 長方形状に横 5 個、縦 4 個の格子点が全部で 20個、等間隔に並んでいます。このすべての格子点を一筆書き(交差してはならない)で辿るとすると、その辿り方は全部で何とおりあるでしょうか。 ただし進む方向は上下左右のみで、また始点と終点が反対…

騎士の巡歴、あるいはナイト・ツアー(Ruby)

「騎士の巡歴」とは、チェスの「騎士(ナイト)」の駒を使って、チェス盤のマスを一度づつ移動していき、最終的にすべてのマスを訪れるというパズルです。「騎士」の駒は将棋の「桂馬」とよく似た動きをしますが、すべての方向に飛べるだけ桂馬とちがいます…

宣教師と人喰い人(Ruby)

次の有名な問題があります。 問題: 宣教師 3人と人喰い人 3人が、船で川を渡ろうとしています。船は 2人まで乗れますが、最低 1人いなければ動かせません。ここで、こちらの岸もあちらの岸も、また船の上でも、宣教師の数が人喰い人の数を下回ると喰われて…

Go言語と Ruby で 8 queens 問題

Go で「8 queens 問題」を解いてみました。実際は n queens が解けます。すべての解を出力します。num = 8 の場合、解は 92通りあります。こんな感じ。 ------------------ n = 1 @....... ....@... .......@ .....@.. ..@..... ......@. .@...... ...@.... …

「最短ヌクレオチド連鎖問題」が解けない

高校生のとき、友人にこんな問題を出されました。適当に再構成してみます。 タンパク質を構成するアミノ酸は 20種類あるよね。DNA または RNA はそのアミノ酸の設計図で、いわゆる「コドン」を指定している。コドンというのはヌクレオチドの塩基3個から成る…

あみだくじの横線(Ruby)

アルゴリズム・パズルです。 問題: 1 ~ 7 の数字を並べてあみだくじを作ることを考えます。引く横線の数を 10本とするとき、下に得られる数字の並びは何とおりになるでしょうか。ただし、下に得られる数字の並びが 10本より少ない横線のあみだくじで既に得…

公平に分けられたケーキ(Ruby)

アルゴリズム・パズルです。 問題: 16cm × 12cm の長方形のケーキがあります。二人で交互にケーキを切るのですが、ケーキを切った人が小さい方のケーキを取り、交代して残りをさらに切るというようにします。(ただし切り方は、辺に平行に直線的に切り、し…

横着なそろばん(Ruby)

アルゴリズム・パズルです。 問題: そろばんで例えば「8 + 9」をこの順に計算すると、「8 を入れる」のに玉を 4つ動かし、「9 を足す」のに玉を 2つ動かすので、全部で 6回玉を動かすことになります。また、逆に「9 + 8」の順に計算すると、全部で玉を 8回…

「絶対左折禁止」の迷路を解く(Ruby)

ブログにスターを頂いて、上のサイトを知りました。オリジナルの様々な迷路が出題されている、すばらしくおもしろそうなブログです。皆さんも御覧になってはいかがでしょうか? …とは別にステマでも何でもないのですが、そこで「絶対左折禁止」という迷路が…

与えられた迷路の最短経路を求める(Go言語)

以前 Ruby で解いたのの Go言語版です。Go言語のお勉強に移植してみました。まずは実行結果。 $ go build solve_maze.go $ time ./solve_maze ************************** *S* *$$$$ * *$* *$ *$ ************* * *$*$$$* $ ************ * *$$$ * $$$$$$$ *…

急がば回れ(Ruby)

アルゴリズム・パズルです。 問題: 上のような規則があります。縦が 5cm、横が 6cm の長方形の場合、A から B までの最長経路は何 cm でしょうか。 Ruby で解いてみました。 q50.rb W, H = 6, 5 def yoko?(y) @yoko[y].inject(:+) < 2 end def tate?(x) @ta…

反転で作る互い違い(Ruby)

アルゴリズム・パズルです。 問題: 表が白で裏が黒の 16 枚のカードがあります。まず、これらを白と黒が 8 枚ずつ連続して見えるように円形に並べます。 そして、連続した 3 枚のカードを裏返していくことにします。適当な位置でこのように反転していくとき…

ふたたび Ruby で 8 queen(関数型プログラミングっぽく)

ここで Ruby で「8 クイーン問題」を解いてみましたが、関数型プログラミングのお勉強に Common Lisp のコード例を移植してみました。参考にしたのはこのサイトです。 実行するとこんな感じです。 ---------- No.1 ...@.... .@...... ......@. ..@..... ....…

ソートの交換回数の最小化(Ruby)

アルゴリズム・パズルです。 問題: 例えば 1~3 の数字が任意に並んだ 3桁の数字を、各桁の入れ替えによってソートする場合、その入れ替えの数が最小になるようにソートしたとします。たとえば 231 なら 231→132→123 で 2回の入れ替えになります。これをすべ…

素数のマトリックス(Ruby)

アルゴリズム・パズルです。 問題: 1 1 3 2 3 3 7 9 7 3桁の異なる素数3つを選びます。これら(例えば 113, 233, 797)を上のように横に行列で並べたとき(行を入れ替えたものは別の行列とみなします)、行列を縦に見て得られる3つの数(ここでは 127, 139,…

グラスの水を半分に(Ruby)

アルゴリズム・パズルです。 問題: すべて大きさのちがう3つのグラス A, B, C があります。その容積は A = B + C, B > C(ただしすべて自然数)で、かつ B と C の値は互いに素とします。 まず、A のグラスに水をいっぱいに入れます。ここから水をどんどん…

ハノイの塔をプログラミングで解く

ハノイの塔とは一種のパズルで、ルールは以下のようです。 3本の杭と、中央に穴の開いた大きさの異なる複数の円盤から構成される。 最初はすべての円盤が左端の杭に小さいものが上になるように順に積み重ねられている。 円盤を一回に一枚ずつどれかの杭に移…

美しい?IPアドレス(Ruby)

アルゴリズム・パズルです。問題。 IPアドレスは例えば 192.168.1.2 のように表せますね。これは2進数で32ビットの数字を、8ビットずつに区切ってさらに10進数で表した形式になっています。 ここで、0~9 のすべての数字が 1度ずつ現れたような IPアドレスで…

並べ替えの繰り返し(Ruby)

アルゴリズム・パズルです。問題。 1~9 のカードを横一列に適当に並べ替えます。そこからスタートして、左端のカードの数字の枚数だけ、左からカードを取って逆順にし、また置き直します。例えば [4, 5, 6, 7, 8, 9, 1, 2, 3] だったら [7, 6, 5, 4, 8, 9, 1…

7セグメントコードの反転(Ruby)

デジタル表示で 0~9 の数字を表示させることを考えます。数字はディスプレイの 7つの場所の on, off で表示することになります。このとき、二つの数字を連続して表示するとして、7つの場所の on, off の切り替わりが出来るだけ少なくなるような順番を考えま…

2枚のカードの間には?(Ruby)

前回のエントリの問題を教えられたサイトに、さらに次のような問題がありました。 1から7の数字を書いたカードが2枚ずつ計14枚ある。そしてこれを1列に並べ,2枚の1の間にはカードが1枚,2枚の2の間にはカードが2枚はさまれていて,同様に,3の間には3枚,4の…