최신 내용을 확인하시려면 여기를 클릭해주세요.
U+Net**** 의 비밀번호 규칙은 의외로 간단하다. Perl을 이용해서 간단히 U+Net**** 용 dictionary를 생성해보았다.
아래 코드를 uplusnet_dict.pl 라는 이름으로 저장한 후,
$ perl uplusnet_dict.pl > uplusnet.dict
와 같이 실행해주면 된다.
|
1
2
3
4
5
6
7
8
9
10
11
12
|
#!/usr/bin/env perl use 5.010; use strict; use warnings; for (1, 5, 6) { my $start = $_*1_000_000_000; my $end = $start + 999_999; for ($start .. $end) { say $_; } } |
컴퓨터상의 모든 문자들은 유일한 코드값에 대응되는데, 보통 ASCII 표준이 널리 쓰입니다. 예를 들면 대문자 A는 65, 별표(*)는 42, 소문자 k는 107라는 값을 가집니다.
현대적인 암호화 기법 중에, 텍스트 파일의 내용을 ASCII 코드로 바꾸고 각 바이트를 비밀키의 값으로 XOR 시키는 것이 있습니다. 이 방법의 장점은 암호화와 복호화에 동일한 키를 사용할 수 있다는 것입니다. 예를 들어 65 XOR 42 = 107 이고, 107 XOR 42 = 65 가 됩니다.
암호문을 절대 깰 수 없도록 하려면, 암호화할 문장의 길이와 같은 무작위의 비밀키를 만들면 됩니다. 암호문과 비밀키는 따로따로 보관해둬야 하고, 그 반쪽짜리 정보 두 개를 함께 확보하지 않는 한 해독은 불가능합니다.
하지만 이 방법은 대부분의 경우 실용적이지 못하므로, 원문보다 짧은 비밀키를 사용하게 됩니다. 이런 경우 비밀키는 전체 메시지에 대해서 반복적으로 돌아가며 적용됩니다. 이 때 키의 길이는 보안상 충분할 정도로 길어야 하지만 또한 쉽게 기억할 수 있을 정도로 짧아야 한다는 미묘한 균형이 요구됩니다.
이번 문제를 위해서 준비된 암호화 키는 단 3개의 영어 소문자이고, cipher1.txt 파일에 암호화된 ASCII 코드값이 들어있습니다. 원래의 메시지는 평범한 영어 문장임을 힌트로 삼아서 암호문을 해독하고, 원문에 포함된 모든 ASCII 코드 값의 총합을 구하세요.
일반적인 문장에서의 알파벳의 빈도 수를 추측하여 문제를 해결한다… 라고 생각해서 알파벳 ‘e’가 가장 많이 나올 것이라 추측하면 오산.
일반적인 문장에서는 ‘띄어쓰기’가 가장 많이 나온다.
참고로 복호화하여 나오는 문장은 다음과 같다.
(The Gospel of John, chapter 1) 1 In the beginning the Word already existed. He was with God, and he was God. 2 He was in the beginning with God. 3 He created everything there is. Nothing exists that he didn’t make. 4 Life itself was in him, and this life gives light to everyone. 5 The light shines through
the darkness, and the darkness can never extinguish it. 6 God sent John the Baptist 7 to tell everyone about the light so that everyone might believe because of his testimony. 8 John himself was not the light; he was only a witness to the light. 9 The one who is the true light, who gives light to everyone,
was going to come into the world. 10 But although the world was made through him, the world didn’t recognize him when he came. 11 Even in his own land and among his own people, he was not accepted. 12 But to all who believed him and accepted him, he gave the right to become children of God. 13 They are rebo
rn! This is not a physical birth resulting from human passion or plan, this rebirth comes from God.14 So the Word became human and lived here on earth among us. He was full of unfailing love and faithfulness. And we have seen his glory, the glory of the only Son of the Father.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
#!/usr/bin/env perl use 5.010; use strict; use warnings; #명령행 인자로 파일 이름 넘겨줄 것. my @a; my @p; my $r = 0; @a = split /,/, $_ while (<>); push @{$p[$_%3]}, $a[$_] for (0..$#a); for (0..2) { my @u = @{$p[$_]}; my $k = k(@{$p[$_]}); for (0..$#u) { $u[$_] = $k^$u[$_]; $r += $u[$_]; } @{$p[$_]} = @u; } say $r; sub k { my %h; for (@_) { $h{$_} = 1 if not defined $h{$_}; $h{$_}++ if defined $h{$_}; } my $t = 0; my $v; for (keys %h) { if ($h{$_} > $t) { $t = $h{$_}; $v = $_; } } return $v^ord(" "); } |
숫자를 1부터 시작해서 하나씩 늘려가며 아래와 같이 시계반대방향으로 감아가면 한 변의 크기가 7인 정사각형 소용돌이가 만들어집니다.
37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18 5 4 3 12 29
40 19 6 1 2 11 28
41 20 7 8 9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49우하단 대각선쪽으로 홀수 제곱수(9, 25, 49)들이 늘어서 있는 것이 눈에 띕니다만, 더 흥미로운 사실은 양 대각선상에 놓인 13개의 숫자 중 8개가 소수라는 것입니다. 그 비율은 대략 8/13 ≈ 62% 정도가 됩니다.
이런 식으로 계속 소용돌이를 만들어갈 때, 양 대각선상의 소수 비율이 처음으로 10% 미만이 되는 것은 언제입니까? 정사각형 한 변의 크기로 답하세요.
2차원 배열을 이용하여 문제를 풀 수도 있겠지만, 모든 값들을 계속 저장하고 있을 필요가 없기 때문에 수열처럼 각 대각선상의 수를 차례대로 얻는 식을 구해 이용했다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#!/usr/bin/env perl use 5.010; use strict; use warnings; use Math::Prime::Util ':all'; my $n = 1; my $c = 1; my ($p, $q) = (0, 1); while (1) { for (1..4) { $n += 2*$c; if (is_prime($n)) { $p++; } else { $q++; } } if ($p/($p+$q) < 0.1) { say 2*$c+1; exit; } $c++; } |
제곱근 2는 다음과 같은 연분수의 형태로 나타낼 수 있습니다.
√ 2 = 1 + 1/(2 + 1/(2 + 1/(2 + … ))) = 1.414213…
위 식을 처음부터 한 단계씩 확장해 보면 아래와 같습니다.
1 + 1/2 = 3/2 = 1.5
1 + 1/(2 + 1/2) = 7/5 = 1.4
1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666…
1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379…그 다음은 99/70, 239/169, 577/408 로 확장이 되다가, 여덟번째인 1393/985 에 이르면 처음으로 분자의 자릿수가 분모의 자릿수를 넘어섭니다.
처음부터 1천번째 단계까지 확장하는 중에, 분자의 자릿수가 분모보다 많아지는 경우는 몇 번이나 됩니까?
처음에는 마법의 함수 eval로 어떻게든 해보려고 했지만, 왠지 찜찜해서 eval을 사용하지 않는 쪽으로 코드를 고쳤다.
분수 덧샘과 나눗셈을 하는 함수를 구현해서 풀었다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
#!/usr/bin/env perl use 5.010; use strict; use warnings; use Math::BigInt; my $c = 0; my ($k, $K) = (Math::BigInt->new(1), Math::BigInt->new(2)); my ($o, $t) = (Math::BigInt->new(1), Math::BigInt->new(2)); for (1..1000) { ($k, $K) = dv(($o, $o), sm(($t, $o), ($k, $K))); my ($n, $N) = sm(($o, $o), ($k, $K)); $c++ if (length($n->bstr()) > length($N->bstr())); } say $c; sub sm { my($a, $A, $b, $B) = @_; return ((Math::BigInt->new($a)->bmul(Math::BigInt->new($B)))->badd(Math::BigInt->new($b)->bmul(Math::BigInt->new($A))), Math::BigInt->new($A)->bmul(Math::BigInt->new($B))) } sub dv{ my($a, $A, $b, $B) = @_; return ((Math::BigInt->new($a)->bmul(Math::BigInt->new($B))), (Math::BigInt->new($b)->bmul(Math::BigInt->new($A)))) } |
구골(googol)은 10100을 일컫는 말로, 1 뒤에 0이 백 개나 붙는 어마어마한 수입니다.
100100은 1 뒤에 0이 2백 개가 붙으니 상상을 초월할만큼 크다 하겠습니다.
하지만 이 숫자들이 얼마나 크건간에, 각 자릿수를 모두 합하면 둘 다 겨우 1밖에 되지 않습니다.a, b < 100 인 자연수 ab 에 대해서, 자릿수의 합이 최대인 경우 그 값은 얼마입니까?
사실 구골하면 구글밖에 생각이 안나지만…
무튼 간단한 문제다. 포럼에서는 갑자기 코드 골프가 되어버려 참전하고 싶었지만 내 펄 스킬이 너무 낮아 감히 도전하지 못했다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
#!/usr/bin/env perl use 5.010; use strict; use warnings; use Math::BigInt; my $d = 0; for my $i (1..100) { for my $j (1..100) { my $t = 0; $t += $_ for (split(//, Math::BigInt->new($i)->bpow($j)->bstr())); $d = $t if ($d < $t); } } say $d; |
47이란 숫자를 골라서 뒤집은 다음 다시 원래 수에 더하면, 47 + 74 = 121 과 같이 대칭수(palindrome)가 됩니다.
물론 모든 숫자가 이토록 쉽게 대칭수를 만들어내지는 않습니다. 예를 들어 349의 경우,349 + 943 = 1292
1292 + 2921 = 4213
4213 + 3124 = 7337위에서 보는 것처럼 3번의 반복과정을 거쳐야 대칭수가 됩니다.
196과 같은 몇몇 숫자들은 이와 같은 과정을 아무리 반복해도 대칭수가 되지 않을 것이라고 추측되는데, 이런 수를 라이크렐 수 (Lychrel number) 라고 부릅니다. 아직 증명되지는 않았지만, 문제 풀이를 위해서 일단 라이크렐 수가 존재한다고 가정을 하겠습니다.
또한 1만 이하의 숫자들은, 50번 미만의 반복으로 대칭수가 되든지 라이크렐 수이든지 둘 중 하나라고 합니다.
1만을 넘어서면 10677에 이르렀을 때 비로소 53번의 반복으로 4668731596684224866951378664 라는 28자리의 대칭수가 만들어집니다.그러면 1만 이하에는 몇 개의 라이크렐 수가 존재합니까?
굳이 Math::BigInt를 사용하지 않아도 정답은 나오지만, 경고 투성이인 터미널을 보기 안타까워 BigInt를 썼는데…
이상하게도 a==b 으로 할 때와 a-b==0 으로 할 때가 달라서 한참 멘붕.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
#!/usr/bin/env perl use 5.010; use strict; use warnings; use Math::BigInt; my $c = 0; for (1..10000) { my $n = Math::BigInt->new($_); for (1..50) { $n->badd(Math::BigInt->new(scalar reverse $n->bstr())); last if ($n == Math::BigInt->new(scalar reverse $n->bstr())); $c++ if ($_ == 50); } } say $c; |
포커라는 카드게임은 다섯 장으로 된 패의 높고 낮음에 따라 승부를 냅니다. (포커 규칙을 이미 아는 분이라면 규칙 설명 부분은 건너뛰셔도 좋습니다)
카드 한 장은 아래와 같은 순서대로 값이 높아집니다.
2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A
다섯 장으로 이루어진 패의 계급(세칭 “족보”)은, 낮은 것부터 높은 순서로 아래와 같습니다.
- High Card : 가장 높은 카드의 값으로 비교.
- One Pair : 한 쌍이 같은 카드.
- Two Pairs : 서로 다른 두 쌍이 같은 카드.
- Three of a Kind : 세 장이 같은 카드.
- Straight : 모든 카드가 연속된 숫자.
- Flush : 모든 카드의 무늬가 같음.
- Full House : 세 장이 같고, 또 한 쌍이 같음 (Three of a Kind + One Pair).
- Four of a Kind : 네 장이 같은 카드.
- Straight Flush : 모든 카드가 연속된 숫자이면서 무늬도 같음.
- Royal Flush : 10, J, Q, K, A가 무늬도 같음.
두 사람의 패가 같은 종류의 계급이라면, 계급을 구성하는 카드 중 높은 쪽을 쥔 사람이 이깁니다. 예를 들면 8 원페어는 5 원페어를 이깁니다.
계급을 이루는 카드 숫자까지 같으면 (예: 둘 다 Q 원페어), 다른 카드를 높은 순서대로 비교해서 승부를 정합니다.텍스트파일 poker.txt 에는 두 선수가 벌인 1,000회의 승부가 저장되어 있습니다. (우클릭해서 다운로드 받으세요)
한 줄에는 10장의 카드가 공백으로 분리되어 들어있는데, 앞의 다섯 장은 1번 선수 것이고 뒤의 다섯 장은 2번 선수의 패입니다. 잘못되거나 중복된 데이터는 없으며, 무승부도 없습니다.카드 숫자는 2, 3, … , 9, T, J, Q, K, A 로 (숫자 10은 T로 표시),
무늬는 C (Club – ♣), D (Diamond – ♦), H (Heart – ♥), S (Spade – ♠) 로 표시되어 있습니다.
예를 들면 3C 3D 3S 9S 9D 의 경우 3 풀하우스가 됩니다.이 데이터를 분석하고, 1번 선수가 이긴 횟수를 구하세요.
참 문제가 길다.
포커 규칙에 따라서 핸드에 있는 패의 점수를 부여하고, 두 사람의 핸드를 비교해서 이긴사람을 구하는 방식으로 문제를 해결 할 수 있을 것이다.
물론 점수를 부여하는 함수를 만드는 부분이 매우 귀찮은(…) 부분이 될 것 같았다.
첫 프로젝트 오일러 시작에서 설명했던 것과 같이, 나는 함수 구현보다 문제를 푼다는 것에 집중하기로 했으므로, 모듈을 찾아봤다.
그 결과 아주 적절한 Games::Cards::Poker 모듈을 발견하여 사용하기로 했다.
내가 원하는 함수가 모두 구현되어 있었으므로, 아주 간단했다.
추가로, 이전까지는 문제에서 주어진 데이터를 코드에 직접 삽입하여 문제풀이를 하였으나, 이번 파일부터 그 크기가 감당할 수 없이 커져버렸다.
따라서 외부 파일에서 데이터를 불러와 사용하기로 하였는데, 나는 명령행 인자로 파일 경로를 넘겨주는 방식으로 구현했다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
#!/usr/bin/env perl use 5.010; use strict; use warnings; use Games::Cards::Poker; #명령행 인자로 파일 이름 넘겨줄 것. my $c = 0; while (<>) { my @a = split(/ /, $_); $c++ if (ScoreHand(@a[0..4]) < ScoreHand(@a[5..9])); } say $c; |
1,2,3,4,5 다섯 숫자 중에서 세 개를 고르는 것에는 다음과 같은 10가지 경우가 있습니다.
123, 124, 125, 134, 135, 145, 234, 235, 245, 345
조합론이라는 분야에서는 이것을 5C3 = 10 이라고 표시하며, 일반적인 식은 아래와 같습니다.
nCr =
r!(n−r)!, 단 r ≤ n 이고, n! = n×(n−1)×…×3×2×1 이며 0! = 1. 이 값은 n = 23 에 이르러서야 23C10 = 1144066 으로 처음 1백만을 넘게 됩니다.
1 ≤ n ≤ 100 일때 nCr의 값이 1백만을 넘는 경우는 모두 몇 번입니까? (단, 중복된 값은 각각 계산합니다)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
#!/usr/bin/env perl use 5.010; use strict; use warnings; use Math::NumSeq::Factorials; my $s = Math::NumSeq::Factorials->new; my $c = 0; for my $n (1..100) { for my $r (1..$n) { $c++ if (1000000 < $s->ith($n)/(($s->ith($r)*($s->ith($n-$r))))); } } say $c; |
125874를 2배 하면 251748이 되는데, 이 둘은 같은 숫자로 이루어져 있고 순서만 다릅니다.
2배, 3배, 4배, 5배, 6배의 결과도 같은 숫자로 이루어지는 가장 작은 수는 무엇입니까?
사실 내 부족한 수학적 직관으로도 1/7과 관계가 있을거라 짐작을 하긴 했지만…
아무튼 문제는 그냥 풀었다. 오랫만에 쉬운 문제.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
#!/usr/bin/env perl use 5.010; use strict; use warnings; my $n = 0; while (++$n) { for (2..6) { last if (join("", sort split(//, $n)) ne join("", sort split(//, $n*$_))); if ($_ == 6) { say $n; exit; } } } |
두 자리 숫자 *3의 첫번째 자리를 여러가지로 바꿨을 때 가능한 아홉 가지의 결과 중에서 13, 23, 43, 53, 73, 83의 여섯 개는 소수입니다.
56**3 의 3번째와 4번째 자리를 동일한 숫자로 바꿔서 만들어지는 10개의 다섯자리 숫자 중에서는 아래에서 보듯이 7개가 소수가 되며, 이것은 이런 식으로 7개의 소수가 만들어지는 첫번째 경우입니다. 이 소수 집단의 첫번째 수인 56003은 이런 성질을 갖는 가장 작은 소수입니다.
56003, 56113, 56333, 56443, 56663, 56773, 56993
위의 예처럼 원래의 일부를 동일한 숫자로 치환했을 때 8개의 소수 집단이 만들어지는 경우를 찾고, 그 집단에 속한 가장 작은 소수를 구하세요.
치환하는 자리는 인접하지 않아도 되고, 가장 앞부분을 치환하는 경우 거기에 0은 올 수 없습니다.
이래저래 고생을 좀 한 문제.
자꾸 120383이 나오는데 이게 오답이여서 왜 그럴까 왜 그럴까 고심했다.
실행 소요시간은 약 10초
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
#!/usr/bin/env perl use 5.010; use strict; use warnings; use Math::Prime::Util ':all'; use List::PowerSet 'powerset_lazy'; my $n = 0; while($n = next_prime($n)) { my @a = split(//, $n); my $p = powerset_lazy(0..$#a); while(my $set = $p->()) { my $c = 0; next if ($#{$set} == -1 or $#{$set} == $#a); for my $i (0..9) { next if ($i == 0 and ${$set}[0] == 0); my @t = @a; for (@{$set}) { $t[$_] = $i; } $c++ if (is_prime(join("", @t))); } if ($c >= 8) { for my $i (0..9) { next if ($i == 0 and ${$set}[0] == 0); my @t = @a; for (@{$set}) { $t[$_] = $i; } say join("", @t) if (is_prime(join("", @t))); exit; } } } } |