#!/usr/bin/ruby -w

require 'pp'

# ------------------------------------------------------------------------------
# DEEP SEA FISH
#
# 9 piece puzzle 0 .. 8
#
#   1: pacific blue marlin head
#   2: atlantic tarpon head
#   3: tuna head
#   4: dolphinfish (mahi-mahi) head
#
#  -1: pacific blue marlin tail
#  -2: atlantic tarpon tail
#  -3: tuna tail
#  -4: dolphinfish (mahi-mahi) tail
#

# definition of pieces top, right, bottom, left

#Pieces = [[ 2, -4,  3,  1],
#          [-1, -4, -3,  4],
#          [ 3, -1,  2, -3],
#          [-3,  4,  2,  1],
#          [ 4,  2, -2,  1],
#          [ 4, -3, -1, -2],
#          [-3,  4, -2, -1],
#          [ 2, -1, -3,  4],
#          [-2, -1, -4,  3]]
# ------------------------------------------------------------------------------

# ------------------------------------------------------------------------------
# BUTTERFLIES
#
# 9 piece puzzle 0 .. 8
#
#   1: american copper head
#   2: monarch head
#   3: palamedes swallowtail head
#   4: red-spotted purple head
#
#  -1: american copper tail
#  -2: monarch tail
#  -3: palamedes swallowtail tail
#  -4: red-spotted purple tail
#

# definition of pieces top, right, bottom, left

Pieces = [[ 2,  4, -1,  3],
          [ 3,  2, -4, -2],     # winner
          [ 1,  4, -2, -3],
          [-1, -2, -3, -4],     # winner
          [ 2, -4, -1,  3],     # winner
          [ 1, -3, -2,  4],     # winner
          [ 3, -3, -1,  4],
          [-1, -4,  2,  3],
          [ 1,  2,  1, -4]]     # winner
# ------------------------------------------------------------------------------


# define 'board' and the match rules
#
#   +-----+-----+-----+
#   |  0  |  0  |  0  |
#   |3 0 1|3 1 1|3 2 1|
#   |  2  |  2  |  2  |
#   +-----+-----+-----+
#   |  0  |  0  |  0  |
#   |3 3 1|3 4 1|3 5 1|
#   |  2  |  2  |  2  |
#   +-----+-----+-----+
#   |  0  |  0  |  0  |
#   |3 6 1|3 7 1|3 8 1|
#   |  2  |  2  |  2  |
#   +-----+-----+-----+
#
# rules are defined in pairs where each pair defines a position on the board
# and a side in that position.  The pairs define adjacent sides that need to
# be matched.  So, for the piece in position n, there are pairs defined for
# each comparison that must be made.
#
Rules = [
    [[[0,1],[1,3]],     # matches in square 0
     [[0,2],[3,0]]],
    [[[1,1],[2,3]],     # matches in square 1
     [[1,2],[4,0]],
     [[1,3],[0,1]]],
    [[[2,2],[5,0]],     # matches in square 2
     [[2,3],[1,1]]],
    [[[3,0],[0,2]],     # matches in square 3
     [[3,1],[4,3]],
     [[3,2],[6,0]]],
    [[[4,0],[1,2]],     # matches in square 4
     [[4,1],[5,3]],
     [[4,2],[7,0]],
     [[4,3],[3,1]]],
    [[[5,0],[2,2]],     # matches in square 5
     [[5,2],[8,0]],
     [[5,3],[4,1]]],
    [[[6,0],[3,2]],     # matches in square 6
     [[6,1],[7,3]]],
    [[[7,0],[4,2]],     # matches in square 7
     [[7,1],[8,3]],
     [[7,3],[6,1]]],
    [[[8,0],[5,2]],     # matches in square 8
     [[8,3],[7,1]]]
]

#
# define the initial state of the board -- the 'board' is an array of number
# pairs where the first number refers to an entry from the pieces array and the
# second number is a counter-clockwise rotation factor relative to the initial
# orientation of the pieces when they were defined.  Everything will start out
# in numeric order and no rotation
#
Board = [[0,0], [1,0], [2,0], [3,0], [4,0], [5,0], [6,0], [7,0], [8,0]]
#Board = [[1,0], [5,0], [3,0], [2,0], [0,0], [6,0], [4,0], [7,0], [8,0]]
#Board = [[1,0], [5,1], [3,0], [2,0], [0,0], [6,2], [4,2], [7,2], [8,3]]

def match?(side1, side2)
    return ((side1 + side2) == 0)
end

def rotate(piece, n = 1)
    n.times do
        piece[3] = piece.shift
    end
end

def solved?()
    solved = true
    for i in 0..8
        Rules[i].each do | rule_pair |
#pp Pieces
#            printf("I want to look at piece %d side %d: %d\n", Board[rule_pair[0][0]][0], rule_pair[0][1], Pieces[Board[rule_pair[0][0]][0]][rule_pair[0][1]])
#            printf("and compare to    piece %d side %d: %d\n", Board[rule_pair[1][0]][0], rule_pair[1][1], Pieces[Board[rule_pair[1][0]][0]][rule_pair[1][1]])
            solved = match?(Pieces[Board[rule_pair[0][0]][0]][rule_pair[0][1]],
                            Pieces[Board[rule_pair[1][0]][0]][rule_pair[1][1]])
            break if !solved
        end
        break if !solved
    end
    return solved
end

def rotate_piece_in_board(x)
    done = false
    if (x < 9)
        rotate(Pieces[Board[x][0]])
        Board[x][1] += 1
        if Board[x][1] == 4
            Board[x][1] = 0
            done = rotate_piece_in_board(x+1)
        end
    else
        done = true
    end
    return done
end

def next_board_permutation!
    # The following algorithm generates the next permutation lexicographically
    # after a given permutation. It changes the given permutation in-place.
    #
    #   1. Find the largest index k such that a[k] < a[k + 1]. If no such
    #      index exists, the permutation is the last permutation.
    #   2. Find the largest index l such that a[k] < a[l]. Since k + 1 is
    #      such an index, l is well defined and satisfies k < l.
    #   3. Swap a[k] with a[l].
    #   4. Reverse the sequence from a[k + 1] up to and including the final
    #      element a[n].
    #
    # After step 1, one knows that all of the elements strictly after position k
    # form a weakly decreasing sequence, so no permutation of these elements will
    # make it advance in lexicographic order; to advance one must increase a[k].
    # Step 2 finds the smallest value a[l] to replace a[k] by, and swapping them
    # in step 3 leaves the sequence after position k in weakly decreasing order.
    # Reversing this sequence in step 4 then produces its lexicographically minimal
    # permutation, and the lexicographic successor of the initial state for the
    # whole sequence.
    n = Board.length
    k = (n - 2)

    # step 1
    while (k >= 0) do
        break if (Board[k][0] < Board[k+1][0])
        k -= 1
    end
    return false if k < 0

    # step 2
    l = (n - 1)
    while (l > k) do
        break if (Board[k][0] < Board[l][0])
        l -= 1
    end

    # step 3
    tmp = Board[k]
    Board[k] = Board[l]
    Board[l] = tmp

    # step 4
    k += 1
    segment = Board.slice(k...n).reverse!
    i = 0
    while k < n do
        Board[k] = segment[i]
        k += 1; i += 1
    end

    return true
end



#-------------------------------------------------------------------------------
# brute_force algorithm                                     by alan partis
#++
#   Attempts all possible solutions until the right one is found.
#
#   There are something on the order of 96 billion permutations to examine
#   in a brute-force solution for a puzzle like this.  My computer is taking
#   roughly a minute to check half a million, or about 30 million per hour.
#   At that rate, it will take well over half a year to check them all, though
#   it is reasonable to expect a solution to be found in half that time.
#-------------------------------------------------------------------------------
def brute_force
    begin
        loop do
            262144.times do
                if solved?
                    puts "puzzle is solved with board looking like this:"
                    pp Board
                    return
                end
                done = rotate_piece_in_board(0)
                break if done
            end
            break if !next_board_permutation!
            pp Board
        end
    rescue Exception => e
        puts e
    end
end


#-------------------------------------------------------------------------------
# the global pool and solution spaces for the human approach
Pool      = [[0,0], [1,0], [2,0], [3,0], [4,0], [5,0], [6,0], [7,0], [8,0]]
Solution  = []

#-------------------------------------------------------------------------------
# fit?                                                      by alan partis
#++
#   Does the 'work_cell' piece fit into the solution?
#
#   return number of rotations to find a fit
#   return -1 if no fit found
#-------------------------------------------------------------------------------
def fit?(work_cell)

    rotations = Solution[work_cell][1]

    return rotations if work_cell == 0

    fit = false
    while !fit && (rotations < 4)
        fit = true
        Rules[work_cell].each do | rule_pair |
            # only examine rules where the matching cell is at, or below,
            # the work_cell location
            if (rule_pair[1][0] <= work_cell)

                # identify the work cell piece and side
                work_piece = Solution[work_cell][0]
                work_side = rule_pair[0][1]

                # calculate which Piece and side to try to match
                solution_cell = rule_pair[1][0]
                test_piece = Solution[solution_cell][0]
                test_side = rule_pair[1][1]

                if !match?(Pieces[work_piece][work_side], Pieces[test_piece][test_side])
                    fit = false
                end
            end
        end

        if !fit
            rotate(Pieces[Solution[work_cell][0]])
            rotations += 1
        end
    end

    return -1 if rotations == 4
    return rotations
end



#-------------------------------------------------------------------------------
# human algorithm                                           by alan partis
#++
#   Looks for a solution much like a human might approach the problem.
#
#   We start by choosing one piece from the pool of pieces and placing it in
#   the first cell.  Then we choose another piece and see if it will work somehow
#   in the next cell.  If it does, then we try another piece in the next cell
#   and so on.  If a piece can't fit, then we try a different one in the previous
#   cell.  If no solutions can be found all the way back to the first cell, we use
#   a different starting piece and try again.
#
#   The calculations for this approach might be slightly longer in this algorithm
#   versus the brute force method, but we will avoid examining billions and billions
#   of possible solutions that we already know can't work.
#
#   It turns out that this solution executes in a matter of a few seconds at most
#   while the brute force approach will likely take several months.
#
#   returns whether we've solved the puzzle, or ran out of options
#-------------------------------------------------------------------------------
def human(work_cell)

    solved = false
    rotate_first = false
    while !solved

        # if we're being asked to find a fit for _this_ cell, then we
        # found fits for all the previous cells and we've found our
        # solution!
        if work_cell > 8
            solved = true
            break
        end

        if rotate_first

            rotate_first = false

            # rotate our piece and retry.  If we've tried all sides, pop it off
            # and try the next piece.  If there are no more pieces, fail.
            rotate(Pieces[Solution[work_cell][0]])
            Solution[work_cell][1] = (Solution[work_cell][1] + 1) % 4
            if (Solution[work_cell][1] == 0)
                Pool[Solution[work_cell][0]] = Solution[work_cell]

                i = Solution[work_cell][0] + 1
                while (i < 9) && (Pool[i] == nil)
                    i += 1
                end
                if (i < 9)
                    Solution[work_cell] = Pool[i]
                    Pool[i] = nil
                else
                    # we've run out of pieces in the pool to work with at this level
                    # so fail back to the previous cell
                    Solution.pop
                    work_cell -= 1
                    rotate_first = true
                    next
                end
            end
        end

        # make sure we've got a piece in the solution to work with
        if Solution[work_cell] == nil
            #get lowest available piece from pool
            i = 0
            while (i < 9) && (Pool[i] == nil)
                i += 1
            end
            Solution[work_cell] = Pool[i]
            Pool[i] = nil
        end

        # does the work piece fit here?
            # calling fit? has the unexpected side-effect of also rotating
            # the given Piece's data.  Get that number and record it in the
            # solution
        rotations = fit?(work_cell)
        if (rotations >= 0)
            # yes, the work piece fits, note the rotations and
            # move to the next cell
            Solution[work_cell][1] = rotations
            work_cell += 1
        else
            # nope, the work piece doesn't fit, reset the rotations, pop the
            # cell from the Solution and get the next higher available piece
            # from the pool.  If no higher piece is available, ...
            Solution[work_cell][1] = 0
            Pool[Solution[work_cell][0]] = Solution[work_cell]

            i = Solution[work_cell][0] + 1
            while (i < 9) && (Pool[i] == nil)
                i += 1
            end
            if (i < 9)
                Solution[work_cell] = Pool[i]
                Pool[i] = nil
            else
                # we've run out of pieces in the pool to work with at this level
                # so fail back to the previous cell
                Solution.pop
                work_cell -= 1
                rotate_first = true
            end
        end
    end

    return solved
end



#-------------------------------------------------------------------------------
# main program entry point                                  by alan partis
#++
#   Get things set up and run the appointed algorithm to find the solution.
#-------------------------------------------------------------------------------
begin
    # if no algorithm specified on the command line, default to 'human'
    algorithm = ARGV[0] || 'human'

    start_time = Time.now

    case algorithm
    when 'brute_force' then brute_force
    when 'human'       then
        solved = human(0)
        if solved
            print "solution: "; pp Solution
        else
            print "Nice try!  solution: "; pp Solution
        end
    end

    stop_time = Time.now

    printf("run time: %0.1f seconds\n", (stop_time - start_time))
end