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

チンイツの待ち問題

makeplex salon:あなたのスキルで飯は食えるか? 史上最大のコーディングスキル判定 (1/2) - ITmedia エンタープライズ
にある問題を解いてみた.

  • 再帰で実装
  • 頭や暗刻は一つの数字につき高々1つであることを利用
  • 1111222333444で1単騎を待ちとしてしまう
  • 七対子については言及されてなかったから実装しなかった.(簡単だしいいでしょ)
  • あってるかは不明(通りすがりさんの指摘でカンチャンを忘れてるのをなおしました.)
  • 実装時間は40分ほど.
public class Machi {
    public static void main(String[] args) {
        int[] hais = new int[20];
        for(int i=0;i<13;++i)hais[Integer.parseInt(""+args[0].charAt(i))]++;
        solve(1,hais,false,"");
    }
    //七対子は判定できない
    public static void solve(int ind, int[] hais, boolean atama,String s){
        int num =0;//残りの牌数
        int min =10;//最小の牌
        for(int i=9;i>0;i--){
            num+=hais[i];
            if(hais[i]>0)min=i;
        }
        //残り1枚なら単騎待ち
        if(num==1){
            System.out.println(s+"["+min+"]");
            return;
        }
        //残り2枚なら両面(ペンチャン)かシャボ -- 嘘です,カンチャンがあります
        if(num==2){
            if(hais[min]==2)System.out.println(s+"["+min+""+min+"]");
            if(hais[min]==1&&hais[min+1]==1)System.out.println(s+"["+min+""+(min+1)+"]");
            if(hais[min]==1&&hais[min+2]==1)System.out.println(s+"["+min+""+(min+2)+"]");//追加  
            return;
        }
        //順子
        if(hais[ind]>=1&&hais[ind+1]>=1&&hais[ind+2]>=1){
            hais[ind]--;hais[ind+1]--;hais[ind+2]--;
            solve(ind,hais,atama,s+"("+ind+""+(ind+1)+""+(ind+2)+")");
            hais[ind]++;hais[ind+1]++;hais[ind+2]++;
        }
        //暗刻
        if(hais[ind]>=3){
            hais[ind]-=3;
            solve(ind+1,hais,atama,s+"("+ind+""+ind+""+ind+")");
            hais[ind]+=3;
        }
        //頭
        if(hais[ind]>=2&&!atama){
            hais[ind]-=2;
            solve(ind+1,hais,true,s+"("+ind+""+ind+")");
            hais[ind]+=2;
        }
        //待ち
        if(ind<9)solve(ind+1,hais,atama,s);
    }
}


ついでに実行結果

coffee:machi# javac Machi.java
coffee:machi# java Machi 1112224588899
(111)(222)(888)(99)[45]
coffee:machi# java Machi 1122335556799
(123)(123)(567)(55)[99]
(123)(123)(567)(99)[55]
(123)(123)(555)(99)[67]
coffee:machi# java Machi 1112223335559
(123)(123)(123)(555)[9]
(111)(222)(333)(555)[9]
coffee:machi# java Machi 1223344888999
(123)(234)(888)(999)[4]
(123)(44)(888)(999)[23]
(234)(234)(888)(999)[1]
coffee:machi# java Machi 1112345678999
(123)(11)(456)(789)[99]
(123)(11)(456)(999)[78]
(123)(11)(678)(999)[45]
(123)(456)(789)(99)[11]
(111)(234)(567)(999)[8]
(111)(234)(567)(99)[89]
(111)(234)(678)(999)[5]
(111)(234)(789)(99)[56]
(111)(345)(678)(999)[2]
(111)(456)(789)(99)[23]
(11)(345)(678)(999)[12]


4/4 追記
ゴルフをしてる人(史上最大のコーディングスキル判定 - yuyarinの日記)がいたのでやってみた.
617B.javaでやるのが間違いだろうけど,まずまずの短かさだと思う.
rubyとかに翻訳すればもっと短くなるはず

public class A{public static void main(String[]a){int[]h=new int[20];for(int i=0;i<13;)h[Integer.parseInt(""+a[0].charAt(i++))]++;r(1,13,h,"");}static void r(int i,int n,int[]h,String s){int m=9;for(int j=9;j>0;)if(h[--j]>0)m=j;if(n<3){System.out.print(n<2?s+"["+m+"]\n":h[m]>1?s+"["+m+m+"]\n":h[m+1]>0?s+"["+m+(m+1)+"]\n":h[m+2]>0?s+"["+m+(m+2)+"]\n":"");return;}if(h[i]*h[i+1]*h[i+2]>0){h[i]--;h[i+1]--;h[i+2]--;r(i,n-3,h,s+"("+i+(i+1)+(i+2)+")");h[i]++;h[i+1]++;h[i+2]++;}if(h[i]>2){h[i]-=3;r(i+1,n-3,h,s+"("+i+i+i+")");h[i]+=3;}if(h[i]>1&&n%3==1){h[i]-=2;r(i+1,n-2,h,s+"("+i+i+")");h[i]+=2;}if(i<9)r(i+1,n,h,s);}}