Mercurial > repos > other > adventofcode2023
annotate day12-failed.rb @ 28:5ba34a851816
Implement Day 19 workflows, skip part 2
author | IBBoard <dev@ibboard.co.uk> |
---|---|
date | Wed, 03 Jan 2024 11:34:54 +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 RowData = Struct.new(:symbols, :counts) |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
12 CandidateCollector = Struct.new(:completed, :pending) |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
13 |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
14 def find_earliest_positions(symbols, counts) |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
15 # We need to skip items (to separate each object) but I don't know enough Ruby to |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
16 # do that in a map/reduce/etc (if it's even possible), so just use classic iteration |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
17 char_pos = 0 |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
18 count_pos = 0 |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
19 match_start = 0 |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
20 earliest_matches = [] |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
21 # puts "Counts: #{counts}" |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
22 while char_pos < symbols.length |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
23 # FIXME: Doesn't take account of pre-existing fixed blocks if there are enough question marks |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
24 if symbols[char_pos] != "." |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
25 if (char_pos - match_start + 1) == counts[count_pos] |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
26 if symbols[char_pos+1] != "#" |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
27 earliest_matches << match_start |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
28 # puts "At #{char_pos} found #{counts[count_pos]} chars from #{match_start} -- #{earliest_matches}" |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
29 # We have to allow one space as well as moving on |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
30 match_start = char_pos + 2 |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
31 count_pos += 1 |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
32 else |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
33 # We can't have found it because there's not a space! Shuffle along one. |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
34 match_start += 1 |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
35 end |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
36 # Else we're still in the middle of it |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
37 end |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
38 elsif match_start < char_pos |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
39 match_start = char_pos + 1 |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
40 end |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
41 char_pos += 1 |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
42 end |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
43 earliest_matches |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
44 end |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
45 |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
46 data = 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
|
47 symbols, counts_str = line.split(" ") |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
48 counts = counts_str.split(",").map(&:to_i) |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
49 |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
50 # There's nothing like Python's strip to strip all matching characters |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
51 # So use a regex to just get the characters that could be items |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
52 candidate_symbols = /\.*?([^.].+[^.]).*?/.match(symbols)[1] |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
53 puts candidate_symbols |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
54 earliest_matches = find_earliest_positions(candidate_symbols, counts) |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
55 latest_matches = find_earliest_positions(candidate_symbols.reverse, counts.reverse).reverse.zip(counts).map {|pos, count| candidate_symbols.length - pos - count} |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
56 puts "#{earliest_matches} to #{latest_matches}" |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
57 # Assume lines are less than 100 chars and put a fake end in so we reduce to the end |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
58 earliest_matches << 100 |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
59 latest_matches << 100 |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
60 ranges = earliest_matches.zip(latest_matches).map {|vals| Range.new(*vals)} |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
61 sum = ranges.zip(counts).reduce([1, [(-1..-1), 0]]) do |accum, next_range_parts| |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
62 size, cur_range_parts = accum |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
63 cur_range, cur_count = cur_range_parts |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
64 next_range, next_count = next_range_parts |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
65 |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
66 if cur_range.max >= next_range.min |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
67 # Overlap - do combinations |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
68 remaining_next_range = next_range.max - cur_range.max - cur_count |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
69 triangular = ((next_range.size * (next_range.size + 1)) / 2) |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
70 puts "#{remaining_next_range} => #{triangular}" |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
71 new_range = (cur_range.max + cur_count + 1)..next_range.end |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
72 [size * triangular, [new_range, next_count]] |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
73 else |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
74 puts "#{cur_range} => #{cur_range.size}" |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
75 [size * cur_range.size, next_range_parts] |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
76 end |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
77 end |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
78 puts sum[0] |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
79 puts |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
80 |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
81 =begin |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
82 # Aborted attempt trying to use regex to start to find positions for us |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
83 count_parts = counts.split(",").map {|count| "([#\?]{#{count.to_i}})"} |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
84 counts_re = /[.?]*#{count_parts.join("[.?]+")}[.?]*/ |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
85 puts symbols |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
86 match = symbols.match(counts_re) |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
87 captures = match.captures |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
88 puts "#{captures}" |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
89 found = captures.map {|v| v.each_char.all?{|c| c == "#"}} |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
90 puts "#{found}" |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
91 puts captures.each.with_index(1).map {|v, i| "#{v} at #{match.offset(i)}"} |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
92 =end |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
93 RowData.new(symbols, counts) |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
94 end |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
95 puts data |
f34254b67082
Add failed and almost complete Day 12 part 1
IBBoard <dev@ibboard.co.uk>
parents:
diff
changeset
|
96 # Rest of algorithm here |