油売り算

http://karetta.jp/article/blog/ll-spirit/033840

僕も書いてみた。一週間くらいかかった...orz
きっと一年後に書いたらもっと違うコードになるんだろうな。

CAPA = [ARGV[0].to_i, ARGV[1].to_i ,ARGV[2].to_i]
GOAL = [CAPA[0]/2, CAPA[0]/2, 0]
STEPS = [[0,1],[0,2],[1,0],[1,2],[2,0],[2,1]]
A = 97 #ASCII code of "a"
phase = [CAPA[0],0,0]
visited = Array.new
stack = Array.new
queue = Array.new

def pourAbura(visit)
  abura = visit[0..2]
  from = visit[3]
  to = visit[4]
  if abura[from] + abura[to] > CAPA[to]
    abura[from] -= CAPA[to] - abura[to]
    abura[to] = CAPA[to]
  else
    abura[to] += abura[from]
    abura[from] = 0
  end
  return abura 
end

def printRoute(s)
  i = 0
  while i < s.size-3 do
    printf("%c から %c に ", A + s[i+3], A + s[i+4])
    print s[i + 5 + s[i + 4]] - s[i + s[i + 4]]
    print " 升移す => " + s[i + 5, 3].join(",") + "\n"
    i += 5
  end
end

puts "初期値: " + phase.join(",")
until phase == GOAL do
  unless visited.include?(phase)
    STEPS.each{|step|
      queue.push(stack + phase + step)
    }
  end
  visited << phase
  stack = queue.shift
  if stack == nil
    puts "解けません！"
    break
  else
    phase = pourAbura(stack[(stack.size-5)..(stack.size-1)])
  end
  if phase == GOAL
    stack += phase
    printRoute(stack)
  end
end

で、結果。

[hide@localhost ~]$ ruby abura.rb 4 7 3
初期値: 4,0,0
解けません！
[hide@localhost ~]$ ruby abura.rb 6 7 3
初期値: 6,0,0
a から c に 3 升移す => 3,0,3
c から b に 3 升移す => 3,3,0
[hide@localhost ~]$ ruby abura.rb 8 7 3
初期値: 8,0,0
a から b に 7 升移す => 1,7,0
b から c に 3 升移す => 1,4,3
c から a に 3 升移す => 4,4,0
[hide@localhost ~]$ ruby abura.rb 10 7 3
初期値: 10,0,0
a から b に 7 升移す => 3,7,0
b から c に 3 升移す => 3,4,3
c から a に 3 升移す => 6,4,0
b から c に 3 升移す => 6,1,3
c から a に 3 升移す => 9,1,0
b から c に 1 升移す => 9,0,1
a から b に 7 升移す => 2,7,1
b から c に 2 升移す => 2,5,3
c から a に 3 升移す => 5,5,0
[hide@localhost ~]$ ruby abura.rb 12 7 3
初期値: 12,0,0
a から c に 3 升移す => 9,0,3
c から b に 3 升移す => 9,3,0
a から c に 3 升移す => 6,3,3
c から b に 3 升移す => 6,6,0
[hide@localhost ~]$ ruby abura.rb 14 7 3
初期値: 14,0,0
a から b に 7 升移す => 7,7,0
[hide@localhost ~]$ ruby abura.rb 16 7 3
初期値: 16,0,0
解けません！

んー。「解けません！」ていうパターンが、あってるんだかあってないんだか分かんない…