The APL Orchard

LdBeth

00:19

is there an efficient method to remove middle element of an array assuming it is always having odd numbers?

Paul Mansour

03:18

@LdBeth What is your non-efficient technique?

LdBeth

@PaulMansour I was trying to do something like b←3 3⍴1 1 1 1 0 1 1 1 1 ⋄ {⌈/,b×⍵}⌺3 3 on a larger 2D array

but instead of fixed 3 3 I'd like to have the window size to be parametric

Paul Mansour

Oh, I wrongly assumed you were starting with a vector... It's not clear to me how one removes an element from a rank 2 or greater array...

I've been putting off learning stencil, probably should look at it.

Oh, is it just the vector arg?

LdBeth

the ⍵ can be flatten by , so it could be just a vector of odd length with the center element removed

Paul Mansour

03:34

cmpx '{⍵/⍨~(⍳≢⍵)∊⌈2÷⍨≢⍵}a'  '{⍵[(⍳≢⍵)~⌈2÷⍨≢⍵]}a'
  {⍵/⍨~(⍳≢⍵)∊⌈2÷⍨≢⍵}a → 7.7E¯3 |    0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  {⍵[(⍳≢⍵)~⌈2÷⍨≢⍵]}a  → 1.8E¯2 | +137% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

Looks like compression works better than bracket indexing.

I can't imagine taking and dropping and catenating would be better.

You can use = of course, don't know why I used ∊

LdBeth

They are roughly the same efficiency on 18.2

 cmpx '{⍵/⍨~(⍳≢⍵)∊⌈2÷⍨≢⍵}a'  '{⍵[(⍳≢⍵)~⌈2÷⍨≢⍵]}a'
  {⍵/⍨~(⍳≢⍵)∊⌈2÷⍨≢⍵}a → 1.1E¯6 |  0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  {⍵[(⍳≢⍵)~⌈2÷⍨≢⍵]}a  → 1.1E¯6 | -1% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

Paul Mansour

Oh yes, I was 18.0! I had known work had been done optimizing compression, I guess that's on hold now.

LdBeth

Guess either one would work for me, thanks!

Paul Mansour

I'm not sure there are many other options?

LdBeth

{a⌽1↓⍵⌽⍨a←⌊2÷⍨≢⍵} could work but still slower

But the whole thing I was writing comes out not very useful: it is an image processing function that only fixes salt & pepper noise, that means replaces small pixels of pure white or pure black with nearby ones

rak1507

10:05

@Adám are there plans to change phase 2 to allow trains?

Adám

@rak1507 I'm pretty sure we used to have instructions on how to use tacit solutions. We're looking into adding those.

rak1507

10:31

@rak1507 update: the triple rank is now only a double rank :(

Razetime

11:24

@rak1507 saddest news of the year ;-;

rak1507

12:01

@Razetime made it ~60x faster though so not all bad

Adám

14:09

@rak1507 I've updated the Phase 2 intro to explain tacit usage.

RikedyP

@xpqz We've published your blog post

xpqz

@RikedyP Amazeballs. Thank you

rak1507

@Adám but why can't we submit foo←1+⊢?

Adám

@rak1507 Because we don't have the ability to do a syntax sanity check on that.

rak1507

@Adám Doesn't bother me personally idk about others but I think being able to submit trains > being told your dyadic dfn is indeed a dyadic dfn

Adám

14:23

Is it a huge bother to wrap it in {⍺(…)⍵} or {(…)⍵}?

rak1507

no, other than aesthetics

it seems easier to not check syntax though

also, if other things are included like comments or other helper definitions, will they go through too? I want to comment the solutions, but if they're fairly short, commenting inside the function breaks it up too much imo

Adám

Yeah, but in previous years, we've had people fail due to simple errors like bad naming or syntax.

@rak1507 Of course. We don't pick out things from your submission, we just analyse it as-is.

PyGamer0

who judges the competition?

rak1507

@Adám this is why I think the ideal competition is entirely objective... if the submissions returned an exact score, syntax errors would be impossible and you could submit whatever you wanted

maybe code quality etc could be a tiebreaker to retain that aspect

Kamila Szewczyk

isn't it how P1 works already

RikedyP

14:31

@rak1507 and what do you get points for?

Adám

@rak1507 That would require running the solutions immediately, as with phase 1, no?

rak1507

@Adám yes

@KamilaSzewczyk well, sort of

@RikedyP correct answers

RikedyP

We already rank based on correctness during the judging process, so it very quickly goes straight to the code quality tie breaker, as you described

since many people correctly solve many if not all of the problems

Adám

@rak1507 There are two objections to that. 1: We need a more capable sandboxing system than TryAPL's. 2: Some think that being able to make sure your submission is correct is part of the challenge (the superficial syntax checking was chosen as a middle ground between that camp and those that wanted phase 1 style checking).

dzaima

@rak1507 then you'd just have n% (where n is large) of submissions needing to be tiebreaker-ed, and (100-n)% of solutions with some very small mistake that have zero chance to win

RikedyP

14:35

@dzaima this is a good point, we are also able to be more lenient in small/obvious mistakes

rak1507

@dzaima 1. have more/harder problems 2. yes, but knowing you got it wrong there and then would make it easier to fix small problems

dzaima

also, it wouldn't anymore be an array language competition, but just a programming competition with a weird language requirement that for whatever reason has : before your usual control structures

rak1507

@RikedyP I made a small mistake last year and there wasn't any lenience (and that was after the tests said it was 'correct')

Adám

Presenting: @xpqz's blog post The 2021 APL Problem Solving Competition: Phase I – Best of Breed

4

Speaking of which, APL Quest is coming up in 20 mins.

dzaima

@rak1507 if you immediately showed the score, then, if the competitiong has a long time frame, everyone trying would eventually get 100% correct. If there's a small time frame, though, there's very little (or negative) incentive to make array-y solutions, again defeating the purpose of "APL" in "APL Problem Solving Competition"

rak1507

14:41

@dzaima that's assuming the problems are easy enough, it could be hard enough that no one actually gets 100%, especially if you take into consideration speed and things

RikedyP

@rak1507 but then it's no longer accessible to its target demographic

rak1507

@RikedyP it would still be accessible it would just also be hard? not every problem would have to be hard

Adám

And I don't think we'd have the resources for such a competition either.

dzaima

@rak1507 taking speed into consideration is another option, but that'd devolve into benchmarking dozens of different ways to write the same thing in Dyalog APL

@dzaima (at least if I got to participate)

Adám

And should it be allowed to ⎕NA into C?

rak1507

14:44

mon.stepik.org/2021 this was a competition a couple of people here did, and look, no one got 100%

Adám

But only runs for 24 hours.

xpqz

@dzaima Are you not taking part this year?

rak1507

@dzaima as long as it was fast enough to pass, using time as a tiebreaker is probably bad for that reason

@Adám true, but even if it ran for longer there's no guarantees lots/any people would get 100%

dzaima

@rak1507 then you run into the issue of some nice solution not passing because it needs to manually implement a non-O(n^2) scan

rak1507

@dzaima slow solutions aren't nice imo

dzaima

14:46

not having an O(n) scan isn't nice

rak1507

I agree

dzaima

@rak1507 (where can i find info about how that was scored :|)

xpqz

I think the Dyalog comp is a good compromise -- not as stressy as AoC

It's nice to have the time to try to do a good job, rather than just mad-hacking it

rak1507

@xpqz I find it quite stressful not knowing if my solution will please the overlords or not

@xpqz yes but 'good job' is subjective and I have no guarantees that what I think is a good job will be universal

xpqz

I think you're probably ok there :)

rak1507

14:50

I agree that a longer contest is good

I just don't agree that it can't be mostly objective

dzaima

@rak1507 I think that Dyalog's "good job" metric is probably still a better metric of solution array-iness than any objective metric for array-iness one can think of though

xpqz

Not that different to any run of the mill code review, right.

rak1507

@xpqz well no, could be one of the phase 1s 'passed' and missed a crucial test case, or I didn't comment enough, or that I didn't include testing in with my solutions (what? who would do that?)...

Razetime

@rak1507 this one was brutal

xpqz

Which number are we on for Quest?

rak1507

14:54

@dzaima maybe, idk, they don't publish solutions

Razetime

according to the wiki, today is 11

whoops 8

dzaima

@dzaima dyalog could run a completely different contest about solution speed or programming speed or algorithm design or some combination of those, but I do not think that'll ever come close to measuring actual array-iness

Razetime

8th one

Richard

problems.tryapl.org/psets/…

xpqz

I have a great solution! Just like all of yours!

Richard

14:56

:)

Adám

I have some fun ideas, that hopefully will make today's Quest less boring.

Richard

I like the competition btw a lot. I am trying to reach the end of phase 1

Most difficult are the edge cases all the time

input ⍬ etc.

Sometimes you can catch them by using a conditional statement but nicer is to include it in the solution itself

Adám

@rak1507 Agreed. And because this happened to you last year, we've added lots of peer review to the test cases this year.

@Richard A good array-oriented solution will often "just work" on edge conditions.

LdBeth

My experience is if there's a problem in edge case in phase1, it is high chance there exists a better method

Richard

yes exactly. So still trying...

Adám

15:00

Welcome to the APL Quest! This week's quest is Go Forth And Multiply:

> Write a dfn which produces a multiplication table.

Razetime

{≢∘,¨∘.(∘.∨)⍨(/∘1)¨⍳⍵}

xpqz

∘.×⍨⍳

PyGamer0

∘.×⍨⍳

shoot ninja'd

xpqz

:D

PyGamer0

was not prepared for this one

Adám

15:01

@Razetime That's… unusual.

xpqz

@Razetime what have you done...

Adám

OK, so with the basic solution out of the way, let's have some fun:

Write it without outer product!

Kamila Szewczyk

{×/¨⍳⍵ ⍵}

Adám

Good. How about using Rank?

rabbitgrowth

×⍤0 1⍨⍳

Adám

15:02

Nice.

OK, now write it using only functions, and no operators whatsoever. (You may want to use a dfn instead of a tacit function.)

Kamila Szewczyk

i think i have an idea

Adám

It can be written as a tacit function too, though. Bonus points?

PyGamer0

I want to see a J solution ...

Adám

To the basic problem or "without operators"?

Razetime

{⍵ ⍵⍴(⍵/⍳⍵)×(⍵×⍵)⍴⍳⍵}

xpqz

15:05

{{⍵×⍉⍵}⍵ ⍵ ⍴⍳⍵}

Adám

Whoa. Both of those count, but I have a much simpler solution in mind.

rabbitgrowth

{↑(⍳⍵)×⊂⍳⍵}

Adám

Nice! That's what I had in mind.

Razetime

ah that makes more sense to tacitify

↑⍳×⊂∘⍳

Adám

> ∘

Kamila Szewczyk

15:06

no operators

PyGamer0

@Adám basic problem...

Razetime

↑⍳×(⊂⍳)

Adám

@PyGamer0 i.*/i. or */~@i. I think.

PyGamer0

k solution to the basic problem: {(!x)*/:!x}

and bqn: ×⌜˜↕

Adám

@Razetime Or (↑⊂×⊢)⍳ etc. which avoids recalculating ⍳

Razetime

15:09

yep, better

always replace × with ∧×∨

Adám

How about a solution that uses no arithmetic functions at all? (⍳ and operators are allowed)

PyGamer0

huh ...

Razetime

I mean, i can change {≢∘,¨∘.(∘.∨)⍨(/∘1)¨⍳⍵} to not use arithmetic ops

Adám

Yes, my solution is kind of like that, but simpler. 11 chars.

I actually have two different 11-char approaches.

Down to 10.

OK, I've got another 10.

Any bids before I begin to reveal mine?

Razetime

{≢¨,∘⍳¨⍳⍵ ⍵}

is a 12

PyGamer0

15:17

@Adám i read that as kids lmao

Adám

@Razetime That's one of mine too: ≢⍤,⍤⍳¨⍳⍤,⍨

Razetime

cute

Richard

Trying something with the power operator but not working yet

Bojan Petrović

@Adám maybe increase by one since J is zero based: */~ @: >: @ i.

Adám

Here's a simple one: ∘.{≢⍺/⍵/#}⍨⍳

LdBeth

15:21

What is #?

Richard

what is the '#' doing?

dzaima

@Adám similar one - ∘.(≢⍸⍤/)⍨⍳

Adám

# is a scalar reference to the root namespace.

I just used it to avoid a number, and save quotes for a char.

@dzaima Nice!

dzaima

≢⍤⍸¨⍳∘./⍳

Adám

Outer replication. Noice. And shortest too (9).

@Richard I found one. Want me to reveal?

Richard

15:27

@Adám yes ok, keep getting errors

Adám

∘.{≢#,⍣⍺⍣⍵⊢⍬}⍨⍳

dzaima

I wonder if an O(n^2) solution without arithmetic is possible

Adám

It appends # to ⍬, ⍺ times, ⍵ times.

@dzaima Uh, do you have a O(<n²) solution at all?

dzaima

@Adám I mean that the current no-arithmetic ones are all O(n^4). ∘.×⍨⍳ is O(n^2) but that of course uses arithmetic

Adám

Oh, I see what you mean.

@dzaima What is the complexity of ×?

dzaima

15:32

(an O(n^3) one - {↑⍵{v←⍬ ⋄ d←⍳⍵ ⋄ {v,←d⋄≢v}¨⍳⍺}¨⍳⍵})

@Adám doesn't matter as it's arithmetic :)

Adám

Sure, but I wonder if × isn't secretly implemented as O(n²) itself, meaning that ∘.×⍨⍳ is O(n⁴).

Richard

which one is fastest? The one without multiplications?

dzaima

well, for IEEE754 64-bit floats × is O(1). Arbitrary precision multiplication is O(n log n) as of recently

Adám

@Richard I've very sure ∘.×⍨⍳ is fastest.

@dzaima Only on galactic scale.

dzaima

of course.

Bojan Petrović

15:38

Here's one with a scan: {↑+\↓⍵ ⍵ ⍴⍳⍵}

Adám

Oh wow.

Can also be written as {↑+\↓⍵⍴⊂⍳⍵}

Or {+⍀⍵ ⍵⍴⍳⍵}

Tacit: +⍀,⍨⍴⍳

That's actually pretty cool.

Bojan Petrović

Thanks! +⍀ is what I was looking for.

Adám

Two +⍀s instead of ⍳: +⍀,⍨⍴+⍀⍤⍴∘1

Richard

@BojanPetrović nice

Adám

Another fun one of that family: +⍀,⍨+\⍤⍴≢

OK, I think we've exhausted this problem. Who would have thought we'd be able to spend 45 minutes on this problem‽

See you next week for It Is a Moving Experience.

Richard

15:46

thanks!

PyGamer0

after asking for help in the k tree, here it is golfed: */:/&=:

rabbitgrowth

Another one without arithmetic just for fun: {{≢,⍵⍴#}¨⍳⍵ ⍵}

Adám

@rabbitgrowth Sure, but:

{{≢,⍵⍴#}¨⍳⍵ ⍵}
{{≢,⍳⍵}¨⍳⍵ ⍵}
{≢⍤,⍤⍳¨⍳⍵ ⍵}
{≢⍤,⍤⍳¨⍳,⍨⍵}
≢⍤,⍤⍳¨⍳⍤,⍨

rabbitgrowth

Oh wow.

xpqz

17:50

@PyGamer0 You may or may not be interested in github.com/xpqz/dyalogk/blob/main/phase1.k

Brian BED

18:16

does ⍴⍣¯1 dyadically work in any cases?

LdBeth

20:41

@BrianBED I don't think there is such a function

apparently, a function needs to be bijective to have an inverse

Brian BED

what does bijective mean?

Brian BED

21:36

bijective

ah i see what you mean. i don't think ⍸ is bijective but it does also work. it picks the smallest size for an array when reversed

Transcript for