Here you go - http://paste2.org/p/1979318
On Tuesday, April 10, 2012 7:24:16 AM UTC+1, SudokuMe wrote: > > 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/-/dLtwRhRb9NEJ. 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.
