CodeIQのデスコロ#2にPrologで挑戦してみた。

最近このサイトが面白くて遊んでます。CodeIQデスコロ#2

問題は、abcdefghijklmnopqrstuvwxyzの26文字を50回繰り返して出力するプログラムを書くこと。そしてそのソースコードをできるだけ短くすると。
　ただし、上記のアルファベット列、最初のaを１番目としてx番目の文字を、
・xが素数である
・xの中に「３」が含まれない。(3,13,33,130など、桁の数に３があるとだめ）
という条件を両方とも満たした場合、大文字にして出力します。なので、こんな感じになります。

aBcdEfGhijKlmn.....

最初はCで書いていたのですが、なかなか短くできず最短にはなれないことがわかってきたので、思いっきり日和ってPrologで書いてみました。

p(X,Y):-X>=Y*Y->X mod Y=\=0,p(X,Y+1);X>1.

t(X):-X mod 10=\=3,(X>9->t(X//10);true).

a(1300).

a(X):-Y is X+1,(p(Y,2),t(Y)->C is 65;C is 97),Z is X mod 26+C,format('~c',Z),a(Y).

:-a(0).

こんな感じ。

１行目のp(X,Y)で素数の判定。XがYで割り切れればアウト判定。

　Yの２乗がXより大きい場合は、割り切れないことが確定なのですが、Xが１の場合のみ失敗。

　そうでない場合は、XをYで割った余りが0でなければ、XをY+1で割り切れるかトライする。

って感じで、１行に無理やりまとめてます。ここで、普通はやっちゃいけないのが

  p(X,Y+1) の部分。PrologではY+1と書くと、Y+1を演算した結果を渡すのではなく、+(Y,1)という項をそのまま渡してしまいます。よって、気をつけないととんでもないことになるのですが、文字数を減らすため、わざと項のままつっこんでます。これは、再度呼び出されたp(X,Y）のなかの条件式を評価する時に展開されます。

２行目のt(X)はXに３が含まれているかのテスト。これもかなり論理をいじってます。

　X を１０で割った余りが3でない場合（３で割れたらばfailして失敗）、Xが１０以上であれば、t(X//10)で10で割った値に対してトライします。Xが一桁ならtueで成功と。ここもわざとt(X//10)にして項の評価を後回しにしてます。

最後のa(X)で文字を出していきます。

1300文字出したら終了

1300文字までは、上記条件を満たすかどうかをp(X,Y),t(X)で判定して、満たしていれば大文字にしています。

普通にPrologで書くとこんな感じになると思います。
素数かつ、３を含まない場合には大文字で、そうでなければ小文字で出力。1301まできたら終了。そして、素数判定も、「３」がある判定もある意味、普通に書くとこんな感じでしょうね。

isPrime(1):-!,fail.        //1は特別扱い

isPrime(X):-isPrime1(X,2). //それ以外は２からの数で割り切れるかチェック

isPrime1(X,Y):-X < Y*Y.

isPrime1(X,Y):-X mod Y =:= 0 ,!,fail.

isPrime1(X,Y):-Y1 is Y + 1,

              isPrime1(X,Y1).

isInThree(X) :- X mod 10 =:= 3. //３で割り切れればtrue.

isInThree(X) :- X > 9 , !,      //割り切れない場合、10以上であれば

              X1 is X // 10,    //数を１０で割って、「３」があるかチェック

              isInThree(X1).

answer(1301).

answer(X) :- isPrime(X),

             not(isInThree(X)),

             Z is 65 + (X - 1) mod 26, //文字コードの計算です

             format('~c',Z),

             X1 is X + 1,

             answer(X1).

answer(X) :- Z is 97 + (X - 1) mod 26, //文字コードの計算です

             format('~c',Z),

             X1 is X + 1,

             answer(X1).

:-answer(1).

そして、最短になるまえに挫折した(笑)Cのソースもだしてみます。本当は１行に詰めてるんですが、読みにくいので適当に改行いれてます。

int n,i=1,f;

main(){

 for(;

      i<1301 p="">

      putchar((i++-1)%26+97-f*32)

      )

   for(n=f=i%10!=3&i/10%10!=3&i/100!=3&i>1;

        ++n

        f=i%n&&f

        );

exit(0);

}

for文のなかに初期化やその後の処理を無理やり詰めて、一文字でも短くしようとしています。セコイです。

２つめのforループですが素数判定と３があるかないかを判断しています。素数かつ３が含まれていない場合、f=1。そうでないならf=0として処理を進めます。

　まずfにiの中に３が含まれていれば０、含まれてなければ１となるように値を論理式で求めます。ここで、i=1つまりaの時は素数ではないのでむりやり０にします。そして、for文の処理のところ、f=i%n&&fで素数かどうかを判定しています。nは、iに３が含まれる時やi=1の時に０になっているので、いきなり１で割るかどうかを判定しちゃうのですが、すでにf=0となっているので、結果としては同じになるのです。わかりにくいですね。

　そして、２個目のfor文が終わるとputcharにはいって文字を出します。fの値によって大文字と小文字を判別します。

　まぁ、もっと短くなるようなので、参考程度に。