We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
A couple things to note:
- The number of moves funciton is symetteric, so I went ahead and memoized it which will half our run time (don't think this is necessary but a good thing to recognize)
- I notice a lot of people are using long if statements to get the adjacent list of positions. I felt a simple filter lambda was cleaner.
memo=[[]]defadj(a,b,x,y,n):returnfilter(lambdav:v[0]>=0andv[1]>=0andv[0]<nandv[1]<n,[[x+a,y+b],[x+a,y-b],[x-a,y+b],[x-a,y-b],[x+b,y+a],[x+b,y-a],[x-b,y+a],[x-b,y-a],])defmove(a,b,n):globalmemo# Since move(a, b, n) == move(b, a, n),# we take advantage of this symmtery by memoization.ifmemo[a][b]isnotNone:returnmemo[a][b]visited=[[False]*nfor_inrange(n)]# Queue stores elements as [x, y, depth]# Start with top left positionqueue=[[0,0,0]]whilelen(queue)>0:x,y,l=queue.pop()# At the end, return level of nodeifx==n-1andy==n-1:memo[a][b]=lmemo[b][a]=lreturnlneighbors=[[x_i,y_i]forx_i,y_iinadj(a,b,x,y,n)ifvisited[y_i][x_i]==False]forx_i,y_iinneighbors:visited[y_i][x_i]=Truequeue.insert(0,[x_i,y_i,l+1])memo[a][b]=-1memo[b][a]=-1return-1# Complete the knightlOnAChessboard function below.defknightlOnAChessboard(n):globalmemomemo=[[Nonefor_inrange(n+1)]for_inrange(n+1)]results=[]forainrange(1,n):results.append([])forbinrange(1,n):results[a-1].append(move(a,b,n))returnresults
KnightL on a Chessboard
You are viewing a single comment's thread. Return to all comments →
Python 3 solution.
A couple things to note: - The number of moves funciton is symetteric, so I went ahead and memoized it which will half our run time (don't think this is necessary but a good thing to recognize) - I notice a lot of people are using long if statements to get the adjacent list of positions. I felt a simple filter lambda was cleaner.