アルゴリズム・パズル

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

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の…

2つのバケツ問題(Ruby)

反復深化/アルゴリズム講座 おもしろそうな問題を見つけました。 8リットルと5リットルのふたつのバケツを使って1リットルの水を最短手順で川からくみあげて下さい。 http://www.ic-net.or.jp/home/takaken/pz/index3.html Ruby で解いてみました。それぞれ…

飛車と角の利き(Ruby)

問題: 飛車と角を将棋盤(9×9)の上にひとつづつおきます。このとき、飛車か角によって(相手の)駒が取られる位置を、飛車と角の「利き」ということにします。 飛車の「利き」の上に角があるとき、その先の飛車の「利き」は(角にさえぎられて)ありません…

paiza オンラインハッカソン vol.6 をやってみた

これも挑戦。使用言語は Ruby。どれも超簡単なので簡潔に。 六村リオ 問題。結果。コード。 operations = [] gets.to_i.times {operations << gets.split.map(&:to_i)} water = coffee = 0.0 operations.each do |op, q| case op when 1 then water += q whe…

paiza オンラインハッカソン vol.5 をやってみた

使用言語は Ruby です。画像クリックで詳細が出ます。 手紙の暗号を解読 簡単。コード。 st = gets result = "" 0.step(st.length - 1, 2) {|i| result += st[i]} puts result 会社の入社試験 超簡単。こんな入社試験、ある筈がないですね。コード。 num = g…

paiza オンラインハッカソン vol.4 をやってみた

またまた挑戦してみました(ヒマ人^^;)。使用言語は Ruby です。画像クリックで詳細が出ます。 ミッション1 こりゃ簡単すぎるだろう。コード。 data = [] gets.to_i.times {data << gets.to_i} puts data.inject(&:+) ミッション2 これも超簡単。コード。 d…

paiza オンラインハッカソン vol.2 をやってみた

またまた Ruby でやってみました。 とりあえず何の工夫もないもの 誰でもすぐに考えそうな方法でやってみました。つまりは総当り。 全然ダメですね。詳しい結果はこちら。コード。 height, width = gets.split.map(&:to_i) @window = [] height.times {@wind…