user7201762 user7201762 - 9 days ago 6
Java Question

Translating a piece of Java code to Haskell

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
is a 1-D array and
boxes
is an object consiting of
height, width, depth
as data members. In Haskell, it is just a list of list. Due to lack of mutable arrays / variables, I am totally helpless.

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!