checkers.cr

class Board
  getter rows
  getter moves
  getter x
  getter y
  getter previous_board
  getter hash

  def initialize(@rows, @x, @y, @moves = 0, @previous_board = nil)
    @length_y = @rows.length
    @length_x = @rows[0].length
    @hash = @rows.hash
  end

  Moves = [
    [0, -2], [0, 2], [-2, 0], [2, 0],
    [0, -1], [0, 1], [-1, 0], [1, 0],
  ]

  def each_next_board
    Moves.each do |move|
      move_x, move_y = move
      occupied_x, occupied_y = @x + move_x, @y + move_y

      if piece = piece_in(occupied_x, occupied_y)
        new_rows = @rows.clone
        new_rows[@y][@x] = piece
        new_rows[occupied_y][occupied_x] = :_
        yield new_next_board(new_rows, occupied_x, occupied_y)
      end
    end
  end

  def new_next_board(rows, x, y)
    Board.new(rows, x, y, @moves + 1, self)
  end

  def []?(x, y)
    return nil if x < 0 || x >= @length_x || y < 0 || y >= @length_y
    @rows[y][x]
  end

  def piece_in(x, y)
    value = self[x, y]?
    (value == :w || value == :b) ? value : nil
  end

  def ==(other : self)
    @hash == other.hash && @rows == other.rows
  end

  def to_s
    String.build do |str|
      str << "In #{@moves} moves:\n"
      @rows.each_with_index do |row, i|
        str << "\n" if i > 0
        row.each do |value|
          case value
          when :b then str << "\033[1;31mo\033[0m"
          when :w then str << "\033[1;34mo\033[0m"
          else str << " "
          end
        end
      end
    end
  end
end

def print_winning(board)
  if previous_board = board.previous_board
    print_winning(previous_board)
  end
  puts board
end

rows = [
      [:x, :x, :w, :w, :w],
      [:x, :x, :w, :w, :w],
      [:b, :b, :_, :w, :w],
      [:b, :b, :b, :x, :x],
      [:b, :b, :b, :x, :x],
    ]

x = nil
y = rows.index do |row|
  index = row.index :_
  if index
    x = index
    true
  else
    false
  end
end
x = x.not_nil!
y = y.not_nil!

winning_rows = rows.clone
winning_rows.each_with_index do |winning_row, ry|
  winning_row.each_with_index do |value, rx|
    if value == :w
      winning_row[rx] = :b
    elsif value == :b
      winning_row[rx] = :w
    end
  end
end

initial_board = Board.new(rows, x, y)
winning_board = Board.new(winning_rows, x, y)

found = Set.new [initial_board]
remaining = [initial_board]

last_moves = 0
index = 0

while !remaining.empty?
  board = remaining.shift

  if board.moves > last_moves
    last_moves = board.moves
    puts last_moves
  end

  board.each_next_board do |next_board|
    unless found.includes? next_board
      if next_board == winning_board
        print_winning next_board
        exit
      end

      found.add next_board
      remaining.push next_board
    end
  end
end