Commits

Grigoriy Petukhov committed 016d642

Solve problem #15

Comments (0)

Files changed (2)

 #!/usr/bin/env python
 """
 Starting in the top left corner of a 22 grid, there are 6 routes (without backtracking) to the bottom right corner.
-
 How many routes are there through a 2020 grid?
 """
 import logging
-from copy import copy
 
-def solve(LIMIT):
-    point = (0, 0)
-    valid_paths = 0
-    path = [point]
-    tried_directions = {}
-    solutions = []
+def count_paths(dim):
+    if not dim:
+        return 0
+    count = 0
+    blocks = [(dim, dim)]
+    cache = {}
+    pending = []
+    while len(blocks):
+        block = blocks.pop()
+        if block in cache:
+            count += cache[block]
+        else:
+            if min(*block) == 1:
+                size = max(*block) + 1
+                count += size
+                cache[block] = size
+            else:
+                block1 = (block[0] -1, block[1])
+                block2 = (block[0], block[1] - 1)
+                if block1 in cache and block2 in cache:
+                    size = cache[block1] + cache[block2]
+                    count += size
+                    cache[block] = size
+                else:
+                    blocks.append(block1)
+                    blocks.append(block2)
+    return count
 
-    while True:
-        # Display
-        #print_map(point, path)
-        #print 'PATH', path
-        #print 'POINT', point
-        #print 'DIRECTIONS', tried_directions.get(point)
-        #print 
-        #res = raw_input()
-        #if res == 'd':
-            #import pdb; pdb.set_trace()
 
-        direction = tried_directions.get(point, -1) + 1
-        if direction == 2:
-            direction = None
 
-        if direction is None:
-            # If all moves from this place were tried
-            if point == (0, 0):
-                return valid_paths
-            else:
-                if point in tried_directions:
-                    del tried_directions[point]
-                path.pop()
-                point = path[-1]
-                continue
-        else:
-            tried_directions[point] = direction
-            if direction == 0:
-                target = (point[0] + 1, point[1])
-            else:
-                target = (point[0], point[1] + 1)
-
-        if (target[0] < 0 or target[0] > LIMIT[0]
-            or target[1] < 0 or target[1] > LIMIT[1]
-            or target in path):
-            # Outside exception or path crossing
-            pass
-        elif target == LIMIT:
-            valid_paths += 1
-        else:
-            # If target is ok then
-            # replace point with target and update path 
-            point = target
-            path.append(point)
-
-
-def format_path(path):
-    return '-'.join(map(str, path))
-
-
-def print_map(point, path):
-    for y in xrange(LIMIT[0] + 1):
-        for x in xrange(LIMIT[1] + 1):
-            if (y, x) == point:
-                print '@',
-            elif (y, x) in path:
-                print path.index((y, x)),
-            else:
-                print '.',
-        print
-    print
-
+def solve():
+    #return count_paths(2)
+    for x in xrange(21):
+        print x, count_paths(x)
 
 
 if __name__ == '__main__':
     if options.test:
         doctest.testmod()
     else:
-        x = 20
-        print 'Limit: %d, path count: %d' % (x, solve((x, x)))
+        print solve()

problem15_brute.py

+#!/usr/bin/env python
+"""
+Starting in the top left corner of a 22 grid, there are 6 routes (without backtracking) to the bottom right corner.
+
+How many routes are there through a 2020 grid?
+"""
+import logging
+from copy import copy
+
+def solve(LIMIT):
+    point = (0, 0)
+    valid_paths = 0
+    path = [point]
+    tried_directions = {}
+    solutions = []
+
+    while True:
+        # Display
+        #print_map(point, path)
+        #print 'PATH', path
+        #print 'POINT', point
+        #print 'DIRECTIONS', tried_directions.get(point)
+        #print 
+        #res = raw_input()
+        #if res == 'd':
+            #import pdb; pdb.set_trace()
+
+        direction = tried_directions.get(point, -1) + 1
+        if direction == 2:
+            direction = None
+
+        if direction is None:
+            # If all moves from this place were tried
+            if point == (0, 0):
+                return valid_paths
+            else:
+                if point in tried_directions:
+                    del tried_directions[point]
+                path.pop()
+                point = path[-1]
+                continue
+        else:
+            tried_directions[point] = direction
+            if direction == 0:
+                target = (point[0] + 1, point[1])
+            else:
+                target = (point[0], point[1] + 1)
+
+        if (target[0] < 0 or target[0] > LIMIT[0]
+            or target[1] < 0 or target[1] > LIMIT[1]
+            or target in path):
+            # Outside exception or path crossing
+            pass
+        elif target == LIMIT:
+            valid_paths += 1
+        else:
+            # If target is ok then
+            # replace point with target and update path 
+            point = target
+            path.append(point)
+
+
+def format_path(path):
+    return '-'.join(map(str, path))
+
+
+def print_map(point, path):
+    for y in xrange(LIMIT[0] + 1):
+        for x in xrange(LIMIT[1] + 1):
+            if (y, x) == point:
+                print '@',
+            elif (y, x) in path:
+                print path.index((y, x)),
+            else:
+                print '.',
+        print
+    print
+
+
+
+if __name__ == '__main__':
+    import doctest;
+    import optparse
+
+    parser = optparse.OptionParser()
+    parser.add_option('-t', '--test', action='store_true',
+                      default=False, help='Run tests')
+    parser.add_option('-d', '--debug', action='store_true',
+                      default=False, help='Output debug info')
+    options, args = parser.parse_args()
+
+    log_level = logging.DEBUG if options.debug else logging.INFO
+    logging.basicConfig(level=log_level, format='%(message)s')
+    if options.test:
+        doctest.testmod()
+    else:
+        for x in xrange(10):
+            print 'Limit: %d, path count: %d' % (x, solve((x, x)))
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.