笹田さんがツイートしておられた。
ホント意味不明。これ実行できるのかと思って試してみた。# よくわからないプログラム
— _ko1 (@_ko1) 2018年2月27日
def foo a
return true if a
else return false
end
$ pry [1] pry(main)> def foo a [1] pry(main)* return true if a [1] pry(main)* else return false [1] pry(main)* end (pry):4: warning: else without rescue is useless => :foo [2] pry(main)> foo true => true [3] pry(main)> foo false => false
なるほど、ここでの else は begin ~ rescue ~ else ~ ensure ~ end の else と解釈されるのか。ちゃんと実行できるのね。
アルゴリズム・パズルです。
問題：
そろばんで例えば「8 + 9」をこの順に計算すると、「8 を入れる」のに玉を 4つ動かし、「9 を足す」のに玉を 2つ動かすので、全部で 6回玉を動かすことになります。また、逆に「9 + 8」の順に計算すると、全部で玉を 8回動かすことになります。このように、同じ答えになる場合でも、玉を動かす回数が異なることがあります。
さて、1 から 10 までの総和をこのようにそろばんで求めるとき、玉を動かす数の最小値はいくらになるでしょうか。
Ruby で解いてみました。
q55.rb
@table = [[0, 1, 2, 3, 4, 1, 2, 3, 4, 5], [0, 1, 2, 3, 2, 1, 2, 3, 4, 1], [0, 1, 2, 3, 2, 1, 2, 3, 2, 1], [0, 1, 4, 3, 2, 1, 2, 3, 2, 1], [0, 5, 4, 3, 2, 1, 4, 3, 2, 1], [0, 1, 2, 3, 4, 1, 2, 3, 4, 5], [0, 1, 2, 3, 2, 1, 2, 3, 4, 1], [0, 1, 2, 3, 2, 1, 2, 3, 2, 1], [0, 1, 4, 3, 2, 1, 2, 3, 2, 1], [0, 5, 4, 3, 2, 1, 4, 3, 2, 1]] def cal(a, b) n1, n2 = a / 10, a % 10 if b == 10 @table[n1][1] else @table[n2][b] + ((n2 + b >= 10) ? @table[n1][1] : 0) end end def solve(before, after, sum, co) if before.empty? if @min > co @min = co p [@min, after] #=>[26, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]] end return end before.size.times do |i| a = before[i] b = co + cal(sum, a) next if b >= @min after1 = after + [a] before1 = before[0, i] + before[i + 1..-1] solve(before1, after1, sum + a, b) end end @min = Float::INFINITY solve([*1..10], [], 0, 0)
答えは 26回ですね。ふつうに 1 から 10 まで順に足すのが最小値を与えるようです（この順だけが最小値を与えるわけではありません。最小値を与える足し方は 614880 通りもあります）。かかった時間は自分の環境でほぼ 4.2秒、solve() 呼び出しの回数は 4090969回です。模範解答とはちがって Array#permutation を使ってはいません。
なお、コード中の after の項はここでは本質的に必要ないので、これをカットすると多少高速化し、実行時間は 3.3秒ほどになります。
ちなみに、最大値は 42 で、例えば [3, 2, 4, 1, 5, 8, 7, 9, 6, 10] の順に足すとこれが得られます。なるほど、5 を作っていくと大きくなるようです。26 と 42 とは結構差があるものですね。
プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問
ブログにスターを頂いて、上のサイトを知りました。オリジナルの様々な迷路が出題されている、すばらしくおもしろそうなブログです。皆さんも御覧になってはいかがでしょうか？
…とは別にステマでも何でもないのですが、そこで「絶対左折禁止」という迷路が出題されているのが目に止まりました。こんなのです。リンク先を御覧下さい。
とまたよくない病が…。Ruby で解いてやろうというのですね。もしかしたら作者様には失礼に当たるかもしれません。であればどうかお許しください。
ルールとしては、もちろん交差路では左折してはいけませんが（直進と右折のみ）、角でも左に曲がってはいけないというものです。さて、どう解くか。迷路を交差路と角のつながりとして抽象化しようかと思いましたが、どうも面倒で、えいテキストエディタで入力だ！ ということにしました（笑）。これがそうです。
maze_never_turn_left.txt
0000000000000000 00000000000ぽちぽちと手作業で入力しました。
0 0 0 0 0 0 0
00S 0000000000000000 0 0
0 0 0 0 000000
0 0 000000 0 0
0 0000 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0000 00000 0 0 0 0
0 0 0 00000000000 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0000000000 0 00000000000
0 0 0 0 0 0 0
000000 00000000 00000000000
0 0 0 0 0
0 0 0 0 0
0 000000000000000000 00000000
0 0 0 0 0 0 0 0 0
0 000000 0 000000000000 0
0 0 0 0 0 0
0 00000000000000000 G00
0 0 0 0 0 0
0 0 0 0 0 0
00000000 0000000000000000000
とりあえず迷路はデータ化しました。あとは解くだけですね。コードはこんな風に出来上がりました。何の準備もなくいきあたりばったりにコーディングしたので、途中でかなりおかしなことをしていたりしました。完成させるのに数時間もかかってしまいました。
maze_never_turn_left.rb
class SolveMaze open("maze_never_turn_left.txt") {|io| @@field = io.readlines} @@field.map! {|f| " " + f.chomp + " "} a = [" " * @@field[0].size] @@field = a + @@field + a class Position def initialize(x, y, dir = nil, parent = nil) @x, @y = x, y @kind = get[y][x] @dir = dir @parent = parent end attr_reader :x, :y, :dir, :parent, :kind def neighbor result = [] [[0, -1], [1, 0], [0, 1], [-1, 0]].each_with_index do |step, i| x = @x + step[0] y = @y + step[1] result << Position.new(x, y, i, self) if get[y][x] != " " end result end def get SolveMaze.class_variable_get(:@@field) end def finish result = [[@x, @y]] a = parent field = Marshal.load(Marshal.dump(get)) loop do result << [a.x, a.y] break if a.kind == "S" field[a.y][a.x] = %w(↑ → ↓ ←)[a.dir] a = a.parent end #puts result.reverse.flatten.join(",") #GIF画像作成用 field.map {|x| x.gsub!("0", " ")} field.each {|x| puts x} #exit end def check a = self loop do a = a.parent return true if a.kind == "S" return false if a.x == @x and a.y == @y and a.dir == @dir end end end def initialize n = @@field.join.index("S") l = @@field[0].length @queue = Position.new(n % l, n / l).neighbor end def go while (po = @queue.shift) pos = po.neighbor.reject {|a| a.dir == (po.dir + 2) % 4} #あと戻り以外に行ける場所 pos.each do |nxt| next if (po.dir - nxt.dir) % 4 == 1 #左折禁止 if nxt.kind == "G" nxt.finish elsif nxt.kind == "0" and (pos.size < 2 or nxt.check) @queue << nxt end end end end end SolveMaze.new.go
Position クラスは現在の位置の他、場所の種類（@kind）、どちらの方向から来たのか（@dir）とひとつ前の位置（@parent）の情報を保持しています。SolveMaze#go がメインループ、Position#check は無限ループしないかチェックしています。Position#neighbor は現在位置の周囲の情報を与えます。
結果です。解くのにかかった時間は自分の環境で 0.1秒未満です。
↑→→→→→→→→→→→→ ↑→→→→→→→→→→正直いってちょっとわかりにくいですね。なので GIFアニメを作ってみました。
↑ ↓ ↑ ↓
←←S ↑→→→↓→→→→→→→ ↓
↑ ↓ ↓ ↓
↑ ↓→→→ ↓ ↓
↑ ↓ ↓ ↓ ↓
↑ ↓ ↓ ↓ ↓
↑ ↓ ↓ ↓ ↓
↑ ↓←←←←←←↓→→→ ↓
↑ ↓ ↓ ↑ ↓ ↓
↑ ↓ ↓ ↑ ↓ ↓
←←←←↓ ↓ ←←←↓→→→→ ↓
↑ ↓ ↓ ↑ ↓ ↓
↑→→→→→ ←←←←←←←↓ ←←←←←←←←←←↓
↑ ↓ ↓ ↑ ↓
↑ ↓ ↓ ↑ ↓
↑ ↑→→↓→→→→→↓→→→→→→→→ ↑→→→↓→→→
↑ ↑ ↓ ↓ ↑ ↓ ↑ ↓ ↓
↑ ←↑→→→→ ↓ ←←←←↓ ←←←←↓ ↓
↑ ↑ ↓ ↓ ↓
↑ ←←←←←←←←↓ G←↓
↑ ↓
↑ ↓
←←←←←←←↓
左折禁止ではない、任意の迷路を解くように改変するのも容易です。左折禁止を判断している一行を削除すればよろしい。ただし、すべての解を求めるのが冗長ならば、Position#finish メソッドの終わりに exit を追加すればよいです。その際はひとつの最短ステップの解を出力して終了します。なお、いまのままだと同じ地点を通っても向きがちがえば許容されるので、同じ地点を通らないようにするには Position#check メソッドの判定条件を変える必要があります。
作者様、楽しい迷路をありがとうございました！
迷路の作者様にブログで取り上げて頂きました。ありがとうございます。とてもうれしいです。
せっかくなのでアルゴリズムについて少しだけ書いておきましょう。基本的なことなので、当り前だという方はスルーして下さい。
迷路を解くにはまず解の経路をどう表現するかです。上のコードでは Position クラスが位置の情報を持っています。そして、それが tree 状の「経路」を表現しているというのは、Position クラスのインスタンスがひとつ前の位置の情報（@parent）を持っているので可能になります。@parent をずっと遡っていけば、スタート地点までたどり着くということですね。なので、探索の数だけ Position クラスのインスタンスが生成されることになります。無駄といえば無駄をしていますが、実際にこの程度ならば大した数ではないですし、コードが簡単になります。もちろん、必ずこのように経路を表現しなければならないということはありません*1。
そして、経路の「探索」ですが、一般に tree 状の探索を行うには、基本的に「深さ優先探索」と「幅優先探索」の二種類があります（これだけということではありません）。一般に、「深さ優先探索」の方が高速かつ省メモリであるとされ、tree をいきなり深く潜っていきます。それに対して「幅優先探索」は tree を探索開始地点から近い順に探索していきます。そこで迷路の探索ですが、すべての解を調べるならばいずれの方法でも同じ結果が出るのがふつうです。ただし、最短経路を探す場合は、「幅優先探索」を使うことになります。また、すべての解を調べる場合でも、「幅優先探索」を使うと経路の短い順に結果が出力されます。なので、上では「幅優先探索」で実装されています。ただし、これを「深さ優先探索」に変更するのはじつに簡単で、上のコードなら SolveMaze#go メソッドの po = @queue.shift の shift を pop に書き換えるだけなのです。以上のことはぐぐればいくらでも解説があると思います。
どうでしょうか。あと、上のコードが多少でも簡潔に書けているとすれば、僕の好きな Ruby 言語の力も大きいと思います。というか、Ruby でコーディングするのが好きで、題材を探しているようなものです。皆さんも Ruby、どうですか？（笑）
*1:例えば、迷路のマップ（上のコードなら @@field）に書き込んでいくとかは、誰でもすぐに思いつくでしょう。ただし、これだと複雑な条件をあらわすのがむずかしくなったりで、一長一短です。ちなみに上のコードでは、@@field の値は一切変更していません。
こんなです。左が 3次、右が 5次です。
描画には自作の Gem 'oekaki' を使いました。最新バージョンでタートルグラフィックスをサポートしています（参照）。
oekaki | RubyGems.org | your community gem host
GTK+でお絵かきしてみた（Ruby） - Camera Obscura
コード。
require 'oekaki' Oekaki.app width: 420, height: 420, title: "Turtle" do draw do clear t = Oekaki::Turtle.new t.color(0, 0xffff, 0) drawing = lambda do |n, p1, p2| v1 = p2 - p1 v2 = Vector[-v1[1], v1[0]] if n == 1 l = v1.norm / sqrt(2) t.move(*p1.to_a) t.dir = v1.normalize t.left(45) t.forward(l) t.right(90) t.forward(l) else drawing[n - 1, v3 = p1 + v2 / 2, p1] drawing[n - 1, v3, v4 = v3 + v1 / 2] drawing[n - 1, v4, v5 = v4 + v1 / 2] drawing[n - 1, p2, v5] end end drawing[5, Vector[-200, -200], Vector[200, -200]] end end
ゴシック・フリーズ（p.102~）。それぞれ 1, 2, 3, 6次。
コード。
require 'oekaki' Oekaki.app width: 420, height: 420, title: "Turtle" do draw do clear t = Oekaki::Turtle.new t.color(0xffff, 0x45ff, 0) #orangered t.move(-200, -200) t.left(45) drawing = lambda do |n, l| if n == 1 t.forward(l) else drawing[n - 1, l / 3] t.left(90) drawing[n - 1, l / 3] t.right(90) drawing[n - 1, l / 3] t.right(90) drawing[n - 1, l / 3] t.left(90) drawing[n - 1, l / 3] end end drawing[6, 400 * sqrt(2)] end end
アニメーション版も作ってみました。コードはこちら。
タートルグラフィックスによるその他の再帰曲線については、こちらもどうぞ。
アルゴリズム・パズルです。
問題：
上のような規則があります。縦が 5cm、横が 6cm の長方形の場合、A から B までの最長経路は何 cm でしょうか。
Ruby で解いてみました。
q50.rb
W, H = 6, 5 def yoko?(y) @yoko[y].inject(:+) < 2 end def tate?(x) @tate[x].inject(:+) < 2 end def search(x, y, co) if x == W and y == H @max = co if co > @max return end if x < W and yoko?(y) @yoko[y][x] += 1 search(x + 1, y, co + 1) @yoko[y][x] -= 1 end if x > 0 and yoko?(y) @yoko[y][x - 1] += 1 search(x - 1, y, co + 1) @yoko[y][x - 1] -= 1 end if y < H and tate?(x) @tate[x][y] += 1 search(x, y + 1, co + 1) @tate[x][y] -= 1 end if y > 0 and tate?(x) @tate[x][y - 1] += 1 search(x, y - 1, co + 1) @tate[x][y - 1] -= 1 end end @tate = Array.new(W + 1) {Array.new(H, 0)} @yoko = Array.new(H + 1) {Array.new(W, 0)} @max = 0 search(0, 0, 0) puts @max #=>25
25 cm が答えです。自分の環境で 3.1 秒かかりました。ループの回数は 1513353 回です。
解法はごく素直に、再帰を使った深さ優先探索です。
ルートは全部で 805通りあります。すべての画像を出力するコードはこちら。 Gem 'cairo' を使っています。下は GIF化（参照）した画像です。
プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問
アルゴリズム・パズルです。
問題：
表が白で裏が黒の 16 枚のカードがあります。まず、これらを白と黒が 8 枚ずつ連続して見えるように円形に並べます。
そして、連続した 3 枚のカードを裏返していくことにします。適当な位置でこのように反転していくとき、すべてのカードが白と黒の互いちがいになるような手順の回数は、最小で何回で済むでしょうか。
Ruby で解いてみました。
q49.rb
mask = [14, 28, 56, 112, 224, 448, 896, 1792, 3584, 7168, 14336, 28672, 57344, 49153, 32771] 15.times do |i| mask.combination(i + 1) do |m| field = 0b0000000011111000 m.each do |x| field = field ^ x if field == 0b1010101010101010 p [i + 2, m] #=>[8, [14, 28, 448, 896, 14336, 28672, 57344]] exit end end end end
答えは 8 回ですね。かかった時間は自分の環境で 0.084 秒でした。ループの回数は 59669 回です。
考え方としては、ビット演算で XOR を取ればビットが反転することを使っています。それから、ビットの反転の順序は答えに関係がないことがポイントです。円形というのは、一箇所を固定して横一列で考えればいいです。なので、始める前に適当に1箇所あらかじめ反転させておきます。
XOR でビットの反転というのは、こういうことですね。
[1] pry(main)> (0b01010101 ^ 0b111).to_s(2) => "1010010"
演算 ^ で XOR を取ります。01010101 の右3桁が反転しているのがわかります。
プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問
Object#method はメソッドをオブジェクト化してくれるのですよね。だから、こんな奇妙なブロックなしの世界が…。
[1] pry(main)> putout = method(:p) => #<Method: Object(Kernel)#p> [2] pry(main)> a = [1, 5, 4, -2, 10, 3] => [1, 5, 4, -2, 10, 3] [3] pry(main)> a.each(&putout) 1 5 4 -2 10 3 => [1, 5, 4, -2, 10, 3] [4] pry(main)> a.each_cons(2, &putout) [1, 5] [5, 4] [4, -2] [-2, 10] [10, 3] => nil
Kernel.#p もこうしてブロックなしで使えてしまう…。
上はこの挙動が元になっています。
[5] pry(main)> putout.call("Tokyo") "Tokyo" => "Tokyo"
例えば a.each(&putout) は、call() が自動的に補われて a.each {|x| putout.call(x)} と同等になります。
なお、よく使われるイデオムである例えば%w(a b c).map(&:upcase) というのは、to_proc.call() が自動的に補われて %w(a b c).map {|x| :upcase.to_proc.call(x)} と同等になります。よく似ていますね。さらにいうと、:upcase.to_proc.call(x) というのは、x.upcase と同等です。うーん、面倒だ。
