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 のメンションなどでお知らせ下さい。

位置関係2題の解説・解題

先日、CodeIQ に出していた

という２つの問題が締め切られた。

私が出した問題が締め切られるのは久々だったので、ちょっと慣れない感じ。

で。

この問題は、タイトルの通り、2つの図形の位置関係を分類する問題になっている。
２つの円の方は、中心と中心の距離を見ればいいだけなので簡単。
円と線分はいろいろ見なくちゃいけないし、分類も多いのでちょっと大変、ということになっている。

数学力はあまり問うていないつもり。高校程度なんだと思う。

いつもなら、一つの事象をひとつのテストデータにするんだけど、今回はそれだと件数が多くなりすぎる感じなので、ひとつのテストデータにたくさんの事象を仕込むことにした。


問題の概要については
http://ange1.hateblo.jp/entry/2016/07/23/001128
をご覧いただくことにして、出題意図を列挙すると。

  • ごちゃごちゃした分類を誤らずに実装できるかどうか
  • 浮動小数点の除算や平方根を使うべきではないという判断ができるかどうか

というつもり。浮動小数点を使っても解決できてしまう場合が多かったようで、この点はテストデータの追い込みが足りなかったと反省している。


「接する」というデリケートな条件を判断する必要がある問題になっているので、誤差がまったくない計算をする必要がある。そして、この問題はそのような実装を無理なくできる問題になっている。入力は整数だし。


誤差のない計算ということで、有理数が簡単に扱える ruby や python だと実装が楽になる。
JavaScript だと苦しい感じかもしれない。


私の場合はやっぱり ruby でこんな感じ：

２つの円の位置関係の実装例：

def solve_one(s)
  x0,y0,r0,x1,y1,r1 = s.scan( /\d+/ ).map(&:to_i)
  d2 = (x0-x1)**2 + (y0-y1)**2
  r0,r1=[r0,r1].minmax
  return "A" if d2==0 && r0==r1
  sr2 = (r0+r1)**2
  return "F" if sr2<d2
  return "E" if sr2==d2
  dr2=(r1-r0)**2
  return "B" if d2<dr2
  return "C" if d2==dr2
  return "D" if d2>dr2
  raise "unexpected"
end

def solve( src )
  src.split(" ").map{ |s|
    solve_one( s )
  }.join("")
end

puts solve(gets)

円と線分の位置関係の実装例：

def calc_min2( a, b, c )
  candidates=[
    c, # x==0
    a+b+c # x==1
  ]
  x=-b/2.to_r/a
  candidates.push( a*x*x+b*x+c ) if 0<=x && x<=1
  candidates.min
end

def solve_one(s)
  cx,cy,r,ax,ay,bx,by = s.scan( /\d+/ ).map(&:to_r)
  ax-=cx
  ay-=cy
  bx-=cx
  by-=cy
  a=ax*ax+ay*ay<=>r*r
  b=bx*bx+by*by<=>r*r
  return "A" if a<0 && b<0
  return "C" if a==0 && b==0
  return "B" if a<=0 && b<=0
  return "F" if a*b<0
  vx=bx-ax
  vy=by-ay
  min2 = calc_min2(vx*vx+vy*vy, 2*(ax*vx+ay*vy), ax*ax+ay*ay )
  case min2<=>r*r
  when -1; a*b==0  ? "D": "E"
  when 0; a*b==0  ? "G": "H"
  when 1; "I"
  end
end

def solve( src )
  src.split(" ").map{ |s|
    solve_one( s )
  }.join("")
end

puts solve(gets)

我ながらもう少しなんとかならなかったのかと思わなくもない。

ともあれ。


多くの方に挑戦いただき大変うれしく思っています。ありがとうございました。

遠い昔、はるか彼方の銀河系の カレンダー の、解題と皆様の実装

「遠い昔、はるか彼方の銀河系の カレンダー」という問題を「初級編 ( https://codeiq.jp/q/2597 )」と「ややリアル編( https://codeiq.jp/q/2598 )」の2題に分けて出した。

多くの方に挑戦いただき、うれしく思っています。ありがとうございます。

解題

問題の内容や解説は
遠い昔、はるか彼方の銀河系の カレンダー - Qiita
や
「遠い昔、はるか彼方の銀河系の カレンダー」問題解答 ( CodeIQ ) - ange1のブログ
を御覧ください。(書いていただき ありがとうございます)

で。

出題意図は：
「ツェラーの公式 を発明してください」
というものだった。これを「ツェラーの公式」をにおわせないで出したい。

そいで。

  • 現実のカレンダーを使うと発明ではなく引用になってしまうので、架空のカレンダーにする。
  • ただ問題を出すだけだとツェラーの公式は不要になってしまうので、ゴルフにする。

ということになった。

とはいえ。下記リンクを見ていただければわかる通り、ツェラーの公式を発明せずともバイト数の要件を満たしてしまうので、その意味では出題者（私）の敗北である。

タイトルは、ちょうどスターウォーズの公開が近かったので、スターウォーズ感のあるものにしてみた。

皆様の実装など

上記の解説ページ以外では、以下のものを発見した。みなさまありがとうございます。







※ 他にもあったら Twitter などでお知らせください。追記します。

今まで CodeIQ に出した問題

今まで CodeIQ に何問出したのかもわからないということに気づき、まとめてみた。

番号は出題順ではなく、URL順。

# 問題へのリンク 挑戦/募集 難易度 締切
0 カードゲームの役を判定する 不明/50 ★☆☆☆ 2013年10月15日
1 テトロミノ＋ビンゴ！ 不明/50 ★☆☆☆ 2013年11月18日
2 メソッド名を当てる空欄補充問題 不明/50 ★☆☆☆ 2013年12月23日
3 最大公約フィボナッチ数(?) 19/100 ★☆☆☆ 2014年1月20日
4 カラフルな八面体を転がそう。 50/50 ★☆☆☆ 2014年2月19日
5 hello, world × 3 67/100 ★★★☆ 2014年3月17日
6 4つの数と四則と括弧 57/100 ★☆☆☆ 2014年4月22日
7 JavaScriptじゃんけん大会！ 40/100 ★☆☆☆ 2014年6月09日
8 長くなるように、増え続けるように 44/100 ★☆☆☆ 2014年7月14日
9 中学入試から：数列の和 35/100 ★☆☆☆ 2014年8月19日
10 中学入試から：単位のある計算 41/100 ★☆☆☆ 2014年9月24日
11 中学入試から：正三角形？二等辺？ 67/100 ★☆☆☆ 2014年10月16日
12 中学入試から：数字の個数 34/100 ★☆☆☆ 2014年11月18日
13 中学入試から：図形と場合の数 34/100 ★☆☆☆ 2014年12月19日
14 中学入試から：概数と計算 22/100 ★☆☆☆ 2015年1月31日
15 中学入試から：対称軸の本数を数えよう 23/100 ★☆☆☆ 2015年2月23日
16 対戦型 hello, world! 100/100 ★☆☆☆ 2015年3月31日
17 Minority's hello, world 87/100 ★☆☆☆ 2015年7月03日
18 直角を探せ！ 〜ピタゴラスさんありがとう〜 141/- ★★☆☆ 2015年10月23日
19 テトロミノの置き方を数えよう 72/- ★☆☆☆ 2015年11月13日
20 バスの料金を計算しよう(ややリアル編) 125/- ★★★☆ 2016年3月31日
21 バスの料金を計算しよう(初級編) 199/- ★★☆☆ 2016年3月31日
22 先制 hello, world 106/150 ★☆☆☆ 2015年9月21日
23 ボタンを押して数を作ろう 264/- ★★☆☆ 2016年3月31日
24 くねくね最短経路 67/- ★★☆☆ 2016年3月31日
25 最寄りの素数 100/- ★★★☆ 2016年3月31日
26 【機械学習 超初級】【選択式】機械学習の基本のようなそうでもないような問題です 359/- ★☆☆☆ 2016年3月31日
27 遠い昔、はるか彼方の銀河系の カレンダー（初級編） 165/- ★★☆☆ 2016年3月24日
28 遠い昔、はるか彼方の銀河系の カレンダー（ややリアル編） 93/- ★★★☆ 2016年3月24日
29 パスカルの　三角形では　ありません（字余り） 140/- ★★☆☆ 2016年3月21日

初めて出題したのが 2013年9月。それから二年半近く。
数えてみたら丁度 30問だった。

難易度が全然実態と合ってないような気がするけどキニシナイキニシナイ。

上記のリストには、挑戦募集中の問題も（これを書いている時点では）含まれている。
挑戦募集中の問題については
codeiq.jp
からどうぞ。

先制 hello, world のこと

先日、CodeIQ に「先制hello, world」という問題を出した。
単純なプログラムのソースコード同士を戦わせるというコンセプトとしては二回目なんじゃないかと思うけどよく憶えていない。

いつもここに書いているような解説解題の記事は CodeIQ Magazine に掲載していただいたので、普通の解説解題については https://codeiq.jp/magazine/2015/10/30191/ の方をご覧頂きたい。

で。
こちらはサブノート。

今回のルール（ルールについては 前出の CodeIQ Magazine の方を御覧ください）に至る経緯を書いてみよう。

最初のアイディアは、一文字ずつ互いに闘うという、以前出した「対戦型hello, world」と同じようなコンセプトだった。勝敗は文字コードの大小。
「負けたほうが退場」をやめて、n 文字目同士が闘うことにしたらどうだろう。とかいう感じ。

しかしそれだと文字数を揃えなくてはいけない。「対戦型hello, world」では揃えていただいたが、バラバラのほうが面白いと思う。

であれば。
n文字目がn文字目と戦うのをやめればよい。
どうやめるか。

文字のインデックスではなく、文字コードで戦う相手を決めればよいか。

戦いの順序はインデックスで決まり、戦う相手は文字コードで決める。よさ気。
戦うからには勝敗を決める必要がある。文字コードが同じ文字が相手なので、インデックスで勝敗を決めるしかない。インデックスが小さいほうが勝ち。
最終的な勝敗を生存者数にしてしまうと、長いコードを書けば勝てることになりそう。よろしくない。
じゃあ殺された数が少ない方はどうか。これだとコードを短くしたくなるので、いい感じに見える。

で。

このあと。
前後の文字も巻き添えでダメージを食らうとか、ヒットポイントがあって3ダメージで死ぬとか、直前にスペースがあると防御力が上がるとか、遠すぎる文字には攻撃できないとか、いろいろルールを考えたものの。
結局出題したようなシンプルなルールが一番面白そうだということになり、出題に至った。

そんな次第。

ちなみに。
同じような問題を出したいと思っていて、アイディアはあるものの、まだ出題できるところまでルールが仕上がっていない。
出題できるといいなぁ。

Minority's hello, world の 解説・解題

CodeIQ に「Minority's hello, world」という問題
https://codeiq.jp/q/1579
を出した。

問題について

ideone にある言語で hello, world! を書いて、競わせようという問題。

提出コードに課された条件は

  • ideone にある言語のどれかで書くこと。
  • 過不足なく「hello, world」を出力すること。
  • ソースコードに使える文字は、アスキーコード 0x20〜0x7e の文字のみ。

という具合。

今回は対戦ではなく、ポイント争い。
ルールはこんな感じ：

提出されたプログラムで使われている文字を、全挑戦者について集計します。
各文字には「(その文字を利用した挑戦者の人数)の2乗」というポイントが割り当てられます。
提出されたプログラムのポイントは、そのプログラムで使われている文字のポイントの合計となります。
提出コードのポイントが少ない順に順位をつけます。最小ポイントの方が優勝です。

という感じ。

戦いの結果は

で見ることが出来る。

勝つために

他の挑戦者の送り込むコードを予想することがまず大事。
予想した上で、ポイントの低いコードを書くための技術力が必要。
様々な言語について何ができるのかを把握していることが求められている内容になっている。

問題の設定はかなり馬鹿げているが、どうやっても勝てない問題というわけではない。

勝つための方法は以下のとおりである：

  1. 各投稿がどの文字を使っているのかを適当に予想する。
  2. 予想をもとに、各文字のポイントを計算する。
  3. 計算結果を元に、自分の書いたコードのポイントを計算し、ゴルフ頑張る。

たぶん、この作業をきちんとやれば、優勝とは言わないまでも、15位ぐらいには入れたのではないかと思う。
もちろん、ある程度、ruby や perl などの素養がないと無理ではあるけれど。

出題意図など

hello, world で競い合う面白いゲームを提供したかった、というのが出題意図である。
必要な能力は

  • 複数の言語の素養
  • 予測しにくい環境に対応する力
  • イレギュラーなゴルフに対応するパズル力

辺りだと思う。

母集団が違うと全然違う戦いになるので、同じルールのゲームを別のところでやっても面白いと思う。
言語を限定しても楽しめると思う。

しかし。
PHP に文字列と文字列の xor があるのは知らなかった。
勉強になりました。

総評的な何か

前回同様、勝ち負けはまあいいんだけど、要求仕様である

  • 改行不可
  • 「"hello, world"」や「Hello World!」ではなく「hello, world」を出力する
  • Ideone で実行可能

などのルールを守れていない方が10名以上いたのが残念だった。

出題文面はだいぶ工夫したつもりなんだけど、全然足りてなかった感じ。

また問題出します。
よろしくお願いします。

バイナリカウント解いてみた

バイナリカウント問題解いてみた。

提出コードはこんな感じ。

# 平易で遅い計算。テスト用。
def solve_slow(x)
  (1..x).inject(0) do |acc,x|
    acc+x.to_s(2).count("1")
  end
end

# F(x) の xが奇数の場合のアルゴリズム。
def solve_odd( x )
  (x+1)/2 + 2*solve(x/2)
end

# 10**100 でも計算できるアルゴリズム。
def solve( x )
  return x if x<3
  if x.odd?
    solve_odd(x)
  else
    x.to_s(2).count(?1) + solve_odd( x-1 )
  end
end

# 計算が正しいことの確認
GIVEN_DATA = [ [3, 4], [13, 25] ].freeze
TEST_DATA = GIVEN_DATA + (1..1000).map{ |s| [s, solve_slow(s)] }
TEST_DATA.each do |src, expected|
  actual = solve(src)
  okay = actual==expected
  p [ src, expected, actual ] unless okay
end

# 答えを出力する
{ "・第１問："=>3, "・第２問："=>10 }.each do |name, pow|
  puts "#{name}#{solve(10**pow)}"
end

もともと solve_odd は solve の中に埋め込まれていて

# 10**100 でも計算できるアルゴリズム。
def solve( x )
  return x if x<3
  cur = ( x.even? ? x.to_s(2).count(?1) : 0 )
  cur + (x+1)/2 + 2*solve((x-1)/2)
end

という感じだった。
これではわかりにくいということで、説明の都合でふたつに分けて提出してみた。

計算量としては大いに改善の余地ありなんだけど、目標だった 10の10乗を大きく超える数でも問題なく計算できるので、計算量の削減作業はこれ以上は行うのをやめた。