how i won the 2019 apl problem solving competition

    ┌────────┐     ┌────────────────────────────────────────────────────┐
    │ title  ├─────┤ how i won the 2019 apl problem solving competition │
    └────────┘     └────────────────────────────────────────────────────┘

    ┌────────┐     ┌────────────────────────────────────────────────────┐
    │ by     ├─────┤ jamin wu                                           │
    └────────┘     └────────────────────────────────────────────────────┘

    ┌───────────┐     ┌─────────────────────────────────────────────────┐
    │ thank you ├──┬──┤ Dyalog!                                         │
    └───────────┘  │  └─────────────────────────────────────────────────┘
                   │
                   │  ┌───────────────────────┐     ┌───────────────────┐
                   ├──┤ competition sponsors  ├──┬──┤ Fiserv            │
                   │  └───────────────────────┘  │  └───────────────────┘
                   │                             │
                   │                             │  ┌───────────────────┐
                   │                             └──┤ SimCorp           │
                   │                                └───────────────────┘
                   │
                   │  ┌─────────────────────────────────────────────────┐
                   └──┤ competition organisers & writers                │
                      └─────────────────────────────────────────────────┘

┌────────────────────┐ ┌──────────────────────────────┐
│ contents           ├┬┤ background                   │
└────────────────────┘│└──────────────────────────────┘
                      │┌──────────────────────────────┐ ┌──────┬─────────────────────────┐
                      ├┤ problems                     ├┬┤ E1.1 │ Cooking on the Grille   │
                      │└──────────────────────────────┘│└──────┴─────────────────────────┘
                      │                                │┌──────┬─────────────────────────┐
                      │                                ├┤ E1.3 │ When in Prison...       │
                      │                                │└──────┴─────────────────────────┘
                      │                                │┌──────┬─────────────────────────┐
                      │                                ├┤ E3.3 │ Watch Out for that Mine │
                      │                                │└──────┴─────────────────────────┘
                      │                                │┌──────┬─────────────────────────┐
                      │                                ├┤ M2.1 │ Trapezoid Rule          │
                      │                                │└──────┴─────────────────────────┘
                      │                                │┌──────┬─────────────────────────┐
                      │                                ├┤ M2.3 │ Romberg's Method        │
                      │                                │└──────┴─────────────────────────┘
                      │                                │┌──────┬─────────────────────────┐
                      │                                ├┤ D3.1 │ Construction & Unfold.. │
                      │                                │└──────┴─────────────────────────┘
                      │                                │┌──────┬─────────────────────────┐
                      │                                └┤ D3.2 │ Twist & Shout           │
                      │                                 └──────┴─────────────────────────┘
                      │┌──────────────────────────────┐ ┌────────────────────────────────┐
                      └┤ reflection                   ├┬┤ good things                    │
                       └──────────────────────────────┘│└────────────────────────────────┘
                                                       │┌────────────────────────────────┐
                                                       └┤ thoughts                       │
                                                        └────────────────────────────────┘

┌──────────────────────┐ ┌──────────────────────┐
│ studying             ├┬┤ med @ Monash (AU)    │
└──────────────────────┘│└──────────────────────┘
                        │┌──────────────────────┐
                        └┤ hobby programmer     │
                         └──────────────────────┘
┌──────────────────────┐ ┌──────────────────────┐
│ languages            ├┬┤ python               │
└──────────────────────┘│└──────────────────────┘
                        │┌──────────────────────┐
                        └┤ elm                  │
                         └──────────────────────┘
┌──────────────────────┐ ┌──────────────────────┐
│ preferences          ├┬┤ static types         │
└──────────────────────┘│└──────────────────────┘
                        │┌──────────────────────┐
                        ├┤ functional           │
                        │└──────────────────────┘
                        │┌──────────────────────┐
                        └┤ emacs + evil         │
                         └──────────────────────┘
┌──────────────────────┐ ┌──────────────────────┐
│ intro to apl/j/k     ├┬┤ project euler forums │
└──────────────────────┘│└──────────────────────┘
                        │┌──────────────────────┐
                        ├┤ news aggregators     │
                        │└──────────────────────┘
                        │┌──────────────────────┐
                        └┤ game of life video   │
                         └──────────────────────┘

Define Grille which takes a left argument grille and a right argument character grid and returns the hidden message corresponding to positions of spaces in the grille, e.g.

    grille grid
┌──────┬──────┐
│##### │ESVWGT│
│#### #│HOWTHZ│
│# # # │HIVSAI│
│## ###│CASSAC│
│ ## ##│FAAUCM│
│ #####│NYMPCE│
└──────┴──────┘

    grille Grille grid
THISISFUN

      ┌──────┐
      │grille├──→  ∊ ──→  ' '=  ──┐
      └──────┘                    ↓      ┌─────────┐
                                  /  ──→ │ message │
      ┌──────┐                    ↑      └─────────┘
      │ grid ├──→  ∊  ────────────┘
      └──────┘


Grille←{(' '=∊⍺)/∊⍵}

Define TapEnc and TapDec which converts between a message and a tap encoding as defined by the following polybius square:

	1	2	3	4	5
1	A	B	C	D	E
2	F	G	H	I/J	K
3	L	M	N	O	P
4	Q	R	S	T	U
5	V	W	X	Y	Z

(I/J both map to the same encoding. When decoding, always produce I instead of J.) e.g.

        TapEnc 'APL'
* * *** ***** *** *

        TapDec '* * *** ***** *** *'
APL

TapEnc ──────────→

        TapLocate              TapKnocks                    Render
┌─────────┐    ┌──────────────────┐   ┌──────────────────────┐    ┌─────────────────┐
│ message ├────┤ alphabet indices ├───┤ polybius coordinates ├────┤ rendered knocks │
└─────────┘    └──────────────────┘   └──────────────────────┘    └─────────────────┘
        TapLocate⍣¯1          TapKnocks⍣¯1                   Parse

                                                               ←────────────── TapDec



TapAlpha←'ABCDEFGHIKLMNOPQRSTUVWXYZJ'
TapKnocks←↓∘⍉1+5 5⊤-∘1
TapLocate←(⊢-(17×∘⌊26÷⍨⊢))(TapAlpha∘⍳)

Render←' '(1↓∘∊,¨)'*'/⍨¨∊
TapEnc←Render TapKnocks∘TapLocate

Parse←(⍴∘1 0∘≢⊂⊢)(≢¨' '∘(≠⊆⊢))
TapDec←(TapKnocks∘TapLocate⍣¯1)Parse

Define MakeMines which takes a left argument number of mines and a right argument board size and returns a random minesweeper board, and define CountMines which fills non-mine cells with a number indicating how many mines surround it, e.g.

      ⊢ board ← 11 MakeMines 5 8
¯1  0 0  0 ¯1  0 ¯1 0
 0  0 0 ¯1 ¯1  0  0 0
¯1 ¯1 0  0  0 ¯1  0 0
¯1 ¯1 0  0  0  0  0 0
 0  0 0  0  0  0 ¯1 0

      CountMines board
¯1  1 1  3 ¯1  3 ¯1 1
 3  3 2 ¯1 ¯1  4  2 1
¯1 ¯1 3  2  3 ¯1  1 0
¯1 ¯1 2  0  1  2  2 1
 2  2 1  0  0  1 ¯1 1

┌────────────┐
│no. of mines├┐
└────────────┘│
              └→┌───────────┐
                │   ⍺?×/⍵   ├┐
              ┌→└───────────┘└→┌───────┐                   ┌──────────────┐
              │                │  ¯1@  ├┐                ┌→│{1++/|∊⍵}⌺3 3 ├─┐
┌─────┐       │ ┌───────────┐┌→└───────┘└→┌───┐  ┌─────┐ │ └──────────────┘ └→┌───┐   ┌─────┐
│shape├───────┴→│ ⍴∘0∘(×/)  ├┘            │ ⍴ │  │board├─┤                    │ × ├──→│ -∘1 │
└──┬──┘         └───────────┘           ┌→└───┘  └─────┘ │ ┌───┐            ┌→└───┘   └─────┘
   │                                    │                └→│0∘=├────────────┘
   └────────────────────────────────────┘                  └───┘


 MakeMines←{⍵∘⍴¯1@(⍺?×/⍵)⍴∘0∘(×/)⍵}
 CountMines←-∘1({1++/|∊⍵}⌺3 3)×0∘=

                  ┌────────┐
             ┌───→│ coeffs ├─────┐
             │    └────────┘     │
             │                   │
    ┌───┐    ├───→┌───────┐      │
    │ n ├────┤    │   Δx  ├──────┤
    └───┘    ├───→└───┬───┘      │   ┌───────────────────────────────────────┐
             │        ↓          ├──→│ (Δx÷2) × +/ ( coeffs × f  x₀ ... xn ) │
    ┌─────┐  ├───→┌───┴───────┐  │   └───────────────────────────────────────┘
    │ a b ├──┤    │ x₀ ... xn ├──┤
    └─────┘  └───→└───────────┘  │
                                 │
    ┌───┐                        │
    │ f ├────────────────────────┘
    └───┘


Trapezoid←{
     Coeffs←1⌽¯2↓1 1,2⍴⍨1+⊢
     Width←-(-/⊢)÷⊣
     Intervals←{(2⊃⍵),⍨(⊃⍵)+(⍺ Width ⍵)×(⍳⍺)-1}
     (2÷⍨⍺ Width ⍵)×+/(Coeffs ⍺)×⍺⍺ ⍺ Intervals ⍵
 }

R:0:0   R:0:1    R:0:2    R:0:3
      \   │   \    │   \    │
       \  │    \   │    \   │
        R:1:1    R:1:2    R:1:3
              \    │   \    │
               \   │    \   │
                 R:2:2    R:2:3
                       \    │
                        \   │
                          R:3:3


 Romberg←{
     Ts←(2*(⍳⍺+1)-1)⍺⍺ Trapezoid¨⊂⍵
     Rmn←{
         0=⍵:1⍴Ts[1]
         RmnPrev←∇(⍵-1)
         ⍵{
             0=⍵:1⍴Ts[⍺+1]
             RmPrev←⍺ ∇(⍵-1)
             RCalc←(1÷1-⍨4*⍵)×((4*⍵)×RmPrev[1])-(⌽RmnPrev)[⍵]
             RCalc,RmPrev
         }⍵
     }⍺
     ⊃Rmn
 }

Define a variable Cube representing a sorted Pocket Cube in an internal representation of your choosing.

┌─────┬─────┐
│1 0 0│1 0 0│                    -x
│0 1 0│0 1 0│                    ^     / +z
│0 0 1│0 0 1│                    |    /
├─────┼─────┤                  +-|-----+
│1 0 0│1 0 0│                 /  |    /|
│0 1 0│0 1 0│                /       / |
│0 0 1│0 0 1│         -y    +-------+  |     +y
└─────┴─────┘           <---|       | ------->
┌─────┬─────┐               |   /   | /
│1 0 0│1 0 0│               |  /    |/
│0 1 0│0 1 0│               +-/-----+
│0 0 1│0 0 1│                /   |
├─────┼─────┤               /    |
│1 0 0│1 0 0│              -z    v
│0 1 0│0 1 0│                    +x
│0 0 1│0 0 1│
└─────┴─────┘


 Cube←2 2 2⍴⊂3 3⍴1 0 0 0 1 0 0 0 1

┌──────┐    ┌─────────────────┐
│ Cube ├───→│ extract 6 faces │
└──────┘    └────────┬────────┘
                     ↓
            ┌────────┴───────────────────────┐
            │ which unit vector pointing out │
            └────────┬───────────────────────┘
                     ↓
            ┌────────┴─────────────────────────┐
            │ match each unit vector to colour │
            └────────┬─────────────────────────┘
                     ↓
            ┌──┬──┬──┬──┬──┬──┐
            │WW│YY│GG│BB│RR│OO│──────┐
            │WW│YY│GG│BB│RR│OO│      │       WW    
            └──┴──┴──┴──┴──┴──┘      │       WW
                                     ├───→ GGRRBBOO
                 ┌───┐               │     GGRRBBOO
                 │ 1 │               │       YY
             ┌───┼───┼───┬───┐       │       YY
             │ 3 │ 5 │ 4 │ 6 │───────┘
             └───┼───┼───┴───┘
                 │ 2 │
                 └───┘


Unfold←{
     Colours←3 2⍴'WYGBRO'

     MatchColour←⌷∘Colours(⍳∘1∘|,2÷⍨3++/)
     On←{(⍺)⌷[1]¨(⍵)⌷[⍺](⍺⍺×3-⍨2×⍵)}

     Fs←MatchColour¨∘⊃¨(⍵ On)/¨↓⍉1+3 2⊤(1-⍨⍳6)
     E←2 2⍴' '

     N←E(⊖⍉⊃Fs)E E(⌽3⊃Fs)(5⊃Fs)(4⊃Fs)(⌽6⊃Fs)E(⍉2⊃Fs)E E
     6 8⍴∊∊¨,/3 4⍴N
 }

                     ┌────────────┐
                     │'yFBx''R''L'│
                     └─────┬──────┘
                           ↓                 ┌────────────────────────────────────────┐
┌──────┐      ┌───┬───┬───┬───┬───┬───┐      │ rotate unit vectors & positional shift │ x18
│ Cube ├──────┤y 0│F 0│B 0│x 1│R 1│L 0│      └───────────────────┬────────────────────┘
└──────┘      └───┴───┴───┴───┴───┴───┘                          ↓
                                          ┌─────────────────────────────────────────────────┐
                     ←────────────────────┤  map char + bool to rotation & shift function   │
                              Fold left   └─────────────────────────────────────────────────┘


Twist←{
     SxMat←3 3⍴0 0 1 0 1 0 ¯1 0 0
     SyMat←3 3⍴1 0 0 0 0 1 0 ¯1 0
     SzMat←3 3⍴0 1 0 ¯1 0 0 0 0 1
     Id←3 3⍴1 0 0 0 1 0 0 0 1

     UShift←(1 0)(⌽⍤0 2)(2 2⍴2 1 1 2)(⍉⍤1 2)⊢
     URotate←((2 2⍴⊂SyMat),[0.5](2 2⍴⊂Id))(+.×)¨⊢
     U←UShift∘URotate

     Sx←(2 2 2⍴∘⍉(⊂3 1 4 2)⌷4 2⍴⊢)∘((SxMat∘(+.×))¨)
     Sy←(⌽∘(⍉⍤2))∘((SyMat∘(+.×))¨)
     Sz←(2 2 2⍴(⊂3 1 4 2)⌷4 2⍴⊢)∘((SzMat∘(+.×))¨)

     Map←{
         r←1+2×⍺⍺
         'F'=⍵:Sx Sx Sx(U⍣r)Sx ⍺
         'B'=⍵:Sx(U⍣r)Sx Sx Sx ⍺
         'z'=⍵:(Sz⍣r)⍺
         'U'=⍵:(U⍣r)⍺
         'D'=⍵:Sx Sx(U⍣r)Sx Sx ⍺
         'y'=⍵:(Sy⍣r)⍺
         'R'=⍵:Sz(U⍣r)Sz Sz Sz ⍺
         'L'=⍵:Sz Sz Sz(U⍣r)Sz ⍺
         'x'=⍵:(Sx⍣r)⍺
         ⍺
     }

     Parse←(⊃,''''∘∊)¨(⊢⊂⍨''''≠⊢)
     Foldl←{↑⍺⍺⍨/(⌽⍵),⊂⍺}
     ⍵{⍺((2⊃⍵)Map)(⊃⍵)}Foldl Parse ⍺
 }

┌──────────────────────┐ ┌──────────────────────┐
│ productivity         ├┬┤ concision            │
└──────────────────────┘│└──────────────────────┘
                        │┌──────────────────────┐
                        ├┤ "paper programming"  │
                        │└──────────────────────┘
                        │┌──────────────────────┐
                        └┤ disposability        │
                         └──────────────────────┘
┌──────────────────────┐ ┌──────────────────────┐
│ expressiveness       ├┬┤ composability        │
└──────────────────────┘│└──────────────────────┘
                        │┌──────────────────────┐
                        ├┤ great primitives     │
                        │└──────────────────────┘
                        │┌──────────────────────┐
                        └┤ symbolic             │
                         └──────────────────────┘
┌──────────────────────┐ ┌──────────────────────┐
│ maintainability      ├┬┤ repl-driven          │
└──────────────────────┘│└──────────────────────┘
                        │┌──────────────────────┐
                        └┤ transparency         │
                         └──────────────────────┘

┌──────────────────────┐ ┌──────────────────────┐
│ competition          ├─┤ awesome              │                             
└──────────────────────┘ └──────────────────────┘                             
┌──────────────────────┐ ┌──────────────────────┐                             
│ apl                  ├┬┤ i want to use it but │                             
└──────────────────────┘│└──────────────────────┘                             
                        │┌──────────────────────┐ ┌──────────────────────┐    
                        ├┤ libraries/tooling    ├┬┤ static analysis      │    
                        │└──────────────────────┘│└──────────────────────┘    
                        │                        │┌──────────────────────┐    
                        │                        ├┤ discoverability      │    
                        │                        │└──────────────────────┘    
                        │                        │┌──────────────────────┐    
                        │                        └┤ emacs mode :)        │    
                        │                         └──────────────────────┘    
                        │┌──────────────────────┐ ┌──────────────────────┐    
                        └┤ wider community      ├┬┤ learning             │    
                         └──────────────────────┘│└──────────────────────┘    
                                                 │┌──────────────────────┐    
                                                 ├┤ adoption             │    
                                                 │└──────────────────────┘    
                                                 │┌──────────────────────┐    
                                                 └┤ open source          │    
                                                  └──────────────────────┘

contents

01/13

background

02/13

E1.1 - Cooking on the Grille

03/13

E1.3 - When in Prison, Do as the Prisoners Do

04/13

E3.3 Watch Out for That Mine!

05/13

E2.1 Trapezoid Rule

06/13

E2.3 Romberg's Method

07/13

D3.1A Construction and Unfold

08/13

D3.1B Construction and Unfold

09/13

D3.2 Twist and Shout

10/13

good things

11/13

thoughts

12/13

summary

13/13