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

1	2	3
4	5	6
7	8	9

ストラックアウトといって 3×3 のボードに玉をぶつけて数字を抜いていく遊びがありますね。その抜き方は何通りあるでしょうといえば、9!（9の階乗）通りとすぐ求められてつまらないので、2抜きを許します。つまり、ひとつの玉で同時に、隣接した 2つを抜くことを許すわけです。ただし、真ん中の 5は同時に抜くことはできません。さて、この場合の抜き方は何通りでしょう。

Ruby で解くとこんな感じです。

A = (1..9).to_a
Hits = A.inject([]) {|r, a| r << [a]} +
   [[1, 2], [2, 3], [3, 6], [6, 9], [9, 8], [8, 7], [7, 4], [4, 1]]

#玉が当たれば false、外れれば true を返す
def check(rest, hit)
  hit.each {|i| return true unless rest.include?(i)}
  false
end

def throw(rest)
  return @h[rest] if @h[rest]
  return 1 if rest.empty?
  sum = 0
  Hits.each do |hit|
    next if check(rest, hit)
    sum += throw((rest - hit).sort)
  end
  @h[rest] = sum
end

@h = {}
puts throw(A)    #=>798000

798000通りと求められます。毎度おなじみの（？）深さ優先探索ですね。いわゆるメモ化をしないと現実的な時間で求められません。

下での模範解答はさらに短いです。すごいなあ。

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

Python に連立方程式を解かせる

定点を通る球の接平面 - オベリスク備忘録
上では手計算で解いたのですが、Python で機械的に解けるようなので。Sympy というライブラリを使っています。

おお、すごい。これ、ライブラリはどうやっているのかな。

※参考
Pythonを使って一瞬で連立方程式を解く - Qiita
3.2. Sympy : Python での代数計算 — Scipy lecture notes

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

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

Ruby で解いてみました。２重の深さ優先探索で求めています。

class ShoeString
  def initialize(left, right)
    @left = left
    @right = right
  end
  attr_reader :left, :right
end

def left_set(left, right, pattern)
  if pattern.size == 10
    @patterns << pattern + [ShoeString.new(left.last, 1)]
  else
    ((2..6).to_a - right).each do |hole_r|
      right_set(left, right + [hole_r], pattern + [ShoeString.new(left.last, hole_r)])
    end
  end
end

def right_set(left, right, pattern)
  ((1..6).to_a - left).each do |hole_l|
    left_set(left + [hole_l], right, pattern + [ShoeString.new(hole_l, right.last)])
  end
end

@patterns = []
left_set([1], [], [])

def cross?(a, b)
  return false if a.left == b.left
  a, b = b, a if a.left > b.left
  a.right > b.right
end

max = 0
@patterns.each do |pa|
  counter = 0
  pa.combination(2) {|a, b| counter += 1 if cross?(a, b)}
  max = counter if max < counter
end
puts max    #=>45

これを実行すると 45が最大値になります。結構ありますね。

なお最大値を与えるパターンのひとつは以下です。

[#<ShoeString:0x00556c44c322a0 @left=1, @right=6>, #<ShoeString:0x00556c44c32188 @left=2, @right=6>,
 #<ShoeString:0x00556c44cb2ec8 @left=2, @right=5>, #<ShoeString:0x00556c44cb2db0 @left=3, @right=5>,
 #<ShoeString:0x00556c44cba920 @left=3, @right=4>, #<ShoeString:0x00556c44cba808 @left=4, @right=4>,
 #<ShoeString:0x00556c44cb9f98 @left=4, @right=3>, #<ShoeString:0x00556c44cb9e80 @left=5, @right=3>,
 #<ShoeString:0x00556c44cb9d68 @left=5, @right=2>, #<ShoeString:0x00556c44cb9c50 @left=6, @right=2>,
 #<ShoeString:0x00556c44cb9bd8 @left=6, @right=1>]

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

野良 Gem 'Utils'

RubyGems.org には上げていませんが、Bundler を使って GitHub からインストールできる Gem（野良Gem）です。

Gemfile に

gem "utils", github: 'obelisk68/utils'

を追加して、$ bundle install でインストールされます。詳細は下。
GitHub - obelisk68/utils
アップデートは $ bundle update utils。
　
　

この Gem の使い方

require 'bundler/setup'
require 'utils'

使い方というか、いつも僕が使っているコードの寄せ集めです。自分用。

Utils.imgexist?("http://www.ninjintei.jp/onetyan/image1203.jpg")    #=>[1016, 1476]

で url の先が画像かどうかを判断します。画像が存在すればそのサイズが配列で返り、存在しなければ nil が返ります。

"http://www.ninjintei.jp/onetyan/image1203.jpg".imgsuffix    #=>".jpg"

は String#imgsuffix で、文字列の最後が画像の識別子ならそれを返し、そうでなければ空文字列を返します。

Utils.getfile(url, "image.jpg")

は url の先をダウンロードします。後の引数は保存されるファイル名です。バイナリ・ファイルも DL 可能です。

[2, 3..5, ["a", "b"]].nest_loop {|i, j, k| print "#{[i, j, k]}  "}; puts

は簡単に多重ループを作ります。ここを参照。

p "327865".pickup(2, nil)    #=>"7865"
p [3, 2, 7, 8, 6, 5].pickup(-1, -4, -1)    #=>[5, 6, 8]

は Python のスライスの Ruby 実装です。ここを参照。

※追記
さらに機能を追加しました。

p "12345678".separate(3)

は String#separate(n) で、文字列をあらゆる組合せで n 分割し、すべての組合せを配列に入れて返します。ここを参照。（※追記　ブロックがある場合はそれを実行、ない場合は Enumerator を返すようにしました。）

loop_with_index {|i| print "\e[1G#{i}  "; sleep(0.5)}

は Kernel#loop_with_index で、インデックス付き無限ループです。ここを参照。

p ("10.(952)".to_r + "5.26(3)".to_r).to_rec_decimal    #=>"16.21(628)"

は String#to_r のオーバーライドと、Rational#to_rec_decimal で、循環小数を扱います。ここを参照。

p 150.divisors_int    #=>[1, 2, 3, 5, 6, 10, 15, 25, 30, 50, 75, 150]

は Integer#divisors_int で、約数を配列で返します。ここを参照。

機能追加（2/27）

p 3.0.integer?    #=>true

は Float#integer? で、レシーバーの小数点以下が 0 なら true、それ以外は false を返します。

p Array.make([2, 3], "a")    #=>[["a", "a", "a"], ["a", "a", "a"]]

は Array.make(ar, ob) で、多重配列を簡単に作成します。ar は Array、ob は初期値（省略可能）ですが、初期値は Array.new とちがって、ob のコピーが入ります。ここを参照。

機能追加（3/11）

p Utils.key_wait

はキーボードからの一文字入力です。

[[1, 2], [3, 4]].deep_copy

は Object#deep_copy で、オブジェクトのいわゆる「ディープコピー」をします。

p 5.factorial    #=>120

は Integer#factorial で、階乗を返します。

p Utils.time_lexic    #=>"kimgfpxtuzl"

はマイクロ秒まで採った現在時刻を、アルファベットの辞書順になるように変換して、String で出力します。ここを参照。

機能追加（4/23）

a = [1, 5, 9, 1, 6]
a.change(1, "a")    #=>["a", 5, 9, "a", 6]
a.change!(1, "a")

は Array#change(a, b) (change! は破壊的メソッド）で、配列のすべての要素 a を b に置き換えます。

p Utils.permutation(4, 2)    #=>12
p Utils.combination(4, 2)    #=>6

は順列と組み合わせを求めます。

機能追加（7/29）
末尾再帰を回避するメソッドを2つ、Utils.trcall と Module#tco を追加しました。詳細はここを参照して下さい。

機能追加（11/10）

p "test".flow {|x| x.upcase}.chars    #=>["T", "E", "S", "T"]

Object#flow は self をブロック内で処理して最後の値を返します。

p "te*st".fname_filter   #=>"test"

String#fname_filter は self に含まれているフォルダ名・ファイル名に使っていけない文字を取り除いて返します。破壊的メソッド。

p nil.nil_trans([])    #=>[]

Object#nil_trans(obj = "") は self が nil ならば obj（デフォルトは ""）を返し、それ以外なら self 自身を返します。

Counter.make(:count, 100, -4)
10.times {puts count}

Counter.make はカウンターを作ります。詳細はここを参照して下さい。

{:A=>0, :B=>2, :C=>0}.collect_keys(0)    #=>[:A, :C]

Hash#collect_keys(ob) は、ob の値を持つキーをすべて集めて配列で返します。詳細はここを参照して下さい。

{1=>2, 3=>4, 5=>6}.map_to_h {|k, v| [k, (v ** 2).to_s]}    #=>{1=>"4", 3=>"16", 5=>"36"}

Hash#map_to_h は、Hash#map して返り値を to_h します。

機能追加（2017/1/24)

5.times_retry(message: true, wait: 1) {raise "test error"}

Integer#times_retry はブロック内でエラーが起きた場合 n 回リトライし、それを超えた場合は停止します。詳細はここを参照。

機能追加（2017/2/10)

Utils.progress_bar do |bar|
  for i in 0..20
    bar.fraction = i / 20.0
    sleep(0.5)
  end
end

Utils#progress_bar は GTK+ で簡単にプログレスバーを使います。詳細はここを参照。

機能追加（2017/2/12)

Utils.delete_non_img("text")    #=>true

Utils.delete_non_img は画像ファイルでなければ削除します。詳細はここを参照。

機能追加（2017/6/8)

Utils.delete_empty_folder('pictures')

Utils.delete_empty_folder は指定したディレクトリの空フォルダを削除します。

Utils.bell

Utils.bell はベルを鳴らします（Ubuntu）。

Ruby のメタプログラミングでカウンターを作る

Ruby はインクリメントやデクリメントがないのですが、遊びでカウンターを作ってみました。メタプログラミングを使って、呼び出されるたびに step（デフォルトは 1）だけ増える数を与えるメソッドを生成します。「メソッド」というのが工夫したところです。

使い方は、Counter.make(:inc) でカウンター inc を作成します。カウンターの名前は何でも構いません。デフォルトの初期値は 0、step は 1です。

Counter.make(:inc)
5.times {puts inc}    #=>0 1 2 3 4

Counter.make(:count, 100, -5)
puts count    #=>100
puts count    #=>95
puts count    #=>90

puts inc      #=>5

こんな感じです。特徴としては、トップレベルのメソッドとして定義されるので、クラスのインスタンス・メソッドの中などへ飛んでもカウントが持続します。また、どこで Counter.make しても構いません。
　カウンターが引数を取ると、step がその値に変わります。なので、カウントを進めずに値だけ知りたいときは、引数を inc(0) のようにすれば可能です。引数の効果はその場限りで、あとは最初に与えられた step が使われます。

class Nya
  def hoge
    puts count
  end
end

Counter.make(:count)
puts count       #=>0
Nya.new.hoge     #=>1
puts count(6)    #=>7
puts count       #=>8

ちょっと注意しておくと、初期値のデフォルトは 0 なので、例えば10回カウントしてカウンターは 9 になりますが、最後に値を取り出すときにもう一度呼べばカウンターは 10 を返すことになります。あるいは初期値を 1 にして 10回カウントし、引数 0 で値を取り出してもいいです。

Counter.make(:count)
10.times {count}
puts count       #=>10

Counter.make(:count, 1)
10.times {count}
puts count(0)    #=>10

コードは以下。

class Counter
  def self.make(mname, counter = 0, step = 1)
    f = true
    counter -= step
    Object.class_eval do
      define_method(mname) do |*arg|
        if arg.size >= 1
          counter += step if f
          counter += arg[0]
        else
          counter += step
        end
        f = false
        counter
      end
    end
  end
end

YコンビネータとZコンビネータ（Ruby）

qiita.comこの記事がおもしろかったので色いろぐぐっていたら、すばらしくわかりやすいサイトがあった。

d.hatena.ne.jpわかりやすいので、いっぱいブクマがついております。以下これを参考にして、メモしておきます。

まずラムダ式であるが、

f(x) = x * 2

と書く代わりに、f というような識別子は余分だとして

λx.x * 2

というように書く。そして、これをカッコで括って後に例えば y をくっつけると、

(λx.x * 2)y → y * 2

のように変換されるものとする。これは見てのとおり一変数しか使えない関数式であるが、これらの組み合わせの工夫で多変数関数も表現できるのである（カリー化）。これがラムダ計算である。

具体的には Ruby でこんな感じ。

f = ->(x, y) {x + y}
f[5, 3]       #=>8

add3 = ->(x) {x + 3}
add3[5]       #=>8

add = ->(x) { ->(y) {x + y} }
add[5][3]     #=>8

Proc#curry を使うと

add = ->(x, y) {x + y}.curry
add[5][3]     #=>8

ラムダ計算で「繰り返し」を実装できる。そのひとつが「Yコンビネータ」である。これは天下り的に

Y = λf.(λx.f(xx))(λx.f(xx))

と与えられる。さて、これに関数 M を作用させてみよう。定義どおりに地道に計算すると、

YM = (λf.(λx.f(xx))(λx.f(xx)))M
   = (λx.M(xx))(λx.M(xx))
   = M((λx.M(xx)(λx.M(xx)))
   = M(YM)

となる。つまり YM = M(YM) となって再帰するのだ。これを繰り返すと

YM = M(YM) = M(M(YM)) = M(M(M(YM))) = ...

となって無限に続く。なので、これを単純に Ruby で実装すると、Ruby の lambda は値渡しなので、関数定義が無限にネストして「スタックオーバーフロー」となってしまう（ここを参照）。

Yコンビネータのようなものを「不動点コンビネータ」というが、不動点コンビネータには「Zコンビネータ」というのもある。これも天下り式に

Z = λf.(λx.f(λy.xxy))(λx.f(λy.xxy))

と与えておこう。これも同様に関数 M を作用させ、地道に計算してみる。

ZM = (λf.(λx.f(λy.xxy))(λx.f(λy.xxy)))M
   = (λx.M(λy.xxy))(λx.M(λy.xxy))
   = M(λy.(λx.M(λy.xxy))(λx.M(λy.xxy))y)
   = M(λy.ZMy)

となる。ここで ZM = A とおくと

A = M(λy.Ay)

であり、関数 A に値 a を代入すれば

Aa = M((λy.Ay)a) = M(Aa)

となってこれも再帰する。しかしこれならば関数定義そのものはネストしておらず、すなわち一種の「遅延評価」をしていることになって、値渡しの Ruby でも実装が可能である。Ruby での実装は、先ほどのサイトのものをありがたく使わせてもらおう。

Z = ->(f) {
  ->(x){
    f.(
      ->(y) {x.(x).(y)}
    )
  }.(
    ->(x){
      f.(
        ->(y) {x.(x).(y)}
      )
    }
  )
}

Z[
  ->(x) {
    ->(n) { (n == 0) ? 1 : n * x[n - 1] }
  }
][5]
#=>120

Zコンビネータと無名関数だけで、一切の識別子なしに 5 の階乗を求めている。

なお、「きしだのはてな」の記事のように、YコンビネータとZコンビネータを並べて書いてみると、

Y = ->(f) { ->(x) {f[x[x]]} [->(x) {f[x[x]]}] }
Z = ->(f) { ->(x) {->(m) { f[x[x]][m] }} [->(x) {->(m) { f[x[x]][m]} }] }

となって、ZコンビネータがYコンビネータに遅延評価（mの部分）を咬ませただけのものだということがはっきりすると思う。（なお、この「きしだのはてな」のZコンビネータは、上の定義どおりではない。）

※追記
LambdaDriver を使って書くとこうなる。

require 'lambda_driver'
Y = ->(f) {->(x) {f < x < x} < ->(x) {f < x < x}}
Z = ->(f) {->(x) {f < ->(y) {x < x < y}} < ->(x) {f < ->(y) {x < x < y}}}
Z < ->(x) {->(n) { (n == 0) ? 1 : n * (x < n - 1) }} < 5
#=>120

「きしだのはてな」の方のはこう。

Z = ->(f) {->(x) {->(m) {(f < (x < x)) < m}} < ->(x) {->(m) {(f < (x < x)) < m}}}

フィボナッチ数列の実装。

Z < ->(f) {->(n) { (n < 2) ? n : f[n - 1] + f[n - 2]}} < 7
#=>13

※参考
不動点コンビネータ - Wikipedia

いわゆる「ビュフォンの針」の同心円バージョンについて

いつも拝読している「完全無欠で荒唐無稽な夢」というブログがあるのですが、そのコメント欄にこんなことが書いてありました。

こんにちは ^^
またお願いなんですが…^^;
ビュフォンの針：平行線の間隔の半分の長さの針が平行線と交わる確率が1/πというものですが…
平行線を同心円に変換した場合，同じように針が同心円と交わる確率ってのは求められるのでしょうか知らん…?
平行線も針も曲げた場合は同じ確率になるわけだから...針だけ直線のままなら…1/πよりも大きくなりそうとは予測できるのですが...計算の方法がよくわかりません…^^;;
例の，モンテカルロ法で近似値だけでも分かればと…Orz…
お手すきのときにでもよろしければお願い致します～m(_ _)m～v

うーん、これはおもしろそうだと考えてみたのですが、コンピュータ計算で任意の実数を等確率に与える乱数を得ることは無理だと気付きました。ただ、これは有限範囲でも近い数字は出せそうなので、やってみました。

針の長さは 2、同心円の間隔は 4 で計算します。
コードはこんな風でいいのですかねえ…（自信なし）　使った言語は Ruby です。

include Math

R = 100000.0
N = 100_0000

def get_num(x, y)
  (sqrt(x ** 2 + y ** 2) / 4).to_i
end

counter = 0
N.times do
  r = rand * R
  Θ = rand * (2 * PI)
  φ = rand * PI
  n1 = get_num(r * cos(Θ) + cos(φ), r * sin(Θ) + sin(φ))
  n2 = get_num(r * cos(Θ) - cos(φ), r * sin(Θ) - sin(φ))
  counter += 1 unless n1 == n2
end
puts counter / N.to_f

このコードでは、同心円の中心から半径 R =100000.0 以内の場所に針が落ちます。試行回数は N = 1000000 回です。

この例でやってみると、確率はだいたい 0.318 くらいになりました。R の値を変えても確率は大きくは変わりませんでした。ただ、R が小さいと確率は多少低くなります（R = 100.0 で 0.312 くらい）。1 / π がだいたい 0.3183... なので、同心円の場合も確率は 1 / π になるのではないでしょうか。

なお、ここでは針の中心の位置を同心円の中心からの距離と回転角であたえていますが、このあたえ方は本質的ではありません。針が同心円と交わるかを調べるときに、それに依存していないからです。だから、完全にランダムであれば、正方形領域に針を落としても同じ答えになる筈です。

※追記
2点で交わる場合の見落としがありました。こうかな。

include Math

R = 100000.0
N = 100_0000

def get_num(x, y)
  (sqrt(x ** 2 + y ** 2) / 4).to_i
end

counter = 0
N.times do
  r = rand * R
  Θ = rand * (2 * PI)
  φ = rand * PI
  n1 = get_num(x1 = r * cos(Θ) + cos(φ), r * sin(Θ) + sin(φ))
  n2 = get_num(x2 = r * cos(Θ) - cos(φ), r * sin(Θ) - sin(φ))
  x3 = ( sin(φ) ** 2 * cos(Θ) - sin(φ) * cos(φ) * sin(Θ)) * r
  y3 = (-sin(φ) * cos(φ) * cos(Θ) + cos(φ) ** 2 * sin(Θ)) * r
  n3 = get_num(x3, y3)
  x1, x2 = x2, x1 if x1 < x2
  if n1 != n2
    counter += 1
  elsif n1 == n2 and n2 - n3 == 1 and x3 < x1 and x2 < x3
    counter += 1
  end
end
puts counter / N.to_f

これでも確率はほぼ 0.318、誤差の範囲で変わらないですね。

BigDecimal を使って精度を上げてみる。しかし、時間がかかりすぎて充分な試行数が取れない…。

require 'bigdecimal'
require 'bigdecimal/math'
include Math
include BigMath

R = 100000.0
N = 10000
F = 12

def get_num(x, y)
  (sqrt(x ** 2 + y ** 2, F) / 4).to_i
end

counter = 0
N.times do
  r = BigDecimal(rand * R, F)
  Θ = BigDecimal(rand * (2 * PI), F)
  φ = BigDecimal(rand * PI, F)
  n1 = get_num(x1 = r * cos(Θ, F) + cos(φ, F), r * sin(Θ, F) + sin(φ, F))
  n2 = get_num(x2 = r * cos(Θ, F) - cos(φ, F), r * sin(Θ, F) - sin(φ, F))
  x3 = ( sin(φ, F) ** 2 * cos(Θ, F) - sin(φ, F) * cos(φ, F) * sin(Θ, F)) * r
  y3 = (-sin(φ, F) * cos(φ, F) * cos(Θ, F) + cos(φ, F) ** 2 * sin(Θ, F)) * r
  n3 = get_num(x3, y3)
  x1, x2 = x2, x1 if x1 < x2
  if n1 != n2
    counter += 1
  elsif n1 == n2 and n2 - n3 == 1 and x3 < x1 and x2 < x3
    counter += 1
  end
end
puts counter / N.to_f

これも確率は 0.318 くらい。

どうやら R を大きくすると、2点で交わる場合はほとんど無視できるようですね。結局ほぼ 1 / π ということですか。

※再追記
中心に大きな穴ができるのをなくしました。メソッド get_num を書き換えています。

def get_num(x, y)
  l = sqrt(x ** 2 + y ** 2) - 2
  return 0 if l <= 0
  (l / 4).to_i + 1
end

こうしても R が大きい場合の確率は誤差の範囲で変わりません。R を小さくすると効果がでます。R = 100.0 の場合の確率は 0.318 となって、補正されていることがわかります。また R = 10.0 とさらに小さくしてみると、確率は 0.323 と今度は大きめになり、2点で交わる効果が出てきて、これも期待どおりになります。