読者です 読者をやめる 読者になる 読者になる

初代Masteries

きっとモヒカンにもなれないお前たちに告げる!!!

Project Euler - Problem 24

Problem 24

30までは頑張りたいです(震え声).

今回の問題は, 0..9からなる順列をソートして並べたときの100万番目を求める問題です.
forループを延々と回してもよいのですが, 時間がかかりそうですしシンプルではないので, こういう風に考えてみました.

9! = 362880なので, 先頭が0の順列は1〜362880番目まで, 先頭が1の順列は362881〜725760番目まで, 先頭が2の順列は725761〜1088640番目まで... と考えることができます.
なので, 先頭は2になるはずです.

...とまあ, こういう感じでそれぞれの桁に該当する数値を求めていきました.

use strict;
use warnings;

my @used_number = qw/0 0 0 0 0 0 0 0 0 0/;
search(1, 9);

sub search {
    my ($n, $pos) = @_;

    my @enable = enable_number();
    if ( $pos == 0 ) {
        print "$enable[0]\n";
        return;
    }

    my $f = factorial($pos);
    my $count = 0;

    while ( $n + $f <= 1_000_000 ) {
        $n += $f;
        $count++;
    }

    my $output = $enable[$count];
    print $output;
    $used_number[$output] = 1;

    sieve($n, $pos-1);
}

sub enable_number {
    return (grep { $used_number[$_] == 0 } (0..9) );
}

sub factorial {
    my $n = shift;

    my $f = 1;
    $f *= $_ for 1..$n;

    return $f;
}

多分もっとシンプルに書けるんだろうなあ...

あと, サブルーチンや変数が増えてきた時の名づけ方がまだまだ微妙ですね.
もう一度リーダブルコードを熟読しようと思います...