🎄 Every Christmas, we muster up the motivation to do AOC again 🎄
- Year 2024
- Tooling Info for this year’s advent of code
- Day 1: Historian Hysteria – Edit Distance and Similarity Score
- Day 2: Red-Nosed Reports – Monotonicity
- Day 3: Mull It Over – Regex-based Parsing
- Day 4: Ceres Search - String Searching
- Day 5: Print Queue - Sorting
- [[#incomplete-part-2-day-6-guard-gallivant—turtlebot-path-tracking][[incomplete part 2] Day 6: Guard Gallivant - TurtleBot Path Tracking]]
I’m just going to use org-babel for this, intending to just use the new python knowledge gained from using the “Fluent Python” book.
I have an input downloader script at ./io/input_fetcher.sh.
It looks something like this:
#!/bin/bash
# Check if the correct number of arguments is provided
if [ "$#" -ne 4 ]; then
echo "Usage: $0 <year> <day> <session_cookie> <output_directory>"
exit 1
fi
YEAR=$1
DAY=$2
SESSION_COOKIE=$3
OUTPUT_DIR=$4
# Create the output directory if it doesn't exist
mkdir -p "$OUTPUT_DIR"
# Download the input file for the specified year and day
curl "https://adventofcode.com/$YEAR/day/$DAY/input" \
--cookie "session=$SESSION_COOKIE" \
-o "$OUTPUT_DIR/${YEAR}_day${DAY}_input.txt"
if [ $? -eq 0 ]; then
echo "Input for Day $DAY of Year $YEAR downloaded successfully to $OUTPUT_DIR."
else
echo "Failed to download input for Day $DAY of Year $YEAR."
fiHere’s how to use it:
pwd;
./io/input_fetcher.sh 2024 1 <your_session_cookie> ./io/Python has a bunch of ways to read files:
- bufferred reading
- chunking
- using a mmap
- will handle huge files, even those that can’t be mapped onto the RAM as well
- here’s some ways to setup the mmap (e.g. with file-locking)
- iter over file obj
- good for text files
class Reader:
def __init__(self, filename):
self.filename = filename
self.url = f"./io/{filename}"
return
def apply_fn_to_lines(self, fn):
with open(self.url) as f:
return [fn(line) for line in f][2024-12-02 Mon] Part 1: get edit distance This is about a very primitive edit-distance metric. It’s all to do with numbers.
Part 2: get similarity score, similarly primitive.
I think this is a good example of python’s expressiveness as a language.
from collections import Counter
class Solution:
def reader(self, url):
with open(url) as f:
data = f.read()
split_lines = (line.split() for line in data.split("\n"))
tups = ((int(line[0]), int(line[1])) for line in split_lines if line)
left, right = [], []
for left_val, right_val in tups:
left.append(left_val)
right.append(right_val)
return left, right
# only to be used for the examples
def parse_input(self, input):
split_lines = (line.split() for line in input.split("\n"))
return ((int(left), int(right)) for left, right in split_lines)
def transform_input(self, input):
left, right = [], []
lines = self.parse_input(input)
for left_val, right_val in lines:
left.append(left_val)
right.append(right_val)
return left, right
def get_edit_distance(self, left_vals, right_vals):
distances = [abs(left - right) for left, right in zip(sorted(left_vals), sorted(right_vals))]
return sum(distances)
def get_similarity_score(self, left_vals, right_vals):
right_counts = Counter(right_vals)
scores = (val * right_counts[val] for val in left_vals)
return sum(scores)
input = \
"""3 4
4 3
2 5
1 3
3 9
3 3"""
url = "./io/2024_day1_input.txt"
s = Solution()
# test small inputs:
small_input = s.transform_input(input)
print(s.get_edit_distance(*small_input))
print(s.get_similarity_score(*small_input))
left, right = s.reader(url)
ans_part_1 = s.get_edit_distance(left, right)
ans_part_2 = s.get_similarity_score(left, right)
print(f'answer for part 1: {ans_part_1}')
print(f'answer for part 2: {ans_part_2}')[2024-12-02 Mon] Notes:
- python’s walrus operator to set aliases is convenient!
- ref:
- assignment expressions release doc
- assignment expressions PEP write-up
- e.g. used in the solution below:
part_2_ans = len([outcome for report in reports if (outcome := s.is_report_tolerably_safe(report))])
- ref:
class Solution:
def read_small(self):
small_input = [[7,6,4,2,1], [1,2,7,8,9], [9,7,6,2,1], [1,3,2,4,5], [8,6,4,4,1], [1,3,6,7,9] ]
return small_input
def read(self, url):
with open(url) as f:
data = f.read()
split_lines = (line.split() for line in data.split("\n"))
numbered_reports = []
for line in split_lines:
numbered_reports.append([int(level) for level in line])
return numbered_reports
def get_first_faulty_level_in_report(self, report):
num_levels = len(report)
if num_levels == 1:
return num_levels # indicates that all levels have been swept
prev_direction = None
for i in range(1, len(report)):
jump = report[i] - report[i - 1]
is_legal_jump = abs(jump) >= 1 and abs(jump) <= 3
if not is_legal_jump:
return i
if jump == 0: # not monotonically increasing, is a plateau
return i
is_same_direction = (jump >= 0) == (prev_direction >= 0) if prev_direction else True
if not is_same_direction:
return i
prev_direction = jump
return num_levels
def is_report_safe(self, report):
if not report:
return False
faulty_idx = self.get_first_faulty_level_in_report(report)
if faulty_idx == len(report):
return True
return False
def is_report_tolerably_safe(self, report):
if self.is_report_safe(report):
return True
for skip_idx in range(len(report)):
edited_report = report[:skip_idx] + report[skip_idx + 1:]
if self.is_report_safe(edited_report):
return True
return False
s = Solution()
small_input = s.read_small()
num_safe_reports = len([outcome for report in small_input if (outcome := s.is_report_safe(report))])
print(f"small input ans 1: {num_safe_reports}")
print(f"small input ans 2: {len([outcome for report in small_input if (outcome := s.is_report_tolerably_safe(report))])}")
reports = s.read("./io/2024_day2_input.txt")
part_1_ans = len([outcome for report in reports if (outcome := s.is_report_safe(report))])
print(f"part 1 ans: {part_1_ans}")
part_2_ans = len([outcome for report in reports if (outcome := s.is_report_tolerably_safe(report))])
print(f"part 2 ans: {part_2_ans}")Completed [2024-12-03 Tue]
Approach:
- define the correct regex, define capture groups and use captured values for doing the math operations.
- I have 2 ways of doing it: A) original and menial way of defining segment buffers and operating on them and B) using a single pass regex named groups
A) Original Versionvalid segments are determined by
<POSITIVE><VALID_SEGMENT><POSITIVE/NEGATIVE>where:POSITIVE: “do”NEGATIVE: “don’t”
After extracting out valid segments, parse them as though they are separate inputs to get partial sums then combine them.
B) use named groups in the regex pattern:
pattern =r"(?P<do>do\(\))|(?P<dont>don't\(\))|mul\((?P<x>\d{1,3}),(?P<y>\d{1,3})\)"
Notes:
- named regex groups make life easy see named capture groups
- backreferences are a good regex capability as well: see backrefs
import re
class Solution:
def read_small(self):
input = "xmul(2,4)%&mul[3,7]!@^do_not_mul(5,5)+mul(32,64]then(mul(11,8)mul(8,5))"
return input
def read_small_2(self):
input = "xmul(2,4)&mul[3,7]!^don't()_mul(5,5)+mul(32,64](mul(11,8)undo()?mul(8,5))"
return input
def read(self, url="./io/2024_day3_input.txt"):
with open(url) as f:
data = f.read()
return data
def parse_input(self, input):
pattern = r"mul\((\d{1,3}),(\d{1,3})\)"
matches = re.findall(pattern, input)
partial_multiples = (int(x) * int(y) for x, y in matches)
return sum(partial_multiples)
# single-pass, uses named regex capture groups:
def parse_valid_segments(self, input: str) -> int:
# Combined regex to match mul instructions and do/don't commands
pattern = r"(?P<do>do\(\))|(?P<dont>don't\(\))|mul\((?P<x>\d{1,3}),(?P<y>\d{1,3})\)"
segments = []
is_enabled = True # Start with multiplications enabled
for match in re.finditer(pattern, input):
if match.group("do"):
is_enabled = True
elif match.group("dont"):
is_enabled = False
elif match.group("x") and match.group("y"): # Check if it's a mul instruction
if is_enabled:
x = match.group("x")
y = match.group("y")
segments.append((x, y)) # Capture x and y
# Calculate partial sums from valid segments
partial_sums = (int(x) * int(y) for x, y in segments)
return sum(partial_sums)
# convoluted version:
def parse_valid_segments_(self, input):
input_len = len(input)
do_or_dont_pattern = r"do\(\)|don\'t\(\)"
# gather valid segments:
segments = []
curr_segment_start = 0
is_ignoring_current_segment = False
for match in (matches := re.finditer(do_or_dont_pattern, input)):
match_start, match_end = match.span()
matched_do = match.group() == "do()"
matched_dont = match.group() == "don't()"
if matched_do and not is_ignoring_current_segment:
segments.append((curr_segment_start, match_start))
curr_segment_start = match_end
if matched_do and is_ignoring_current_segment:
curr_segment_start = match_end
is_ignoring_current_segment = False
if matched_dont and not is_ignoring_current_segment:
segments.append((curr_segment_start, match_start))
is_ignoring_current_segment = True
# remember possible last part of the buffer:
should_consider_remaining_end_of_buffer = not is_ignoring_current_segment and curr_segment_start < input_len - 1
if should_consider_remaining_end_of_buffer:
segments.append((curr_segment_start, input_len))
valid_segments = (input[start:end] for start, end in segments)
partial_sums = (self.parse_input(segment) for segment in valid_segments)
return sum(partial_sums)
s = Solution()
small_input = s.read_small()
print(f"small input: { small_input }")
print(f"small input ans: {s.parse_input(small_input)}")
actual_input = s.read()
part_1_ans = s.parse_input(actual_input)
print(f"Part 1 ans: {part_1_ans}")
small_input_2 = s.read_small_2()
small_part_2 = s.parse_valid_segments(small_input_2)
part_2_ans = s.parse_valid_segments(actual_input)
print(f"Part 2 ans: {part_2_ans}")Learnings:
- for directions, it’s easier to define the unit vectors rather than fixed-length vectors and then rely on the correct slicing logic. Should have been more plastic in my solution, and have moved away from the slicing version earlier (harder to debug).
class Solution:
# it's easier to define directions as unit vectors
directions = [
(0, 1), # right
(0, -1), # left
(1, 0), # down
(-1, 0), # up
(1, 1), # down-right
(-1, -1), # up-left
(1, -1), # down-left
(-1, 1) # up-right
]
diagonals = [[
(-1, -1), # up-left
(1, 1), # down-right
],
[
(1, -1), # down-left
(-1, 1) # up-right
]
]
def read_small(self):
input = """MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX"""
matrix = [list(line) for line in input.split("\n") if line]
return matrix
def read_input(self, url="./io/2024_day4_input.txt"):
with open(url) as f:
input = f.read()
matrix = [list(line) for line in input.split("\n") if line]
num_rows, num_cols = len(matrix), len(matrix[0])
print(f"Read a matrix of shape {num_rows}x{num_cols}\n")
return matrix
def is_coord_bounded_in_matrix(self, coord, matrix):
r, c = coord
num_rows, num_cols = len(matrix), len(matrix[0]) return 0 <= r < num_rows and 0 <= c < num_cols
def count_xmas_word_hits(self, coord, matrix):
target = "XMAS"
r, c = coord
hits = 0
# Check each direction for the word "XMAS", iteratively collect chars
for dx, dy in self.directions:
chars = []
for i in range(len(target)):
new_r = r + ( i * dx )
new_c = c + ( i * dy )
if not self.is_coord_bounded_in_matrix((new_r, new_c), matrix):
break
chars.append(matrix[new_r][new_c])
if ''.join(chars) == target:
hits += 1
return hits
def is_x_mas_hit(self, coord, matrix):
target = "MAS"
reversed_target = "".join(list(reversed(target)))
r, c = coord
is_hit = True
for vectors in self.diagonals:
coords = [(r + dx, c + dy)for dx, dy in vectors]
is_invalid_center_candidate = any([not self.is_coord_bounded_in_matrix(coord , matrix) for coord in coords])
if is_invalid_center_candidate:
return False
letters = [matrix[r][c] for r, c in coords]
word = f"{letters[0]}A{letters[1]}"
is_mas = ( word == target ) or ( word == reversed_target )
is_hit = is_hit and is_mas
return is_hit
def solve_part_1(self, matrix):
num_rows, num_cols = len(matrix), len(matrix[0])
total_hits = sum(self.count_xmas_word_hits((r, c), matrix)
for r in range(num_rows)
for c in range(num_cols)
if matrix[r][c] == 'X')
return total_hits
def solve_part_2(self, matrix):
num_rows, num_cols = len(matrix), len(matrix[0])
hits = [True for r in range(num_rows) for c in range(num_cols)
if matrix[r][c] == 'A' and
self.is_x_mas_hit((r, c), matrix)]
return len(hits)
s = Solution()
small_input_matrix = s.read_small()
small_ans_part_1 = s.solve_part_1(small_input_matrix)
print(f"Small ans part 1: {small_ans_part_1}") # Expected output: 18
print(f"Small ans part 2: {s.solve_part_2(small_input_matrix)}")
actual_input = s.read_input()
print(f"Part 1 Ans: {s.solve_part_1(actual_input)}")
print(f"Part 2 Ans: {s.solve_part_2(actual_input)}")This version did some undercounting. It would work on the small input example but not on the actual text input.
So this version is unnecessarily complicated because:
- it relied heavily on correct slicing logic. On hindsight, it’s easier to just rely on unit vectors for direction and iteratively collect the slice.
- the backward slice was likely to be the cause of the undercounting
class Solution:
directions = [ #inclusive range
(-3, 0), # top
(3, 0), # bottom
(0, 3), # right
(0, -3), # left
(-3, -3), # top left
(3, -3), # bottom left
(-3, 3), # top right
(3, 3), # bottom right
]
def read_small(self):
input = """MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX"""
matrix = [list(line) for line in input.split("\n") if line]
num_rows, num_cols = len(matrix), len(matrix[0])
print(f"Read a matrix of shape {num_rows}x{num_cols}\n")
return matrix
def read_input(self, url="./io/2024_day4_input.txt"):
with open(url) as f:
input = f.read()
matrix = [list(line) for line in input.split("\n") if line]
num_rows, num_cols = len(matrix), len(matrix[0])
print(f"Read a matrix of shape {num_rows}x{num_cols}\n")
return matrix
def is_coord_bounded_in_matrix(self, coord, matrix):
r, c = coord
num_rows, num_cols = len(matrix), len(matrix[0])
return r >= 0 and r < num_rows and c >= 0 and c < num_cols
def count_xmas_word_hits(self, coord, matrix):
target ="XMAS"
r, c = coord
hits = 0
for direction in self.directions:
dx, dy = direction
end_coord = (r + dx, c + dy)
if not self.is_coord_bounded_in_matrix(end_coord, matrix):
continue
match direction:
case (x, 0): # it's a column slice
rows_slice = matrix[r: r + dx + 1] if dx > 0 else matrix[r: r + dx - 1: -1]
slice = "".join((row[c] for row in rows_slice))
# print(f"==> COLUMN SLICE {direction} \n\
# sliced out {len(rows_slice)} rows for column slicing\n\
# slice = {slice}")
hits += 1 if slice == target else 0
case (0, y): # it's a row slice:
row = matrix[r]
slice = "".join(row[c: c + dy + 1] if dy > 0 else row[c:c + dy - 1:-1])
# print(f"==> ROW SLICE {direction} \n\
# slice = {slice}")
hits += 1 if slice == target else 0
case _: # it's a diagonal slice:
rows_slice = matrix[r: r + dx + 1] if dx > 0 else matrix[r: r + dx - 1: -1]
dy_direction = 1 if dy > 0 else -1
curr_col = c
cells = []
for row in rows_slice:
# print(f"cell: ({row}, {curr_col}) {row[curr_col]}")
cells.append(row[curr_col])
curr_col += dy_direction
slice = "".join(cells)
# print(f"==> DIAGONAL SLICE {direction} \n\
# sliced out {len(rows_slice)} rows for column slicing\n\
# slice = {slice}")
hits += 1 if slice == target else 0
return hits
def solve_part_1(self, matrix):
num_rows, num_cols = len(matrix), len(matrix[0])
print(f"SEE ME: num rows = {num_rows}, num_cols={num_cols}")
possible_hits = [self.count_xmas_word_hits((r, c), matrix) for r in range(num_rows) for c in range(num_cols) if matrix[r][c] == "X"]
print(f"cells investigated: {len(list(possible_hits))}")
return sum(possible_hits)
s = Solution()
small_input_matrix = s.read_small()
[print(r) for r in small_input_matrix]
small_ans_part_1 = s.solve_part_1(small_input_matrix)
print(f"Small ans part 1 {small_ans_part_1}")
actual_input = s.read_input()
ans_part_1 = s.solve_part_1(actual_input)
print(f"Part 1 {ans_part_1}")[Learnings:]
- python ordering in the modern version is always key-based. So it’s an accessor pattern that the
keyarg consumes. The older way used to be to provide a comparator function (Java-style).So, to use the old way, use
functools.cmp_to_key. When defining the comparator, remember that default sorting is always in ascending order. So if x comes after y, then comparator should return 1, if x comes before y comparator should return -1; 0 otherwise
[Solution Approach:] The first part has inputs that contain 2 info:
- the ordering rules
- multiple ordering configuration
The rules define before and after, and my intial thought was to use a topo-sort approach on this. Realised that it wouldn’t be that helpful to do quicker lookups since it’s going to require us to iterate through a path of the toposort graph.
So, for part 1 the approach shall be:
- ingest the rules definition and create a rules map.
We keep rules using a map of sets.
For each number e.g. 12,
- we have to keep numbers that come after it => use the key = 12
- we have to keep numbers that come before it ==> use the key = -12
- When checking if the order is correct, we check if union or not.
for each element, i in the order:
- every element before it should appear in the prefix set for that element
- every element after it should appear in the suffix set for that element
- every element after it should NOT appear in the prefix set
- every element before it should NOT appear in the suffix set
So for part 2, it’s a natural extension of part 1:
- for the bad updates, try to fix them
So this requires a sorting to be done, but using a custom comparator. The custom comparator part requires a functool (ref python docs)
from collections import defaultdict
from functools import cmp_to_key
class Solution:
def read_input(self, url="./io/2024_day5_input.txt"):
with open(url) as f:
input = f.read()
return input
def parse_input_data(self, data="""47|53
97|13
97|61
97|47
75|29
61|13
75|53
29|13
97|29
53|29
61|53
97|53
61|29
47|13
75|47
97|75
47|61
75|61
47|29
75|13
53|13
75,47,61,53,29
97,61,53,29,13
75,29,13
75,97,47,61,53
61,13,29
97,13,75,29,47"""):
data = data.strip()
rules_def, orders_def = data.split("\n\n")
rules = rules_def.split("\n")
orders = orders_def.split("\n")
rules_map = defaultdict(set)
for rule_def in rules:
before, after = (int(x) for x in rule_def.split("|"))
rules_map[before].add(after)
rules_map[-after].add(before)
parsed_orders = []
for order_def in orders:
parsed_orders.append([int(n) for n in order_def.split(",")])
return rules_map, parsed_orders
def is_order_legal(self, order, rules):
is_legal_order = True
for idx, page in enumerate(order):
preceding_pages = order[:idx]
following_pages = order[idx + 1:]
is_preceding_pages_legal = all((before_page in rules[-page] and before_page not in rules[page] for before_page in preceding_pages))
is_following_pages_legal = all((after_page in rules[page] and after_page not in rules[-page] for after_page in following_pages))
is_legal_order = is_legal_order and is_preceding_pages_legal and is_following_pages_legal
return is_legal_order
def solve_part_1(self, rules, orders):
partial_vals = []
# ASSUMPTION: there are no even_length lists?
return sum(order[len(order) // 2]
for order in orders
if self.is_order_legal(order, rules))
def solve_part_2(self, rules, orders):
erroneous_orders = (order for order in orders if not self.is_order_legal(order, rules))
def comparator(x, y):
# NOTE: default order for sorting is in ascending order
# So if x comes after y ==> it's 1
# if x comes before y ==> it's -1
# if tie then 0
is_x_after_y = x in rules[y]
if is_x_after_y: #
return 1
is_x_before_y = x in rules[-y]
if is_x_before_y:
return -1
return 0
corrected_orders = (sorted(order, key=cmp_to_key(comparator) ) for order in erroneous_orders)
return sum(order[len(order) // 2] for order in corrected_orders)
s = Solution()
small_input = s.parse_input_data()
actual_input = s.parse_input_data(s.read_input())
print(f"part 1 example ans: {s.solve_part_1(*small_input)}")
print(f"part 1 ans: {s.solve_part_1(*actual_input)}")
print(f"part 2 example ans: {s.solve_part_2(*small_input)}")
print(f"part 2 ans: {s.solve_part_2(*actual_input)}")last attempted [2024-12-16 Mon], might come back to this eventually, let’s skip this
Notes: [Part 1]
- from input we need to grok the following: a. guard_start_coord b. obstacle_coords c. map dimensions we don’t need to keep track of the entire cartesian plane, just the obstacles and boundaries
- auxiliary info needed:
- visited_coord set –> so that you don’t double count the positions
- visited_positions counter
edge cases / mistakes:
- though the input doesn’t include it, the traversal algo should detect cycles and avoid infinite recursion.
- I had a silly off-by-one-error because of my
is_bounded()fn.
[Part 2]
- it’s about creating cycles. We could improve our current path simulation to add in cycle-detection To do cycle detection, we can keep a count of duplicate cells encountered. If num_duplicates > total number of cells then it’s a cycle
- For the possible places, we can have candidates for where we can add the obstruction, and we just simulate to check if a cycle is detected, assuming that obstruction is pushed into my list of obstacles
^ following this is basically a brute-force approach and is it some ungodly polynomial time (actually tried it, took about 15mins of running the brute-force version), so we explore improvements:
Some observations:
- we can likely do a single pass, because at any one point, if there was a new obstacle infront of a current cell, then the guard would turn and keep going until he goes back to a similar loop as before.
- from 1, only cummulative history matters
- rules for valid “new obstacle”,
- doesn’t have any original obstacle between the current cell and it
- can create loop with history so far
Note that to find a loop, we don’t just check immediate adjacent cell from current, but all the cells in the vertical/horizontal
from collections import defaultdict
class Solution():
next_direction = {
"^":">",
"v": "<",
"<": "^",
">": "v"
}
def read_input(self, url="./io/2024_day6_input.txt"):
with open(url) as f:
input = f.read()
return input
def parse_input(self, input="""....#.....
.........#
..........
..#.......
.......#..
..........
.#..^.....
........#.
#.........
......#..."""):
lines = input.strip().split("\n")
guard_start_info = None
obstacles = []
num_rows = len(lines)
for row_idx, row in enumerate(lines):
num_cols = len(row)
for col_idx, cell_val in enumerate(row):
coord = (row_idx, col_idx)
match cell_val:
case "#":
obstacles.append((row_idx, col_idx))
case "^" | "<" | ">" | "v":
guard_start_info = ((row_idx, col_idx), cell_val) # coordinate and direction
case ".":
continue
map_dims = (num_rows, num_cols)
return {
"map_dims": map_dims,
"obstacles": obstacles,
"guard_start_info": guard_start_info
}
def is_coord_in_map(self, coord, map_dims):
num_rows, num_cols = map_dims
r, c = coord
return r >=0 and r < num_rows and c >= 0 and c < num_cols
def get_next_cell(self, curr_cell, direction):
curr_row, curr_col = curr_cell
match direction:
case "^":
next_cell = (curr_row - 1, curr_col)
case "v":
next_cell = (curr_row + 1, curr_col)
case "<":
next_cell = (curr_row, curr_col - 1)
case ">":
next_cell = (curr_row, curr_col + 1)
return next_cell
def turn(self, direction):
return self.next_direction[direction]
def is_point_between(self, a, b, test):
"""
Check if the point 'test' is within the bounding box defined by points 'a' and 'b'.
"""
x1, y1 = a
x2, y2 = b
test_x, test_y = test
return (min(x1, x2) <= test_x <= max(x1, x2)) and (min(y1, y2) <= test_y <= max(y1, y2))
def can_create_loop(self, current_cell, current_direction, obstacles, visited):
"""
Given the current cell, it would have a current direction and the next cell in that direction may be a candidate for a new obstacle.
Suppose we turned (and hence are facing direction = turned_direction), then to create a loop, we just have to find from within the visited history, a cell in that same direction.
from current cell, we have a row_idx, col_idx, for the current direction.
Based on the direction, we just need a match:
if ^ then have to be same col and row_idx less than curr
if v then have to be same col and row_idx more than curr
if < then have to be same row and col_idx is less than
if > then have to be same row and col_idx is more than
There may be NO obstacles in the middle of the two
"""
obstacle_candidate_coord = self.get_next_cell(current_cell, current_direction)
if (obstacle_candidate_coord in obstacles):
return False
turned_direction = self.next_direction[current_direction]
row_idx, col_idx = current_cell
has_obstacle_in_the_middle = lambda curr_coord, matching_coord: any((True for obstacle in obstacles if self.is_point_between(matching_coord, current_cell, obstacle)))
match_fn = {
"^": lambda r, c: c == col_idx and r < row_idx,
"v": lambda r, c: c == col_idx and r > row_idx,
"<": lambda r, c: r == row_idx and c < col_idx,
">": lambda r, c: r == row_idx and c > col_idx
}
matches = [
matching_coord for matching_coord in visited.keys()
if match_fn[turned_direction](*matching_coord) and
turned_direction in visited[matching_coord] and
not has_obstacle_in_the_middle(current_cell, matching_coord)
]
return len(matches) > 0
def simulate_guard_path(self, input_info):
map_dims = input_info.get("map_dims")
total_cells = map_dims[0] * map_dims[1]
obstacles = input_info.get("obstacles")
guard_start_coord, current_direction = input_info.get("guard_start_info")
guard_coord = guard_start_coord
visited = defaultdict(set)
new_obstacle_candidates = set()
num_turns = 0
repeat_visits = 0
has_detected_cycle = False
while is_guard_on_map:= self.is_coord_in_map(guard_coord, map_dims):
if (is_repeat_visit:= len(visited[guard_coord]) > 0):
repeat_visits += 1
if (has_detected_cycle:= repeat_visits > total_cells + 1):
print("CYCLE FOUND")
break
next_cell = self.get_next_cell(guard_coord, current_direction)
turned_direction = self.next_direction[current_direction]
turned_next_cell = self.get_next_cell(guard_coord, turned_direction)
# mark cell as visited:
visited[guard_coord].add(current_direction)
if (self.is_coord_in_map(next_cell, map_dims) and
next_cell != guard_start_coord and
self.can_create_loop(guard_coord, current_direction, obstacles, visited)):
new_obstacle_candidates.add(next_cell)
if (is_blocked_by_obstacle:= next_cell in obstacles):
current_direction = turned_direction
next_cell = turned_next_cell
num_turns += 1
guard_coord = next_cell
return has_detected_cycle, visited, new_obstacle_candidates
s = Solution()
actual_input = s.read_input()
example_parsed_info = s.parse_input()
parsed_info = s.parse_input(actual_input)
is_cyclic, visited, obstacle_candidates = s.simulate_guard_path(example_parsed_info)
print(f"example part 1: is_cyclic_simulation? {is_cyclic} # visited = {len([k for k, v in visited.items() if v])} # obstacle candidates: {len(obstacle_candidates)}")
is_cyclic, visited, obstacle_candidates = s.simulate_guard_path(parsed_info)
print(f"actual ans: is_cyclic = {is_cyclic}, # visited = {len(visited)} # obstacle candidates: {len(obstacle_candidates)}")Here’s the brute-force approach to part 2:
# brute-forced, my initial answer was 1909 from this, somehow it's incorrect, says that ans applies for a different input(?)
def get_obstruction_locations(self, input_info):
print(input_info.keys())
num_rows, num_cols = map_dims = input_info.get("map_dims")
guard_start_coord, _= guard_start_info = input_info.get("guard_start_info")
obstacles = input_info.get("obstacles")
reserved_locations = set(obstacles)
reserved_locations.add(guard_start_coord)
obstruction_candidates = ((row_idx, col_idx) for row_idx in range(num_rows) for col_idx in range(num_cols) if (row_idx, col_idx) not in reserved_locations)
valid_locations = [candidate for candidate in obstruction_candidates if (is_cyclic:= self.simulate_guard_path({
"map_dims": map_dims,
"obstacles": obstacles + [candidate],
"guard_start_info": guard_start_info
})[0])]
return valid_locations