読者です 読者をやめる 読者になる 読者になる

変進小数の足し算 問題解答 ( CodeIQ )

CodeIQ Brainf**k

はじめに

CodeIQというところでプログラミング問題「変進小数の足し算」に解答しましたので、ネタバレです。

codeiq.jp

問題

小数点以下、桁が深くなる毎に10進数、9進数、…と基数が変わっていく、名付けて「変進小数」に関して、2数の足し算の式と答えが与えられた時に、その答えが合っているかどうかを判別する問題です。

例えば、999.886644221 という変進小数は、実際には次の有理数を表しています。 $$ 999+\frac{8}{10}+\frac{8}{10\cdot 9}+\frac{6}{10\cdot 9\cdot 8}+\frac{6}{10\cdot 9\cdot 8\cdot 7}+\frac{4}{10\cdot 9\cdot 8\cdot 7\cdot 6}+\frac{4}{10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5}+\frac{2}{10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4}+\frac{2}{10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3}+\frac{1}{10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2} $$

なお、基数がどんどん小さくなっていく関係上、高々小数点第9位 ( 基数 2 ) までしか存在しません。

問題の入出力は次の通りです。

  • 入力
    • 入力は複数行
    • 各行は、行のID、2数の足し算の式、答えの3カラムのタブ区切りテキスト
      例えば、0 724.22705012+219.4121222 943.64121232 のようになっている
    • 足し算に現れる数値は10万を超えない
    • ( 問題には明記されていませんでしたが ) 答えに現れる数値は20万を超えない
    • 答えが整数になる場合、小数点以下は現れない
      ( 逆に、足し算に現れる2数は必ず小数になっている )
  • 出力
    • 答えが間違っている行のIDをカンマ区切りでつなげたもの

用意された入力データは1,000行のもので、そのうち答えが間違っているのは5件以上10件以下 ( 実際には6件 ) でした。

解説

提出版

以下のRubyのコードを提出しました。

puts $<.map{|l|
  i,*a=l.split(/[+\t]/)
  x,y,z=a.map{|s|s.scan(s[?.] ? /.*?\.|./ : /.+/).map(&:to_i)+[0]*9}
  9.downto(c=0).all?{|j|(t=x[j]+y[j]-z[j]+c)==(11-j)*c=t<=>0}&&c==0 ? nil : i
}.compact*?,

方針についてですが、変進小数になっている各数値を有理数に変換してあげれば ( ちょうどRubyにはRationalがありますし ) 単純な数値比較になるのですが…。それでは面白くないため後述のBrainf**kの実装を見据えて、変進小数の値を直接求めず、足し算の結果が同じかどうかにフォーカスして調べました。

各変進小数は、整数部と、小数部の各桁による配列として管理し、足し算の2数 x,y と答え z に対して、x+y=z の検証のために、x+y-z の筆算に相当する計算を下の桁から、キャリー込みで行います。

答えがあっているかどうかは、全ての桁が 0 ( かつ残ったキャリーが 0 ) になるかどうかによって判断できます。

ただし、与えられた変進小数の桁数は不定なので、確実に2進の桁 ( 小数第9位 ) まで揃うように、0 を9個埋めて処理します。筆算部分に相当するループは 9.downto(0) で行っており、配列のインデクスとしては 0~9 しか使いませんから、配列の末尾に余分な要素があったとしても結果に影響しません。

配列の先頭に来る整数部分については、小数点以下の桁とは規則性が変わりますが、桁の一致とキャリーだけを見るので、小数点以下の規則の延長として、11進数の桁と見ても支障がありません。なので、同じループによって処理できます。

なお、フィードバックでは「おそらく一番短いコード」とのコメントを頂いたのですが、今回特に短さを目指したわけではなかったりします。

Brainf**k版その1

というわけで、提出版のRubyの方針そのままにBrainf**kで実装しました。ただし、筆算部分は下の桁から行うのではなく上の桁から行います。これも各桁の一致を見るだけですから、

  • ある桁での x+y-z が 0,-1 以外なら、答えは即座に invalid と判断できる
  • ある桁での x+y-z が -1 の場合、その桁の基数分をボローとして、下位の桁から引く

といったように処理できます。

Rubyによる擬似コードは次の通りです ( 動作確認していないのでマトモに動かないかもしれませんが… )。Brainf**kである以上、入力の解析等含め、状態遷移を管理するような処理が必要になるため、見た目はかなり異なっていますが、方針自体は変わっていません。

notfirst=false
while c=getc
  id=c
  id+=c while ?\t != c=getc
  a=[0]*11
  3.downto(1){|n|
    s= n==1 ? 3 : 4
    i=t=0
    while s>0
      c=getc
      nn=0
      case c
      when ?0..?9
        case s
        when 1
          a[i]+=c.to_i
          i+=1
        when 2
          a[i]-=c.to_i
          i+=1
        when 3,4
          t=t*10+c.to_i
        end
      when ?.
        nn=1
      else # ?\t,?+,?\n
        nn=2
      end      
      if nn>0
        case s
        when 3
          a[0]+=t
        when 4
          a[0]-=t
        end
        case nn
        when 1
          s-=2
        when 2
          s=0
        end
      end
    end
  }
  valid=a[0]==0||a[0]==-1
  a[1]-=10 if a[0]==-1
  1.upto(9){|i|
    valid=false if a[i]!=0&&a[i]!=-1
    a[i+1]-=11-i if a[i]==-1
  }
  valid=false if a[10]!=0
  if !valid
    print ?, if notfirst
    print id
    notfirst=true
  end
end

で、Brainf**kの実装は次で示す通りなのですが…。ほぼ正しい結果を示すものの、おそらくバグが取り切れていないのと、処理時間が長すぎて ideone の制限だと入力の1/10程度しか捌けないという欠点が残ってしまいました。
処理時間が長すぎる理由は明白で、整数部分を単純化するために桁が増える毎に以前の累積値を10倍していくところ、ここが数値に比例してステップ数を喰うためです。

Brainf**k版その2

で、しようがないかなあと思ったのですが。というのは、読み込んだ時点で桁の位置が確定する小数部分と違い、整数部分は確定しませんから、読み込んだ桁を覚えておいて、小数点が来た時点で正しい桁に反映するという処理が必要になるからです。

しかしここで諦めていてはBrainf**k使いの名折れです。ということで改良したのが次のコードです

答えまで含めて、整数部分は高々6桁ですから、6桁+9桁の最大15桁の変則BCDとみなし、整数部分の桁は小数点が現れるまで記憶しておいて、後でずらすようにしました。これにより、現実的な時間で全データを処理できるようになりました。

終わりに

久しぶりの手動採点ということで…。Brainf**k版も含めて提出したかったのですが、限定100人に間に合わない公算が高かったので、泣く泣く諦め、後から実装することにしました。

…というのは嘘ぴょんです。流石にそれは採点者の鍋谷さんに対するイジメに近い気がしましたので…。