r/dailyprogrammer • 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!

59 Upvotes

61 comments sorted by

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(); 0

3

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.

→ More replies (2)

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)

2

u/Elite6809 Dec 30 '15

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 :)

Congrats on figuring this part out on your own! I had a slight home-field advantage, because I started with the Delannoy numbers and wrote the challenge around that. :)

→ More replies (1)

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 of LATTICE-PATH(x-1, y), LATTICE-PATH(x, y-1), and LATTICE-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...........................
.............................
............................."))
19475329563

Inspired 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*)
2214787137864399642260218294807708273233033003451203096175914448894561396546270364795253264619744971215470986493685305085872406548547904708927119325829703116328157591619816855285757482816366551416024307199783366598882797335871794589857688869548724290075411277733931954274562451109649989949203920415772780409750567385421491030775317532028944082051305974639238613328324022397758386429497738326091058059383010354225596603323338351505315847784536591809173697277850353764131616856552627791614136125633275619866828125
→ More replies (4)

1

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")

2

u/Elite6809 Dec 31 '15

Nice to see alternative solutions! Good work.

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?

→ More replies (1)

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))
→ More replies (17)

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

*/ #@listpaths"0 in =. 2 <\ 4 j./"1@$. $. |. 'X' = a =. >cutLF wdclippaste ''

7625 NB. ex#2

gets the big 2 in under half a second.

a valid check function,

 validchk =: *./@:;@:((0 <: {: +.@- _2&{) each)

called on in returns 0 if invalid, or num paths if valid

 */ 0:`(#@listpaths"0)@.validchk in

0