Google Code Jam 2016 Qualification

今年的GCJ有一點小嘗試，在無時限的Qualification用不多人用過的Q來寫。

為了方便大家，這裏便是documentation。
http://code.kx.com/wiki/Main_Page


題目也不多說了，只集中寫一寫今次的一些學習。詳細要看題目的在這裏
https://code.google.com/codejam/contest/6254486/dashboard

Problem A

a:read0`:al.in;

f:{ distinct raze string x*1+til y };
g:{
  k:f[x;]each 1+til 100;
  ret:x*1+first where 10=count each k;
  $[null ret;"INSOMNIA";string ret]};
res:g each 1_"I"$a;

output:{"Case #",string[x],": "} each 1+til -1+count a;
`:al.out 0:output,'res

先簡介一下程式，大概便是先把input變成一個string list (a)，再通過function f和g去處理input，最後兩行便是把output放入file中。


這題剛開始熱身，便假設n在100次以內必然會出現0-9起碼一次(其實可以證明的)。主要把每一個數字變成string，再串起來，加上distinct，來判斷是否有10個不同的數字(Function f)。

Problem B

a:read0`:bl.in;

f:{
  x:x where differ x;
  if["+"=last x;x:-1_x];
  string count x };

res:f each 1_a;

output:{"Case #",string[x],": "} each 1+til -1+count a;
`:bl.out 0:output,'res

這一題主要用了一個trick，去掉所有連續的+和-，以及最後一個+，便可根據剩下的string的長度來得出答案。特別一提Q中的x where differ x便可以做到去掉連續的效果，很簡潔。

Problem C

res:{"2",raze string ?[-15#0b vs x;22;11],"2"} each 1+til 500;
`:cl.out 0:(enlist "Case #1:"),(raze each string "2"=res),\:raze " ",'string 3+til 9

最喜歡要算是這題，利用了有連續的1在base n必會整除(n+1)。所以基本上做法是把長k的01 string，去掉頭尾的1，再分成(k-1)/2組，每組必然是11或00。然後根據10進位轉2進位的方法，用頭500個數的二進位來放進那些組中。

Q的轉二進位很容易，在0b vs x這句中做到，更可以因為vector conditional來一次過製造最終的組合(全都在第一行做了)。第二行只是給出指定的output format。

Problem D

a:read0`:dl.in;

pow:{show y;$[y;$[y mod 2;:pow[x;y-1]*x;:g*g:pow[x;y div 2]];:1]};

f:{
 c:"J"$" " vs x;
 n:c[0]; k:c[1]; s:c[2];
 if[s<try:1+(n-1)div k;:"IMPOSSIBLE"];
 id:(try;k)#til n;
 pp:pow[n;]each til k;
 " " sv string 1+sum each id*\:pp };

res:f each 1_a;
res

output:{"Case #",string[x],": "} each 1+til -1+count a;
`:dl.out 0:output,'res

這一題算最複雜。或者可以寫得更簡單，但大致上的原理是算出每一個generation所要取的位置，再乘以n的power，以得出最後要得的index。特別喜歡(try;k)#til n這一行，基本上它把0到n-1自動放進try x k的表格中，並自動wrap over。然後便可以用vector operation直接乘以n的power，加起來便是所需的index。