Geek asks and answers

List Recursion - Haskell

I am trying to write a recursive function that takes a list containing a list of integers as input and returns a tuple of type ([Int], Int). ([Int], Int)

This is for a “board game” where you come with a board:

 [[5,4,3,8,6],
  [0,2,1,0,7],
  [0,1,9,4,3],
  [2,3,4,0,9]]

It will be a board with 4 rows and 5 columns. The numbers inside the list are "coin values." The goal of this board game would be to move from the top of the list to the bottom of the coin collection. You can start in any position from the top row and move down, you can go straight down or diagonally to the left or right. You will need a path that will give you the greatest overall coin values.

I created the first function in which you enter the list of paths [([Int], Int)] and returns the path ([Int], Int) with the maximum value of the coin.

Now I need to create a function to actually create a list of paths that I will enter in the first function.

I know that I will have to use recursion. I will introduce the board (as above) and the start column. I will need to take the column number and then create a list of all possible paths. If I start with the column number, my next possible steps are the positions (in the next row) - the same column number, column num -1 and column num +1. I would have to call it recursively until I get to the bottom.

How can I save these path steps while I go and then save the final list of all possible paths?

([Int], Int) - [Int] is the position in the list / columns or rows, and Int is the value of the coin.

I am new to haskell, and although I understand what I need to do, it is very difficult to write code.

+5
3

, () . . (pat index_combinations)

* > : "new1.hs"
[1 1] Main (new1.hs, )
, : .
* >
([8,7,4,9], 28)
* >
[3,4,3,4]

import Data.List
import Data.Ord
import Data.Maybe

r = [[5,4,3,8,6],
     [0,2,1,0,7],
     [0,1,9,4,3],
     [2,3,4,0,9]]

r1 = r !! 0
r2 = r !! 1
r3 = r !! 2
r4 = r !! 3

index_combinations = 
  [[a,b,c,d] | a <- [0..4], b <- [max 0 (a-1)..min 4 (a+1)], 
   c <- [max 0 (b-1)..min 4 (b+1)], d <- [max 0 (c-1)..min 4 (c+1)]]  

mapR xs = [r1 !! (xs !! 0), r2 !! (xs !! 1), 
           r3 !! (xs !! 2), r4 !! (xs !! 3)]

r_combinations = map mapR index_combinations
r_combinations_summed = zip r_combinations $ map (foldr (+) 0) r_combinations

result = maximumBy (comparing snd) r_combinations_summed
path = index_combinations !! fromJust (elemIndex result r_combinations_summed)
0

grid (userguide) , , . ( , .)

4 5 .

λ> :m + Math.Geometry.Grid
λ> let g = rectSquareGrid 4 5
λ> indices g
[(0,0),(0,1),(0,2),(0,3),(1,0),(1,1),(1,2),(1,3),(2,0),(2,1),(2,2),(2,3),(3,0),(3,1),(3,2),(3,3),(4,0),(4,1),(4,2),(4,3)]

" " , GridMap.

λ> :m + Math.Geometry.GridMap
λ> let m = lazyGridMap g [5,4,3,8,6,0,2,1,0,7,0,1,9,4,3,2,3,4,0,9]
λ> m
lazyGridMap (rectSquareGrid 4 5) [5,4,3,8,6,0,2,1,0,7,0,1,9,4,3,2,3,4,0,9]
λ> toList m
[((0,0),5),((0,1),4),((0,2),3),((0,3),8),((1,0),6),((1,1),0),((1,2),2),((1,3),1),((2,0),0),((2,1),7),((2,2),0),((2,3),1),((3,0),9),((3,1),4),((3,2),3),((3,3),2),((4,0),3),((4,1),4),((4,2),0),((4,3),9)]

, : RectSquareGrid .

λ> neighbours (1,2) m
[(0,2),(1,3),(2,2),(1,1)]

Grid, . , :

λ> let neighbours2 (x, y) g = filter (`inGrid` g) [(x-1,y-1), (x-1,y), (x-1,y+1), (x,y-1), (x,y+1), (x+1,y-1), (x+1,y), (x+1,y+1)]
λ> neighbours2 (1,2) m
[(0,1),(0,2),(0,3),(1,1),(1,3),(2,1),(2,2),(2,3)]

, , :

λ> let allowedMoves (x, y) g = filter (`inGrid` g) [(x+1,y-1), (x+1,y), (x+1,y+1)]
λ> allowedMoves (1,2) m
[(2,1),(2,2),(2,3)]

, , .

allPathsFrom a g | fst a == fst (size g) = [[a]]
                 | otherwise             = Prelude.map (a:) xs
  where xs = concatMap (\x -> allPathsFrom x g) ys
        ys = allowedMoves a g

:

λ> allPathsFrom (0,1) m
[[(0,1),(1,0),(2,0),(3,0),(4,0)],[(0,1),(1,0),(2,0),(3,0),(4,1)],[(0,1),(1,0),(2,0),(3,1),(4,0)],[(0,1),(1,0),(2,0),(3,1),(4,1)],[(0,1),(1,0),(2,0),(3,1),(4,2)],[(0,1),(1,0),(2,1),(3,0),(4,0)],[(0,1),(1,0),(2,1),(3,0),(4,1)],[(0,1),(1,0),(2,1),(3,1),(4,0)],[(0,1),(1,0),(2,1),(3,1),(4,1)],[(0,1),(1,0),(2,1),(3,1),(4,2)],[(0,1),(1,0),(2,1),(3,2),(4,1)],[(0,1),(1,0),(2,1),(3,2),(4,2)],[(0,1),(1,0),(2,1),(3,2),(4,3)],[(0,1),(1,1),(2,0),(3,0),(4,0)],[(0,1),(1,1),(2,0),(3,0),(4,1)],[(0,1),(1,1),(2,0),(3,1),(4,0)],[(0,1),(1,1),(2,0),(3,1),(4,1)],[(0,1),(1,1),(2,0),(3,1),(4,2)],[(0,1),(1,1),(2,1),(3,0),(4,0)],[(0,1),(1,1),(2,1),(3,0),(4,1)],[(0,1),(1,1),(2,1),(3,1),(4,0)],[(0,1),(1,1),(2,1),(3,1),(4,1)],[(0,1),(1,1),(2,1),(3,1),(4,2)],[(0,1),(1,1),(2,1),(3,2),(4,1)],[(0,1),(1,1),(2,1),(3,2),(4,2)],[(0,1),(1,1),(2,1),(3,2),(4,3)],[(0,1),(1,1),(2,2),(3,1),(4,0)],[(0,1),(1,1),(2,2),(3,1),(4,1)],[(0,1),(1,1),(2,2),(3,1),(4,2)],[(0,1),(1,1),(2,2),(3,2),(4,1)],[(0,1),(1,1),(2,2),(3,2),(4,2)],[(0,1),(1,1),(2,2),(3,2),(4,3)],[(0,1),(1,1),(2,2),(3,3),(4,2)],[(0,1),(1,1),(2,2),(3,3),(4,3)],[(0,1),(1,2),(2,1),(3,0),(4,0)],[(0,1),(1,2),(2,1),(3,0),(4,1)],[(0,1),(1,2),(2,1),(3,1),(4,0)],[(0,1),(1,2),(2,1),(3,1),(4,1)],[(0,1),(1,2),(2,1),(3,1),(4,2)],[(0,1),(1,2),(2,1),(3,2),(4,1)],[(0,1),(1,2),(2,1),(3,2),(4,2)],[(0,1),(1,2),(2,1),(3,2),(4,3)],[(0,1),(1,2),(2,2),(3,1),(4,0)],[(0,1),(1,2),(2,2),(3,1),(4,1)],[(0,1),(1,2),(2,2),(3,1),(4,2)],[(0,1),(1,2),(2,2),(3,2),(4,1)],[(0,1),(1,2),(2,2),(3,2),(4,2)],[(0,1),(1,2),(2,2),(3,2),(4,3)],[(0,1),(1,2),(2,2),(3,3),(4,2)],[(0,1),(1,2),(2,2),(3,3),(4,3)],[(0,1),(1,2),(2,3),(3,2),(4,1)],[(0,1),(1,2),(2,3),(3,2),(4,2)],[(0,1),(1,2),(2,3),(3,2),(4,3)],[(0,1),(1,2),(2,3),(3,3),(4,2)],[(0,1),(1,2),(2,3),(3,3),(4,3)]]

, GridMap Grid s, m g.

λ> allPathsFrom (0,1) m

(amy at nualeargais dot ie), , , Grid.

0

More articles:


All Articles