-
-
Save eregon/d59af62165414688a248 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This is a player I made for fun, normally compatible ruby 1.8.7 and 1.9 | |
I hope you'll let me battle against others, while I'm posting my solution late | |
(anyway I can't win this time because I did last time ;) ) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class String | |
unless "".respond_to? :ord | |
def ord | |
self.unpack('c')[0] | |
end | |
end | |
end | |
class Coord < Struct.new(:x, :y) | |
SIDE = 10 | |
N = Coord.new(0,-1) | |
E = Coord.new( 1,0) | |
S = Coord.new(0, 1) | |
W = Coord.new(-1,0) | |
DIRS = { :h => [W, E], :v => [N, S] } | |
DIRECTIONS = [N, E, S, W] | |
def initialize(*args) | |
case args.length | |
when 1 | |
args[0] =~ /\A([A-Z]+)([0-9]+)\z/ | |
x, y = $~.captures | |
super(x.ord - 'A'.ord, y.to_i - 1) | |
when 2 | |
super(*args) | |
end | |
end | |
def to_s | |
"#{(x+'A'.ord).chr}#{y+1}" | |
end | |
alias :inspect :to_s | |
[:+, :-].each { |m| | |
define_method(m) { |c| | |
Coord.new(x.send(m,c.x), y.send(m,c.y)) | |
} | |
} | |
def * n | |
Coord.new(x*n, y*n) | |
end | |
def neighbours | |
DIRECTIONS.map { |dir| self + dir } | |
end | |
def distance(c) | |
Math.sqrt( (x-c.x)**2 + (y-c.y)**2 ) | |
end | |
def in?(o) | |
case o | |
when Array | |
o.include?(self) | |
when Hash | |
o.keys.include?(self) | |
else | |
raise | |
end | |
end | |
def valid?(ary = []) | |
if ary.empty? | |
(0...SIDE) === x and (0...SIDE) === y | |
else | |
(0...SIDE) === x and (0...SIDE) === y and not in?(ary) | |
end | |
end | |
# 1: 8 | |
# 2: 8*2 | |
# 3: 8*3 | |
FREESPACE_LEVELS = Array.new(SIDE) { |i| | |
l = i+1 | |
c = (N+W)*l # NW | |
[E, S, W, N].inject([]) { |lvl, dir| | |
(l*2).times { | |
lvl << c | |
c += dir | |
} | |
lvl | |
} | |
} | |
def freespace_around(shots) | |
FREESPACE_LEVELS.inject(0.0) { |i, lvl| | |
continue = true | |
lvl.each { |add| | |
c = self+add | |
next unless c.valid? | |
if !c.in?(shots) | |
i += 1.0 / self.distance(c) * (FREESPACE_LEVELS.index(lvl)+1) | |
else | |
continue = false | |
end | |
} | |
return i unless continue | |
i | |
} | |
end | |
end | |
if __FILE__ == $0 | |
require "test/unit" | |
class TestCoord < Test::Unit::TestCase | |
def setup | |
@a = Coord.new(0,0) | |
@c = Coord.new(2,3) | |
end | |
def c(actual, expected) | |
assert_equal expected, actual | |
end | |
def test_new | |
c Coord.new("A1").to_a, [0,0] | |
c Coord.new("J10").to_a, [9,9] | |
c [@c.x, @c.y], [2,3] | |
end | |
def test_to_s | |
c @c.to_s, "C4" | |
c Coord.new("D5").to_s, "D5" | |
end | |
def test_in? | |
assert @c.in? [@a,@c] | |
assert !@c.in?([@a]) | |
assert @c.in?({@c=>false, @a => nil}) | |
assert !@c.in?({@a => true}) | |
end | |
def test_valid? | |
assert @c.valid? | |
assert @c.valid? [] | |
assert !@c.valid?([@c]) | |
assert !Coord.new(10,9).valid? | |
end | |
def test_neighbours | |
c @c.neighbours, [Coord.new(2,2), Coord.new(3,3), Coord.new(2,4), Coord.new(1,3)] | |
end | |
def test_freespace_around | |
shooted = %w{B1 D1 B3 C2}.map { |s| Coord.new(s) } | |
s = 1/Math.sqrt(2) | |
assert_equal 2+2*s, Coord.new("E1").freespace_around(shooted) # 4 | |
assert_equal 1+4*s, Coord.new("B2").freespace_around(shooted) # 5 | |
assert_equal 11.406135888745856, Coord.new("F1").freespace_around(shooted) # 13 | |
assert_equal 69.79675884855767, Coord.new("J10").freespace_around(shooted) # 78 | |
assert_equal 4+3*s, Coord.new("D3").freespace_around(shooted) # 7 | |
end | |
end | |
end | |
=begin | |
+----+---+---+---+---+---+---+---+---+---+---+ | |
| | A | B | C | D | E | F | G | H | I | J | | |
+----+---+---+---+---+---+---+---+---+---+---+ | |
| 1 | | X | | X | | | | | | | | |
+----+---+---+---+---+---+---+---+---+---+---+ | |
| 2 | | | X | | | | | | | | | |
+----+---+---+---+---+---+---+---+---+---+---+ | |
| 3 | | X | | | | | | | | | | |
+----+---+---+---+---+---+---+---+---+---+---+ | |
| 4 | | | | | | | | | | | | |
+----+---+---+---+---+---+---+---+---+---+---+ | |
| 5 | | | | | | | | | | | | |
+----+---+---+---+---+---+---+---+---+---+---+ | |
| 6 | | | | | | | | | | | | |
+----+---+---+---+---+---+---+---+---+---+---+ | |
| 7 | | | | | | | | | | | | |
+----+---+---+---+---+---+---+---+---+---+---+ | |
| 8 | | | | | | | | | | | | |
+----+---+---+---+---+---+---+---+---+---+---+ | |
| 9 | | | | | | | | | | | | |
+----+---+---+---+---+---+---+---+---+---+---+ | |
| 10 | | | | | | | | | | | | |
+----+---+---+---+---+---+---+---+---+---+---+ | |
=end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
require File.expand_path('../coord', __FILE__) | |
class Array | |
def other(than) | |
find { |o| o != than } | |
end | |
def select_max_by | |
best = map { |e| yield(e) }.max | |
select { |e| yield(e) == best } | |
end | |
# 1.8 problems for Hash | |
def keys | |
map(&:first) | |
end | |
unless [].respond_to? :each_with_object | |
def each_with_object(obj) | |
self.each { |e| | |
yield(e, obj) | |
} | |
obj | |
end | |
end | |
unless [].respond_to? :sample | |
def sample | |
self[rand(size)] | |
end | |
end | |
end | |
class Player | |
attr_reader :name, :shots, :fired | |
NAME = /\w+/ | |
SIDE = 10 | |
ALL_COORDS = (SIDE**2).times.map { |i| Coord.new(i % SIDE, i / SIDE) } | |
def initialize(name, ships = [5, 4, 3, 3, 2]) | |
@name = name | |
@ships = ships | |
@ships_cells = [] | |
@shots = [] | |
@fired = {} | |
@sinking = [] | |
end | |
def fire(coord, hit) | |
@fired[Coord.new(coord)] = (hit.to_sym == :hit) | |
end | |
# Only for ourselves | |
def place_ships | |
ships = "SHIPS" | |
@ships.each { |size| | |
begin | |
current_ship_cells = [] | |
if rand < 0.5 # Horizontal | |
d = :H | |
x = rand(SIDE-size) | |
y = rand(SIDE) | |
else # Vertical | |
d = :V | |
x = rand(SIDE) | |
y = rand(SIDE-size) | |
end | |
size.times { |i| current_ship_cells << Coord.new( x + (d == :H ? i : 0), y + (d == :V ? i : 0) ) } | |
end until (@ships_cells & current_ship_cells).empty? | |
@ships_cells += current_ship_cells | |
ships << " #{size}:#{Coord.new(x, y)}:#{d}" | |
} | |
ships | |
end | |
def shot!(n) | |
targets = [] | |
@sinking = @fired.select { |c,r| r }.keys | |
# 1 Sinking | |
while hit = @sinking.pop | |
targets += sink_that_ship!(hit) | |
targets.uniq! | |
if targets.length >= n | |
targets = targets[0...n] | |
break | |
end | |
end | |
# 2 Secure perimeter | |
if targets.length < n | |
targets += shots_around_hits((n-targets.length)/2) | |
end | |
@shots += targets | |
# 3 Try new locations | |
while targets.length < n | |
targets << shot | |
end | |
raise "We've got a problem: #{@fired.keys & shots}" if !(@fired.keys & targets).empty? | |
"SHOTS #{targets.map(&:to_s).join(' ')}" | |
end | |
def shots_around_hits(n) | |
@fired.select { |c, v| | |
v | |
}.keys.map { |c| | |
Coord::DIRECTIONS.map { |d| c+d } | |
}.flatten.uniq.select { |c| | |
c.valid?(@fired) | |
}.shuffle[0...n] | |
end | |
def find_same_dir(start, dir) | |
Coord::DIRS[dir].each_with_object([start]) { |add, coords| | |
c = start | |
while c += add and c.valid? and @fired[c] | |
coords << c | |
end | |
} | |
end | |
def sink_that_ship!(start) | |
# Find shooted H and V | |
dirs = { | |
:h => find_same_dir(start, :h), | |
:v => find_same_dir(start, :v) | |
} | |
dirs.each_value { |dir| @sinking -= dir } | |
if dirs[:h].length == dirs[:v].length | |
# We got only one coord, or there are as much tries in H & V. So we choose random dir | |
dir = rand < 0.5 ? :h : :v | |
shooted = dirs[dir] | |
else | |
# We know which direction is more interesting | |
dir, shooted = dirs.max_by { |_,d| d.length } | |
end | |
coords = Coord::DIRS[dir].map { |add| | |
shooted.map { |s| s+add }.find { |c| | |
c.valid?(@fired) | |
} | |
}.compact.select { |c| c.valid?(@fired) } | |
n_shoots = ((@ships.inject(:+) - @fired.count { |_,r| r }) / @ships.size + 0.5).to_i | |
if coords.size == 1 # we know which way to go, let's shoot a max ! | |
way_to_go = coords.other(start)-start | |
else # we go both side | |
way_to_go = Coord::DIRS[dir].sample | |
end | |
n_shoots.times { |i| | |
c = start + way_to_go*(i+1) | |
if c.valid?(@fired) | |
coords << c | |
else | |
break | |
end | |
} | |
coords | |
end | |
def shot | |
free = ALL_COORDS - @shots | |
# free = free.shuffle[0..(free.size/2)] # To make it quicker ... but less accurate | |
free.select_max_by { |c| c.freespace_around(@shots) }.sample.tap { |s| @shots << s } | |
end | |
def random_shot | |
begin | |
shot = Coord.new(rand(SIDE), rand(SIDE)) | |
end while shot.in?(ALL_COORDS - @shots) | |
shot | |
end | |
end | |
if __FILE__ == $0 | |
require "test/unit" | |
class TestPlayer < Test::Unit::TestCase | |
def setup | |
@p = Player.new('test_player') | |
@p.fire('B1', :miss) | |
@p.fire('B3', :hit) | |
@p.fire('C3', :hit) | |
end | |
def test_sink | |
assert_equal [Coord.new('B3'), Coord.new('C3')], @p.find_same_dir(Coord.new('B3'), :h) | |
assert_equal [Coord.new('B3')], @p.find_same_dir(Coord.new('B3'), :v) | |
end | |
def test_shot | |
assert_equal "SHOTS A3 D3", @p.shot!(2) | |
p = Player.new('test_player') | |
p.fire('F6', :hit) | |
r = p.shot!(2) | |
assert ["SHOTS F5 F7", "SHOTS E6 G6"].include?(r), r | |
p = Player.new('test_player2') | |
p.fire('H2', :hit) | |
p.fire('G2', :hit) | |
p.fire('I2', :miss) | |
expected = "SHOTS F2 E2" | |
assert_equal expected, p.shot!(5)[0...expected.length] | |
end | |
end | |
end | |
=begin | |
+----+---+---+---+---+---+---+---+---+---+---+ | |
| | A | B | C | D | E | F | G | H | I | J | | |
+----+---+---+---+---+---+---+---+---+---+---+ | |
| 1 | | 0 | | | | | | | | | | |
+----+---+---+---+---+---+---+---+---+---+---+ | |
| 2 | | | | |< >|< >|<1>|<1>|<0>| | | |
+----+---+---+---+---+---+---+---+---+---+---+ | |
| 3 |< >|<1>|<1>|< >| | | | | | | | |
+----+---+---+---+---+---+---+---+---+---+---+ | |
| 4 | | | | | | | | | | | | |
+----+---+---+---+---+---+---+---+---+---+---+ | |
| 5 | | | | | | ? | | | | | | |
+----+---+---+---+---+---+---+---+---+---+---+ | |
| 6 | | | | |<?>|<1>|<?>| | | | | |
+----+---+---+---+---+---+---+---+---+---+---+ | |
| 7 | | | | | | ? | | | | | | |
+----+---+---+---+---+---+---+---+---+---+---+ | |
| 8 | | | | | | | | | | | | |
+----+---+---+---+---+---+---+---+---+---+---+ | |
| 9 | | | | | | | | | | | | |
+----+---+---+---+---+---+---+---+---+---+---+ | |
| 10 | | | | | | | | | | | | |
+----+---+---+---+---+---+---+---+---+---+---+ | |
=end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
$stdout.sync = true | |
@name = File.basename(__FILE__, '.rb') | |
require File.expand_path('../../lib/eregon/player', __FILE__) | |
ARGF.each_line do |line| | |
case line | |
when /\AACTION SHIPS\b/ | |
# We have been asked to place our ships, so we send a valid response: | |
##puts "SHIPS 5:A1:H 4:A2:H 3:A3:H 3:A4:H 2:A5:H" | |
puts @self.place_ships | |
when /\AACTION SHOTS (\d)/ | |
shots = @self.shot!($1.to_i) | |
puts shots | |
when /\AACTION FINISH\b/ | |
# We don't save data, so we just need to tell the server we are done: | |
puts "FINISH" | |
when /\AINFO SETUP players:(#{Player::NAME}),(#{Player::NAME}) board:(?:\d+)x(?:\d+) ships:((?:[0-9]+,?)+)/ | |
n1,n2=$1,$2 | |
@ships = $3.split(',') | |
p1 = Player.new(n1) | |
p2 = Player.new(n2) | |
@self, @opp = [p1,p2].partition { |p| p.name == @name }.map(&:first) | |
when /\AINFO SHOTS (#{Player::NAME})((?: ?\w+\d+:(?:hit|miss))+)/ | |
player, shots = $1, $2.split(' ').map { |shot| shot.split(':') } | |
shots.each do |shot| | |
[@self, @opp].find { |p| p.name == player }.fire(*shot) | |
end | |
when /\AINFO WINNER (#{Player::NAME})/ | |
end | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment