CODEWITHSUNDEEP
f#
Hoodwinked
Hoodwinked

Reputation: 9

Filtering a list of lists, using List.map and/or List.length

I have a list containing lists as seen below:

[[(3, 3); (2, 3); (1, 3); (1, 2); (1, 1)];
[(3, 3); (2, 3); (2, 2); (1, 2); (1, 1)];
[(3, 3); (2, 3); (2, 2); (2, 1); (1, 1)];
[(3, 3); (3, 2); (2, 2); (1, 2); (1, 1)];
[(3, 3); (3, 2); (2, 2); (2, 1); (1, 1)];
[(3, 3); (3, 2); (3, 1); (2, 1); (1, 1)]]

The list shows the shortest paths from source to target for a robot. In this case, our source grid point is (3, 3) and target grid point is (1, 1).

I have now added code so that the robot can move diagonally (and not only vertically/horizontally). The code has thus so far been conditioned to ONLY take steps that bring it closer to the target. However, after adding the diagonal dimension to the code, I get STACKOVERFLOW.

Hence, I only want a list of lists (robot moves) that brings the robot to the target.

I am thinking that List.map and List.length could be of help here, and lastly imposing a "return minimum length only" in order to obtain the shortest routes to the target.

My code so far (see bottom of code for stackoverflow problem):

type pos = int*int

let p1 = (1, 1) // source grid point
let p2 = (3, 3) // target grid point

let dist (p1: pos) (p2: pos) : int =
 (((pown ((fst p2)-(fst p1)) 2) + (pown ((snd p2)-(snd p1)) 2)))

dist p1 p2
// printfn "%A" (dist p1 p2)

///////////////////////////////////////////////////////////////////////
let src = p1
let tg = p2
let candidates (src: pos) (tg: pos) : pos list =
 let candi = [((fst src)+1), (snd src); ((fst src)-1), (snd src); (fst src), ((snd src)+1); (fst src), ((snd src)-1)]
 let candilist = candi |> List.filter (fun x -> dist x tg <= dist src tg)
 candilist
//printfn "%A" (candidates src tg)

///////////////////////////////////////////////////////////////////////

let source = (3, 3)
let target = (1, 1)
let rec routes (src: pos) (tg: pos) : pos list list =
 match src with
  p when p = tg -> [[tg]]
  |_ -> List.concat (List.map (fun j -> List.map (fun i -> src :: i) (routes j tg))(candidates src tg))

// printfn "%A" (routes source target)

///////////////////////////////////////////////////////////////////////

let candidates2 (src: pos) (tg: pos) : pos list =
 let candi = [((fst src)+1), (snd src); ((fst src)-1), (snd src); (fst src), ((snd src)+1); (fst src), ((snd src)-1); ((fst src)+1), ((snd src)+1); ((fst src)+1), ((snd src)-1); ((fst src)-1), ((snd src)+1); ((fst src)-1), ((snd src)-1)]
 let candilist = candi |> List.filter (fun x -> dist x tg <= dist src tg)
 candilist

// printfn "%A" (candidates2 src tg)

let rec routes2 (src: pos) (tg: pos) : pos list list =
 match src with
  p when p = tg -> [[tg]]
  |_ -> List.concat (List.map (fun j -> List.map (fun i -> src :: i) (routes2 j tg))(candidates2 src tg))

printfn "%A" (routes2 source target) // stackoverflow

Upvotes: 0

Views: 120

Answers (1)

Tomas Petricek
Tomas Petricek

Reputation: 243041

One issue is in the candidates2 function. When filtering the possible solutions, you look for locations that are closer or equal as the current one (using dist x tg <= dist src tg). This means that you can create routes where your robot keeps jumping back and forth between two locations:

(1, 2) -> (2, 1) -> (1, 2) -> (2, 1) -> ...

You can fix this by changing the condition to just less than <. When debugging the code, I also made a couple of changes that make it more readable:

let candidates2 ((x, y): pos) (tg: pos) : pos list =
 [1,0; -1,0; 0,1; 0,-1; 1,1; 1,-1; -1,1; -1,-1]
 |> List.map (fun (dx, dy) -> (x+dx, y+dy))
 |> List.filter (fun pos -> dist pos tg <= dist (x, y) tg)

let rec routes2 (src: pos) (tg: pos) : pos list list =  
  if src = tg then [[tg]] 
  else  
    candidates2 src tg
    |> List.map (fun j -> List.map (fun i -> src :: i) (routes2 j tg))
    |> List.concat

Upvotes: 2

Related Questions