Codeへの愛とCuriosity

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

「変進小数の足し算」の解題解説

変進小数の足し算の解説・解題

「変進小数の足し算」( https://codeiq.jp/q/2924 )という問題を CodeIQ に出題させて頂いた。

久々の手動採点問題。

フィードバックは終えているが、なにせ手動なので、採点ミスなどあるかも。あったらすいません。twitter DM などで連絡いただければと思います。

多くの方の挑戦があり、大変嬉しく思っています。

採点は久々なのとシステムに慣れていないのとで思ったよりも大変だったんだけど、無事終了。

問題の概要

小数の足し算をして下さい。 ただしこの小数は、

  • 小数第 n 位 が 11-n 進数

という不思議なルールになっています。例えば、小数第1位は 10進数、小数第9位は2進数です。
このルールを「変進小数」と呼びます。
【入出力】
入力は
8.622+3.177
こんな感じです。
2個の変進小数が「+」で区切られて並んでいます。

出力は、
11.811
のように、足し算の結果を変進小数で出力して下さい。

具体的な課題として、変進小数の足し算とその結果が含まれるファイル data.txt があり、結果が間違っているデータの ID を答えさせるという趣向になっている。

解題とか

位取り記数法とは何か、みたいなところに趣旨がある。
そう見せかけておいて、きちんと文字列処理ができるかどうか、というテーマもあったりする。
それと。誤差を許容しない問題なので、浮動小数点で書くとやや負けるようにしたつもり。

採点した感触としては、簡単な問題だった様子。

実装方針

実装方針は

  • 繰り上がりの計算をする
  • 変進小数との普通の数の相互変換を実装する
    • 有理数との相互変換
    • 整数との相互変換
  • それ以外

と、いくつかの方針があり得る。

「それ以外」以外が想定解。それ以外の例は、 haruya 様のこんな
http://ideone.com/GOIUuC
実装。素晴らしいです。

実装例( 繰り上がりの計算をする )

繰り上がりの計算の例は、こんな感じ：

C++11 で

// "clang++ -std=c++11 -Wall"
#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <string>

/** 変進小数 v の小数第 pos0 桁目を取り出す */
int at( std::string const & v, int pos0 )
{
  size_t pos = v.find( '.' ) + pos0;
  return  ( pos < v.size() ) ? v.at(pos)-'0' : 0;
}

/** 整数部 z、小数部 v の変進小数文字列を構築する 
 * @note v を関数内で変更するので const 参照にしない。
 */
std::string build_string( int z, std::vector<char> v )
{
  while( '0'==v.back() ){
    v.pop_back();
  }
  std::stringstream ss;
  ss << z;
  if ( !v.empty() ){
    ss <<"." << std::string( v.data(), v.size() );
  }
  return ss.str();
}

/** 変進小数 a と 変進小数 b を加えた結果の文字列を返す */
std::string add_varbase( std::string const & a, std::string const & b )
{
  std::vector<char> v(9);
  int carry=0;
  for( int i=9 ; 0<i ; --i ){
    int base = 11-i;
    int val = carry+at(a,i)+ at(b,i);
    v[i-1]=( val % base ) + '0';
    carry = val / base;
  }
  return build_string( std::stoi(a)+std::stoi(b)+carry, v );
}

/** 問題を解く */
std::string solve( std::string const & src )
{
  std::string lhs, rhs;
  std::stringstream stream( src );
  std::getline( stream, lhs, '+' );
  stream >> rhs;
  return add_varbase( lhs, rhs );
}

/** delim でつなげて begin から end までを出力する */
template< typename iter_t, typename delim_t >
std::ostream &
join( std::ostream & ostr, iter_t begin, iter_t end, delim_t const & delim )
{
  bool first_time = true;
  for( auto it = begin ; it != end ; ++it ){
    if ( first_time ){
      first_time = false;
    } else {
      ostr << delim;
    }
    ostr << *it;
  }
  return ostr;
}

/** data.txt に含まれる間違いの id を出力する */
int main()
{
  std::vector<std::string> ids;
  for( std::ifstream stream( "./data.txt" ) ; stream ; ){
    std::string id, src, expected;
    stream >> id >> src >> expected;
    if ( ! src.empty() ){
      auto actual = solve( src );
      if ( actual != expected ){
        ids.push_back( id );
      }
    }
  }
  join( std::cout, ids.cbegin(), ids.cend(), "," ) << std::endl;
}

正直、挑戦いただいた方の実装にもっといいのがあった。ちょっと悔しい感じ。
join に10行以上要しているのが残念な感じ。

実装例( 有理数との相互変換 )

ruby のような、有理数が組み込み型にある場合には、有理数との相互変換を書くとわかりやすくていいと思う。

組み込み型に有理数がない場合には、10の階乗 倍 したら必ず整数になるので、その整数との変換をするといい。

で。ruby なので、有理数との相互変換を書くとこんな感じ：

def to_num(x)
  a,b=x.split(".")
  bases = [*2..10].reverse.inject([1]){|acc,n|
    acc+[acc.last*n]
  }.drop(1)
  b2=[*2..10].reverse
  a.to_i + b.chars.zip(bases, b2).map{ |n,base,limit| 
    raise "#{n} in #{x} is not valid" unless n.to_r<limit
    n.to_r/base
  }.inject(&:+)
end

def to_digit(x)
  int=x.floor.to_i
  return int.to_s if x==int
  frac = x-int
  d=int.to_s+"."
  [*2..10].reverse.each do |b|
    c=(frac*b).floor.to_s
    raise "bug?" unless c.size==1
    d+=c
    frac*=b
    frac-=frac.floor
  end
  raise "#{x} is not valid for to_digit" unless frac==0
  d.gsub( /0*$/, "")
end

def solve(src)
  to_digit(src.split("+").map{|x| to_num(x)}.inject(&:+))
end

File.open( "data.txt", "r" ) do |f|
  f.map{ |line|
    line.split("\t").map(&:strip)
  }.select{ |id, src, expected|
    expected != solve( src )
  }.map(&:first).join(",").tap{ |x| puts x }
end

私なりだとこんな感じ。
挑戦いただいたものにはもっとコンパクトで読みやすいものがあったように思うので、ちょっと悔しい。

その他の話題

英語

「変進小数」という この問題固有の造語をどう変数名やクラス名にするかという問題があって、そこに悩む方が多くいらっしゃった。

「小数」の英語が「decimal」なのがよくなくて、「decimal」には10進法という意味もあるので今回の問題にはそぐわないと思う。

「可変進法表記」を英語にして「variable base notation」ぐらいが良いかと思う。長いか。

「変進小数」を漢字表記のまま使っている方や、「HenshinShosu」とローマ字で来る方も多かった。潔くて良いと思う。

納品物

問題文中に「足し算の結果を変進小数で出力して下さい。」と書いたので、そのような関数なりクラスなりを用意してほしいと考えていた。
結果と合っているかどうかを見るだけでも「具体的な課題」の結果は正しくできるようにしたし、それを理由に減点したりもしなかったけど。

実装例

気づいた範囲内では、下記の通りです。皆様公開ありがとうございます。

他にもありましたら、 Twitter のメンションなどでお知らせ下さい。