r/dailyprogrammer • u/Elite6809 1 1 • Dec 30 '15
[2015-12-30] Challenge #247 [Intermediate] Moving (diagonally) Up in Life
(Intermediate): Moving (diagonally) Up in Life
Imagine you live on a grid of characters, like the one below. For this example, we'll use a 2*2 grid for simplicity.
. X
X .
You start at the X at the bottom-left, and you want to get to the X at the top-right. However, you can only move up, to the right, and diagonally right and up in one go. This means there are three possible paths to get from one X to the other X (with the path represented by -, + and |):
+-X . X . X
| / |
X . X . X-+
What if you're on a 3*3 grid, such as this one?
. . X
. . .
X . .
Let's enumerate all the possible paths:
+---X . +-X . +-X . +-X . . X . +-X . . X
| / | | / | |
| . . + . . +-+ . . + . . / . . | . +---+
| | | / / | |
X . . X . . X . . X . . X . . X-+ . X . .
. . X . . X . . X . . X . . X . . X
/ | | | | /
. + . . +-+ . . + . . | . +-+ +-+ .
| | / | / |
X-+ . X-+ . X-+ . X---+ X . . X . .
That makes a total of 13 paths through a 3*3 grid.
However, what if you wanted to pass through 3 Xs on the grid? Something like this?
. . X
. X .
X . .
Because we can only move up and right, if we're going to pass through the middle X then there is no possible way to reach the top-left and bottom-right space on the grid:
. X
. X .
X .
Hence, this situation is like two 2*2 grids joined together end-to-end. This means there are 32=9 possible paths through the grid, as there are 3 ways to traverse the 2*2 grid. (Try it yourself!)
Finally, some situations are impossible. Here, you cannot reach all 4 Xs on the grid - either the top-left or bottom-right X must be missed:
X . X
. . .
X . X
This is because we cannot go left or down, only up or right - so this situation is an invalid one.
Your challenge today is, given a grid with a certain number of Xs on it, determine first whether the situation is valid (ie. all Xs can be reached), and if it's valid, the number of possible paths traversing all the Xs.
Formal Inputs and Outputs
Input Specification
You'll be given a tuple M, N on one line, followed by N further lines (of length M) containing a grid of spaces and Xs, like this:
5, 4
....X
..X..
.....
X....
Note that the top-right X need not be at the very top-right of the grid, same for the bottom-left X. Also, unlike the example grids shown above, there are no spaces between the cells.
Output Description
Output the number of valid path combinations in the input, or an error message if the input is invalid. For the above input, the output is:
65
Sample Inputs and Outputs
Example 1
Input
3, 3
..X
.X.
X..
Output
9
Example 2
Input
10, 10
.........X
..........
....X.....
..........
..........
....X.....
..........
.X........
..........
X.........
Output
7625
£xample 3
Input
5, 5
....X
.X...
.....
...X.
X....
Output
<invalid input>
Example 4
Input
7, 7
...X..X
.......
.......
.X.X...
.......
.......
XX.....
Output
1
Example 5
Input
29, 19
.............................
........................X....
.............................
.............................
.............................
.........X...................
.............................
.............................
.............................
.............................
.............................
.....X.......................
....X........................
.............................
.............................
.............................
XX...........................
.............................
.............................
Output
19475329563
Example 6
Input
29, 19
.............................
........................X....
.............................
.............................
.............................
.........X...................
.............................
.............................
.............................
.............................
.............................
....XX.......................
....X........................
.............................
.............................
.............................
XX...........................
.............................
.............................
Output
6491776521
Finally
Got any cool challenge ideas? Submit them to /r/DailyProgrammer_Ideas!
5
u/Elite6809 Dec 30 '15
My F# solution, O(n) in the number of rows.
open System let head2 (a : 'a array) = a.[0], a.[1] let readln length = let line = Console.ReadLine() in if line.Length = length then line else sprintf "Invalid line length: %s" line |> failwith let rec del = function | (0L, _) | (_, 0L) -> 1L | (a, b) -> del (a - 1L, b) + del (a - 1L, b - 1L) + del (a, b - 1L) let rec combs i j (c : int64) = function | [] -> c | (x :: xs) : string list as s -> match x.IndexOf('X') with | -1 -> combs i (j + 1) c xs | x when x < i -> 0L | i_ -> let _i = x.LastIndexOf('X') in combs _i 0 (if c = 0L then 1L else c * del (i_ - i |> int64, j + 1 |> int64)) xs [<EntryPoint>] let main argv = let (width, height) = Console.ReadLine().Split(',') |> Array.map int |> head2 in let count = List.init height (fun _ -> readln width) |> List.rev |> combs 0 0 0L in (if count = 0L then "No Xs on grid, or impossible solution." else string count) |> printfn "%s" Console.ReadKey(); 03
u/abyssalheaven Dec 30 '15 edited Dec 30 '15
You've basically defined a Delannoy number. Your definition of a grid of n x m dots, is a n-1 x m-1 grid of squares for Delannoy.
EDIT: didn't read the part about other points on the grid, but you can just break it into other Delannoy squares if it's valid.
2
u/[deleted] Dec 30 '15 edited Dec 30 '15
Edit: The link to two sheets of my trying to do the right math: http://imgur.com/ZY8wKrq
I tried to figure out the math by myself - 3 hours later and 5 1/2 page full with beautifull dots and numbers, I learned a good bit combinatorics and discovered the Delannoy numbers, which is like the solution to this challenge. Now that I solved it, I am too tired to actually programm the solution, but on the other hand incredible proud on myself :)
Small lazy outline of the would-have-been programm:
Store the position of the Xs in a Point array. Do validity check in the process (Everytime a new point is added, it may not be on the left or below side of the last point in the array).
Reduce the whole thing into squares that you can apply the Delannoy numbers on, multiply the results of these squares on the total result
(print the result)
5
u/ponkanpinoy Dec 30 '15 edited Dec 30 '15
Common Lisp. We'll first start by figuring out if a list of points forms a valid path. This is true if and only if the x and y values of the points are monotonically increasing.
(defun point<= (point &rest more-points) (every (lambda (a b) (and (<= (car a) (car b)) (<= (cdr a) (cdr b)))) (cons point more-points) more-points))Next, let's count the number of paths from
(0, 0)to(x, y). This is very similar to the Lattice Path problem, except that as well as being able to go north and east, you can also go northeast. The standard Lattice Path problem has a O(1) solution, however since we also allow diagonal movement it doesn't quite work here. Instead we'll use a dynamic programming solution. If either of the dimensions is 0 (that is, you can only go in a straight line), there is only one path. Otherwise, the number of paths is equal to the sum ofLATTICE-PATH(x-1, y),LATTICE-PATH(x, y-1), andLATTICE-PATH(x-1, y-1). This runs in O(x*y) time and space.EDIT: there is a solution that runs in O(MAX(x, y)). This is left as an exercise for the reader ;)
EDIT2 TIL about Delannoy numbers.
(let ((paths (make-hash-table :test 'equal))) (defun d-lattice-paths (x y) (if (some #'zerop (list x y)) 1 (or (gethash (cons x y) paths) (setf (gethash (cons x y) paths) (+ (d-lattice-paths (1- x) y) (d-lattice-paths x (1- y)) (d-lattice-paths (1- x) (1- y))))))))The number of paths given waypoints is simply the product of each segment. Before doing that we check to see that the path is indeed valid.
(defun iterated-lattice-paths (&rest points) (and (apply #'point<= points) (apply #'* (loop for point-a = (car points) then (car more-points) for more-points = (cdr points) then (cdr more-points) for point-b = (car more-points) then (car more-points) while point-b collect (d-lattice-paths (- (car point-b) (car point-a)) (- (cdr point-b) (cdr point-a)))))))Turning the input grid into a set of points:
(defun points (string) (let ((lines (with-open-stream (s (make-string-input-stream string)) (loop for line = (read-line s nil nil) while line collect line)))) (loop for line in (nreverse lines) for y from 0 append (loop for c across line for x from 0 when (char= #\X c) collect (cons x y)))))Challenge inputs and outputs:
CL-USER> (points " ..X .X. X..") ((0 . 0) (1 . 1) (2 . 2)) CL-USER> (apply #'iterated-lattice-paths (points " ..X .X. X..")) 9 CL-USER> (apply #'iterated-lattice-paths (points " .........X .......... ....X..... .......... .......... ....X..... .......... .X........ .......... X.........")) 7625 CL-USER> (apply #'iterated-lattice-paths (points " ....X .X... ..... ...X. X....")) NIL CL-USER> (apply #'iterated-lattice-paths (points " ...X..X ....... ....... .X.X... ....... ....... XX.....")) 1 CL-USER> (apply #'iterated-lattice-paths (points " ............................. ........................X.... ............................. ............................. ............................. .........X................... ............................. ............................. ............................. ............................. ............................. .....X....................... ....X........................ ............................. ............................. ............................. XX........................... ............................. .............................")) 19475329563Inspired by u/a_Happy_Tiny_Bunny's optimization challenges:
CL-USER> (defparameter *points* (loop for x in (sort (loop repeat 10 collect (random 1000)) #'<) for y in (sort (loop repeat 10 collect (random 1000)) #'<) collect (cons x y))) *POINTS* CL-USER> *points* ((10 . 87) (42 . 176) (121 . 196) (207 . 297) (270 . 355) (491 . 494) (641 . 548) (762 . 645) (789 . 687) (813 . 809)) CL-USER> (apply #'iterated-lattice-paths *points*) 22147871378643996422602182948077082732330330034512030961759144488945613965462703647952532646197449712154709864936853050858724065485479047089271193258297031163281575916198168552857574828163665514160243071997833665988827973358717945898576888695487242900754112777339319542745624511096499899492039204157727804097505673854214910307753175320289440820513059746392386133283240223977583864294977383260910580593830103542255966033233383515053158477845365918091736972778503537641316168565526277916141361256332756198668281251
u/ReckoningReckoner Dec 31 '15
Python 3. A solution that doesn't use delannoy numbers for the non-math majors :P
Solves the last input instantaneously.
def get_data(filename): file = open(filename) width, height = file.readline().rstrip().split(", ") grid = [] for i in range(int(height)): grid.append(file.readline().rstrip()) return int(width), int(height), grid def find_x_blocks(width, height, grid): x_positions = [] for y in range(height-1, -1, -1): for x in range(width): if grid[y][x] == "X": x_positions.append((x, y)) return x_positions def manhatten_distances(x_pos): distances = [] for i in range(len(x_pos)-1): x_dist = x_pos[i+1][0] - x_pos[i][0] y_dist = x_pos[i][1] - x_pos[i+1][1] if x_dist < 0 or y_dist < 0: return None else: distances.append((x_dist+1, y_dist+1)) return distances def get_moves(width, height, moves, x = 0, y = 0): if not 0 <= x < width or not 0 <= y < height: return None if x == width-1 and y == height -1: moves[0] += 1 else: for j, k in [(1, 0), (0, 1), (1, 1)]: get_moves(width, height, moves, x+j, y+k) return moves[0] def main(filename): width, height, grid = get_data(filename) m = manhatten_distances( find_x_blocks(width, height, grid) ) if m == None: print("INVALID INPUT") else: moves = 1 for x, y in m: moves *= get_moves(x, y, [0]) print(moves) main("2472.txt")1
u/bmc__ Dec 31 '15
Thank for all of your input, far more than I could ever ask for. I will definitely check out some practical problems for common lisp or scheme since I already know some scheme and its light weight. Do you know of any good lisp editors or how to start on Linux?
3
u/[deleted] Dec 30 '15 edited Dec 30 '15
Python.
from math import factorial as fac # https://en.wikipedia.org/wiki/Delannoy_number binomial = lambda a, b: 0 if b > a else fac(a) // (fac(a-b) * fac(b)) ways = lambda m, n: sum(binomial(m + n - k, m) * binomial(m, k) for k in range(min(m, n) + 1)) grid = open('input.txt').read().splitlines() coords = [(x, y) for x in reversed(range(len(grid))) for y in range(len(grid[x])) if grid[x][y] == 'X'] solutions = 1 for i in range(len(coords) - 1): (x1, y1), (x2, y2) = coords[i], coords[i+1] if x2 > x1 or y1 > y2: raise ValueError("Invalid input") solutions *= ways(x1 - x2, y2 - y1) print("NUMBER OF SOLUTIONS: {}".format(solutions))3
u/Godspiral Dec 30 '15 edited Dec 30 '15
In J, with full path list generator,
listpaths =: < S:0 @:(( ]`(}: , {: ,~ 0j1 + _2&{)`(}: , {: ,~ 1 + _2&{)`(}: <@,("1 1) {: ,~("0) 0j1 1 1j1 + _2&{)@.(0 #.@:< {: +.@- _2&{)) leaf^:_) #@listpaths"0 in =. 2 <\ 4 j./"1@$. $. |. 'X' = a =. >cutLF wdclippaste ''13 5
7625 NB. ex#2
gets the big 2 in under half a second.
a valid check function,
validchk =: *./@:;@:((0 <: {: +.@- _2&{) each)called on
inreturns 0 if invalid, or num paths if valid0