「1時間以内に解けなければプログラマ失格となってしまう5つの問題」の5を解いた

1時間以内に解けなければプログラマ失格となってしまう5つの問題が話題に より、問題5を解きました。

問題5

1,2,…,9の数をこの順序で、”+”、”-“、またはななにもせず結果が100となるあらゆる組合せを出力するプログラムを記述せよ。例えば、1 + 2 + 34 – 5 + 67 – 8 + 9 = 100となる

ruby

  res=[]
  n=3;l=8;m=["",",+,",",-,"]
  (n**l-1).times do |s| #0~(n**l-1)
    # 3進法で表す
    p=s.to_s(3) #ex:12022121
    p="#{'0'*(l-p.size)}#{p}" #8桁の空欄を0で埋める
    str=""
    p.size.times do |t|
      str+="#{(t+1).to_s}#{m[p[t].to_i]}"
    end
    str+=(l+1).to_s
    ary=str.split(",")
    # 計算する
    tmp=ary[0].to_i
    1.upto(ary.size-1) do |t|
      tmp=tmp+ary[t+1].to_i if ary[t]==="+"
      tmp=tmp-ary[t+1].to_i if ary[t]==="-"
    end
    res << ary.join("") if tmp==100
  end
  puts res

javascript

var calc = function(n){
  // n=9の時、対象は1~9
  var ac=Math.pow(3,n-1),m=["",",+,",",-,"],res=[];
  for(var i=0;i<(ac-1);i++){
    var p=Number(i).toString(3);//3進法で表す
    p=Array(n-1-p.length+1).join("0")+p;
    var str="";
    for(var j=0;j<p.length;j++){
      str+=(j+1).toString()+m[p[j].toString()];
    }
    str+=n.toString();
    var ary = str.split(",");
    var tmp = Number(ary[0]);
    for(j=1;j<(ary.length-1);j++){
      if(ary[j]==="+"){
        tmp+=Number(ary[j+1]);
      } else if(ary[j]==="-"){
        tmp-=Number(ary[j+1]);
      }
    }
    if(tmp===100){
      res.push(ary.join(""));
    }
  }
  console.log("result",res);
};
calc(9)

結果
["123+45-67+8-9", "123+4-5+67-89", "123-45-67+89", "123-4-5-6-7+8-9", "12+3+4+5-6-7+89", "12+3-4+5+67+8+9", "12-3-4+5-6+7+89", "1+23-4+56+7+8+9", "1+23-4+5+6+78-9", "1+2+34-5+67-8+9", "1+2+3-4+5+6+78+9"]
11個

1時間では解けなかったので失格ではありますが。