4
\$\begingroup\$

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

Road

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.

p

\$\endgroup\$
9
  • \$\begingroup\$ Can you explain the math behind the score computation? If I divide the red/blue paths into corner vs. straight, the numbers don't add up. \$\endgroup\$ – aghast Nov 11 '20 at 19:26
  • 1
    \$\begingroup\$ Dynamic programming. Start from the end block and evaluate the minimum cost for each free block linked with it, then propagate until you arriverà to the starting block. \$\endgroup\$ – N74 Nov 11 '20 at 21:16
  • \$\begingroup\$ @AustinHastings there is photo below I think it might help you. for example 3×3, 0,0 0,1 0,2 1,2 2,2 it is shortest 4 straight roads and 1corner so 900$ \$\endgroup\$ – sherloock Nov 12 '20 at 2:10
  • \$\begingroup\$ @N74 umm I tried to do that... but I wonder how to do that. IF I USE QUEUE would that be shorter than mine???please explain more. Thank you \$\endgroup\$ – sherloock Nov 12 '20 at 2:19
  • 1
    \$\begingroup\$ @sherloock, just use taxi-cab distance. The heuristic can be any estimate as long as it never overestimates the remaining cost. In this case, taxi-cab distance would have zero or one turn. If there are walls in the way, then the path would have more turns and a higher cost. So the taxi-cab distance would never be an overestimate. \$\endgroup\$ – RootTwo Nov 17 '20 at 16:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.