Mercurial > repos > other > adventofcode2023
annotate day5b.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 | 5c8d2d181b94 |
| children |
| rev | line source |
|---|---|
| 10 | 1 #! /usr/bin/env ruby |
| 2 | |
| 3 require 'set' | |
| 4 | |
| 5 if ARGV.length != 1 | |
| 6 abort("Incorrect arguments - needs input file") | |
| 7 elsif not File.exist? (ARGV[0]) | |
| 8 abort("File #{ARGV[0]} did not exist") | |
| 9 end | |
| 10 | |
| 11 file = ARGV[0] | |
| 12 | |
| 13 maps = Hash.new | |
| 14 | |
| 15 lines = File.open(file, "r").each_line(chomp: true) | |
| 16 | |
|
13
7826431dbc4f
Finish day 5 part 2 - seeds with ranges
IBBoard <dev@ibboard.co.uk>
parents:
10
diff
changeset
|
17 seeds = lines.first.split(":")[1].split(" ").map(&:to_i).each_slice(2).map {|v| v[0]...(v[0]+v[1])} |
| 10 | 18 |
| 19 RawMapping = Struct.new(:from, :to, :ranges) | |
| 20 MappingRange = Struct.new(:source_range, :offset) | |
| 21 | |
| 22 mappings = Array.new | |
| 23 mappings_array = [] | |
| 24 | |
| 25 lines.drop(1).reduce(mappings_array) do |mappings, val| | |
| 26 if m = /([a-z]+)-to-([a-z]+) map:/.match(val) then | |
| 27 mappings << RawMapping.new(m[1], m[2], []) | |
| 28 elsif val != "" then | |
| 29 dest_start, source_start, range_length = val.split(" ").map(&:to_i) | |
| 30 mappings[-1].ranges << MappingRange.new((source_start...(source_start + range_length)), dest_start - source_start) | |
| 31 end | |
| 32 mappings | |
| 33 end | |
| 34 | |
| 35 mappings = mappings_array.map {|mapping| [mapping.from, mapping]}.to_h | |
| 36 | |
|
13
7826431dbc4f
Finish day 5 part 2 - seeds with ranges
IBBoard <dev@ibboard.co.uk>
parents:
10
diff
changeset
|
37 def map_with_override(mappings, inputs) |
|
7826431dbc4f
Finish day 5 part 2 - seeds with ranges
IBBoard <dev@ibboard.co.uk>
parents:
10
diff
changeset
|
38 inputs.flat_map do |input| |
|
7826431dbc4f
Finish day 5 part 2 - seeds with ranges
IBBoard <dev@ibboard.co.uk>
parents:
10
diff
changeset
|
39 processed = [] |
|
15
5c8d2d181b94
Remove an unnecessary level of nesting
IBBoard <dev@ibboard.co.uk>
parents:
14
diff
changeset
|
40 reduced_unprocessed = mappings.ranges.reduce(input) do |input_range, mapping| |
|
5c8d2d181b94
Remove an unnecessary level of nesting
IBBoard <dev@ibboard.co.uk>
parents:
14
diff
changeset
|
41 if input_range.nil? |
|
14
dcc060e59c47
Replace "each… each…" with a reduce and a flat map
IBBoard <dev@ibboard.co.uk>
parents:
13
diff
changeset
|
42 nil |
|
dcc060e59c47
Replace "each… each…" with a reduce and a flat map
IBBoard <dev@ibboard.co.uk>
parents:
13
diff
changeset
|
43 elsif mapping.source_range.end <= input_range.begin or input_range.end <= mapping.source_range.begin |
|
dcc060e59c47
Replace "each… each…" with a reduce and a flat map
IBBoard <dev@ibboard.co.uk>
parents:
13
diff
changeset
|
44 # Input is entirely outside the mapped range |
|
dcc060e59c47
Replace "each… each…" with a reduce and a flat map
IBBoard <dev@ibboard.co.uk>
parents:
13
diff
changeset
|
45 input_range |
|
dcc060e59c47
Replace "each… each…" with a reduce and a flat map
IBBoard <dev@ibboard.co.uk>
parents:
13
diff
changeset
|
46 elsif mapping.source_range.cover?(input_range) |
|
dcc060e59c47
Replace "each… each…" with a reduce and a flat map
IBBoard <dev@ibboard.co.uk>
parents:
13
diff
changeset
|
47 # Input is inside the mapped range |
|
dcc060e59c47
Replace "each… each…" with a reduce and a flat map
IBBoard <dev@ibboard.co.uk>
parents:
13
diff
changeset
|
48 processed << ((input_range.begin+mapping.offset)...(input_range.end+mapping.offset)) |
|
dcc060e59c47
Replace "each… each…" with a reduce and a flat map
IBBoard <dev@ibboard.co.uk>
parents:
13
diff
changeset
|
49 nil |
|
dcc060e59c47
Replace "each… each…" with a reduce and a flat map
IBBoard <dev@ibboard.co.uk>
parents:
13
diff
changeset
|
50 elsif input_range.begin < mapping.source_range.begin |
|
dcc060e59c47
Replace "each… each…" with a reduce and a flat map
IBBoard <dev@ibboard.co.uk>
parents:
13
diff
changeset
|
51 # Input straddles the start |
|
dcc060e59c47
Replace "each… each…" with a reduce and a flat map
IBBoard <dev@ibboard.co.uk>
parents:
13
diff
changeset
|
52 processed << ((mapping.source_range.begin+mapping.offset)...(input_range.end+mapping.offset)) |
|
dcc060e59c47
Replace "each… each…" with a reduce and a flat map
IBBoard <dev@ibboard.co.uk>
parents:
13
diff
changeset
|
53 (input_range.begin)...(mapping.source_range.begin) |
|
dcc060e59c47
Replace "each… each…" with a reduce and a flat map
IBBoard <dev@ibboard.co.uk>
parents:
13
diff
changeset
|
54 else |
|
dcc060e59c47
Replace "each… each…" with a reduce and a flat map
IBBoard <dev@ibboard.co.uk>
parents:
13
diff
changeset
|
55 # Must straddle the end |
|
dcc060e59c47
Replace "each… each…" with a reduce and a flat map
IBBoard <dev@ibboard.co.uk>
parents:
13
diff
changeset
|
56 processed << ((input_range.begin+mapping.offset)...(mapping.source_range.end+mapping.offset)) |
|
dcc060e59c47
Replace "each… each…" with a reduce and a flat map
IBBoard <dev@ibboard.co.uk>
parents:
13
diff
changeset
|
57 (mapping.source_range.end)...(input_range.end) |
| 10 | 58 end |
| 59 end | |
|
15
5c8d2d181b94
Remove an unnecessary level of nesting
IBBoard <dev@ibboard.co.uk>
parents:
14
diff
changeset
|
60 if ! reduced_unprocessed.nil? |
|
5c8d2d181b94
Remove an unnecessary level of nesting
IBBoard <dev@ibboard.co.uk>
parents:
14
diff
changeset
|
61 processed << reduced_unprocessed |
|
5c8d2d181b94
Remove an unnecessary level of nesting
IBBoard <dev@ibboard.co.uk>
parents:
14
diff
changeset
|
62 end |
|
5c8d2d181b94
Remove an unnecessary level of nesting
IBBoard <dev@ibboard.co.uk>
parents:
14
diff
changeset
|
63 processed |
| 10 | 64 end |
| 65 end | |
| 66 | |
| 67 steps = ["seed", "soil", "fertilizer", "water", "light", "temperature", "humidity"] | |
| 68 | |
| 69 # FIXME: Some negative values and 0s, and the final `min()` gets a nill value | |
|
13
7826431dbc4f
Finish day 5 part 2 - seeds with ranges
IBBoard <dev@ibboard.co.uk>
parents:
10
diff
changeset
|
70 converted_ranges = steps.reduce(seeds) {|vals, map_name| map_with_override(mappings[map_name], vals)} |
|
7826431dbc4f
Finish day 5 part 2 - seeds with ranges
IBBoard <dev@ibboard.co.uk>
parents:
10
diff
changeset
|
71 puts converted_ranges.map{|v| v.min}.min |
|
7826431dbc4f
Finish day 5 part 2 - seeds with ranges
IBBoard <dev@ibboard.co.uk>
parents:
10
diff
changeset
|
72 |