A New Stack for the APL Challenge

In February 2026, the APL Challenge quietly launched its next round on a rewritten stack. The previous infrastructure was retired and replaced by something considerably smaller and, I think, much more pleasant to maintain. This blog post describes how we got here, and shows off some of the Dyalog v20.0 idioms that shaped the rewrite along the way.

A short tour of competition history

Dyalog Ltd has been running some form of programming contest for 17 years now, and almost every era has had its own stack.

2009-2012 – Email: The earliest competitions were essentially mailing lists: Brooke Allen seeded the very first World Wide Programming Competition with the first twenty Project Euler problems, and entrants emailed in their solutions. Subsequent International APL Programming Contest rounds described the tasks on the main Dyalog Ltd website. The 2011 winner, Joel Hough, observed that most popular programming languages had a “Try X” website that let newcomers experiment without installing anything, and that APL didn’t. Participation was restricted to those who could prove their student status; participants also needed to apply for a free educational licence. They could only access the full Dyalog product (and start solving problems) once the application was approved and they had downloaded and installed the system. Joel’s suggestion led directly to the creation of TryAPL, significantly lowering the bar to entry.

2013-2018 – StudentCompetitions/Sqore: Task descriptions and submissions moved onto the third-party platform StudentCompetitions (later renamed Sqore), and the title went through a period of flux, eventually settling on the APL Problem Solving Competition, emphasising APL as a problem solving tool over the mechanical programming aspects. The problems were split into two “phases”: Phase 1 consisted of ten “one-liner” problems while Phase 2 had a PDF specification of more complex problems and included a template for answering. There wasn’t much code involved on our side, but submissions arrived in inconsistent formats and weren’t sandboxed in any way, so each one had to be inspected (and possibly reformatted by hand) before it could be run. We used Phase 1 as a filter; you could only enter Phase 2 if you had correctly answered a minimum of one problem from Phase 1. We wrote ad-hoc code for testing at least parts of Phase 2. From 2014, we also allowed non-student participants, but they could only win a free trip to the next user meeting, and not a cash prize like the student winners.

2019-2021 – Back in-house: The contest moved onto Dyalog-grown infrastructure. Almost everything we could write in APL, we wrote in APL:

  • MiServer generated and served the website
  • HttpCommand talked to remote services
  • SMTP sent confirmation emails
  • DCL hashed passwords
  • Conga provided network communications for both MiServer and HttpCommand
  • DrA logged and reported errors to the developers
  • SQAPL communicated with a MariaDB database

This is what it looked like:

APL Problem Solving Competition screenshot

The sources were managed with Git and stored on GitHub in two repositories: one which held the MiSite code and styling, and one which held the per-round JSON test specifications and per-problem MiPages. The intention was that Jenkins’ continuous integration using Docker containers deployed using Rancher (and later Docker Swarm, when Rancher went all-in on Kubernetes) would make content updates hot-swappable into a running site. In practice, this never worked reliably and content pushes regularly required a service restart anyway, and the split added co-ordination overhead between the two repositories.

We used HAProxy for load balancing and reCAPTCHA to keep the bots out. Phase 1 validation was done by generating test scripts which were then sent to Try It Online for sandboxed execution. Phase 2 was a glorified file upload form. Brian Becker showed a simplified diagram of the moving parts in his Dyalog ’19 presentation:

Brian's diagram

2022-2023 – Enhancements: The Try It Online dependency was replaced with Safe Execute, itself derived from the original TryAPL code, and bespoke checks were added to verify that submitted Phase 2 entries followed the syntactic constraints of each task. Code quality still factored into the final score, so the automated tests were one input among several.

In his introduction to the competition prize-giving ceremony during Dyalog ’23, Brian outlined our thoughts for the future of the competition.

Enter the APL Challenge

In February 2024 we launched the first round of the APL Challenge, replacing the previous Phase 1. After a short break, Phase 2 also got a replacement: The APL Forge. The competition was now:

  • for everyone: While previous competitions exclusively or primarily targetted students, the APL Challenge is equally open to everyone. To facilitate participation by younger, new-to-APL, and foreign-language contestants, its descriptions of APL features and problems are deliberately written in a simplified style.
  • always open: Previously the competition was open for a few months each year. The APL Challenge is open (almost) continuously, with four rounds each lasting three months (with only a day’s down-time between them), and each round is followed by the awarding of prizes.
  • self-contained: Previously, you had to learn APL on your own to be able to participate. With the APL Challenge, each round teaches everything that is needed as part of the problem statements, building up to a more demanding tenth problem (often inspired by – or lifted directly from – the old Phase 1 archive).
  • entirely automated: Every submission is quickly and fully checked, with prizes awarded only based on correctness.

Initially, we recycled the existing server set-up, including the account system and the Phase 1 code for presenting problems and checking submissions. However, that code had already accumulated a significant amount of technical debt, and the changes needed to repurpose it didn’t help. MiServer’s performance characteristics meant that we had to run several parallel containers behind a load balancer, and the automated checker was slow because each submission was juggled across threads. When I showed the APL Challenge to a couple of classes at my children’s school, I also noticed that the account system was a significant barrier: the children either had no email addresses of their own, or couldn’t access them during school hours, which halted the sign-up flow before it began. Although none of this was really broken, it was a consideration for the list of “things to clean up when there’s time”.

The front end of the site was also redesigned to align more closely with modern styling:

MiServer-based APL Challenge screenshot

In late 2025 I finally found the time we needed. With Dyalog v20.0’s release approaching, I incorporated several of the key features introduced in that release into my rewrite – especially ⎕VGET, the enhancements to ⎕NS, array notation, and the behind operator (), but even the new ⎕SHELL found a use in the code base. Most of the code is fairly straightforward, but one section constructs APL expressions, including single-line dfns, at run time to put the participant’s solution into an appropriate testing context. Traditional debugging tools fell short here, but inline tracing came to the rescue. The result has been live since February 2026.

The new stack

We’d accumulated a lot of experience with Material for MkDocs from the online documentation overhaul for Dyalog v20.0 (compare it to the older v19.0 site it replaced) and from rewriting the APL Quest site, which hosts the old APL Problem Solving Competition Phase 1 problems. Both sites are static MkDocs builds, although the APL Quest does automated checking using an external fork of Attempt This Online, and both have proven straightforward to maintain. Reusing Material for MkDocs as the APL Challenge frontend was the obvious move. Combined with Jarvis for the backend and a small amount of dynamic content, the new stack is:

  • APL code that builds a static site for each round using Material for MkDocs.
  • Jarvis with one small enhancement, serving both the static site and a four-endpoint JSON API.
  • HttpCommand to forward subscription requests to MailerLite.
  • Conga for Jarvis and HttpCommand.
  • Git, GitHub, Docker Swarm, and Jenkins (as before).

By adding Material for MkDocs and Jarvis, we were able to remove MiServer, SMTP, DCL, DrA, SQAPL, HAProxy, Rancher, MySQL/MariaDB, reCAPTCHA, Safe Execute, the load balancer, the multiple container replicas, the dual-repository arrangement, and seven JavaScript libraries used by the MiSite code.

The database was replaced with two TSV (Tab-Separated Values) files in persistent storage. Authorisation, where it exists, is a token that is compared to an environment variable.

After some deliberation, and consulting with our in-house GDPR experts, we also found a way to remove the need to register: the participant’s email is now submitted along with each solution. This let us remove the whole signup-password-confirmation-email procedure, so children at school can use their own (or their parents’) email address without needing access to it immediately, and only receiving an email if they win a prize.

The entire backend is now just over 400 short lines (averaging less than 25 characters) of APL across 16 functions, plus one namespace of 35 English phrases (we plan on adding internationalisation later). For comparison, the previous site used over 2,000 lines of APL and eight files of English phrases and email stubs.

One static site for each round

Each round teaches a different progression of glyphs and concepts. Rather than rendering pages dynamically, we build one Material for MkDocs site for each round. Each round lives in its own uppercase single-letter directory (A through I, with Z reserved for the holding-period site that’s served between rounds). The previous system identified rounds by calendar slots (2024’s round 1 was 20241, and so on). Decoupling round identity from the schedule means that a given round can be re-served later and a round can be designed and tested entirely independently of when it goes live.

A single copy of the shared files and folders – assets, JavaScript, and the legal and front pages – are kept in add/. Before the MkDocs build runs, these are copied into each round’s directory and {{X}} placeholders in markdown files are substituted with the round letter:

 dirs←⊃⊢⍤//1=@1⊢1 0 ⎕NINFO ⎕OPT 1⊢dir,'/?'
 Copy←{
     dest←d,'/',⍺
     ⎕←'COPY -',(2↓∊' & '∘,¨⊆⍵),' → ',∊1 ⎕NPARTS dest,'/'
     dest ⎕NCOPY ⎕OPT'IfExists' 'Replace'⊢(dir,'/add/',⍺,'/')∘,¨⊆⍵
 }
 ls←⊢/¨dirs
 incl←ls∊build
 :For d l :InEach incl∘/¨dirs ls
     ''Copy'mkdocs.yml' 'overrides'
     'docs'Copy'ass' 'js' 'legal.md','index.md'/∘⊂⍨'Z'≠l

     files←(0∊2∘⊃∊⎕D⍨)¨⍤⎕NPARTS⍛/⊃⎕NINFO ⎕OPT 1⊢d,'/docs/*.md'
     :For file :In files
         cont←⊃⎕NGET file 1
         file 1 ⎕NPUT⍨⊂'{{X}}'⎕R l ⎕OPT'Regex' 0⊢cont
     :EndFor

     :If build∩0 1
         {⎕←⍵}¨⊃⊃⎕SHELL ⎕OPT'WorkingDir'd⊢'python -m mkdocs build'
     :EndIf
 :EndFor

A hot-swappable Jarvis

Jarvis serves a static directory using its HTMLInterface setting. However, that setting was defined as a field that was read once when the server starts, and we needed to be able to switch which round’s site/ directory was being served while the server was running, on a fixed UTC schedule. So we amended Jarvis to make HTMLInterface a property: assigning to it now adjusts the private fields that were previously only set at boot time.

That small change is what makes the rest of the design work; round switching is a background thread that watches a single TSV file:

 :Repeat
     :Trap 0
         newChange←13 ⎕NINFO filename
         :If change≢newChange
         :OrIf 0∊40 ⎕ATX'utc' 'dir'
             change←newChange
             (utc dir)←⊃(TSV ⎕OPT'Invert' 2)filename ⍬ 1 1
             inst.Log'Schedule loaded from ',filename
         :EndIf
         begin←1 ⎕DT(2⊃⎕VFI)¨' '@(~∊∘⎕D)¨utc
         interval←begin⍸now
         :If 900⌶0
             newRound←interval⊃dir
         :EndIf
         :If round≢newRound
             round←newRound
             html←⌽round@7⊢'/',(⊃∊'/\'⍨)⍛↓⌽inst.HTMLInterface
             inst.Log'Web interface changed: ',inst.HTMLInterface,' → ',html
             inst.HTMLInterface←html
             file←inst.CodeSource,'/',round,'.json5'
         :EndIf

         newTestFileInfo←FileInfo file
         :If fileInfo≢newTestFileInfo
             fileInfo←newTestFileInfo
             inst.Log'Test data updated from ',file
             data←0 ⎕JSON ⎕OPT'Dialect' 'JSON5'⊃⎕NGET file
         :EndIf

         :If ~900⌶0
             :Leave
         :EndIf
         t←20 ⎕DT'Z'
         ⎕DL 1+1800|¯1-t ⍝ wait until next half-hour
     :Else
         …
     :EndTrap
 :EndRepeat

Every half an hour, the thread re-reads schedule.tsv if its modification time has changed. If the round that should be live differs from the one currently being served, then the HTMLInterface property is updated; the corresponding test data is then (re-)loaded if either the test data file or the round has changed. The schedule itself is a two-column TSV mapping UTC start times to round letters:

utc                 dir
…
2026-01-30 09:00    Z
2026-02-11 09:00    G
2026-04-30 08:00    Z
2026-05-01 08:00    C
2026-07-31 08:00    Z
2026-08-02 08:00    H
…

Editing this file is the entire process for scheduling rounds. There’s no separate content repository, and there’s no longer an aspiration to swap content underneath a running site without telling the site about it. The builds tend to take less than 30 seconds, and the live site is swapped with only a few seconds of downtime:

Jenkins build times for the MkDocs-based APL Challenge

A huge improvement over the previous architecture:

Jenkins build times for the MiServer-based APL Challenge

The JSON5 test catalogue

Each round has a JSON5 file with members P1 through P10 describing how to test each problem. The format was inherited from the MiServer-based system; the test framework that consumes it has been completely rewritten. Here’s part of one:

{
    P1: {
        r:"^ *⍳ *\\d+",
        s:"⍳24",
    },
    …
    P7: {
        a: [
            "'HELLO'",
            "'DYALOG'",
            "'APL'",
            "{⍵[?≢⍵]}¨'AEIOU' 'BCDFGHJKLM' 'NPQRSTVWXYZ' 'AEIOU'",
        ],
        f: "{(2⊃⍵),(2⊃⌽⍵)}",
    },
    …
}

Problems 1–6 ask the participant to type one specific expression that produces one specific value, so the specification carries a reference solution s and a regex r that describes the acceptable solutions. Problems 7-10 ask for a function: the specification carries a reference function f, an array of test arguments a, and (optionally) a preprocessor p to apply before comparing the user’s result with the reference’s. Since the JSON5 strings are APL expressions, we can generate random tests as needed to prevent participants from hard-coding answers.

Submitting an answer

JavaScript included in the frontend makes the user’s browser POST [lang, problem, code, email] to the /Submit endpoint. First, we do some sanity checking:

 (rc msg)←req Submit(lang problem code email);anon;T
 lang ⎕C⍨←¯3
 :If ~lang⊂⍛∊##.⎕NL ¯9
     lang←'en'
 :EndIf
 T←lang∘Text
 :If 'Z'≡round
     (rc msg)←8(T'closed')
 :ElseIf ~problem⊂⍤,⍤⍕⍛∊⍕¨⍳10
     (rc msg)←8(T'badProbNo')
 :ElseIf 0∊∊' '=⊃0⍴⊂code
     (rc msg)←8(T'badCode')
 :OrIf 255<≢code←∊code
     (rc msg)←8(T'longCode')
 :ElseIf 0∊∊' '=⊃0⍴⊂email
     email←'^\s+|\s+$'⎕R''∊email
 :OrIf (''≢email)∧⍬≡'\S.*@.*\S'⎕S 3⊢email
 :OrIf email∊⍨⎕UCS 9
 :OrIf 254<≢email
     (rc msg)←¯8(T'badEmail')
 :Else
     …

We then test the submission and add an entry to the sub[mission]s and, if correct, wins database files:

     …
     (rc msg)←'data' 'problem' 'lang'⎕NS⍛Test code
     …
     ((unixtime:20 ⎕DT'Z' ⋄ code:'\t'⎕R'␉'⊢code)⎕NS'problem' 'rc')AppendTSV dbDir,'/subs.tsv'
     :If 0=rc
         req.Server.Log anon,' solved ',round,' problem ',problem
         :Hold 'wins'
             'email' 'problem' 'round'⎕NS⍛AppendTSV dbDir,'/wins.tsv'
         :EndHold
     :EndIf
 :EndIf

Responses consist of a return code and a message, ready for the frontend to render as a Material admonition:

Example admonition

The submission record uses two new Dyalog v20.0 features:

(unixtime:20 ⎕DT'Z' ⋄ code:'\t'⎕R'␉'⊢code)⎕NS'problem' 'rc'

The parenthesised expression is a namespace literal containing unixtime and code with their value expressions, and ⎕NS'problem' 'rc' amends the reference left argument (new!) with copies of those two variables. The result is a four-member namespace, ready to be appended as a TSV row. I chose to pass the row as a namespace rather than an ordered vector so that the table column order wouldn’t matter.

The test harness

Test is the largest function in the codebase (110 lines), but mostly consists of validation; the actual evaluation is short. The function begins with more usage of new Dyalog v20.0 features:

 (rc msg)←params Test code;…
 ⎕THIS ⎕NS params
 :Trap ⎕VGET⊂'debug' 0
     T←lang∘Text
     spec←data ⎕VGET⊂'P',problem
     …

⎕THIS ⎕NS params merges the entire params namespace into the current function’s scope, so data, problem, and lang (set up by the caller in Submit) are now ordinary local names with no params. qualifier required. data ⎕VGET⊂'debug' 0 decides whether to trap unexpected errors at the top level (during development, I set debug←1 from the session), and ⎕VGET then reads the specification for the requested problem out of the test data.

When initial validation is complete, the function proceeds based on the type of specification that was supplied (a regex-and-value check for problems 1-6, or a test-cases-and-function check for 7-10) and (after more specific validation) either runs the user’s code with ()⍎ (to run it in a separate namespace) or composes a small expression that wraps the user’s function and the reference function side-by-side and runs both in turn. (Debugging the generated expression is where inline tracing came in handy for me.) If the answers match, the frontend gets 0 'Your answer is correct. Good job!'. Otherwise the message tells them whether the answer was wrong, the methods used were wrong, the symbols used were wrong, or the code crashed.

Security is delivered by a safe character set, which stops glyphs that are dangerous (, , , ) or can lead to runaway execution (, , ):

safe←'+-×÷⌈⌊*⍟|!○~∨∧⍱⍲<≤=≥>≠.@≡≢⍴,⍪⍳↑↓?⍒⍋⍉⌽⊖∊⊥⊤⌹⊂⊃∪∩⍷⌷∘/⌿\⍀¨⍨⊆⍥⊣⊢⍤⌸⌺⍸()[];⋄:⍛⍬{}⍺⍵¯ '

This, together with limited memory, makes the new system light-weight enough that we can run it in the main thread, thus saving on thread juggling.

Authorisation as a one-liner

There are only two protected endpoints – Table for reading the TSVs, and Purge for deleting records – both for our own administrative use. (Participants don’t authenticate at all; an email goes in with each submission, the browser remembers it client-side, and that’s it. The worst that can happen is that I submit a correct answer with your email address, and that you then get a single notification email about having won a competition you haven’t heard of. Your email is then purged from our systems.) A single dfn, evaluated once for each protected request, is sufficient:

Authorised←{(⊂⍵.GetHeader'AuthToken')∊(⎕VGET⊂'authToken' '' ⋄ Env'AUTHTOKEN')~⊂''}

The valid token is whichever of the variable authToken (set manually for local testing) and the environment variable $AUTHTOKEN (set by Docker from a Jenkins credential) is non-empty. ⎕VGET returns its default of '' if authToken isn’t defined. The request’s AuthToken header is compared against the resulting list.

The “database”

The two storage tables are TSV files. They’re created at server start if they don’t exist. The combination of :For:In with multi-line array notation makes it easy to spot what goes where, whilst preventing the lines from getting too long:

 :For name head :In (
         'subs'('code' 'rc' 'problem' 'unixtime')
         'wins'('email' 'problem' 'round')
     )
     pathfile←dbDir,'/',name,'.tsv'
     :If ~⎕NEXISTS pathfile
         pathfile ⎕NPUT⍨[head ⋄ ]TSV''
     :EndIf
 :EndFor

[head ⋄ ] is array notation for a one-row matrix containing the row head – a header row. TSV is ⎕CSV with the separator pre-set to the Tab character and quotes disabled (Submit already protected us against Tab characters in the submission by replacing them with the Unicode control picture ):

 TSV←⎕CSV ⎕OPT('Separator'(⎕UCS 9) ⋄ 'QuoteChar' '')

subs.tsv contains code, rc, problem, and unixtime – every submission, with no email column. wins.tsv contains email, problem, and round – correct submissions only, with no code column and no timestamp. The two tables share no column that would let you join a participant’s email to the code they typed. We can produce statistics (“how many people solved problem 7 of round G?”), and we can email prize winners, but we can’t, even ourselves, look at a piece of submitted code and say which person wrote it. That’s deliberate.

Appending a record is a one-liner that takes a namespace whose names match the table’s columns, slots the values into a fresh row in the right column order, and asks ⎕NPUT to append (2):

 r←file 2 ⎕NPUT⍨[ns.⎕VGET⊃⌽(TSV ⎕OPT'Records' 1)file ⍬ 4 1 ⋄ ]TSV''

(TSV ⎕OPT'Records' 1)file ⍬ 4 1 reads only the header row (one record), and ns.⎕VGET then plucks the values out of the namespace in that order.

Reading a whole table for the administrative Table endpoint is:

 resp←0 ⎕JSON 1 ⎕JSON⊂2(TSV path ⍬ 4)

Here, we read the file then round-trip through ⎕JSON to leverage a dataset wrapper – introduced in Dyalog v19.0 – that transforms a table into a vector of namespaces. To see what’s happening, here is a sample wins table:

      wins←[
            'email'           'problem' 'round'
            'foo@example.com' 1         'A'
            'bar@example.com' 2         'B'
           ]
      1 ⎕JSON⊂2 wins
[{"email":"foo@example.com","problem":1,"round":"A"},{"email":"bar@example.com","problem":2,"round":"B"}]

Jarvis will respond with JSON data, but does the conversion from APL array for us, so we preempt the double-conversion with 0 ⎕JSON. Yes, it is unnecessary work, but it happens rarely enough not to matter, and even with the round-trip it is faster than the alternative, more-involved, ⊃{()⎕VSET(↑⍵)⍺}⍤1/TSV path ⍬ 4 1.

Behind the scenes with

Dyalog v20.0 introduced the new behind operator, . This uses the left operand to provide a left argument to the right operand:

  • X f⍛g Y is (f X) g Y
  • f⍛g Y is (f Y) g Y

This is a very common pattern, and across the 400-line backend appears over 30 times. Here are some of the representative uses:

New 'data' 'problem' 'lang'⎕NS⍛Test code Make Test take a list of names representing a namespace,
rather than taking a namespace reference
Old (⎕NS'data' 'problem' 'lang')Test code
New lang⊂⍛∊##.⎕NL ¯9 Make look for a single whole text,
rather than for each letter
Old (⊂lang)∊##.⎕NL ¯9
New mask~⍛/what / means “filter in”; “keep the indicated”
~⍛/ means “filter out”; “remove the indicated”
Old (~mask)/what
New (∨/spec.s∘∊)⍛/¨groups ⍛/ is a monadic filtering operator
f⍛/¨Y filters each element of Y by the predicate function f
Old ((∨/spec.s∘∊)¨groups)/¨groups

I especially like how allows me to extend the primitive vocabulary of APL by providing oft-needed variants of existing primitives; X⊂⍛∊Y and X~⍛/Y and f⍛/Y could easily have been primitives in their own right.

Internationalisation

Responses to submissions, including both success and failure messages, as well as reports about internal errors in the system (luckily, we’ve only had one minor error, and it was due to a mistake in the frontend), are sent as plain human-readable text together with a return code. The frontend renders it as a Material-style admonition with the colour and icon determined by the return code. English phrasings live in an array notation namespace in the file en.apla:

(
 and:'and'
 ansCorrect:'Your answer is correct. Good job!'
 ansErr:'Error<p>Your answer caused a'
 ansPass:'Your answer passed all tests. Good job!'
 arg:'argument'
 as:'as'
 badEmail:'Invalid email address'
 …
)

Jarvis loads .apla files together with the other application code. Now, you might have spotted the line :If ~lang⊂⍛∊##.⎕NL ¯9 and thought that this looks error-prone; surely, a malicious actor could issue a POST with the language set to the name of an unrelated namespace! Worry not; the line lang ⎕C⍨←¯3 makes sure only namespaces with entirely lowercase names are reachable as language packs, while all the system’s top-level namespaces begin with a capital letter. Phew, close!

Adding a new language to the backend consists of adding one file. Of course, the problem statements and informational pages will also need translation, but Material for MkDocs supports internationalisation by having a separate directory per language. I only recently finished composing all nine planned rounds of content, and want to harmonise them a bit more before we begin translating, but at least the wiring is there.

Looking back and forwards

The previous stack was a very useful test of the code and tools that we supply: it exercised our libraries, gave us bug reports against our own tools, and kept us using what we were selling. However, it also accumulated technical debt, and as the system evolved, the seams started to show.

The new stack also uses Dyalog technology (Jarvis, HttpCommand, Conga, and most of the newest language features) and these are really the things we’re selling today. It does so much more economically too: the whole thing runs on a single virtual CPU with 512 MB of RAM, whereas the old system used at least two virtual CPUs (more during peaks) with 1 GB of RAM each.

Have a look at Jarvis! It is really easy to get started. Here’s the bare minimum to get from a clear workspace to a running service with a good architecture in a folder /rot (replace with any other folder you want to use instead):

  1. Design your API: We’ll make it really simple; create a single function Rotate←{⊃⌽/⍵} in the workspace.
  2. Create the folder and function source file: ]Create # /rot
  3. Create the Jarvis configuration file: The easiest is ]Repr (CodeLocation:'.' ⋄ HTMLInterface:'.' ⋄ IncludeFns:'Rotate') -f=json -o=/rot/jarvis.json
  4. Create the HTML interface: Here’s one with two input fields, a button, and the minimal JavaScript needed to make the button work:
    <!DOCTYPE html>
    <html>
      <head>
        <title>Jarvis Text Rotator</title>
        <script>
          Exec=()=>{
            fetch("/Rotate",{
              method:"POST",
              headers:{"content-type":"application/json; charset=utf-8"},
              body:JSON.stringify([steps.valueAsNumber, text.value])
            }).then(r=>r.json()).then(d=>out.innerHTML=d)
          }
        </script>
      </head>
      <body>
        <input id=steps placeholder=Steps type=number>
        <button onclick=Exec()>⌽</button>
        <input id=text placeholder=Text>
        <br>
        <output id=out></output>
      </body>
    </html>

    Save this text to /rot/index.html.

  5. Get Jarvis: ]Get github.com/Dyalog/Jarvis/blob/master/Source/Jarvis.dyalog
  6. Start the server: Jarvis.Run'/rot/jarvis.json'
  7. Try it: Open localhost:8080 in your browser, fill in the fields, and click the button!

Try HttpCommand, too! While the above server is running, we can easily use it as a micro-service, bypassing the HTML frontend:

  1. Get HttpCommand: ]Get HttpCommand
  2. Issue the command: resp←HttpCommand.GetJSON'POST' 'localhost:8080/Rotate' (2 'Hello')
  3. Inspect the response: resp.Data – this will give the character vector 'lloHe'

If you’ve made it all the way to here, congratulations! Don’t forget to promote the APL Challenge and the APL Forge – they are available year-round!

D’Hondt Apportionment Made Easy with APL

Today, the UK is holding elections for local councillors in England, and members of the devolved parliaments in Scotland and Wales. Until a political party starts pushing for mandatory APL lessons, we’re not interested in the results of these elections for this blog post. What we are interested in is algorithms, and, for the first time, the elections to the Welsh Parliament (usually referred to as the Welsh ‘Senedd’) used the D’Hondt method for allocating seats.

The D’Hondt method is named after Belgian mathematician and lawyer Victor D’Hondt, although it was independently invented by United States Founding Father Thomas Jefferson almost a century earlier! The method transforms a vote count for a number of political parties into an approximately proportional allocation of seats to each of the parties. Therefore, unlike in previous Senedd elections, Welsh voters do not have individual representatives on their ballots. Instead, they each vote for one political party. The parties then send as many representatives to the Senedd as they are allocated by the D’Hondt method.

With the D’Hondt method, seats are allocated to parties one-by-one. When each seat is allocated, it is given to the party with the largest vote count relative to the number of seats they have already been given. This way, more popular parties are given seats first, but when they have several already, a seat goes to a smaller party so that it is also represented.

This means that, when allocating a seat, the ‘quotient’ votes÷(seats+1) is calculated for each party, where votes is the number of votes the party received, and seats is the number of seats they have been allocated so far. The +1 is included to avoid division by zero. The party with the largest quotient is allocated the seat, and the process is repeated until all seats have been allocated.

Let’s implement this in APL. Given a vector votes and a vector seats, with each index corresponding to a political party, the index of the party with the greatest quotient can be found as follows:

      i←⊃⍒votes÷seats+1

The grade down of the quotient returns the indices to sort the quotients in descending order. Therefore, the first of these indices will be the index of the greatest quotient – exactly what the algorithm calls for.

We then need to update seats to give a seat to this lucky party. There’s more than one way to do this, but I’ll take a functional approach and use the at operator (@) to add 1 ‘at’ the index of party i:

      1(+@i)seats

This can be wrapped in a dfn, in which is the votes vector and is the current seat allocation.

      Step←{
          i←⊃⍒⍺÷⍵+1
          1(+@i)⍵
      }

To allocate, say, fifty seats, the Step function should be applied 50 times on successive seat allocations – an ideal use-case for the power operator (). Let’s try it with a hypothetical vote share of 4:3:2 for three parties:

      4000 3000 2000 (Step⍣50) 0 0 0
22 17 11

That’s a ratio of around 4:3.1:2 – a good approximation of the original vote-share!

It’s easier to visualise the behaviour of the D’Hondt method over time by considering just two parties. Let’s call them Party A and Party B. Suppose that these parties received 12,345 and 6,789 votes respectively, and share a 50 seat parliament.

      12345 6789 (Step⍣50) 0 0
32 18

Party A is allocated 32 seats, while party B is allocated 18. This ratio is, again, reasonably close to that of the votes:

      12345÷6789  ⍝ vote ratio
1.818382678
      32÷18       ⍝ seat ratio
1.777777778

Let’s see how this ratio changes with each step. By modifying the Step function, we can record the intermediate seat allocations. is now a matrix with a row for the seat allocation after each step. The most recent allocation is extracted with ⊢⌿, which is an idiom for the last row of a matrix. The function must now be called with an initial value of [0 0⋄], which is a one-row matrix of two zeros expressed using array notation.

      Step←{
          seats←⊢⌿⍵
          i←⊃⍒⍺÷seats+1
          ⍵⍪1(+@i)seats
      }
      12345 6789 (Step⍣50) [0 0⋄]
 0  0
 1  0
 1  1
 2  1
 3  1
 3  2
 4  2
 5  2
...

We can now plot the ratio (the ÷/ of this result matrix, on the vertical axis) against the step of the method (on the horizontal axis). The ratio after each step is drawn as an orange dot, and the perfect ratio which the method is approaching is drawn by the lavender line.

We can see the ratio converging to the ratio of the votes. The really interesting question is why. I won’t give a formal proof here, that’s one for mathematicians and political scientists to write about. I will, however, show you how I understand it.

It’s interesting to look at a plot of the seat allocation given by the D’Hondt method alongside a ‘perfect’ allocation where we are allowed fractional seats. The vertical axis corresponds to seats allocated to party A, and the horizontal axis corresponds to seats allocated to party B. The trace of seat allocations is drawn as an orange line in the shape of a staircase, and the line of perfect allocation is drawn as a straight lavender line.

At each step, the D’Hondt method (usually) moves towards, and subsequently crosses, the line of perfect allocation. When an allocation is above the line, Party A has ‘too many’ seats, giving it a smaller quotient. The method then allocates a seat to Party B to correct for this, corresponding to the rightward move on the plot. The opposite also applies – when the allocation is below the line, Party B has the smaller quotient, and the method moves the allocation vertically.

There are exceptions to this pattern – cases where the allocation moves away from the line of perfect allocation. This is because of the “fudge factor” +1 on the seat count. This imaginary extra seat for each party can skew the allocation decision occasionally. From my limited reading, it looks like this is a known behaviour of the D’Hondt method, and is deliberately retained.

By ‘hugging’ the perfect allocation like this, the D’Hondt method stays within a few seats of being perfectly proportional. As the number of seats increases, this error is relatively smaller, so the accuracy of the method increases.

This is how the D’Hondt method allocates seats at a ratio close to the ratio of votes, and gets better as there are more seats available.

Irrespective of whether you’re Welsh, I hope it was interesting to explore the D’Hondt method for apportionment with APL!

Towards Improvements to Stencil

Background

The stencil operator was introduced in Dyalog version 16.0 in 2017. Recently we received some feedback (OK, complaints) that (a) stencil does padding which is unwanted sometimes and needs to be removed from the result and (b) stencil is too slow when it is not supported by special code.

First, stencil in cases supported by special code is much faster than when it is not. The special cases are as follows, from Dyalog ’17 Workshop SA3.

   {⍵}      {⊢⍵}      {,⍵}      {⊂⍵}
{+/,⍵}    {∧/,⍵}    {∨/,⍵}    {=/,⍵}    {≠/,⍵}  
    
{  +/,A×⍵}    {  +/⍪A×⍤2⊢⍵}
{C<+/,A×⍵}    {C<+/⍪A×⍤2⊢⍵}
C:  a single number or variable whose value is a single number
A:  a variable whose value is a rank-2 or 3 array
The comparison can be < ≤ ≥ > = ≠
odd window size; movement 1; matrix argument
 

You can test whether a particular case is supported by using a circumlocution to defeat the special case recognizer.

   )copy dfns cmpx

   cmpx '{⍵}⌺3 5⊢y' '{⊢⊢⍵}⌺3 5⊢y' ⊣ y←?100 200⍴0
  {⍵}⌺3 5⊢x   → 4.22E¯4 |      0%                               
  {⊢⊢⍵}⌺3 5⊢x → 5.31E¯2 | +12477% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

   cmpx '{⌽⍵}⌺3 5⊢y' '{⊢⊢⌽⍵}⌺3 5⊢y'
  {⌽⍵}⌺3 5⊢y   → 2.17E¯1 |  0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  {⊢⊢⌽⍵}⌺3 5⊢y → 2.21E¯1 | +1% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

If the timings are the same then there is no special code.

Padding and performance improvements will take a lot of work. For example, for padding (i.e. the treatment of cells at the edge of the universe) multiple options are possible: no padding, padding, wrap from opposite edge, etc. While working on these improvements I hit upon the idea of writing a stencil function which produces the stencil cells. It only works with no padding and only for movements of 1 (which I understand are common cases), but turns out to be an interesting study.

A Stencil Function

⍺ stencell ⍵ produces the stencil cells of size from  , and is equivalent to {⍵}⌺⍺⊢⍵ after the padded cells are removed.

stencell←{
  ⎕io←0                 ⍝ ⎕io delenda est!
  s←(≢⍺)↑⍴⍵
  f←1+s-⍺               ⍝ frame AKA outer shape
  m←⊖×⍀⊖1↓s,1           ⍝ multiplier for each axis
  i←⊃∘.+⌿(m,m)×⍳¨f,⍺    ⍝ indices
  (⊂i) ⌷ ⍵ ⍴⍨ (×⌿(≢⍺)↑⍴⍵),(≢⍺)↓⍴⍵
}

For example, stencell is applied to x with cell shape 3 5 .

   ⊢ x←6 10⍴⍳60                    ⍝ (a)
 0  1  2  3  4  5  6  7  8  9
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29
30 31 32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47 48 49
50 51 52 53 54 55 56 57 58 59

   c←3 5 stencell x                ⍝ (b)
   ⍴c
4 6 3 5

   c ≡ 1 2 ↓ ¯1 ¯2 ↓ {⍵}⌺3 5 ⊢x    ⍝ (c)
1

   ⊢ e←⊂⍤2 ⊢c                      ⍝ (d)
┌──────────────┬──────────────┬──────────────┬──────────────┬──────────────┬──────────────┐
│ 0  1  2  3  4│ 1  2  3  4  5│ 2  3  4  5  6│ 3  4  5  6  7│ 4  5  6  7  8│ 5  6  7  8  9│
│10 11 12 13 14│11 12 13 14 15│12 13 14 15 16│13 14 15 16 17│14 15 16 17 18│15 16 17 18 19│
│20 21 22 23 24│21 22 23 24 25│22 23 24 25 26│23 24 25 26 27│24 25 26 27 28│25 26 27 28 29│
├──────────────┼──────────────┼──────────────┼──────────────┼──────────────┼──────────────┤
│10 11 12 13 14│11 12 13 14 15│12 13 14 15 16│13 14 15 16 17│14 15 16 17 18│15 16 17 18 19│
│20 21 22 23 24│21 22 23 24 25│22 23 24 25 26│23 24 25 26 27│24 25 26 27 28│25 26 27 28 29│
│30 31 32 33 34│31 32 33 34 35│32 33 34 35 36│33 34 35 36 37│34 35 36 37 38│35 36 37 38 39│
├──────────────┼──────────────┼──────────────┼──────────────┼──────────────┼──────────────┤
│20 21 22 23 24│21 22 23 24 25│22 23 24 25 26│23 24 25 26 27│24 25 26 27 28│25 26 27 28 29│
│30 31 32 33 34│31 32 33 34 35│32 33 34 35 36│33 34 35 36 37│34 35 36 37 38│35 36 37 38 39│
│40 41 42 43 44│41 42 43 44 45│42 43 44 45 46│43 44 45 46 47│44 45 46 47 48│45 46 47 48 49│
├──────────────┼──────────────┼──────────────┼──────────────┼──────────────┼──────────────┤
│30 31 32 33 34│31 32 33 34 35│32 33 34 35 36│33 34 35 36 37│34 35 36 37 38│35 36 37 38 39│
│40 41 42 43 44│41 42 43 44 45│42 43 44 45 46│43 44 45 46 47│44 45 46 47 48│45 46 47 48 49│
│50 51 52 53 54│51 52 53 54 55│52 53 54 55 56│53 54 55 56 57│54 55 56 57 58│55 56 57 58 59│
└──────────────┴──────────────┴──────────────┴──────────────┴──────────────┴──────────────┘

    ∪¨ ,¨ e-⍬⍴e                    ⍝ (e)
┌──┬──┬──┬──┬──┬──┐
│0 │1 │2 │3 │4 │5 │
├──┼──┼──┼──┼──┼──┤
│10│11│12│13│14│15│
├──┼──┼──┼──┼──┼──┤
│20│21│22│23│24│25│
├──┼──┼──┼──┼──┼──┤
│30│31│32│33│34│35│
└──┴──┴──┴──┴──┴──┘
(a)  The matrix x is chosen to make stencil results easier to understand.
(b) stencell is applied to x with cell shape 3 5 .
(c) The result of stencell is the same as that for {⍵}⌺ after cells with padding are dropped.
(d) Enclose the matrices in c (the cells) to make the display more compact and easier to understand.
(e) Subsequent discussion is based on the observation that each cell is some scalar integer added to the first cell.

Indices

The key expression in the computation is

   ⊃∘.+⌿(m,m)×⍳¨f,⍺ 

where

   m:  10 1;  multiplier for each axis
   f:  4 6;  multiplier for each axis
   ⍺:  3 5;  multiplier for each axis
 

We discuss a more verbose but equivalent version of this expression,

   (⊃∘.+⌿m×⍳¨f)∘.+(⊃∘.+⌿m×⍳¨⍺)

and in particular the right half, ⊃∘.+⌿m×⍳¨⍺ , which produces the first cell.

   ⍳⍺               ⍝ ⍳3 5
┌───┬───┬───┬───┬───┐
│0 0│0 1│0 2│0 3│0 4│
├───┼───┼───┼───┼───┤
│1 0│1 1│1 2│1 3│1 4│
├───┼───┼───┼───┼───┤
│2 0│2 1│2 2│2 3│2 4│
└───┴───┴───┴───┴───┘
   (⍴⍵)∘⊥¨⍳⍺        ⍝ 6 10∘⊥¨ ⍳3 5
 0  1  2  3  4
10 11 12 13 14
20 21 22 23 24

Alternatively, this last result obtains by multiplying by m the corresponding indices for each axis, where an element of m is the increment for a unit in an axis. That is, m←⊖×⍀⊖1↓s,1 where s←(≢⍺)↑⍴⍵ is a prefix of the shape of  . The multipliers are with respect to the argument because the indices are required to be with respect to the argument  .

   ⍳¨⍺              ⍝ ⍳¨3 5
┌─────┬─────────┐
│0 1 2│0 1 2 3 4│
└─────┴─────────┘
   m×⍳¨⍺            ⍝ 10 1×⍳¨3 5
┌───────┬─────────┐
│0 10 20│0 1 2 3 4│
└───────┴─────────┘
   ∘.+⌿ m×⍳¨⍺       ⍝ ∘.+⌿ 10 1×⍳¨3 5
┌──────────────┐
│ 0  1  2  3  4│
│10 11 12 13 14│
│20 21 22 23 24│
└──────────────┘
   ((⍴⍵)∘⊥¨⍳⍺) ≡ ⊃∘.+⌿m×⍳¨⍺
1

This alternative computation is more efficient because it avoids creating and working on lots of small nested vectors and because the intermediate results for ∘.+⌿ grows fast from one to the next (i.e., O(⍟n) iterations in the main loop).

The left half, ⊃∘.+⌿m×⍳¨f , is similar, and computes the necessary scalar integers to be added to the result of the right half.

   ⊃ ∘.+⌿ m×⍳¨f     ⍝ ⊃ ∘.+⌿ 10 1×⍳¨4 6
 0  1  2  3  4  5
10 11 12 13 14 15
20 21 22 23 24 25
30 31 32 33 34 35

The shorter expression derives from the more verbose one by some simple algebra.

(⊃∘.+⌿m×⍳¨f)∘.+(⊃∘.+⌿m×⍳¨⍺)    ⍝ verbose version
⊃∘.+⌿(m×⍳¨f),m×⍳¨⍺             ⍝ ∘.+ is associative
⊃∘.+⌿(m,m)×(⍳¨f),⍳¨⍺           ⍝ m× distributes over ,
⊃∘.+⌿(m,m)×⍳¨f,⍺               ⍝ ⍳¨ distributes over ,

I am actually disappointed that the shorter expression was found ☺; it would have been amusing to have a non-contrived and short expression with three uses of ∘.+ .

Cells

Having the indices i in hand, the stencil cells obtain by indexing into an appropriate reshape or ravel of the right argument  . In general, the expression is

   (⊂i) ⌷ ⍵ ⍴⍨ (×/(≢⍺)↑⍴⍵),(≢⍺)↓⍴⍵

specifies the cell shape. If (≢⍺)=≢⍴⍵ , that is, if a length is specified for each axis of  , the expression is equivalent to (⊂i)⌷,⍵ or (,⍵)[i] ; if (≢⍺)<≢⍴⍵ , that is, if there are some trailing unstencilled axes, the expression is equivalent to (,[⍳≢⍺]⍵)[i;…;] (the leading ≢⍺ axes are ravelled) or ↑(,⊂⍤((≢⍴⍵)-≢⍺)⊢⍵)[i] (as if the trailing axes were shielded from indexing). The general expression covers both cases.

Application

stencell makes it possible to workaround current shortcomings in . The alternative approach is to use stencell to get all the stencil cells, all at once, and then work on the cells using  , +.× , and
other efficient primitives.

The following example is from Aaron Hsu. In the original problem the size of x is 512 512 64 .

   K←?64 3 3 64⍴0
   x←?256 256 64⍴0

   t←1 1↓¯1 ¯1↓{+/⍪K×⍤3⊢⍵}⌺3 3⊢x
   ⍴t
256 256 64

   cmpx '1 1↓¯1 ¯1↓{+/⍪K×⍤3⊢⍵}⌺3 3⊢x'
6.76E0 

The computation is slow because the cells are rank-3, not supported by special code. Aaron then devised a significant speed-up using a simpler left operand to create the ravels of the cells (but still no special code):

   t ≡ (1 1↓¯1 ¯1↓{,⍵}⌺3 3⊢x)+.×⍉⍪K
1
   cmpx '(1 1↓¯1 ¯1↓{,⍵}⌺3 3⊢x)+.×⍉⍪K'
1.67E0 

Use of stencell would improve the performance a bit further:

   t ≡ (,⍤3 ⊢3 3 stencell x)+.×⍉⍪K
1
   cmpx '(,⍤3 ⊢3 3 stencell x)+.×⍉⍪K'
1.09E0 

   cmpx '3 3 stencell x'
6.10E¯2

The last timing shows that the stencell computation is 6% (6.10e¯2÷1.09e0) of the total time.

Materializing all the cells does take more space than if the computation is incorporated in the left operand of  , and is practicable only if the workspace sufficiently large.

   )copy dfns wsreq

   wsreq '1 1↓¯1 ¯1↓{+/⍪K×⍤3⊢⍵}⌺3 3⊢x'
110649900
   wsreq '(1 1↓¯1 ¯1↓{,⍵}⌺3 3⊢x)+.×⍉⍪K'
647815900
   wsreq '(,⍤3 ⊢3 3 stencell x)+.×⍉⍪K'
333462260

Performance

stencell is competitive with {⍵}⌺ on matrices, where it is supported by special code written in C, and is faster when there is no special code. The benchmarks are done on a larger argument to reduce the effects of padding/unpadding done in {⍵}⌺ .

   y2←?200 300⍴0
          
   cmpx '3 5 stencell y2' '1 2↓¯1 ¯2↓{⍵}⌺3 5⊢y2' 
  3 5 stencell y      → 1.85E¯3 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕           
  1 2↓¯1 ¯2↓{⍵}⌺3 5⊢y → 2.91E¯3 | +57% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

   cmpx '3 5 stencell y' '{⍵}⌺3 5⊢y' 
  3 5 stencell y → 1.85E¯3 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
* {⍵}⌺3 5⊢y      → 1.04E¯3 | -45% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕             

   y3←?200 300 64⍴0

   cmpx '3 5 stencell y3' '1 2↓¯1 ¯2↓{⍵}⌺3 5⊢y3' 
  3 5 stencell y3      → 8.90E¯2 |    0% ⎕⎕⎕                           
  1 2↓¯1 ¯2↓{⍵}⌺3 5⊢y3 → 7.78E¯1 | +773% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

   cmpx '3 5 stencell y3' '{⍵}⌺3 5⊢y3' 
  3 5 stencell y3 → 9.38E¯2 |    0% ⎕⎕⎕⎕⎕⎕⎕⎕                      
* {⍵}⌺3 5⊢y3      → 3.34E¯1 | +256% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

There is an interesting question of whether the shorter version of the key computation (in the Indices section above) is faster than the more verbose version.

   m←10 1 ⋄ f←4 6 ⋄ a←3 5

   cmpx '⊃∘.+⌿(m,m)×⍳¨f,a' '(⊃∘.+⌿m×⍳¨f)∘.+(⊃∘.+⌿m×⍳¨a)'
  ⊃∘.+⌿(m,m)×⍳¨f,a            → 3.75E¯6 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  (⊃∘.+⌿m×⍳¨f)∘.+(⊃∘.+⌿m×⍳¨a) → 5.20E¯6 | +38% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

In this case, it is faster, and I expect it will be faster for cases which arise in stencil calculations, where the argument size is larger than the cell size. But it is easy to think of arguments where ∘.+⌿ is slower than ∘.+ done with a different grouping:

   cmpx '((⍳0)∘.+⍳100)∘.+⍳200' '(⍳0)∘.+((⍳100)∘.+⍳200)' '⊃∘.+/⍳¨0 100 200'
  ((⍳0)∘.+⍳100)∘.+⍳200   → 7.86E¯7 |     0% ⎕⎕                            
  (⍳0)∘.+((⍳100)∘.+⍳200) → 1.05E¯5 | +1234% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕  
  ⊃∘.+/⍳¨0 100 200       → 1.11E¯5 | +1310% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

This question will be explored further in a later post.

Ascending and Descending

Lexicographic Ordering

Lexicographic ordering is what the APL primitives and provide:

   ⎕io←0     ⍝ ⎕io delenda est
   ⎕rl←7*5   ⍝ to get reproducible random results

   a←?11 3⍴3

   a          a ⌷⍨⊂ ⍋a
2 1 0      0 1 0
0 2 2      0 2 2
1 1 1      1 0 0
1 0 0      1 0 1
1 1 1      1 0 1
1 2 1      1 1 0
1 0 1      1 1 1
1 0 1      1 1 1
1 1 0      1 2 1
0 1 0      1 2 2
1 2 2      2 1 0

First order by column 0, resulting in groups of rows with the same values in column 0. Then, within each group, order by column 1, getting subgroups with the same values in columns 0 and 1. Then, within each subgroup, order by column 2, getting subsubgroups with the same values in columns 0, 1, and 2. In general, for each subsub…subgroup, order by column k, getting groups with identical values in columns ⍳k.

The preceding discourse is descriptive rather than prescriptive—algorithms for can use more efficient and more straightforward approaches. As well, for ease of understanding, the description is for a matrix and speaks of columns and rows. In general, any non-scalar array can be ordered, whence instead of rows, think major cells, instead of column, think item in a major cell. Symbolically and more succinctly, ⍋⍵ ←→ ⍋⍪⍵.

can be used if the orderings in the process are all ascending, or if all descending. The problem to be solved here is where the orderings are a mix of ascending and descending.

Numeric Arrays

Since ⍒⍵ ←→ ⍋-⍵ if is numeric, for such multiply each descending column by ¯1 and each ascending column by 1, then apply . This induces a “control array” having the same shape as a major cell of the argument, with a ¯1 for descending and a 1 for ascending.

   adn←{⍵ ⌷⍨⊂ ⍋ ⍺ ×⍤99 ¯1 ⊢⍵}

For the array a in the previous section:

   a              1 ¯1 1 adn a        ¯1 1 1 adn a
2 1 0          0 2 2               2 1 0  
0 2 2          0 1 0               1 0 0  
1 1 1          1 2 1               1 0 1  
1 0 0          1 2 2               1 0 1  
1 1 1          1 1 0               1 1 0  
1 2 1          1 1 1               1 1 1  
1 0 1          1 1 1               1 1 1  
1 0 1          1 0 0               1 2 1  
1 1 0          1 0 1               1 2 2  
0 1 0          1 0 1               0 1 0  
1 2 2          2 1 0               0 2 2  

In 1 ¯1 1 adn a, column 0 is ascending, and within that, column 1 is descending, and within that, column 2 is ascending. In ¯1 1 1 adn a, column 0 is descending, and within that, column 1 is ascending, and within that, column 2 is ascending.

Ordinals

An array to be sorted can be converted to an order-equivalent integer array by assigning to each item an ordinal (an integer) which has the same ordering relationship as the original item relative to other items in the array:

   sort    ← {(⊂⍋⍵)⌷⍵}
   ordinal ← {⎕ct←0 ⋄ ⍵⍳⍨sort,⍵}

That is, the ordinals obtain as the indices of the original array in the sorted list of the ravelled elements, using exact comparisons. (Exact comparisons are used because sorting necessarily uses exact comparisons.)
For example:

   ⊢ d←¯1 'syzygy' (3 ¯5) 1j2 'chthonic' (¯1)
┌──┬──────┬────┬───┬────────┬──┐
│¯1│syzygy│3 ¯5│1J2│chthonic│¯1│
└──┴──────┴────┴───┴────────┴──┘
   ordinal d
0 5 3 2 4 0

In the example, the data items are ¯1, 'syzygy', 'chthonic', 3 ¯5, 1j2, and ¯1 again. With respect to ordering, these data items are perfectly represented by the ordinals (numbers) 0, 5, 3, 2, 4, and 0, respectively. That is, ⍋d ←→ ⍋ordinal d.

   ⍋ d
0 5 3 2 4 1
   ⍋ ordinal d
0 5 3 2 4 1

As the example illustrates, it is imperative that identical ordinals are assigned to identical items, else the ordering relationships would be changed. For example, if b←0,⍪2 1 and the 0s are assigned different ordinals,

   ⊢ b←0,⍪2 1               
0 2
0 1
   ordinal b                 ⊢ bo←0 3,⍪1 2  ⍝ faux ordinals
0 3                       0 3
0 2                       1 2
   ⍋ ordinal b               ⍋ bo
1 0                       0 1
   ⍋ b
1 0

Computation of ordinals is greatly facilitated by the total array ordering introduced in Dyalog APL version 17.0.

Non-Numeric Arrays

A general solution for the ordering problem obtains by first converting the array to an order-equivalent integer array through the use of ordinals.

   ado ← {⍵ ⌷⍨⊂ ⍋ ⍺ ×⍤99 ¯1 ordinal ⍵}

For example:

   ⎕rl←7*5   ⍝ to get reproducible random results

   x0← ?19⍴4                            
   x1← (⊂?19⍴2) ⌷ 'alpha' 'beta'          
   x2← (⊂?19⍴3) ⌷ 'abc'                   
   x3← (⊂?19⍴3) ⌷ 'able' 'baker' 'charlie'

   x ← x0,x1,x2,⍪x3

   ordinal x
13 49 19 42
10 49 32 68
13 49 63 68
 4 49 63 42
 0 27 19 23
13 49 32 42
 0 49 19 42
10 49 32 68
10 27 32 23
 4 49 32 68
 4 49 32 68
 4 27 32 23
 4 49 32 68
 0 49 63 68
13 49 63 68
 0 49 32 42
13 27 32 23
 4 27 63 42
13 49 19 42

   (⍋x) ≡ ⍋ ordinal x
1

Suppose x is to be sorted ascending in columns 0 and 2 and descending in columns 1 and 3. The control array is 1 ¯1 1 ¯1, and:

   x                       1 ¯1 1 ¯1 ado x
┌─┬─────┬─┬───────┐     ┌─┬─────┬─┬───────┐
│2│beta │b│baker  │     │0│beta │a│able   │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│3│alpha│a│able   │     │0│beta │b│charlie│
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│3│beta │b│able   │     │0│beta │b│baker  │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│3│alpha│b│baker  │     │0│beta │c│charlie│
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│1│beta │b│charlie│     │0│beta │c│able   │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│1│beta │a│baker  │     │0│alpha│c│baker  │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│0│beta │c│charlie│     │1│beta │a│baker  │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│0│beta │b│baker  │     │1│beta │b│charlie│
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│0│beta │c│able   │     │1│alpha│c│able   │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│0│beta │a│able   │     │2│beta │a│baker  │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│3│alpha│a│baker  │     │2│beta │b│baker  │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│3│alpha│a│baker  │     │3│beta │b│able   │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│1│alpha│c│able   │     │3│beta │b│able   │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│0│beta │b│charlie│     │3│beta │c│charlie│
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│0│alpha│c│baker  │     │3│alpha│a│baker  │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│3│beta │b│able   │     │3│alpha│a│baker  │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│2│beta │a│baker  │     │3│alpha│a│able   │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│3│beta │c│charlie│     │3│alpha│a│able   │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│3│alpha│a│able   │     │3│alpha│b│baker  │
└─┴─────┴─┴───────┘     └─┴─────┴─┴───────┘

Finally

   (ordinal x) ≡ ordinal ordinal x
1

That is, ordinal is idempotent. Actually, this is kind of obvious, but I never miss an opportunity to use the word “idempotent”.☺

Krypto

In the 2016 Year Game, the task was to generate the numbers 0 to 100 using APL primitives and the digits 2 0 1 6 in that order. For example,

   20=16
   ×2016
   2⌊016
   2+×016
   …

This “puzzle of the year” brings to mind Krypto, a game I played many years ago while in grade school.

Krypto

Krypto is a mathematical card game. The Krypto deck has 56 cards: 3 each of numbers 1-6, 4 each of the numbers 7-10, 2 each of 11-17, 1 each of 18-25.

   ⎕io←0
   DECK ← (3/1+⍳6),(4/7+⍳4),(2/11+⍳7),18+⍳8

Six cards are dealt: an objective card and five other cards. A player must use all five of the latter cards’ numbers exactly once, using any combination of arithmetic operations (+, -, ×, and ÷) to form the objective card’s number. The first player to come up with a correct formula is the winner. The stricter “International Rules” specify the use of non-negative integers only; fractional or negative intermediate results are not permitted.

For example, if the objective card were 17 and the other cards were 2, 8, 14, 19, and 21, then a Krypto solution can be as follows. Without loss of generality, we use APL notation and syntax.

   8 - 19 + 14 - 2 × 21

In this article we present functions to find all solutions to a Krypto hand.

A Solution

There are a maximum of !5 permutations of the 5 cards and 4 possibilities in each of the 4 places where an operation can be put, for (!5)×4*4 or 30720 total possibilities. This number is small enough for an exhaustive approach.

deal←{DECK ⌷⍨⊂ 6?≢DECK}

Krypto←{
  perm←{0=⍵:1 0⍴0 ⋄ ,[⍳2](⊂0,1+∇ ¯1+⍵)⌷⍤1⍒⍤1∘.=⍨⍳⍵}
  a←256⌿5 0⍕⍵[perm 5]
  a[;6+5×⍳4]←'+-×÷'[((256×!5),4)⍴⍉(4⍴4)⊤⍳256]
  ⊣⌸ a ⌿⍨ ⍺ = ⍎⍤1 ⊢a
}

   deal ⍬
17 8 19 14 2 21

   ⊢ t← 17 Krypto 8 19 14 2 21
    8 - 19 + 14 -  2 × 21
    8 - 19 + 14 - 21 ×  2
    8 - 19 - 21 + 14 ÷  2
    8 - 14 + 19 -  2 × 21
        ...
   21 +  8 - 19 - 14 ÷  2
   21 - 19 -  8 + 14 ÷  2

   ⍴ t
24 25

Intermediate Steps

The function perm is from the Dyalog blog post Permutations, 2015-07-20. perm n generates the sorted table of all permutations of ⍳n.

The local variable a in Krypto is a 30720-row character matrix computed from the 5 non-objective numbers. It consists of all !5 permutations of the 5 numbers interspersed with all 4*4 arrangements of the four operations + - × ÷.

Executing the rows of a produces a 30720-element numeric vector. Comparison of this vector with the objective yields a boolean vector that selects the rows of a which are correct formulas.

   ⍴ a
30720 25

   8↑a
    8 + 19 + 14 +  2 + 21
    8 + 19 + 14 +  2 - 21
    8 + 19 + 14 +  2 × 21
    8 + 19 + 14 +  2 ÷ 21
    8 + 19 + 14 -  2 + 21
    8 + 19 + 14 -  2 - 21
    8 + 19 + 14 -  2 × 21
    8 + 19 + 14 -  2 ÷ 21
   ¯5↑a
   21 ÷  2 ÷ 14 × 19 ÷  8
   21 ÷  2 ÷ 14 ÷ 19 +  8
   21 ÷  2 ÷ 14 ÷ 19 -  8
   21 ÷  2 ÷ 14 ÷ 19 ×  8
   21 ÷  2 ÷ 14 ÷ 19 ÷  8

   +/ b ← 17 = ⍎⍤1 ⊢a
24

   t ≡ b⌿a
1

We note that use of the @ operator, new to Dyalog version 16.0, obviates the need to name intermediate results for reasons for syntax. Instead, names are only used to break the code down into more comprehensible components.

Krypto1←{
  perm←{0=⍵:1 0⍴0 ⋄ ,[⍳2](⊂0,1+∇ ¯1+⍵)⌷⍤1⍒⍤1∘.=⍨⍳⍵}
  ⊣⌸ ⍺ (⊢(⌿⍨)=∘(⍎⍤1)) '+-×÷'[((256×!5),4)⍴⍉(4⍴4)⊤⍳256]⊣@(6+5×⍳4)⍤1 ⊢256⌿5 0⍕⍵[perm 5]
}

Krypto2←{
  perm←{0=⍵:1 0⍴0 ⋄ ,[⍳2](⊂0,1+∇ ¯1+⍵)⌷⍤1⍒⍤1∘.=⍨⍳⍵}
  fns  ← '+-×÷'[((256×!5),4)⍴⍉(4⍴4)⊤⍳256]
  nums ← 256⌿5 0⍕⍵[perm 5]
  ⊣⌸ ⍺ (⊢(⌿⍨)=∘(⍎⍤1)) fns ⊣@(6+5×⍳4)⍤1 ⊢nums
}

   17 (Krypto ≡ Krypto1) 8 19 14 2 21
1

   17 (Krypto ≡ Krypto2) 8 19 14 2 21
1

International Rules

The international rules (intermediate results must be non-negative integers) can be enforced readily:

irules←{⍵⌿⍨∧/(i=⌊i)∧0≤i←8 13 18{⍎¨⍺↓¨⊂⍵}⍤1⊢⍵}

   irules 17 Krypto 8 19 14 2 21
    8 +  2 + 14 ÷ 21 - 19
    8 + 21 - 19 - 14 ÷  2
   19 -  2 ×  8 - 21 - 14
   19 -  2 ÷  8 - 21 - 14
   19 -  2 × 14 - 21 -  8
   19 -  2 ÷ 14 - 21 -  8
    2 +  8 + 14 ÷ 21 - 19
   21 - 19 -  8 + 14 ÷  2

It is instructive to look at how the local variable i in irules is formed:

   ⊢ t←17 Krypto 8 19 14 2 21
    8 - 19 + 14 -  2 × 21
    8 - 19 + 14 - 21 ×  2
    8 - 19 - 21 + 14 ÷  2
    8 - 14 + 19 -  2 × 21
        ...
   21 +  8 - 19 - 14 ÷  2
   21 - 19 -  8 + 14 ÷  2

   8 13 18 {⍺↓¨⊂⍵}⍤1 ⊢t
┌─────────────────┬────────────┬───────┐
│19 + 14 -  2 × 21│14 -  2 × 21│ 2 × 21│
├─────────────────┼────────────┼───────┤
│19 + 14 - 21 ×  2│14 - 21 ×  2│21 ×  2│
├─────────────────┼────────────┼───────┤
│19 - 21 + 14 ÷  2│21 + 14 ÷  2│14 ÷  2│
├─────────────────┼────────────┼───────┤
│14 + 19 -  2 × 21│19 -  2 × 21│ 2 × 21│
├─────────────────┼────────────┼───────┤
            ...
├─────────────────┼────────────┼───────┤
│ 8 - 19 - 14 ÷  2│19 - 14 ÷  2│14 ÷  2│
├─────────────────┼────────────┼───────┤
│19 -  8 + 14 ÷  2│ 8 + 14 ÷  2│14 ÷  2│
└─────────────────┴────────────┴───────┘

      ⍎¨ 8 13 18 {⍺↓¨⊂⍵}⍤1 ⊢t
¯9 ¯28  42
¯9 ¯28  42
¯9  28   7
¯9 ¯23  42
   ...
¯4  12   7
 4  15   7

(An earlier version of the text appeared as the Jwiki essay Krypto, 2013-07-04.)

Beauty and the Beast

beauty-and-the-beastFinally, the last accessory I ordered for my Raspberry Pi Zero (that’s the little red thing behind my keyboard) has arrived – an Acer 43″ ET430K monitor. The Zero won’t quite drive this monitor at its maximum resolution of 3840×2160 pixels, but as you can see, you get enough real estate to do real graphics with “ASCII Art” (well, Unicode Art, anyway)!

Some readers will recognise the image as the famous Mandelbrot Set, named after the mathematician Benoit Mandelbrot, who studied fractals. According to Wikipedia a fractal is a mathematical set that exhibits a repeating pattern displayed at every scale – they are interesting because they produce patterns that are very similar to things we can see around us – both in living organisms and landscapes – they seem to be part of the fundamental fabric of the universe.

Fractals are are also interesting because they produce images of staggering beauty, as you can see on the pages linked to above and one of our rotating banner pages, where a one-line form of the APL expression which produced the image is embedded:

Website_banner_MbrotW

The colourful images of the Mandelbrot set are produced by looking at a selection of points in the complex plane. For each point c, start with a value of 0 for z, repeat the computation z = c + z², and colour the point according to the number of iterations required before the function becomes “unbounded in value”.

In APL, the function for each iteration can be expressed as {c+⍵*2}, where c is the point and ⍵ (the right argument of the function) is z (initially 0, and subsequently the result of the previous iteration):

      f←{c+⍵*2} ⍝ define the function
      c←1J1     ⍝ c is 1+i (above and to the right of the set)
      (f 0)(f f 0)(f f f 0)(f f f f 0) (f f f f f 0)
1J1 1J3 ¯7J7 1J¯97 ¯9407J¯193

If you are not familiar with complex numbers, those results may look a bit odd. While complex addition just requires adding the real and the imaginary parts independently, the result of multiplication of two complex numbers (a + bi) and (c + di) is defined as (ac-db) + (bc+ad)i. Geometrically, complex multiplication is a combined stretching and rotation operation.

Typing all those f’s gets a bit tedious, fortunately APL has a power operator , a second-order function that can be used to repeatedly apply a function. We can also compute the magnitude of the result number using |:

      (|(f⍣6)0)(|(f⍣7)0)
8.853E7 7.837E15

Let’s take a look at what happens if we choose a point inside the Mandelbrot set:

      c←0.1J0.1
      {|(f⍣⍵)0}¨ 1 2 3 4 5 6 7 8 9 10
0.1414 0.1562 0.1566 0.1552 0.1547 0.1546 0.1546 0.1546 0.1546 0.1546

Above, I used an anonymous function so I could pass the number of iterations in as a parameter, and use the each operator ¨ to generate all the results up to ten iterations. In this case, we can see that the magnitude of the result stabilises, which is why the point 0.1 + 0.1i is considered to be inside the Mandelbrot set.

Points which are just outside the set will require varying numbers of applications of f before the magnitude “explodes”, and if you colour points according to how many iterations are needed and pick interesting areas along the edge of the set, great beauty is revealed.

1200px-GalaxyOfGalaxies

The above image is in the public domain and was created by Jonathan J. Dickau using ChaosPro 3.3 software, which was created by Martin Pfingstl.

Our next task is to create array of points in the complex plane. A helper function unitstep generates values between zero and 1 with a desired number of steps, so I can vary the resolution and size of the image. Using it, I can create two ranges, multiply one of them by i (0J1 in APL) and use an addition table (∘.+) to generate the array:

      ⎕io←0 ⍝ use index origin zero
      unitstep←{(⍳⍵+1)÷⍵}
      unitstep 6
0 0.1667 0.3333 0.5 0.6667 0.8333 1
      c←¯3 × 0.7J0.5 - (0J1×unitstep 6)∘.+unitstep 6
      c
¯2.1J¯1.5 ¯1.6J¯1.5 ¯1.1J¯1.5 ¯0.6J¯1.5 ¯0.1J¯1.5 0.4J¯1.5 0.9J¯1.5
¯2.1J¯1   ¯1.6J¯1   ¯1.1J¯1   ¯0.6J¯1   ¯0.1J¯1   0.4J¯1   0.9J¯1  
¯2.1J¯0.5 ¯1.6J¯0.5 ¯1.1J¯0.5 ¯0.6J¯0.5 ¯0.1J¯0.5 0.4J¯0.5 0.9J¯0.5
¯2.1      ¯1.6      ¯1.1      ¯0.6      ¯0.1      0.4      0.9     
¯2.1J00.5 ¯1.6J00.5 ¯1.1J00.5 ¯0.6J00.5 ¯0.1J00.5 0.4J00.5 0.9J00.5
¯2.1J01   ¯1.6J01   ¯1.1J01   ¯0.6J01   ¯0.1J01   0.4J01   0.9J01  
¯2.1J01.5 ¯1.6J01.5 ¯1.1J01.5 ¯0.6J01.5 ¯0.1J01.5 0.4J01.5 0.9J01.5

The result is subtracted from 0.7J0.5 (0.7 + 0.5i) to get the origin of the complex plane slightly off centre in the middle, and multiplied the whole thing by 3 to get a set of values that brackets the Mandelbrot set.

Note that APL expressions are typically rank and shape invariant, so our function f can be applied to the entire array without changes. Since our goal is only to produce ASCII art, we don’t need to count iterations, we can just compare the magnitude of the result with 9 to decide whether the point has escaped:

      9<|f 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
      9<|(f⍣3) 0 ⍝ Apply f 3 times
1 1 1 0 0 0 1
1 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
1 0 0 0 0 0 0
1 1 1 0 0 0 1

We can see that points around the edge start escaping after 3 iterations. Using an anonymous function again, we can observe more and more points escape, until we recognise the (very low resolution) outline of the Mandelbrot set:


      ]box on
      {((⍕⍵)@(⊂0 0))' #'[9>|(f⍣⍵)0]}¨2↓⍳9
┌───────┬───────┬───────┬───────┬───────┬───────┬───────┐
│2######│3  ### │4      │5      │6      │7      │8      │
│#######│ ######│   ### │    #  │    #  │    #  │    #  │
│#######│#######│ ##### │  #### │  #### │   ### │   ### │
│#######│#######│###### │ ##### │ ##### │ ##### │ ####  │
│#######│#######│ ##### │  #### │  #### │   ### │   ### │
│#######│ ######│   ### │    #  │    #  │    #  │    #  │
│#######│   ### │       │       │       │       │       │
└───────┴───────┴───────┴───────┴───────┴───────┴───────┘

The last example allowed me to sneak in a preview of the new “at” operator coming in Dyalog v16.0. It is a functional merge operator that I am using to insert the formatted right argument (the number of iterations) into position (0 0) of each matrix.

If I use our remote IDE (RIDE) on my Windows machine and connect to the Pi, I can have an APL session on the Pi with 3840×2160 resolution. In this example, I experimented with grey scale “colouring” the result by rounding down and capping the result at 10, and using the character ⍟ (darkest) for 0, ○ for 1-5, × for 6-9, and blank for points that “escaped”, by indexing into an array of ten characters:

      '⍟○○○○○×××× '[10⌊⌊|(f⍣9)c]

Who needs OpenGL?! (click on the image to enlarge)

mandelbrot-ride4