Programming

원문은 Monaca: 스도쿠 규칙 검사 에서 가져왔습니다. 저는 한단계 건너서 rein 님의 Quiz: 스도쿠 규칙 검사 를 보고 알게 되었습니다.

스도쿠는 1~9까지 숫자가 겹치지 않게 채워 넣는 게임이다.

여기서는 규칙을 조금 단순하게 해서 한 열에 1~9까지 숫자가 빠짐없이 들어 있는지 검사하는 코드를 작성한다고 가정하자.

입력 값이 규칙에 맞으면 True, 틀리면 False를 출력한다.

입력
123456789
112345678
223456788
012345678
134445679

출력
True
False
False
False
False

이런 문제를 풀 수 있는 방법은 대략

1. 정렬 후 비교
2. 원소 카운팅 – 카운팅 소트(counting sort)에서 사용하는
3. set 같은 자료구조를 사용하는 방법

등이 있습니다.

아무래도 속도가 가장 빠른 방법은 카운팅 소트에서처럼 입력값을 쭉 읽어나가면서 1부터 9의 갯수를 세는 방법인데, 이 경우 길이가 9로 고정되어 있으므로 아무 카운트나 2가 되면 중간에 바로 False 를 리턴할 수 있습니다.

그 외에 파이썬의 경우 정렬 후 비교나 set() 으로 만든 후 비교해도 코드가 간단하게 한줄로 나옵니다.

이미 속도에 중점을 둔 방식이나 그 외에 방식들은 많은 분들이 좋은 코드를 올려주셔서 뭔가 다른 방법 없나 생각해보다가 원래 문제 의미를 그대로 풀어쓰는 형태로 Haskell 로 짜보기로 했습니다.

그렇게 해서 나온 하스켈 코드가 …

sudoku_check x = all (flip elem x) [1..9]

실행 결과 (ghci 사용¹)

Prelude> let sudoku_check x= all (flip elem x) [1..9]
Prelude> sudoku_check [1,2,3,4,5,6,7,8,9]
True
Prelude> sudoku_check [1,1,2,3,4,5,6,7,8]
False
…

입니다. 보시면 아시겠지만 1부터 9까지의 숫자가 모두 입력값에 있어야만 True 를 리턴하는 함수입니다.² 입력값을 여러번 읽으므로 물론 속도는 느리지만 문제의 의미를 그냥 코드로 옮겨적은 형태고 간단해 보여서 올립니다.

하지만 임의의 길이의 입력값들도 다 처리할 수 있는 일반적인 솔루션이기 때문에 입력값의 길이가 9로 제한되어 있다는 조건을 유용하게 사용하지 못한 점은 약간 아쉽네요.

1. ghci 에 바로 입력 시에는 앞에 “let ” 을 붙여줘야 합니다. [↩]
2. 중간에 flip 은 인자 순서 때문에 들어간 보조 함수고 의미 상은 all (elem’ x) [1..9] 와 같습니다. [↩]

개미 수열이란게 있습니다. 베르나르 베르베르의 소설 “개미” 에 나와서 유명해진 수열인데, 대략 아래와 같은 형태입니다.

1
11
12
1121
122111
112213
12221131
…

처음 보는 분들을 위해 간단히 설명하자면, 일단 수열의 처음은 “1” 로 시작합니다. 그리고 그 다음 원소부터는 이전 원소의 숫자들을 읽어서 만들어냅니다.

우선 첫 원소 “1” 은 1이 1개 있기 때문에 두번째 원소는 “11” (1이 1개) 가 됩니다.

그 다음 원소는 이전 원소가 “11” 이므로 “12” (1이 2개), 또 그 다음 원소는 “1121” (1이 1개, 2가 1개) 가 됩니다.

이와 같은 규칙으로 생성되는 수열인데, 문제가 간단해서 Haskell 이라는 함수형 언어(functional programming language)로 한번 작성해보았습니다.

module AntSeq
    where

ant_seq [] = []
ant_seq l@(x:xs) = let (xs1, xs2) = span ((==) x) l
                   in x : (length xs1) : ant_seq xs2

gen_seq n = take n $ iterate (ant_seq) [1]

--pretty print
pprint n = mapM_ print $ gen_seq n

위 하스켈 코드를 ant_seq.hs 파일로 저장한 다음 하스켈 인터프리터에서

:load ant_seq.hs

한 후 pprint 함수를 실행시키면 아래와 같이 출력됩니다.

*AntSeq> pprint 12
[1]
[1,1]
[1,2]
[1,1,2,1]
[1,2,2,1,1,1]
[1,1,2,2,1,3]
[1,2,2,2,1,1,3,1]
[1,1,2,3,1,2,3,1,1,1]
[1,2,2,1,3,1,1,1,2,1,3,1,1,3]
[1,1,2,2,1,1,3,1,1,3,2,1,1,1,3,1,1,2,3,1]
[1,2,2,2,1,2,3,1,1,2,3,1,2,1,1,3,3,1,1,2,2,1,3,1,1,1]
[1,1,2,3,1,1,2,1,3,1,1,2,2,1,3,1,1,1,2,1,1,2,3,2,1,2,2,2,1,1,3,1,1,3]

함수형 언어는 특정 타입의 문제들을 아주 깔끔하고 간단하게 구현하는 것이 가능합니다. 그러나 그런 몇가지 예제들을 가지고 함수형 언어가 마치 모든 문제의 가장 완전하고 빠른 해결책인 것처럼 오도하는 것은 분명 경계해야 할 것입니다.

이 예제는 함수형 언어의 특징을 효과적으로 보여주는 그런 전형적인 예제들과는 거리가 멀지만, 생각보다 코드가 간단하게 나와서 포스팅 해봤습니다.

간단한 문제이므로 각자 선호하는 언어로 구현해 보고 비교해보는 것도 재미있을 것 같습니다.