책 이야기

Comparing two numbers written in index form like 2¹¹ and 3⁷ is not difficult, as any calculator would confirm that 2¹¹ = 2048 < 3⁷ = 2187.

However, confirming that 632382⁵¹⁸⁰⁶¹ > 519432⁵²⁵⁸⁰⁶ would be much more difficult, as both numbers contain over three million digits.

Using base_exp.txt (right click and 'Save Link/Target As...'), a 22K text file containing one thousand lines with a base/exponent pair on each line, determine which line number has the greatest numerical value.

NOTE: The first two lines in the file represent the numbers in the example given above.

지수로 표현된 두 수 2¹¹과 3⁷을 비교하는 것은 어렵지 않다. 계산기를 이용하면 2¹¹ = 2048 < 3⁷ = 2187을 확인할 수 있다.

그러나, 3백만 자릿수 이상이 되는 두 수가 632382⁵¹⁸⁰⁶¹ > 519432⁵²⁵⁸⁰⁶ 인 것을 확인하는 것은 상당히 어렵다.

1천 개 이상의 밑과 지수 쌍이 각 행에 있는 22K 크기의 텍스트 파일 base_exp.txt (오른쪽 클릭하고 다른 이름으로 링크 저장) 중 가장 큰 값을 가지는 숫자를 찾으시오.

주의: 파일의 첫 두 줄은 위의 예시에 있는 숫자이다.

--------------------------------------------------------------------------

정직하게 프로그래밍 했더니 역시나 OverflowError: math range error라는 에러메시지를 보게 되었다. 급격하게 커지는 지수를 따라가지 않고 계산할 방법은 이제는 까맣게 잊어버린 log를 다시 찾아보는 방법밖에 없어 보인다.

로그의 지수법칙(loga^b=bloga)을 이용하여 동일한 밑인 상황에서 base_exp 파일의 밑과 지수를 로그에 대입하면(문제의 예시에서 518061*log632382와 525806*log519432를 비교하는 형태) 어렵지 않게 해결 가능하다.

By replacing each of the letters in the word CARE with 1, 2, 9, and 6 respectively, we form a square number: 1296 = 36². What is remarkable is that, by using the same digital substitutions, the anagram, RACE, also forms a square number: 9216 = 96². We shall call CARE (and RACE) a square anagram word pair and specify further that leading zeroes are not permitted, neither may a different letter have the same digital value as another letter.

Using words.txt (right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, find all the square anagram word pairs (a palindromic word is NOT considered to be an anagram of itself).

What is the largest square number formed by any member of such a pair?

NOTE: All anagrams formed must be contained in the given text file.

단어 CARE의 각 글자를 각각 1, 2, 9, 6으로 바꾸면 1296 = 36²의 제곱수가 된다. 여기서 주목할만한 점은, 동일한 디지털 교체 방법인 애너그램(anagram, 철자 순서 바꾸기)을 적용한 RACE 또한 9216 = 96²로 제곱수가 된다. CARE(와 RACE)는 제곱 애너그램 쌍이라 부르는데, 단어는 0으로 시작하지 않고 서로 다른 글자는 같은 디지털 값을 가지지 않도록 한다.

약 2천개 일반 영어 단어가 있는 16K 텍스트 파일인 words.txt (우클릭하고 다른 이름으로 저장)을 이용하여 모든 제곱 애너그램 쌍을 찾으시오 (회문 형태는 자신의 애너그램이 아니다).

이 쌍에서 구할 수 있는 가장 큰 제곱수는 무엇인가?

주의: 모든 애너그램은 제시된 텍스트 파일에서 구해야 한다.

--------------------------------------------------------------------------

문제를 해결할 때마다 드는 생각이지만, 요즘 언어 특성에 맞는 간결하면서도 빠른 접근방법이 있을 것 같은 느낌은 들지만 정확하게 모르기 때문에 정공법이라 할 수 있는 시간이 걸려도 단계별로 구현해 나가는 형태로 해결하고 있는 것 같다.

이 문제를 해결하려면, 일단 파일을 읽어 단어 리스트를 만들고, 그 중 애너그램이 될 수 있는 단어를 찾고, 단어 길이만큼의 제곱수 목록을 만들어서, 애너그램 후보 단어 그룹과 제곱수 목록이 매치되는 최대값을 찾는 4가지 과정이 필요했다.

파일을 읽어 단어 리스트를 만드는 것은 프로젝트 오일러 문제를 풀면서 몇 번 해봤기 때문에 기존에 작성한 것을 활용해서 따옴표만 처리해주면 되었다.

애너그램이 될 수 있는 단어를 찾기 위해, 각 단어를 알파벳 순으로 정렬했을 때 같은 값을 가지는 단어를 묶어 리스트를 만들었다.

제곱수 목록을 만들기 위해, 애너그램이 될 수 있는 단어들의 길이를 측정해서 최소 길이부터 최대 길이 사이에 있는 제곱수 목록을 만들었다. 조금 편하게 쓸 수 있을 것 같아 제곱수 목록을 단어 길이별로 만들었다.

애너그램 후보 단어 그룹과 제곱수 목록을 매치시키는 것을 구현하는 부분이 제일 어려웠는데, 실제 구현한 코드도 처음 생각한 모든 기능을 반영한 것은 아니지만 일단 정답을 맞췄기에 넘어가기로 했다. 문제의 예시로 설명하면, 4자리 제곱수의 1296, 애너그램 대상이 되는 CARE, RACE를 읽어서 애너그램 숫자 9216을 만들고 그것이 4자리 제곱수 목록에 있는지, 각 단어그룹을 해당 자리 제곱수 목록만큼 2중 반복문을 통해 찾도록 했는데 간단히 구현한 만큼 문제가 있었다.

SHEET, THESE의 경우 E의 자리 값이 같아야 되고, 그 값이 THESE로 되었을 때 같은 자리에 있어야 한다. SHEET의 숫자가 12334이면, THESE는 42313이 되어야 되는데 가지고 있는 실력으로는 그렇게까지 정교하게 만들어 낼 수가 없었다. 그래서 고민끝에 아이디어를 낸 것이 두 숫자의 종류가 같고, 같은 숫자 최대값이 애너그램의 같은 문자 최대값과 같은 경우로 조건을 추가했는데 답을 구할 수 있었다.

문제에서 요구한 기능을 모두 구현한 것은 아니지만 답은 구할 수 있어서 아쉽지만 기뻤다. 코드가 깔끔해지 못하지만 실행시간이 짧은 것은 의외였다.

The first known prime found to exceed one million digits was discovered in 1999, and is a Mersenne prime of the form 2^6972593−1; it contains exactly 2,098,960 digits. Subsequently other Mersenne primes, of the form 2^p−1, have been found which contain more digits.

However, in 2004 there was found a massive non-Mersenne prime which contains 2,357,207 digits: 28433×2^7830457+1.

Find the last ten digits of this prime number.

1백만 자릿수가 넘는 소수 중 처음으로 알려진 소수가 1999년에 발견되었다. 이것은 2^6972593−1 형태인 메르센 소수(Mersenne prime)이다. 이 숫자는 2,098,960 자리로 구성된다. 마르센 소수 이후, 자릿수가 더 많은 2^p−1 형태의 메르센 소수가 발견되고 있다.

그러나, 2004년에 2,357,207 자릿수인 큰 규모의 비 메르센 소수 28433×2^7830457+1이 발견되었다.

이 소수의 마지막 열 자릿수를 구하시오.

--------------------------------------------------------------------------

메르센 소수(Mersenne prime)라는 새로운 형태의 소수를 소개하고 그것을 응용하는 문제이다. 프로그래밍을 효율적으로 또는 어렵게 하는 데 수학이 필요하다는 것은 인정하지만, 갈수록 프로그래밍 보다는 수학을 공부하고 있는 것 같다.

파이썬의 정수 최대값 허용폭이 넓은 것을 믿고 정직하게 한 줄로 작성했더니 최대값을 넘어 동작하지 않는다는 에러가 나왔다.

문제에서 마지막 10자리 숫자를 물어봤고, 이것은 모든 숫자를 계산할 필요없이 마지막 10자리 숫자만 계산하면 되는 것이었다. 그래서 % 연산자를 이용해 계속 10자리만 남게 하면서 2를 계속 곱해 2^7830457을 구하고, 거기에 28433곱하고 1을 더해서 나온 숫자의 마지막 10자리만 뽑아내면 되므로 문제를 해결하는 것은 그리 까다롭지 않았다.

The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property.

Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.

소수 3, 7, 109, 673은 주목할 만하다. 두 소수를 선택해서 연결하면 소수가 된다. 예를 들면, 7, 109를 연결한 7109와 1097은 모두 소수이다. 네 소수의 합인 792는 이런 속성을 가진 네 소수의 합 중 가장 작은 값이다.

임의의 두 소수를 연결해도 소수가 되는 다섯 소수의 합계 중 가장 작은 값을 구하시오.

--------------------------------------------------------------------------

값을 찾을 소수의 최대값을 정해야 하는데, 예시를 보고 일단 1만 이하의 소수를 대상으로 찾아보기로 했다.

단순대입법보다 좋은 방법이 생각나지 않아서, 크기가 커지는 5개의 소수를 대상으로 반복문을 구성해서 이 중 2개씩 연결한 것 모두 소수인 것을 찾도록 구성했다. 5개 숫자를 a, b, c, d, e라고 할 때 2번째 반복문에서 ab, ba가 소수이고, 3번째 반복문에서 ac, ca, bc, cb가 소수이고, 4번째 반복문에서 ad, da, bd, db, cd, dc가 소수이며, 5번째 반복문에서 ae, ea, be, eb, ce, ec, de, ed의 20가지 모두 소수가 되는 경우를 찾게 했다.

소수 리스트가 1200개가 넘게 있으니 5중 반복문이면 최악의 경우 1200⁵를 계산해야 되는 구조여서 예상했던 것 보다 시간이 많이 필요했다. 제일 처음 나오는 값이 합계가 가장 작은 경우라는 보장이 없기 때문에 모든 경우를 계산해서 답을 찾아야 하지만, 가장 먼저 나온 경우를 입력했을 때 정답으로 처리되어 다행히 조금 더 빨리 답을 구할 수 있었다.

상황을 분석해보니 연결한 숫자의 소수여부를 판별하는 데 시간이 많이 걸리는 것을 발견하고, 초기에 소수 목록을 연결된 숫자까지 만들고 난 이후에 그 값으로 판별하게 하니 실행 시간이 몇시간에서 몇분으로 개선되었다. 그리고, 계속 오답을 찾아 이상했는데 리스트의 값과 인덱스를 잘 구분하지 못하고 사용한 문제 때문에 발생한 것이었다.

1만 이하 소수에서 답이 되는 경우가 하나 이상 있을 수 있어 5중 반복문을 전부 돌려 답을 찾게 했는데, 실제로는 답이 되는 경우가 하나 밖에 없었다.

Each character on a computer is assigned a unique code and the preferred standard is ASCII (American Standard Code for Information Interchange). For example, uppercase A = 65, asterisk (*) = 42, and lowercase k = 107.

A modern encryption method is to take a text file, convert the bytes to ASCII, then XOR each byte with a given value, taken from a secret key. The advantage with the XOR function is that using the same encryption key on the cipher text, restores the plain text; for example, 65 XOR 42 = 107, then 107 XOR 42 = 65.

For unbreakable encryption, the key is the same length as the plain text message, and the key is made up of random bytes. The user would keep the encrypted message and the encryption key in different locations, and without both "halves", it is impossible to decrypt the message.

Unfortunately, this method is impractical for most users, so the modified method is to use a password as a key. If the password is shorter than the message, which is likely, the key is repeated cyclically throughout the message. The balance for this method is using a sufficiently long password key for security, but short enough to be memorable.

Your task has been made easy, as the encryption key consists of three lower case characters. Using p059_cipher.txt (right click and 'Save Link/Target As...'), a file containing the encrypted ASCII codes, and the knowledge that the plain text must contain common English words, decrypt the message and find the sum of the ASCII values in the original text.

컴퓨터의 각 글자에는 유일한 코드가 할당되어 있으며, 선호되는 표준은 ASCII(American Standard Code for Information Interchange)이다. 예를 들어, 대문자A=65, 별표(*)=42, 소문자k=107이다.

근대 암호화 기법은 텍스트 파일을 가져와서, 바이트를 ASCII로 변환하고, 각 바이트를 비밀키에서 가져온 값으로 XOR 계산하는 것이다. XOR 함수의 장점은 암호화 된 텍스트에 같은 키를 적용하면 평문(원래 텍스트)을  복원할 수 있다는 것이다. 예를 들어 65 XOR 42 = 107이고, 107 XOR 42 = 65이다.

깰 수 없는 암호화를 위하여 키는 평문과 같은 길이이고, 키는 랜덤한 바이트로 만들어진다. 사용자가 암호화 된 메시지를 가지고 있지만 암호화 키를 다른 곳에 보관하면, 둘 모두가 있지 않으면 복호화할 수 없다(암호를 해독할 수 없다).

불행하게도, 이 방법은 대부분 사용자에게 실용적이지 못하기 때문에, 수정된 방법이 패스워드를 키로 사용하는 것이다. 패스워드가 메시지보다 짧으면, 키는 전체 메시지에 반복되면서 적용된다. 이 방법을 위한 균형은 패스워드가 보안을 유지하기에 충분히 길면서 기억할 수 있을만큼 짧은 것이다.

당신의 과제는 암호화 키를 3자리의 소문자로 구성하는 것으로 단순화되었다. 암호화 된 ASCII 코드를 가지고 있는 p059_cipher.txt (우클릭하고 '다른 이름으로 링크 저장') 파일을 복호화하여 일반 영어 단어로 구성된 평문을 구하고 원문에 있는 ASCII 값의 합계를 구하시오.

--------------------------------------------------------------------------

포커 게임을 설계해보는 57번 문제에 이어 실제 상황에 필요할만한 프로그램을 만들어보는 문제이다. 이 문제도 간단해 보여 덤볐다가 생각보다 까다로워 나중에 풀어보기로 했던 것이다.

파일에 있는 숫자를 이진수로 변환하고 XOR 계산을 하려고 했는데, 계속 에러가 나서 이해하기 어려운 상황이 되었다. 이유를 찾다 보니 파이썬의 bin 함수로 변환한 이진수는 문자열로 처리가 되고, 파이썬의 경우 십진수를 대상으로 XOR 연산을 해도 이진수에 대한 XOR과 같은 결과가 나온다는 것이었다. 간단하게 진행할 수 있는 것을 멀리 돌아가고 있었다.

XOR을 적용한 내용이 영어 평문인지 확인하는 방법을 고민했는데, 처음에는 결과의 아스키코드 값이 숫자와 알파벳에만 있는 것으로 했는데 나오지 않아서, 영어 평문에 나올 수 없는 기호인 경우를 제외하는 형태로 했더니 3자리 글자 후보로 하나씩만 나왔다.

그 값을 이용해서 XOR을 적용하고 나온 아스키 코드 값을 더해서 답을 구할 수 있었다. 참고로, 그 결과를 파이썬 chr 함수를 이용해서 원문 형태로 바꾸니 말이 되지 않는 문장이 나온다. 찾아낸 복호화 코드가 맞는지 의심은 들었지만 결과값이 맞기에 넘어가기로 했다.

(유튜브로 해법을 올리는 영상을 확인하니 일반 영어문장이 나오는 것을 보면 키를 잘 못 찾았는데, XOR을 적용한 결과는 같아 정답을 맞춘 것으로 나온 것 같다. 괜히 복호화한 문장을 확인했다가 찝찝함을 남기게 되었다. 그리고, 유튜브에서는 내가 접근한 나올 수 없는 기호를 제외하는 방법이 아니라 복호화했을 때 가장 흔한 영어단어인 'the', 'and'가 있는지 확인하는 형태로 키를 찾고 있었다.)