JavaコードをHaskellに翻訳する

Question

私はBaby Blocksの問題を解決しています。

のJava：

optHeightは、1次元配列であると boxesはデータメンバとして height, width, depthのオブジェクトconsitingある

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; 
} 

私はHaskellのに変換するJavaコードのpeiceを持っています。ハスケルでは、それは単なるリストのリストです。可変配列/変数がないため、私は全く無力です。

ハスケル：

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：私は完全にHaskellの

Answer 1

で初心者（と思う）。この問題を解決する方法です、すべてのボックスのすべての回転を考慮することである（あなたが3nを持っています合計回転数）。次に、ベースのサイズの増加に基づいてこれらを注文します。問題は、お互いに「フィット」するボックスのうち最も長いサブシーケンスを選択することです（同じボックスを2回選ぶことを心配する必要はありません。これは標準的なlongest increasing subsequenceの問題とよく似ています。これは、動的プログラミングソリューションが必要であることを示唆しています。長さが3nの配列があります。ここで、i番目の要素は、i番目のボックスの上にあるスタックの最大高さを表します。

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

ここで、Haskellソリューションを開始しましょう。私はあなたの入力が寸法のリストであると仮定します。コードが私が説明したソリューションをどれくらい密接に反映しているかに注目してください。そのトリックは物事を宣言的に書くことです。

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 (0 : [ maxHeight j | j<-[0..(i-1)] 
                 , width j > width i 
                 , depth j > depth i ])) 

あなたはとのトラブルを持っているように見えた部分は、最後の部分で動的計画です。 Haskellは怠惰なので、実際にはmaxHeightを使用してmaxHeightsを定義すると、私のベクトルがどのような順序で初期化されるのかわからなくても、完全にOKです！

Answer 2

この問題は、全体的な解決策を見つけるための非常に単純な関数を作成することによって、非常に読みやすい方法で解決できます。可能な戦略は次のとおりです。

1. すべてのブロックを取り出し、初期のタワーセットとして宣言します。
2. 各タワーを使用可能なブロック（可能な場合）と結合します。これにより、新しいタワーセットが作成されます。
3. ステップ2を繰り返して、一連のタワーがもう変更されなくなるまで繰り返します。
4. 最も高いセットのタワーを抽出します。

   type Block = (Int,Int,Int) 
   type Tower = [Block] 
   
   babyBlocks :: [Block] -> Int 
   babyBlocks blocks = highest $ converge allBlocks initialTowers 
       where allBlocks = possibleBlocks blocks 
         initialTowers = map (:[]) allBlocks 
   
   possibleBlocks :: [Block] -> [Block] 
   possibleBlocks = concatMap (\(w,d,h) -> [(w,d,h),(w,h,d),(d,h,w)]) 
   
   canStack :: Block -> Block -> Bool 
   canStack (w1,d1,_) (w2,d2,_) = w2 < w1 && d2 < d1 || w2 < d1 && d2 < w1 
   
   expand :: Tower -> [Block] -> [Tower] 
   expand tower@(top:_) = map (:tower) . filter (canStack top) 
   
   converge :: [Block] -> [Tower] -> [Tower] 
   converge blocks towers | null newTowers = towers 
            | otherwise = converge blocks newTowers 
       where newTowers = concatMap (flip expand blocks) towers 
   
   height :: Tower -> Int 
   height = sum . map (\(_,_,h) -> h) 
   
   highest :: [Tower] -> Int 
   highest = maximum . map height 
   

   • babyBlocks：この関数は、（それらを回転させることによって）指定されたブロックタイプのためのすべての可能なブロックを生成し、初期に変換する（以下説明）以下のように対応するコードである

（1つの要素で単純なリストにラップして）タワーセットを作成し、最初のタワーセットのコンバージェンスを最終タワーセットに開始します。

possibleBlocks：与えられたブロックタイプのセットに対して、この関数はすべてのブロックを回転させて返します。厳密には、3! = 6の回転（3つの座標のすべての順列）があるはずですが、スワップされた幅と深さの回転を重複として扱うことができるため、それらの半分を考慮する必要があります。

canStack：あるブロックを別のブロックに配置できるかどうかを確認します。

expand：タワーの場合、タワーの上部に置くことができれば、使用可能なすべてのブロックがチェックされます。上に置くことができる互換性のあるブロックごとに新しいタワーが作成されます。

converge：この機能は、タイルのセットに対して本質的にexpandを繰り返して、そのうちの1つにブロックを追加できなくなるまで繰り返す。解決策は残りのタワーの最大高さでなければなりません。

height：ブロックタワーの高さを合計して、タワーの高さを返します。

highest：所定のタワーセットについて、最大高さを識別します。