アルゴリズム・パズル

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

ハノイの塔とは一種のパズルで、ルールは以下のようです。 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…

Swift で 8queen 問題を解く

以前 Ruby で「エイト・クイーン」問題を解きましたが、それを Swift に移植してみました。「エイト・クイーン」というのは チェスの盤上に、8個のクイーンを配置する。このとき、どの駒も他の駒に取られるような位置においてはいけない。 https://ja.wikipe…

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

前回のエントリでやったのがおもしろかったので、最初からやってみた。いつもながら Ruby です。 結果。 まあ悪くないのだけれど…。いや、これは苦しみました。最初はソートしてバイナリサーチというアルゴリズムを考えていたのだけれど、バグに悩まされて挫…

paiza Online Hackathon をやってみた

もうとっくに応募は締め切られているけれど、とにかく Ruby でやってみました。 結果。 やったね!コードです。 need = gets.to_i company = gets.to_i number, cost = [], [] company.times {|i| number[i], cost[i] = gets.split.map(&:to_i)} h = {} comp…

結城先生の薬品格納クイズ(Ruby)

「既約分数クイズ」に続いて、結城先生の「薬品格納クイズ」というというのをやってみます。 薬品格納クイズ 問題: 6×2=12個の区画に分かれている薬品箱があります。 ここにA, Bという二種類の薬品を格納します。 ところが、薬品Bは縦や横に隣り合った区画…

「既約分数クイズ」を解く(Ruby, C言語)

ここのところで結城先生の「既約分数クイズ」のことを知りました。結城先生らしい「お話」仕立てですので、是非参照して頂きたいですが、簡単にいうと 問題:正の整数Nが与えられているとき、 以下の条件を満たす既約分数p/qを「すべて」求めるアルゴリズム…

エイト・クイーン(8 queen)問題を Ruby で解いてみる

エイト・クイーン - Wikipedia チェスの盤上に、8個のクイーンを配置する。このとき、どの駒も他の駒に取られるような位置においてはいけない。 チェスの盤面は 8×8 であり、クイーンのコマは前後左右斜めにどれだけでも進むことができます。盤面上に 8つの…

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

人材獲得作戦・4 試験問題ほか: 人生を書き換える者すらいた。 さて試験問題です。 内容は、壁とスペースで構成された迷路が与えられたとき、スタート地点からゴール地点に至る最短経路を求めよ、というものです。 おもしろそうなので Ruby で解いてみまし…

1Ωの抵抗10個で黄金比の値に近づける(Ruby)

問題: 1Ω の抵抗 10個を使い、合成抵抗が黄金比 1.6180339887..Ωにもっとも近づく場合の値を、少数第10位まで求めよ。 aΩ と bΩ の抵抗をつなげる場合、直列つなぎにすれば合成抵抗はたんに a + b Ω になりますが、並列つなぎの場合はそれらの逆数の和の逆…

ナップサック問題(Ruby)

次のような問題があるとします。 学校でクラブ活動をするのに、選んだクラブの人数の合計が 150人以下になるようにするとします。クラブの想定人数とそれが使う敷地面積は次のように与えられています。 クラブを幾つか適当に選ぶとき、必要な敷地面積の総和…

右折禁止(アルゴリズム・パズル)

アルゴリズム・パズルを Ruby で解いてみました。 class TurnLeft class Position def initialize(x, y) @x, @y = x, y end attr_accessor :x, :y def +(dir) Position.new(@x + dir[0], @y + dir[1]) end end class Field def initialize @yoko = Array.new…

いわゆる「スライドパズル(15パズル)」もどきを Ruby で解いてみる

スライドパズルっていうおもちゃがありますよね。4×4 のマス目に空白がひとつあって(残りはコマ)、コマは空白にスライドさせて動かすしかなく、それを特定のパターンに揃えるというものです。ここではルールを少し改変して、特定のマスを別の特定のマスに…

「10分でコーディング」やってみた(Ruby)

10分でコーディング|プログラミングに自信があるやつこい!!はてなブックマーク- 10分でコーディング|プログラミングに自信があるやつこい!! たぶん10分以内にできたと思う。問題は、num_player 人のプレーヤーに deck で与えられたカードを切ると…

「孤独の7」を Ruby で

rscの日記さんのところで、「孤独の7」という虫喰い算を知りました。問題は右の画像のとおりです。ここで回答を募集していたようです。 Ruby で解きました。かかった時間はほぼ 0.1秒です(答えの uniqueness のチェックなし。チェックすると 0.7秒程度)。R…

2抜きを許したストラックアウトの抜き方(Ruby)

1 2 3 4 5 6 7 8 9 ストラックアウトといって 3×3 のボードに玉をぶつけて数字を抜いていく遊びがありますね。その抜き方は何通りあるでしょうといえば、9!(9の階乗)通りとすぐ求められてつまらないので、2抜きを許します。つまり、ひとつの玉で同時に、隣…

スニーカーの靴紐の通し方についての問題(Ruby)

問題: スニーカーに靴紐を通すのに、左右に6個づつ、計12個の穴があるとします。色いろな通し方がありますが、左右の穴に交互に紐を通していった場合、紐が交差してできる点の数の最大値はいくらになるでしょうか。なお、一番上の穴から通し始めて、最後も…

「rscの日記」さんが紹介されていた問題を解く(Ruby)

またまた「rscの日記」さんが紹介されていた問題を Ruby で解いてみました。問題はこちらです。 A~Eの5人はある事業所に勤務する派遣社員である。この5人のある月曜日から金曜日までの出勤状況について次のことがわかっているとき、正しくいえるのはどれ…

不等式の一問題

また rscの日記さんのところからです。もとの問題はこちら。 ある塾のA組からC組までの3つの組には、合計105人の生徒が在籍しており、それぞれの組の生徒数に関して、次のア、イのことがわかっている。 ア B組の生徒数の3倍は、A組の生徒数の2倍より5人以上…

質問投稿サイトの問題を解く

また rscの日記さんのところにあった問題です。おもしろそうなので Ruby で解いてみました。元の問題はこれです。問題をコピペしておきます。 円卓の判断推理 問題 A~E の5人が円卓に等間隔で着席している。5人のうち女性は2人で、この2人の席は隣り合…

google の入社試験

rscの日記さんのところで知りました。 Googleの入社試験です。次の覆面算を解きなさい : IT速報 WWWDOT - GOOGLE = DOTCOM ただし、EとMは交換可能。Ruby で解いてみました。 def to_int(a, b, c, d ,e, f) a * 10 ** 5 + b * 10 ** 4 + c * 10 ** 3 + d * 1…