Facebook Jobs Puzzle—battleship

06 Oct 2009

From Facebook's Job Puzzles page:

Well, now that I have no use for a Facebook job, I better start posting the rest of my solutions. This was a fun one... a straightforward puzzle with no requirements for fancy algorithms or data structures... just good old organic strategy.

In battleship, you can hit every boat by laying down a checkerboard firing pattern:

Once you hit something, you can aim for one of the four adjacent squares to finish off the boat.

You can either randomly aim at squares in the pattern or hard-code a certain sequence, which is what I did. There might be an optimal sequence/strategy for statistical reasons, but then again a smart opponent can adapt and counter any specific strategy. That's all extra credit for you folks out there.

The following solution in Ruby passed the Facebook puzzle robot:

#!/usr/bin/env ruby
require 'gen-rb/Battleship'

host = ARGV[0] ? ARGV[0] : "thriftpuzzle.facebook.com"
port = ARGV[1] ? ARGV[1].to_i : 9060

trans = Thrift::Socket.new(host, port)
trans.open

$battle = Battleship::Client.new(Thrift::BinaryProtocol.new(trans))
p $battle.registerClient

p $battle.placePiece(Ship::CARRIER,     Coordinate.new({:row => 2, :column => 3}), true)
p $battle.placePiece(Ship::BATTLESHIP,  Coordinate.new({:row => 1, :column => 2}), false)
p $battle.placePiece(Ship::DESTROYER,   Coordinate.new({:row => 3, :column => 4}), true)
p $battle.placePiece(Ship::SUBMARINE,   Coordinate.new({:row => 7, :column => 2}), false)
p $battle.placePiece(Ship::PATROL,      Coordinate.new({:row => 5, :column => 7}), false)

sequence = []
$done = []
$ptdown = false

sequence = [
  [0,0], [1,1], [2,2], [3,3], [4,4], [5,5], [6,6], [7,7], [8,8], [9,9],
  [2,0], [3,1], [4,2], [5,3], [6,4], [7,5], [8,6], [9,7],
  [4,0], [5,1], [6,2], [7,3], [8,4], [9,5],
  [6,0], [7,1], [8,2], [9,3],
  [8,0], [9,1] ]
  
strat1 = [
  [0,2], [1,3], [2,4], [3,5], [4,6], [5,7], [6,8], [7,9],
  [0,4], [1,5], [2,6], [3,7], [4,8], [5,9],
  [0,6], [1,7], [2,8], [3,9],
  [0,8], [1,9] ]

strat2 = [
  [0,3], [1,4], [2,5], [3,6], [4,7], [5,8], [6,9],
  [0,6], [1,7], [2,8], [3,9],
  [0,9] ]

def attack(pos)
  return nil if $done.include?(pos)
  return nil unless pos[0] >= 0 && pos[0] < 10 && pos[1] >= 0 && pos[1] < 10
  
  while !$battle.isMyTurn()
    1000.times { |i| i += 1 }
  end
  $done << pos
  result = $battle.attack(Coordinate.new({:row => pos[0], :column => pos[1] }))
  $ptdown = true if result == AttackResult::SUNK_PATROL
  return result
end

def neighbors(pos) # North, South, East, West
  [ [pos[0], pos[1] - 1], [pos[0], pos[1] + 1], [pos[0] + 1, pos[1]], [pos[0] - 1, pos[1]] ]
end

def hit(pos, direction=nil)
  puts "#{pos} #{direction}"
  neighs = neighbors(pos)
  if direction
    result = attack(pos)
    return false if result.nil?
    return hit(neighs[direction], direction) if result == AttackResult::HIT
    # return (result < 6) ? true : false
    return false
  else
    neighs.each_with_index { |n, i| return if hit(n, i) }
  end
end

begin
  loop do
    if sequence.empty?
      $ptdown ? sequence = strat2 : sequence = strat1
    end
    next_move = sequence.shift
    next if $done.include?(next_move)

    if attack(next_move) == AttackResult::HIT
      hit(next_move)
    end
  end

rescue Thrift::TransportException
  trans.close
  exit
end