正しい文(クイズ) in Perl DouKaku?

「この文は0が□個，1が□個，...，9が□個あります」
が正しくなるように□を埋めてください．数値は10進数とします．
一般のn(<=16で可)進数でも解いてみてください．

たとえば2進数なら
「この文は0が11個，1が100個あります」
となります．

まず問題ですが、

> が正しくなるように□を埋めてください．数値は10進数とします．

はn進数の間違いですよね。

以上を踏まえて、お代を忠実にコードしたらそのまま解けました。Regexpを使っているのがポイントかな。一秒といわず瞬殺です。

出力フォーマットは、#4382(http://ja.doukaku.org/comment/4382/)のものを採用していますが、日本語化は`sentenceed()`と`solve()`の該当箇所を変えるだけでOK.

Dan the Perl Monger

#!/usr/local/bin/perl
use strict;
use warnings;

my @digits = ( '0' .. '9', 'a' .. 'z' );

sub n2s {
    use integer;
    my ( $n, $b ) = @_;
    my $s = $digits[ $n % $b ];
    $s = $digits[ $n % $b ] . $s while ( $n /= $b );
    $s;
}

sub sentenceed {
    my $b = shift;
    join( ",", map { "$_*1" } @digits[ 0 .. $b - 1 ] );
}

sub count {
    my ( $s, $d ) = @_;
    my $c = ( eval qq{\$s =~ y/$d/$d/} );
    $c;
}

sub solve {
    my $b    = shift;
    my $ans  = sentenceed($b);
    my $nans = '';
    while ( $ans ne $nans ) {
        $nans = $ans;
        $ans =~ s{([0-9a-z])\*[0-9a-z]+}{
            my $d = $1;
            my $c = n2s(count($ans, $d), $b);
            qq($d*$c)
        }egx;
    }
    $ans;
}

print "base($_):", solve($_), "\n" for ( 2 .. (shift||16) );

rucker氏の漸近アプローチのパクリです（解いてから気づいたorz）。
関数を自力実装してる分やたらと長い。

see:

#!perl

use strict;
use warnings;

my @i2s_table = ("0".."9", "a".."f");
my %s2i_table = ();
@s2i_table{"0".."9", "a".."f"} = 0..15;

for my $n (2..16) {
  my %answer = solve($n);
  my @answers = ();

  for my $key (sort { hex('0x' . $a) <=> hex('0x' . $b) } keys %answer) {
    push @answers, "$keyが" . int2str($answer{$key}, $n) . "個";
  }
  print "この文は ", join(", ", @answers), "あります\n";
}

sub hash_equals(\%\%) {
  my ($lhs, $rhs) = @_;

  return 0 if scalar(keys %$lhs) != scalar(keys %$rhs);
  for my $key (keys %$lhs) {
    return 0 unless exists $rhs->{$key};
    return 0 if $lhs->{$key} != $rhs->{$key};
  }

  return 1;
}

sub solve {
  my $n = shift;
  my @chars;
  my (%init, %count, %new_count);
  $init{int2str($_, $n)} = 1 for 0..($n - 1);
  %new_count = %init;

  do {
    %count = %new_count;
    %new_count = %init;

    @chars = ();
    push @chars, split //, int2str($_, $n) for values %count;
    $new_count{$_}++ for @chars;
  } until (hash_equals(%count, %new_count));

  return %new_count;
}

sub int2str {
  my ($num, $n) = @_;

  return $num < $n
    ? $i2s_table[$num]
      : int2str(int $num / $n, $n) . $i2s_table[$num % $n];
}

sub str2int {
  my ($str, $n) = @_;
  my $result = 0;

  for my $c (split //, $str) {
    $result *= $n;
    $result += $s2i_table{$c};
  }

  return $result;
}

DouKaku?

正しい文(クイズ)

Posted feedbacks - Perl

Index

Feed

Other

Link

Pathtraq