2022 APL Problem Solving Competition Discussion

Update from Jeremy: I’ve made this a wiki post so please put links to useful resources for the competition here


Hello All!

So the 2022 APL Problem Solving Competition has come to a close. I learned so much attempting these problems and struggling to think with arrays. If you also participated I think it would be fun to share your solutions so we can learn from each other. Here is what I ended up with for Phase 1:

Some solutions came out nice, others got messy. I did not attempt Phase 2.

I would love to discuss and hear about your experience.

Lets talk APL!
:slight_smile:


APL Problem Solving Competition 2022 (questions with test cases in pdf):

Useful Resources:

  • All Phase I solutions shared so far are consolidated in this Repo. Please feel free to add your solution to benchmark the performance.
  • Adam’s previous competition walk-thru (APL Quest - APL Wiki)
  • Transform tacit APL into dfn form using tacit.help
4 Likes

here are mine: mostly aimed for shortness despite it not being a code golf competition (old habits die hard…)

4 Likes

Would be great if you gents broke down some of these expression (dissect -ed them?) to explain what it’s doing.

1 Like

If you have any particular questions I’d be happy to explain - if you want to give it a go yourself https://tacit.help/ could be useful

2 Likes

My solutions here: GitHub - xpqz/dyalog2022

4 Likes

Here is my submission. :trophy: I am so glad I managed to complete them all with gold tropies although the solutions are sub-optiumal. :sweat_smile:

I am keen to learn from @eitanlees and @rak1507. I consolidated their solutions, transformed into Dfn and added execution time for each solution. Here is the repo.

I am planning to " dissect their solutions into a group of glyph that can be run.

@mike.moloch would you like to help?

3 Likes

Let’s see your evil Ballot solution!

@eitanlees for some reason, I can’t run your solution #7. Any idea? Can you copy and paste your solution there?
image

Does Dfn take longer to execute than Tacit?

I also added @xpqz solutions in my repo. If anyone participated in the competition, please feel free to add your solutions there and benchmark the execution time. It feels like a mini-Kaggle competition. :star_struck:
image

1 Like
2 Likes

Thanks for @eitanlees spotting my typo. Fixed now.

image

R and D are ~identical, just that R has some tacit pixie dust on it.

Phase 1 Review

Sorry I was busy this weekend and didn’t get a chance to respond.

I am excited to see how others approached the problems. Thank you @Moody for compiling the problems.

Here is some commentary on my solutions.

1: Counting DNA Nucleotides

fn ← +/'ACGT'∘.=,

This was an eye-opening experience for me. Using the outer product to build a relationship table

dna ← 'AGCTTTTCATTCTGAC'
'ACGT' ∘.= dna

1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0
0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1
0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 1 1 1 1 0 0 1 1 0 1 0 0 0

and then summing

+/ 'ACGT' ∘.= dna
3 4 2 7

was a perfect example of β€œThinking with Arrays”. The , was to catch an edge case.

2: Attack of the Mutations!

fn ← +/β‰ 

This solution creates a boolean mask where the arrays are not equal and then sums. Pretty straightforward.

3: Uniquely Qualified

fn ← (~,~⍨)β₯,

From what I understood this question is asking for the β€œExclusive Or” of the arguments.


The Without function A ~ B provided the elements of A without the elements of B. For the solution, I would need to reverse B ~ A as well. The Commute operator ⍨ flips the arguments. Finally, I join the lists together with β₯,. I am not so comfortable with the use of the Over operator β₯ but it worked!

4: In the Long One…

fn ← ⌈/0,β‰’Β¨β€βŠ†β¨βˆ˜,

My approach here came from experimenting with applying the partition function to a binary array.

b ← 1 1 1 0 1 1 0 0 1 1 1 1 0
(βŠ†β¨) b
β”Œβ”€β”€β”€β”€β”€β”¬β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”
β”‚1 1 1β”‚1 1β”‚1 1 1 1β”‚
β””β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”˜

Now I wanted to count each box

(β‰’Β¨β€βŠ†β¨) b
3 2 4

and then take the maximum

(⌈/β‰’Β¨β€βŠ†β¨) b
4

5: Stairway to Heaven (with apologies to Led Zeppelin)

fn ← βŒ½βˆ˜β†‘β΄βˆ˜'βŽ•'¨∘⍳

My approach here was to generate a sequence of boxes from 1 to n, and then reshape it to look correct.

(⍴∘'βŽ•'¨∘⍳) 5
β”Œβ”€β”¬β”€β”€β”¬β”€β”€β”€β”¬β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”
β”‚βŽ•β”‚βŽ•βŽ•β”‚βŽ•βŽ•βŽ•β”‚βŽ•βŽ•βŽ•βŽ•β”‚βŽ•βŽ•βŽ•βŽ•βŽ•β”‚
β””β”€β”΄β”€β”€β”΄β”€β”€β”€β”΄β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”˜

Here ⍴∘'βŽ•' is applied to each number from iota ⍳. The last bit opens the boxed array and rotates it.

(βŒ½βˆ˜β†‘β΄βˆ˜'βŽ•'¨∘⍳) 5
    βŽ•
   βŽ•βŽ•
  βŽ•βŽ•βŽ•
 βŽ•βŽ•βŽ•βŽ•
βŽ•βŽ•βŽ•βŽ•βŽ•

6: Pyramid Scheme

fnβ†βŒŠβˆ˜βŒ½βˆ˜βŠ–β¨(∘.⌊⍨∘⍳0⌈¯1+Γ—βˆ˜2)

My thought process here was to generate a matrix, flip it around and then take the minimum. The phrase 0⌈¯1+Γ—βˆ˜2 came from the question and calculates the appropriate size for the matrix. Next up was to generate a matrix. I decided to use the outer product with a minimum ⌊ as the function to be applied.

(∘.⌊⍨∘⍳0⌈¯1+Γ—βˆ˜2) 3
1 1 1 1 1
1 2 2 2 2
1 2 3 3 3
1 2 3 4 4
1 2 3 4 5

Then rotate it

βŒ½βˆ˜βŠ–(∘.⌊⍨∘⍳0⌈¯1+Γ—βˆ˜2) 3
5 4 3 2 1
4 4 3 2 1
3 3 3 2 1
2 2 2 2 1
1 1 1 1 1

Finally, take the minimum of these two matrices

(βŒŠβˆ˜βŒ½βˆ˜βŠ–β¨(∘.⌊⍨∘⍳0⌈¯1+Γ—βˆ˜2)) 3
1 1 1 1 1
1 2 2 2 1
1 2 3 2 1
1 2 2 2 1
1 1 1 1 1

7: Just Golfing Around

fn ← (βŠƒ,/)((β‰’βŠ’β€/+βŒΏΓ·β‰’)¨⍳⍨β₯,βŠ†β³βˆ˜β‰’)

This problem caused me a lot of difficulties. My initial approach was to do a similar technique to problem 4 where I use the partition function.

t ← 68 71 71 73

βŠ†β¨ t
β”Œβ”€β”€β”¬β”€β”€β”€β”€β”€β”¬β”€β”€β”
β”‚68β”‚71 71β”‚73β”‚
β””β”€β”€β”΄β”€β”€β”€β”€β”€β”΄β”€β”€β”˜

but the issue here is I need to group the places not the value of the score. Luckily the function argument is always sorted so we can use iota ⍳ to generate a list of places

(⍳≒) t
1 2 3 4

and I will also use the dyadic for of iota which gives me the index of the first occurrence of each score

⍳⍨ t
1 2 2 4

These two functions are joined by a partition βŠ† to form the separate rankings

(β³β¨βŠ†β³βˆ˜β‰’) t
β”Œβ”€β”¬β”€β”€β”€β”¬β”€β”
β”‚1β”‚2 3β”‚4β”‚
β””β”€β”΄β”€β”€β”€β”΄β”€β”˜

Next, I wanted to find the average of each box.

((+βŒΏΓ·β‰’)Β¨β³β¨βŠ†β³βˆ˜β‰’) t
1 2.5 4

but the problem was I needed to replicate the average for tied places. The replicate function / was used along with β‰’.

((β‰’βŠ’β€/+βŒΏΓ·β‰’)¨⍳⍨β₯,βŠ†β³βˆ˜β‰’) t
β”Œβ”€β”¬β”€β”€β”€β”€β”€β”€β”€β”¬β”€β”
β”‚1β”‚2.5 2.5β”‚4β”‚
β””β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”˜

It turns out the slash symbol is tricky because sometimes it can be a function and other times it can be an operator. In this case, I appended a right tack to the slash to force it to be a function rather than an operator.

All that is left is to concatenate the values and unbox the result

(βŠƒ,/)((β‰’βŠ’β€/+βŒΏΓ·β‰’)¨⍳⍨β₯,βŠ†β³βˆ˜β‰’) t
1 2.5 2.5 4

8: Let’s Split!

fn ← {n←⍺(-∘1(⌊/⊣⍳⍨(⍬∘,⊒)))⍡⋄(n↑⍡)(n↓⍡)}

For this problem, we were asked to split a list based on the first occurrence of an element from the left array in the right array.

My first task was to find the location where to split the array. For this, the dyadic ⍳ was very useful.

(⌊/ 'do' ⍳⍨ 'Hello World')-1
4

Then it was just a matter of taking and dropping the same amount

(4 ↑ 'Hello World')(4 ↓ 'Hello World')
β”Œβ”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”
β”‚Hellβ”‚o Worldβ”‚
β””β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”˜

The rest of the solution was catching edge cases, and train building.

9: An Average Window (or a Windowed Average)

fn ← {n←(1+2×⍺)β‹„n÷⍨n+/(⍺/1↑⍡),⍡,(⍺/Β―1↑⍡)}

For this problem, I wanted to construct an array with the appropriate padding and then perform the windowed average.

I would need ⍺ extra copies on each end of my array to accommodate a window size of 1+2×⍺.

2 { (⍺/1↑⍡),⍡,(⍺/Β―1↑⍡) } ⍳6
1 1 1 2 3 4 5 6 6 6

With such an array constructed, the windowed sum was performed and divided by the window size to calculate the average

2 fn ⍳ 6
1.6 2.2 3 4 4.8 5.4

10: Separation Anxiety

fn ← {↑,/ ⍺ {⍺} @ {0=6|βŒ½β³β‰’β΅}1↓(2 βŠ‚ ⍡)}

My approach here was to split up the input by using a partition enclose. The left argument of the dyadic form represents the number of dividers to place between each element.

{1↓(2 βŠ‚ ⍡) }'10000000'
β”Œβ”€β”¬β”¬β”€β”¬β”¬β”€β”¬β”¬β”€β”¬β”¬β”€β”¬β”¬β”€β”¬β”¬β”€β”¬β”¬β”€β”
β”‚1β”‚β”‚0β”‚β”‚0β”‚β”‚0β”‚β”‚0β”‚β”‚0β”‚β”‚0β”‚β”‚0β”‚
β””β”€β”΄β”΄β”€β”΄β”΄β”€β”΄β”΄β”€β”΄β”΄β”€β”΄β”΄β”€β”΄β”΄β”€β”΄β”΄β”€β”˜

With this setup, now we need a function to insert our separators where they belong. We want our separator to be placed at every 6th position, starting from the right, so I reversed an iota and performed a modulo.

{0=6|βŒ½β³β‰’β΅} {1↓(2 βŠ‚ ⍡)} '100000000'
0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0

With a boolean mask established all we need to pass to the @ operator is the separator and join the result

',' {↑,/ ⍺ {⍺} @ {0=6|βŒ½β³β‰’β΅}1↓(2 βŠ‚ ⍡)} '100000000'
100,000,000
4 Likes

Very nicely done.

I am interested in how to approach problems. rak1507 and xpqz have different take-on. Note: I converted tacit forms to Dfn, if any, for my understanding.

6: Pyramid Scheme

image

⍳,1β†“βŒ½βˆ˜β³ is a tacit form of {(⍳⍡),1↓(⌽(⍳⍡))}.
image

Question: It seems tacit form needs to be assigned with a function name. Without it, the output is different. Can anyone explain this? :thinking:
image

Adding curly brackets for the tacit form will cause a syntax error.
image

7: Just Golfing around

8: Let’s Split!

image

9: An Average Window

10: Separation Anxiety

Thank you for those sharing their solutions here. Well done! :clap: :clap:

You can execute trains β€˜anonymously’ by enclosing the phrase in parentheses:

      (⍳,1β†“βŒ½βˆ˜β³) 3
β”Œβ†’β”€β”€β”€β”€β”€β”€β”€β”€β”
β”‚1 2 3 2 1β”‚
β””~β”€β”€β”€β”€β”€β”€β”€β”€β”˜
1 Like

If not isolation (by assignment or parenthesis), the phrase just forms a normal (β€œexplicit”) APL expression.

1 Like

I have been studying other solutions and I wanted to share a few I found interesting

4 In the Long One

@rak1507 and @xpqz came up with the same approach.

Here we are asked to find the longest run of 1’s

t ← 1 1 1 0 1 1 0 0 1 1 1 1 0

The self partition groups the ones

βŠ†β¨ t
β”Œβ”€β”€β”€β”€β”€β”¬β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”
β”‚1 1 1β”‚1 1β”‚1 1 1 1β”‚
β””β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”˜

but the solution takes an interesting turn

β†‘βŠ†β¨ t
1 1 1 0
1 1 0 0
1 1 1 1

I had used the dyadic up arrow for β€œTake” but had not considered the monadic case. From the documentation:

Monadic Up Arrow means β€œMix”

Mix will stack elements of an array, and pad values to make the result rectangular.

After that it’s just a matter of figuring out how many columns the matrix has. Transpose and Tally do just that.

β‰’β‰β†‘βŠ†β¨ t
4

6 Pyramid

I thought @rak1507 's solution was nice. I had also thought to use the minimum outer product but the question then is β€œwhat array to use as input?”

He constructed the following vector by combining ⍳ and the reversed list with the first element dropped.

(⍳,1β†“βŒ½βˆ˜β³) 3
1 2 3 2 1

essentially mirroring the array. Feeding this into the minimum outer product gives the result

(∘.⌊⍨ ⍳,1β†“βŒ½βˆ˜β³) 3
1 1 1 1 1
1 2 2 2 1
1 2 3 2 1
1 2 2 2 1
1 1 1 1 1

Very clever!

7 In Place - just golfing around

Once again I found @rak1507 's solution was excellent. The approach exploited the fact that the input is a non-decreasing vector.

For tied scores, we want to calculate the average of the places. This can be done by taking the average of the first and last place in each group.

    |<------>|
 1  2  3  4  5  6 ⍝ Places
67 71 71 71 71 73 ⍝ Scores
 1   (2+5)÷2    6 ⍝ Average
 1      3.5     6 

The first position of each group can be found using ⍳

⍳⍨ 68 71 71 71 71 73
1 2 2 2 2 6

Since the input is ordered when ⍸ applied to itself what is returned is the index of the final element in the group

⍸⍨ 68 71 71 71 71 73
1 5 5 5 5 6

The solution is the average of the two vectors.

( (⍳+⍸) ⍨ 68 71 71 71 71 73 ) ÷ 2
1 3.5 3.5 3.5 3.5 6

or rearranged

(2÷⍨⍳+⍸)⍨ 68 71 71 71 71 73
1 3.5 3.5 3.5 3.5 6

I found the use of ⍳ and ⍸ really interesting. Well done!

5 Likes

Thank you @eitanlees , I’m really enjoying your commentary! :smiley:

1 Like

Late to the party because I’ve been away on holiday. I’m just catching up on the videos from session 12 onwards.

Here are my phase 1 solutions. Nothing spectacular but it was fun to give it a go.

4 Likes