Codingame: Great Escape bot in Ruby

Question

(EDIT: I incorporated a lot of the feedback from the answers, and posted a follow-up question here: Codingame: Great Escape bot in Ruby - Follow-up)

I started working on some code challenges at CodinGame to learn Ruby, and this is my first big Ruby project. It's a bot for their Great Escape contest (here is a sample gameplay video).

Each player starts at one side of the board and must reach the opposite side. Each turn, a player can either move along the grid, or try to block their opponents by placing a wall somewhere. It is illegal to completely cut an opponent off from their goal side.

My bot maintains the distance to the goal and next step along the shortest path for each grid cell for each player and follows that. In addition, it tries to block the opponent who is closest to victory by placing walls across their shortest path.

Communication goes through console gets / puts. Each turn, my bot receives player and wall coordinates and outputs a single command to either move or place a new wall.

As I said, this is my first big Ruby project, so all comments on coding style, code organisation, naming conventions, performance, etc., are welcome. The only constraints are that the contest system requires everything to be in one file and has a limited set of libraries (I'm not actually sure which ones).

#!/usr/bin/env ruby
STDOUT.sync = true # DO NOT REMOVE

require 'set'

class BinaryHeap
    def initialize
        @elements = []
    end

    def size
        @elements.size
    end

    def empty?
        @elements.empty?
    end

    def clear
        @elements.clear
        self
    end

    def push(element)
        @elements << element
        bubble_up(@elements.size - 1)
        self
    end

    alias :<< :push

    def pop
        return nil if empty?

        root = @elements[0]

        @elements[0] = @elements[@elements.size - 1]
        @elements.pop
        trickle_down(0)

        root
    end

    def peek
        return nil if empty?
        @elements[0]
    end

    def inspect
        "<#{self.class}: size=#{size}, peek=#{peek || "nil"}>"
    end

    private

        def bubble_up(i)
            p = parent(i)

            while (i > 0 && comp(i, p) < 0) do
                swap(i, p)
                i, p = p, parent(p)
            end
        end

        def trickle_down(i)
            begin
                j, r, l = -1, right_child(i), left_child(i)

                if (r < @elements.size && comp(r, i) < 0)
                    j = comp(l, r) < 0 ? l : r
                elsif (l < @elements.size && comp(l, i) < 0)
                    j = l;
                end

                swap(i, j) unless j < 0
                i = j
            end while i >= 0
        end

        def left_child(i)
            2 * i + 1
        end

        def right_child(i)
            2 * i + 2
        end

        def parent(i)
            (i - 1) / 2
        end

        def swap(i, j)
            @elements[i], @elements[j] = @elements[j], @elements[i]
        end

        def comp(i, j)
            @elements[i] <=> @elements[j]
        end
end

Player = Struct.new(:id, :row, :col, :walls_left)

Wall = Struct.new(:row, :col, :dir)

Node = Struct.new(:row, :col, :left, :right, :up, :down, :dists, :successors) do
    def to_s
        "(#{row}, #{col})"
    end

    def inspect
        "(#{row}, #{col})"
    end

    def neighbours
        [left, right, up, down].compact
    end

    def successorString(id)
        case successors[id]
        when nil then "nil"
        when left then "LEFT"
        when right then "RIGHT"
        when up then "UP"
        when down then "DOWN"
        end
    end
end

NodeWrapper = Struct.new(:node, :player_id) do
    def <=> (other)
        node.dists[player_id] <=> other.node.dists[player_id]
    end
end

# w: width of the board
# h: height of the board
# player_count: number of players (2 or 3)
# my_id: id of my player (0 = 1st player, 1 = 2nd player, ...)
$w, $h, @player_count, @my_id = gets.split(" ").collect {|x| x.to_i}

#init grid
@grid = Array.new($h){Array.new($w){Node.new()}}

for row in 0..$h-1 do
    for col in 0..$w-1 do
        @grid[row][col].row = row
        @grid[row][col].col = col
        @grid[row][col].left = @grid[row][col - 1] unless col == 0
        @grid[row][col].right = @grid[row][col + 1] unless col == $w - 1
        @grid[row][col].up = @grid[row - 1][col] unless row == 0
        @grid[row][col].down = @grid[row + 1][col] unless row == $h - 1
        @grid[row][col].dists = [$w - col - 1, col, $h - row - 1]
        @grid[row][col].successors = [@grid[row][col].right, @grid[row][col].left, @grid[row][col].down]
    end
end

@walls = []
@players = []

# Breaks the connections in the grid between these cells
# Returns the list of invalidated cells
def breakConnection(row1, col1, row2, col2)
    invalid = [];

    if row1 == row2
        r = row1
        c1 = (col1 < col2 ? col1 : col2)
        c2 = (col1 < col2 ? col2 : col1)

        if @grid[r][c1].right
            @grid[r][c1].right = nil
            @grid[r][c2].left = nil

            for id in 0..@player_count-1 do
                if @grid[r][c1].successors[id] == @grid[r][c2]
                    invalid += invalidateCell(@grid[r][c1], id)
                end
                if @grid[r][c2].successors[id] == @grid[r][c1]
                    invalid += invalidateCell(@grid[r][c2], id)
                end
            end
        end
    else
        c = col1
        r1 = (row1 < row2 ? row1 : row2)
        r2 = (row1 < row2 ? row2 : row1)

        if @grid[r1][c].down
            @grid[r1][c].down = nil
            @grid[r2][c].up = nil

            for id in 0..@player_count-1 do
                if @grid[r1][c].successors[id] == @grid[r2][c]
                    invalid += invalidateCell(@grid[r1][c], id)
                end
                if @grid[r2][c].successors[id] == @grid[r1][c]
                    invalid += invalidateCell(@grid[r2][c], id)
                end
            end
        end
    end

    return invalid
end

# Breaks the connections in the grid crossing this wall
# Returns the list of invalidated cells
def addWall(wall)
    invalid = []

    if wall.dir == "V"
        # Wall starts at the top left corner of (row, col) and continues down for 2 cells
        invalid += breakConnection(wall.row, wall.col - 1, wall.row, wall.col)
        invalid += breakConnection(wall.row + 1, wall.col - 1, wall.row + 1, wall.col)
    else # H
        # Wall starts at the top left corner of (row, col) and continues right for 2 cells
        invalid += breakConnection(wall.row - 1, wall.col, wall.row, wall.col)
        invalid += breakConnection(wall.row - 1, wall.col + 1, wall.row, wall.col + 1)
    end

    return invalid
end

# Invalidates the given node and all nodes whose shortest path go through it
# Returns the list of invalidated cells
def invalidateCell(node, player_id)
    STDERR.puts "Invalidating #{node.to_s} for player #{player_id}"

    node.successors[player_id] = nil

    # Check if we can reroute
    node.neighbours.each do |n| 
        if n.dists[player_id] == node.dists[player_id] - 1
            node.successors[player_id] = n
            STDERR.puts "Rerouting successful"
            return []
        end
    end

    STDERR.puts "No rerouting possible"

    # No rerouting possible. Invalidate this and predecessors.
    node.dists[player_id] = nil

    invalid = [[node, player_id]]

    node.neighbours.each do |n|
        invalid += invalidateCell(n, player_id) if n.successors[player_id] == node
    end

    STDERR.puts "Finished invalidating #{node.to_s} for player #{player_id}"
    STDERR.puts invalid.to_s

    return invalid
end

# Updates the shortest paths of the given cells
def computeNewPaths(invalid)
    playerCells = Array.new(@player_count){[]}

    invalid.each do |node, id|
        playerCells[id] << node
    end

    for id in 0..@player_count-1 do
        computeNewPathsForPlayer(playerCells[id], id)
    end
end

# Updates the shortest paths of the given cells
def computeNewPathsForPlayer(invalid, player_id)
    frontier = BinaryHeap.new()

    # Add all non-invalidated neighbours to our frontier
    invalid.each do |node|
        node.neighbours.each do |neighbour|
            frontier << NodeWrapper.new(neighbour, player_id) if neighbour.dists[player_id]
        end
    end

    # Expand the closest frontier node until they're out
    until frontier.empty? do
        node = frontier.pop.node

        node.neighbours.each do |neighbour|
            if neighbour.dists[player_id].nil? || neighbour.dists[player_id] > node.dists[player_id] + 1
                neighbour.dists[player_id] = node.dists[player_id] + 1
                neighbour.successors[player_id] = node
                frontier << NodeWrapper.new(neighbour, player_id)
            end
        end
    end
end

def block(opponent)
    STDERR.puts "Trying to block #{opponent}"

    # Try to block each move of the upcoming shortest path
    blocked = false
    node = @grid[opponent.row][opponent.col]
    succ = node.successors[opponent.id]

    until (blocked || succ.nil?) do
        blocked = blockConnection(node, succ)

        node = succ
        succ = node.successors[opponent.id]
    end

    return blocked
end

def blockConnection(node, succ)
    STDERR.puts "Trying to block the connection between #{node} and #{succ}"

    if node.row == succ.row
        dir = "V"
        col = [node.col, succ.col].max

        return tryWall(node.row, col, dir) || tryWall(node.row - 1, col, dir)
    else
        dir = "H"
        row = [node.row, succ.row].max

        return tryWall(row, node.col, dir) || tryWall(row, node.col - 1, dir)
    end
end

def tryWall(row, col, dir)
    if isValidWall(row, col, dir)
        puts "#{col} #{row} #{dir}"
        return true
    else
        return false
    end
end

def isValidWall(row, col, dir)
    # Within the grid
    return false if row < 0 || row > $h-1
    return false if col < 0 || col > $w-1
    return false if dir == "V" && row == $h-1
    return false if dir == "H" && col == $w-1

    # Does not intersect existing walls
    @walls.each do |wall|
        if wall.dir == dir
            return false if dir == "V" && col == wall.col && (row - wall.row).abs < 2
            return false if dir == "H" && row == wall.row && (col - wall.col).abs < 2
        else
            return false if dir == "V" && col == wall.col + 1 && row == wall.row - 1
            return false if dir == "H" && col == wall.col - 1 && row == wall.row + 1
        end
    end

    # Does not cut off a player's last path
    (0..@player_count-1).each do |player_id|
        return false unless verifyDestinationStillReachableWithWall(row, col, dir, player_id)
    end

    return true
end

def verifyDestinationStillReachableWithWall(row, col, dir, player_id)
    return explore(@players[player_id].row, @players[player_id].col, player_id, row, col, dir, Set.new())
end

# DFS with preference towards the destination side
def explore(row, col, player_id, wall_row, wall_col, wall_dir, marked)
    node = @grid[row][col]
    return true if node.dists[player_id] == 0

    marked << node

    neighbours =
        case player_id
        when 0
            [node.right, node.up, node.down, node.left]
        when 1
            [node.left, node.up, node.down, node.right]
        when 2
            [node.down, node.left, node.right, node.up]
        end

    neighbours.compact.each do |n|
        unless (wallBlocks(wall_row, wall_col, wall_dir, node, n) || marked.include?(n))
            return true if explore(n.row, n.col, player_id, wall_row, wall_col, wall_dir, marked)
        end
    end

    return false
end

def wallBlocks(wall_row, wall_col, wall_dir, node, neighbour)
    if node.row == neighbour.row
        wall_dir == "V" && wall_col == [node.col, neighbour.col].max && (wall_row == node.row || wall_row == node.row - 1)
    else
        wall_dir == "H" && wall_row == [node.row, neighbour.row].max && (wall_col == node.col || wall_col == node.col - 1)
    end
end

# game loop
loop do
    @players = []
    @player_count.times do |id|
        # x: x-coordinate of the player
        # y: y-coordinate of the player
        # walls_left: number of walls available for the player
        col, row, walls_left = gets.split(" ").collect {|x| x.to_i}
        @players << Player.new(id, row, col, walls_left)
    end

    invalid = []
    @walls = []

    wall_count = gets.to_i # number of walls on the board
    wall_count.times do
        # wall_x: x-coordinate of the wall
        # wall_y: y-coordinate of the wall
        # wall_orientation: wall orientation ('H' or 'V')
        wall_x, wall_y, wall_orientation = gets.split(" ")
        wall = Wall.new(wall_y.to_i, wall_x.to_i, wall_orientation)
        @walls << wall
        invalid += addWall(wall)
    end

    computeNewPaths(invalid) unless invalid.empty?

    me = @players[@my_id]
    myDist = @grid[me.row][me.col].dists[@my_id]

    tookAction = false

    if me.walls_left > 0
        opponents = (0..@player_count-1).to_a - [@my_id]
        opponents.map! { |id| @players[id] }
        opponents.select! { |o| o.row > -1 }
        opponents.shuffle! if opponents.length >= 2
        opponents.sort_by! { |o| @grid[o.row][o.col].dists[o.id] } if opponents.length >= 2
        opponents.each do |o|
            dist = @grid[o.row][o.col].dists[o.id]

            if !tookAction && dist <= 3 && (dist < myDist || (dist == myDist && o.id < @my_id))
                # This opponent will beat me if I don't block them
                tookAction = block(o)
            end
        end
    end

    # Follow the shortest path
    puts @grid[me.row][me.col].successorString(@my_id) unless tookAction
end

EDIT: If you want to run the program, try the following input:

9 9 2 0
0 7 10
8 3 10
0

The first line of the input is given once at the start of the game and sets these variables:

• w: width of the board
• h: height of the board
• player_count: number of players (2 or 3)
• my_id: id of my player (0 = 1st player, 1 = 2nd player, ...)

Every game turn, my program expects the following input:

• One line per player, containing:
  • col: x-coordinate of the player
  • row: y-coordinate of the player
  • walls_left: number of walls available for the player
• A line containing the number of walls present
• One line per wall, containing:
  • wall_col: x-coordinate of the wall
  • wall_row: y-coordinate of the wall
  • wall_orientation: wall orientation ('H' or 'V')

The program gives one line of output, either:

• A direction to move in (LEFT, RIGHT, UP, or DOWN); or
• A new wall placement putX putY putOrientation

Answer 1

A few things to improve the game experience:

1. Add a shebang: #!/usr/bin/env ruby, this will help the users run your code from the console like this: ./great_escape_bot.rb.
2. Add a banner or anything to let the user know that input is required and what he should do next an example here.
3. I don't know your experience with testing, but for a program that's small as this it would be worth to have a small test suite to check that everything will work as expected, you can try minitest. This will not affect your game submission but it will help you refactor your code easily without and with confidence.
   This is a good tutorial to get you started with minitest: link. The main idea being that you have a file that test your implementation to make sure your code is working as expected without having to check it manually (this is an example):

```

def test_it_turns_left
  assert_equal Game.move_to(9), 'Robot moved to 9,0' 
end

4. Use the recommended code style for ruby, one thing that you can do to help it be more ruby-like is to use 2 spaces instead of tabs to align your code.

5. Consider adding everything inside a module and use more classes (while still keeping everything in the same class), that will increase the readability.
   Example:

```

#!/usr/bin/env ruby

module Game
  class BinaryHeap
    # Code
  end

  class Runner
    # Code
  end

  class ErrorChecker
    # Code
  end
end

Game::Runner.run

That's all I can say for now since I can't run the program, maybe write in the beginning of the file if there are any restrictions to the environment, or maybe force the restriction when the file is ran.

Depending on my time I'll decide to debug it later, without unit tests I don't know if my environment or the code is at fault.

Answer 2

Consider the forwardable library

Consider using the built-in forwardable library to build forwarding methods. Instead of this:

class BinaryHeap
  ...
  def size
    @elements.size
  end

  def empty?
    @elements.empty?
  end

You can do this:

require "forwardable"

class BinaryHeap
  extend Forwardable
  ...
  def_delegators :@elements,
    :size,
    :empty?

Use $stderr instead of STDERR

Consider writing to $stderr instead of STDERR. The difference is that STDERR is a constant, whereas $stderr is a global variable that, by default, refers to STDERR. Among other things, code writing to $stderr is easier to test than code writing to STDERR, because the test can temporarily reassign $stderr to a StringIO in order to caputre the output.

Don't use return at the end of a method

When returning a value at the end of a method:

  return false
end

Omit the return:

  false
end

The value of a method is the value of the last expression evaluated by the method.