자바 코드를 하스켈로 번역하기

Question

Baby Blocks 문제를 해결 중입니다.

자바 :

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

optHeight는 1 차원 배열입니다

및 boxes는 데이터 멤버로 height, width, depth의 객체 consiting이다 나는 하스켈로 번역 할 자바 코드의 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 : 나는 하스켈

Answer 1

에서 완전히 초보자이 문제를 (내가 생각하는) 해결하는 길이 요, 모든 상자의 모든 회전 (그래서 당신은 3n을 고려하는 것입니다 총 회전). 그런 다음, 증가하는베이스의 크기에 따라 이들을 주문합니다. 그런 다음 문제는 서로 가장 잘 맞는 상자의 가장 긴 하위 시퀀스를 선택하는 것입니다. 상자가 자체적으로 적합하지 않을 수 있으므로 동일한 상자를 두 번 선택하는 것에 대해 걱정할 필요가 없습니다. 이것은 표준적인 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 } 

이제 하스켈 솔루션을 시작하십시오. 귀하의 의견은 크기의 목록이라고 가정합니다. 코드가 내가 설명한 솔루션을 얼마나 가깝게 반영하는지주의하십시오. 트릭은 선언적으로 항목을 작성하는 것입니다.

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 ])) 

당신에 문제가있는 것처럼 보였다 부분은 마지막 부분에서 동적 프로그래밍입니다. 하스켈은 게으르므로 maxHeight을 사용하는 동안 실제로 벡터가 초기화 될 순서가 무엇인지 알지 못하는 경우에도 maxHeights을 정의하는 것이 좋습니다.

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 : (아래에 설명) 다음

대응 코드는 타워를 (하나의 요소로 간단한 목록으로 묶음으로써) 초기 타워 세트의 수렴을 시작하여 최종 타워 세트로 만듭니다.

possibleBlocks : 주어진 블록 유형 집합에 대해이 함수는 가능한 모든 블록을 회전시켜 반환합니다. 엄밀히 말하자면, 3! = 6 회전 (3 개 좌표의 모든 순열)이 있어야하지만, 교체 된 너비와 깊이로 회전을 중복으로 처리 할 수 ​​있기 때문에 절반 만 고려하면됩니다.

canStack : 주어진 블록을 다른 블록에 배치 할 수 있는지 확인합니다.

expand : 주어진 타워의 경우 타워의 맨 위에 올릴 수있는 경우 사용 가능한 모든 블록을 확인합니다. 상단에 놓을 수있는 호환 가능한 블록마다 새 타워가 작성됩니다.

converge :이 기능은 본질적으로 타워 세트에 대해 expand을 반복하여 더 이상 블록을 둘 수 없을 때까지 반복합니다. 솔루션은 나머지 타워의 최대 높이 여야합니다.

height : 블록 높이를 합산하여 주어진 타워의 높이를 반환합니다.

highest : 주어진 타워 세트에 대해 최대 높이를 식별합니다.