Mercurial > repos > other > adventofcode2023

annotate day14b.rb @ 39:0e17e4bd97a9 default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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 19481b061461
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
24
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
1 #! /usr/bin/env ruby
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
2
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
3 require 'set'
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
4
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
5 if ARGV.length != 1
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
6 abort("Incorrect arguments - needs input file")
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
7 elsif not File.exist? (ARGV[0])
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
8 abort("File #{ARGV[0]} did not exist")
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
9 end
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
10
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
11 file = ARGV[0]
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
12
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
13 platform = File.open(file, "r").each_line(chomp: true).map {|row| row.each_char.to_a}.to_a.transpose()
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
14
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
15 COL_SIZE = platform[0].length
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
16 puts "Column size: #{COL_SIZE}"
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
17
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
18 def cycle(platform)
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
19 [:north, :west, :south, :east].reduce(platform) do |platform, iter|
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
20 # puts "Push #{iter}"
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
21 result = platform.map {|col| col.chunk_while {|i, j| i != "#"}.to_a}.map do |col|
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
22 col.flat_map do |chunk|
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
23 num_movable_objects = chunk.count("O")
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
24 new_chunk = Array.new(num_movable_objects, "O")
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
25 new_chunk.concat(Array.new(chunk.length - num_movable_objects, "."))
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
26 new_chunk[-1] = "#" if chunk[-1] == "#"
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
27 new_chunk
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
28 end
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
29 end
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
30 case iter
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
31 when :north
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
32 # Pushed it North, now we need to go West
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
33 # puts "#{result.transpose.map{|col| col.join('')}.join("\n")}\n\n"
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
34 result.transpose
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
35 when :west
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
36 # Pushed it West, now we need to go South
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
37 # puts "#{result.map{|col| col.join('')}.join("\n")}\n\n"
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
38 result.transpose.map(&:reverse)
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
39 when :south
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
40 # Pushed it South, now we need to go East
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
41 # puts "#{result.map(&:reverse).transpose.map{|col| col.join('')}.join("\n")}\n\n"
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
42 result.transpose.map(&:reverse)
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
43 when :east
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
44 # Pushed it East, now we need to get back to North alignment
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
45 # puts "#{result.map(&:reverse).transpose.map(&:reverse).transpose.map{|col| col.join('')}.join("\n")}\n\n"
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
46 result.map(&:reverse).transpose.map(&:reverse)
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
47 end
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
48 end
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
49 end
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
50
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
51 previous_states = []
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
52 max_cycle_length = 1000000000
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
53 cycle_start = nil
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
54 cycle_length = max_cycle_length
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
55 (1..max_cycle_length).each do |iter|
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
56 # puts "Cycle #{iter}"
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
57 platform = cycle(platform)
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
58 if iter % 1000 == 0
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
59 puts iter
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
60 end
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
61 cycle_start = previous_states.index platform
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
62 if !cycle_start.nil?
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
63 cycle_start += 1 # Compensate for zero-indexing in array
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
64 cycle_length = iter - cycle_start
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
65 # puts "#{iter} - #{cycle_start} + 1 = #{cycle_length}"
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
66 break
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
67 end
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
68 previous_states << platform
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
69 puts "\n\n"
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
70 end
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
71 # Already did the first cycle of the loop, so skip it
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
72 #puts "#{(max_cycle_length - cycle_start)} % #{cycle_length} = #{((max_cycle_length - cycle_start) % cycle_length)} extras"
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
73 ((max_cycle_length - cycle_start) % cycle_length).times {|n| platform = cycle(platform)}
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
74 total_load = platform.reduce(0) do |weight, col|
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
75 col_weight = col.each_with_index.reduce(0) do |accum, cell|
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
76 cell_contents, cell_pos = cell
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
77 accum + (cell_contents == "O" ? (COL_SIZE - cell_pos) : 0)
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
78 end
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
79 # puts "#{col} = #{col_weight}"
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
80 weight + col_weight
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
81 end
19481b061461 Implement tilting and cycling for Day 14 part 2
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
82 puts total_load