The solutions to advent of code puzzles, year 2018.
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

#### 282 lines 7.6 KiB Raw Permalink Blame History

 ```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 ``` ``` ```