Mercurial > repos > other > adventofcode2023
annotate day12.rb @ 32:a1b748f2c416
Implement day 23 "longest route finding"
Allows for "downhill only" and "can climb" approaches. But
climbing still brute-forces the map and takes too long on the
final input.
author | IBBoard <dev@ibboard.co.uk> |
---|---|
date | Thu, 04 Jan 2024 11:18:56 +0000 |
parents | f34254b67082 |
children |
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}" |