Finding cheapest route (turn costs 500, going straight costs 100)

Question

Story

Original link written in korean

Jordi, the architect of a construction company, received a request from a customer for an estimate for the construction of a raceway. According to the raceway design drawing provided, the raceway site is in the form of an N x N square grid, each grid being 1 x 1. In the design drawing, the cells in each grid are filled with 0 or 1, where 0 indicates that the cells are empty and 1 indicates that the cells are filled with walls. The starting point of the raceway is the (0, 0) space (top left), and the end point is the (N-1, N-1) space (bottom right).

Jordi must build a raceway so that the car from the starting point (0, 0) can safely reach the destination (N-1, N-1). A raceway can be constructed by connecting two adjacent blank spaces up, down, left and right, and a raceway cannot be built in a wall with walls. At this time, a raceway that connects two adjacent blank spaces up and down or left and right is called a straight road.

Also, the point where two straight roads meet each other at right angles is called a corner. Calculating the construction cost, it costs 100 $ to make a straight road, and 500$ to make a corner.

Jordi needs to calculate the minimum cost required to build a raceway in order to make an estimate.

I/O Example

[[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[0,1,0,0,0,1],[0,0,0,0,0,0]]

answer=3200

If you build a raceway like the red one, it costs 3200 won for 12 straight roads and 4 corners. If you build a raceway like the blue path, it costs a total of 3,500 won for 10 straight roads and 5 corners, and it costs more.

my question

My code consumes lots of running time... my new idea is making an library. key value of(x,y). If BFS arrives at (x,y) first time it saves the cost to reach (x,y). If BFS arrives (x,y) again, and it's cost is compared with value existing. and if it bigger than value, it is not added to BFS how's this idea? I did not use this idea on code because I'm afraid this would take long time too.

And I wonder your idea too there is a hint, but I could not understand it.

My code(original code, new idea not used)

from collections import deque
import copy
def check(a,b,board,n):
#checks if it can be added to queue#
    if b=='U':
        if a[0][0]>0 and board[a[0][0]-1][a[0][1]]!=1 and [a[0][0]-1,a[0][1]] not in a[3]:
            return True
    if b=='D':
        if a[0][0]<n-1 and board[a[0][0]+1][a[0][1]]!=1 and [a[0][0]+1,a[0][1]] not in a[3]:
            return True
    if b=='R':
        if a[0][1]<n-1 and board[a[0][0]][a[0][1]+1]!=1 and [a[0][0],a[0][1]+1] not in a[3]:
            return True
    if b=='L':
        if 0<a[0][1] and board[a[0][0]][a[0][1]-1]!=1 and [a[0][0],a[0][1]-1] not in a[3]:
            return True
    return False
def move(a,b):
# append next movement to queue, change direction and add Turn counts
    if b==a[1]:
        if b=='U':
            a[0][0]-=1
            return a
        if b=='D':
            a[0][0]+=1
            return a
        if b=='R':
            a[0][1]+=1
            return a
        if b=='L':
            a[0][1]-=1
            return a
    else:
        if b=='U':
            a[2]+=1
            a[0][0]-=1
            a[1]='U'
            return a
        if b=='D':
            a[2]+=1
            a[0][0]+=1
            a[1]='D'
            return a
        if b=='R':
            a[2]+=1
            a[0][1]+=1
            a[1]='R'
            return a
        if b=='L':
            a[2]+=1
            a[0][1]-=1
            a[1]='L'
            return a
def solution(board):
    value=[]
    n=len(board)
    d=0
    queue=deque()
    # In queue i added elements [current location, Direction,Turn Counts,visited dots in list]
    queue.append([[0,0],'R',0,[]])
    queue.append([[0,0],'D',0,[]])
    while len(queue)!=0:
        p=queue.popleft()

        #to use differnt lists in case of error in if loop

        Up=copy.deepcopy(p)
        Down=copy.deepcopy(p)
        Right=copy.deepcopy(p)
        Left=copy.deepcopy(p)
        past=p[0]
        Up[3].append(past)
        Down[3].append(past)
        Left[3].append(past)
        Right[3].append(past)
        p[3].append(past)
        #I thought the cheapest route can not be longer than shortest route+3
        if d!=0 and len(p[3])>d+3:
            answer = min(value)*100
            return answer
        if p[0]==[n-1,n-1]:
            value.append((len(p[3])-1)+5*p[2])
            d=len(p[3])-1
        if check(Up,'U',board,n)==True:
            queue.append(move(Up,'U'))
        if check(Down,'D',board,n)==True:
            queue.append(move(Down,'D'))
        if check(Right,'R',board,n)==True:
            queue.append(move(Right,'R'))
        if check(Left,'L',board,n)==True:
            queue.append(move(Left,'L'))
    answer = min(value)*100
    return answer

hint (just for reference)

For the lowest cost with K corners, you can reduce the number of straight roads as much as possible. This is done by making K corners and finding the shortest route from the origin to the destination.

Now we define the state space S as follows:

• [Vertical coordinate R][Horizontal coordinate C][Number of corners K][Looking direction D] → Shortest distance when arriving at the (R, C) position while making K corners and looking at direction D

At this time, it is assumed that the cost of moving one space is 1, and the cost of creating a corner is also 1. Now it finds the shortest route to the origin → destination for all Ks. The BFS search code is written as follows:

• Based on the last viewed direction, it searches for three cases: turning left, turning right, and going straight.
• In the case of left and right rotation, add a corner and change the viewing direction.
• In the case of going straight, advance one space in the direction you are looking.

After searching for BFS as above, finally K = 1, 2, 3,… at (N – 1, N – 1) position. Find the shortest distance for the case. At this time, it is important to note that the shortest distance obtained here is a value including the number of corners. Therefore, in the shortest distance with K corners, the construction cost can be calculated as follows:

• (Shortest distance-K) x 100 + K * 500

So how big can the K value here? Each grid can have a maximum of 1 corner. If so, the number of corners in an N x N grid should be less than the number of grid cells. Therefore, the number of corners K can be at most N x N.

Answer 1

tuple, not list

    # In queue i added elements [current location, Direction,Turn Counts,visited dots in list]
    queue.append([[0,0],'R',0,[]])
    queue.append([[0,0],'D',0,[]])

Prefer to write the origin location as (0, 0) rather than [0, 0]. Why? In python we use a tuple to model a C struct, a fixed-length collection of "different" things. We use a list to model an arbitrarily long collection of "same" thing. We're storing two integers here. But are they the "same"? No, certainly not, we impose an interpretation on \$x\$ coordinates which is very different from how we interpret a \$y\$ coordinate.

Similarly, instead of
[[0, 0], 'R', 0, []], prefer this 4-tuple:
((0, 0), 'R', 0, []). Notice that the final visited is perfect: it is a growing list of "same" thing, of visited coordinate pairs.

Using cryptic indexes 0 .. 3 is inconvenient. Prefer to define a namedtuple having four named elements.

Sometimes an immutable tuple is not suitable, and we'll instead choose a mutable @dataclass.

\$(Δx, Δy)\$ representation

The {L, R, U, D} str representation does not come from the Problem Statement, and it is not convenient in the implementation. Prefer a 2-tuple of deltas.

• L: (-1, 0)
• R: (0, 1)
• U: (0, -1)
• D: (0, 1)

Now you can uniformly add a delta to a location without four special cases.

The OP code as written would have benefited from an enum that mapped those four values to delta tuples. Even a dict lookup mapping would have been preferrable.

helpers

The move() and check() helpers are entirely appropriate; thank you for adding them.

def move(a, b):

Yikes! That is just a terrible signature. And doesn't come with a """docstring""" to help the Gentle reader out of this mess. The comment turns out to be insufficient, plus it should be promoted to a docstring.

What is a? What is b? Hard to say. Plus we're treated to lots of cryptic subscripts, instead of e.g. .x or .y coordinate. Yech! And the check() signature suffers the same syndrome.

quadratic time complexity

        if ... and [a[0][0]-1, a[0][1]]   not in a[3]:
            ...
        if ... and [a[0][0]+1, a[0][1]]   not in a[3]:
            ...
        if ... and [a[0][0],   a[0][1]+1] not in a[3]:
            ...
        if ... and [a[0][0],   a[0][1]-1] not in a[3]:
            return True

Wow, that's a lot of linear scans of an increasingly long list. You do this often enough that it would be worth caching a set version of the same datastructure, to reduce the in complexity from \$O(n)\$ linear to \$O(1)\$ constant.

quadratic space complexity

        Up    = copy.deepcopy(p)
        Down  = copy.deepcopy(p)
        Right = copy.deepcopy(p)
        Left  = copy.deepcopy(p)

Wow, that's a lot of duplicate visited coordinates, by the time we get near the exit square.

Prefer to represent "current state" with this mapping:
(entry_direction, location) --> cost.
That is, we entered this location square in one of four ways, and cumulative price of constructing prior squares plus this square is cost. Now it suffices to create four (\$O(1)\$ constant space!) copies of this square, to enqueue four distinct deltas to explore.

You might find it convenient to have a defaultdict report such cost figures. For an as yet unexplored location, report some very large \$\infty\$ cost, perhaps math.float('inf').

We can read out a solution from any location, including the end location, by having DFS scan four adjacent cost values and carry on from there. The entry direction is easily turned into a reverse delta pointing at the next square, typically closer to the origin.

pruning

My code consumes lots of running time

Yeah, that's what comes of exhaustively exploring the space.

An A* consistent admissible heuristic here would be Manhattan distance. That is, pretend there's zero barriers between here and the goal. We'll need to make either zero, or typically one turn. Add up the turn cost, the \$x\$, and the \$y\$ distances to get the best possible "cost to goal", and use that to prioritize which paths to explore first.

Or, since this problem is simple enough, use Dijkstra.

Answer 2

There should be a docstring at the top of the code describing the purpose of the code.

Add blank lines between the functions.

---

For the check function, it is good that you added a comment.

def check(a,b,board,n):
#checks if it can be added to queue#

It is customary to use a docstring and to indent it with the code below it:

def check(a,b,board,n):
    """Checks if it can be added to queue"""

It would be easier to read with spaces after the commas:

def check(a, b, board, n):

The variable name board is descriptive, but the other variable names are not. Choose better names and also add descriptions for each to the docstring.

Since the function returns a boolean value, it is customary to name it with an is_ prefix. For example, rename check as is_valid, or something more meaningful to the code.

The 4 if statements should be combined into an if/elif statement because the 4 conditions are dependent on each other. This better conveys the intent of the code, and it is more efficient since it is unnecessary to check all conditions.

if b=='U':

elif b=='D':

elif b=='R':

elif b=='L':

Add space around the operators (== and !=) for readability:

if b == 'U':

---

Many of the above suggestions also apply to the move function.

The following statement is repeated 8 times:

return a

I think it can be only executed once, outside of the if/else:

def move(a, b):
    # append next movement to queue, change direction and add Turn counts
    if b == a[1]:

    else:

    return a

---

For the solution function, add spaces around the assignment operators for readability:

value = []

The following line:

while len(queue)!=0:

is simpler as:

while len(queue):

Similarly, these 2 lines:

answer = min(value)*100
return answer

can be simplified as:

return min(value)*100

This also eliminates a variable.

This line:

    if check(Up,'U',board,n)==True:

is simpler as:

    if check(Up,'U',board,n):

There is a typo in the following comment (change "differnt" to "different")

    #to use differnt lists in case of error in if loop