I'm a bit annoyed as to why my answer is wrong because, it passes the outputs for the test cases they have provided. Here is the link to the problem https://adventofcode.com/2023/day/17
Can anyone try to suggest me what I'm doing wrong here. I really can't figure out what I'm doing wrong since everything seems to be correct.
from copy import deepcopy
from heapq import heappush, heappop
pInput = [
[int(char) for char in list(line.replace("\n", ""))]
for line in open("input.txt", "r")
]
width, height = len(pInput[0]), len(pInput)
def maxStepsReached(steps):
return steps > 10
def isOOB(y, x):
return not (0 <= y < len(pInput) and 0 <= x < len(pInput[0]))
def expand_helper(node, dy, dx, dir, res):
new_y = node[1] + dy
new_x = node[2] + dx
if isOOB(new_y, new_x) or dir == node[3] and maxStepsReached(node[4] + 1):
return res
if dir == node[3]:
res.append((node[0] + pInput[new_y][new_x], new_y, new_x, dir, node[4] + 1))
elif node[4] >= 4:
res.append((node[0] + pInput[new_y][new_x], new_y, new_x, dir, 1))
return res
def expand(node):
res = []
if node[3] == ">":
for dy, dx, dir in [[0, 1, ">"], [-1, 0, "A"], [1, 0, "V"]]:
res = expand_helper(node, dy, dx, dir, res)
elif node[3] == "<":
for dy, dx, dir in [[0, -1, "<"], [-1, 0, "A"], [1, 0, "V"]]:
res = expand_helper(node, dy, dx, dir, res)
elif node[3] == "A":
for dy, dx, dir in [[-1, 0, "A"], [0, 1, ">"], [0, -1, "<"]]:
res = expand_helper(node, dy, dx, dir, res)
elif node[3] == "V":
for dy, dx, dir in [[1, 0, "V"], [0, 1, ">"], [0, -1, "<"]]:
res = expand_helper(node, dy, dx, dir, res)
return res
def ucs():
closed = set()
open = []
heappush(open, (0, 0, 0, ">", 1))
while open:
node = heappop(open)
if node[1] == height - 1 and node[2] == width - 1 and node[4] >= 4:
return node[0]
if (node[1], node[2], node[3], node[4]) in closed:
continue
closed.add((node[1], node[2], node[3], node[4]))
successors = expand(node)
for s in successors:
heappush(open, s)
return -1
print(ucs())
OK, I found it. The problem is your initial conditions. You push the (0,0) point on your stack in all possible directions with an initial count of 1, but that's not correct. When we start out, we don't COUNT that initial square, so the initial count should be 0.
Change your initialization to:
heappush(open, (0, 0, 0, ">", 0))
and it all works.
So, why does matter? Because your code allows us to consider a path that goes THREE from the origin, when in fact the requirement is to go FOUR from the origin. My maze, for example, does not have that shorter path.
from heapq import heappush, heappop
from collections import namedtuple
Node = namedtuple('Node',['score','y','x','dir','c'])
pInput = [[int(char) for char in list(line.replace("\n", ""))] for line in open("day17.txt", "r")]
width, height = len(pInput[0]), len(pInput)
def isOOB(y, x):
return not (y in range(height) and x in range(width))
alldirs = ((0,1,'>'), (1,0,'V'), (0,-1,'<'), (-1,0,'A'))
opposite = {a:b for a,b in zip('<>AV','><VA')}
MIN,MAX = (1,3)
MIN,MAX = (4,10)
def expand(node):
for dy, dx, dir in alldirs:
if opposite[node.dir] == dir:
continue
if dir != node.dir and node.c < MIN:
continue
new_y = node.y + dy
new_x = node.x + dx
if isOOB(new_y, new_x):
continue
if dir == node.dir:
if node.c < MAX:
yield Node(node.score + pInput[new_y][new_x], new_y, new_x, dir, node.c + 1)
else:
yield Node(node.score + pInput[new_y][new_x], new_y, new_x, dir, 1)
def ucs():
closed = set()
open = []
heappush(open, Node(0, 0, 0, '>', 0))
heappush(open, Node(0, 0, 0, 'V', 0))
while open:
node = heappop(open)
if node.y == height - 1 and node.x == width - 1 and node.c >= MIN:
return node.score
if node[1:] in closed:
continue
closed.add(node[1:])
for s in expand(node):
heappush(open, s)
return -1
print(ucs())
Note that my version lets you do either part 1 or part 2 by commenting out one of the MIN/MAX lines.