# Commits

committed 016d642

Solve problem #15

# problem15.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 = []`
`+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.