책 이야기

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면 로얄플러쉬, 무늬만 같으면 스트레이트 플러쉬, 무늬가 다르면 스트레이트, 숫자와 관계없이 무늬가 같으면 플러쉬로 판정하면 된다. 복잡하게 썼지만 조건문으로 만들기에는 까다롭지 않았다.

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

The proper divisors of a number are all the divisors excluding the number itself. For example, the proper divisors of 28 are 1, 2, 4, 7, and 14. As the sum of these divisors is equal to 28, we call it a perfect number.

Interestingly the sum of the proper divisors of 220 is 284 and the sum of the proper divisors of 284 is 220, forming a chain of two numbers. For this reason, 220 and 284 are called an amicable pair.

Perhaps less well known are longer chains. For example, starting with 12496, we form a chain of five numbers:

12496 → 14288 → 15472 → 14536 → 14264 (→ 12496 → ...)

Since this chain returns to its starting point, it is called an amicable chain.

Find the smallest member of the longest amicable chain with no element exceeding one million.

숫자의 진약수는 자신을 제외한 약수이다. 예를 들어, 28의 진약수는 1, 2, 4, 7, 14이다. 진약수의 합계가 28이므로, 완벽수라 부른다. 흥미롭게도 220의 진약수의 합은 284이고, 284의 진약수의 합은 220이어서 두 숫자간에 체인을 만든다. 이런 이유로, 220과 284는 친화쌍(우애쌍, 친구쌍, amicable pair)이라 부른다.

더 긴 체인은 잘 알려져 있지 않다. 예를 들어, 12496으로 시작하면 5개 숫자의 체인을 만든다.

12496 → 14288 → 15472 → 14536 → 14264 (→ 12496 → ...)

이 체인은 시작 지점으로 돌아오기 때문에, 친화 체인(amicable chain)이라 부른다.

요소가 1백만을 넘지 않는 가장 긴 친화 체인의 가장 작은 수를 구하시오.

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

친화쌍(amicable pair) 등 일부 명칭은 한글로 찾을 수 없어서 친화수(amicable number)와 연계해서 친화쌍, 친화 체인으로 임의로 번역을 했다.

파이썬을 이용해 진약수 구하기, 진약수의 합 구하기, 체인 만들기 등은 이제 어렵지 않는 부분인데, 테스트로 몇 개 숫자를 대상으로 실행해보니 몇 가지 추가로 고려해야 할 것이 있었다. 모든 수가 체인을 만든다고 생각을 하고 다른 예외상황을 생각하지 않았는데, 고려할 사항을 예로 들면 소수가 되면 다음 숫자는 1이 되면서 무한 반복하고, 6이 되어도 6을 무한반복하고, 562로 시작하면 중간에 220과 284를 반복하고 있었다.

이렇게 하고도, 1백만까지 반복하려 하니 시간이 너무 많이 걸리는 문제가 있어, 이미 체인으로 파악한 경우에는 다시 진약수를 구하고 체인을 만드는 과정을 반복하지 않도록 하고, 약수가 1밖에 없는 소수는 더 이상 계산하지 않도록 하는 등 속도를 빠르게 조정했지만, 수 시간 걸릴 것으로 예상되는 등 속도가 문제가 되는 상황이었다.

하지만, 검증을 위해 나온 중간결과값이 정답이 되어 버려서 느린 성능에도 불구하고 정답을 맞힐 수는 있었다. 다른 사람의 방법을 확인하니 역시나 소인수분해를 응용해서 해결하는 것이 정석인 것 같다.

It is easily proved that no equilateral triangle exists with integral length sides and integral area. However, the almost equilateral triangle 5-5-6 has an area of 12 square units.

We shall define an almost equilateral triangle to be a triangle for which two sides are equal and the third differs by no more than one unit.

Find the sum of the perimeters of all almost equilateral triangles with integral side lengths and area and whose perimeters do not exceed one billion (1,000,000,000).

변의 길이가 정수이고 정수 크기의 면적을 가지는 정삼각형이 없다는 것은 증명하기 쉽다. 그러나, 거의 정삼각형인 5-5-6의 면적은 12로 정수가 된다.

두 변이 같고 다른 변과 길이 차이가 1 이하인 삼각형을 "거의 정삼각형"으로 정의하고자 한다.

변의 길이와 면적이 정수이고 둘라가 10억을 이하인 모든 "거의 정삼각형"의 둘래의 합계를 구하시오.

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

"거의 정삼각형"을 다시 생각해보면 2개의 직각삼각형이 붙어 있는 구조이며, 직각삼각형의 빗변(가장 긴 변)이 "거의 정삼각형"에서 길이가 같은 변이 된다. 그리고 길이가 같은 변을 a, 나머지 변을 b라 하면, 문제에서 정의한 내용에 따라 b=a±1이 되고, "거의 정삼각형" 안에 있는 직각삼각형은 빗변이 a, 다른 변은 피타고라스 정리에 의해 각각 b/2=(a±1)/2, (a**2-(b/2)**2)**0.5가 된다.

문제에서 둘레와 면적이 모두 정수가 된다고 했으므로 b, b/2, (a**2-(b/2)**2)**0.5 모두 정수가 되어야 하며 a*2+b는 10억 이하가 되어야 한다. 그리고, b/2가 정수가 되기 위해서는 a는 홀수가 된다.

이런 전제조건에 따라 a가 커지면서 b, b/2, (a**2-(b/2)**2)**0.5가 정수이고, 둘레가 10억 이하인 "거의 정삼각형"을 계속 구했는데, 정상적으로 나와야 할 갯수보다 6개가 더 나와서 둘레의 합이 훨씬 크게 나오는 문제가 생겼다.

원인을 파악해 보니 (a**2-(b/2)**2)**0.5 값을 int(a**2-(b/2)**2)**0.5)와 비교해서 같으면 정수로 판별했는데, 제곱수와 차이가 매우 미세하면 제곱수가 아닌데도 두 값이 같게 나오는 문제 때문에 답을 6개나 더 구한 것으로 추정되었다.

is_integer() 등 몇 가지 방법을 적용했지만 해결되지 않아서, 제곱근을 씌운 상태에서 계산하지 않고 제곱인 상태에서 값을 비교해서 제곱수 여부를 판별하게 했더니 정답을 구할 수 있었다. 이전 문제에서 비슷한 경험이 있어 빨리 해결 가능했지, 로직의 문제가 아닌 프로그램 고유 특성에서 생기는 이런 현상은 찾기가 쉽지 않은 것 같다.

By using each of the digits from the set, {1, 2, 3, 4}, exactly once, and making use of the four arithmetic operations (+, −, *, /) and brackets/parentheses, it is possible to form different positive integer targets.

For example,

    8 = (4 * (1 + 3)) / 2
    14 = 4 * (3 + 1 / 2)
    19 = 4 * (2 + 3) − 1
    36 = 3 * 4 * (2 + 1)

Note that concatenations of the digits, like 12 + 34, are not allowed.

Using the set, {1, 2, 3, 4}, it is possible to obtain thirty-one different target numbers of which 36 is the maximum, and each of the numbers 1 to 28 can be obtained before encountering the first non-expressible number.

Find the set of four distinct digits, a < b < c < d, for which the longest set of consecutive positive integers, 1 to n, can be obtained, giving your answer as a string: abcd.

{1, 2, 3, 4}의 각 숫자를 한 번씩 사용하고, 4개 연산자(+, -, *, /)와 괄호를 사용하여, 서로 다른 정수를 구할 수 있다.

예를 들면 다음과 같다.

    8 = (4 * (1 + 3)) / 2
    14 = 4 * (3 + 1 / 2)
    19 = 4 * (2 + 3) − 1
    36 = 3 * 4 * (2 + 1)

주의할 것은 숫자를 연결하여 12+34로 계산하는 것은 허용되지 않는다.

{1, 2, 3, 4} 집합을 이용하여 31가지 다른 숫자를 구할 수 있고, 최대값은 36이다. 그리고, 1~28까지는 연속해서 구할 수 있다.

1부터 n까지 가장 긴 연속으로 숫자를 구할 수 있는 a<b<c<d인 숫자 4개를 구하고, 답안은 abcd 형태로 작성하라.,

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

몇가지 고민할 사항이 있어 나중에 해결했는데, 인터넷에서 누군가가 알려준 eval() 함수를 활용하면서 많은 부담을 덜 수 있었다.

연산자는 +,-,*,/의 4가지를 사용하는데, 예시에 있는 것처럼 연산자의 우선순위와 관계없이 계산하기 위하여 괄호를 이용해 인위적으로 순서를 지정할 필요가 있다. 연산자가 들어갈 곳은 3자리이므로 괄호를 통해 순서를 강제하는 것은 연산자의 순서를 1,2,3이라 할 때 (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)의 6가지 경우가 있는데 이 중 (3,1,2)는 괄호를 통해서도 만들어낼 수 없는 경우이기 때문에 5가지 연산을 하게 만들면 된다.

4가지 숫자를 점차 커지는 순서로 만들고, 생성된 숫자 4개를 순열을 통해 다양한 순서를 만들고, 각 순서에 4가지 연산자 조합에 대해 5가지 연산을 해서, 결과가 양의 정수일 때 결과에 더하고, 모은 결과를 집합, 정렬을 통해 순서대로 배열해서 1부터 가장 긴 연속된 숫자가 있는 4가지 숫자 조합을 찾으면 된다.

위 경우 중 4가지 숫자를 커지는 순서로 만드는 데 반복문 4회, 순열 생성에 반복문 1회, 연산자를 3자리에 배열하는 데 반복문 3회를 해서 들여쓰기를 많이 하는 구조가 되었다.

그리고, 0으로 나누는 경우가 발생할 수 있으므로 exception을 사용하여 예외처리했는데, 개발툴인 Visual Studio Code가 익숙하지 않아서 exception을 무시하도록 설정하지 않아 처음에는 계속 F5를 눌러야 했다. 나중에 보니 Raised Exceptions을 Breakpoints로 설정하지 않도록 하는 옵션이 있어 결과를 빨리 볼 수 있었다.

A number chain is created by continuously adding the square of the digits in a number to form a new number until it has been seen before.

For example,

44 → 32 → 13 → 10 → 1 → 1
85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89

Therefore any chain that arrives at 1 or 89 will become stuck in an endless loop. What is most amazing is that EVERY starting number will eventually arrive at 1 or 89.

How many starting numbers below ten million will arrive at 89?

숫자 체인은 각 자릿수를 더하여 새로운 숫자를 구하는 것을 끝날때까지 반복하면서 생성된다.

예를 들면 다음과 같다.

44 → 32 → 13 → 10 → 1 → 1
85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89

따라서, 어떤 체인이든 1 또는 89가 되면 무한반복되면서 정체된다. 가장 놀라운 것은 모든 숫자는 결국 1 또는 89에 이른다는 것이다.

1천만 이하의 숫자 중에 89가 되는 숫자는 몇 개인가?

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

10자리수 이상은 자릿수별로 쪼개어서 제곱하고 더하는 과정을 반복하면서 89가 나오는 경우의 수를 더하도록 하면 되는 문제이다. 다만, 1천만 까지 계산하기를 요구했기 때문에 시간은 생각보다 엄청 많이 필요하게 된다.

그래도, 이 방법이 가장 정확한 방법이라 생각하고 속도를 조금 개선해보기 위해 제곱수를 매번 계산하지 않고 리스트를 만들어서 참조하게 했다. 그렇게 해서 256초가 245초로 조금 개선될 수 있었다.

문제를 해결한 후에, 인터넷을 검색해보니 동일한 순열(4666777과 6466777, 7664776)에 대해서는 한 번 계산한 결과를 이용하여 모든 체인을 계산하지 않도록 성능 개선이 가능하다고 되어 있다. 정말 세상은 넓고 해결방안은 다양하다는 것을 새삼 느끼게 된다.