The APL Orchard

6:36 AM

@LdBeth Make the / very long and very slanted and make - very short.

3:00 PM

Welcome to APL Quest 2014-6! Today's quest is Roll The Dice:

> Write a dfn that takes an integer vector representing the sides of a number of dice and returns a 2 column matrix of the number of ways each possible total of the dice can be rolled.

xpqz

I offer {,∘≢⌸,+/↑,¨⍳⍵}

Adám

That would fail with 16 dice.

xpqz

I consider that an implementational detail :)

rabbitgrowth

Mine was {,∘≢⌸,+/¨⍳⍵}

Richard

Have to find mine, just a moment, sorry

Adám

3:02 PM

An "issue" for both of these is the usage of nested arrays.

Richard

 {⍺,≢⍵}⌸,+/¨⍳⍵

Adám

Huh, you both disagree with the last example case. I do too.

Richard

quite simular this one

Adám

Clearly, there's only one possible outcome, so the result should be 1 2⍴0 1

Luckily, the test framework doesn't seem to test that case. I should change it.

xpqz

Maybe add the 16+ dice test, too

Adám

3:07 PM

@Richard Yeah, that's the same as rabbitgrowth's, except for making the Key operand explicit (and omitting braces).

Richard

{+⌿⍵∘.=⍞←(¯1+⌊/⍵)↓⍳⌈/⍵}{,+/¨⍳⍵ }

Adám

I have {,∘≢⌸+⌿1+⍵⊤⍥,¯1+⍳×/⍵}

@Richard That doesn't look right.

I wonder if the right column can be computed directly, rather than actually counting.

Richard

@Adám is does work, only not in two columns.

I just replaced Key

Adám

Yes, you implemented it, but you need {l,⍪+⌿⍵∘.=l←(¯1+⌊/⍵)↓⍳⌈/⍵}{,+/¨⍳⍵} to get the result.

Richard

ah, ok

Adám

3:11 PM

Might be better to write ⍤0 than ⍪

Richard

btw it is slow, ⌸ is faster. Hoped to get some speed improvement

Adám

Hm, I'd have expected that too, as your computation of the range is a nice way to avoid finding the unique.

rabbitgrowth

@Adám Why do you need the ⍥,?

xpqz

Feels like there should be a super-fast not-key solution (that I can't find)

rabbitgrowth

Ah, because the argument can be a scalar?

Adám

3:14 PM

Yes.

I actually need ,⍛⊤ rather than ⊤⍥, but we don't have ⍛ yet.

@xpqz Agreed.

Richard

@xpqz I have been thinking about permutations.

but have no other solution

Adám

@Richard Instead of comparing all elements for the min and max, you can take the first and last. And instead of generating the entire range and dropping leading, you can compute how much to generate, and then adjust: {b←⊃⍵ ⋄ e←⊃⌽⍵ ⋄ l,⍤0+⌿⍵∘.=l←b+¯1+⍳e-b-1}

Richard

Yes indeed.

ovs

Here is a terrible one without Key: {(¯1+(≢⍵)+⍳≢x),⍪x←⊃{+⌿↑↑∘⍵¨1-(⍳⍺)+≢⍵}/⍵,⊂,1}

Adám

What even is that‽

dzaima

3:20 PM

shorter than mine - {((¯1+⍳∘≢)((0≠⊢)⊢⍤⌿,[1.5])⊢) ⊃{⍺+/(⍺⍴0)(,,⊣)⍵}/⍵,1}

ovs

It builds the right column one die at a time

xpqz

@ovs It definitely works....

Razetime

this looks like a pascal's triangle-ish pattern

so i assume binomial is useful here

Adám

Possibly. There seems to be a recursive solution too.

NARS2000's ‼ should be able to make quick process of this.

dzaima

@dzaima shorter - {(0∘≠⊢⍤⌿⊢,[1.5]⍨¯1+⍳∘≢) ⊃{⍺+/(⍺⍴0)(,,⊣)⍵}/⍵,1}

@dzaima alternative - {((¯1+(≢⍵)+⍳∘≢),[1.5]⊢)⊃{⍺+/⍵(⊢,,)0⍴⍨⍺-1}/⍵,1}; half is still just adding the first column

Adám

3:30 PM

Isn't the first column just the numbers from ≢⍵ to +/⍵?

Richard

@ovs no outer product, so probably much more efficient

ovs

maybe, but the reduction isn't great either

with a bit less nesting: {(¯1+(≢⍵)+⍳≢x),⍪x←⊃{¯1↓+⌿(⍳⍺)⌽⍤0 1⊢⍵,⍨⍺⍴0}/⍵,1}

dzaima

@Adám {(((¯1+≢⍵)↓⍳+/⍵),[1.5]⊢)⊃{⍺+/⍵(⊢,,)0⍴⍨⍺-1}/⍵,1} - not any shorter

(I guess for golfing you could ↑(((¯1+≢⍵)↓⍳+/⍵),¨⊢))

Adám

This looks interesting:

  ovs 2⍴6    → 5.2E¯6 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  dzaima 2⍴6 → 5.5E¯6 |  +5% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  adam 2⍴6   → 1.6E¯6 | -70% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

  ovs 3⍴6    → 7.8E¯6 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  dzaima 3⍴6 → 8.2E¯6 |  +4% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  adam 3⍴6   → 4.7E¯6 | -40% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

  ovs 4⍴6    → 9.8E¯6 |    0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  dzaima 4⍴6 → 9.9E¯6 |   +1% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  adam 4⍴6   → 2.6E¯5 | +163% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

More interesting performance:

  ovs 16⍴2    → 2.5E¯5 |     0% ⎕
  dzaima 16⍴2 → 1.6E¯5 |   -35%
  adam 16⍴2   → 1.4E¯3 | +5466% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

dzaima

@dzaima one shorter (+ not using ,¨) - {(((≢1↓⍵)+⍳∘≢),⍤0⊢)⊃{⍺+/⍵(⊢,,)0⍴⍨⍺-1}/⍵,1}

Adám

3:42 PM

@ovs @dzaima How fast (rather than short) can you get?

Well, I guess we're done, other than those speed tweaks.

Richard

Did you also check the speed for the Key solutions? Is it indeed slower?

Or is that the third one in your speed test?

dzaima

@Adám my solution is O((+/⍵) × ⌈/⍵) or something like that; given that the result has length O(+/⍵), the ⌈/⍵ term isn't strictly necessary and is space for improvement

Adám

@Richard Yeah, that's adam but using {⍺,≢⍵} which is much faster than ,∘≢

ovs

@Adám My first function (with ↑∘⍵¨) was the fastest I've gotten so far :/

dzaima

@dzaima (a slightly simplified big O would be O((≢⍵) × (⌈/⍵)*2))

ovs

4:01 PM

Not faster, but might be of interest: If Pm is polynomial multiplication, {⊃Pm/⍴∘1¨⍵} builds the right column

dzaima

4:13 PM

(i'm working on something horrible that's gonna be slower and might not work and is gonna be very messy, but is fun)

ovs

Full J solution using the polynomial multiplication: (# }. [: i. 1++/) ,. [: +//.@(*/&>)/ #&1&.>

dzaima

voilà:

{a i←↓⍉(⊂∘⍋⌷⊢){⍺,+/⍵}⌸∘(,∘-⍨⍣(≢⍵),1) ⊃{⍵,⍺+⍵}/⍵,,⊂1 ⋄ 0~⍨+\⍣(≢⍵)⊢ (⍸⍣¯1⊢a)\i}

for the second column

comparison; so this is better with a short length but large elements, while my original is better with many elements
https://dzaima.github.io/paste/#0xVK7TsMwFN39FXdBTYgT7DxKfgCmbggxUIaKLB0qdUQqYQAU9WWEQEjMZYCtCxUVYz/lfgnXdgiR2gWEVCuKdex7zj0nuQB6ZRKL@wGObwaoPr09VAsHxzPOXYHqHdUbnfoy1@dc5gwsJ9ScDnRpw@IR1Yg41zh8RjXB6QfxXa3GjVyO0yVdOZxevhF8cXA0oxuXSxds5wXX3XW16cRJTgJObkFcEcVr10ikDg6qJR2t5pJQx213c1ZaO@/1L6CRSZDavxSiQSj8QUwnriBg8QBREB@s5jFcEl3sAN49beVhu1AzapzFQUrOEnLmp81NztZSh5ZuQ38Dm7lERrgZiFIYqtC2f70qChKqiqjKS/bTbX6a9Z9bz1khdnIEh8etFsvCU3H2n2P6lyndMKTwy4XD1y8#BQN

Richard

4:28 PM

:) What did you do?

dzaima

@Richard stared at this for a long time

({,∘~⍨⍣⍵,0} for the first 2*⍵ elements of the ABBA/thue-morse sequence would be a nice addition to APLcart)

ovs

{q←0≤t←∘.-⍨⍳m←1+(+/⍵)-≢⍵ ⋄ (¯1+(≢⍵)+⍳≢x),⍪x←⊃+.×/((q∧t∘<)¨⍵),⊂m↑1} seems to perform a bit better than the previous solutions (at least for 16⍴2)

dzaima

4:48 PM

@dzaima oh here's a fun thing - this requires all the intermediate items to be evaluated precisely, but ⌈/f 10⍴90 is 1.6e17, so this happens

dzaima

5:12 PM

you can hack that away with

{a i←↓⍉(⊂∘⍋⌷⊢){⍺,+/⍵}⌸∘(,∘-⍨⍣(≢⍵),1) ⊃{⍵,⍺+⍵}/⍵,,⊂1 ⋄ (⊢,(2|≢t)↓⌽) +\⍣(≢⍵)⊢ (⌈.5×≢t)↑t← (-≢⍵)↓(⍸⍣¯1⊢a)\i}

- computing one half and reversing & appending the result; but the problem of the result overflowing 53 bits is still a thing, and means that for reasonably sized inputs you'd need to consider the implications of arbitrary-precision arithmetic too

Adám

We've chosen the universal logo for APL:

Get your mugs, tote bags, shirts and hoodies from the APL stuff store!

2

pitr

7:42 PM

hi, just upgraded from Dyalog 18 to 18.2 and now dyalog -script file.apl does not print every line, I need to explicitly print with ⎕←. Any way to return that behaviour

um, should mention that I DID switch to: /usr/local/bin/dyalogscript file.apl

doug

I had {⍉↑((⊂⊣/),∘⊂¯1+(+/(1⌊⊢))),⌸+/¨,⍳⍵}

Transcript for