# 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.

Lets talk APL!

## 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. I am so glad I managed to complete them all with gold tropies although the solutions are sub-optiumal.

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?

4 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?

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.

1 Like
2 Likes

Thanks for @eitanlees spotting my typo. Fixed now.

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
``````
5 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

`β³,1ββ½ββ³` is a tacit form of `{(β³β΅),1β(β½(β³β΅))}`.

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

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

## 10: Separation Anxiety

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

1 Like

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.

2 Likes

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
``````

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!

6 Likes

Thank you @eitanlees , Iβm really enjoying your commentary!

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.

Edit: notebook exploring some of the solutions

4 Likes

The winners have been announced. Congratulations!

2022 APL Problem Solving Competition Winners

3 Likes