Mercurial > repos > other > adventofcode2023
view day8.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 | a7fb64b48830 |
children |
line wrap: on
line source
#! /usr/bin/env ruby 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] lines = File.open(file, "r").each_line(chomp: true) steps = lines.first.each_char.to_a.cycle node_lines = lines.drop(1).to_a #first_node, _ = node_lines[0].split("=") #first_node.strip! nodes = node_lines.map {|line| node, rest = line.split("="); left, right = rest.split(","); [node.strip, {"L" => left.strip[1..-1], "R" => right.strip[0..-2]}]}.to_h cur_node = "AAA" step_count = 0 while cur_node != "ZZZ" step_count += 1 cur_node = nodes[cur_node][steps.next] end puts step_count