4

Using the list zipper, for example, one is able to walk through a unidimensional space. Is there any similarly elegant and efficient way to encode the notion of walking (with no pattern) through a bidimensional grid?

MaiaVictor
  • 51,090
  • 44
  • 144
  • 286
  • 1
    Do you mean like a 2-dimensional grid? Related SO discussion: http://stackoverflow.com/questions/8905030/two-dimensional-zipper – ErikR Oct 18 '15 at 00:26
  • 1
    OK, I understand one can not build a bidimensional zipper as defined. But does that mean it is simply impossible to efficiently walk through a 2d grid? I find that hard to believe... – MaiaVictor Oct 18 '15 at 00:32
  • 1
    @Viclib Actually, I don't think anybody is claiming it's impossible. As far as I know, it's an open question whether it's possible. – Daniel Wagner Oct 18 '15 at 02:13
  • 1
    Suppose you have a completely filled quadtree with a specific depth. That forms a grid. Isn't it possible to walk from any tile to any neighbor in amortized constant time? – MaiaVictor Oct 18 '15 at 03:19
  • 3
    Quick googling gave me [this](http://pastebin.com/f55d96074). tl;dr though. – effectfully Oct 18 '15 at 04:35
  • How sparsely is this grid populated? Would you be better off using grid coordintes as keys in a map of some sort? – Paul Johnson Oct 18 '15 at 10:52
  • 1
    I think so, maybe. It is densely packed as it is a map for a game. – MaiaVictor Oct 18 '15 at 10:54
  • 2
    To "Isn't it possible to walk from any tile to any neighbor in amortized constant time?": In log time, not constant time, since you could walk back and forth between two tiles which require going up and down several levels. – gelisam Oct 18 '15 at 11:06
  • 1
    Key question: are the map data fixed up front, or do they mutate over the course of execution. Laziness makes it easy (if you know how) to cook up read-only graph structures with constant-time navigation. But mutating structures with more than tree-like pointer inconnection is inevitably a bad show for purely functional programming. – pigworker Oct 18 '15 at 12:01
  • Gelisam but sometimes it takes just two movements. Roughly 50% of the tiles take 2 movements to to a neighbor. 25% take 4. And so on. It is very rare for it to take log(n). Isn't the average constant? – MaiaVictor Oct 18 '15 at 13:26
  • 2
    But it's fixed *which* cells have higher costs, so a pathologic series of moves can force you to pay log(n) all the time. It's only amortized constant if you make assumptions about the moves you'll have to do that forbids the pathological cases. – Ben Oct 18 '15 at 20:37
  • @Viclib I'd also like to try to make a simple 2D game (~ HOMM3) with dynamic maps, using immutable/functional structures if possible. Have you found an answer? – sam boosalis Jun 27 '16 at 22:46
  • Nothing really satisfactory, @samboosalis. – MaiaVictor Jun 28 '16 at 11:55

1 Answers1

6

The real question is, what do you want to walk through a 2D grid to do?

Is it random access, or some pattern? Dynamic programming problems are often modeled as traversing a 2D grid, but it's not random access, it's quite patterned. And patterns we can work with.

For example, consider the problem finding the edit distance between two strings, where we're given:

-- the cost of replacing one character with another
charEditCost :: Char -> Char -> Int

-- the cost of inserting a character
charInsertCost :: Char -> Int

We can give the following recurrence for determining the edit distance between two strings:

editDistance [] [] = 0
editDistance (a:as) [] = editDistance as [] + charInsertCost a
editDistance [] (b:bs) = editDistance [] bs + charInsertCost b
editDistance (a:as) (b:bs) = minimum
  [ editDistance as bs + charEditCost a b
  , editDistance (a:as) bs + charInsertCost b
  , editDistance as (b:bs) + charInsertCost a
  ]

But that's really inefficient - note how in the fourth equation, editDistance as bs would be calculated three times - once directly, once by editDistance (a:as) bs, and once by editDistance as (b:bs).

The dynamic programming technique tells us to introduce the two-dimensional grid to cache results:

editDistance as bs = last . last $ grid where 
  firstRow j = grid !! 0 !! (j-1) + charInsertCost (as!!j)
  firstCol i = grid !! (i-1) !! 0 + charInsertCost (bs!!i)
  innerCel i j = minimum
    [ grid !! (i-1) !! (j-1) + charEditCost (as!!j) (bs!!i)
    , grid !! i !! (j-1) + charInsertCost (as!!j)
    , grid !! (i-1) !! j + charInsertCost (bs!!j)
    ]
  grid = (          0 : [ firstRow j   | j <- [1..length as] ] ) : 
       [ ( firstCol i : [ innerCel i j | j <- [1..length as] ] ) | i <- [1..length bs ]

This still gives horrible asymptotics since !! is O(n). But we can improve on this by noting we don't need random access; we know exactly which cells we need to compute each cell of the grid. So all we need to do is provide those cells when needed.

So much like the classic fibs = 1 : 1 : zipWith (+) fibs (tail fibs) provides fibs!!(i-1) and fibs!!(i-2) just in time to calculate fibs!!i, we can do the same here.

editDistance as bs = last . last $ grid where
  firstRow = scanl (+) 0 $ map charInsertCost as
  firstCol = scanl (+) 0 $ map charInsertCost bs
  grid = ( 0 : firstRow ) : zipWith3 mkRow bs firstCol grid
  mkRow b firstCel lastRow = let thisRow = firstCel : zipWith4 (mkCel b) as thisRow lastRow (tail lastRow) in thisRow
  mkCel b a leftCel aboveLeftCel aboveCel = minimum
    [ aboveLeftCel + charEditCost b a
    , aboveCel + charInsertCost b
    , leftCel + charInsertCost a
    ]

Not every problem on a 2D grid is amenable to this kind of knot-tying, but it does work for some.

rampion
  • 87,131
  • 49
  • 199
  • 315
  • 1
    The pattern is random because the problem is implementing a map for a game where creatures will walk through... – MaiaVictor Oct 18 '15 at 03:08