クロスワードパズルを作成せよ！（Ruby）

アルゴリズム・パズルです。
　

クロスワードを作る場合、空白と黒マスについて次のルールがあります。

• 黒マスは縦横に連続しない。
• 黒マスによって盤面が分断されてはいけない。

黒マスルール - Wikipedia

これを「黒マスルール」といいます。
　
さて、縦 5、横 6 のクロスワードパズルを作るとき、空白と黒マスの配置の仕方（盤面）は何とおりあるでしょうか。

　
Ruby で解いてみました。コード。
q67.rb

X, Y = 6, 5
@field = Array.new(L = X * Y, 0)    #盤面。最初はすべて空白
@co = 0

#盤面が分断されていないか？
def check
  area = @field.dup
  set = ->(n) {
    area[n] = 2
    [-1, 1, X, -X].each do |dir|
      next if dir == -1 and (n % X).zero?
      next if dir ==  1 and n % X == X - 1
      next if dir ==  X and n >= L - X
      next if dir == -X and n < X
      m = n + dir
      set.(m) if area[m].zero?
    end
  }
  set.(area.find_index(0))
  !area.find_index(0)
end

def try(i)
  if i >= L
    @co += 1 if check
  else
    #空白をセットしてひとつ先へ
    try(i + 1)
    #可能であれば黒マスをセットしてひとつ先へ
    if ((i % X).zero? or @field[i - 1].zero?) and (i < X or @field[i - X].zero?)
      @field[i] = 1
      try(i + 1)
      @field[i] = 0
    end
  end
end

try(0)
puts @co

結果。

$ time ruby q67.rb
149283

real	0m9.822s
user	0m9.788s
sys	0m0.000s

　
結構むずかしかったですね。盤面の小さい場合で確かめながらコーディングしてようやくできました。
　

プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問

浮動小数点演算の謎

30年前の名著「数値計算の常識」を読んでたらBASICで0.01を10000回足したら100.003になるとか書いてあった。まあ昔のPCなんてそんなものかなと思いながら、Visual Studio 2017で試してみたら同じ結果だったｗ pic.twitter.com/HBwJhlhZjc

— ｍはげ (@Tw_Mhage) 2018年11月17日

Ruby 2.5.1 でやってみたらこうなりました。

a = 0
10000.times {a += 0.01}
puts a    #=>100.00000000001425

笑。

しかし、Ruby には BigDecimal がある。

require 'bigdecimal'

a = BigDecimal("0")
10000.times {a += BigDecimal("0.01")}
puts a.to_s("F")    #=>100.0

きちんと正確に計算できました。
　

追記

Rational を使ってもよいね。

a = 0
10000.times {a += 1/100r}
puts a.to_f    #=>100.0

Ruby/SDL でランダム・ウォーク

Ruby/SDL（参照）を使ってランダム・ウォークしてみました。Linux Mint 19、Ruby 2.5.1 で確認しました。

コード。
sdl_random_walk.rb

require_relative 'sdl_draw'

WindowWidth = 300
FieldWidth = 50.0
N = 30

class Agent
  def initialize(ob)
    @x = @y = 0
    @slot = ob
  end
  
  def next_step
    @x += rand(-0.5..0.5)
    @y += rand(-0.5..0.5)
  end
  
  def paint
    ratio = WindowWidth / FieldWidth
    x = WindowWidth / 2 + @x * ratio
    y = WindowWidth / 2 - @y * ratio
    @slot.draw_circle(x, y, 5, @slot.color(255, 0, 0), true, true)
  end
end

draw(WindowWidth, WindowWidth) do
  agents = (1..N).map { Agent.new(self) }
  
  loop do
    fill_rect(0, 0, WindowWidth, WindowWidth, color(0, 0, 0))
    agents.each(&:next_step)
    agents.each(&:paint)
    flip
    sleep(0.05)
  end
end

sdl_draw.rb に関してはここを参照して下さい。簡単なライブラリみたいなものです。

平方根（ルート）を計算して遊ぶライブラリを作った（Ruby）

遊びで平方根（二乗根）を扱うクラス（Root）を Ruby で書いてみました。三乗根とかそれ以上は扱えません（笑）。

コードは下（Gist）にあります。
平方根の計算 · GitHub

オブジェクトの生成。Integer, Rational, Float のルートが扱えます。Root.new(n) または Root.new(a, b) でも、 Root(n) または Root(a, b) でもどちらでも OK です。分数（Rational）のルートを取った場合など、有理化は自動的になされます。Float の場合は to_r してルートを取ります。また、根号の外へ出せる数がある場合は自動的に外へ出します。

$ pry
[1] pry(main)> require_relative "root"
=> true
[2] pry(main)> Root.new(3)
=> Root(3)
[3] pry(main)> Root(7, 3)
=> (7)Root(3)
[4] pry(main)> Root(1/3r)
=> (1/3)Root(3)
[5] pry(main)> Root(2.5)
=> (1/2)Root(10)
[6] pry(main)> Root(12)
=> (2)Root(3)
[7] pry(main)> Root(4)
=> (2)Root(1)

根号の中はかならず自然数であり、係数は整数あるいは分数（Rational）です。
　
係数と根号の中身を取り出すことができます。

[4] pry(main)> x = Root(12)
=> (2)Root(3)
[5] pry(main)> x.content
=> 3
[6] pry(main)> x.coefficient
=> 2

　
掛け算（*）、割り算（/）、累乗（**）ができます。マイナスの単項演算子が使えます。

[2] pry(main)> a = Root(3)
=> Root(3)
[3] pry(main)> a * Root(6)
=> (3)Root(2)
[4] pry(main)> a * Root(3)
=> 3
[5] pry(main)> a * Root(1/5r)
=> (1/5)Root(15)
[6] pry(main)> a / Root(6)
=> (1/2)Root(2)
[7] pry(main)> a * 5
=> (5)Root(3)
[8] pry(main)> (2/7r) * a
=> (2/7)Root(3)
[9] pry(main)> a / 1.5
=> (2/3)Root(3)
[10] pry(main)> a ** 2
=> 3
[11] pry(main)> a ** 3
=> (3)Root(3)
[12] pry(main)> 3 / a
=> Root(3)
[13] pry(main)> 2 ** a
=> 3.3219970854839125
[14] pry(main)> a ** 1.5
=> 2.2795070569547775
[15] pry(main)> -a
=> (-1)Root(3)

　
計算できる場合に限り、足し算と引き算ができます。

[2] pry(main)> a = Root(3)
=> Root(3)
[3] pry(main)> a + Root(12)
=> (3)Root(3)
[4] pry(main)> a - Root(3) * 2
=> (-1)Root(3)
[5] pry(main)> 4 + Root(9)
=> 7
[6] pry(main)> 3.0 - Root(4)
=> 1.0
[7] pry(main)> Root(2) + 3.0
=> 4.414213562373095
[8] pry(main)> a + Root(5)
TypeError: Root(5) (Class Root) can not be used at this place.
from /home/***/Documents/Ruby/root.rb:197:in 'error'
[9] pry(main)> 3 - Root(5)
TypeError: (-1)Root(5) (Class Root) can not be used at this place.
from /home/***/Documents/Ruby/root.rb:224:in `error'

　
比較ができます。定義されている演算子は、< > <= >= == <=> です。

[1] pry(main)> Root(5) > Root(3)
=> true
[2] pry(main)> Root(3) > 2
=> false
[3] pry(main)> Root(3) <= 2
=> true
[4] pry(main)> Root(4) == 2
=> true
[5] pry(main)> Root(5) == Root(3)
=> false
[6] pry(main)> Root(3) > 1.7
=> true
[7] pry(main)> 2 < Root(5)
=> true
[8] pry(main)> 3 <=> Root(10)
=> -1

　
なのでソートもできます。

[2] pry(main)> a = [3.0, -1, Root(3), Root(12), Root(1/5r), 6.5]
=> [3.0, -1, Root(3), (2)Root(3), (1/5)Root(5), 6.5]
[3] pry(main)> a.sort
=> [-1, (1/5)Root(5), Root(3), 3.0, (2)Root(3), 6.5]

　
プラスの単項演算子は、オブジェクトが整数なら Integer に変換します。そうでなければ self をそのまま返します。

[2] pry(main)> a = Root(4)
=> (2)Root(1)
[3] pry(main)> +a
=> 2
[4] pry(main)> +Root(5)
=> Root(5)

なお、計算をする場合はこの変換が自動でなされます。

Float への変換は to_f。Integer への変換 to_i は内部で to_f.to_i になります（小数点以下切り捨て）。Integer, Rational, Float からのオブジェクトの生成は to_root。

[5] pry(main)> Root(7).to_f
=> 2.6457513110645907
[6] pry(main)> Root(7).to_i
=> 2
[7] pry(main)> 2.to_root
=> (2)Root(1)
[8] pry(main)> 1.5.to_root
=> (3/2)Root(1)

　
計算例。

[7] pry(main)> Root(6) * Root(1/3r) + 8 / Root(2)
=> (5/1)Root(2)
[8] pry(main)> Root(60) / Root(3/10r)
=> (10/1)Root(2)

　
例えばここのほとんどの計算ができます。

[2] pry(main)> Root(180)
=> (6)Root(5)
[3] pry(main)> Root(50) + Root(18)
=> (8)Root(2)
[6] pry(main)> Root(7, 3) - Root(27)
=> (4)Root(3)
[7] pry(main)> Root(5, 2) * Root(3, 2)
=> 30
[8] pry(main)> Root(4, 3) * Root(2, 5)
=> (8)Root(15)
[9] pry(main)> Root(4, 6) / Root(2, 2)
=> (2/1)Root(3)
[10] pry(main)> Root(4, 30) * Root(3, 21) / Root(6, 14)
=> (6/1)Root(5)
[11] pry(main)> 2 / Root(3)
=> (2/3)Root(3)
[12] pry(main)> Root(3) / Root(2, 7)
=> (1/14)Root(21)

作っていてなかなか楽しかったです。

31ゲーム（Go言語）

「たけしのコマ大数学科」の問題をいろいろ Ruby で解いているときに、こんな問題がありました。

問題：
１から６までのトランプ２４枚を使い、２人が交互に１枚ずつ取り、２人の取ったカードの合計を先に３１にした方が勝ち、というゲームをする。（31を超えたら負け。）
　
このゲームで先手が勝つためには始めに何を取ればよいか。

（問題の書いてあるサイトはここです。元記事に感謝します。）

「先手が勝つためには始めに何を取ればよいか」とあるように、このゲームは先手必勝です。ちなみにこの問題はここで Ruby で解いています。

で、実際にこのゲームをコンピュータ相手に対戦するためのプログラムを組んでみました。本当はこれも Ruby で書きたかったのですが、コンピュータの思考時間の関係で Ruby では（自分のスキルでは）無理だったので、Go で書いてみました。ソースコードはここにあります。
31ゲーム · GitHub
　
あなたが先手なので、先手必勝ということはわかっていますから、やり方によっては必ずあなたが勝てます。しかし、コンピュータ側は完璧な対応をしてくるので、ひとつでも手をまちがえれば絶対にコンピュータには勝てません。こんな感じです。

$ go build thirty_one_play.go
$ ./thirty_one_play

**第1手目**
合計： 0
カードを選んで下さい（1~6）：　[4 4 4 4 4 4]6

**第2手目**
---あなたの負けは確定しています
コンピュータの手は 4 です

**第3手目**
合計： 10
カードを選んで下さい（1~6）：　[4 4 4 3 4 3]4

**第4手目**
---あなたの負けは確定しています
コンピュータの手は 3 です

**第5手目**
合計： 17
カードを選んで下さい（1~6）：　[4 4 3 2 4 3]2

**第6手目**
---あなたの負けは確定しています
コンピュータの手は 5 です

**第7手目**
合計： 24
カードを選んで下さい（1~6）：　[4 3 3 2 3 3]1

**第8手目**
コンピュータの手は 6 です
合計 31 で、あなたの負けです！

こんな風に、あなたが一回でもミスをすると「あなたの負けは確定しています」と出ます。コンピュータのくせに、なまいきですね。なお、カードを選ぶところの例えば「[4 4 4 3 4 3]」というのは、左から順に 1~6 のカードの残りの枚数を表しています（この例の場合だと、4 と 6 のカードがそれぞれ 3 枚づつ残っていて、残りのカードはすべて 4 枚残っているということです。）

じつのところ、なかなか勝てないと思います。是非必勝法を編み出してみて下さい！

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

marginalia.hatenablog.com
marginalia.hatenablog.com
marginalia.hatenablog.comいまこちらの記事で挑戦中です。「たけしのコマ大数学科」については Wikipedia でどうぞ。

問題例です。

10人が円卓に座って1人ずつ握手をするとき、全員の手が交差しないように握手する仕方は全部で何通りあるか？

1～1000の数字が振られている1000個の電球がある。すべてOFFの状態から始めて、1回目の操作で1の倍数の電球のスイッチのON/OFFを切り替え、2回目の操作では2の倍数の電球のON/OFFを切り替える。
　このように、n回目の操作でnの倍数の電球のON/OFFを切り替える操作を、1000回目までおこなったとき、最後にONの状態の電球の数は何個か。

直径ＡＢの円とＡの地点に点Ｐがある。直径（線分）ＡＢが円に沿って等速で一回転する間に点ＰもＡからＢへ等速で移動する。このときの点Ｐの軌跡を書きなさい。

連続数字をハイフンでつなぐ（Ruby）

既に更新はされていませんが、僕はブログ「hp12c」をよく読んでいます。Ruby 好きには楽しいですね。

そこで、「Rubyで連続数字をハイフンでつなぐよ」というエントリがありました。元ネタはここということです。やることは要するに、「スペース区切りの数字列を、数字が連続する場合にその箇所をハイフンにする」ということです。

"1 2 3" => "1-3."
"1 2 3 5 7 8" => "1-3, 5, 7-8."
"1 3 4 5 7" => "1, 3-5, 7."

こんな感じ。で、元ネタのも含めていろいろ Ruby の便利メソッドを使った華麗な回答がいくつもあるのですが、ふつうにというか、あんまり便利メソッドを使わない素直な回答を考えてみました。

こんな感じになりました。

def hyphenize(st)
  ar = st.split.map(&:to_i)
  compress = ->{
    result = ar.first.to_s
    i = 0
    i += 1 while ar[i].succ == ar[i + 1]
    result += "-" + ar[i].to_s if i.nonzero?
    ar = ar.drop(i + 1)
    result
  }
  str = ""
  str += compress.() + ", " until ar.empty?
  str[0..-3] + "."
end

ちょっと長いし華麗でも何でもないですけれど、まあ素直だと思います。是非リンク先の凝った回答たちも見てみて下さい。
追記：　クロージャの機能を使って書き換えてみました。変数ar がクロージャcompress.() に保持されています。

リンク先の回答例の中では、smileruby さんのこれが特に凝っていると思います。ただし、掲載されたコードは Ruby 2.5.1 では動かないので、多少変更しました。

def hyphenize(str)
  nums = str.scan(/\d+/).map(&:to_i).sort
  prev = nums.first
  nums.slice_before do |e|
    prev, prevprev = e, prev
    prevprev.succ != prev
  end.map {|e| e.minmax.uniq.join('-')}.join(', ') + '.'
end 

slice_before とか minmax.uniq.join('-') とか、凝っていますねえ。僕は思わずリファレンス・マニュアルを調べましたよ。
　

おまけ

上記事とは関係ないけれど、その smileruby さんのブログを読んでいたらすごい FizzBuzz を発見。これは今まで見た中の（Ruby での）最短じゃないか。

1.upto(100){|i|puts"#{[:Fizz][i%3]}#{[:Buzz][i%5]}"[/.+/]||i}

記事はこちら。わかるまでしばらく考えましたよ。

追記。さらに過去のブログ記事を読んでいたら、これよりも短いのも可能らしい（参照）。ひゃー、すごい世界だな。