Mercurial > repos > other > adventofcode2023
view day12.rb @ 36:7197f31970ff
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 |
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}"