perlで「増やす減らす2倍にする」に挑戦

ATNDフルカレンダーを見ていたら (オフラインリアルタイムどう書く)http://atnd.org/events/41603 という勉強会があって、そこに興味深い問題が載っていた。 こそで、perlにて「増やす減らす2倍にする」に挑戦してみたが・・・

初めて、Perlbeginnersでytnobodyさんも紹介していた、 関数のリファレンスというのを使ってみた。

package Counter;
use strict;
use warnings;

sub calc {

    my $final_value   = shift;
    my @results_array = ( [0] );
    my $index         = 0;

    my $add_1   = sub { my $val = shift; return ++$val; };
    my $multi_2 = sub { my $val = shift; return $val * 2; };
    my $sub_1   = sub { my $val = shift; return --$val; };

    my @operations = ( $add_1, $multi_2, $sub_1 );

    while (1) {
        my @p_results = @{$results_array[ $index++]};
        my @n_results = ();
        foreach my $p_result (@p_results) {

            for my $operation (@operations) {
                my $n_result = $operation->($p_result);
                if ( $final_value == $n_result ) {
                    return $index;
                }
                if ( $n_result > 0 ){
                    push (@n_results, $n_result);
                }
            }
        }
        push (@results_array, \@n_results);
    }
}

1;

しかし、性能が悪くてテストの途中でジッと待たないといけない。。。 とりあえず、同じ数になったら間引く処理を入れないとＮＧかな。

というわけで、同じ数は間引く処理を追加（以下）したら、何とかすべてのテストが通りました。

package Counter;
use strict;
use warnings;

sub calc {

    my $final_value   = shift;
    my @results_array = ( [0] );
    my %displayed_values = (0 => 1);
    my $index         = 0;

    my $add_1   = sub { my $val = shift; return ++$val; };
    my $multi_2 = sub { my $val = shift; return $val * 2; };
    my $sub_1   = sub { my $val = shift; return --$val; };

    my @operations = ( $add_1, $multi_2, $sub_1 );

    while (1) {
        my @p_results = @{$results_array[ $index++]};
        my @n_results = ();
        foreach my $p_result (@p_results) {

            for my $operation (@operations) {
                my $n_result = $operation->($p_result);
                if ( $final_value == $n_result ) {
                    return $index;
                }
                if ( $n_result > 0 && !defined($displayed_values{$n_result})){
                    push (@n_results, $n_result);
                    $displayed_values{$n_result} = 1;
                }
            }
        }
        push (@results_array, \@n_results);
    }
}

1;