모든 가능한 세계 구성 인쇄

Question

그냥 하스켈에서 시작!

우리는 사각형, 인쇄 가능한 모든 세계의 구성 N이 :

이

• (1) 각 사각형은 "P"를 가질 수는 다음과 같이 연습으로, 내가 구현하기 위해 노력하고있어 현재의 문제는 (피트) 여부 (2^n 가능성).
• (2) n 개의 모든 제곱 (n + 1 개의 가능성)에 최대 하나의 "W"(Wumpus)가있을 수 있습니다.

두 개의 사각형을 두 개의 문자열로 표시하면 여기에 n = 2에 대한 출력 예가 나와 있습니다. 우리는 (2^n) · (n + 1) = (2^2) · (2 ​​+ 1) = 12 구성을가집니다.

[[" W"," "],[" "," W"],[" "," "], 
[" W","P"],[" ","PW"],[" ","P"], 
["PW"," "],["P"," W"],["P"," "], 
["PW","P"],["P","PW"],["P","P"]] 

조건 (1)은 쉽게 구현됩니다.

p 0 = [[]] 
p n = [x:xs | x <- [" ","P"], xs <- p (n-1)] 

또는

p n = mapM (\x -> [" ","P"]) [1..n] 

또는

p n = replicateM n [" ","P"] 

나는, 아직 마지막 두를 이해하는 주장 할 수 있지만 여기에 그들은 : 둘러보고, 나는 그것을 표현하는 몇 가지 방법을 발견했습니다 완전을 기하기위한 것이다.

질문 : 어떻게 조건 (2)을 추가 할 수 있습니까? 목록 이해로 끝낼 수 있습니까? 내 그리-좋은 찾고 초보자 솔루션은 이러한 기능을 포함 :

insertw :: Int -> [String] -> [String] 
insertw n xs 
    | n < 0  = xs 
    | n >= lgth = xs 
    | otherwise = (take (n) xs) ++ [xs!!n++"W"] ++ (drop (n+1) xs) 
    where lgth = length xs 

duplicate :: Int -> [String] -> [[String]] 
duplicate i squares 
    | i > lgth = [] 
    | otherwise = (insertw i squares) : duplicate (i+1) squares 
    where lgth = length squares 

worlds :: Int -> [[String]] 
worlds n = concat . map (duplicate 0) . p $ n 

Answer 1

나에게 분명해 보인다. :). 목록 이해에서 나중에 목록은 이전 목록에서 생성 된 값에 따라 달라질 수 있습니다. 두 번째 함수는 wumpus를 추가 할 때 첫 번째 함수를 호출하여 집합을 생성합니다.

p 0 = [[]] 
p n = [[x,' ']:xs | x <- [' ','P'], xs <- p (n-1)] 

pw 0 = [[]] 
pw n = [[x,w]:xs | w <- [' ','W'], x <- [' ','P'], xs <- if w == 'W' then p (n-1) else pw (n-1)] 

가능한 한 깨끗하지는 않지만 목록 내재는 항상 문제에 대한 우아함을 제공합니다. 그럴만 한 가치가있어.

Answer 2

조건 2는 지능형리스트에 대한 명백한 후보가 아니라 이미 작성한 작업 코드가 정리 될 수있다.

duplicate에서 lgth에 0에서 반복은 map 대신 명시 적으로 재귀 수행 할 수 있습니다 :

duplicate squares = map (\i -> insertw i squares) [0 .. length squares] 

duplicate 더 이상 인덱스 매개 변수를 사용하고, concat . map 같은 concatMap과 같습니다

worlds = concatMap duplicate . p 

drop과 take을 모두 입력하면 splitAt 종종 더 나은 작업입니다. 우리가 너무 length xs 및 xs !! n 작업을 제거있어

insertw n xs = 
    case splitAt n xs of 
     (as, []) -> as 
     (as, b : bs) -> as ++ ((b ++ "W") : bs) 

참고.

연습으로 다른 duplicate 기능은 및 tailssquares 목록을 통해 압축하여 작성할 수 있습니다.