pythongraph-theorydijkstrapath-findinga-star

I'm trying to solve, Advent of Code Day 17 Part 2. I get the correct answer to Part 1 but when i modified to solve P2 I get the wrong answer for input


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())

Solution

  • 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.