annotate day14.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 46fb65f2cb94
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
21
46fb65f2cb94 Add Day 14 part 1 implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
1 #! /usr/bin/env ruby
46fb65f2cb94 Add Day 14 part 1 implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
2
46fb65f2cb94 Add Day 14 part 1 implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
3 if ARGV.length != 1
46fb65f2cb94 Add Day 14 part 1 implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
4 abort("Incorrect arguments - needs input file")
46fb65f2cb94 Add Day 14 part 1 implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
5 elsif not File.exist? (ARGV[0])
46fb65f2cb94 Add Day 14 part 1 implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
6 abort("File #{ARGV[0]} did not exist")
46fb65f2cb94 Add Day 14 part 1 implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
7 end
46fb65f2cb94 Add Day 14 part 1 implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
8
46fb65f2cb94 Add Day 14 part 1 implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
9 file = ARGV[0]
46fb65f2cb94 Add Day 14 part 1 implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
10
46fb65f2cb94 Add Day 14 part 1 implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
11 platform = File.open(file, "r").each_line(chomp: true).map {|row| row.each_char.to_a}.to_a.transpose()
46fb65f2cb94 Add Day 14 part 1 implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
12
46fb65f2cb94 Add Day 14 part 1 implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
13 COL_SIZE = platform[0].length
46fb65f2cb94 Add Day 14 part 1 implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
14
46fb65f2cb94 Add Day 14 part 1 implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
15 chunked_platform = platform.map {|col| col.chunk_while {|i, j| i != "#"}.to_a}
46fb65f2cb94 Add Day 14 part 1 implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
16 total_load = chunked_platform.reduce(0) do |weight, col|
46fb65f2cb94 Add Day 14 part 1 implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
17 _, col_weight = col.reduce([COL_SIZE, 0]) do |accum, chunk|
46fb65f2cb94 Add Day 14 part 1 implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
18 first_obj_weight, temp_weight = accum
46fb65f2cb94 Add Day 14 part 1 implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
19 num_moved_objs = chunk.count("O")
46fb65f2cb94 Add Day 14 part 1 implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
20 last_obj_weight = first_obj_weight - num_moved_objs
46fb65f2cb94 Add Day 14 part 1 implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
21 temp_weight += ((first_obj_weight * (first_obj_weight + 1)) / 2) - ((last_obj_weight * (last_obj_weight + 1)) / 2)
46fb65f2cb94 Add Day 14 part 1 implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
22 first_obj_weight -= chunk.length
46fb65f2cb94 Add Day 14 part 1 implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
23 [first_obj_weight, temp_weight]
46fb65f2cb94 Add Day 14 part 1 implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
24 end
46fb65f2cb94 Add Day 14 part 1 implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
25 weight + col_weight
46fb65f2cb94 Add Day 14 part 1 implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
26 end
46fb65f2cb94 Add Day 14 part 1 implementation
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
27 puts total_load