Mercurial > repos > other > adventofcode2023
comparison day12.rb @ 23:f34254b67082
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}" |