CodeIQ に出した「4つの数と四則と括弧」の解説・解題

CodeIQ に「4つの数と四則と括弧」( https://codeiq.jp/ace/nabetani_takenori/q820 )という問題を出した。
挑戦の募集はすでに締めきっている。
というわけで、解説・解題。

で。
まずは問題

問題

■問題
4つの数と四則演算と括弧を使って数を作るというゲームがあります。
例えば、2, 3, 7, 8 なら、34, 24, 60, 12, 65 などの数を

238÷7 = 34

8÷(7÷3-2) = 24

(8-2)×(7+3) = 60

72÷8+3 = 12

28+37 = 65

などの方法で作ることができます。
しかし、54 や 95 などの数は、2, 3, 7, 8 を使って作ることができません。
以上をふまえて、2, 3, 7, 8 と四則演算・括弧をどう組み合わせても作ることができない正の整数で、100より小さいものをすべて挙げて下さい。
■詳細と注意事項

2, 3, 7, 8 の4つの数は、すべて一度ずつ使わなくてはいけません。二度以上使ってはいけませんし、使わない数があってもいけません。

演算子や括弧は何度でも使うことができます。

使える演算子は四則( +, -, ×, ÷ )のみです。指数や剰余は使えません。

例の通り、複数の数字を並べてひとつの数を作ることができます。たとえば、2 と 3を並べて 23 や 32 を作ることができます。

3÷2 は 1 ではなく、2分の3 です。

解答欄には、作ることができない整数で、1〜99 の範囲内のものを書いて下さい。

実装に使用する言語は自由ですが、ruby, C, C++, Java, JavaScript, groovy 以外の言語を使用した場合、惜しいかどうかの判断を諦めることがあります。

こんな感じ。

出題の背景と意図とか

子供の頃、切符を買って電車に乗ったとき。
切符に4桁の番号が書いてあり、それをつかって 10 を作るというゲーム(本稿では以下、切符ゲーム)をよくやった。
それをプログラムを書いて解決しようという問題。
切符ゲームには

2と3 から 23 を作ったりして良い。
2と3 から 23 を作ったりすることはできない。

という2つのレギュレーションがあって、今回はちょっと面倒な前者にした。

10を作るだけだと問題にしにくいので、1〜99 で作れない数を出すということにした。

プログラミングという方面から見れば、数式とは何であるかみたいなこととか、それを構成するロジックとか、そういうことを考える機会になるという感じ。

実装戦略と例

実装戦略は

「(38-7)*2」のような文字列を実際に作り、それを eval のような関数に丸投げする
「(38-7)*2」のような文字列を評価する場合の処理を実装する

の二通りがある。

前者は(私の印象では)バグりにくい感じだけど、実行効率が悪い。
後者はややバグりやすい感じだけど(ちゃんと書けば)すごく速い。

いずれの場合も以下の二点に気をつける必要がある：

「 (7-3/2)*8」のような式を 44 であると( つまり、3/2 を 1 ではなく 2分の3 であると )評価する
「7」と「2」をつなげると 72 になるが、「7」と「(8-3)」をつなげても 75 にはならない

前者は、浮動小数点で実装しても困らないんだけど、どれだけの誤差を無視して良いのかを決める必要がある。
誤差のしきい値を根拠を持って決めるのは結構難しいので、有理数を使うのが良い。
とはいえ、有理数を真剣に実装するのはまた面倒なので、有理数クラスを持っている ruby/python を使うのが楽ということになる。

逆ポーランド記法で式を立ててからそれを自力で評価するという戦略の方が一定数いらっしゃったが、逆ポーランド記法の式をつくる処理とそれを評価する処理は一緒にすることができる。
一緒にしてしまえば、先に挙げた後者の実装戦略となる。

ruby / 文字列を eval する作戦

# ruby 2.1.1p76 
require "mathn" # mathn は、4/6 を 0 ではなく (2/3) にする

OPERATORS=[ "+", "\\-", "*", "/", "_" ]# tr に渡す都合で "-" ではなく "\\-" にしている

EXPRESSIONS=%w[
  AxByCzD    ((AxB)yC)zD    (AxB)y(CzD)    
  (Ax(ByC))zD    Ax((ByC)zD)    Ax(By(CzD))
]

def solve( *nums0 )
  nums0.permutation(nums0.size) do |nums|
    OPERATORS.repeated_permutation(3).each do |ops|
      EXPRESSIONS.each do |exp|
        begin
          yield eval(exp.tr( "ABCDxyz", (nums+ops).join ))
        rescue SyntaxError, ZeroDivisionError
          # ignore!
        end
      end
    end
  end
end

puts( ( (1..99).to_a - enum_for( :solve, 2, 3, 7, 8 ).to_a ).join(", ") )

ruby には mathn というライブラリがあるのでこの問題には非常に向いている。
括弧の付け方がリテラルになっているのはちょっとみっともない気もするが、括弧の付け方を生成するコードよりもリテラルのほうが短い気がするのでこれで。
eval の引数は "2((37)*8)" のようになることもあるが、その場合は SyntaxError が上がって、結果的には無視される。
計算量を減らす努力がないし、enum_for → to_a → 引き算という流れが富豪的にすぎるような気もするが、これでも手元で 1秒未満なので高速化すべき理由がない。

C++ / 式の評価を自力でする

思いのほか長くなってしまったんだけど、C++ だとこんな感じ。

// Apple LLVM version 5.1 (clang-503.0.40) (based on LLVM 3.4svn)
// clang++ -std=c++11 -Wall
#include <iostream>
#include <functional>
#include <vector>
#include <map>
#include <cassert>
#include <initializer_list>

struct digit{
 int n, d; // 分子と分母
 int dig_size; // join する際に乗じる値。0 は join不能を示す。
};

auto mul( digit const & a, digit const & b )->digit
{
    return digit{ a.n*b.n, a.d*b.d, 0 };
}
struct operation_fail{};

auto join( digit const & a, digit const & b )->digit
{
  if ( a.dig_size<=0 || b.dig_size<=0 ){
    throw operation_fail();
  }
  return digit{ a.n*(b.dig_size) + b.n, 1, a.dig_size * b.dig_size };
}

std::function<digit( digit const & a, digit const & b )>
ops[]={
  #define DEF_OP( x )   []( digit const & a, digit const & b )->digit{ return (x); }
  DEF_OP( ( digit{ a.n*b.d + b.n*a.d, a.d*b.d, 0 } ) ), // add
  DEF_OP( (  digit{ abs(a.n*b.d - b.n*a.d), a.d*b.d, 0 } ) ), // sub
  mul,
  DEF_OP( ( mul( { a.d, a.n, 0 }, b ) ) ), // b÷a
  DEF_OP( ( mul( a, { b.d, b.n, 0 } ) ) ), // a÷b
  join,
  DEF_OP( ( join( b, a ) ) ), // 逆join
  #undef DEF_OP
};

auto solve( std::vector<digit> const & src, std::map<int,bool> & result )->void
{
  if ( src.size()==1 ){
    auto n = *src.begin();
    if ( 0<n.d && n.n % n.d==0 && 0<n.n/n.d ){
      result[ n.n/n.d ] = true;
    }
    return;
  } else {
    for( size_t i=0 ; i<src.size() ; ++i ){
      for( size_t j=0 ; j<i ; ++j ){
        auto keep = src;
        keep.erase( keep.begin()+i );
        keep.erase( keep.begin()+j );
        for( auto const & op : ops ){
          auto newset = keep;
          try{
            newset.push_back( op( src.at(i), src.at(j) ) );
            solve( newset, result );
          }
          catch( operation_fail const & e ){
            // ignore
          }
        }
      }
    }
  }
}

auto solve(  std::initializer_list<int> list ) -> std::map<int,bool> 
{
  std::vector<digit> digits;
  for( auto const & v : list ){
    digits.push_back( { v, 1, 10 } );
  }
  std::map<int,bool> result;
  solve( digits, result );
  return result;
}

int main()
{
  std::map<int,bool> result = solve( { 2,3,7,8 } );
  bool shown=false;
  for( int i=1 ; i<100 ; ++i ){
    if ( ! result[i] ){
      std::cout << ( shown ? ", " : "" ) << i;
      shown=true;
    }
  }
  return 0;
}

マクロ使ってすいません。
見ての通り

数のリストから2つを取り出す。
取り出したものに演算子を適用しする。
取り出さなかったものと、演算子の適用結果をくっつけたリストを作って再帰的に。
数のリストの長さが1 だったら、出来上がった数。

という流れ。

2 と 3 から 23 を作る処理を join と名づけて二項演算の一種にしているんだけど、足し算などの結果は join できないということを表現する必要がある。
で。
dig_size というメンバ変数がわかりにくいと思うんだけど、
23 と 7 をくっつけると 23*10 + 7 だけど、2 と 37 をくっつけると 2*100+37 になる、
という計算の、10 や 100 が dig_size に入っている。
この変数を join 可能かどうかにも流用するという作戦。
こちらの実装はまあまあ真面目なので、数を5つにしてもそのまま動く。実行時間も短い。

有理数は、この問題では約分が不要なので、GCD なんかは出てこない。

感想など

こういう話題に慣れている人には簡単なので簡単かなぁと思ったんだけど、慣れてる人はそれほど多くなかったようで、結果的にはやや難問だった感じ。

とはいえ、コンピュータによる計算の基礎みたいな部分のある問題なので、やっておいて損はない。
実際、私も仕事でこのての話題が必要になったことが何度かある。

言語による差が出やすい問題だったと思う。
eval がある、有理数がある、順列組み合わせが簡単に書ける、という3点があると楽になるので、ruby が有利。どれもない C言語は比較的大変だったと思う。

テストデータがなかったことも難しく感じられた原因だと思うけど、テストデータを作りやすい問題だったと思うので、そこは自力で対応してほしいと思っていた。

ゼロ除算へのケアがない方や、全パターンの列挙に失敗しているのに偶然正解している方もいらっしゃったので、そういう場合には正解にたどり着けないような問題にすべきだったかなと、ちょっと反省している。

最後に

今月中か来月上旬に次の問題を出す予定（作成中）なのでよろしくお願い致します。

それと。
第21回オフラインリアルタイムどう書く( http://yhpg.doorkeeper.jp/events/10503 ) やります。5月9日(金) 横浜。
お暇とご興味のある方は是非。
ぬるいイベントなのでお気軽に。

Codeへの愛とCuriosity

CodeIQ への出題・解説解題・その周辺について、思いつくままに。