Tool of Thought

APL for the Practical Man

LeetCode 601: Human Traffic of Stadium

July 9, 2022

In this strangely titled LeetCode problem, we are given the following table:

 t.Display 0
── LeetCode601.Numbers ─────────
 ┌ID──┐  ┌VisitDate─┐  ┌People┐ 
 ↓1   │  ↓2017-01-01│  ↓10    │ 
 │2   │  │2017-01-02│  │109   │ 
 │3   │  │2017-01-03│  │150   │ 
 │4   │  │2017-01-04│  │99    │ 
 │5   │  │2017-01-05│  │145   │ 
 │6   │  │2017-01-06│  │1,455 │ 
 │7   │  │2017-01-07│  │199   │ 
 │8   │  │2017-01-09│  │188   │ 
 └Int8┘  └Date──────┘  └Int16─┘ 
── 8 rows by 3 columns ─────────

And informed that:

VisitDate is the primary key for this table. Each row of this table contains the visit date and visit id to the stadium with the number of people during the visit. No two rows will have the same VisitDate, and as the ID increases, the dates increase as well.

And then charged with:

Write an SQL query to display the records with three or more rows with consecutive id's, and the number of people is greater than or equal to 100 for each. Return the result table ordered by VisitDate in ascending order.

Let's take a look at how to the solve this in APL, and then translate to a FlipDB solution. First some variables:

      i←1+⍳8
      p←10 109 150 99 145 1455 199 188 

Note that the visit date adds nothing of interest to this problem. Also note we assume, for now, the IDs are already in ascending order. Selecting out IDs where the number of People is greater than 100:

      j←(p>100)/i
      j
2 3 5 6 7 8

This yields non-consecutive IDs, which is the heart of the problem. We now need to identify runs of non-consecutive IDs, which is easy using the rank idiom (⍋⍋):

      j-⍋⍋j
2 2 3 3 3 3 

We might reach for pair-wise reduction here instead, to find where the IDs increase by more than one, but that leads to a more complicated solution. Now partition or group the IDs by their runs:

     g←(j-⍋⍋j)⊆j 
     g
┌───┬───────┐
│2 3│5 6 7 8│
└───┴───────┘

And finally, get a simple vector of all IDs that exist in groups of 3 or more:

       k←∊(3≤≢¨g)/g
       k
5 6 7 8 

A boolean where clause to apply to the original table is then:

      i∊k
0 0 0 0 1 1 1 1

And we are pretty much done. We can write this as a one-liner using a couple of dfns if we want an expression that maps to a single FlipDB where statement:

      i∊∊{(2<≢¨⍵)/⍵}{(⍵-⍋⍋⍵)⊆⍵}(p>100)/i
0 0 0 0 1 1 1 1

Now we can almost transliterate into FlipDB:

      ID in {z where 2 < count z} {(z-rankUp z) partition z} ID where People > 100

Note that the where appearing twice above is not a where clause, which is the entire statement, but the where function - a FlipDB structural function. Of course in FlipDB we might break the problem down a bit, and define some computed values first in our query, and we should probably sort the IDs to ensure ascending order:

NameExpression
Over100sortUp ID where People > 100
Groups{(z - rankUp z) partition z} Over100
ThreesGroups where 2 < count Groups

and then write a simple where statement:

      ID in Threes

This keeps it clean, simple, and usefully traceable in the FlipDB tracer.