view day16.rb @ 26:eb6c3a7d2f72

Constrained and more optimised route finding * Track routes so we can see if we have gone straight for too long * Track multiple routes so we can use a non-optimal route to X if it makes another route to Y through X possible (e.g. optimal route takes three consecutive steps to X, but then has to turn, whereas a longer straight earlier and two consecutive steps to X gives a much better next hop to Y) * We have a start point, so only include the nodes from the search front in "unvisited" to avoid looking at lots of irrelevant nodes
author IBBoard <dev@ibboard.co.uk>
date Sun, 17 Dec 2023 20:13:03 +0000
parents ad73a2ff3d06
children
line wrap: on
line source

#! /usr/bin/env ruby

require "set"

if ARGV.length != 1
        abort("Incorrect arguments - needs input file")
elsif not File.exist? (ARGV[0])
	abort("File #{ARGV[0]} did not exist")
end

file = ARGV[0]

Laser = Struct.new(:x, :y, :direction)

mirror_map = {
	"." => {
		right: [:right],
		up: [:up],
		left: [:left],
		down: [:down]
	},
	"/" => {
		right: [:up],
		up: [:right],
		down: [:left],
		left: [:down]
	},
	"\\" => {
		right: [:down],
		down: [:right],
		up: [:left],
		left: [:up]
	},
	"-" => {
		right: [:right],
		left: [:left],
		down: [:left, :right],
		up: [:left, :right]
	},
	"|" => {
		right: [:up, :down],
		left: [:up, :down],
		down: [:down],
		up: [:up]
	}
}

def next_positions(puzzle, mirror_map, laser)
	x_prime, y_prime = case laser.direction
		when :right then [laser.x + 1, laser.y]
		when :down then [laser.x, laser.y + 1]
		when :left then [laser.x - 1, laser.y]
		when :up then [laser.x, laser.y - 1]
	end
	if x_prime < 0 or x_prime >= puzzle[0].length or y_prime < 0 or y_prime >= puzzle.length
		[]
	else
		new_space = puzzle[y_prime][x_prime]
		# puts "#{laser.direction} to #{x_prime}, #{y_prime} (#{new_space})"
		mirror_map[new_space][laser.direction].map {|dir| Laser.new(x_prime, y_prime, dir)}
	end
end

puzzle = File.open(file, "r").each_line(chomp: true).map {|line| line.each_char.to_a}
lasers = next_positions(puzzle, mirror_map, Laser.new(-1, 0, :right))
energised = Array.new(puzzle.length) {Array.new(puzzle[0].length)}
energised [0][0] = 1
previous_lasers = Set.new

while lasers != []
#	puts "#{lasers}"
	lasers = lasers.flat_map do |laser|
		next_positions(puzzle, mirror_map, laser).filter {|new_laser| !previous_lasers.include? new_laser}.each {|new_laser| energised[new_laser.y][new_laser.x] = 1; previous_lasers << new_laser}
	end
end

puts energised.flatten.map(&:to_i).reduce(:+)