油売り算

Python

Python で書いてみた。

import sys
from collections import deque

def solve_abura(a, b, c):
    limits = (a, b, c)
    choices = ((0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1))

    def is_complete(state):
        return state == (a / 2, a / 2, 0)

    def is_movable(state, i, j):
        return state[i] != 0 and state[j] != limits[j]

    def move(state, i, j):
        new_state = list(state)
        if new_state[i] + new_state[j] > limits[j]:
            new_state[i] -= limits[j] - new_state[j]
            new_state[j] = limits[j]
        else:
            new_state[j] += new_state[i]
            new_state[i] = 0
        return tuple(new_state)

    queue = deque()
    queue.append(((), (a, 0, 0)))
    visited = set()

    while queue:
        seq, state = queue.popleft()
        for i, j in choices:
            if not is_movable(state, i, j):
                continue
            new_state = move(state, i, j)
            new_seq = seq + ((i, j),)
            if new_state in visited:
                continue

            if is_complete(new_state):
                return new_seq
            queue.append((new_seq, new_state))
            visited.add(new_state)

    return None

def print_sequence(seq):
    chars = 'A B C'.split()
    for f, t in seq:
        print 'move from %c to %c' % (chars[f], chars[t])

def main(a, b, c):
    seq = solve_abura(a, b, c)
    if seq is not None:
        print_sequence(seq)
    else:
        print 'cannot be solved'

if __name__ == '__main__':
    if len(sys.argv) == 4:
        a, b, c = [int(s) for s in sys.argv[1:]]
    else:
        a, b, c = 10, 7, 3

    main(a, b, c)

結構長くなってしまった。一応 deque を使っているけど、この程度なら単純に list でもいいかもしれない。