how can ı upload my program into the code jam uploading path? 14 Nisan 2012 18:50 tarihinde Chris Knott < [email protected]> yazdı:
> 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<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. > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. 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.
