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).

Screenshot of a 3-player game of the Great Escape

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.

• Mangara: Thanks for the tips! I added the shebang and example input. I can't print anything else to the console, because the contest system will reject it. I hadn't seen the style guide, that's a great resource! Could you expand a little on numbers #3 and #5?
• Theo Chirica: I have updated my answer to give you examples. After I'll have time to look more closely at the code and make it run I'll get back to you.

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.