CODEWITHSUNDEEP
f#
Avrohom Yisroel
Avrohom Yisroel

Reputation: 9440

How do I branch through multiple possibilities in a function?

Been trying to solve Project Euler problem 15 (need to see the diagram on the site to understand it).

I know there are mathematical ways to solve this, but I am interested in finding a way using direct exploration. My idea was to start at the top left corner, then use a recursive function to branch through every possibly option (ie right or down, as long as you aren't at the edge already), returning a list of al possible paths.

My problem is that I don't see how to handle the case where you can branch. So far I came up with the following...

let findPaths n =
  let rec path n x y p =
    if x < 1 || x > n || y < 1 || y > n then failwith (sprintf "Invalid position (%d, %d)" x y)
    match (x, y) with
    | (_, _) when x = n && y = n ->
      printfn "Done"
      (x, y)::p
    | (_, _) when x = n && y < n ->
      printfn "At (%d, %d), can only move down" x y
      (x, y)::path n x (y + 1) p
    | (_, _) when x < n && y = n ->
      printfn "At (%d, %d), can only move right" x y
      (x, y)::path n (x + 1) y p
    | (_, _) ->
      printfn "At (%d, %d), can move right or down" x y
      (x, y)::path n (x + 1) y p
  path n 1 1 []

The printfn lines are there so I could see how it worked its way through the grid.

This will find one path, namely by going right until it hits the edge, then going down to the end of the grid.

What I would like to do is have the last case explore both possibilities, returning a list of paths. That way, it would eventually return all paths. I can't see how to do this though.

Anyone any ideas? Can I even do this? If not, how else would you tackle this problem? Again, I'm looking for a solution that explores the grid, so could theoretically be used on a grid with missing edges, where the plain mathematical approach wouldn't work.

Upvotes: 0

Views: 64

Answers (1)

Tomas Petricek
Tomas Petricek

Reputation: 243041

One solution that I find quite nice is to change the path function so that it returns a sequence of paths rather than a single path. This can be done by wrapping the body inside seq { .. } and producing results using the yield keyword. The nice thing is that it does not change your code very much:

let findPaths n =
  let rec path n x y p = seq {
    if x < 1 || x > n || y < 1 || y > n then failwith (sprintf "Invalid position (%d, %d)" x y)
    match (x, y) with
    | (_, _) when x = n && y = n ->
      printfn "Done"
      yield (x, y)::p
    | (_, _) when x = n && y < n ->
      printfn "At (%d, %d), can only move down" x y
      for subPath in path n x (y + 1) p do
        yield (x, y)::subPath
    | (_, _) when x < n && y = n ->
      printfn "At (%d, %d), can only move right" x y
      for subPath in path n (x + 1) y p do
        yield (x, y)::subPath
    | (_, _) ->
      printfn "At (%d, %d), can move right or down" x y
      for subPath in path n x (y + 1) p do
        yield (x, y)::subPath
      for subPath in path n (x + 1) y p do
        yield (x, y)::subPath }
  path n 1 1 []

The one tricky bit is that you now need to iterate over all possible sub-paths when you call path recursively - and then append the current (x, y) at the beginning of each sub-path.

There is a bit of duplication because you now need the code to move down / move right in two different places. I think this is actually easier to write using ordinary if - there is not much benefit using match when you are not pattern matching on anything:

let findPaths n =
  let rec path n x y p = seq {
    if x < 1 || x > n || y < 1 || y > n then 
      failwith (sprintf "Invalid position (%d, %d)" x y)
    if x = n && y = n then yield (x, y)::p
    if y < n then
      for subPath in path n x (y + 1) p do
        yield (x, y)::subPath
    if x < n then
      for subPath in path n (x + 1) y p do
        yield (x, y)::subPath }
  path n 1 1 []

Also, I think that you started working on a solution that would use the accumulator parameter p, but then you abandoned it and rather than building the path as you go, you are building it as you are returning from a recursive call. Using p makes the code even nicer:

let findPaths n =
  let rec path n x y p = seq {
    if x < 1 || x > n || y < 1 || y > n then 
      failwith (sprintf "Invalid position (%d, %d)" x y)
    if x = n && y = n then yield List.rev ((x, y)::p)
    if y < n then
      yield! path n x (y + 1) ((x, y)::p)
    if x < n then
      yield! path n (x + 1) y ((x, y)::p) }
  path n 1 1 []

Upvotes: 4

Related Questions