Skip to content

Instantly share code, notes, and snippets.

@emasaka
Created August 23, 2010 09:44
Show Gist options
  • Save emasaka/545149 to your computer and use it in GitHub Desktop.
Save emasaka/545149 to your computer and use it in GitHub Desktop.
#!/usr/bin/env ruby
# works on Ruby 1.9.2 (maybe on Ruby 1.9.1, too)
class Loc
def initialize(x, y)
@x = x
@y = y
end
attr_reader :x, :y
def ==(p)
@x == p.x && @y == p.y
end
alias_method :eql?, :==
def hash
@x * 1000 + @y
end
def -(p)
self.class.new(@x - p.x, @y - p.y)
end
MOVEMENTS = {
down: Loc.new(0, 1),
left: Loc.new(-1, 0),
up: Loc.new(0, -1),
right: Loc.new(1, 0),
}
def move(dir)
m = MOVEMENTS[dir]
self.class.new(@x + m.x, @y + m.y)
end
end
class Mover
def initialize(loc, prev = nil)
@loc = loc
@prev = prev
end
attr_reader :loc, :prev
def move_to?(x, y)
MAP[y][x]
end
def move?(dir)
d = Loc::MOVEMENTS[dir]
move_to?(@loc.x + d.x, @loc.y + d.y)
end
private
def all_moves
cx = @loc.x; cy = @loc.y
[[cx - 1, cy], [cx, cy - 1],
[cx + 1, cy], [cx, cy + 1] ].find_all do |x, y|
move_to?(x, y)
end
end
end
class Jiki < Mover
def initialize(loc, prev = nil)
@hist = []
super(loc, prev)
end
def move_to_loc(loc)
self.class.new(loc, self)
end
end
class Enemy < Mover
def move_next(jiki)
self.class.new(next_loc(jiki), self)
end
def next_loc(jiki)
if @prev
m = all_moves
if m.size == 1 # deadend
Loc.new(m[0][0], m[0][1])
elsif m.size == 2 # way
n = m.find {|e| !(e[0] == @prev.loc.x && e[1] == @prev.loc.y) }
Loc.new(n[0], n[1])
else # cross
next_loc_cross(jiki)
end
else # 1st step
next_loc_cross_base(jiki)
end
end
def next_loc_cross_base(jiki)
@loc.move([:down, :left, :up, :right].find {|dir| move?(dir) })
end
def to_char
self.class.to_s[-1]
end
private
def turn_l2r
d = @loc - @prev.loc
x = d.x <=> 0; y = d.y <=> 0
[[y, - x], [x, y], [- y, x]] # left, ahead, right
end
def turn_r2l
d = @loc - @prev.loc
x = d.x <=> 0; y = d.y <=> 0
[[- y, x], [x, y], [y, - x]] # right, ahead, left
end
end
class EnemyV < Enemy
def next_loc_cross(jiki)
d = jiki.loc - @loc
if d.y > 0 && move?(:down)
@loc.move(:down)
elsif d.y < 0 && move?(:up)
@loc.move(:up)
elsif d.x > 0 && move?(:right)
@loc.move(:right)
elsif d.x < 0 && move?(:left)
@loc.move(:left)
else
next_loc_cross_base(jiki)
end
end
end
class EnemyH < Enemy
def next_loc_cross(jiki)
d = jiki.loc - @loc
if d.x > 0 && move?(:right)
@loc.move(:right)
elsif d.x < 0 && move?(:left)
@loc.move(:left)
elsif d.y > 0 && move?(:down)
@loc.move(:down)
elsif d.y < 0 && move?(:up)
@loc.move(:up)
else
next_loc_cross_base(jiki)
end
end
end
class EnemyL < Enemy
def next_loc_cross(jiki)
turn_l2r.each do |dx, dy|
nx = @loc.x + dx; ny = @loc.y + dy
if move_to?(nx, ny)
return Loc.new(nx, ny)
end
end
raise "No Way: (#{@loc.x}, #{@loc.y}, #{turn_l2r}"
end
end
class EnemyR < Enemy
def next_loc_cross(jiki)
turn_r2l.each do |dx, dy|
nx = @loc.x + dx; ny = @loc.y + dy
if move_to?(nx, ny)
return Loc.new(nx, ny)
end
end
raise "No Way: (#{@loc.x}, #{@loc.y}, #{turn_l2r}"
end
end
class EnemyJ < Enemy
def initialze
@flag = true
super
end
def next_loc_cross(jiki)
ary = @flag ? turn_l2r : turn_r2l
@flag = !@flag
ary.each do |dx, dy|
nx = @loc.x + dx; ny = @loc.y + dy
if move_to?(nx, ny)
return Loc.new(nx, ny)
end
end
raise "No Way: (#{@loc.x}, #{@loc.y}, #{turn_l2r}"
end
end
MAP = []
class State
def parse_file(file)
@jiki = nil
@enemies = []
@dots = {}
@points = 0
@hist = []
@next_link = nil
@visited = false
open(file) do |io|
@life = io.gets.chomp.to_i
io.gets # just skip field size
io.each_line.with_index do |s, y|
MAP << s.chomp.split(//).map.with_index {|c, x| char2item(c, x, y)}
end
end
self
end
attr_reader :life, :hist, :points, :prev, :next_link, :visited
def to_s
m = MAP.map.with_index do |row, y|
row.map.with_index do |col, x|
col ? (@dots[Loc.new(x, y)] ? '.' : ' ') : '#'
end
end
@enemies.each {|e| m[e.loc.y][e.loc.x] = e.to_char }
m[@jiki.loc.y][@jiki.loc.x] = '@'
"#{@life.to_s}:#{@points}\n" + m.map {|row| row.join }.join("\n")
end
def next_states
tmpl = dup.step
@visited = true
link = self
cx = @jiki.loc.x; cy = @jiki.loc.y
[[cx, cy, '.'], [cx - 1, cy, 'h'], [cx, cy - 1, 'k'],
[cx + 1, cy, 'l'], [cx, cy + 1, 'j'] ].find_all do |x, y, c|
@jiki.move_to?(x, y) or next
st = tmpl.dup.move_jiki(Loc.new(x, y), c)
unless st.eaten?
link = st.check_dot.set_next_link(link)
end
end
link
end
def eaten?
@enemies.any? do |e|
e.loc == @jiki.loc ||
(e.prev && e.prev.loc == @jiki.loc && e.loc == @jiki.prev.loc)
end
end
def dot_complete?
@dots.empty?
end
KEY2MOVE = {
'j' => Loc.new(0, 1),
'h' => Loc.new(-1, 0),
'k' => Loc.new(0, -1),
'l' => Loc.new(1, 0),
'.' => Loc.new(0, 0),
}
def play(c)
m = KEY2MOVE[c]
loc = @jiki.loc
dup.step.move_jiki(Loc.new(loc.x + m.x, loc.y + m.y), c).check_dot
end
protected
def step
@enemies = @enemies.map {|e| e.move_next(@jiki) }
@life -= 1
self
end
def move_jiki(loc, c)
@jiki = @jiki.move_to_loc(loc)
@hist = @hist.dup << c
self
end
def check_dot
p = @jiki.loc
if @dots[p]
@dots = @dots.dup
@dots.delete(p)
@points += 1
end
self
end
def set_next_link(link)
@next_link = link
self
end
private
CHAR2ENEMY = {
'V' => EnemyV, 'H' => EnemyH, 'L'=> EnemyL, 'R' => EnemyR, 'J' => EnemyJ,
}
def char2item(c, x, y)
case c
when '.'
@dots[Loc.new(x, y)] = true
when '@'
@jiki = Jiki.new(Loc.new(x, y))
when 'V', 'H', 'L', 'R', 'J'
@enemies << CHAR2ENEMY[c].new(Loc.new(x, y))
end
c != '#'
end
end
if __FILE__ == $0
require 'optparse'
opt = OptionParser.new
$auto_play_str = nil
$debug_mode = false
$report_timeover = false
opt.on('-d', 'debug mode') {|v| $debug_mode = v }
opt.on('-t', 'report timeover') {|v| $report_timeover = v }
opt.on('-p STR', 'auto play mode') {|s| $auto_play_str = s }
opt.parse!(ARGV)
filename = ARGV[0]
def puts_message(st, msg = nil)
puts "#{st.points}: #{msg ? msg + ': ' : ''}#{st.hist.join}"
end
st = State.new.parse_file(filename)
if $auto_play_str
puts st
$auto_play_str.split(//).each do |c|
st = st.play(c)
if st.eaten?
puts 'eaten!'
break
end
puts "> #{c}"
puts st
end
else
while st
puts_message(st) if $debug_mode
if st.dot_complete?
puts_message(st, 'got all dots!')
break if st.eaten?
st = st.next_link
elsif st.life == 1 # time over
puts_message(st, 'timeover!') if $report_timeover
st = st.next_link
elsif st.visited
st = st.next_link
else
if link = st.next_states
st = link
else
st = st.next_link
end
end
end
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment