Mercurial > repos > other > adventofcode2023
diff day12-failed.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 diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/day12-failed.rb Sat Dec 16 20:04:27 2023 +0000 @@ -0,0 +1,96 @@ +#! /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] + +RowData = Struct.new(:symbols, :counts) +CandidateCollector = Struct.new(:completed, :pending) + +def find_earliest_positions(symbols, counts) + # We need to skip items (to separate each object) but I don't know enough Ruby to + # do that in a map/reduce/etc (if it's even possible), so just use classic iteration + char_pos = 0 + count_pos = 0 + match_start = 0 + earliest_matches = [] +# puts "Counts: #{counts}" + while char_pos < symbols.length + # FIXME: Doesn't take account of pre-existing fixed blocks if there are enough question marks + if symbols[char_pos] != "." + if (char_pos - match_start + 1) == counts[count_pos] + if symbols[char_pos+1] != "#" + earliest_matches << match_start +# puts "At #{char_pos} found #{counts[count_pos]} chars from #{match_start} -- #{earliest_matches}" + # We have to allow one space as well as moving on + match_start = char_pos + 2 + count_pos += 1 + else + # We can't have found it because there's not a space! Shuffle along one. + match_start += 1 + end + # Else we're still in the middle of it + end + elsif match_start < char_pos + match_start = char_pos + 1 + end + char_pos += 1 + end + earliest_matches +end + +data = File.open(file, "r").each_line(chomp: true).map do |line| + symbols, counts_str = line.split(" ") + counts = counts_str.split(",").map(&:to_i) + + # There's nothing like Python's strip to strip all matching characters + # So use a regex to just get the characters that could be items + candidate_symbols = /\.*?([^.].+[^.]).*?/.match(symbols)[1] + puts candidate_symbols + earliest_matches = find_earliest_positions(candidate_symbols, counts) + latest_matches = find_earliest_positions(candidate_symbols.reverse, counts.reverse).reverse.zip(counts).map {|pos, count| candidate_symbols.length - pos - count} + puts "#{earliest_matches} to #{latest_matches}" + # Assume lines are less than 100 chars and put a fake end in so we reduce to the end + earliest_matches << 100 + latest_matches << 100 + ranges = earliest_matches.zip(latest_matches).map {|vals| Range.new(*vals)} + sum = ranges.zip(counts).reduce([1, [(-1..-1), 0]]) do |accum, next_range_parts| + size, cur_range_parts = accum + cur_range, cur_count = cur_range_parts + next_range, next_count = next_range_parts + + if cur_range.max >= next_range.min + # Overlap - do combinations + remaining_next_range = next_range.max - cur_range.max - cur_count + triangular = ((next_range.size * (next_range.size + 1)) / 2) + puts "#{remaining_next_range} => #{triangular}" + new_range = (cur_range.max + cur_count + 1)..next_range.end + [size * triangular, [new_range, next_count]] + else + puts "#{cur_range} => #{cur_range.size}" + [size * cur_range.size, next_range_parts] + end + end + puts sum[0] + puts + +=begin + # Aborted attempt trying to use regex to start to find positions for us + count_parts = counts.split(",").map {|count| "([#\?]{#{count.to_i}})"} + counts_re = /[.?]*#{count_parts.join("[.?]+")}[.?]*/ + puts symbols + match = symbols.match(counts_re) + captures = match.captures + puts "#{captures}" + found = captures.map {|v| v.each_char.all?{|c| c == "#"}} + puts "#{found}" + puts captures.each.with_index(1).map {|v, i| "#{v} at #{match.offset(i)}"} +=end + RowData.new(symbols, counts) +end +puts data +# Rest of algorithm here \ No newline at end of file