Lesson 38 - ⊤ in depth – Conversation in The APL Orchard

Adám

Mar 26, 2020 14:30

Hello and welcome to APL Cultivation!

xpqz

Hello.

Adám

Today's subject is ⊤ in depth, as a continuation of the previous lesson, ⊥ in depth.

⊤ is known as "Encode" or "Represent"

It takes a number (or multiple numbers, in the same way as with ⊥) as right argument and generates a representation in the (mixed) number base(s) given in the left argument.

I like to call it N-code ("encode") to remember that it is typed with APL+n

(While ⊥ is clearly a "base", and indeed evaluates numbers in custom bases, B for base; type it with APL+b.)

xpqz

I've learnt you can "zero-pad" an int as 4⊤⍨5⍴10.

Adám

@xpqz Sure, but that splits the digits too.

xpqz

Yes.

Adám

Mar 26, 2020 14:35

Is everyone clear about how ⊥ works?

xpqz

It's the inverse, sort of?

Adám

Well, ⊥ is quite simple. In a way, it is a fancy +.×

It just gives the given "digits" weights, and sums the result.

The weights being determined from the reverse cumulative product of the left argument. (And there's some transposing going on too.)

⊤ is much more complex, computationally speaking, but not really conceptually, where it is basically the inverse operation.

I think the best way to explain it, is to show how ⊤ constructs its result. As a simple example, let's take:

      0 7 24 60⊤12345
1 1 13 45

The 0 7 24 60 here represents a number system with 60 of the basic units in the next larger unit, 24 of those larger units in the next larger, etc.

It could e.g. be 60 minutes in an hour, 24 hours in a day, and 7 days in a week.

The 0 means that there are no larger units, and we'll keep stacking large value multiple in that position no matter how big the "pile" gets.

Compare this to making cash change. There's nothing larger than a $500 unit, so even if we have to pay a million, we'll have to use lots of $500s.

OK. What are our weights?

      ⌽×\⌽1,⍨1↓0 7 24 60
10080 1440 60 1

That is, there's 1 minute in a minute, 60 minutes in an hour, 1440 minutes in a day, and 10080 minutes in a week.

We can check the result that ⊤ gave us, by using these weights:

      1 1 13 45+.×⌽×\⌽1,⍨1↓0 7 24 60
12345

Yup, that worked.

How did ⊤ get the result then?

Let's do it step-by-step. We build our result from the right.

The first unit rolls over at 60, so we can find how many of the smallest units (here, minutes) we need to get the exact total value by applying division remainder:

      60|12345
45

There's our right-most "digit". Let's put that aside in our result. How many minutes are left?

      12345-45
12300

The next unit (the hours) consist roll over at 24 hours of 60 minutes each.

So any multiple of 24 hours will be days instead. We only want the remainder of 24-hour-periods, that is, 24×60 minutes, to be counted in hours:

      (24×60)|12300
780

This is how many minutes we want counted as hours. How many hours is that, though?

      60÷⍨(24×60)|12300
13

Hey, there's the second-from-right element of our result. Let's prepend it to get a preliminary result of 13 45

So we've used 780 minutes this time around. How much do we have left (which will be counted in days and maybe weeks)?

      12300-780
11520

Next up are days, which we'll use to fill until we have a value that can be counted in whole weeks.

A week, of course, being how many minutes?

      7×24×60
10080

So we need the division remainder when divided by that.

      (7×24×60)|11520
1440

That's how many days (stated in minutes) we have. How many actual days does that add up to?

      (24×60)÷⍨(7×24×60)|11520
1

Well, that's the next value in our result, giving us 1 13 45. And left is how much?

      11520-1440
10080

Which you might recognise as a single week (expressed in minutes), i.e. we get another 1 in our result: 1 1 13 45

@all How was that? Still alive?

Jeff Zeitlin

Mar 26, 2020 14:57

/me nods

Adám

Any questions so far?

OK, I'll take the silence as a no.

Now for the classic question. Why doesn't this work for making change?

      4 2.5 2 5⊤42 ⍝ 4 quarters in a dollar, 2.5 dimes in a quarter, 2 nickels in a dime, 5 pence in a nickel
1 1.5 0 2

0/10 — I can't pay 42 pence as 1 quarter, 1.5 dimes, and 2 pennies!

Jeff Zeitlin

Is it because of the fractional multiplier?

Adám

I mean, sure, mathematically, it'd work, but I'm not sure the US mint will be too excited if I start chopping dimes in half.

@JeffZeitlin Yes, but what exactly happened?

Let's walk through the process again.

We start by finding what the remainder is, which we'll have to pay in pennies:

      5|42
2

That leaves 40 pence.

Since 2 nickels go into a dime, we do a mod-10 to find how many nickels we need:

      (2×5)|40
0

None, of course. So we still have 40p or ¢40 if you want.

Continuing on, how many dimes?

Jeff Zeitlin

Should be 4

Adám

@JeffZeitlin But it can't be, because the dimes roll over at 2.5:

      (2.5×2×5)|40
15

So only 15 pence will need to be paid in dimes. Herein lies our problem.

That's of course 1.5 dimes. Hence our result.

And left over is 40-15, that is, 25 pence, enough for a single quarter.

Actually, proper change-making with arbitrarily valued coins is a weakly NP-hard problem.

RGS

Mar 26, 2020 15:10

@Adám how so?

(I do not want to disrupt! I assumed it was ok to ask questions, please let me know if it is not!)

Adám

@RGS Look at the total amount as a knapsack you need to fill. You only have items of fixed volume to put in there. There's no obvious way to see exactly how to fill the bag fully.

@RGS (no, by all means, this is intended to be an interactive lesson, not a monologue!)

RGS

But for coins there is!

A greedy algorithm works

Assuming you want to minimize number of coins used, ofc

Adám

Ah, this is because mints are careful to only issue pieces so that the greedy algorithm works.

RGS

Really..?

xpqz

I had no idea.

RGS

Mar 26, 2020 15:13

Can you provide an example?

Ah nice, making 12 with coins of sizes [10, 7, 5, 1]

Greedy would do 10 + 1 + 1 but I would be better off with 7 + 5! Nice :D

Adám

US coins are 1 5 10 25 50 and 100… UK coins are 1 5 10 20 50 100…

xpqz

(UK +2?)

(UK +200, too)

Jeff Zeitlin

a 20p coin? Must be a legacy from the Lsd days...

RGS

So if the next coin is at least the double of the previous one, it always works, right?

Adám

Hm, I think so.

Jeff Zeitlin

Mar 26, 2020 15:18

In the simple case, where each value "rolls over" at the same number of previous values, I have to specify all of the places - e.g., I can't just say 2⊤13 to get 1 1 0 1; I have to explicitly extend the left argument. I don't have to do so with ⊥. Why the difference?

Adám

@JeffZeitlin ⊤ gives you the possibility of running a custom counter or odometer which rolls over eventually. Think of the case 24 60 60⊤. If it didn't "chop" (mod, really), there'd be no way to know what the next digit value would be.

So what 2⊤13 means is a base-2 odometer with a single digit display, rolling over whenever the value exceeds 1.

Now, you could complain that this equates 2 and ,2.

You'd be right. There probably never any reason to use a scalar as left argument for ⊤. If you want mod, use |

Jeff Zeitlin

So, really, ⊤ is less useful for simple (homogeneous) base conversion than inverting ⊥ - but is absolutely more useful for heterogeneous conversions.

Adám

The only difference between ⊤ and | for scalar left arguments, is comparison tolerance (⎕CT) which | cares about, but ⊤ ignores.

But if you want ⎕CT←0, you should set it explicitly rather than obscuring your code with ⊤ and a scalar left argument.

Jeff Zeitlin

(unless you're golfing...) :)

Adám

Yeah, never happened to me.

So, as Jeff said, if you want a variable number of digits, just depending on the how many are needed, use ⊥⍣¯1

@all Any more questions before we look at some neat tricks with ⊤?

Jeff Zeitlin

Mar 26, 2020 15:30

/me is ready for the tricks

Adám

You can use 0 1⊤ to split a number into its integer part and fractional part:

      0 1⊤3.14
3 0.14
      0 1⊤3.14 2.7 100.23
3    2   100
0.14 0.7   0.23

Jeff Zeitlin

Oh, nice! DivMod!

Adám

You can use ⊤ to split "packed integers":

      0 100 100⊤20200326
2020 3 26

A golfing trick is getting 0 0⍴0 (an empty numeric matrix):

      (0 0⍴0) ≡ ⍬⊤⍬
1

Jeff Zeitlin

@RGS - Bot's down; @Adám is running them on a local terp and then cutpasting.

RGS

@JeffZeitlin k, thanks!

Adám

Mar 26, 2020 15:37

If fact, you can "silence" anything by making the leading axis have length 0 using ⍬⊤:

      ⍬⊤2 3⍴⎕A

Jeff Zeitlin

So that adds a dimension - that is, it converts the rank-2 array created by 2 3 ⍴ ⎕A into a rank-3 array of ⍴ 0 2 3

(determined experimentally in the terp)

Adám

If you have a multi-dimensional array, but want the Nth element without having to ravel the array, how do you find the multi-dimensional index of the sought element?

Consider:

      4 5⍴⎕A
ABCDE
FGHIJ
KLMNO
PQRST

RGS

You use this thingy you have been talking about with the lengths of the axis?

Adám

@RGS Yes. It is called Encode or Represent.

Using 0-based indexing, this is very simple:

      ⎕IO←0
      4 5⊤13
2 3
      (4 5⊤13)⌷4 5⍴⎕A
N
      13⊃,4 5⍴⎕A
N

@all Do you understand why?

Jeff Zeitlin

Why force ⎕IO to 0?

Adám

Mar 26, 2020 15:47

Because of how ⊤ works. It does a mod (|) all the time. When we "roll over" from one row to the next, we end up in position 0.

Jeff Zeitlin

OK.

But that means that getting the "N"th item is really getting the "N+1"th item, considering the ordinals in the 'natural' way.

Adám

@JeffZeitlin True.

Jeff Zeitlin

Briefly getting back to the problem of making change... The problem in the US model happens because we have that fractional multiplier. Would it actually work for UK coinage, where you have the 20p piece instead of the quarter?

Adám

@JeffZeitlin No because there are 2.5 20p coins on a half-pound.

Jeff Zeitlin

OK. We theroretically do have the half-dollar, but I can't remember the last time I actually saw one - for the most part, day-to-day coinage stops with the quarter, plus the occasional dollar coin thrown into the mix.

If the 50p is more common, I can see the problem simply shifting a bit.

Adám

Mar 26, 2020 15:59

OK, if there are no more questions. then that's it for today.

Jeff Zeitlin

No, I think I'm clear on it.

Adám

Thank you for participating!

Lesson 38 - ⊤ in depth

The APL Orchard

Participants