Mercurial > repos > other > adventofcode2023

comparison day12.rb @ 23:f34254b67082

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add failed and almost complete Day 12 part 1 Read some discussion around solutions in other languages, realised that recursion may work. And we can do caching. Also includes failed map/reduce attempts.
author IBBoard <dev@ibboard.co.uk>
date Sat, 16 Dec 2023 20:04:27 +0000
parents
children
comparison
equal deleted inserted replaced
22:ad73a2ff3d06 23:f34254b67082
1 #! /usr/bin/env ruby
2
3 if ARGV.length != 1
4 abort("Incorrect arguments - needs input file")
5 elsif not File.exist? (ARGV[0])
6 abort("File #{ARGV[0]} did not exist")
7 end
8
9 file = ARGV[0]
10
11 def truthy?(val)
12 !val.nil? and val != [] and val != ""
13 end
14
15 def arrangements(candidate, other_candidates, run_lengths, cache)
16 # puts "Looking for #{run_lengths} (#{truthy?(run_lengths)}) in #{candidate} (#{truthy?(candidate)}), #{other_candidates.nil? '' : other_candidates.join(", ")}"
17 puts "Looking for #{run_lengths} in #{candidate}, #{other_candidates.nil? ? '' : other_candidates.join(",")}"
18 if !truthy?(candidate) and !truthy?(run_lengths)
19 puts "Combos: 1 (both empty)"
20 return 1
21 elsif !truthy?(run_lengths) and !candidate.include? "#" and (!truthy?(other_candidates) or other_candidates.all? {|candidate| truthy?(candidate)})
22 return 1
23 elsif (!truthy?(candidate) and truthy?(run_lengths)) or (!truthy?(run_lengths) and candidate.include? "#")
24 puts "Combos: 0 (fail)"
25 return 0
26 end
27 find_length = run_lengths.first
28
29 cached = cache[[candidate, other_candidates, run_lengths]]
30 if !cached.nil?
31 puts "Combos: #{cached} (cached)"
32 return cached
33 end
34
35
36 combo_count = 0
37
38 if find_length == candidate.length
39 # We found a perfect match!
40 new_candidate = other_candidates[0]
41 new_other_candidates = other_candidates[1..]
42 combo_count += arrangements(new_candidate, new_other_candidates, run_lengths[1..], cache)
43 if truthy?(candidate) and !candidate.include? "#"
44 # What if we skip this all all question mark candidate and try later?
45 combo_count += arrangements(new_candidate, new_other_candidates, run_lengths, cache)
46 end
47 elsif find_length < candidate.length
48 if candidate[find_length] != "#"
49 if find_length == candidate.length - 1
50 new_candidate = other_candidates[0]
51 new_other_candidates = other_candidates[1..]
52 else
53 new_candidate = candidate[(find_length+1)..]
54 new_other_candidates = other_candidates
55 end
56 # We found a substring match that ends in a valid place
57 combo_count += arrangements(new_candidate, new_other_candidates, run_lengths[1..], cache)
58 end
59 if candidate[0] == "?"
60 # We've got space, so try the other combo
61 combo_count += arrangements(candidate[1..], other_candidates, run_lengths, cache)
62 end
63 else
64 # This candidate must all be good parts
65 combo_count += arrangements(other_candidates[0], other_candidates[1..], run_lengths, cache)
66 end
67 puts "Combos: #{combo_count}\n"
68 cache[[candidate, other_candidates, run_lengths]] = combo_count
69 combo_count
70 end
71
72 cache = Hash.new
73
74 combos = File.open(file, "r").each_line(chomp: true).map do |line|
75 symbols, run_lengths_str = line.split(" ")
76 run_lengths = run_lengths_str.split(",").map(&:to_i)
77 candidates = symbols.split(".").filter {|candidate| candidate != ""}
78 candidate = candidates.shift
79 line_arrangements = arrangements(candidate, candidates, run_lengths, cache)
80 puts "Line arrangements: #{line_arrangements}\n\n"
81 line_arrangements
82 end
83 puts "#{combos} = #{combos.sum}"