#!/usr/bin/env python
# encoding: utf-8
"""Script for solving the "clock puzzle" mini-games in Final Fantasy XIII-2.

The clock puzzles consist of N integers from 1 to ⌊N/2⌋ arranged in a
circle.  The puzzle is solved by initially picking any of the N
positions in the circle. Let the integer in the chosen position be M.
Now one has to choose either the number at position M positions
clockwise, counter-clockwise from the previously chosen integer. The
solution to the puzzle is a sequence of choices such that each integer
in the circle is chosen exactly once.

Solving the clock puzzle is equivalent to finding a directed Hamiltonian
path in a directed graph with N vertices, where the directed edges
describe the valid moves around the circle. More precisely if the
integer at position N is M, then there are directed edges to the
vertices M positions clockwise, or counter-clockwise from position N.

Finding a directed Hamiltonian path in a general directed graph is
NP-hard.  The graphs corresponding to the clock puzzles are special
cases due to their structure where the outdegree of each vertex is 2 and
the edges have a certain symmetry due to the clockwise/counter-clockwise
movement rules. Finding a Hamiltonian path in a graph with a limited
outdegree is still NP-hard, but it is unclear if the symmetricity would
allow a devising a fast algorithm for solving these puzzles. In the
puzzles present in the game N ranges from 5 to 13 which is sufficiently
small to allow those puzzles to be easily solved by brute force.

The script takes a list of values corresponding to integers of the
puzzle circle. Each value is assigned a consecutive letter indicating
its position in the ring starting with `a` for the first value.

The script outputs a sequence of positions corresponding to a solution
to the puzzle.

"""
import sys

def main():
    "Parses command line arguments and attempts to solve puzzle by brute force."
    if len(sys.argv) == 1:
        sys.exit("%s: error: missing argument" % sys.argv[0])

    # Determine clock values from command line arguments
    values = [int(arg) for arg in sys.argv[1:]]

    # Attempt solving the puzzle by starting from each position in turn
    for i in range(len(values)):
        chain = solve_puzzle(values, i)
        
        # A solution is valid if it contains all positions
        if len(chain) == len(values):
            break

    # Determine the corresponding letter for each position and print solution
    positions = [chr(i) for i in range(97, 97 + len(values))]
    solution = [positions[elem] for elem in chain]
    print " → ".join(solution)

def solve_puzzle(values, i, chain=None):
    """Recursively solves clock puzzle based on specified state.

    Args:
        values:  Current clock values.
        i:       Current clock position.
        chain:   The current possible solution.

    Returns:
        A list of positions representing a possible solution.

    Raises:
        IndexError: If i out of range.

    """
    if not chain:
        chain = []

    # If the value of the current position is 0, it has already been visited
    if values[i] == 0:
        return chain

    # Determine the two possible positions by moving clockwise or counter-
    # clockwise the number of steps determined by the current position
    position1 = (i + values[i]) % len(values)
    position2 = (i - values[i]) % len(values)

    # Mark the current position as visited
    values[i] = 0
    chain.append(i)

    # Attempt solution by moving clockwise
    solution = solve_puzzle(values[:], position1, chain[:])
    
    # If the clockwise move does not lead to a solution, move counter-clockwise
    return (solution[:] if len(solution) == len(values)
            else solve_puzzle(values, position2, chain))

if __name__ == '__main__':
    main()
