# ------------------------------------------------------------------------------
# pegboard.rb
# ------------------------------------------------------------------------------

# == Copyright
#
# Copyright (c) 2012 thundernet development group, inc.  All rights reserved.
#
# == Synopsis
#
#   Provides solutions for triangular 15 peg puzzle game commonly found at Cracker
#   Barrel restaurants.  Also provides data for self-analysis of the algorithms
#   used to generate the solutions.  Perhaps this can also be used as "inspiration"
#   for an Android version.
#
# == Usage
#
#   $ ruby pegboard.rb [-h | -? | --help]
#
# ------------------------------------------------------------------------------
#
#   Given a peg board with 15 holes and 14 pegs, jump pegs to empty spots until
#   only 1 remains.  A typical starting board (and solution) will look like this:
#
#               o                       o                 0
#              x x                     o o              1    2
#             x x x       = = =>      o o o            3  4   5
#            x x x x                 o o o o          6  7  8  9
#           x x x x x               o o x o o       10 11 12 13 14
#
#   First I'll need a Peg (a class to represent a position on the board).  A Peg
#   will maintain its state (open/occupied) and a list of adjacent Pegs over which
#   it COULD jump.
#
#   Then I'll need a Board.  This will be a static, predefined, collection of Pegs
#   that know their place i.e. have built-in rules about who is adjacent to them.
#   All of this can be represented in a single multi-dimensional array.  Like
#   10-pin bowling, Peg 0 is at the top of the pyramid.
#
#   For the moment, I'll assume the above starting board ...
#
# ------------------------------------------------------------------------------

require 'pp'
require 'tdglib'

#----- predefined CONSTANT values -----
#
OPEN        = false     # indicates that a given board position is open or un-occupied
OCCUPIED    = true      # indicates that a given board position is occupied



#
# each element of START represents an initial position on a game board.  Each
# element is an array where the first element represents the state of a given
# position (open or occupied), and the 2nd element is an array of neighbors.
# Each element of a neighbor array is a 2-element array indicating the source
# and destination positions one can jump through and to from the given position.
#
START = [
    [1, [[1,3], [2,5]]],        # Peg 0 can jump over Pegs 1 (to 3) and 2 (to 5)
    [1, [[3,6], [4,8]]],        # Peg 1 can jump over Pegs 3 (to 6) and 4 (to 8)
    [1, [[4,7], [5,9]]],        # Peg 2 can jump over Pegs 4 (to 7) and 5 (to 9)
    [1, [[1,0], [4,5], [6,10], [7,12]]],    # Peg 3 can jump over Pegs 1 (to 0), 4 (to 5), 6 (to 10), and 7 (to 12)
    [1, [[7,11], [8,13]]],      # Peg 4 can jump over Pegs 7 (to 11) and 8 (to 13)
    [1, [[2,0], [4,3], [8,12], [9,14]]],    # Peg 5 can jump over Pegs 2, 4, 8, and 9
    [1, [[3,1], [7,8]]],        # Peg 6 can jump over Pegs 3 and 7
    [1, [[4,2], [8,9]]],        # Peg 7 can jump over Pegs 4 and 8
    [1, [[4,1], [7,6]]],        # Peg 8 can jump over Pegs 4 and 7
    [1, [[5,2], [8,7]]],        # Peg 9 can jump over Pegs 5 and 8
    [1, [[6,3], [11,12]]],      # Peg 10 can jump over Pegs 6 and 11
    [1, [[7,4], [12,13]]],      # Peg 11 can jump over Pegs 7 and 12
    [0, [[7,3], [8,5], [11,10], [13,14]]],  # Peg 12 can jump over Pegs 7, 8, 11, and 13
    [1, [[8,4], [12,11]]],      # Peg 13 can jump over Pegs 8 and 12
    [1, [[9,5], [13,12]]],      # Peg 14 can jump over Pegs 9 and 13
]



class BadMoveError < RuntimeError
    # nothing special ... just a name to use
end



class Peg

    #-------------------------------------------------------------------------------
    #   public attributes
    #-------------------------------------------------------------------------------
    attr_reader :state, :neighbors


    #-------------------------------------------------------------------------------
    # Peg::initialize()
    #++
    #   constructor - defines and initializes object attributes
    #-------------------------------------------------------------------------------
    def initialize(state = OPEN, neighbors = Array.new)
        @state = state.true?
        if neighbors.kind_of? Array
            @neighbors = neighbors
        else
            @neighbors = Array.new
        end
    end



    #-------------------------------------------------------------------------------
    # Peg::jumped!()
    #++
    #   Tells this Peg that it has been jumped and must OPEN its state.  Raises an
    #   exception if it is already OPEN.
    #-------------------------------------------------------------------------------
    def jumped!
        if @state == OPEN
            raise BadMoveError, "you can't jump over me, I'm already OPEN!"
        end
        @state = OPEN
    end



    #-------------------------------------------------------------------------------
    # Peg::jumped_neighbor()
    #++
    #   Who do I have to jump over to get to where you're sending me?
    #-------------------------------------------------------------------------------
    def jumped_neighbor(dst)
        j = nil
        @neighbors.each do | neighbor |
            j = neighbor[0] if neighbor[1] == dst
        end
        if j.nil?
            raise BadMoveError, "You can't get there from here"
        end
        return j
    end



    #-------------------------------------------------------------------------------
    # Peg::move_in!
    #++
    #   Tells this position that there's a new peg in town!
    #-------------------------------------------------------------------------------
    def move_in!
        if @state == OCCUPIED
            raise BadMoveError, "You can't come in here ... this space is occupied!"
        end
        @state = OCCUPIED
    end



    #-------------------------------------------------------------------------------
    # Peg::move_out!
    #++
    #   Peg (like Elvis) has left the building
    #-------------------------------------------------------------------------------
    def move_out!
        if @state == OPEN
            raise BadMoveError, "You must be lost.  No one here but us mice!"
        end
        @state = OPEN
    end



    #-------------------------------------------------------------------------------
    # Peg::occupied?()
    #++
    #   indicates whether we are an OCCUPIED peg, or not.
    #-------------------------------------------------------------------------------
    def occupied?
        return @state == OCCUPIED
    end



    #-------------------------------------------------------------------------------
    # Peg::to_s()
    #++
    #   default string representation of the Peg
    #-------------------------------------------------------------------------------
    def to_s
        @state == OPEN ? 'o' : 'x'
    end

end     # end of class Peg


class Board

    #-------------------------------------------------------------------------------
    #   public attributes
    #
    #   @solutions      collection of puzzle solutions - each element is a series
    #                       of moves taken to solve it
    #-------------------------------------------------------------------------------
    attr_writer :solutions


    #-------------------------------------------------------------------------------
    #   private attributes
    #
    #   @pegs           array of Peg positions on the board - one for each hole
    #   @dupes          counter of duplicate (non-unique) solutions found
    #-------------------------------------------------------------------------------

    #-------------------------------------------------------------------------------
    # Board::initialize()
    #++
    #   constructor - defines and initializes object attributes
    #-------------------------------------------------------------------------------
    def initialize(pegs = Array.new)
        # for this application, the given pegs array SHOULD have 15 elements.
        #  Any missing elements will get default (empty) positions.  Excess
        #  positions will be ignored.
        n = min(pegs.length, 15)
        i = 0
        @pegs = Array.new

        # use the elements in the given pegs array
        n.times do
            @pegs[i] = Peg.new(pegs[i][0], pegs[i][1])
            i += 1
        end

        # now deal with any shortage in the given pegs array
        (15 - i).times do
            @pegs[i] = Peg.new(0)
            i += 1
        end

        # ... and, of course, initially our solutions are blank/unkonwn
        @solutions = Array.new
        @dupes = 0
    end



    #-------------------------------------------------------------------------------
    # Board::analyze()
    #++
    #   returns a hash containing 'interesting' summary values about our solutions
    #-------------------------------------------------------------------------------
    def analyze
        h = Hash.new(0)     # set zero as a default value
        f = File.open("pegboard.dat", "w")

        # how many solutions do we have?
        h[:solutions] = @solutions.length

        # which is the last peg standing?
        h[:last_peg] = Hash.new(0)
        @solutions.each do | solution |
            f << "#{mkhash(solution)} :: #{solution}\n"
            final_step = solution[-1]
            last_peg = final_step[:choices][final_step[:choice]][1]
            h[:last_peg][last_peg] += 1
        end

        f.close
        return h
    end



    #-------------------------------------------------------------------------------
    # Board::choices()
    #++
    #   returns an array containing all the moves possible with the current pegs
    #-------------------------------------------------------------------------------
    def choices

        choices = Array.new
        i_choice = 0
        i_peg = 0

        # iterate our Pegs, looking for any that are OCCUPIED and have OCCUPIED
        # neighbors they can jump over to an OPEN target
        @pegs.each do | peg |
            if peg.occupied?
                peg.neighbors.each do | neighbor |
                    jumpee = neighbor[0]
                    target = neighbor[1]
                    if (@pegs[jumpee].occupied? && !@pegs[target].occupied?)
                        choices[i_choice] = [i_peg, target]
                        i_choice += 1
                    end
                end
            end
            i_peg += 1
        end

        return choices
    end



    #-------------------------------------------------------------------------------
    # Board::finished?()
    #++
    #   indicates whether any more moves can be made on the board.
    #-------------------------------------------------------------------------------
    def finished?
        return (choices().length == 0)
    end



    #-------------------------------------------------------------------------------
    # Board::mkhash()
    #++
    #   returns a 'hash' string for the given solution by simply concatenating the
    #   numerals in the choice for each step therein
    #-------------------------------------------------------------------------------
    def mkhash(solution)
        hash = ""
        solution.each do | step |
            hash += step[:choice].to_s
        end
        return hash
    end



    #-------------------------------------------------------------------------------
    # Board::move()
    #++
    #   Attempts to move from the given source location to the destination.  May
    #   raise exceptions if you try to execute an invalid move.
    #-------------------------------------------------------------------------------
    def move(src, dst)
        if (!src.kind_of?(Fixnum) || !dst.kind_of?(Fixnum))
            raise BadMoveError, "I can't work with this.  Give me numbers people!"
        end

        jumpee = @pegs[src].jumped_neighbor(dst)

        if (!@pegs[src].occupied? or !@pegs[jumpee].occupied? or @pegs[dst].occupied?)
            raise BadMoveError, "That's just not right."
        end

        # OK, it's all good ... let's get a move on!
        @pegs[src].move_out!
        @pegs[jumpee].jumped!
        @pegs[dst].move_in!
    end



    #-------------------------------------------------------------------------------
    # Board::pegs_remaining()
    #++
    #   returns the number of Pegs remaining on our board
    #-------------------------------------------------------------------------------
    def pegs_remaining
        n = 0
        @pegs.each do | peg |
            n += 1 if peg.occupied?
        end
        return n
    end



    #-------------------------------------------------------------------------------
    # Board::solutions=
    #++
    #   Records the given solution in our solutions collectin IF it is proven to be
    #   a solution we haven't seen before ... and we have a VERY good memory!
    #-------------------------------------------------------------------------------
    def solutions=(candidate)
        #
        # before accepting this "new" solution ... let's make sure it really
        #  IS unique.  Remember that a solution is an array of steps and each
        #  step contains a selected choice and a list of choices from which
        #  to choose
        #
        unique = false
        unique = true if @solutions.length == 0
        @solutions.each do | solution |
            # compare each solution with the candidate step by step
            istep = 0
            solution.each do | step |
                same_choice = (step[:choice] == candidate[istep][:choice])
                if !same_choice
                    unique = true
                    break
                end
                istep += 1
            end

            # I know this process seems somewhat disjointed and laborious, but
            #  this should execute quite a bit faster, especially as the list
            #  of solutions grows
            if (!unique)
                # if at first we don't 'look' unique ... check the choices arrays
                istep = 0
                solution.each do | step |
                    same_choices = (step[:choices] == candidate[istep][:choices])
                    if !same_choices
                        unique = true
                        break
                    end
                    istep += 1
                end
            end
        end

        if unique or true
            # ruby's .clone() and .dup() only do shallow copies i.e. the steps
            #  in given solution will remain vulnerable to being overwritten
            #  unless we do a deep copy here.  The "cheap" method for doing that
            #  is to marshal the candidate object out/in before storing
            @solutions << Marshal.load(Marshal.dump(candidate))
            printf "found another solution: %d   dupes: [%d]\r", @solutions.length, @dupes
        else
            @dupes += 1
        end
    end



    #-------------------------------------------------------------------------------
    # Board::to_s()
    #++
    #   default string representation of the board
    #-------------------------------------------------------------------------------
    def to_s
        s =  "\n"
        s << "      #{@pegs[0].to_s}\n"
        s << "     #{@pegs[1].to_s} #{@pegs[2].to_s}\n"
        s << "    #{@pegs[3].to_s} #{@pegs[4].to_s} #{@pegs[5].to_s}\n"
        s << "   #{@pegs[6].to_s} #{@pegs[7].to_s} #{@pegs[8].to_s} #{@pegs[9].to_s}\n"
        s << "  #{@pegs[10].to_s} #{@pegs[11].to_s} #{@pegs[12].to_s} #{@pegs[13].to_s} #{@pegs[14].to_s}\n"
        return s
    end



    #-------------------------------------------------------------------------------
    # Board::unmove()
    #++
    #   Reverses a previous move denoted by the given original source and destination.
    #   We will raise exceptions if you try to execute an invalid unmove.
    #-------------------------------------------------------------------------------
    def unmove(src, dst)
        if (!src.kind_of?(Fixnum) || !dst.kind_of?(Fixnum))
            raise BadMoveError, "I can't with this.  Give me numbers people!"
        end

        jumpee = @pegs[src].jumped_neighbor(dst)

        # ensure we've got pegs and openings in the right places ...
        if (@pegs[src].occupied? or @pegs[jumpee].occupied? or !@pegs[dst].occupied?)
            raise BadMoveError, "That's just not right."
        end

        # OK, it's all good ... let's get an unmove on!
        @pegs[src].move_in!
        @pegs[jumpee].move_in!
        @pegs[dst].move_out!
    end
end     # end of class Board


#-------------------------------------------------------------------------------
# solve                                                     by alan partis
#++
#   OK, now we need to get serious ... a 'solution' is composed of a number of
#   steps (a maximum of 13 of them if only 1 peg remains at the end).  So we
#   could maintain an array of Steps that are composed of the available choices
#   at that time, plus the choice currently taken.  At the end, the solution
#   should be obvious.
#
#   We'll go through an iterative 'stack' approach to do this ... for the moment
#   anyway.  This feels wrong -- it seems like I should be implementing a
#   recursive solution -- but almost "looks" right in my head.  Let's see how it
#   works out on paper <grin>
#-------------------------------------------------------------------------------
def solve(board)

    done = false
    new_step = true
    solution = Array.new
    step = 0

    # let's take the first step and see how it goes ...
    while (!done)
        if new_step
            # as we go up, initialize a new step
            solution[step] = Hash.new
            solution[step][:choice] = 0
            solution[step][:choices] = board.choices
        end

        # make your move
        choice = solution[step][:choice]
        move_src = solution[step][:choices][choice][0]
        move_dst = solution[step][:choices][choice][1]
        board.move(move_src, move_dst)

        # if we're not finished then go to the next step
        if !board.finished?
            new_step = true
            step += 1
        else

            # if we found a solution, report it.
            if (board.pegs_remaining == 1)
                board.solutions = solution
            end

            # whether we found a solution or not, we've come to the end of this
            #  permutation.  Undo the last move and see if there were other
            #  choices we could make
            board.unmove(move_src, move_dst)

            # if there are more choices in this step, choose the next choice, but
            #  stay in this step
            last_option = solution[step][:choices].length - 1

            if (choice < last_option)
                # we have at least one more choice in this step ...
                solution[step][:choice] += 1
                new_step = false
            else
                #
                # out of choices in this step ... look back for a step with
                #  choices remaining
                #
                while ((step > 0) and (choice == last_option))

                    solution.pop
                    step -= 1
                    choice = solution[step][:choice]
                    move_src = solution[step][:choices][choice][0]
                    move_dst = solution[step][:choices][choice][1]
                    board.unmove(move_src, move_dst)

                    last_option = solution[step][:choices].length - 1

                    # if there are more choices in this previous step, choose the
                    #  next one and again, stay in that step
                    if (choice < last_option)
                        solution[step][:choice] += 1
                        new_step = false
                    end
                end

                if ((step == 0) and (choice == last_option))
                    # there's nothing left to try -- we're done
                    done = true
                end
            end
        end
    end
end



#-------------------------------------------------------------------------------
# main program entry point                                  by alan partis
#++
#   Initialize our options and proceed to find a solution for our game board.
#   Print out completion stats when done.
#-------------------------------------------------------------------------------
begin

    board = Board.new(START)
    solve board

    puts board
    if board.finished?
        puts "#{board.pegs_remaining} pegs remain on the board"
        case board.pegs_remaining
            when 0 then puts "something's wrong ... the board is empty!"
            when 1 then puts "You're a genius."
            when 2 then puts "You're purty smart."
            when 3 then puts "You're just plain dumb."
            else        puts "You're eg-no-ra-moose!"
        end
    else
        puts "You're not done yet, there are still more moves available."
    end

    puts "analyzing ... results in pegboard.dat when I'm done."
    pp board.analyze

rescue StandardError => e

    puts
    puts e
    puts e.backtrace.join("\n")

end
# end of program