Mercurial > repos > other > adventofcode2023

annotate day12-failed.rb @ 25:79dc2ba41df2

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Copy a Dijkstra's Algorithm implementation Gets us the shorted route but doesn't handle the additional "keep turning" conditions
author IBBoard <dev@ibboard.co.uk>
date Sun, 17 Dec 2023 10:32:05 +0000
parents f34254b67082
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
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