Programming – 페이지 2

프로젝트 오일러 54번

2013/09/21
Perl

포커라는 카드게임은 다섯 장으로 된 패의 높고 낮음에 따라 승부를 냅니다. (포커 규칙을 이미 아는 분이라면 규칙 설명 부분은 건너뛰셔도 좋습니다)

카드 한 장은 아래와 같은 순서대로 값이 높아집니다.

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 모듈을 발견하여 사용하기로 했다.
내가 원하는 함수가 모두 구현되어 있었으므로, 아주 간단했다.

추가로, 이전까지는 문제에서 주어진 데이터를 코드에 직접 삽입하여 문제풀이를 하였으나, 이번 파일부터 그 크기가 감당할 수 없이 커져버렸다.
따라서 외부 파일에서 데이터를 불러와 사용하기로 하였는데, 나는 명령행 인자로 파일 경로를 넘겨주는 방식으로 구현했다.

#!/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;

#!/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;

프로젝트 오일러 53번

2013/09/21
Perl

1,2,3,4,5 다섯 숫자 중에서 세 개를 고르는 것에는 다음과 같은 10가지 경우가 있습니다.

123, 124, 125, 134, 135, 145, 234, 235, 245, 345

조합론이라는 분야에서는 이것을 ₅C₃ = 10 이라고 표시하며, 일반적인 식은 아래와 같습니다.

_nC_r =
n!
r!(n−r)!
, 단 r ≤ n 이고, n! = n×(n−1)×…×3×2×1 이며 0! = 1.

이 값은 n = 23 에 이르러서야 ₂₃C₁₀ = 1144066 으로 처음 1백만을 넘게 됩니다.

1 ≤ n ≤ 100 일때 _nC_r의 값이 1백만을 넘는 경우는 모두 몇 번입니까? (단, 중복된 값은 각각 계산합니다)

#!/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;

#!/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;

프로젝트 오일러 52번

2013/09/20
Perl

125874를 2배 하면 251748이 되는데, 이 둘은 같은 숫자로 이루어져 있고 순서만 다릅니다.

2배, 3배, 4배, 5배, 6배의 결과도 같은 숫자로 이루어지는 가장 작은 수는 무엇입니까?

사실 내 부족한 수학적 직관으로도 ¹/₇과 관계가 있을거라 짐작을 하긴 했지만…
아무튼 문제는 그냥 풀었다. 오랫만에 쉬운 문제.

#!/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;
        }
    }
}

#!/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;

}

프로젝트 오일러 51번

2013/09/20
Perl

두 자리 숫자 *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초

#!/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;
            }
        }
    }
}

#!/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;

}

프로젝트 오일러 50번

2013/09/18
Perl

41은 소수이면서 다음과 같은 6개의 연속된 소수의 합으로도 나타낼 수 있습니다.

41 = 2 + 3 + 5 + 7 + 11 + 13

이것은 100 이하에서는 가장 길게 연속된 소수의 합으로 이루어진 소수입니다.

1000 이하에서는 953이 연속된 소수 21개의 합으로 가장 깁니다.

1백만 이하에서는 어떤 소수가 가장 길게 연속되는 소수의 합으로 표현될 수 있습니까?

백만 이하의 소수를 모두 구해 배열에 넣어 놓고 구하자.

#!/usr/bin/env perl
use 5.010;
use strict;
use warnings;
use Math::Prime::Util ':all';

my @p = @{primes(1000000)};
my $n = 0;
my $d = 0;

for my $i (0..$#p) {
    my $t = 0;
    for my $j (0..$#p) {
        last if not defined $p[$i+$j];
        $t += $p[$i+$j];
        last if ($t > 1000000); 
        if (is_prime($t) and $d < $j) {
            $n = $t;
            $d = $j;
        }
    }
}

say $n;

#!/usr/bin/env perl

use 5.010;

use strict;

use warnings;

use Math::Prime::Util ':all';

my @p = @{primes(1000000)};

my $n = 0;

my $d = 0;

for my $i (0..$#p) {

my $t = 0;

for my $j (0..$#p) {

last if not defined $p[$i+$j];

$t += $p[$i+$j];

last if ($t > 1000000);

if (is_prime($t) and $d < $j) {

$n = $t;

$d = $j;

}

say $n;

프로젝트 오일러 49번

2013/09/18
Perl

1487, 4817, 8147은 3330씩 늘어나는 등차수열입니다. 이 수열에는 특이한 점이 두 가지 있습니다.

세 수는 모두 소수입니다.

세 수는 각각 다른 수의 자릿수를 바꿔서 만들 수 있는 순열(permutation)입니다.

1자리, 2자리, 3자리의 소수 중에서는 위와 같은 성질을 갖는 수열이 존재하지 않습니다. 하지만 4자리라면 위엣것 말고도 또 다른 수열이 존재합니다.

그 수열의 세 항을 이었을 때 만들어지는 12자리 숫자는 무엇입니까?

등차수열인 세 소수를 구해 순열인지 확인했다.

#!/usr/bin/env perl
use 5.010;
use strict;
use warnings;
use Math::Prime::Util ':all';

my @p = @{primes(1000, 9999)};

for my $i (@{primes(1000, 9999)}) {
    for my $j (@{primes($i+1, ($i+9999)/2)}) {
        my $k = $j*2-$i;
        if (is_prime($k) and f($i) eq f($j) and f($j) eq f($k)) {
			next if ($i.$j.$k == "148748178147"); //문제에서 주어진 값
            say $i.$j.$k;
        }
    }
}

sub f {
    return join("", sort split (//, shift));
}

#!/usr/bin/env perl

use 5.010;

use strict;

use warnings;

use Math::Prime::Util ':all';

my @p = @{primes(1000, 9999)};

for my $i (@{primes(1000, 9999)}) {

for my $j (@{primes($i+1, ($i+9999)/2)}) {

my $k = $j*2-$i;

if (is_prime($k) and f($i) eq f($j) and f($j) eq f($k)) {

next if ($i.$j.$k == "148748178147"); //문제에서 주어진 값

say $i.$j.$k;

}

sub f {

return join("", sort split (//, shift));

}

프로젝트 오일러 48번

2013/09/18
Perl

1¹ + 2² + 3³ + … + 10¹⁰ = 10405071317 입니다.

1¹ + 2² + 3³ + … + 1000¹⁰⁰⁰ 의 마지막 10자리 숫자는 무엇입니까?

Math::BigInt를 이용하여 구했다.
사실 마지막 10자리만 끊어서 계산해도 무방하지만, 약 10초 내로 결과가 나오기에 그냥 풀기로 했다.

#!/usr/bin/env perl
use 5.010;
use strict;
use warnings;
use Math::BigInt;

my $n = Math::BigInt->bzero(); 
for (1..1000) {
    my $t = Math::BigInt->new($_);
    $t->bpow($t);
    $n->badd($t);
}

say substr($n->bstr(), -10);

#!/usr/bin/env perl

use 5.010;

use strict;

use warnings;

use Math::BigInt;

my $n = Math::BigInt->bzero();

for (1..1000) {

my $t = Math::BigInt->new($_);

$t->bpow($t);

$n->badd($t);

}

say substr($n->bstr(), -10);

프로젝트 오일러 47번

2013/09/18
Perl

서로 다른 두 개의 소인수를 갖는 수들이 처음으로 두 번 연달아 나오는 경우는 다음과 같습니다.

14 = 2 × 7
15 = 3 × 5

서로 다른 세 개의 소인수를 갖는 수들이 처음으로 세 번 연속되는 경우는 다음과 같습니다.

644 = 2² × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19

서로 다른 네 개의 소인수를 갖는 수들이 처음으로 네 번 연속되는 경우를 찾으세요. 그 첫번째 숫자는 얼마입니까?

해쉬를 이용하여 좀 더 빠르게 구한다.

#!/usr/bin/env perl
use 5.010;
use strict;
use warnings;
use Math::Prime::Util ':all';

my $n = 0;
while (++$n) {
    if (f($n) == 4 and f($n+1) == 4 and f($n+2) == 4 and f($n+3) == 4) {
        say $n;
        exit;
    }
}

my %h;

sub f {
    my $n = shift;
    return $h{$n} if defined $h{$n};
        
    my ($i, %s, @r);
    foreach my $i (factor($n)) {
        push(@r, $i) unless $s{$i}++;
    }
    $h{$n} = $#r+1;
    return $#r+1;
}

#!/usr/bin/env perl

use 5.010;

use strict;

use warnings;

use Math::Prime::Util ':all';

my $n = 0;

while (++$n) {

if (f($n) == 4 and f($n+1) == 4 and f($n+2) == 4 and f($n+3) == 4) {

say $n;

exit;

}

my %h;

sub f {

my $n = shift;

return $h{$n} if defined $h{$n};

my ($i, %s, @r);

foreach my $i (factor($n)) {

push(@r, $i) unless $s{$i}++;

}

$h{$n} = $#r+1;

return $#r+1;

}

프로젝트 오일러 46번

2013/09/18
Perl

크리스티안 골드바흐는 모든 홀수인 합성수를 (소수 + 2×제곱수)로 나타낼 수 있다고 주장했습니다.

9 = 7 + 2×1²
15 = 7 + 2×2²
21 = 3 + 2×3²
25 = 7 + 2×3²
27 = 19 + 2×2²
33 = 31 + 2×1²

이 추측은 잘못되었음이 밝혀졌습니다.

위와 같은 방법으로 나타낼 수 없는 가장 작은 홀수 합성수는 얼마입니까?

우변의 2×제곱수 항을 좌변으로 넘겨, 좌변이 소수인지 확인한다.

#!/usr/bin/env perl
use 5.010;
use strict;
use warnings;
use Math::Prime::Util ':all';

my $n = 3;
while ($n += 2) {
    next if is_prime($n);
    my $a = 1;
    my $b = 0;
    while ($n-2*$a**2>1) {
        if (is_prime($n-2*$a**2)) {
            $b = 1;
            last;
        }
        $a++;
    }
    if (!$b) {
        last;
    }
}

say $n;

#!/usr/bin/env perl

use 5.010;

use strict;

use warnings;

use Math::Prime::Util ':all';

my $n = 3;

while ($n += 2) {

next if is_prime($n);

my $a = 1;

my $b = 0;

while ($n-2*$a**2>1) {

if (is_prime($n-2*$a**2)) {

$b = 1;

last;

}

$a++;

}

if (!$b) {

last;

}

say $n;

프로젝트 오일러 45번

2013/09/17
Perl

삼각수, 오각수, 육각수는 아래 식으로 구할 수 있습니다.

삼각수 T_n = n (n + 1) / 2 1, 3, 6, 10, 15, …

오각수 P_n = n (3n − 1) / 2 1, 5, 12, 22, 35, …

육각수 H_n = n (2n − 1) 1, 6, 15, 28, 45, …

여기서 T₂₈₅ = P₁₆₅ = H₁₄₃ = 40755 가 됩니다.

오각수와 육각수도 되는, 그 다음으로 큰 삼각수를 구하세요.

이전 44번 문제를 풀었다면, n각수 판별식을 쉽게 만들 수 있다. 이를 이용하면 된다.

이 때, 변수가 정수인지 판별하는 함수가 필요한데, Scalar::Util::Numeric 모듈의 isint 함수를 사용해도 되겠지만, 정규식을 이용하여 판별하여도 성능상 크게 관계가 없다.

#!/usr/bin/env perl
use 5.010;
use strict;
use warnings;

my $c = 285;
while($c++) {
    my $n = $c*($c+1)/2;
    if (((1+sqrt(1+24*$n))/6) =~ m/^d+$/ and ((1+sqrt(1+8*$n))/4) =~ m/^d+$/){
        say $n;
        exit;
    }
}

#!/usr/bin/env perl

use 5.010;

use strict;

use warnings;

my $c = 285;

while($c++) {

my $n = $c*($c+1)/2;

if (((1+sqrt(1+24*$n))/6) =~ m/^d+$/ and ((1+sqrt(1+8*$n))/4) =~ m/^d+$/){

say $n;

exit;

}

blog.update.sh

이 블로그는 더 이상 업데이트되지 않습니다.

Programming (77)

프로젝트 오일러 54번

프로젝트 오일러 53번

프로젝트 오일러 52번

프로젝트 오일러 51번

프로젝트 오일러 50번

프로젝트 오일러 49번

프로젝트 오일러 48번

프로젝트 오일러 47번

프로젝트 오일러 46번

프로젝트 오일러 45번

카테고리

보관함

최신 글

최신 댓글

메타