2014 APL Programming Contest 3rd place entry
Again, I’m the 3rd place. Here are the problems and the code.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| U←⎕A | |
| L←⎕UCS 32+⎕UCS U | |
| Count←{+/⍵⍷⍺} | |
| MostFrequent←{ | |
| kmers←∪⍵,/⍺ | |
| counts←(⊂⍺)Count¨kmers | |
| (counts=⌈/counts)/kmers | |
| } | |
| FindClumps←{ | |
| kmers←∪⍵[1],/⍺ | |
| counts←kmers(⍵[2]{⌈/⍺⍺+/⍺⍷⍵})¨⊂⍺ | |
| (counts≥⍵[3])/kmers | |
| } | |
| ⍝ A helper function, return position of all 1's | |
| P ← {¯1+⍵/⍳⍴⍵} | |
| ApproxMatch←{P ⍺⍺≥(⊂⍵)+.≠¨(⍴⍵),/⍺} | |
| SharedKmers←{ | |
| A←⍺⍺,/⍺ | |
| B←⍺⍺,/⍵ | |
| ⍝ match both the string and it's reverse complement | |
| match←{P B∊('TGAC'['ACTG'⍳⊖⍵] ⍵)} | |
| ⊃,/(¯1+⍳⍴A)∘.,¨(match¨A) | |
| } | |
| LongestShared ← {⍺ (∩ KmerOperator ¯1) ⍵} | |
| ShortestNonShared ← {⍺ (~ KmerOperator 1) ⍵} | |
| KmerOperator←{ | |
| a←⍵ | |
| b←⍺ | |
| ⍝ For each length, find all kmer of the same length and operate on them | |
| r←(⍺⍺{(∪⍵,/b)⍺⍺∪⍵,/a})¨⍳(⍴⍵)⌊⍴⍺ | |
| ⊃⍵⍵↑(0<⊃∘⍴¨r)/r | |
| } | |
| EditDistance←{ | |
| ⍝ compute next row from previous row ⍵ | |
| ⍝ min(prevrow[i]+1, | |
| ⍝ prevrow[i-1]+notequal, | |
| ⍝ currentrow[i-1]+1) | |
| ⍝ (string1 f maxlength) string2 | |
| ⍝ ↓ new row ↓ prev row | |
| f←⍵{⊃{⍵,(⊃⊖⍵+1)⌊⍺}/⊖(1+⍵)⌊⍵⍵,(¯1↓⍵)+⍺⍺≠⍺}(⍴⍺,⍵) | |
| ⍝ reduce over the rows | |
| ⊃⊖⊃f/(⊖⍺),⊂¯1+⍳1+⍴⍵ | |
| } | |
| VigEncrypt ← {⎕UCS 65+26|¯130+((⍴⍵)⍴⎕UCS ⍺)+⎕UCS ⍵} | |
| VigDecrypt ← {⎕UCS 65+26|26-((⍴⍵)⍴⎕UCS ⍺)-⎕UCS ⍵} | |
| Normalise←{ | |
| ⍝ add space in beginning and end, and map everything to uppercase or space | |
| a←' ',(U,U,' ')[(U,L)⍳⎕SE.UnicodeFile.ReadText ⍵],' ' | |
| ⍝ remove extra space | |
| 1↓¯1↓(~' '⍷a)/a | |
| } | |
| BookEncrypt←{ | |
| ⍝ position of the start of words | |
| w←0,{⍵/⍳⍴⍵}' '=⍺ | |
| ⍝ all possible ways to specify a position | |
| table←{p←((w≤⍵)∧w≥⍵-20)/⍳⍴w | |
| p,¨⍵-w[p]}¨⍳⍴⍺ | |
| ⍝ pick a random position to encode a letter | |
| ⊃,/⍺{c←⊃,/(⍺⍺=⍵)/table | |
| ⊃c[1?⊃⍴c]}¨⍵ | |
| } | |
| BookDecrypt←{ | |
| w←0,{⍵/⍳⍴⍵}' '=⍺ | |
| ⍺{⍺⍺[w[⍺]+⍵]}/((0.5×⍴⍵),2)⍴⍵ | |
| } | |
| PlayfairTable ← {5 5⍴∪(U[(⍳9),9,10+(⍳16)])[U⍳(∪⍵),U~∪⍵]} | |
| PlayfairEncrypt←{ | |
| w←⍵,(2|⊃⍴⍵)⍴'Z' | |
| ⍝ interleave the strings ABC... and XXXXX... to get AXBXCX... | |
| ⍝ then remove the extra X's | |
| w←(,((⍴w)⍴1),[1.5](2=/w,0))/(,w,[1.5]((⍴w)⍴'X')) | |
| w←w,(2|⊃⍴w)⍴'Z' | |
| ⍝ the actual coding is handled by Digraph | |
| ⊃,/(0 Digraph ⍺)/(⊃(⍴w)÷2)2⍴w | |
| } | |
| PlayfairDecrypt←{⊃,/(¯2 Digraph ⍺)/(⊃(⍴⍵)÷2)2⍴⍵} | |
| Digraph←{ | |
| ⍝ find the positions of the two characters | |
| v←⊃,/⍵⍵{(,⍺⍺∊⍵)/,⍳⍴⍺⍺}¨(⍺ ⍵) | |
| ⍝ ↓ not same row, col | |
| ⍵⍵[⊃((⍱/⊃=/v),⊃=/v)/(⊂↓0 1⊖↑v),1+5|(v v)+¨(⊂⊂¯1 ⍺⍺),⊂⊂⍺⍺ ¯1] | |
| ⍝ ↑ filter correct result ↑ same row, col | |
| } | |
| D←{ | |
| ⍝ create a nested array of diagonals | |
| ((,⍵){(⍵⍵=⍵)/⍺⍺}(,(⍳⊃⊖⍴⍵)∘.+⍳⊃⍴⍵))¨⍳+/⍴⍵ | |
| } | |
| WordSearch←{ | |
| ⍝ all directions of the tables | |
| d←{(↓⍵)(↓⌽⍉⍵)(↓⌽⊖⍵)(↓⊖⍉⍵)(D ⍵)(D⌽⍉⍵)(D⌽⊖⍵)(D⊖⍉⍵)} | |
| ⍝ table of positions | |
| pos←⊃,/(d⊂¨⍳⍴⍺),¨¨¨⊂∘⊂∘⊂¨'E' 'N' 'W' 'S' 'SW' 'SE' 'NE' 'NW' | |
| puz←⊃,/d ⍺ | |
| ⍝ ↓ successful match? | |
| match←⍵{((⍵{∨/⍵⍷⍺⍺})¨⍺⍺)/(⍵{(⊂⍵),⊃(⍵⍷⍺⍺)/⍵⍵}⍺)¨⍺⍺} | |
| ⍝ ↑ information about the matched position | |
| ↑⊃,/pos match¨puz | |
| } | |
| BuildDictionary←{ | |
| {({~0∊⍴⍵}¨⍵)/⍵}{({∧/⍵∊L}¨⍵)/⍵}⊃,/⎕SE.UnicodeFile.ReadNestedText¨((⊂⍵),¨⎕CMD'DIR ',⍵,' /B')} | |
| MaxWord←{ | |
| v←1 3 3 2 1 4 2 4 1 8 5 1 3 1 1 3 10 1 1 1 1 4 4 8 4 10 0 | |
| d←(⊂⍵),{U[L⍳⍵]}¨{({7≥⊃⍴⍵}¨⍵)/⍵}⍺ ⍝ dictionary | |
| h←(∪⍵)~'?' ⍝ the set character | |
| table←d∘.{+/⍺=⍵}h ⍝ how many of each character | |
| r←,(1↑table) ⍝ first row | |
| extra←(⊃∘⍴¨d)-+/table ⍝ amount of letters require '?' to cover | |
| feasible←(extra++/0⌈-table(-[2])r)≤⊃extra ⍝ is it feasible | |
| s←↓1↓feasible⌿table | |
| d←1↓feasible/d | |
| value←d{(50×7=⊃⍴⍺)+(v[U⍳h])+.×r⌊⍵}¨s | |
| i←{⍵⍳⌈/⍵}value | |
| ⍝ construct the solution | |
| spell←{ | |
| ⍝ characters needs to be replaced | |
| rep←(⍺~h),(⍵-r⌊⍵)/h | |
| {a←⍵ | |
| a[a⍳⍺]←'?' | |
| a}/rep,⊂⍺ | |
| } | |
| ((⊃d[i])spell⊃s[i]),value[i] | |
| } | |
| hands←DealHands | |
| hands←(↓4 13⍴52?52)-1 | |
| Suits ←{(⊂⍵){(⍵=1+⌊⍺÷13)/13|⍺}¨⍳4} | |
| ShowHand←{↑'♠♡♢♣'{⍺,⊂{('-'/⍨''≡⍵),⍵}('23456789TJQKA'[⍵[⍒⍵]])}¨(1+Suits ⍵)} | |
| ValueHand←{ | |
| ⍝ high cards , distribution ↓trick 4A+1,0A-1 ↓other correction rules | |
| (+/¯8+8⌈13|⍵),(+/{0⌈¯4++/0≤⍵}¨Suits ⍵),(⌊(¯1++/12=13|⍵)÷3)++/{+/-(3 2 1=⊃⍴⍵)∧10 11 12∊⍵}¨Suits ⍵ | |
| } | |
| ⍝ input test | |
| ⍝ ValueHand 12 10 23 22 18 37 35 34 33 31 27 50 46 | |
| Simulate←{ | |
| v←⊃,/{⊃∘ValueHand¨DealHands}¨⍳⍵ | |
| grand←(+/37=+/(2×⍵ 1)⍴v) | |
| high←{+/v=⍵}¨¯1+⍳38 | |
| (⊂⍉3 38⍴(¯1+⍳38),high,high÷⍴v),⊂grand,grand÷⍵ | |
| } |