Mercurial > repos > other > adventofcode2023

annotate day12.rb @ 33:676461cc3a70

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Day 23 - track segments, not each space This allows us to explore the branches once then do quicker calculations for valid route lengths. But still requires exploring 1,262,816 routes to find the longest!
author IBBoard <dev@ibboard.co.uk>
date Thu, 04 Jan 2024 14:52:24 +0000
parents f34254b67082
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
23
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
1 #! /usr/bin/env ruby
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
2
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
3 if ARGV.length != 1
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
4 abort("Incorrect arguments - needs input file")
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
5 elsif not File.exist? (ARGV[0])
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
6 abort("File #{ARGV[0]} did not exist")
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
7 end
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
8
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
9 file = ARGV[0]
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
10
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
11 def truthy?(val)
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
12 !val.nil? and val != [] and val != ""
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
13 end
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
14
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
15 def arrangements(candidate, other_candidates, run_lengths, cache)
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
16 # puts "Looking for #{run_lengths} (#{truthy?(run_lengths)}) in #{candidate} (#{truthy?(candidate)}), #{other_candidates.nil? '' : other_candidates.join(", ")}"
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
17 puts "Looking for #{run_lengths} in #{candidate}, #{other_candidates.nil? ? '' : other_candidates.join(",")}"
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
18 if !truthy?(candidate) and !truthy?(run_lengths)
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
19 puts "Combos: 1 (both empty)"
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
20 return 1
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
21 elsif !truthy?(run_lengths) and !candidate.include? "#" and (!truthy?(other_candidates) or other_candidates.all? {|candidate| truthy?(candidate)})
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
22 return 1
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
23 elsif (!truthy?(candidate) and truthy?(run_lengths)) or (!truthy?(run_lengths) and candidate.include? "#")
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
24 puts "Combos: 0 (fail)"
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
25 return 0
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
26 end
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
27 find_length = run_lengths.first
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
28
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
29 cached = cache[[candidate, other_candidates, run_lengths]]
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
30 if !cached.nil?
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
31 puts "Combos: #{cached} (cached)"
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
32 return cached
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
33 end
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
34
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
35
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
36 combo_count = 0
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
37
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
38 if find_length == candidate.length
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
39 # We found a perfect match!
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
40 new_candidate = other_candidates[0]
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
41 new_other_candidates = other_candidates[1..]
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
42 combo_count += arrangements(new_candidate, new_other_candidates, run_lengths[1..], cache)
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
43 if truthy?(candidate) and !candidate.include? "#"
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
44 # What if we skip this all all question mark candidate and try later?
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
45 combo_count += arrangements(new_candidate, new_other_candidates, run_lengths, cache)
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
46 end
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
47 elsif find_length < candidate.length
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
48 if candidate[find_length] != "#"
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
49 if find_length == candidate.length - 1
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
50 new_candidate = other_candidates[0]
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
51 new_other_candidates = other_candidates[1..]
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
52 else
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
53 new_candidate = candidate[(find_length+1)..]
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
54 new_other_candidates = other_candidates
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
55 end
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
56 # We found a substring match that ends in a valid place
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
57 combo_count += arrangements(new_candidate, new_other_candidates, run_lengths[1..], cache)
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
58 end
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
59 if candidate[0] == "?"
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
60 # We've got space, so try the other combo
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
61 combo_count += arrangements(candidate[1..], other_candidates, run_lengths, cache)
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
62 end
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
63 else
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
64 # This candidate must all be good parts
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
65 combo_count += arrangements(other_candidates[0], other_candidates[1..], run_lengths, cache)
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
66 end
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
67 puts "Combos: #{combo_count}\n"
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
68 cache[[candidate, other_candidates, run_lengths]] = combo_count
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
69 combo_count
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
70 end
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
71
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
72 cache = Hash.new
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
73
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
74 combos = File.open(file, "r").each_line(chomp: true).map do |line|
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
75 symbols, run_lengths_str = line.split(" ")
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
76 run_lengths = run_lengths_str.split(",").map(&:to_i)
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
77 candidates = symbols.split(".").filter {|candidate| candidate != ""}
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
78 candidate = candidates.shift
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
79 line_arrangements = arrangements(candidate, candidates, run_lengths, cache)
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
80 puts "Line arrangements: #{line_arrangements}\n\n"
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
81 line_arrangements
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
82 end
f34254b67082 Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
83 puts "#{combos} = #{combos.sum}"