Mercurial > repos > other > adventofcode2023
view 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 |
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}"