Encode 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. As a memory aid, we can 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).

As we saw previously, ⊥ is quite simple. In a way, it is a fancier +.×: 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. One 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, for example, 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.

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, building 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 in order 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. 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

There’s the second-from-right element of our result. Let’s prepend it to get a preliminary result of 13 45. 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

That’s the next value in our result, giving us 1 13 45. How much is left now?

11520-1440

10080

Which you might recognise as a single week (expressed in minutes), giving us another 1 in our result: 1 1 13 45.

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

I can’t pay 42 pence as 1 quarter, 1.5 dimes, and 2 pennies! Sure, mathematically, it’d work, but I’m not sure the US mint will be too excited if I start chopping dimes in half.

So what happened here? 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? 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. 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. 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. However, mints are careful to only issue pieces in such a way that a greedy algorithm works.

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

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.

Let’s look at some neat tricks with ⊤. You can use 0 1⊤ to split a number into its integer part and fractional part:

0 1⊤3.14
0 1⊤3.14 2.7 100.23

3 0.14

3    2   100
0.14 0.7   0.23

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

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

⍬⊤2 3⍴⎕A

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

Using 0-based indexing, this is very simple:

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

2 3

N

N

We need ⎕IO←0 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.