며칠전 '별다방손코딩'을 다른 이들에게 소개하며 같이 풀어본 문제다. 쉬워보여서.. https://www.hackerrank.com/challenges/manasa-and-stones
0에서 시작하여 (a 혹은 b)를 (n-1)번 더했을 때 나올 수 있는 값을 모두 찾으라는 것인데, 문제 자체는 매우 간단해서 a만 (n-1)번 더한 것과 b만 (n-1)번 더한 것을 n개의 등차수열로 만들면 된다.
하지만 문제가 말하는 바 그대로를 살펴보면 non-deterministic calculation이다. 즉 0에 x를 n번 더한 결과는? 당연히 x*n이지만.. x가 (a 혹은 b)라면 그 결과가 어느 한 값이 아니라 위처럼 여러 가능한 값을 가진다. 심지어 n이 (c 혹은 d)라면? x가 세 값 중 어느 값이라면? .. 더하기 뿐 아니라 연산이 더 복잡하다면?
Haskell에서는 non-deterministic value를 List로 표현하였을 때 (+) 연산을 lifting해주는 것만으로 쉽게 답을 구할 수 있다.
iterate (+ x) 0 == [0, x, 2*x, 3*x, ...] -- 0에 '더하기 x'를 반복 적용하는 것이다.
[a,b,c] !! 2 == c -- (!!)는 index 연산자다.
iterate (+ x) 0 !! (n-1) -- 0에 x를 n-1번 더한 값을 얻을 수 있다.
(+)는 Num -> Num -> Num 이지만, x 가 [1,2] 가 된다면 바로 적용할 수 없으므로 lift해줘야 한다.
iterate (liftA2 (+) x) [0] !! (n-1)
여기엔 중복된 값이 있으므로 마지막에 nub(유일 값만 추출하기)을 적용하면 된다.
lastStone n a b = nub $ iterate(liftA2 (+) [a,b]) [0] !! (n-1)
0에서 시작하여 (a 혹은 b)를 (n-1)번 더했을 때 나올 수 있는 값을 모두 찾으라는 것인데, 문제 자체는 매우 간단해서 a만 (n-1)번 더한 것과 b만 (n-1)번 더한 것을 n개의 등차수열로 만들면 된다.
하지만 문제가 말하는 바 그대로를 살펴보면 non-deterministic calculation이다. 즉 0에 x를 n번 더한 결과는? 당연히 x*n이지만.. x가 (a 혹은 b)라면 그 결과가 어느 한 값이 아니라 위처럼 여러 가능한 값을 가진다. 심지어 n이 (c 혹은 d)라면? x가 세 값 중 어느 값이라면? .. 더하기 뿐 아니라 연산이 더 복잡하다면?
Haskell에서는 non-deterministic value를 List로 표현하였을 때 (+) 연산을 lifting해주는 것만으로 쉽게 답을 구할 수 있다.
iterate (+ x) 0 == [0, x, 2*x, 3*x, ...] -- 0에 '더하기 x'를 반복 적용하는 것이다.
[a,b,c] !! 2 == c -- (!!)는 index 연산자다.
iterate (+ x) 0 !! (n-1) -- 0에 x를 n-1번 더한 값을 얻을 수 있다.
(+)는 Num -> Num -> Num 이지만, x 가 [1,2] 가 된다면 바로 적용할 수 없으므로 lift해줘야 한다.
iterate (liftA2 (+) x) [0] !! (n-1)
여기엔 중복된 값이 있으므로 마지막에 nub(유일 값만 추출하기)을 적용하면 된다.
lastStone n a b = nub $ iterate(liftA2 (+) [a,b]) [0] !! (n-1)
