Sample stuff for gaming with coding_game

coding_game.rb

require "minitest/autorun"
require "pry-byebug"

class Position

  DIRECTIONS= %i(north east south west)

  class Radius
    include Enumerable
    def initialize(value); @value =value; end
    def each
      (-@value..@value).each do |i|
        (-@value..@value).each do |j|
          yield(Position.new(i,j))
        end
      end
    end
  end

  attr_accessor :x, :y

  def initialize(x,y); @x,@y=x,y; end

  def self.opposed(direction);
    DIRECTIONS[(DIRECTIONS.index(direction) + 2) % 4]
  end

  def move_north!(cell=1); @y-=cell; self; end
  def move_east! (cell=1); @x+=cell; self; end
  def move_south!(cell=1); @y+=cell; self; end
  def move_west! (cell=1); @x-=cell; self; end

  def move!(direction, cell=1)
    __send__("move_#{direction}!", cell);
  end

  def move(direction, cell=1)
    Position.new(x,y).move!(direction, cell)
  end

  def +(other)
    self.x = x + other.x; self.y = y + other.y; self
  end
  def -(other)
    self.x = x - other.x; self.y = y - other.y; self
  end

  def ==(other);    x == other.x && y == other.y; end
  def !=(other);    !(self == other);             end

  def hash;         to_a.hash;                    end
  def eql?(other);  self == other;                end

  def <(other); x < other.x || (x == other.x && y < other.y); end
  def >(other); x > other.x || (x == other.x && y > other.y); end

  def circle_area(radius);
    Radius.new(radius).map do |pos|
      pos + self if (pos.x.abs + pos.y.abs) <= radius
    end.compact
  end

  def square_area(radius);
    Radius.new(radius).map { |pos| pos + self }
  end

  def to_s; "(#{x},#{y})";  end
  def to_a; [x,y];          end
end

class Grid2D
  include Enumerable

  def initialize(width, height)
    @width, @height = width, height
    @_data = Array.new(size())
  end

  def set(x,y, value)
    if (index = to_index(x,y))
      @_data[index]= value
    end
  end

  def get(x,y)
    to_index(x,y) && @_data[to_index(x,y)]
  end

  def clone;
    copy = Grid2D.new(@width, @height)
    copy.instance_variable_set(:@_data, @_data.clone)
    return copy
  end

  def size();   @width * @height; end
  def width();  @width;           end
  def height(); @height;          end

  def [](position);         get(position.x,position.y);         end
  def []=(position, value); set(position.x, position.y, value); end

  def each
    return enum_for(:each) unless block_given?
    @_data.each_with_index do |value, index|
      yield(to_position(index), value)
    end
  end

  def slice(*positions); positions.map { |pos| self[pos] }.compact; end

  def to_s
    cell_to_s = -> (pos, value) { "#{pos} => #{value}" }
    max_cell_size = map { |pos, value| cell_to_s.call(pos, value).length }.max
    row_separator=nil
    out = "\n"
    (0...@height).each do |col|
      row_line=(0...@width).map do |row|
        pos, value = Position.new(row,col), get(row, col)
        cell_to_s.call(pos, value).center(max_cell_size)
      end.join(" | ")
      row_separator ||= "| "+"-"*row_line.size + " |\n"
      out+=row_separator
      out+="| #{row_line} |\n"
    end
    out+=row_separator+"\n"
    out
  end

  def include?(x,y); !!to_index(x,y); end

  private
  def to_position(index);
    Position.new(index % width, index/@width)
  end

  def to_index(x,y)
    index = (x + y * @width)
    return index if x >= 0 && y >= 0 && y < @height && x < @width
    return nil
  end
end

class Cell
  Neighbor = Struct.new(:distance, :direction) do
    def <=>(other); self.distance <=> other.distance; end
  end

  attr_accessor :uid, :data, :neighbors

  def initialize(uid, data);
    @uid, @data, @neighbors = uid, data, {}
  end

  def set_neighbor(uid, distance, direction)
    @neighbors[uid] = Neighbor.new(distance, direction)
  end

  def accessible?(); true;                end
  def <=>(other);    data <=> other.data; end
  def to_s;          data.to_s;           end
end

class GameCell < Cell
  def accessible?(); data != 'X'; end
end

class PathFinder
  def initialize(grid); @grid; end

  def shortest(from, to);
    return nil unless @grid.slice(from, to).all?(&:accessible?)
    @visited, @to_visit, current_uid = {}, [[0, from, nil]], nil

    while(!@to_visit.empty? && current_uid != to)
      @to_visit.sort_by! { |dist, _| dist }
      distance, current_uid, previous_uid = @to_visit.shift
      @visited[current_uid] ||= begin
        @grid[current_uid].neighbors.each do |ngh_uid, ngh_data|
          next unless @grid[ngh_uid].accessible?
          @to_visit << [
            distance + ngh_data.distance,
            ngh_uid, current_uid ]
        end
        [distance, previous_uid]
      end
    end

    distance, res_to = @visited[to]

    return nil unless res_to
    loop do
      break if @visited[res_to].last == from
      res_to = @visited[res_to].last
    end
    {
      to: res_to,
      dir: @grid[from].neighbors[res_to].direction,
      dist: distance
    }
  end

  def longest(from, to_conditions=[]);
    to_conditions << ->(visited) {
      visited.max_by { |k,v| v.first }
    }
    return nil unless @grid[from]&.accessible?
    @visited, @to_visit, current_uid = {}, [[0, from, nil]], nil

    while(!@to_visit.empty?)
      @to_visit.sort_by! { |dist, _| dist }
      distance, current_uid, previous_uid = @to_visit.shift
      @visited[current_uid] ||= begin
        @grid[current_uid].neighbors.each do |ngh_uid, ngh_data|
          next unless @grid[ngh_uid].accessible?
          @to_visit << [
            distance + ngh_data.distance,
            ngh_uid, current_uid ]
        end
        [distance, previous_uid]
      end
    end

    res_to, (distance, _) = to_conditions.map { |method|
      method.call(@visited) }.first
    loop do
      break if @visited[res_to].last == from
      res_to = @visited[res_to].last
    end

    {
      to: res_to,
      dir: @grid[from].neighbors[res_to].direction,
      dist: distance
    }
  end

  def to_s;
    to_display = @grid.clone
    @visited.each do |distance, origin|
      to_display[distance] = origin
    end
    to_display.to_s
  end
end

class Grid2DTest < Minitest::Test

  def init_grid(data = nil, cell_klass = nil)
    data ||= [
      ['(x0,y0)', '(x1,y0)', '(x2,y0)', '(x3,y0)'],
      ['(x0,y1)', '(x1,y1)', '(x2,y1)', '(x3,y1)'],
      ['(x0,y2)', '(x1,y2)', '(x2,y2)', '(x3,y2)'],
    ]

    width = data.map { |row| row.size }.max
    height = data.size
    grid = Grid2D.new(width, height)

    data.each_with_index do |row, col_index|
      row.each_with_index.each do |value, row_index|
        c_pos = Position.new(row_index,col_index)
        cell = (cell_klass || Cell).new(c_pos, value)
        Position::DIRECTIONS.each do |dir|
          dir_pos = c_pos.move(dir)
          cell.set_neighbor(dir_pos, 1, dir) if grid.include?(dir_pos.x, dir_pos.y)
        end
        grid.set(row_index, col_index, cell)
      end
    end
    grid
  end

  def test_opposed_directions
    assert_equal :north, Position.opposed(:south)
    assert_equal :south, Position.opposed(:north)
    assert_equal :east,  Position.opposed(:west)
    assert_equal :west,  Position.opposed(:east)
  end

  def test_size_grid
    grid = init_grid();
    assert_equal 4*3, grid.size()
    assert_equal 4,   grid.width()
    assert_equal 3,   grid.height()
  end

  def test_set_get;
    grid = init_grid();
    assert_equal '(x0,y0)', grid.get(0,0).data
    assert_equal '(x0,y1)', grid.get(0,1).data
    assert_equal '(x0,y2)', grid.get(0,2).data
    assert_equal '(x1,y0)', grid.get(1,0).data
    assert_equal '(x1,y1)', grid.get(1,1).data
    assert_equal '(x1,y2)', grid.get(1,2).data
    assert_equal '(x2,y2)', grid.get(2,2).data
    assert_nil grid.get(2,3)
    assert_nil grid.get(-1,0)
  end

  def test_neighbors;
    grid = init_grid();
    neighbors_data = ->(x,y) {
      positions = grid.get(x,y).neighbors.keys
      grid.slice(*positions).map(&:data).sort
    }

    assert_equal ['(x1,y0)', '(x0,y1)'].sort, neighbors_data.call(0,0)
    assert_equal ['(x1,y2)', '(x0,y1)'].sort, neighbors_data.call(0,2)
    assert_equal ['(x1,y0)', '(x0,y1)', '(x2,y1)', '(x1,y2)'].sort, neighbors_data.call(1,1)
    assert_equal ['(x0,y2)','(x1,y1)','(x2,y2)'].sort, neighbors_data.call(1,2)
    assert_equal ['(x1,y1)', '(x2,y0)', '(x2,y2)', '(x3,y1)'].sort, neighbors_data.call(2,1)
    assert_equal ['(x2,y0)', '(x3,y1)'].sort, neighbors_data.call(3,0)
  end

  def test_position;
    grid = init_grid();
    position = Position.new(0,0)
    assert_equal '(x0,y0)', grid[position].data
    position.move!(:north)
    assert_equal(position, Position.new(0,-1))
    position2 = position.move(:east)
    refute_equal(position, position2)
    assert_equal(true, position != position2)
    assert_equal(position2, Position.new(1,-1))
  end

  def test_square_area;
    grid = init_grid();
    positions = Position.new(2,1).square_area(1)
    assert_equal(9, positions.count)
    assert_equal([
      [1,0],[2,0],[3,0],
      [1,1],[2,1],[3,1],
      [1,2],[2,2],[3,2]
    ].sort, positions.map(&:to_a).sort)
  end

  def test_circle_area;
    grid = init_grid();
    positions = Position.new(2,1).circle_area(1)
    assert_equal(5, positions.count)
    assert_equal([
      [2,0],
      [1,1],[2,1],[3,1],
      [2,2]
    ].sort, positions.map(&:to_a).sort)
  end

  def test_shortest_path_finder
    data ||= [
      ['.', '.', '.', '.', '.', '.', 'X', '.'],
      ['.', 'X', '.', 'X', 'X', '.', 'X', '.'],
      ['.', 'X', 'X', 'X', '.', '.', 'X', '.'],
      ['.', 'X', '.', '.', '.', '.', 'X', '.'],
      ['.', 'X', 'X', 'X', 'X', '.', 'X', '.'],
      ['.', '.', '.', '.', '.', '.', 'X', '.'],
    ]
    grid = init_grid(data, GameCell);

    assert_equal({ to: Position.new(1,0), dir: :west, dist: 7 },
      PathFinder.new(grid).shortest(
        Position.new(2,0), Position.new(0,5))
      )

    assert_equal({ to: Position.new(2,0), dir: :north, dist: 10 },
      PathFinder.new(grid).shortest(
        Position.new(2,1), Position.new(2,3))
      )

    assert_equal({ to: Position.new(3,0), dir: :east, dist: 9 },
      PathFinder.new(grid).shortest(
        Position.new(2,0), Position.new(2,3))
      )

    assert_nil(PathFinder.new(grid).shortest(
      Position.new(2,0), Position.new(10,10)))

    assert_nil(PathFinder.new(grid).shortest(
      Position.new(1,1), Position.new(0,0)))

    assert_nil(PathFinder.new(grid).shortest(
      Position.new(2,0),
      Position.new(1,1)))

    assert_nil(PathFinder.new(grid).shortest(
      Position.new(0,0),
      Position.new(7,0)))
  end

  def test_longest_path_finder
    data ||= [
      ['.', 'X', '.', '.', '.', '.', 'X', '.'],
      ['.', 'X', '.', 'X', 'X', '.', 'X', '.'],
      ['.', 'X', 'X', 'X', '.', '.', 'X', '.'],
      ['.', 'X', 'X', '.', '.', '.', 'X', '.'],
      ['.', 'X', 'X', 'X', 'X', '.', 'X', '.'],
      ['.', 'X', '.', '.', '.', '.', 'X', '.'],
    ]
    grid = init_grid(data, GameCell);

    assert_equal({ to: Position.new(0,2), dir: :south, dist: 4 },
      PathFinder.new(grid).longest(
        Position.new(0,1))
      )

    grid[Position.new(1,0)].data = '.'

    assert_equal({ to: Position.new(0,0), dir: :north, dist: 14 },
      PathFinder.new(grid).longest(
        Position.new(0,1))
      )

    grid[Position.new(1,0)].data = 'X'
    grid[Position.new(0,0)].set_neighbor(Position.new(7,0), 2, :west)

    assert_equal({ to: Position.new(0,0), dir: :north, dist: 8 },
      PathFinder.new(grid).longest(
        Position.new(0,1))
      )
  end
end

old_spf_for_graph.rb

require 'pry-byebug'

class Node
  Neighbour = Struct.new(:to, :cost)

  def initialize(id)
    @id, @neighbours = id, neighbours;
  end

  def add_neighbour(to, cost);
    @neighbours[to] = cost << Neighbour.new(to, cost)
  end

  def distance(id); @neighbours
end


class Graph
  Node = Struct.new(:id, :neighbours, :distance, :previous)

  def initialize(graph)
    @nodes = Hash.new{|h,k| h[k]=Node.new(k,[],Float::INFINITY)}
    @edges = {}
    graph.each do |(from, to, cost)|
      @nodes[from].neighbours << to
      @nodes[to].neighbours << from
      @edges[[from, to]] = @edges[[to, from]] = cost
    end
    @dijkstra_source = nil
  end

  def dijkstra(source)
    binding.pry
    return if @dijkstra_source == source
    q = @nodes.values
    q.each do |v|
      v.distance = Float::INFINITY
      v.previous = nil
    end
    @nodes[source].distance = 0
    until q.empty?
      u = q.min_by {|node| node.distance}
      break if u.distance == Float::INFINITY
      q.delete(u)
      u.neighbours.each do |neighbour_id|
        neighbour = @nodes[neighbour_id]
        if q.include?(neighbour)
          alt = u.distance + @edges[[u.id, neighbour_id]]
          if alt < neighbour.distance
            neighbour.distance = alt
            neighbour.previous = u.id
          end
        end
      end
    end
    @dijkstra_source = source
  end

  def shortest_path(source, target)
    dijkstra(source)
    path = []
    u = target
    while u
      path.unshift(u)
      u = @nodes[u].previous
    end
    return path, @nodes[target].distance
  end

  def to_s
    "#<%s nodes=%p edges=%p>" % [self.class.name, @nodes.values, @edges]
  end
end

g = Graph.new([ [:a, :b, 7],
                [:a, :c, 9],
                [:a, :f, 14],
                [:b, :c, 10],
                [:b, :d, 15],
                [:c, :d, 11],
                [:c, :f, 2],
                [:d, :e, 6],
                [:e, :f, 9],
              ])

start, stop = :a, :e
path, distance = g.shortest_path(start, stop)
puts "shortest path from #{start} to #{stop} has cost #{distance}:"
puts path.join(" -> ")