『プログラマ脳を鍛える数学パズル』

ここからの続きです。

とにかく 2(n - 1) 回目に元に戻る場合。

def shuffle(n, cards)
  shuffled = []
  n.times do |i|
    shuffled << cards[i]
    shuffled << cards[n + i]
  end
  shuffled
end

def check(n)
  cards = (1..2 * n).to_a
  org = cards
  (2 * n - 2).times {cards = shuffle(n, cards)}
  org == cards
end

co = 0
1.upto(100) do |i|
  co += 1 if check(i)
end
puts co    #=>46

初めて元に戻るのが 2(n - 1) 回目の場合。

def shuffle(n, cards)
  shuffled = []
  n.times do |i|
    shuffled << cards[i]
    shuffled << cards[n + i]
  end
  shuffled
end

result = 0
1.upto(100) do |n|
  cards = (1..2 * n).to_a
  org = cards
  co = 1
  loop do
    cards = shuffle(n, cards)
    break if cards == org
    co += 1
  end
  result += 1 if co == 2 * n - 2
end
puts result    #=>22

class HourGlass
  def initialize(n, order)
    @order = order
    @i = n
    @now = order
    @memo = [[@i, @now]]
  end
  
  def upside_down
    @now = @now.map {|i| (i > 0) ? i - 1 : 0}
    @order[@i].times do |j|
      idx = (@i + j) % N
      @now[idx] = @order[idx] - @now[idx]
    end
    return true if @now == Goal
    @i = (@i + 1) % N
    a = [@i, @now]
    return false if @memo.include?(a)
    @memo << a
    upside_down
  end
end

N = 8
Goal = [1] * N

co = 0
[*1..N].permutation do |ar|
  hg = HourGlass.new(0, ar)
  co += 1 if hg.upside_down
end
puts co    #=>6055

#real 7.241秒

惜しかった。あと少しで正解だった。模範解答とはちょっとちがう。

N, Ame = 6, 5
@memo = {}

def solve(left, i, co)
  a = @memo[left + [i] + [co]]
  return a if a
  ctr = 0
  return 1 if left == [0] * Ame
  Ame.times do |j|
    next if j == i
    next if left[j] == 0
    left[j] -= 1
    if co < N
      ctr += solve(left, i, co + 1)
    else
      ctr += solve(left, i + 1, 1)
    end
    left[j] += 1
  end
  @memo[left + [i] + [co]] = ctr
end

puts solve([N] * Ame, 0, 1)    #=>1926172117389136

N = 11
@field = Array.new(N * 2, 0)

def solve(i)
  return 1 if i == 0
  co = 0
  (2 * N - (i + 1)).times do |j|
    if @field[j] == 0 and @field[j + i + 1] == 0
      @field[j] = @field[j + i + 1] = 1
      co += solve(i - 1)
      @field[j] = @field[j + i + 1] = 0
    end
  end
  co
end

puts solve(11)    #=>35584