LoginSignup
3
1
paiza×Qiita記事投稿キャンペーン「プログラミング問題をやってみて書いたコードを投稿しよう！」
@TD12734

【paiza×Qiita】JavaScriptで最小文字数での解答を目指す【Aランク編】

Posted at

はじめに

こちらのpaiza×Qiita記事投稿キャンペーンのCランク問題を、コードゴルフの要領で最小文字数で解答することを目指しました。
言語はJavaScriptです。

他のランクはこちら

多分これが一番短いと思います

本の整理

I=0;require('readline').createInterface({input:process.stdin}).on('line',m=>+m||console.log((a=m.split` `.map(i=>i-1)).filter(i=>(a[j=a.indexOf(I,++I)]=i)*~j).length))

167文字

山折り谷折り

process.stdin.some(l=>{for(a="";l--;)a+=0+a.split``.reduce((b,c)=>(c-1?1:0)+b,"");console.log(a)})

98文字

ハノイの塔

H=[[b=" ",b,b]];process.stdin.some(l=>{[n,t]=(0+l).split` `;for(i=0;i++<n;)H=H.reduceRight((a,c)=>([[A=i+b+c[0],B=c[2],C=c[1]],...a,[C,B,A]]),[]);H[+t].map(c=>console.log(c!=b?c.trim():"-"))})

192文字

じゃんけんの手の出し方

N=W=C=P=0;process.stdin.some(l=>{(0+l).split`
`.map(a=>{if(N&&a){for(i=N;i--;a[i]>"O"&&P++)a[i]<"D"&&C++;G=N-C-P;for(i=N;i>=0;i--)for(j=N-i;j>=0;j--)W=M-2*j-5*(k=N-i-j)||W>(w=(i<C?i:C)+(j<P?j:P)+(k<G?k:G))?W:w;console.log(W)}else[N,M]=a.split` `})})

249文字

お菓子の詰め合わせ

process.stdin.some(l=>{[m,...O]=(0+l).split`
`;[N,X,A]=m.split` `;for(i=N;!A||console.log(X-A);B(N,i--))B=(j,t,k=0)=>{for(;~--j;B(j,t-1,K))A=X<(K=+O[j]+k)||t||A>K?A:K}})

169文字

解説

本の整理

I=0;
require('readline').createInterface({input:process.stdin}).on('line',m=>
  +m||
  console.log((a=m.split` `.map(i=>i-1)).filter(i=>
    (a[j=a.indexOf(I,++I)]=i)*~j).length
  )
)

Iは現在参照している本です。
以下の事をしています。

  1. 現在の行が0ではない数値に変換できるとき(1行目)、終了
  2. 現在の行が0ではない数値に変換できないとき(2行目)、まずは現在の行を空白区切りで、さらに値を1引いて(ついでに数字を数値に変換した)配列のaを作る
  3. jにIDがIの本のインデックスを代入する。ただし、インデックスはI+1以降に限定する(ここでIもインクリメント)
  4. jが-1の時は~0になり、filterがfalseになって終了
  5. jが-1では無い時、a[j]の本をiにする
    • iの本はもう参照しないのでそのままです(交換とは一体・・・)
  6. 最後にフィルターされた配列の長さを出力する

上記のコードは問題文ガン無視で交換していません。
こっちの方が文字数を削減できますし、こうするのも仕方ない。

なお、標準入力はこれでないと最後のテストの出力時にエラー落ちします。
また、以下のコードの方が短いですが、++I+""による文字列置換が重い所為でタイムアウトします。

I=0;require('readline').createInterface({input:process.stdin}).on('line',m=>+m||console.log((a=m.split` `).filter(i=>(a[j=a.indexOf(++I+"",I)]=i)*~j).length))

山折り谷折り

process.stdin.some(l=>{
  for(a="";l--;)a+=0+a.split``.reduce((b,c)=>
    (c-1?1:0)+b
  ,"");
  console.log(a)
})

N回折った時、折り目は中央は0、中央から左はN-1回目の結果、中央から右はN-1回目の結果の01と左右を反転させた物になります。
この仕組みに気付けば簡単ですが、気付くまでが大変です。
コードの処理としては以下のようになります。

  1. for文の初期化時にa(出力)に空白文字を代入する
  2. forでl(入力された値)回ループして以下の事を行う
    1. aに0を足す
    2. reduce文でN-1回目の結果の01と左右を反転させた文字列を作り、それを足す
      • 文字列としての数字を引き算すると数値になる事と、0がfalse扱いされる事を利用してc-1がtrue(c="0")の時は1、false(c="1")の時は0を反転させた文字列に加えています
  3. 最後にaを出力

また、以下に参考としてaが配列の版も残しておきます。
こちらも短縮の余地があるかもしれません。

process.stdin.some(l=>{for(a=[0];--l;)a=[...a,0,...a.reverse().map(m=>m?0:1)];console.log(a.join``)})

ハノイの塔

H=[[b=" ",b,b]];
process.stdin.some(l=>{
  [n,t]=(0+l).split` `;
  for(i=0;i++<n;)H=H.reduceRight((a,c)=>
    ([[A=i+b+c[0],B=c[2],C=c[1]],...a,[C,B,A]]),[]);
  H[+t].map(c=>console.log(c!=b?c.trim():"-"))
})

Hはハノイの塔の状態の配列、bは (空白)です。
まず、ハノイの塔には以下の性質があります。

  1. 初期状態(t=0)も含めると、全部で2のn乗個の状態が存在する
  2. 状態の前半(t=0から2の(n-1)乗)までは杭Aがn-1の杭Aにnの円盤を追加した状態、杭Bがn-1の杭Cの状態、杭Cがn-1の杭Bの状態と同一になる
  3. 状態の後半からは杭Aは前半の杭C、杭Bは前半の杭B、杭Bは前半の杭Aの状態を時間的に逆転させたものになる

以上を踏まえて、以下のようなコードを書きました。

  1. reduceRightで前回のHについて、逆順でn回以下の事をする
    1. n回目のHの先頭に[前回のHの杭Aにiを加えた物,前回のHの杭C,前回のHの杭B]の配列を加える
    2. n回目のHの末尾に[今回のHの杭C,今回のHの杭B,今回のHの杭A]の配列を加える
  2. 今回のHのt回目の各状態を出力する
    • tは改行を含む文字列なので+を前に付けて数値に変換する
    • 空白なら-を出力する
    • 3 みたいな出力だと失格扱いになるのでtrimで末尾の空白を消す

じゃんけんの手の出し方

N=W=C=P=0;
process.stdin.some(l=>{(0+l).split`
`.map(a=>{
  if(N&&a){
    for(i=N;i--;a[i]>"O"&&P++)a[i]<"D"&&C++;
    G=N-C-P;
    for(i=N;i>=0;i--)for(j=N-i;j>=0;j--)W=M-2*j-5*(k=N-i-j)||W>(w=(i<C?i:C)+(j<P?j:P)+(k<G?k:G))?W:w;
    console.log(W)
  }else[N,M]=a.split` `})
})

C,G,PはC,G,Pの文字の数、Wは最多勝利回数、wはループ内での勝利回数です。
以下の事をしています。

  1. Nが0の時(1行目)か現在の行がfalsy(3行目として追加される改行)の時、NとMに値を代入する
  2. 2行目の時、まずはC,G,Pの数を数える
    • ==で比較するよりも不等号でCとPを判別する方が短く書けます
    • 上記のようにすればifを使わずに書けます
    • GはN-C-Pをして求めます
  3. グーがN～0(=i)回出された時、チョキがN-i(=j)回出された時、パーがN-i-j(=k)回出された時の指の本数と勝利回数を全て求める
    • 指をM本使ったかどうかはM-2j-5kが0かどうかで判断しています
    • 勝利回数(w)は(iとCの小さい方)+(jとPの小さい方)+(kとGの小さい方)の合計で求めて、wがWよりも大きければWにwを代入します
  4. 最後にWを出力

つまるところ、総当たりで調べています。
もっと良いロジックが思い付けばfor文の数も減らせて、文字数も削減できる気がしますが思い付かない・・・
力技な点と言いコードがAランクの中で最長の点と言い、Aランクの中で最も改善の余地がありそうですね。
また、試行回数が多そうな割には本の整理と違ってタイムアウトしそうな気配が無いのは意外でした。

お菓子の詰め合わせ

process.stdin.some(l=>{[m,...O]=(0+l).split`
`;
[N,X,A]=m.split` `;
for(i=N;!A||console.log(X-A);B(N,i--))B=(j,t,k=0)=>{
  for(;~--j;B(j,t-1,K))A=X<(K=+O[j]+k)||t||A>K?A:K
}})

Oはお菓子の金額の配列、Aはお釣りが最小となるお菓子の購入金額、Bはお菓子購入用の再帰関数です。
以下の事をしています。

  1. 1行目をm、2行目以降をOに代入
  2. NとXを1行目から代入し、ついでにAにundefinedを代入
  3. iにNを代入し、Aに金額が入っていない間はループでB(N,i--)を呼び続ける
  4. forの中で再帰関数Bを定義する。これはforの中で定義する必要は無いが、forの中だと;を消せる
    1. Bではまず、j(参照しているお菓子のインデックス)をデクリメントする。-1になるまでループする
    2. XがK(現在参照しているお菓子と今まで買ったお菓子の合計金額)より小さい、またはt(お菓子を買う残り回数)が0ではない、またはAがKより大きい時はAにAを代入する。そうでなければAにKを代入する
    3. B(j,t-1,K)を実行し、1個前のインデックスのお菓子を買う処理をする
  5. Aに何かしらの値が入った時、ログを出力してループを抜ける
  6. そうでない時、お菓子を買う個数を1減らしてループに戻る

こっちも総当たりで調べています。
そうは言ってもじゃんけんよりはスマートに書けた感じがします。

おわりに

何だか簡単かと思ったらタイムアウト要素が出て来て驚きました。
コードの短さだけでなく実行時間の短さも求められるとは。
タイムアウトが30秒ぐらいなら何とかなりそうですが、16秒は結構厳しいですね。

このイベントに期限間近で気付きましたが、何とかAランクまでは解けました。
Sランクは気が向けば解いてみます。

3
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
3
1