Those are some really great optimizations, thank you! I understand what you’re doing generally, but I’ll have to step through the code myself to get completely familiar with it.
It’s interesting that string operations win out here over graph algorithms even though this is technically a graph problem. Honestly your write-up and optimizations deserve its own post.
Completely tone deaf. At least they reconsidered and merged the PR after the backlash.
Interesting, how would one write such a finder? I can only think of backtracking DFS, but that seems like it would outweigh the savings.
Good catch! IIRC, only when a node is selected from the min heap can we guarantee that the cost to that node will not go any lower. This definitely seems like a bug, but I still got the correct answer for the samples and my input somehow ¯\_(ツ)_/¯
I chose to represent nodes using the location (i, j) as well as the direction dir faced by the reindeer.
Initially I tried creating the complete adjacency graph but that lead to max recursion so I ended up populating graph for only the nodes I was currently exploring.
First, I modified the algorithm to look through neighbors with equal cost along with the ones with lesser cost, so that it would go through all shortest paths.
Then, I keep track of the list of previous nodes for every node explored.
Finally, I use those lists to run through the paths backwards, taking note of all unique locations.
import os
# paths
here = os.path.dirname(os.path.abspath(__file__))
filepath = os.path.join(here, "input.txt")
# read input
with open(filepath, mode="r", encoding="utf8") as f:
data = f.read()
from collections import defaultdict
from dataclasses import dataclass
import heapq as hq
import math
# up, right, down left
DIRECTIONS = [(-1, 0), (0, 1), (1, 0), (0, -1)]
# Represent a node using its location and the direction
@dataclass(frozen=True)
class Node:
i: int
j: int
dir: int
maze = data.splitlines()
m, n = len(maze), len(maze[0])
# we always start from bottom-left corner (facing east)
start_node = Node(m - 2, 1, 1)
# we always end in top-right corner (direction doesn't matter)
end_node = Node(1, n - 2, -1)
# the graph will be updated lazily because it is too much processing
# to completely populate it beforehand
graph = defaultdict(list)
# track nodes whose all edges have been explored
visited = set()
# heap to choose next node to explore
# need to add id as middle tuple element so that nodes dont get compared
min_heap = [(0, id(start_node), start_node)]
# min distance from start_node to node so far
# missing values are treated as math.inf
min_dist = {}
min_dist[start_node] = 0
# keep track of all previous nodes for making path
prev_nodes = defaultdict(list)
# utility method for debugging (prints the map)
def print_map(current_node, prev_nodes):
pns = set((n.i, n.j) for n in prev_nodes)
for i in range(m):
for j in range(n):
if i == current_node.i and j == current_node.j:
print("X", end="")
elif (i, j) in pns:
print("O", end="")
else:
print(maze[i][j], end="")
print()
# Run Dijkstra's algo
while min_heap:
cost_to_node, _, node = hq.heappop(min_heap)
if node in visited:
continue
visited.add(node)
# early exit in the case we have explored all paths to the finish
if node.i == end_node.i and node.j == end_node.j:
# assign end so that we know which direction end was reached by
end_node = node
break
# update adjacency graph from current node
di, dj = DIRECTIONS[node.dir]
if maze[node.i + di][node.j + dj] != "#":
moved_node = Node(node.i + di, node.j + dj, node.dir)
graph[node].append((moved_node, 1))
for x in range(3):
rotated_node = Node(node.i, node.j, (node.dir + x + 1) % 4)
graph[node].append((rotated_node, 1000))
# explore edges
for neighbor, cost in graph[node]:
cost_to_neighbor = cost_to_node + cost
# The following condition was changed from > to >= because we also want to explore
# paths with the same cost, not just better cost
if min_dist.get(neighbor, math.inf) >= cost_to_neighbor:
min_dist[neighbor] = cost_to_neighbor
prev_nodes[neighbor].append(node)
# need to add id as middle tuple element so that nodes dont get compared
hq.heappush(min_heap, (cost_to_neighbor, id(neighbor), neighbor))
print(f"Part 1: {min_dist[end_node]}")
# PART II: Run through the path backwards, making note of all coords
visited = set([start_node])
path_locs = set([(start_node.i, start_node.j)]) # all unique locations in path
stack = [end_node]
while stack:
node = stack.pop()
if node in visited:
continue
visited.add(node)
path_locs.add((node.i, node.j))
for prev_node in prev_nodes[node]:
stack.append(prev_node)
print(f"Part 2: {len(path_locs)}")
Basically the company is “losing” money every time someone claims the promotion because they are giving their service away for free.
Normally, companies will have a good estimate on how many people will make use of the promotion and how much money they will “lose”, but sometimes the reality exceeds expectations and so they put a cap on tbe number of times a promotion can be claimed so as to not get exploited too much.
Btw I say “lose” in quotes because it may not be an actual loss of money but a loss of potential earnings from a customer. Also, don’t worry about the downvotes, I’ve seen many innocuous comments also get a few downvotes for no reason.
Not to ruin the absurdity of it, but sometimes they have “until supplies last” on digital promotions because they have a limit on the total number of redemptions.
Part 1: Simple DFS counting up the cells and exposed edges
Part 2: Still DFS, however I chose to keep track of all segments of the area, merging them if two segments connected. In the end, number of non-overlapping, non-intersecting segments is equal to number of sides. Not the most efficient solution, but it works.
import os
from collections import defaultdict
# paths
here = os.path.dirname(os.path.abspath(__file__))
filepath = os.path.join(here, "input.txt")
# read input
with open(filepath, mode="r", encoding="utf8") as f:
data = f.read()
# setup input vars
garden = data.splitlines()
m, n = len(garden), len(garden[0])
def part1():
visited = set()
def calcFenceCostFrom(i, j):
"""Calculates the fencing cost of the region starting from coords (i, j)"""
global garden, m, n
plant_type = garden[i][j]
stack = [(i, j)]
area, perimeter = 0, 0
while stack:
ci, cj = stack.pop()
if (ci, cj) in visited:
continue
visited.add((ci, cj))
# add cell to area
area += 1
# check top cell
if ci > 0 and garden[ci - 1][cj] == plant_type:
stack.append((ci - 1, cj))
else:
# if no top cell, add the edge to perimeter
perimeter += 1
# check left cell
if cj > 0 and garden[ci][cj - 1] == plant_type:
stack.append((ci, cj - 1))
else:
# if no left cell, add the edge to perimeter
perimeter += 1
# check bottom cell
if ci < m - 1 and garden[ci + 1][cj] == plant_type:
stack.append((ci + 1, cj))
else:
# if no bottom cell, add the edge to perimeter
perimeter += 1
# check right cell
if cj < n - 1 and garden[ci][cj + 1] == plant_type:
stack.append((ci, cj + 1))
else:
# if no right cell, add the edge to perimeter
perimeter += 1
return area * perimeter
# calculate fencing cost for every region
fencing_cost = 0
for i in range(m):
for j in range(n):
if (i, j) in visited:
continue
fencing_cost += calcFenceCostFrom(i, j)
print(fencing_cost)
def part2():
visited = set()
def calcFenceCostFrom(i, j):
"""Calculates the fencing cost of the region starting from coords (i, j)"""
global garden, m, n
plant_type = garden[i][j]
stack = [(i, j)]
area = 0
# keep track of all distinct, non-intersecting horizontal and vertical segments
segments = {
"H": defaultdict(set),
"V": defaultdict(set)
} # fmt: skip
while stack:
ci, cj = stack.pop()
if (ci, cj) in visited:
continue
visited.add((ci, cj))
# add cell to area
area += 1
# check top cell
if ci > 0 and garden[ci - 1][cj] == plant_type:
stack.append((ci - 1, cj))
else:
# record edge segment
ei = ci - 0.25 # push out the horizontal segment
segment_set = segments["H"][ei]
ej_from, ej_to = cj - 0.5, cj + 0.5 # extend the segment to connect with neighbors
merge_segments(segment_set, ej_from, ej_to) # merge with current segment set
# check left cell
if cj > 0 and garden[ci][cj - 1] == plant_type:
stack.append((ci, cj - 1))
else:
# record edge segment
ej = cj - 0.25 # push out the vertical segment
segment_set = segments["V"][ej]
ei_from, ei_to = ci - 0.5, ci + 0.5 # extend the segment to connect with neighbors
merge_segments(segment_set, ei_from, ei_to) # merge with current segment set
# check bottom cell
if ci < m - 1 and garden[ci + 1][cj] == plant_type:
stack.append((ci + 1, cj))
else:
# record edge segment
ei = ci + 0.25 # push out the horizontal segment
segment_set = segments["H"][ei]
ej_from, ej_to = cj - 0.5, cj + 0.5 # extend the segment to connect with neighbors
merge_segments(segment_set, ej_from, ej_to) # merge with current segment set
# check right cell
if cj < n - 1 and garden[ci][cj + 1] == plant_type:
stack.append((ci, cj + 1))
else:
# record edge segment
ej = cj + 0.25 # push out the vertical segment
segment_set = segments["V"][ej]
ei_from, ei_to = ci - 0.5, ci + 0.5 # extend the segment to connect with neighbors
merge_segments(segment_set, ei_from, ei_to) # merge with current segment set
# number of distinct segments == number of sides
sides = sum(len(segment_set) for seg_dict in segments.values() for segment_set in seg_dict.values())
return area * sides
def merge_segments(segment_set: set, idx_from: int, idx_to: int):
"""Merge segment into existing segment set"""
# find any overlapping / intersecting segments before and after current
former_segment, latter_segment = None, None
for s_from, s_to in segment_set:
if s_from < idx_from and s_to >= idx_from:
former_segment = (s_from, s_to)
if s_to > idx_to and s_from <= idx_to:
latter_segment = (s_from, s_to)
if former_segment is None and latter_segment is None:
# there is no overlapping segment
segment_set.add((idx_from, idx_to))
elif former_segment == latter_segment:
# the overlap segment contains our full segment
pass
elif former_segment is None:
# there is a latter segment only
segment_set.remove(latter_segment)
segment_set.add((idx_from, latter_segment[1]))
elif latter_segment is None:
# there is a former segment only
segment_set.remove(former_segment)
segment_set.add((former_segment[0], idx_to))
else:
# both are disconnected segments
segment_set.remove(former_segment)
segment_set.remove(latter_segment)
segment_set.add((former_segment[0], latter_segment[1]))
fencing_cost = 0
for i in range(m):
for j in range(n):
if (i, j) in visited:
continue
fencing_cost += calcFenceCostFrom(i, j)
print(fencing_cost)
part1()
part2()
One of the most gorgeous games I’ve played!
Can you add your current code to the question? Maybe it’s an edge case you’re missing.
Part 1: Simulate the guard’s walk, keeping track of visited positions
Part 2: Semi brute-force. Try to place an obstacle at every valid position in the guard’s original path and see if it leads to a loop.
import os
from collections import defaultdict
# paths
here = os.path.dirname(os.path.abspath(__file__))
filepath = os.path.join(here, 'input.txt')
# read input
with open(filepath, mode='r', encoding='utf8') as f:
data = f.read()
rows = data.splitlines()
# bounds
m = len(rows)
n = len(rows[0])
# directions following 90 degree clockwise turns
# up, right, down, left
DIRECTIONS = [(-1, 0), (0, 1), (1, 0), (0, -1)]
# find position of guard
guard_i, guard_j = -1, -1
for i in range(m):
for j in range(n):
if rows[i][j] == '^':
guard_i, guard_j = i, j
break
if guard_i != -1:
break
def part1(guard_i, guard_j):
# keep track of visited positions
visited = set()
visited.add((guard_i, guard_j))
dir_idx = 0 # current direction index
# loop while guard is in map
while True:
delta_i, delta_j = DIRECTIONS[dir_idx]
next_gi, next_gj = guard_i + delta_i, guard_j + delta_j # next pos
# if out of bounds, we are done
if not (0 <= next_gi < m) or not (0 <= next_gj < n):
break
# change direction when obstacle encountered
if rows[next_gi][next_gj] == "#":
dir_idx = (dir_idx + 1) % 4
continue
# update position and visited
guard_i, guard_j = next_gi, next_gj
visited.add((guard_i, guard_j))
print(f"{len(visited)=}")
def part2(guard_i, guard_j):
# keep track of visited positions
visited = set()
visited.add((guard_i, guard_j))
dir_idx = 0 # current direction index
loops = 0 # loops encountered
# walk through the path
while True:
delta_i, delta_j = DIRECTIONS[dir_idx]
next_gi, next_gj = guard_i + delta_i, guard_j + delta_j # next pos
# if out of bounds, we are done
if not (0 <= next_gi < m) or not (0 <= next_gj < n):
break
# change direction when obstacle encountered
if rows[next_gi][next_gj] == "#":
dir_idx = (dir_idx + 1) % 4
continue
# if a position is not already in path,
# put a obstacle there and see if guard will loop
if (next_gi, next_gj) not in visited and willLoop(guard_i, guard_j, dir_idx):
loops += 1
# update position and visited
guard_i, guard_j = next_gi, next_gj
visited.add((guard_i, guard_j))
print(f"{loops=}")
# used in part 2
# returns whether placing an obstacle on next pos causes a loop or not
def willLoop(guard_i, guard_j, dir_idx) -> bool:
# obstacle pos
obs_i, obs_j = guard_i + DIRECTIONS[dir_idx][0], guard_j + DIRECTIONS[dir_idx][1]
# keep track of visited pos and the direction of travel
visited: defaultdict[tuple[int, int], list[int]] = defaultdict(list)
visited[(guard_i, guard_j)].append(dir_idx)
# walk until guard exits map or loops
while True:
delta_i, delta_j = DIRECTIONS[dir_idx]
next_gi, next_gj = guard_i + delta_i, guard_j + delta_j # next pos
# if out of bounds, no loop
if not (0 <= next_gi < m) or not (0 <= next_gj < n):
return False
# change direction when obstacle encountered
if rows[next_gi][next_gj] == "#" or (next_gi == obs_i and next_gj == obs_j):
dir_idx = (dir_idx + 1) % 4
continue
# we are looping if we encounter a visited pos in a visited direction
if (next_gi, next_gj) in visited and dir_idx in visited[(next_gi, next_gj)]:
return True
# update position and visited
guard_i, guard_j = next_gi, next_gj
visited[(guard_i, guard_j)].append(dir_idx)
part1(guard_i, guard_j)
part2(guard_i, guard_j)
Their war on emulation is the reason I’ll never buy Nintendo again.
I would hold off on switching to AllDebrid for a bit, because they are also based in France and may be hit with a similar order.
It sounds and looks really cool! Added to my list.
Reading your comment and #32459, I realize that VSCode source control did have some major issues back then.
It looks like they have improved though, as the latest VSCode I use doesn’t auto-initialize repositories anymore.
It’s not that. It means discard all changes made after the last change committed to this local repository.
He wouldn’t have seen the “Discard Changes” button at all if source control wasn’t already setup (and detected by VSCode).
No sane program will delete files when you initialize source control either.
As I found later, VSCode did have weird behaviors with source control back then. My experience is more with the latest versions.
Python
Approach: Recursive memoized backtracking with a Trie
I get to use one of my favorite data structures here, a Trie! It helps us figure out whether a prefix of the design is a valid pattern in linear time.
I use backtracking to choose potential component patterns (using the Trie), kicking off matching the rest of the design down the stack. We can continue matching longer patterns immediately after the recursion stack unwinds.
In addition, I use global memoization to keep track of the feasibility (part 1) or the number of combinations (part 2) for designs and sub-designs. This way, work done for earlier designs can help speed up later ones too.
I ended up combining part 1 and 2 solutions into a single function because part 1 is a simpler variant of part 2 where we count all designs with the number of possible pattern combinations > 0.
Reading Input
import os here = os.path.dirname(os.path.abspath(__file__)) # read input def read_data(filename: str): global here filepath = os.path.join(here, filename) with open(filepath, mode="r", encoding="utf8") as f: return f.read()Trie Implementation
class Trie: class TrieNode: def __init__(self) -> None: self.children = {} # connections to other TrieNode self.end = False # whether this node indicates an end of a pattern def __init__(self) -> None: self.root = Trie.TrieNode() def add(self, pattern: str): node = self.root # add the pattern to the trie, one character at a time for color in pattern: if color not in node.children: node.children[color] = Trie.TrieNode() node = node.children[color] # mark the node as the end of a pattern node.end = TrueSolution
def soln(filename: str): data = read_data(filename) patterns, design_data = data.split("\n\n") # build the Trie trie = Trie() for pattern in patterns.split(", "): trie.add(pattern) designs = design_data.splitlines() # saves the design / sub-design -> number of component pattern combinations memo = {} def backtrack(design: str): nonlocal trie # if design is empty, we have successfully # matched the caller design / sub-design if design == "": return 1 # use memo if available if design in memo: return memo[design] # start matching a new pattern from here node = trie.root # number of pattern combinations for this design pattern_comb_count = 0 for i in range(len(design)): # if design[0 : i+1] is not a valid pattern, # we are done matching characters if design[i] not in node.children: break # move along the pattern node = node.children[design[i]] # we reached the end of a pattern if node.end: # get the pattern combinations count for the rest of the design / sub-design # all of them count for this design / sub-design pattern_comb_count += backtrack(design[i + 1 :]) # save the pattern combinations count for this design / sub-design memo[design] = pattern_comb_count return pattern_comb_count pattern_comb_counts = [] for design in designs: pattern_comb_counts.append(backtrack(design)) return pattern_comb_counts assert sum(1 for dc in soln("sample.txt") if dc > 0) == 6 print("Part 1:", sum(1 for dc in soln("input.txt") if dc > 0)) assert sum(soln("sample.txt")) == 16 print("Part 2:", sum(soln("input.txt")))