「中学入試から：数列の和」の解説・解題

CodeIQ に「中学入試から：数列の和」という問題
https://codeiq.jp/ace/nabetani_takenori/q1012
を出した。

挑戦の募集はすでに締めきっている。
というわけで、解説・解題。

で。
まずは問題

問題

■問題の概要
中学入試の問題に、以下の様な問題がよく出ます。
あるきまりにしたがって、下のように数をならべました。
1,2,100,1,2,101,1,2,102,1,2,103,1,2,104,1,2,105, ...
この数列の100番目から順に110番目まで加えると、その和はいくらになりますか？
100番目から110番目を足すと
1+2+133+1+2+134+1+2+135+1+2
なので
414
が答えとなります。

この問題を
あるきまりにしたがって、下のように数をならべました。
【　A　】
この数列の【　B　】番目から順に【　C　】番目まで加えると、その和はいくらになりますか？
と考え、A, B, C を入力文字列として与えます。
問題の答えを計算するプログラムを書いて下さい。
■具体的な課題
下記リンクの zip 内に data.txt というファイルがあります。
このファイルには
　「データID、空欄Aの内容、空欄Bの内容、空欄Cの内容、期待する答え」
が、空白区切りで1000件余り入っていますが「期待する答え」が間違っているデータが数件(10件前後)含まれています。
間違っているデータのIDを答えて下さい。
■補足
・データIDがTで始まるデータには、間違っているものは含まれていません。テストにお使い下さい。
・間違っているデータの ID は全て数字になっています。間違い数は5件より多く、20件より少なくなっています。
・数列は、小学生の知識でルールが推測できるような数列です。カタラン数だったりはしません。
・数列は、小学生の知識で和の計算ができるような数列です。フィボナッチ数だったりはしません。
・空欄 B, C の値については、中学入試でそんな大きな数にはしないだろ、と言いたくなるようなデータがありますが、答えは 2の63乗を超えないようになっています。
・数列が「1, 2, 3, 4, ... 」で、2番目から5番目なら ( 2+3+4+5 ) を計算して下さい。つまり、数列の先頭は1番目(0番目ではない)で、5番目まで足します(両端含む)。
・仕様が曖昧で、厳密に考えると答えが一意に定まりませんが、そのあたりも中学入試と同じです。
・不正な入力（空欄Bの値よりも空欄Cの値が小さいなど）に対処する必要はありません。

■資料
http://nabetani.sakura.ne.jp/codeiq/q1012.zip
上記リンク先の zip ファイルの中には、以下のファイル含まれています
・ data.txt
　→ このファイルに含まれるデータについて調査します。

こんな感じ。

出題の背景と意図とか

最近、中学入試算数と関わる機会があり、この問題を実際に目にした。
これは面白かもと思い、問題にしてみた。

実際、これはかなりリアルな中学入試の問題になっている。
中学入試に出る数列は意外と種類が多く、等差数列だけではなく、等比数列やフィボナッチ数列も出ることがあるらしい。しかし、「和を求めよ」という出題になると、等差数列と周期的な数列しか出せなくなるようだ。
等比数列の和の公式には指数が必要で、小学生の範囲には指数がない。からだと思う。
というわけで、この問題には等差数列（公差 0 を含む ) しか入っていない。

人工知能を作れというような無茶な要求を想起させる問題文になっているせいか、難しく感じた方が多かったようにも思うけど、実際は例として挙げた

1,2,100,1,2,101,1,2,102,1,2,103,1,2,104,1,2,105, ...

の定数違いしか出ていないので、（ちゃんと書けば）1個解ければ全部解けるという状況になっている。

実装戦略と例

実装するには

入力を解釈する
ルールを推測する
和を計算する
間違ったデータのIDを収集して出力

という4つの処理が必要になる。まあ、わけかたはそれぞれだけど。

和を計算する際に

全項列挙して足し上げる
和の公式を使う

という2つの作戦がある。課題データに入っているものは最悪 100万件程度なので、全部足し上げてもいまどきのコンピュータなら間に合うので、それはそれでいいと思う。

というわけで、私の実装例を示しておく。

私の実装例 ( ruby )

# ruby 2.1.2p95

class Sequence
  def initialize(sample)
    @sample = sample
    @groupsize = guess_groupsize(sample) or fail 'failed to guess groupsize'
  end

  def arithmetic_seq?(s)
    s.each_cons(2).map { |a, b| b - a }.uniq.size == 1
  end

  def guess_groupsize(sample)
    (1..sample.size / 3).find do |gs|
      gs.times.all? do |subseq_ix|
        subseq = (0..sample.size / gs).map { |i| sample[i * gs + subseq_ix] }
        arithmetic_seq? subseq.compact
      end
    end
  end

  def at(subseq, ix_in_subseq)
    start = @sample[subseq]
    diff = @sample[subseq + @groupsize] - start
    start + diff * ix_in_subseq
  end

  def subseq_sum(subseq, count)
    return 0 if count <= 0
    ( at(subseq, 0) + at(subseq, count - 1)) * count / 2
  end

  def sum(total_count)
    @groupsize.times.reduce(0) do |acc, subseq|
      count = (total_count - 1 - subseq) / @groupsize + 1
      acc + subseq_sum(subseq, count)
    end
  end
end

def solve(sample, first, last)
  seq = Sequence.new(sample)
  seq.sum(last) - seq.sum(first - 1)
end

open('data.txt') do |f|
  bads = f.flat_map{ |line|
    ident, a, b, c, expected = line.split(/\s+/)
    actual = solve(a.split(',').map(&:to_i), b.to_i, c.to_i)
    expected.to_i == actual ? [] : [ident]
  }
  puts bads.join(',')
end

和の公式を使って普通に書いた感じ。
sum の中にある +1 や -1 が難しくて、私も紙とペンがないとちゃんと書けない。
和の公式を使わなければ簡単だけど。

フィードバックで、多くの方に「メソッド・関数・プロシジャをもっと短く」と書いているんだけど、私としては、これぐらいが模範的な感じだと思っている。
ruby だと 5行ぐらい。C++ や Java なら 10行ぐらいが目安。
いろんな意見があるけどね。

コメントはもっと書いたほうがいいと思う。すいません。

感想など

テストせずに提出するのはほぼ無理という形で出題したのが功を奏し、ほぼ全員が正解だった。
おめでとう！

いつも通り、締切後はコード公開大歓迎。
コードを公開したら、 twitter などで知らせてくれると見つけやすくて助かります。

最後に

次の問題は、もう CodeIQ の中の人に渡してあるので近日中に公開されると思う。

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

Codeへの愛とCuriosity

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

「中学入試から：数列の和」の解説・解題

問題

出題の背景と意図とか

実装戦略と例

私の実装例 ( ruby )

感想など

最後に