ok, I had to reverse the path, and added it to p. Then I added around 15 lines of code or so, and it worked fine - however the only problem was it was too slow. I tried to solve the small input, it solved a couple very slowly. (and in one case it gave a memory error with Pypy)
Any ideas on how to do it more efficiently? On Monday, April 9, 2012 11:08:12 AM UTC+5:30, SudokuMe wrote: > > Hello, > > I've tried using BFS for this problem but am having trouble. > http://code.google.com/codejam/contest/186264/dashboard#s=p2 > > After I get one path for minimal solution, [from bfs] I need to fully > search for all solutions in the bfs, [by looking at number of steps] > but am not able to do it. > > In the code, (shown below) x is the minimal number of steps to reach > the i,j th position. Now I want to look till the x + 1th step - tried > to implement another bfs, but that runs very slow. > > > My code in Python - this basically does BFS, but need to go further > down and better (This will return one path ending at the i,j th > position, with minimal steps) > > ************************************************************************* > from collections import deque > > class Square: > def __init__ (self, x = 0, y = 0, s = 0, a = 0, b = None): > self.X = x > self.Y = y > self.sum = s > self.steps = a > self.square = b > > def SquareMath(i,j,a,target): # l is the Square that we're looking > at, i,j are the positions > a[0] = list(map(int,(a[0].split(' ')))) > l = a[1:] > m = [] > q = deque() > start = Square(i,j,int(l[i][j]),0) > #Square is of type (x,y, sum,steps,square) > q.append(start) > sum1 = 0 > y = 0 > p = [] > c = False > > #Now its the standard BFS algorithm > > while len(q) != 0: > top = q[0] > q.popleft() > > for direction1 in [[1,0],[-1,0],[0,1],[0,-1]]: > for direction2 in [[1,0],[-1,0],[0,1],[0,-1]]: > i,j = direction1[0],direction1[1] > u,v = direction2[0],direction2[1] > new_X = top.X + i > new_Y = top.Y + j > if new_X <= len(l)-1 and new_X >= 0 and new_Y <= > len(l)-1 and new_Y >= 0: > t = Square(new_X,new_Y,top.sum,top.steps,top) > > new2_X = new_X + u > new2_Y = new_Y + v > if new2_X <= len(l)-1 and new2_X >= 0 and new2_Y > <= len(l)-1 and new2_Y >= 0: > s = 0 > if l[new_X][new_Y] == '+': > s = top.sum + int(l[new2_X][new2_Y]) > q.append(Square(new2_X,new2_Y,s,top.steps > + 1,t)) > if top.sum == target: > return top.steps + 1 > elif l[new_X][new_Y] == '-': > s = top.sum - int(l[new2_X][new2_Y]) > q.append(Square(new2_X,new2_Y,s,top.steps > + 1,t)) > if top.sum == target: > return top.steps + 1 > > if top.sum == target: #and c == False: > x = top.steps + 1 > path = [] > t2 = top > path = path + [l[top.X][top.Y]] > while top.square != None: > t1 = top.square > path = path + [l[t1.X][t1.Y]] > top = top.square > > s = ''.join([i for i in path]) > p = p + [[s,x]] > return p > > > ********************************************************************** > > Any ideas/ suggestions? > Thanks alot :) > > > > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To view this discussion on the web visit https://groups.google.com/d/msg/google-code/-/iTD4GAA476QJ. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
