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 ยฏ\_(ใ)_/ยฏ
Python
Part 1: Run Dijkstra's algorithm to find shortest path.
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.
Part 2: Track paths while performing Dijkstra's algorithm.
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.
Code:
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.
Python
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()
Can you add your current code to the question? Maybe it's an edge case you're missing.
About 15-20 seconds, not too bad.
Python
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.
Too much water
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.