The APL Orchard - 2022-07-08

« first day (1990 days earlier) ← previous day next day → last day (665 days later) »

Stack Exchange Feeds

1:38 PM

0

Q: Alexa Redirects to home page

We have implemented APL in our skill which is a static list of item. While APL was showing in echo show device is automatically redirected to home page of echo show while alexa was speaking. Skill works fine. when we try to speak again the APL comes back to the screen. Its was not happening every...

alexa-skills-kit alexa-voice-service apl

1 hour later…

2:47 PM

Here’s what I came up with for 2015/day3: {(⊢⌷⍨∘⊂∘⍋÷/¨)(⊂0 1),⊃,⌿(↓⊢(,⍨⍤0)1,⍸⍤(⍳{×⍺|⍵}⊢))¨⍳⍵}

Can surely be cleaned up but this is fresh off the presses.

@doug You're starting early!

I’m heading off to bed. :) I’m based in Asia.

Welcome to APL Quest 2015-3! Today's quest is Farey Tale:

> Write a function that takes an integer right argument and returns a vector of the terms in the Farey sequence of that order.

{⍵=0:(,⊂0 1) ⋄ (⊂⍵ ⍵),⍨(⊂0 1),{⍵[⍋÷/↑⍵]}{1↓∪,(1=⍵∘.∨⍵)×(⍵∘.<⍵)×∘.,⍨⍵}⍳⍵}

Essentially, this means the fractions (as 2-element vectors) between 0 and 1, with no part of the fraction exceeding the given number.

3:01 PM

{f[k][⍋d[k←(⍸d≤1)∩{⊃⍵}⌸d←÷/¨f←,(⊂0 1),,⍳⍵ ⍵]]}

⎕IO←0: {{⍵[⍋÷/¨⍵]}⍸∘.(1=∨∧≤)⍨⍳1+⍵}

Fails on 0

I've got {(,÷∨)∘1¨{⍵[⍋⍵]}0,∪1⌊,∘.÷⍨⍳⍵}

This is going to be a fun episode :)

Yeah, now we have a few solutions, let's see if we can understand what's going on.

My solution just brute force generates all combinations, then filters.

Looks like @xpqz is doing something clever. Can you explain?

Also, mine (and @rabbitgrowth's?) relies on floating point accuracy. Not ideal.

Oh, so does @Richard's

I'm not sure I can... too long ago... but I believe it's the wikipedia "smart" solution

3:05 PM

@xpqz ⍳⍵ ⍵ is better than my solution to create the matrix

As someone who's not very well versed in maths, I really enjoyed reading the explanation for the smart solution on Wikipedia

I don't understand the ⌸ part however

It's basically just unique-ing

That's getting the index of the first occurrence of each unique element.

Isn't that the same as ⍸≠?

Seems so.

Ah nice

Probably faster, too

3:10 PM

than they all use the same method more or less, isn't it? Only some a little bit more efficient and compact

Yeah

user image

And I could probably have skipped one outer product.

^^ should compute the next pair p q in terms of the previous two pairs a b and c d.

a b and c d are a÷b and c÷d?

3:14 PM

Yes.

But then you still need to calculate the first two pairs

They will always be (0 1)(1 n)

:)

and repeating that n-2 times?

Something like that.

Someone tell me my mistake here:

      n←5 ⋄ {(a b)(c d)←¯2↑⍵ ⋄ ⍵,⊂(⌊d÷⍨n+b)×(c-a)(d-b)}⍣2⊢(0 1) (1 n)
┌───┬───┬───┬────┐
│0 1│1 5│1 4│0 ¯2│
└───┴───┴───┴────┘

Behind ⍣ (n-2)?

3:19 PM

Yeah, well the dfn should be a literal translation of the above formulas.

Indeed, it correctly computes the next pair as 1 4

it should calculate 11 pairs. What is the end condition for the loop?

What loop?

Looks like you're calculating k(c-a) and k(d-b) instead of kc-a and kd-b?

Oh, I'm reading it like APL 🤦🏿🤦‍♂️

@Adám Maybe I misunderstood, but ⍣ is calculating two pairs, but there should be 11

3:23 PM

Yes, but I detected an issue at pair number 4.

⋄ n←5 ⋄ {(a b)(c d)←¯2↑⍵ ⋄ ⍵,⊂a b-⍨c d×⌊d÷⍨n+b}⍣9⊢(0 1)(1 n)

@Adám
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│0 1│1 5│1 4│1 3│2 5│1 2│3 5│2 3│3 4│4 5│1 1│
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘

Nice

That will be the fastest

nice, and add (⊂0 1)

Nah, was a typo.

How do we know the length of the sequence in terms of n?

But why 9?

exactly

3:25 PM

Because we start with 2 and need 11.

yes, but that's cheeting ;)

can't we have an ending condition with the ⍣ operator?

what is pair number 12 if you generate it?

{1 1≡⊃⊢/⍺}?

Hm: 2 3 5 7 11 13 19…

@Richard 6 5

@rabbitgrowth yes, better than calculating primes

Why not 17?

3:28 PM

A lot of info here: nature.com/articles/s41598-021-99545-w

So I've got {⍵{(a b)(c d)←¯2↑⍵ ⋄ ⍵,⊂a b-⍨c d×⌊d÷⍨⍺+b}⍣{=/⊃⌽⍺}(0 1)(1⍵)} — time to clean up.

Ah, {=/⊃⌽⍺} is a lot nicer :)

We need to handle 0 and 1 too.

Can it be done better than {(1+⍵)↑⍵{(a b)(c d)←¯2↑⍵ ⋄ ⍵,⊂a b-⍨c d×⌊d÷⍨⍺+b}⍣{≥/⊃⌽⍺}(0 1)(⌈\1⍵)}?

Also, I'm thinking of accumulating a matrix instead of a vector of pairs.

That's incorrect

I think

It is indeed.

{⍵{(a b)(c d)←¯2↑⍵ ⋄ ⍵,⊂a b-⍨c d×⌊d÷⍨⍺+b}⍣{≥/⊃⌽⍺}⍣(1<⍵)⊢(0 1)(1 ⍵)↑⍨2⌊1+⍵}

then?

I still have a feeling it is possible to generate (0 1)(1 ⍵) in a neat way, like a scan.

3:38 PM

it works at least

⍵(⊢,⍥⊂*)0 1 ;-)

0 ⍵∘.*0 1

I'm still not sure I understand why F0 should be (0 1) ⍨

How else would you write 0 as a fraction?

The enumerator surely has to be 0, and the denominator has to be the smallest possible integer.

This surprises me (as always):

      A←{⍵{(a b)(c d)←¯2↑⍵ ⋄ ⍵,⊂a b-⍨c d×⌊d÷⍨⍺+b}⍣{≥/⊃⌽⍺}⍣(1<⍵)⊢(0 1)(1 ⍵)↑⍨2⌊1+⍵}
      X←{f[k][⍋d[k←(⍸d≤1)∩⍸≠d←÷/¨f←,(⊂0 1),,⍳⍵ ⍵]]}
      cmpx 'A 100' 'X 100'
  A 100 → 6.0E¯2 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  X 100 → 1.2E¯2 | -80% ⎕⎕⎕⎕⎕⎕⎕⎕

I am curious about the speed. The last solution seems slower for large numbers like 300

3:42 PM

Looping is slow?

Brute force and vectors wins again.

How about very large numbers? X is O(n²)

Whereas A is O(n)

Mine happily does 1000. A doesn't

Wonder if it will compile.

compile?

3:44 PM

Yeah, it does compile.

@Adám it's O(result length), but the result length seems quadratic in terms on n

Oh, right.

You could make the loop much faster by using actual recursion and an outside accumulaor

Passing the lengthening list between loop iterations is probably choking it

      cmpx 'A 100' 'Ac 100' 'X 100'
  A 100  → 4.7E¯2 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  Ac 100 → 4.2E¯2 | -11% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  X 100  → 8.5E¯3 | -82% ⎕⎕⎕⎕⎕⎕⎕

Compilation helped a little, but not much.

What do you mean with compilation?

3:47 PM

Dyalog can compile to native

Dyalog has a built-in compiler.

ah, ok making executable?

It is kind of fun to see the compiled byte code, but I don't understand anything.

   )t {𝕊x0: {⟨a‿b⋄c‿d⟩←¯2↑𝕩 ⋄ 𝕩∾<a‿b-˜c‿d×⌊d÷˜x0+b}•_while_{<´¯1⊑𝕩}⍟(1<𝕩) ⟨0‿1⋄1‿𝕩⟩↑˜2⌊1+𝕩}1000 # CBQN on the input of 1000
105.5ms

@Adám But then why not include 1/1 too? The problem states that each sequence starts with 0/1 and ends with 1/1.

3:50 PM

? We do include 1/1

I mean, for the 0 case

Whoa:

      Am←{⍵{(a b c d)←,¯2↑⍵ ⋄ ⍵⍪a b-⍨c d×⌊d÷⍨⍺+b}⍣{≥/⊢⌿⍺}⍣(1<⍵)↑(0 1)(1 ⍵)↑⍨2⌊1+⍵}
      cmpx'A 100' '↓Am 100'
  A 100   → 4.6E¯2 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  ↓Am 100 → 7.5E¯3 | -84% ⎕⎕⎕⎕⎕⎕

Flat arrays FTW.

      cmpx'X 100' '↓Am 100'
  X 100   → 8.6E¯3 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  ↓Am 100 → 7.6E¯3 | -12% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

@Adám try 1000

Already processing… Doom:

      cmpx'X 1000' '↓Am 1000'
  X 1000   → 1.2E0  |     0% ⎕⎕⎕
  ↓Am 1000 → 1.6E1  | +1182% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

@dzaima so dyalog taking ±forever on 1000 is weird; CBQN is faster but not like 100x faster

3:53 PM

How fast is CBQN using the flat version?

if anything, I'd expect it to be slower :)

And including 0/1 for the 0 case seems contradictory to the requirement that each of the denominators should be less than or equal to n.

@dzaima oh I don't think I have amortized O(1) append to a non-vector, so, yes, 0.1s → 19s :P

Sorry, I don't understand it anymore. What is the second ⍣ doing? And what do you mean with flat.

@rabbitgrowth Agreed, the 0 case is odd. Wikipedia doesn't list it either.

@Richard One is for the stop condition, and one is a conditional computation, to prevent executing on 0 or 1.

@Richard Flat: Compare A and Am:

A ←{⍵{(a b)(c d)← ¯2↑⍵ ⋄ ⍵,⊂a b-⍨c d×⌊d÷⍨⍺+b}⍣{≥/⊃⌽⍺}⍣(1<⍵)⊢(0 1)(1 ⍵)↑⍨2⌊1+⍵}
Am←{⍵{(a b  c d)←,¯2↑⍵ ⋄ ⍵⍪ a b-⍨c d×⌊d÷⍨⍺+b}⍣{≥/⊢⌿⍺}⍣(1<⍵)↑(0 1)(1 ⍵)↑⍨2⌊1+⍵}

@xpqz Is my golfed version consistently faster than yours?

3:59 PM

The ⍸≠ bit? I didn't measure.

@dzaima pfft who needs high rank -

{𝕊x0: ∘‿2⥊{a‿b‿c‿d←¯4↑𝕩 ⋄ 𝕩∾a‿b-˜c‿d×⌊d÷˜x0+b}•_while_{<´¯2↑𝕩}⍟(1<𝕩) ⥊>⟨0‿1⋄1‿𝕩⟩↑˜2⌊1+𝕩}1000

- 76ms

@xpqz No, Ag←{(,÷∨)∘1¨{⍵[⍋⍵]}0,∪1⌊,∘.÷⍨⍳⍵}:

  X 100  → 8.6E¯3 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  Ag 100 → 1.8E¯3 | -80% ⎕⎕⎕⎕⎕⎕⎕⎕

I am still keen to understand why the power varieties die on largish numbers -- is it the cost of passing the accumulator betwen iterations?

I think it is the many times accessing memory.

Try writing a tail recursive version, or use an external accumulator.

here's an APL one with an explicit accululator -

{r←↑(0 1)(1 ⍵)↑⍨2⌊1+⍵ ⋄ r ⊣ {(a b c d)←,¯2↑r ⋄ r⍪←a b-⍨c d×⌊d÷⍨⍵+b ⋄ ⍵}⍣{≥/⊢⌿r}⍣(1<⍵)⊢⍵}

4:02 PM

  X 100  → 9.0E¯3 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  Ag 100 → 1.8E¯3 | -81% ⎕⎕⎕⎕⎕⎕⎕⎕
  ↓D 100 → 6.3E¯3 | -30% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

@Adám I stil like this one the most. More APL'llke instead of translating a formula into APL

@dzaima for 1000:

      cmpx 'D 1000' 'X 1000'
  D 1000 → 8.9E¯1 |    0% ⎕⎕⎕⎕⎕⎕⎕
* X 1000 → 4.9E0  | +447% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

That makes sense. Yours should be faster.

  X 1000  → 1.3E0  |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  Ag 1000 → 1.9E¯1 | -86% ⎕⎕⎕⎕⎕⎕
  ↓D 1000 → 6.5E¯1 | -49% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

@Adám why is yours faster than mine?

I might be able to answer that if I understood yours.

Oh wait, ÷/¨ vs ∘.÷

So mine at least stays flat for the O(n²) part.

4:08 PM

This was an interesting problem.

Also, yours uses the set function ∩ to filter out those pairs that end up > 1, while mine simply caps them at 1.

∩ has to decide per-element. ⌊ can apply to all.

Good luck with the video @Adám. Could become one of an hour with some major preparation :)

hehe, thanks. I think I understand most of X now, except the triple-indexing.

also, dzaima/APL brute force that I wrote first - 310ms for 1000

OK, got the indexing.

@Steffan Welcome back.

For general interest, here's a Boolean mask version of X:

 X ← {f[k][⍋d[k←(⍸d≤1)∩⍸≠d←÷/¨f←,(⊂0 1),,⍳⍵ ⍵]]}
Xb ← {(k/f)[⍋d/⍨k←(d≤1)∧≠d←÷/¨f←,(⊂0 1),,⍳⍵ ⍵]}

(I used this to understand X)

@xpqz Maybe also because I use the sort idiom.

4:17 PM

I need a G&T.

Yeah, see y'all next week for PDI - Progressive Dyadic Iota.

Gin Tonic?

I have a great one for that.

@Richard aye

:)

@xpqz 🍸

4:20 PM

I'll probably will not be able to join the next three/four times. Nevertheless I will do my homework and try to send them at least.

You'll be here in ~~spirit~~ code.

ngn/k: {?(,!2),x@*'<==%/'x}1_+&+|\=1+

These problems seem to be getting harder

Yeah, this year seems tougher.

@dzaima some micro-optimization gets it down to 62ms:

{∘‿2⥊𝕩{𝕩∾((¯2↑𝕩)×⌊(𝕨+¯3⊑𝕩)÷¯1⊑𝕩)-¯2↑¯2↓𝕩}•_while_{<´¯2↑𝕩}⍟(1<𝕩) ⥊>⟨0‿1⋄1‿𝕩⟩↑˜2⌊1+𝕩}1000

4:25 PM

@dzaima Is there somewhere I can read up on •_while_?

@Adám here - it's currently CBQN-specific

Thanks.

p.s. I managed to solve the encode/decode problem for the competition. Any suggestions on which one might be the next most easy to solve?

   )t:10 {𝕊x0: ∘‿2⥊{𝕩∾((¯2↑𝕩)×⌊(x0+¯3⊑𝕩)÷¯1⊑𝕩)-¯2↑¯2↓𝕩}•_while_{<´¯2↑𝕩}⍟(1<𝕩) ⥊>⟨0‿1⋄1‿𝕩⟩↑˜2⌊1+𝕩}1000
60.73ms
without •_while_, using {𝔽⍟𝔾∘𝔽_𝕣_𝔾∘𝔽⍟𝔾𝕩} instead:
   )t:10 {𝕊x0: ∘‿2⥊{𝕩∾((¯2↑𝕩)×⌊(x0+¯3⊑𝕩)÷¯1⊑𝕩)-¯2↑¯2↓𝕩}{𝔽⍟𝔾∘𝔽_𝕣_𝔾∘𝔽⍟𝔾𝕩}{<´¯2↑𝕩}⍟(1<𝕩) ⥊>⟨0‿1⋄1‿𝕩⟩↑˜2⌊1+𝕩}1000
67.95ms

@Richard You mean this year's Phase 2? Base₈₅?

4:31 PM

@Adám yes

I'd say ⍴ is pretty simple.

And "It's a Date!".

ok thanks!

5:05 PM

@Adám ?!

« first day (1990 days earlier) ← previous day next day → last day (665 days later) »

Transcript for

Jul '228

The APL Orchard

apl.chat ― Learn, teach, ask, code, golf, & discuss usage. See ...

apl array-manipulation j tips

join this room
about this room

00:00

06:00

12:00

18:00

all times are UTC

site design / logo © 2024 Stack Exchange Inc; legal

mobile