Mercurial > repos > other > adventofcode2023
view day16.rb @ 39:0e17e4bd97a9 default tip
Rewrite as four-dimensional route finding
The grid isn't just a 2D grid. The constraints make it 4D:
* X
* Y
* Last direction
* Number of steps in that direction
By tracking all four dimensions, we can find the shortest route
for _all_ combinations of the constraint. Previously, we were dropping
routes that were currently longer but ended up shorter because
they could take subsequent steps that other routes couldn't.
author | IBBoard <dev@ibboard.co.uk> |
---|---|
date | Sun, 22 Sep 2024 11:30:53 +0100 |
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(:+)