책 이야기

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이 되어야 되는데 가지고 있는 실력으로는 그렇게까지 정교하게 만들어 낼 수가 없었다. 그래서 고민끝에 아이디어를 낸 것이 두 숫자의 종류가 같고, 같은 숫자 최대값이 애너그램의 같은 문자 최대값과 같은 경우로 조건을 추가했는데 답을 구할 수 있었다.

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

In the card game poker, a hand consists of five cards and are ranked, from lowest to highest, in the following way:

• High Card: Highest value card.
• One Pair: Two cards of the same value.
• Two Pairs: Two different pairs.
• Three of a Kind: Three cards of the same value.
• Straight: All cards are consecutive values.
• Flush: All cards of the same suit.
• Full House: Three of a kind and a pair.
• Four of a Kind: Four cards of the same value.
• Straight Flush: All cards are consecutive values of same suit.
• Royal Flush: Ten, Jack, Queen, King, Ace, in same suit.

The cards are valued in the order:
2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, King, Ace.

If two players have the same ranked hands then the rank made up of the highest value wins; for example, a pair of eights beats a pair of fives (see example 1 below). But if two ranks tie, for example, both players have a pair of queens, then highest cards in each hand are compared (see example 4 below); if the highest cards tie then the next highest cards are compared, and so on.

Consider the following five hands dealt to two players:

The file, poker.txt, contains one-thousand random hands dealt to two players. Each line of the file contains ten cards (separated by a single space): the first five are Player 1's cards and the last five are Player 2's cards. You can assume that all hands are valid (no invalid characters or repeated cards), each player's hand is in no specific order, and in each hand there is a clear winner.

How many hands does Player 1 win?

포커에서는 카드 5장을 다음 순서로 등급을 매긴다.

• 하이 카드: 가장 높은 값의 카드
• 원 페어: 2장의 카드가 같은 값
• 투 페어: 2개 서로 다른 페어
• 트리플: 카드 3장이 같은 값
• 스트레이트: 모든 카드가 연속된 숫자
• 플러쉬: 모든 카드가 같은 무늬
• 풀 하우스: 트리플과 원 페어
• 포카드: 카드 4장이 같은 값
• 스트레이트 플러쉬: 연속된 숫자이며 같은 무늬
• 로얄 플러쉬: 10, J, Q, K, A가 같은 무늬

카드의 순서는 다음과 같다.
2, 3, 4, 5, 6, 7, 8, 9, 10, J(잭), Q(퀸), K(킹), A(에이스)

두 플레이어의 등급이 같으면 가장 높은 카드로 구성된 플레이어가 이긴다. 예를 들어, 8 페어는 5 페어를 이긴다(아래의 예시1을 참조). 그러나, 두 등급이 동일한 경우 가장 높은 카드를 비교한다(아래의 예시4 참조). 가장 높은 카드도 동일한 경우에는 다음 높은 카드를 비교하는 식으로 계속 한다.

두 플레이어 간 다음 다섯 게임을 보면:

poker.txt 파일에는 1천 개의 랜덤한 두 플레이어 간 게임이 있다. 파일의 각 중에는 스페이스로 구분된 10장의 카드가 있으며, 이 중 처음 5장은 플레이어 1의 카드이고, 다음 5장은 플레이어 2의 카드이다. 모든 카드는 유효하고, 각 플레이어의 카드에는 특정 순서가 없고, 각 게임에는 분명하게 승자가 있다고 가정하자.

플레이어 1은 몇 번 이겼는가?

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

포커 게임을 실제로 만들어 보는 문제인데, 문제를 해결하는 것은 어렵지 않았는데 포커 룰을 모두 프로그래밍하는 것에 시간이 많이 필요할 것 같아 천천히 풀어봤다. 어려운 문제들을 많이 풀었기 때문에 조건문이 많이 들어가고, 동점상황 때문에 길게 프로그램을 만들어야 했지만 쉬는 기분으로 해결할 수 있었다.

파일을 읽어 각 게임을 문자열 하나로 만들고, 플레이어1,2의 각 숫자 갯수와 무늬를 판별해서 등급을 매기고, 그것을 기준으로 누가 이기는지 결정하면 된다.

숫자 갯수와 무늬를 판별하고 등급을 매기는 것이 반복되어 함수로 만들었고, 숫자 갯수는 리스트의 각 숫자 위치에 몇장 있는지 기록을 하고, 무늬는 4장 모두 같은 무늬인지만 판별하게 했다. 등급은 특정 숫자가 4개면 포카드, 3개,2개이면 풀하우스, 3개면 트리플, 2개가 2개면 투페어, 5개면 원페어이고, 연속된 숫자가 있는데 숫자가 같은 무늬이며 10,J,Q,K,A면 로얄플러쉬, 무늬만 같으면 스트레이트 플러쉬, 무늬가 다르면 스트레이트, 숫자와 관계없이 무늬가 같으면 플러쉬로 판정하면 된다. 복잡하게 썼지만 조건문으로 만들기에는 까다롭지 않았다.

그런데, 동점 상황일 때 높은 카드를 가진 사람이 이기는 것을 적용하기 위해 추가로 작성한 부분이 전체 코드보다 더 길게 나오는 것을 보면, 예외처리 상황이 많아 논리가 복잡하게 나왔던 것 같다. 문제에서 요구하지 않은 예외상황까지 생각하면서 너무 복잡하게 구현한 것 갈은 느낌도 들었다.

NOTE: This problem is a more challenging version of Problem 81.

The minimal path sum in the 5 by 5 matrix below, by starting in any cell in the left column and finishing in any cell in the right column, and only moving up, down, and right, is indicated in red and bold; the sum is equal to 994.

Find the minimal path sum from the left column to the right column in matrix.txt (right click and "Save Link/Target As..."), a 31K text file containing an 80 by 80 matrix.

주의: 이 문제는 문제81 보다 더 어렵다.

첫번째 열의 원소에서 시작해서 마지막 열에서 끝나며 위, 아래, 오른쪽으로만 움직일 때 아래의 5x5 행렬에서 최소 경로는 붉은 색으로 굵게 표시되어 있으며 합계는 994이다.

80x80 행렬이 있는 31K 텍스트 파일 matrix.txt (우클릭 하고 "다른 이름으로 링크 저장")의 첫번째 열에서 마지막 열까지 이동할 때 최소 경로의 합계를 구하시오.

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

81번 문제를 해결한 방법을 그대로 사용할 수는 없었지만, 그 방법을 가져와서 반복을 통해 해결했다. 81번 문제에서는 답을 구할 자리가 행렬 전체의 마지막 자리(80, 80)이지만, 이번 문제에서는 마지막 열(x,80) 모두가 답이 되는 후보이기 때문에 마지막 열 각 행을 기준으로 최소 경로의 값을 구하는 방식으로 접근했다..

위 예시를 기준으로 예를 들면, 2번째 열, 2번째 행의 최소값 후보는 1번째 열 각 행에서 시작한 5개 경로의 값 900(131+673+96), 297(201+96), 1529(630+803+96), 2135(537+699+83+96), 3135(805+732+699+803+96) 중 가장 작은 297이 된다. 이 예시에서 131다음에 201로는 왜 안가고 673으로만 가는지 의문이 들 수 있는데, 이 경우 201에서 시작한 경우보다는 무조건 크기 때문에 최소값이 될 수 없다고 생각해서 배제했다.

이런 식으로 각 열의 최소값을 2번째 열부터 마지막 열까지 구하고, 마지막 열 각 행의 최소 경로 값 중에서 제일 작은 값을 찾으면 된다. 그런데, 다중 반복문을 실행하느라 시간이 7초 이상 걸리는 것을 보면 좀 더 빠른 방식으로 해결하는 방법이 있을 것 같다.

Using names.txt (right click and 'Save Link/Target As...'), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.

For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 × 53 = 49714.

What is the total of all the name scores in the file?

5천 개 이상의 이름이 들어 있는 46K 크기의 names.txt를(우클릭하고 "(으)로 링크 저장") 이용하여, 우선 알파벳 순서로 정렬하시오. 그리고, 목록의 알파벳 순서 위치와 알파벳 값을 곱하여 점수를 구하라.

예를 들어, 알파벳 순서로 정렬된 목록에서 COLIN의 값은 3+15+12+9+14=53이며, 목록의 938번째 있다. 따라서, COLIN의 점수는 938x53=49714이다.

파일에서 모든 이름 점수의 합계는 무엇인가?

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

파일을 이용하는 첫번째 문제이다. 파일로 읽어들인 문자열을 쉼표 기준으로 구분하여 따옴표(")를 제거하면서 리스트로 바꾸고, 알파벳 값으로 딕셔너리를 만들면 문제를 해결하기 위한 기초 작업은 끝난 것이다.

내장 함수를 이용해 정렬하고, 딕셔너리를 활용해 각 단어의 글자를 값으로 바꾸고 순서를 활용해 점수를 구하는 과정을 모든 단어를 대상으로 반복하면 된다.