Mercurial > repos > other > adventofcode2023

annotate day12.rb @ 36:7197f31970ff

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Day 25 part 1 instructions and partial solution
author IBBoard <dev@ibboard.co.uk>
date Thu, 18 Apr 2024 19:56:23 +0100
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}"