Project Euler - Problem 24

問題

原文

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?
日本語訳

0,1,2,3,4,5,6,7,8,9からなる順列を辞書式に並べたときの100万番目を答えよ

解答

n (> 0)桁目の数字が決まると残りの数字の順列は(n - 1)!通りですから、一般にn桁の順列の（0から数えて）m番目というとき、m = p_n(n - 1)! + p_n-1(n - 2)! + ... + p₁(0)! (0 <= p_i < i)と表すと、p_n, p_n-1, ..., p₁の値は一意に定まります。よってn桁目の数字を決めるとき、その時点で使える数字を昇順に並べた中からp_n番目の数字を選ぶという操作をn = 1まで繰り返すことで解が得られます。

(use srfi-1)

(define (factorial n) (apply * (iota n 1)))

(define (solve)
  (define (solve-1 n digits acc)
    (if (null? digits) (list->string (map integer->digit (reverse acc)))
        (let* ((fact (factorial (- (length digits) 1)))
               (mult (floor (/ n fact)))
               (digit (ref digits mult))
               (rest (remove (cut = digit <>) digits)))
          (solve-1 (- n (* fact mult)) rest (cons digit acc)))))
  (solve-1 (- 1000000 1) (iota 10) '()))

(define (main argv)
  (display (solve))
  (newline))

このブログの人気の投稿

Perl の新 class 構文を使ってみる

Perl 5 のオブジェクト指向機能は基本的には Python の影響を受けたものだが、データを名前空間 (package) に bless する機構だけで Perl 4 以来の名前空間とサブルーチンをそのままクラスとメソッドに転換し第一級のオブジェクト指向システムとした言語設計は驚嘆に価する。実際この言語のオブジェクトシステムは動的型付言語のオブジェクト指向プログラミングに要求されるおよそあらゆる機能を暗にサポートしており、CPAN には Moose を筆頭とした屋下屋オブジェクトシステムが複数存在しているがその多くは Pure Perl ライブラリである。つまり「やろうと思えば全部手書きで実現できる」わけである。そういうわけで Perl のオブジェクト指向プログラミングサポートは機能面では (静的型検査の不在という現代的には極めて重大な欠如を除けば) 申し分ないのだが、しかし Moose その他の存在が示しているように一つ明らかな欠点がある。記述の冗長さだ。コンストラクタを含むあらゆるメソッドは第一引数としてレシーバを受ける単なるサブルーチンとして明示的に書く必要があるし、オブジェクトのインスタンス変数 (a.k.a. プロパティ / データメンバ) は bless されたデータに直接的ないし間接的にプログラマ定義の方法で格納されるためアクセス手段は実装依存である。これはカプセル化の観点からは望ましい性質だが、他者の書いたクラスを継承するときに問題となる。ある日データ表現を変更した親クラスがリリースされると突然自分の書いた子クラスが実行時エラーを起こすようになるわけだ。そうならないためにはインスタンス変数へのアクセスに (protected な) アクセサを使う必要があるのだが、そのためには親クラスが明示的にそれらを提供している必要があるし、そもそも Perl にはメソッドのアクセス修飾子というものがないので完全な制御を与えるならばオブジェクトの内部状態がすべて public になってしまう。そのような事情もあり、特にパフォーマンスが問題にならないようなアプリケーションコードでは Moose のようなリッチな語彙を提供するオブジェクトシステムを使うことが公式のチュートリアルでも推奨されてきた。Perl コアのオブジェクトシステムの改良は...

去る6月に Perl 5.32.0 がリリースされたので差分を把握するために perldelta を読んだ件

要旨 Perl 5 メジャーバージョンアップの季節がやって来たのでまともな Perl プログラマの嗜みとして perldelta を読んだ。今回は有り体に言えばルーティン的なリリースで、言語コアの拡張は他言語にも見られる構文が実験的に入ったくらいで大きな変化はない。新機能は RegExp の拡充が主である。比較的重要と思われる変更点を抜粋する。新機能 isa 演算子実験的機能。Python とか Java における isinstance とか instanceof 。これまでも UNIVERSAL::isa があったが、これはメソッドなのでレシーバにオブジェクトでもクラスでもない値 (i.e., 未定義値 / bless されていないリファレンス) を置くと実行時エラーが起きるのが問題だった: package Foo { use Moo; } package Bar { use Moo; extends ' Foo ' ; } package Baz { use Moo; } use feature qw/ say / ; sub do_something_with_foo_or_return_undef { my ( $foo ) = @_ ; # Returns safely if the argument isn't an expected instance, in mind. return unless $foo -> isa ( ' Foo ' ); ...; } # OK. do_something_with_foo(Bar->new); # |undef| is expected in mind, but actually error will be thrown. do_something_with_foo( undef ); これを避けるために今までは Scalar::Util::blessed を併用したりしていたわけだが、 isa 演算子は左辺が何であっても意味のある値を返すのでよりシンプルになる: # True +( bless +{} ...

Project Euler - Problem 35

問題原文 How many circular primes are there below one million? 日本語訳 100万未満の巡回素数は何個か? 解答回転させた数値がすべて素数ということは、すべての桁が奇数でなければいけません(ただし2を除く)。追記匿名氏にコメントでご指摘頂いたのでコードを一部修正しました。いずれかの桁に5がある場合も、回転させると必ず5の倍数が現れるので除外できます。もっと追記前の修正に間違いが入っているのをご指摘頂いたので修正しました。 5自体は素数なので、巻き添えで除外してはいけません。 #!/usr/bin/env perl use strict; use warnings; use feature qw/say state/; use List::MoreUtils qw/all none/; sub is_prime($) { state %memos; my $n = shift; return 0 if $n < 2; return 1 if $n == 2; return 1 if $n == 3; return $memos{$n} if exists $memos{$n}; $memos{$n} = none { $n % $_ == 0 } 2 .. sqrt $n; } sub rotate($) { my $n = shift; substr($n, 1) . substr($n, 0, 1); } sub rotations($) { my $n = shift; my %seen = ($n => 1); $seen{$n} = 1 until exists $seen{$n = rotate $n}; keys %seen; } sub is_circular_prime($) { state %memos; my $n = shift; return 0 if $n =~ /[024568]/ and $n != 2 and $n != 5; return $memos{$n} if exists $memos{$n}; my ...

LIBLINEAR 2.41 で One-class SVM が使えるようになったので Perl から触ってみよう

改訂 (Sep 15, 2020): 必要のない手順を含んでいたのでサンプルコードと記述を修正しました。 CPAN に Algorithm::LibLinear 0.22 がリリースされました (しました。) 高速な線形 SVM およびロジスティック回帰による複数の機械学習アルゴリズムを実装したライブラリである LIBLINEAR への Perl バインディングです。利用している LIBLINEAR のバージョンが LIBLINEAR 2.30 から LIBLINEAR 2.41 に上がったことで新しいソルバが追加され、One-class SVM (OC-SVM) による一値分類が利用可能になっています (しました。) OC-SVM って何一値分類を SVM でやること。一値分類って何ある値が学習したクラスに含まれるか否かを決定する問題。 HBO の「シリコンバレー」に出てきた「ホットドッグ」と「ホットドッグ以外」を識別するアプリが典型。「ホットドッグ以外」の方は犬でも神でも一つの指輪でも何でも含まれるのがミソ。二値分類の場合正反両者のデータを集める必要があるのに対して、一値分類の学習器は正例データのみしか要求しない (ものが多い。) 主な用途は外れ値検出で、もちろんホットドッグやホットドッグ様のものを検出したりもできる。使い方手順自体は他の二値ないし多値分類問題と同じです。つまり、訓練パラメータを決めて訓練データセットで訓練してテストデータセットで確度を検証して十分良くなったらモデルを保存するといういつもの流れ。訓練パラメータ use 5.032 ; use Algorithm::LibLinear ; my $learner = Algorithm::LibLinear ->new( epsilon => 0.01 , nu => 0.75 , solver => ' ONECLASS_SVM ' , ); solver => 'ONECLASS_SVM' が一値分類用のソルバです。LIBLINEAR の train コマンドで言うところの -s 21 。 OC-SVM の良いところは (ハイパー)...

Perl 7 より先に Perl 5.34 が出るぞという話

Perl 5 の次期バージョンとして一部後方互換でない変更 (主に間接オブジェクト記法の削除とベストプラクティスのデフォルトでの有効化) を含んだメジャーバージョンアップである Perl 7 がアナウンスされたのは昨年の 6 月のことだったが、その前に Perl 5 の次期周期リリースである Perl 5.34 が 5 月にリリース予定である。現在開発版は Perl 5.33.8 がリリースされておりユーザから見える変更は凍結、4 月下旬の 5.33.9 で全コードが凍結され 5 月下旬に 5.34.0 としてリリース予定とのこと。そういうわけで事前に新機能の予習をしておく。 8進数数値リテラルの新構文見た瞬間「マジかよ」と口に出た。これまで Perl はプレフィクス 0 がついた数値リテラルを8進数と見做してきたが、プレフィクスに 0o (zero, small o) も使えるようになる。もちろんこれは2進数リテラルの 0b や 16進数リテラルの 0x との一貫性のためである。リテラルと同じ解釈で文字列を数値に変換する組み込み関数 oct も` 新構文を解するようになる。昨今無数の言語に取り入れられているリテラル記法ではあるが、この記法の問題は o (small o) と 0 (zero) の区別が難しいことで、より悪いことに大文字も合法である： 0O755 Try / Catch 構文 Perl 5 のリリース以来 30 年ほど待たれた実験的「新機能」である。 Perl 5 における例外処理が特別な構文でなかったのは予約語を増やさない配慮だったはずだが、TryCatch とか Try::Tiny のようなモジュールが氾濫して当初の意図が無意味になったというのもあるかも知れない。 use feature qw/ try / ; no warnings qw/ experimental::try / ; try { failable_operation(); } catch ( $e ) { recover_from_error( $e ); } Raku (former Perl 6) だと CATCH (大文字なことに注意) ブロックが自分の宣言されたスコープ内で投げられた例外を捕らえる...

僕のIT革命

このブログを検索