# == Synopsis
#
# Library to support Trap the Cap play
# 
# == Author
# Neil Smith
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program.  If not, see <http://www.gnu.org/licenses/>.
#
# == Change history
# Version 1.1::  07 Sep 2007  
#                * Changed format for showing moves via bases.
#                * Raise error when moving via base without captured pieces
#                * Raise error when moving onto a safe space with 3 or more 
#                  pieces already there
# Version 1.2::  10 Sep 2007  
#                * Incorporated changes in move legality above into 
#                  Game#possible_moves
# Version 1.3::  25 Mar 2008  
#                * Fixed bug to detect a winner, and also eliminate players 
#                  that have no uncaptured pieces.

# Errors for a game

# Pieces can only capture pieces that they're on.
class InvalidCaptureError < StandardError
end

# Moves can only be [1..6] spaces
class InvalidMoveError < StandardError
end

# Game is won when only one player has uncaptured pieces
class GameWonNotice < StandardError
end


# Each possible position for a piece is an object
# Each neighbour is another position object
class Position
  attr_reader :place        # the name of this place
  attr_accessor :contains   # the pieces it contains
  attr_accessor :neighbours # the positions that neighbour it

  def initialize(place, safety, base)
    @place = place
    @safe = safety
    @base = base
    @neighbours = Array.new
  end

  # is this position a safety one (i.e. no captures allowed)?
  def safe?
    @safe
  end

  # Is this position a base?
  def base?
    @base
  end

  def to_s
    @place
  end

  def to_str
    to_s
  end
  
end


# The game board
class Board

  attr_reader :positions
  attr_reader :valid_moves
  attr_reader :distance_between
  attr_reader :centre


  # A laborious procedure to create all the positions and tie them all together
  def initialize(spokes, spoke_length, arc_length)
    # A hash of all positions, indexed by position names
    @positions = Hash.new   
    @centre = Position.new('ac' + spoke_length.to_s, false, false)
    @positions['ac' + spoke_length.to_s] = centre
    a1_corner = nil
    end_of_previous_arc = nil

    # Do each arc-spoke-base set
    (?a...(?a + spokes)).each do |arc_code|
      arc = arc_code.chr
      base = Position.new(arc, false, true)
      this_arc = Array.new
      
      # build the arc
      (1..arc_length).each do |arc_position|
        position_name = arc + arc_position.to_s
        arc_place = Position.new(position_name, arc_position == 4, false)
        arc_place.neighbours = []
        @positions[position_name] = arc_place
        this_arc << arc_place
        a1_corner = a1_corner || arc_place
      end
      (0...arc_length).each do |arc_position|
        if arc_position > 0
          this_arc[arc_position].neighbours << this_arc[arc_position - 1]
        end
        if arc_position < (arc_length - 1)
          this_arc[arc_position].neighbours << this_arc[arc_position + 1]
        end
      end
        
      # build the spoke
      this_spoke = Array.new
      (1..(spoke_length - 1)).each do |spoke_position|
        position_name = arc + "c" + spoke_position.to_s
        spoke_place = Position.new(position_name, spoke_position == 3, false)
        spoke_place.neighbours = []
        @positions[position_name] = spoke_place
        this_spoke << spoke_place
      end
      (0...(spoke_length - 1)).each do |spoke_position|
        if spoke_position > 0
          this_spoke[spoke_position].neighbours << this_spoke[spoke_position - 1]
        end
        if spoke_position < spoke_length - 2
          this_spoke[spoke_position].neighbours << this_spoke[spoke_position + 1]
        end
      end
      
      # tie the spoke and arc together, 
      this_arc[0].neighbours << this_spoke[0]
      this_spoke[0].neighbours << this_arc[0]

      # tie the spoke to the centre, and
      this_spoke[-1].neighbours << @centre
      @centre.neighbours << this_spoke[-1]
      
      # tie the base to the arc
      base = Position.new(arc, false, true)
      @positions[arc] = base
      base.neighbours << this_arc[0]
      this_arc[0].neighbours << base

      # record the ends of the arc for tying to adjacent arcs
      if end_of_previous_arc
        end_of_previous_arc.neighbours << this_arc[0]
        this_arc[0].neighbours << end_of_previous_arc
      end
      end_of_previous_arc = this_arc[-1]

    end # arc

    # tie both ends of the rim together 
    a1_corner.neighbours << end_of_previous_arc
    end_of_previous_arc.neighbours << a1_corner

    cache_valid_moves

  end # def

  def to_s
    layout
  end
  
  def to_str
    to_s
  end
  
  
  # For each position, show its name and what it touches
  def layout
    out_string = ""
    @positions.keys.sort.each do |position|
      out_string << sprintf("%s touches ", @positions[position])
      @positions[position].neighbours.each do |neighbour|
        out_string << sprintf("%s, ", neighbour)
      end
      out_string << sprintf("\n")
    end
    out_string
  end


  # Precompute the valid moves for this board, and the distances between each 
  # pair of positions
  def cache_valid_moves
    # A hash of arrays.  The has key is the name of a positions.  The array 
    #  element [i] stores the positions that are i spaces from here
    @valid_moves = Hash.new
    # A hash of hashes.  Given two names, return the shortest distance between
    #  the two locations
    @distance_between = Hash.new
    @positions.each do |place, position|
      @valid_moves[place] = Array.new
      @distance_between[place] = Hash.new
      @valid_moves[place][0] = [@positions[place]]
      @distance_between[place][place] = 0
      # Find the shortest routes by Dijkstra's algorithm
      agenda = [position]
      closed_list = [position]
      i = 1
      while not agenda.empty?
        @valid_moves[place][i] = []
        new_agenda = []
        agenda.each do |pos|
          valid_extensions = pos.neighbours.reject {|new_position| closed_list.include?(new_position) }
          @valid_moves[place][i] += valid_extensions
          valid_extensions.each {|ext| @distance_between[place][ext.place] ||= i }
          closed_list += valid_extensions
          new_agenda += valid_extensions
        end
        agenda = new_agenda
        i += 1
      end
    end
  end

end


# Each piece on the board is an object
class Piece
  attr_reader :colour
  attr_accessor :position, :contains, :captured

  def initialize(number, position, colour)
    @number = number
    @position = position
    @colour = colour
    @captured = false
    @contains = []
  end

  def name
    @colour + @number.to_s
  end

  def to_s
    self.name
  end
  
  def to_str
    to_s
  end

  def move_to(new_position)
    @position = new_position
    @contains.each {|c| c.move_to(new_position)}
  end

  # Caputre another piece
  def capture(other_piece)
    if @position = other_piece.position
      @contains << other_piece
      @contains += other_piece.contains
      other_piece.contains = []
      other_piece.captured = true
    else
      raise(InvalidCaptureError, 
        "Piece #{self.name} cannot capture #{other_piece.name}: different locations")
    end
  end

end


# A move in a game
class Move
  attr_reader :piece, :destination
  
  def initialize(piece, destination, via_base = false)
    @piece = piece
    @destination = destination
    @via_base = via_base
  end
  
  def via_base?
    @via_base
  end

  # Write a move to a string
  # Note the inverse, String#to_move, is defined below
  def to_s
    if @via_base
      if @destination.base?
        @piece.to_s + " "  + @destination.to_s
      else
        @piece.to_s + " " + piece.colour + " " + @destination.to_s
      end
    else
      @piece.to_s + " " + @destination.to_s
    end
  end
  
  def to_str
    to_s
  end
  
end



# A class to record each of the states previously found in a game.  
# Note that this is a deep copy of the pieces and what they've captured, so 
# you'll need to convert back
class GameState
  attr_accessor :move, :player, :pieces_after_move
  
  def initialize(move, player, pieces)
    @move = move
    @player = player
    @pieces_after_move = Hash.new
    pieces.each {|k, p| @pieces_after_move[k] = p.dup}
    @pieces_after_move.each_value {|p| p.contains = []}
    # and now to make the captured pieces point to the copies
    pieces.each do |k, p|
      p.contains.each do |captured_piece|
        @pieces_after_move[k].capture(@pieces_after_move[captured_piece.name])
      end
    end
  end
  
  def ==(other)
    @move.to_s == other.move.to_s and
      @player == other.player and
      @piece_after_move == other.pieces_after_move
  end
  
end


# A game of Trap the Cap.  It keeps a history of all previous states.  
class Game

  attr_reader :history
  attr_reader :current_player, :players
  attr_reader :board
  attr_reader :pieces

  # Create a new game
  def initialize(players = 6, spokes = 6, spoke_length = 6, arc_length = 6, 
      pieces_each = 6)
    @board = Board.new(spokes, spoke_length, arc_length)
    @history = []
    @pieces = Hash.new
    @players = case
    when players == 2 ; ['a', 'd']
    when players == 3 ; ['a', 'c', 'e']
    when players == 4 ; ['a', 'b', 'd', 'e']
    when players == 5 ; ['a', 'b', 'c', 'd', 'e']
    when players == 6 ; ['a', 'b', 'c', 'd', 'e', 'f']
    end
    @current_player = 'a'
    @players.each do |player|
      players_base = @board.positions[player]
      (1..pieces_each).each do |count|
        piece = Piece.new(count, players_base, player)
        @pieces[player + count.to_s] = piece
      end
    end
  end
  

  # Apply a single move to a game.  
  def apply_move!(move, player = @current_player)
    # Check the move is a valid one
    raise(InvalidMoveError, "Piece #{move.piece} does not exist") unless @pieces.has_key?(move.piece.name)
    raise(InvalidMoveError, "Player #{player} moving piece #{move.piece}") unless move.piece.colour == player
    raise(InvalidMoveError, "Attempting to move captured piece #{move.piece}") if move.piece.captured
    raise(InvalidMoveError, "Attempting to move #{move.piece} onto or via base without captured pieces") if move.via_base? and move.piece.contains.empty?
    if move.destination.safe?
      if (@pieces.find_all {|k, p| p.position == move.destination}).length >= 3
        raise(InvalidMoveError, "Attempting to move #{move.piece} onto safe position #{move.destination} when there are already three or more pieces there")
      end
    end
    if move.via_base?
      moved_distance = board.distance_between[move.piece.position.place][player] +
        board.distance_between[player][move.destination.place]
    else
      moved_distance = board.distance_between[move.piece.position.place][move.destination.place]
    end
    raise(InvalidMoveError, "Attempting to move piece #{move.piece} #{moved_distance} places (from #{move.piece.position} to #{move.destination})") if moved_distance < 1 or moved_distance > 6

    # Apply this move
    move.piece.move_to(move.destination)

    # Capture anything already there (unless it's a safe place or a base, 
    # or our own colour, or already captured)
    unless move.destination.safe? or move.destination.base?
      @pieces.each do |name, target_piece|
        if target_piece.position == move.destination and 
            target_piece != move.piece and
            not move.piece.contains.member?(target_piece) and
            target_piece.colour != player and
            not target_piece.captured
          move.piece.capture(target_piece)
        end
      end
    end
    
    # If the move was via our base, drop all captured pieces
    if move.via_base?
      capturers_base = board.positions[move.piece.colour]
      move.piece.contains.each do |captured_piece|
        captured_piece.move_to capturers_base
        captured_piece.captured = false if captured_piece.colour == move.piece.colour
      end
      move.piece.contains = []
    end
    
    # Record the new stae
    this_game_state = GameState.new(move, player, @pieces)
    @history << this_game_state

    # Retain only players that have uncaptured pieces.  
    # If there's only one player with uncaptured pieces, declare a win.
    potential_players = []
    @players.each do |p|
      if (@pieces.values.select {|piece| piece.colour == p}).any? {|piece| not piece.captured}
        potential_players << p
      end
      #      potential_players << p if (@pieces.values.select {|p| p.colour == @current_player}).any? {|p| not p.captured}
    end
    if potential_players.length <= 1
      raise(GameWonNotice, "Game won by #{potential_players[0]}")
    end
    @players = potential_players.sort
  end
  
  # Undo a move 
  def undo_move!
    if @history.length > 1
      # general case
      state_to_restore = @history[-2]
      @current_player = @history[-1].player
      @pieces.each do |name, piece| 
        copy_piece = state_to_restore.pieces_after_move[name]
        piece.position = copy_piece.position
        piece.captured = copy_piece.captured
        piece.contains = []
        copy_piece.contains.each do |p|
#          piece.capture(@pieces[p.name])
          piece.contains << @pieces[p.name]
        end
      end
      @history.pop    
    elsif @history.length == 1
      # reset to start
      @current_player = 'a'
      @pieces.each do |name, piece| 
        piece.position = @board.positions[piece.colour]
        piece.captured = false
        piece.contains = []
      end
      @history.pop    
    end
  end
    
  # Apply a list of moves in order
  def apply_moves!(moves)
    moves.each do |move| 
      if move.via_base?
        moved_distance = board.distance_between[move.piece.position.place][@current_player] +
          board.distance_between[@current_player][move.destination.place]
      else
        moved_distance = board.distance_between[move.piece.position.place][move.destination.place]
      end
      self.apply_move!(move, @current_player)
      next_player! unless moved_distance == 6
    end
  end


  # Set the current player to be the next player
  def next_player!
    original_player = @current_player
    begin
      if @current_player == @players[-1]
        @current_player = @players[0]
      else
        @current_player = @players[@players.index(@current_player) + 1]
      end
    end while (@pieces.values.select {|p| p.colour == @current_player}).all? {|p| p.captured} and @current_player != original_player
    @current_player
  end


  # Return an array of all possible moves from this state, given the die roll 
  # and the active player
  def possible_moves(die_result, player = @current_player)
    moves = []
    @pieces.each do |key, piece|
      # only move current player's pieces, and only if they're not captured
      if piece.colour == player and (not piece.captured)
        (@board.valid_moves[piece.position.place][die_result]).each do |destination|
          if destination.safe?
            if (@pieces.find_all {|k, p| p.position == destination}).length < 3
              moves << Move.new(piece, destination, false)
            end
          else
            moves << Move.new(piece, destination, false) unless destination.base?
          end
        end
        # if we can move to our base (but not already on it), add moves via that...
        if @board.distance_between[piece.position.place][player] <= die_result and 
            not piece.position.place == player and
            not piece.contains.empty?
          distance_after_base = die_result - @board.distance_between[piece.position.place][player]
          (@board.valid_moves[player][distance_after_base]).each do |destination|
            if destination.safe?
              if (@pieces.find_all {|k, p| p.position == destination}).length < 3
                moves << Move.new(piece, destination, true)
              end
            else
              moves << Move.new(piece, destination, true)
            end
          end
        end
      end
    end
    moves
  end


  def build_state_string
    outstr = "Current player = #{@current_player}\n"
    @pieces.keys.sort.each do |piece_name|
      if @pieces[piece_name].captured
        outstr << "Piece #{piece_name} captured, at #{@pieces[piece_name].position}\n"
      else
        outstr << "Piece #{piece_name} is at #{@pieces[piece_name].position}, holds #{(@pieces[piece_name].contains.collect{|c| c.name}).join(' ')}\n"
      end
    end
    outstr
  end
  
  # Show the state of the board
  def show_state
    puts build_state_string
#    @pieces.keys.sort.each do |piece_name|
#      if @pieces[piece_name].captured
#        puts "Piece #{piece_name} captured, at #{@pieces[piece_name].position}"
#      else
#        puts "Piece #{piece_name} is at #{@pieces[piece_name].position}, holds #{(@pieces[piece_name].contains.collect{|c| c.name}).join(' ')}"
#      end
#    end
  end

  def to_s
    show_state
  end
  
  def to_str
    to_s
  end
  
  
  # Given a set of lines from an input file, turn them into a Game object and 
  # a set of Move objects.
  # Note the multiple return values.
  # Class method
  def Game.read_game(gamelines)
    gamelines.each {|l| l.chomp!}
    game = Game.new(gamelines[0].to_i, 6, 6, 6, 6)
    moves = []
    gamelines[1..-2].each {|m| moves << m.to_move(game)}
    return game, moves, gamelines[-1].to_i
  end


end
  

# Extension to String class to convert a move-description string into a Move object.  
# This is the inverse of the Move#to_s method
class String
  def to_move(game)
    move_elements = self.downcase.split
    piece_name = move_elements[0]
    destination_name = move_elements[-1]
    if destination_name.length > 2 and 
        destination_name[-2,2] == game.board.centre.place[-2,2]
      destination_name = game.board.centre.place
    end
    raise(InvalidMoveError, "Invalid piece in move read") unless game.pieces.has_key?(piece_name)
    raise(InvalidMoveError, "Invalid destination in move read") unless game.board.positions.has_key?(destination_name)
    # Deal with the synonyms for the centre position
    via_base = (destination_name.length == 1 or move_elements.length > 2)
    Move.new(game.pieces[piece_name], game.board.positions[destination_name], via_base)
  end
end


# Read a game description file and convert it into a Game object and set of Move objects.
# Note that Game.read_game method returns multiple values, so this one does too.
class IO
  def IO.read_game(filename)
    gamelines = IO.readlines(filename)
    return Game.read_game(gamelines)
  end
end