user7201762 - 7 months ago 50

Java Question

I am solving the Baby Blocks problem. I have a peice of java code that I want to translate to Haskell:

Java:

`for (int i = 1; i <optHeight.length ; i++) {`

int maxHeightIndex = 0;

for (int j = i-1; j >=0 ; j--) {

// Need help from here

if(boxes[j].width>boxes[i-1].width && boxes[j].depth>boxes[i-1].depth) {

if(optHeight[maxHeightIndex]<optHeight[j+1]) { <-- How do I write this condition

maxHeightIndex = j+1;

}

}

}

optHeight[i]=optHeight[maxHeightIndex] + boxes[i-1].height;

}

where

`optHeight`

`boxes`

`height, width, depth`

Haskell:

`b list = do`

forM_ [1..length list] $ \i -> do

let maxHeight = 0

forM_ [0..(i-1)] $ \j -> do

if list!!j!!1 > list!!i-1!!1 && list!!j!!2 > list !!j!!2 then

maxHeight = j + 1

PS: I am totally a beginner in Haskell

Answer

The way to solve this problem (I think), is to consider every rotation of every box (so you have `3n`

total rotations). Then, you order these based on increasing size of their base. The problem then is just to pick the longest subsequence of boxes that "fit" with each other (you don't need to worry about picking the same box twice because a box could never fit on itself). This sounds a lot like the canonical longest increasing subsequence problem, which suggests we will want a dynamic programming solution. We will have an array of length `3n+1`

where the ith element represents the maximum height of the stack you can make with the ith box at the top.

```
maxHeight(i) = { height(i) + max[ maxHeight(j) ] such that
width(j) > width(i), depth(j) > depth(i), 0 <= j < i }
```

Now, lets get started on the Haskell solution. I will assume your input is a list of the dimensions. Notice how closely the code mirrors the solution I described - the trick is to write things declaratively.

```
import Data.List (sortOn)
import Data.Vector (fromList, (!), generate)
import Data.Ord (Down(..))
babyBlocks :: [(Int,Int,Int)] -> Int
babyBlocks blocks = maxHeights ! (3*n - 1)
where
-- get the number of blocks
n = length blocks
-- generate the `3n` blocks formed by rotating the existing blocks,
-- sort them by their base size, and store them in a vector for
-- fast retrieval
sortedBlocks = fromList
. sortOn (\(x,y,z) -> Down (x*y))
. concatMap (\(x,y,z) -> [(x,y,z),(y,z,x),(z,x,y)])
$ blocks
-- we'll make ourselves a couple helper functions, just so
-- our translation of the recurrence relation looks better
height n = let (_,_,z) = sortedBlocks ! n in z
width n = let (_,y,_) = sortedBlocks ! n in y
depth n = let (x,_,_) = sortedBlocks ! n in x
maxHeight n = maxHeights ! n
-- state the dynamic programming
maxHeights = generate (3*n)
(\i -> height i +
maximum ([ maxHeight j | j<-[0..(i-1)]
, width j > width i
, depth j > depth i ]
++ [0]))
```

The part you seemed to be having trouble with is the dynamic programming in the last part. Because Haskell is lazy, it is actually completely OK for me to use `maxHeight`

while defining `maxHeights`

, even if I don't know what order my vector is going to be initialized in!

Source (Stackoverflow)