Mercurial > repos > other > adventofcode2023

annotate day22.rb @ 31:47dc75915e91

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Implement falling/destroying blocks Implemented part 1 with supports/supported by logic. Implemented part 2 with cascades and summing counts. Code has caching so it is quick _but_ it gives an answer that's too low.
author IBBoard <dev@ibboard.co.uk>
date Wed, 03 Jan 2024 17:00:56 +0000
parents
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
31
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
1 #! /usr/bin/env ruby
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
2
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
3 require 'set'
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
4
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
5 if ARGV.length != 1
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
6 abort("Incorrect arguments - needs input file")
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
7 elsif not File.exist? (ARGV[0])
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
8 abort("File #{ARGV[0]} did not exist")
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
9 end
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
10
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
11 file = ARGV[0]
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
12
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
13 Block = Struct.new(:id, :x, :y, :z)
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
14 SupportedBy = Struct.new(:blocks, :z)
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
15 supports = Hash.new
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
16 supported_by = Hash.new
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
17
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
18 blocks = File.open(file, "r").each_line(chomp: true).with_index.map do |line, id|
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
19 block_start, block_end = line.split("~")
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
20 start_x, start_y, start_z = block_start.split(",")
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
21 end_x, end_y, end_z = block_end.split(",")
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
22 supports[id] = []
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
23 Block.new(id, start_x.to_i..end_x.to_i, start_y.to_i..end_y.to_i, start_z.to_i..end_z.to_i)
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
24 end
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
25
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
26 def height_sort(a,b)
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
27 if a.z.first == b.z.first
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
28 # Make it a stable sort
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
29 a.y.first == b.y.first ? a.x.first <=> b.x.first : a.y.first <=> b.y.first
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
30 else
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
31 a.z.first <=> b.z.first
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
32 end
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
33 end
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
34
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
35 blocks.sort! {|a,b| height_sort(a, b)}
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
36
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
37 def overlap?(range_1, range_2)
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
38 range_1.include?(range_2.first) || range_1.include?(range_2.last) || range_2.include?(range_1.first) || range_2.include?(range_1.last)
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
39 end
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
40
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
41 blocks.reduce([]) do |lower_blocks, block|
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
42 support_blocks = lower_blocks.reduce(SupportedBy.new([], 0)) do |candidate_supports, lower_block|
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
43 if overlap?(block.x, lower_block.x) && overlap?(block.y, lower_block.y)
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
44 if lower_block.z.last > candidate_supports.z
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
45 SupportedBy.new([lower_block], lower_block.z.last)
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
46 elsif lower_block.z.last == candidate_supports.z
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
47 candidate_supports.blocks << lower_block
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
48 candidate_supports
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
49 else
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
50 candidate_supports
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
51 end
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
52 else
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
53 candidate_supports
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
54 end
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
55 end
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
56 drop = block.z.first - support_blocks.z - 1
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
57 block.z = (support_blocks.z+1)..(support_blocks.z+block.z.size)
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
58 support_blocks.blocks.each {|support| supports[support.id] << block}
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
59 supported_by[block.id] = support_blocks.blocks
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
60 lower_blocks << block
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
61 lower_blocks
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
62 end
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
63
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
64 disintegratable = supports.filter {|block_id, supports_list| supports_list.all? {|supported| supported_by[supported.id].length > 1} }
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
65
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
66 puts "#{disintegratable.length} disintegratable blocks"
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
67
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
68 def find_droppers(id, supports, supported_by, dropping, cache)
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
69 new_drops = supports[id].filter do |block|
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
70 (Set.new(supported_by[block.id].map(&:id)) - dropping).length == 0
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
71 end
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
72 dropping = dropping + new_drops.map(&:id)
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
73 new_drops.each do |supported_block|
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
74 cache_key = [supported_block.id, Set.new(supported_by[supported_block.id].map(&:id)) & dropping]
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
75 if cache.include?(cache_key)
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
76 dropping += cache[cache_key]
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
77 #puts "Got #{cache[cache_key]} for #{cache_key}"
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
78 else
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
79 supported_droppers = find_droppers(supported_block.id, supports, supported_by, dropping, cache)
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
80 cache[cache_key] = supported_droppers
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
81 #puts "Caching #{supported_droppers} for #{cache_key} while dropping #{dropping}"
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
82 dropping += supported_droppers
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
83 end
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
84 end
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
85 dropping - [id]
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
86 end
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
87
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
88 cascade = Hash.new
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
89 cache = Hash.new
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
90
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
91 blocks.reverse.each do |block|
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
92 id = block.id
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
93 cascade[id] = find_droppers(id, supports, supported_by, Set.new([id]), cache)
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
94 end
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
95
47dc75915e91 Implement falling/destroying blocks
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
96 puts "Dropping a total of #{cascade.values.map{|val| val.length}.sum} blocks"