Mercurial > repos > other > adventofcode2023

annotate day10.rb @ 24:19481b061461

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Implement tilting and cycling for Day 14 part 2 Lots of false starts trying to iterate. Eventually looked for "back in same position" to spot a loop. Then took longer to spot that "same position" isn't necessarily "start position" and loop can be offset!
author IBBoard <dev@ibboard.co.uk>
date Sat, 16 Dec 2023 20:39:02 +0000
parents 9b1d04091335
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
16
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
1 #! /usr/bin/env ruby
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
2
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
3 if ARGV.length != 1
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
4 abort("Incorrect arguments - needs input file")
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
5 elsif not File.exist? (ARGV[0])
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
6 abort("File #{ARGV[0]} did not exist")
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
7 end
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
8
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
9 file = ARGV[0]
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
10
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
11 charmap = File.open(file, "r").each_line(chomp: true).map {|line| line.each_char.to_a}.to_a
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
12 $map_height = charmap.length
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
13 $map_width = charmap[0].length
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
14
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
15 # Ugly way to find the start, because we know there's one (for now)
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
16 start = charmap.each_with_index.flat_map { |columns, i| j = columns.find_index("S"); if j then [j, i] else nil end }.compact
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
17 start_x, start_y = start
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
18
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
19 $direction_inversion = {north: :south, south: :north, east: :west, west: :east}
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
20
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
21 $pipemap = charmap.map do |row|
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
22 row.map do |cell|
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
23 case cell
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
24 when "|"
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
25 [:north, :south]
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
26 when "-"
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
27 [:east, :west]
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
28 when "L"
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
29 [:north, :east]
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
30 when "J"
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
31 [:north, :west]
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
32 when "7"
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
33 [:south, :west]
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
34 when "F"
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
35 [:south, :east]
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
36 when "S"
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
37 # Assume all directions are valid
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
38 [:north, :source, :east, :west]
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
39 else
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
40 []
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
41 end
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
42 end
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
43 end
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
44
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
45 def valid_position? (x, y)
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
46 x >= 0 and x < $map_width and y >= 0 and y < $map_height
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
47 end
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
48
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
49 def get_target_for_step(step)
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
50 case step.direction
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
51 when :north then [step.x, step.y-1]
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
52 when :south then [step.x, step.y+1]
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
53 when :east then [step.x+1, step.y]
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
54 when :west then [step.x-1, step.y]
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
55 end
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
56 end
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
57
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
58 def get_next_step(step)
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
59 new_x, new_y = get_target_for_step(step)
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
60 target_inputs = valid_position?(new_x, new_y) ? $pipemap[new_y][new_x] : []
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
61 required_direction = $direction_inversion[step.direction]
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
62 target_inputs.include?(required_direction) ? Step.new(new_x, new_y, (target_inputs - [required_direction])[0]) : nil
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
63 end
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
64
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
65 Step = Struct.new(:x, :y, :direction)
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
66
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
67 routes = [:north, :south, :east, :west].map {|dir| [Step.new(start_x, start_y, dir)]}
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
68
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
69 while ! routes.any? {|route| last_step = route[-1]; route.length > 1 and last_step.x == start_x and last_step.y == start_y}
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
70 routes = routes.map do |route|
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
71 next_step = get_next_step(route[-1])
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
72 if next_step
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
73 route << next_step
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
74 else
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
75 nil
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
76 end
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
77 end.compact
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
78 end
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
79
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
80 routes.each {|route| puts "Route: #{route.map{|step| [step.x, step.y]}}"}
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
81 # Subtract one because we end up back at the start
9b1d04091335 Path finding through the pipes for day 10
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
82 puts "Steps: #{routes.map{|route| (route.length - 1)/2}}"