[📜일지] 코딩 재활을 위한 뻘짓...

[Ray.(choxu0826)]

[서론]

The Artisan of Glimmith이라는 퍼즐 게임을 아는가?

이런 타일에 존재하는 아이콘에 해당하는 조건을 만족하여 모든 타일을 칠하는 퍼즐 게임이다.

유튜브 쇼츠를 보던 과정에서 이 퍼즐 게임을 알게 되었고, 꽤 재밌어 보여서 이거 한번 알아봤더니, 모든 퍼즐이 유일해를 가지고, 모든 퍼즐은 추론이 필요 없다고 한다.

추론 필요 없음은 뭐 사람이 한다고 쳐도, 저 수많은 가짓수를 어떻게 확인하여 해가 유일함을 보장하는지 매우 궁금했음.

이걸 알아보니까, 이런 퍼즐 게임은 퍼즐과 동시에 솔버를 만들어서, 그걸 이용하여 푼다고 하더라고? 

그래서 나도 내가 잠깐 시간 때우려고 예전에 했었던 퍼즐 게임이 생각나길래, 오랜만에 코딩 재활 좀 할겸 솔버 하나 만들어 보기로 했음..

[문제]

이런 형태의 퍼즐을 크립토그램이라고 한다.

크립토그램은 '빈칸 아래의 문자가 같으면, 빈칸의 내용이 같다' 라는 조건으로, 단어를 알아내고 문장을 완성하는 형태의 퍼즐 게임이다..

다만 유일해를 보장 안할수도 있으니 (당연하게도, 수십만개가 넘어가는 영단어를 배열하면서 유일성 검증하기는 매우 까다롭다) 내 솔버 또한 유일해를 내놓기 보다는, 충분히 매칭되는 가장 빠른 결과를 우선 출력하고, 필요하면 다음 결과를 요청 및 확인할 수 있도록 만들었다.

예시로 올린 스샷에 해당하는 게임은, 중간 중간 자물쇠로 숫자를 알 수 없는 경우도 있고, 미리 문자가 숫자와 함께 배정된 경우도 있고, 이미 배정되어 다른데에 쓰이지 않는 문자도 있길래, 이거 전부 해결 할 수 있도록 코드를 짰음.

추가로, 매우 원시적인 형태의 솔버를 만들었기에, 문장이 완성되는가? 단어의 빈도를 고려하는가? 이런 거는 그냥 배제하기로 했음...

그런거 넣는 순간 장난감이 장난감이 아니게 되므로...

[단어 단위]

우선 문제를 해결하는 방법에 대해 생각해보자.

가장 쉽게 떠올릴 수 있는건.

"1~26의 모든 숫자에 무작위 알파벳을 넣어보고 모두 단어가 되는지 검증해보자"

인데, 미쳤습니까 휴면?

넣고 확인하는 작업 단위 하나를 10억분의 1초로 잡아도 약 4.03 * (10^19)초이고, 약 1조 2700억년이니

우주가 멸망해도 이건 못 풀거임. 이거로 풀었다? 그 운으로 로또를 하지 왜 그랬음...

위의 방법은 당연히 기각이다. 그렇다면 떠올릴 수 있는 다른 방법은?
단어를 하나 완성 해보고, 그 다음 단어를 완성해보고... 쭉 쭉 쭉 타고 내려가면서, 모든 단어가 만족스러운 수준으로 완성될 경우, 그걸 내보내는거다.

그런데, 이제 이 단어를 어떻게 완성할까? 여기서도 시도할 수 있는 것이 무작위 대입 이후, HashSet을 이용한 단어 검사인데, 이 방법또한 위의 미친 짓보다는 훨씬 낫지만 여전히 미친 짓이다.

그래서 필요한 것이 우리 Trie다.

Trie는 단어를 한글자씩 분해하여 넣는 검색 구조로, 사전식 검색에 최적화 되어있는 구조이다.

Trie를 사용하여 현재 단어 완성본을 기준으로 하위 노드만 탐색하는 구조이기 때문에, 아무리 최악의 상황을 가정한다고 하더라도 반드시 사전에 저장된 단어의 개수 내에서 끝장을 볼 수 있다.

즉 5글자 기준 사전에 10000단어가 있다면 26^5 -> 10000으로 탐색 공간을 획기적으로 줄이는 것이 가능하다는 의미.

어쩌피 방법상 prefix 검색을 위주로 할 것이기에 그냥 이놈의 단점이 없다.

또한 위와 같이 Trie도 그냥 쓰기보다는, 단어 길이 별로 다른 Trie를 배정하는 방식으로, 5글자 단어 탐색 과정에서 8글자 단어가 끼어들어 탐색 공간의 크기를 키우는 일이 발생하지 않도록 만들어주었음.

이제 탐색을 위한 자료구조를 정했으니, 탐색하는 절차를 생각해보자.

어떤 암호문 '1 2 3 3 4' 가 있다고 하자, 사람은 'apple', 'allow' 뭐 이런 단어가 금방 금방 떠오를 수도 있겠지만, 우리 멍청한 컴퓨터는 그런 거 할 줄 모른다.

즉, 트라이의 루트 노드에서 그냥 하나 하나 찾아보면서 완성 가능한지 판단해야 함. 완성이 안되면? 뭐 어쩔 수 있나 되돌아가야지.

그럴 때 쓰는 방법이 백트래킹이다.

DFS를 기반으로 진행하다가 안될거같아? 되돌아가. 또 안돼? 되돌아가. 돼? 진행 시켜.

이런 방식이다. 그리고 이제 해결에 그 짝꿍인 재귀함수를 대령하면 된다.

깔끔한 코드를 짜기 귀찮아 좀 난잡하므로, 그냥 대충 케이스를 나누고, 아래의 케이스에 따라 다음 단계로 재귀시키는 방식을 사용했다는 것만 대충 알면 된다.

_Storage는 그냥 암호 숫자를 인덱스로 가지는 알파벳 보관소라고 생각하면 된다. 그냥 인지하기 편하려고 길이 27 배열로 만들고 0을 배제함.

ex. (1 2 2 3 4) = (a p p l e) 일 때, _Storage[2] = p;

1. '숫자' -> Trie 기준 가능 목록에서 다음 거 하나 가져와서 임시 배정 후 재귀, 재귀 복귀 이후 복원.

2. '알파벳 = 숫자' -> _Storage에 넣는 작업은 여기서 안하고 상단에서 끝냈으므로, 그냥 영어 떼서 다음 노드에 있으면 재귀.

3. '알파벳' -> 다음 노드에 있으면  재귀

4. '?(상단의 자물쇠)' -> 다음 가능 노드 전부 순차적으로 박아보며 재귀.

또한, 각 단위에서 종료 조건 -> 반환 내용은

1. 최대 길이 도달 -> true

2. 전부 탐색했는데 실패 -> false

로 만들어졌다.

IEnumerable<T> 같은 경우는, 메모리도 메모리고, 결과를 중간에 지나치면 안되므로 멈춰주는 용도.

이제, 단어를 완성하는 방법에 대해서는 어느정도 완성이 되었다. 그렇다면 이제 무엇을 해야하는가?

단어 하나에 대해 완성 되었으니, 이걸 기반으로 '모든 단어'가 완성 될 수 있는지 검증해야한다.

[문장 단위]

이제 문장 단위로 생각해보자. 어떤 단어가 완성 되었으면, 그 단어에 할당된 숫자는 모두 일단 해결되었다고 생각하는 것이 타당할 것이다.

'I ate apple yesterday' 라는 문장을 생각해보자. 이걸 암호로 치환하면 대충 '21 / 20 8 25 / 20 10 10 17 25 / 19 25 11 8 25 7 24 20 19'

이런 형태가 될 것이고, 여기서 20 8 25를 라는 결과를 ate로 만들었으면, 당연히 다른 단어들에서도 20 8 25는 각각 a t e인거다.

그렇다면 apple이나 yesterday에 존재하는 e와 a, t는 사실상 확정된 상태이므로, 단어 완성에 있어서 훨씬 수월해질 것이다.

그렇다면 어떤 단어가 완성되었을 때, 그 단어에 포함되는 숫자는 다음 단어에 영향을 미친다는 의미이므로, 제약 조건을 전파하는 셈이다.

이 효과를 극대화하기 위하여 간단히 사용할 수 있는 아이디어를 적용한 코드를 작성하였다.

코드를 읽기 싫은 사람들을 위해 간단한 설명을 들어가자면,

1. totalSplit이라는 문장을 미리 단어 단위로 분해한 컬렉션을 준비한다.

2. totalSplit을 한번 순회하여, 가장 추론해야 할 빈칸이 적은 것을 sortedSplit에 넣는다.

3. sortedSplit에 포함된 '숫자'는 확정된 것으로 간주하고, totalSplit에서 해당 단어를 제거한다.

4. 해당 확정 때문에, 새로운 제약이 생겼으므로 이를 이용하여 totalSplit을 다시 순회해가며 확인한다.

5. 위의 과정을 반복하면, 최종적으로 totalSplit이 비게 되고, sortedSplit은 제약 갱신에 의해 추론이 최소화 된 상태로 정렬된다.

더 빠르게 하기 위해서는 빈출단어 같은거 사용해야겠지만, [문제]에서 적어놨듯이 패스...

이제 이 정렬된 단어 나열을 기반으로 각 단어를 완성해 나가면서, 문장 만들기를 시도하면 된다. 실패하면? 되돌아간다.

그렇다 또 백트래킹과 재귀가 등장한다.

각 생성된 단어와 암호표를 기반으로, SolveSentence의 재귀 단계를 늘려가며 동작하는 재귀 함수이고,

종료 조건은 문장의 단어 수와 재귀 단계가 일치, 즉 모두 찾았을 때가 된다.

빨간 네모 칸에 든 함수는 그냥 고유명사를 위한 조건 완화로, 단어 하나 정도 못 찾은 것 정도는 관대하게 넘어가라는 의미이다. 즉 결과적으로 문장에서 단어를 모두 찾거나 한두개 정도 못 찾은 가장 빠른 결과를 얻을 수 있는 함수가 완성되었다. 맘에 안 들면? 다음 것도 찾아 볼 수 있다.

[테스트]

우리 지피티놈한테, 문장 하나를 요청했다.

이걸 암호로 만들면

12 9 2 22 13 / 3 9 13 / 11 16 2 18 / 12 16 23 / 24 16 22 22 2 18 25 / 4 19 3 23 2 1 13 / 23 5 9 4 26 13 18 9 16 19 13 11 / 8 19 2 13 3 22 10 / 22 13 24 3 / 9 2 23 / 4 22 1 / 21 16 25 / 4 18 / 3 9 13 / 6 2 3 5 9 13 18 / 5 9 16 2 11 / 4 26 13 18 13 1 / 3 9 13 / 12 2 18 1 4 12 / 15 16 1 13 / 23 4 15 13 / 3 13 16 / 16 18 1 / 12 16 3 5 9 13 1 / 16 / 23 15 16 22 22 / 1 4 25 / 23 22 13 13 26 / 21 13 23 2 1 13 / 3 9 13 / 12 16 11 15 / 22 2 25 9 3

가 되고,

이걸 솔버에 넣고 냅다 돌려보면?

약 2분 15초의 대장정을 걸쳐 정확한 결과를 만들어주는 것을 확인 가능하다.

이 방식의 특성 상 굉장히 재밌는 아이러니가 있는데, 문장이 길수록 더 잘 풀린다는 거다..

제약조건이 존나 많아지니까, 브랜치가 거의 안 생기기 때문.

이게 암호학에서 말하는 단순 치환 암호의 문제점이기도 하다. 제약이 많아지다 보니, 너무 정직하게 케이스가 딱 튀어나와버린다는것이니..

아무튼 퍼즐 게임 관련해서 솔버라는것이 존재하고, 이거 한번 만들어보면서 코딩 재활을 마쳤으니, 내일부터는 진짜 다시 작업 시작해야지...

[비월(lunar1228)]

[익명(recycle8790)]

보통 저런건 의도가 명확해서 솔버 쓰더라도 검증용 일 거 같은데

[Ray.(choxu0826)]

맞음 ㅋㅋ 퍼즐 유일성 검증, 추론 불필요 검증 이런 용도지

[익명(218.209)]

이 글에서 말하는 추론이 뭐임?

[Ray.(choxu0826)]

일단 맨 위에서 말한 게임의 추론은 직접 해당 퍼즐 게임을 플레이해본 결과, 1.현재 내가 칠한 부분과 주어진 정보를 기준 2. 어떤 타일에서도 최소 2개 이상의 가능성이 존재. 3. 어떤 타일에서든 퍼즐을 해결하기 위해서는 깊게 나아가서 막히면 되돌아와야만 하는 경우. 로 말하는거 같았음

[익명(recycle8790)]

예를 들어 스도쿠나 지뢰찾기에서 이 칸이 ~ 일 것이다 가정하고 풀어서 막히면 다시 탐색하는 소거법류 추측 하는거