기탁님 블로그에 오늘 재미난 내용이 올라왔더군요. 다름 아닌 사이냅소프트에서 개발자들을 상대로 하는 이벤트 였습니다. 그런데 기념품이 먼지를 모르겠습니다. 마지막까지 가르쳐주지 않더군요. 갈수록 코딩을 더 마니 요구하는 문제들이 나옵니다. 사실 2,3,4단계는 전부 같은 문제입니다. 문제 푸는 분들의 삽질 시간을 덜어 드리기 위해서 간단한 소개와 힌트만 담아보았습니다.
일 단계: 피보나치
피보나치 수열에 관한 문제입니다.
문제는 여기서 보실 수 있습니다.
저는 이 문제에서 완전 삽질했습니다. 왜냐하면 문제가 a, b 두 수가 주어졌을때 사이에 존재하는 피보나치 숫자 개수를 구하는 건줄 알았거든요. a+b뭐 이런 식이 답이 되는 줄 알았던거죠. 생각하고 적고, 구글링을 해도 답을 찾을 수가 없었습니다. 한탄하고 있는 이 때 문제를 다시 보았습니다. 밑에 다른 글씨로 뭔가 적혀있더군요. 그렇습니다. 그 숫자 사이의 피보나치 숫자의 합을 구하는게 문제였습니다. 이건 뭐 쉽죠. 숫자가 커서 __int64로 구해야 합니다. 그러면 금방 답이 나오죠.
이 단계: SYNAP + SOFT = WANTS + YOU
다음 단계는 헨리 듀드라는 사람이 만든 암호문에 관한 문제 입니다. 알파벳 각 자리가 한 가지 숫자에 대응하는 쉬운 암호죠. 아래는 원리를 가르쳐주는 간단한 암호문입니다.
SEND + MORE = MONEY
9567 +1085 = 10652[E=5, D=7, M=1, O=0, N=6, S=9, R=8, Y=2]
문제는 SYNAP + SOFT = WANTS + YOU의 암호문을 만족하는 숫자들을 구하는 겁니다.
푸는 방법이야 여러가지가 있겠지만 저는 걍 무식하게(brute force)로 풀었습니다.
그래도 금방 끝나더군요. 이 문제의 경우 알파벳과 숫자가 각각 열 개기 때문에
C++에 있는 next_permutation을 사용하면 쉽게 구할 수 있습니다.
삼 단계: 78, 79번째 단어를 구하기
그 다음 단계도 문제는 똑같습니다. 동일한 암호문 문제를 푸는 거죠.
사전 파일이 주어지고 그 중에 암호가 있는 78, 79번째 단어를 구하는 겁니다.
한 가지 주의해야 할 것은 여기서는 next_permutation이 안통합니다.
왜냐하면 글자는 5개고, 숫자는 10개인 뭐 그런 경우가 있기 때문이죠.
저는 걍 간단하게 재귀로 만들어서 돌렸습니다.
좌변은 같고 우변만 틀리기 때문에 우변만 처리할 수 있도록 만들었죠.
무식하게 풀어서 생각보다 쪼금 오래 걸리더군요.
78, 79번째 단어라 다행이었습니다.
1078, 1079였으면 생각하기 시러지죠.
사 단계: 헨리 듀드 암호 해독 프로그램 작성
파이날 단계도 똑같습니다. 헨리 듀드 암호문을 해독하는 프로그램을 만드는 겁니다.
아래와 같이 암호문이 주어지고 그것에 답을 구하는 프로그램을 만드는 문제입니다.
SYNAP + SOFT = WANTS + YOU
SEND +MORE = MONEY
EMAIL= SPAM + SPAM + SPAM + SPAM + SPAM + SPAM
FORTY +TEN+ TEN= SIXTY
NUMBER = SQUARE + SQUARE + SQUARE + SQUARE
SEVENTY = FIVE + SEVEN + ELEVEN + TWELVE + FIFTEEN + TWENTY
MANET + MANTISSE + MIRO + MONET + RENOIR = ARTISTS
SIX+SIX+SIX = NINE + NINE
ABCDE*F=GGGGGG
ADAM+AND+EVE=MOVED
FIVE+FIVE+NINE+ELEVEN=THIRTY
CROSS+ROADS=DANGER
USE + LESS = KIDDY
BILL + WILLIAM + MONICA = CLINTON
GREEN + ORAGNE = COLORS
CEZANNE + MANET + MATISSE = ARTISTS
OLD+SALT+TOLD+TALL=TALES
COFFEE + COFFEE + COFFEE = THEOREM
SEND * ME = EMAIL
POWER = YOUR + SHOW
ALLEN = K * JEON
갈수록 노가다틱해지죠. ㅋㅋ 저는 이제껏 쓰던 거에서 문자열을 처리할 수 있는 간단한 스캐너를 추가하고, 좌변 우변을 리스트로 등록해서 계산하는 방법으로 문제를 풀었습니다. 사실 암호푸는 코드보다 부가적인 코드를 더 마니 만들어야하는 부분입니다. 다항식을 리스트로 연결해서 구하는게 핵심이라면 핵심일 수 있겠네요.
2 단계에서 4 단계로 오면서 느끼겠지만 코드는 점점 더 제너럴한 솔루션을 구하는 걸 원합니다. 사실 2 단계 때 벌써 범용적으로 쓸 수 있는 코드를 만들었다면 4 단계 까지는 금방 가죠. 저는 그 때 그 때 답을 구하는데 맞춰서 작성해서 4 단계 때 제법 마니 뜯어 고쳐야 했습니다. ㅋㅋ
차마 조잡해서 소스는 못 보내고, 화면만 보내도 기념품 준다길래 화면만 보냈습니다. 답이 맞는지 아닌지도 모르겠습니다. 그나저나 헨리 듀드같은 저런 문제는 어디서 구하는걸까요? 20세기 최고의 퍼즐리스트라는데 저는 처음 들어봤습니다. ㅎㅎ