170924

Ruby


途中で自身と交差しないgolygon の数

自身と交差しないように伸ばしていき、始点と終点が一致したらカウントする。
以下において、線対称のものや点対称なものは同一なものとみなすために、[[0, 0], [1, 0], [1, 1], [1, 2]] から出発している。

def A(n)
  b_ary = [[[0, 0], [1, 0], [1, 1], [1, 2]]]
  s = 4
  (3..n).each{|i|
    s += i
    t = 0
    f_ary, b_ary = b_ary, []
    if i % 2 == 1
      f_ary.each{|a|
        b = a.clone
        x, y = *b[-1]
        b += (1..i).map{|j| [x + j, y]}
        b_ary << b if b.uniq.size == s
        t += 1 if b[-1] == [0, 0] && b.uniq.size == s - 1
        c = a.clone
        x, y = *c[-1]
        c += (1..i).map{|j| [x - j, y]}
        b_ary << c if c.uniq.size == s
        t += 1 if c[-1] == [0, 0] && c.uniq.size == s - 1
      }
    else
      f_ary.each{|a|
        b = a.clone
        x, y = *b[-1]
        b += (1..i).map{|j| [x, y + j]}
        b_ary << b if b.uniq.size == s
        t += 1 if b[-1] == [0, 0] && b.uniq.size == s - 1
        c = a.clone
        x, y = *c[-1]
        c += (1..i).map{|j| [x, y - j]}
        b_ary << c if c.uniq.size == s
        t += 1 if c[-1] == [0, 0] && c.uniq.size == s - 1
      }
    end
    p [i, b_ary.size, t]
  }
end

A(24)

出力結果
[3, 2, 0]
[4, 4, 0]
[5, 8, 0]
[6, 16, 0]
[7, 29, 1]
[8, 54, 1]
[9, 98, 0]
[10, 176, 0]
[11, 318, 0]
[12, 572, 0]
[13, 1026, 0]
[14, 1826, 0]
[15, 3255, 1]
[16, 5794, 3]
[17, 10233, 0]
[18, 18172, 0]
[19, 32012, 0]
[20, 56488, 0]
[21, 99469, 0]
[22, 175034, 0]
[23, 307479, 25]
[24, 540068, 67]