Mercurial > repos > other > adventofcode2023
view day12.rb @ 33:676461cc3a70
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 |
line wrap: on
line source
#! /usr/bin/env ruby if ARGV.length != 1 abort("Incorrect arguments - needs input file") elsif not File.exist? (ARGV[0]) abort("File #{ARGV[0]} did not exist") end file = ARGV[0] def truthy?(val) !val.nil? and val != [] and val != "" end def arrangements(candidate, other_candidates, run_lengths, cache) # puts "Looking for #{run_lengths} (#{truthy?(run_lengths)}) in #{candidate} (#{truthy?(candidate)}), #{other_candidates.nil? '' : other_candidates.join(", ")}" puts "Looking for #{run_lengths} in #{candidate}, #{other_candidates.nil? ? '' : other_candidates.join(",")}" if !truthy?(candidate) and !truthy?(run_lengths) puts "Combos: 1 (both empty)" return 1 elsif !truthy?(run_lengths) and !candidate.include? "#" and (!truthy?(other_candidates) or other_candidates.all? {|candidate| truthy?(candidate)}) return 1 elsif (!truthy?(candidate) and truthy?(run_lengths)) or (!truthy?(run_lengths) and candidate.include? "#") puts "Combos: 0 (fail)" return 0 end find_length = run_lengths.first cached = cache[[candidate, other_candidates, run_lengths]] if !cached.nil? puts "Combos: #{cached} (cached)" return cached end combo_count = 0 if find_length == candidate.length # We found a perfect match! new_candidate = other_candidates[0] new_other_candidates = other_candidates[1..] combo_count += arrangements(new_candidate, new_other_candidates, run_lengths[1..], cache) if truthy?(candidate) and !candidate.include? "#" # What if we skip this all all question mark candidate and try later? combo_count += arrangements(new_candidate, new_other_candidates, run_lengths, cache) end elsif find_length < candidate.length if candidate[find_length] != "#" if find_length == candidate.length - 1 new_candidate = other_candidates[0] new_other_candidates = other_candidates[1..] else new_candidate = candidate[(find_length+1)..] new_other_candidates = other_candidates end # We found a substring match that ends in a valid place combo_count += arrangements(new_candidate, new_other_candidates, run_lengths[1..], cache) end if candidate[0] == "?" # We've got space, so try the other combo combo_count += arrangements(candidate[1..], other_candidates, run_lengths, cache) end else # This candidate must all be good parts combo_count += arrangements(other_candidates[0], other_candidates[1..], run_lengths, cache) end puts "Combos: #{combo_count}\n" cache[[candidate, other_candidates, run_lengths]] = combo_count combo_count end cache = Hash.new combos = File.open(file, "r").each_line(chomp: true).map do |line| symbols, run_lengths_str = line.split(" ") run_lengths = run_lengths_str.split(",").map(&:to_i) candidates = symbols.split(".").filter {|candidate| candidate != ""} candidate = candidates.shift line_arrangements = arrangements(candidate, candidates, run_lengths, cache) puts "Line arrangements: #{line_arrangements}\n\n" line_arrangements end puts "#{combos} = #{combos.sum}"