283 lines
7.6 KiB
Crystal
283 lines
7.6 KiB
Crystal
require "./common.cr"
|
|
|
|
lines = STDIN.gets_to_end.split("\n")
|
|
lines.pop
|
|
|
|
units = [] of NamedTuple(type: Symbol, power: Int32, hp: Int32, x: Int32, y: Int32)
|
|
lines.each_with_index do |line, y|
|
|
line.each_char_with_index do |char, x|
|
|
units << { type: :elf, power: 3, hp: 200, x: x, y: y } if char == 'E'
|
|
units << { type: :goblin, power: 3, hp: 200, x: x, y: y } if char == 'G'
|
|
end
|
|
end
|
|
map = lines.map &.chars
|
|
|
|
alias Spot = NamedTuple(x: Int32, y: Int32)
|
|
|
|
def nearby_spots(map, x, y)
|
|
spots = [] of Spot
|
|
spots << { x: x, y: y - 1} if y > 0
|
|
spots << { x: x - 1, y: y } if x > 0
|
|
spots << { x: x + 1, y: y } if x < map[0].size - 1
|
|
spots << { x: x, y: y + 1} if y < map.size - 1
|
|
return spots
|
|
end
|
|
|
|
def all_open_spots(map, units, type)
|
|
open_spots = [] of Spot
|
|
units.select &.[:type].==(type)
|
|
units.each do |unit|
|
|
next unless unit[:type] == type
|
|
x = unit[:x]
|
|
y = unit[:y]
|
|
|
|
open_spots.concat nearby_spots(map, x, y)
|
|
end
|
|
open_spots.select! do |spot|
|
|
map[spot[:y]][spot[:x]] != '#'
|
|
end
|
|
sort_reading_order(open_spots)
|
|
return open_spots
|
|
end
|
|
|
|
def sort_reading_order(collection)
|
|
collection.sort_by! do |item|
|
|
item[:y] * 100 + item[:x]
|
|
end
|
|
end
|
|
|
|
def in_range(map, units, spot, type)
|
|
nearby_spots(map, spot[:x], spot[:y]).select do |spot|
|
|
units.any? { |u| u[:x] == spot[:x] && u[:y] == spot[:y] && u[:type] == type }
|
|
end
|
|
end
|
|
|
|
def occupied(map, units, x, y)
|
|
return (map[y][x] == '#') || units.any? { |u| (u[:x] == x) && (u[:y] == y) }
|
|
end
|
|
|
|
def filter_reachable(map, units, start_spot, open_spots)
|
|
open_spots.select do |spot|
|
|
shortest_path(map, units, start_spot, spot)
|
|
end
|
|
end
|
|
|
|
def opposite_type(type)
|
|
return :goblin if type == :elf
|
|
return :elf
|
|
end
|
|
|
|
def dist(one, other)
|
|
(one[:x] - other[:x]).abs + (one[:y] - other[:y]).abs
|
|
end
|
|
|
|
def path(came_from : Hash(T|R, T|R), start : R) forall T, R
|
|
path = [ start ] of (T|R)
|
|
while came_from.has_key? start
|
|
start = came_from[start]
|
|
path << start
|
|
end
|
|
return path.reverse!
|
|
end
|
|
|
|
def astart_path(map, units, from, to)
|
|
done = Set(Spot).new
|
|
open = Set(Spot).new
|
|
start = {x: from[:x], y: from[:y] }
|
|
open << start
|
|
fscore = {} of Spot => Int32
|
|
gscore = { start => 0 }
|
|
came_from = {} of Spot => Spot
|
|
while !open.empty?
|
|
min = open.min_by { |spot| fscore[spot]? || 100000000 }
|
|
return path(came_from, min) if min == to
|
|
|
|
open.delete min
|
|
done << min
|
|
|
|
min_gscore = gscore[min]? || (100000000)
|
|
nearby_spots(map, min[:x], min[:y]).select { |spot| !occupied(map, units, spot[:x], spot[:y]) }.each do |neighbor|
|
|
next if done.includes? neighbor
|
|
neighbor_gscore = gscore[neighbor]? || (100000000)
|
|
new_score = min_gscore + 1
|
|
open << neighbor if !open.includes? neighbor
|
|
next if new_score >= neighbor_gscore
|
|
|
|
|
|
came_from[neighbor] = min
|
|
gscore[neighbor] = new_score
|
|
fscore[neighbor] = new_score + (neighbor[:y] - min[:y]) * 2 + (neighbor[:x] - min[:x]) # + (dist(neighbor, to)) # + ((neighbor[:y] - min[:y]) * 10))
|
|
end
|
|
end
|
|
end
|
|
|
|
def shortest_path(map, units, from, to)
|
|
visited = Set(Spot).new
|
|
open = Deque(Spot).new(1, { x: from[:x], y: from[:y] } )
|
|
from_hash = {} of Spot => Spot
|
|
return [{ x: from[:x], y: from[:y] }] if from[:x] == to[:x] && from[:y] == to[:y]
|
|
|
|
while !visited.includes?(to) && !open.empty?
|
|
current = open.first
|
|
open.delete current
|
|
visited << current
|
|
x, y = current[:x], current[:y]
|
|
|
|
nearby_spots(map, x, y).each do |it|
|
|
next if visited.includes? it
|
|
visited << it
|
|
next if occupied(map, units, it[:x], it[:y])
|
|
from_hash[it] = current
|
|
open << it
|
|
end
|
|
end
|
|
return path(from_hash, to) if visited.includes? to
|
|
return nil
|
|
end
|
|
|
|
def moved_unit(map, units, unit)
|
|
all_spots = all_open_spots(map, units, opposite_type(unit[:type]))
|
|
# puts "all spots: #{all_spots}"
|
|
all_spots.select! do |spot|
|
|
next true if spot[:x] == unit[:x] && spot[:y] == unit[:y]
|
|
next !occupied(map, units, spot[:x], spot[:y])
|
|
end
|
|
# puts "spots not occupied: #{all_spots}"
|
|
all_paths = all_spots.compact_map do |spot|
|
|
shortest_path(map, units, unit, spot)
|
|
end
|
|
# puts "all paths: #{all_paths}"
|
|
path = all_paths.min_by? &.size
|
|
# puts "picked path: #{path}"
|
|
new_spot = path.try &.[1]?
|
|
return unit unless new_spot
|
|
return { x: new_spot[:x], y: new_spot[:y], power: unit[:power], hp: unit[:hp], type: unit[:type] }
|
|
end
|
|
|
|
def unit_at?(units, x, y)
|
|
units.select { |u| u[:x] == x && u[:y] == y }.first?
|
|
end
|
|
|
|
def unit_at(units, x, y)
|
|
units.select { |u| u[:x] == x && u[:y] == y }.first
|
|
end
|
|
|
|
def attacked_unit(map, units, unit)
|
|
all_spots = nearby_spots(map, unit[:x], unit[:y])
|
|
enemy_spots = all_spots.select! do |spot|
|
|
next false unless enemy = unit_at?(units, spot[:x], spot[:y])
|
|
enemy[:type] == opposite_type(unit[:type])
|
|
end
|
|
return nil if enemy_spots.empty?
|
|
min_hp = enemy_spots.min_of do |spot|
|
|
unit_at(units, spot[:x], spot[:y])[:hp]
|
|
end
|
|
enemy_spots.select! do |spot|
|
|
unit_at(units, spot[:x], spot[:y])[:hp] == min_hp
|
|
end
|
|
return nil if enemy_spots.empty?
|
|
|
|
sort_reading_order(enemy_spots)
|
|
attacked_spot = enemy_spots[0]
|
|
attacked_index = units.index do |unit|
|
|
unit[:x] == attacked_spot[:x] && unit[:y] == attacked_spot[:y]
|
|
end
|
|
return nil unless attacked_index
|
|
attacked_unit = units[attacked_index]
|
|
return { attacked_index, { x: attacked_unit[:x],
|
|
y: attacked_unit[:y],
|
|
power: attacked_unit[:power],
|
|
hp: attacked_unit[:hp] - unit[:power],
|
|
type: attacked_unit[:type] } }
|
|
end
|
|
|
|
def draw(map, units)
|
|
min_x = 0
|
|
max_x = map[0].size - 1
|
|
min_y = 0
|
|
max_y = map.size - 1
|
|
|
|
(min_y..max_y).each do |y|
|
|
(min_x..max_x).each do |x|
|
|
unit = unit_at?(units, x, y)
|
|
if unit
|
|
STDOUT << ((unit[:type] == :elf) ? 'E' : 'G')
|
|
else
|
|
STDOUT << (map[y][x] == '#' ? '#' : '.')
|
|
end
|
|
end
|
|
puts
|
|
end
|
|
end
|
|
|
|
def step(map, units)
|
|
sort_reading_order(units)
|
|
index = 0
|
|
elf_death_count = 0
|
|
while index < units.size
|
|
return nil if (units.count &.[:type].==(:elf)) == 0
|
|
return nil if (units.count &.[:type].==(:goblin)) == 0
|
|
|
|
unit = units[index]
|
|
unit = moved_unit(map, units, unit)
|
|
units[index] = unit
|
|
attacked_u = attacked_unit(map, units, unit)
|
|
if attacked_u
|
|
attacked_index, attacked_unit = attacked_u
|
|
if attacked_unit[:hp] <= 0
|
|
elf_death_count += 1 if attacked_unit[:type] == :elf
|
|
units.delete_at attacked_index
|
|
index -= 1 if index >= attacked_index
|
|
else
|
|
units[attacked_index] = attacked_unit
|
|
end
|
|
end
|
|
index += 1
|
|
end
|
|
|
|
return elf_death_count
|
|
end
|
|
|
|
def check_win(units)
|
|
current_winning = nil
|
|
units.each do |u|
|
|
if current_winning
|
|
return nil if current_winning != u[:type]
|
|
else
|
|
current_winning = u[:type]
|
|
end
|
|
end
|
|
return current_winning
|
|
end
|
|
|
|
def winning_score(units, type)
|
|
units.select(&.[:type].==(type)).sum &.[:hp]
|
|
end
|
|
|
|
power = 3
|
|
loop do
|
|
simulating_units = units.dup.map do |unit|
|
|
next unit unless unit[:type] == :elf
|
|
{ x: unit[:x], y: unit[:y], hp: unit[:hp], type: :elf, power: power }
|
|
end
|
|
steps = 0
|
|
died = false
|
|
# draw(map, simulating_units)
|
|
until won = check_win(simulating_units) || died
|
|
result = step(map, simulating_units)
|
|
if result
|
|
steps += 1
|
|
died = result > 0
|
|
end
|
|
# draw(map, simulating_units)
|
|
sort_reading_order(simulating_units)
|
|
# simulating_units.each do |unit|
|
|
# puts "health (#{unit[:type]}): #{unit[:hp]}"
|
|
# end
|
|
# puts "-- (end of roun #{steps})"
|
|
end
|
|
puts "(power: #{power}) #{steps} * #{winning_score(simulating_units, won)} = #{steps * winning_score(simulating_units, won)}"
|
|
break if !died && won != :goblin
|
|
power += 1
|
|
end
|