NYCJUG/2023-05-09

Show-and-tell

Ed shows us a visual display tool for handling large amounts of textual data such as found in the J wiki.

JWikiViz

The J wiki comprises over 2000 pages; the J forums nearly 100,000 posts. While these volumes are modest compared to those of (say) the English-language Wikipedia, they're large enough that the classic Web browser model struggles to deliver a fast, fluid, welcoming experience to users--to the contrary, its halting, spoon-fed, disorienting, client-server approach to navigation actually tends to discourage exploration.

Bob Therriault, Raul Miller, Devon McCormick and Ed Gottsman have been working on a hybrid presentation environment for J content. Its left pane (written entirely in J) provides instant "structural navigation" for Bob's ~200-node content hierarchy, several hundred "free-floating" tag nodes, and the six date-organized forums, as well as search results and bookmarks. Its right pane shows the web page corresponding to the selection made in the left pane.

The interface is hover-based in order to sidestep our learned aversion to clicking links. Clicking a link is a punitive experience: you lose any sense of orientation you might have had as the current page disappears, to be replaced (after an unconscionable delay) by the link's target page. Then you have to wait again while you re-load and re-render the original page ("Go Back") and (even worse) recover your lost orientation. At some level we understand this cost, which is why we often find ourselves hovering indecisively on a link, trying to work out whether the unpleasant investment (delay/disorientation) is worth the uncertain benefit. So, in this experience, no clicking: hovering indecisively is enough to load a page (just as it might normally load a tool tip) and you always move forward--you never waste time Going Back.

As far as I can tell, the culture that's grown up around J is almost exclusively one of mathematical programming but (in combination with Qt and gl2) J turns out to be extremely well-suited to the "soft" task of prototyping atypical user experiences. I've done this kind of work in many languages and libraries over the years. J provides by far the most productive environment for rapidly building a "left-field" UX that I've ever seen.

Beginner's regatta

We look at how to find the center of a set of points. This method extends to multiple dimensions.

Center of Points

To find the center of a set of points, average them. It should be apparent that the center of a two-dimensional set of points is the average of the X and Y coordinates. This "center" is defined as the single point closest to all the points in a cluster as measured by a standard Euclidean distance measure like ([: %: [: +/ [: *: ,).

For example, say we have this set of points and we want to find the center of the polygon shown by their outline:

pts0 1.47723 1 1.94254 1.26864 1.78743 1.53728 1.16703 1.53728 1.01193 1.26864 0.546628 1.53728 0.081326 1.26864 0.236427 1 0.546628 1 0.546628 0.462715 1.01193 0.194073 1.16703 0.462715 1.47723 0.462715

An Aside on Plotting a Polygon

We plotted the above polygon like this:

   'type line;pensize 3;title An Irregular Polygon' plot (],{.) j./"1 pts0

This creates point pairs from pts0 by turning each pair in a row into a complex number (with j./"1). The expression (],{.) repeats the first point at the end to finish at the starting point in order to add the final line segment of the polygon.

An alternative to using complex numbers is to box the X and Y coordinates like this:

   'type line;pensize 3;title An Irregular Polygon' plot <"1|:(],{.)pts0

Finding the Center

We find the center of the points of a polygon simply by averaging the points (assuming we have a two-column table of points):

   ]ctr=. (+/%#) pts0
1 1

Plotting this again and including the center point,

   pd (],{.)j./"1 pts0 [ pd 'type line;pensize 2;color blue' [ pd 'reset'
   pd 'title Polygon and its Center'
   pd 'show' [ pd ,:j./ctr [ pd 'type dot;pensize 4' [ pd 'color red'

We have to use the plotting primitive pd instead of the plot cover function because we are mixing plot types to show lines and a point.

Note that this averaging method should work to find the center of a point cluster for any dimension. However, be aware that a center point may not be contained in a polygon as shown here:

   pts2=: 1 1,2 1,4 3,2 5,1 4,:3 3
   pd (],{.)j./"1 pts2 [ pd 'type line;pensize 2;color blue' [ pd 'reset'   
   pd 'title Polygon Not Containing its Center'
   pd 'show' [ pd ,:j./(+/%#)pts2 [ pd 'type dot;pensize 4' [ pd 'color red'

Advanced topics

We incorporate finding the center of a polygon with with different methods of rotating a polygon about this center.

Rotating Points

We look at rotating points in two dimensions and the related problem of finding the center of the points. Our initial attempt relies on polar coordinate conversions as shown below.

NB.* rotatePtsP: rotate (nx2) points y by x degrees by polar method.
rotatePtsP=: 4 : 0
   pts=. c2p"1 y-"1 center=. (+/%#) y       NB. polar coords (r, θ)
   pts=. ((x*2p1%360)+1{"1 pts) 1}&.|: pts  NB. *2p1%360: degrees to radians
   center+"1 p2c"1 pts                NB. Polar->Cartesian and re-center
)           

Here we use c2p to convert Cartesian coordinates to polar coordinates, add the angle of rotation (in radians) to the angle θ, then convert the result back to Cartesian using p2c.

   p2c=: +.@(r./)
   c2p=: ({. , 6.28318530717958623&|@{:)@:(*.@(j./))

However, notice that before we calculate the rotation, we first find the center of the points and subtract this from each point. This effectively moves the polygon to be centered at the origin (0,0) We then we rotate them and add the center back after we've done so. We do this because our intention is to rotate the points about their own center. Otherwise we would be rotating the polygon about the origin which would change the position of the polygon in addition to changing its orientation.

Just for fun, we asked the Microsoft Bing AI: What is the formula for rotating points in two dimensions? This is the answer we got:

The trigonometric method, rotatePts below, is easily extendable into three dimensions so has the advantage of generality. Additionally, we can also rotate in three dimensions using eigenvectors, as shown here in Matlab.

Different Rotation Methods

Implementing the two methods above gives us these two alternate ways of rotating points.

NB.* rotatePtsC: rotate (nx2) points y by x degrees using complex number method
rotatePtsC=: 4 : 0
   pts=. y-"1 center=. (+/%#) y
   center+"1 +. (j./"1 pts)*(^1)^j. x*2p1%360   NB. *2p1%360: degrees to radians
)

NB.* rotatePts: rotate (nx2) points y by x degrees by trigonometric method.
rotatePts=: 4 : 0 
   x=. x*2p1%360                 NB. angle in radians
   pts=. y-"1 center=. (+/%#) y  NB. Center image at origin
   center+"1 (-/"1 (2 1 o. x)*"1 pts),.+/"1 (1 2 o. x)*"1 pts   
)      

Quick sanity check that all three methods give the same result for a limited set of values:

   (30 rotatePtsP pts0) -: 30 rotatePts pts0
1
   (30 rotatePtsP pts0) -: 30 rotatePtsC pts0
1

Timings

Now let's time the methods against each other using a large number of points and a random set of angles.

   $rndpts=. <.0.5+100*<:+:1000 2?@$0
1000 2
   angles=. 100?360
   6!:2 'angles rotatePtsP &.>/<rndpts'
0.117258
   6!:2 'angles rotatePts &.>/<rndpts'
0.0210479
   6!:2 'angles rotatePtsC &.>/<rndpts'
0.0251319
   24.3538%20.5253
1.18653              NB. rotatePtsC about 19% slower than rotatePts 

Here we use &.>/<rndpts to apply each angle to the entire set of points to get a large set of comparisons. The latter two methods appear to be considerably faster than our initial idiosyncratic method based on conversion to and from polar coordinates. Another strike against rotatePtsP is that its results do not always agree, as shown by more extensive testing, with the results of the two faster methods but this is a tiny difference because of floating point imprecision. We see below that that largest and smallest differences are on the order of 2e_13 and average around 4e_16:

   (angles rotatePtsP &.>/<rndpts) -: angles rotatePts &.>/<rndpts
0
   usus ,(;angles rotatePtsP &.>/<rndpts) - ;angles rotatePts &.>/<rndpts
_1.95399e_13 2.06057e_13 _4.43148e_16 2.7022e_14          NB. Min, max, average, standard deviation of differences.

However the two faster ones agree with each other more precisely.

   (angles rotatePtsC &.>/<rndpts) -: angles rotatePts &.>/<rndpts
1

Looking at a Rotation

Let's say we want to rotate by 60° the polygon defined above. Here's how we could do that while including the center point of both the original and the rotated versions.

   ctr=. (+/%#) pts0
   pts1=. 60 rotatePts pts0
   ((+/%#) pts0) -: (+/%#) pts1    NB. Same center?
1
   pd (],{.)j./"1 pts0 [ pd 'type line;pensize 2;color blue' [ pd 'reset'
   pd (],{.)j./"1 pts1 [ pd 'type line;pensize 2;color green'
   pd 'title Polygon, its 60° Rotation and their Center'
   pd 'show' [ pd ,:j./ctr [ pd 'type dot;pensize 4' [ pd 'color red'

The blue is the original and the green is the rotation. Notice that a positive number implies a counter-clockwise rotation.

A Single Tile to Tile Them All

This New Scientist article shows a single 13-sided tile which has been proven to be able to tile an infinite plane without repetition.

Some Background on Tiling

There are only three regular polygons that can tile an infinite plane: the triangle, the square, and the hexagon. So, whereas a regular pentagon cannot tile a plane without overlap or gaps, these three are able to. However, each of these tiles with a repeating pattern. This means that, for instance, if we know what a unit square tiling looks like at the origin, we also know what the tiling looks like at point (1000, 1000) or any other point because the pattern repeats and it's simple to calculate what it looks like at any arbitrary point.

However, since the pattern of this new shape does not repeat, we cannot simply figure out what the tiling looks like at an arbitrary point without actually tiling out to that point. Indeed, as we see below, there appears to be at least one alternate valid tiling even in the simple case of only three tiles.

The Hat

"Now, Chaim Goodman-Strauss at the University of Arkansas and his colleagues have found a single tile shape – which they have called “the hat” – that does the same job." .

Here is an example picture from the article showing a section of tiling with this new tile.

The significance of this is that

[u]ntil now, it wasn’t even clear whether such a single shape, known as an einstein (from the German “ein stein” or “one stone”), could even exist. Sarah Hart at Birkbeck, University of London, who wasn’t involved with the research, says that until now she thought it would be impossible. “There are infinitely many possible candidate tiles, and even the existence of a solution feels quite counterintuitive,” she says.

There may be no practical value for this new discovery but there is at least use of its physical incarnation: someone has built a football (soccer ball) using the tile.

In the spirit of exploration, how can we make a hat of our very own?

Estimating Tile Co-ordinates

The New Scientist article gives no details about the set of points that comprises this tile, so we figured it out for ourselves.

Our initial attempt at re-creating the tile was very crude: we created a grid in J that we overlaid on a picture of some tiles and used the grid to estimate point values. However, upon noticing the hexagonal grid on which the tiles were laid, and having some routines from a previous NYCJUG meeting for working with hexagons, we were able to calculate precise values for the points of the tile.

Unit Hexagons	Grid on Tiles' Picture	Measurement Error

When we compared our original estimate of the corners of the einstein to the calculated values, it appears that while the estimated shape - in blue - approximates the tile in appearance, it differs conspicuously.

Alternate Tiling

While working on adding multiple tiles to mimic part of the diagram from the New Scientist article, we accidently added a third tile that fits with the other two but has a different orientation than the one we were trying to match.

Alternate Orientation of Third Tile	Proper Orientation

Starting to Tile

By referring to the hexagonal grid, we see that the einsteins used to tile the plane differ by angles that are multiples of 30 degrees and each one of these 12 tiles has a mirror image as the tile is not symmetric. So we can calculate all possible tiles using our point rotation routine from above and incorporating a point mirroring routine like this one:

NB.* mirrorPts: rotate (x,y) points about the x axis (x=0) or y axis (x=1)
mirrorPts=: 3 : 0
   0 mirrorPts y
:
   pts=. y-"1 center=. (+/%#) y
   xctr=. (+/%#)x{"1 pts
   center+"1 (xctr-"1 ] x{"1 pts) x}&.|:pts
)

After discussing this in the meeting, we realized that using matrix multiplication to mirror points along either the X or Y axis is a more general, simpler way to do this:

   mirrorY=: 13 : '((+/%#)y)+"1 (_1 0,:0 1)+/ . *&.|:y-"1 (+/%#)y'  NB. Center on origin, mirror along Y axis, re-center
   mirrorX=: 13 : '((+/%#)y)+"1 (1 0,:0 _1)+/ . *&.|:y-"1 (+/%#)y'  NB. Center on origin, mirror along X axis, re-center

With these to tools, we can create all 24 possible valid variations of the tile.

NB. All variations rotated and mirrored
   allHats=. (30*i.12) rotatePts&.><ptsHat
   allHats=. allHats,mirrorPts&.>allHats

Once we have all these variations of the tile, with a little trial and error we can figure out how to combine some of them to start to tile the plane.

   'title Three Tiles;aspect 0.85;pensize 3;type line;color black,blue,red;key Tile0 Tile1 Tile2;keycolor black,blue,red' plot ((],{.)j./"1 ] >0{allHats),((],{.)j./"1 ] (>22{allHats)+"1 (1{>0{allHats)-6{>22{allHats),:(],{.)j./"1 ] (>2{allHats)+"1 (9{>0{allHats)-0{>2{allHats

The plot above gives us this:

We do not have a general tiling method but these routines should give us a start on figuring it out. Breaking out and naming the three tiles above shows us this:

   tile0=. j./"1 >0{allHats
   tile1=. j./"1 (>22{allHats)+"1 (1{>0{allHats)-6{>22{allHats
   tile2=. j./"1 (>2{allHats)+"1 (9{>0{allHats)-0{>2{allHats

   tile0 e. tile1
1 1 0 0 0 0 0 0 0 0 0 1 1
   tile0 e. tile2
0 0 0 0 0 0 0 1 1 1 1 0 0
   tile1 e. tile2
0 1 1 0 0 0 0 0 0 0 0 0 0

The part of the equations for the latter two tiles, e.g. +"1 (9{>0{allHats)-0{>2{allHats, is the offset by which we move a tile into its proper position in relation to the initial tile centered on the origin. The expression, (9{>0{allHats)-0{>2{allHats reflects that point 9 of hat 0 coincides with point 0 of hat 2 which is why we shift hat 2 by this amount.

Learning and Teaching J

We look at a recently created notation for numbers that has some advantages for practical arithmetic in this article.

A Number System Invented by Inuit Schoolchildren

In the remote Arctic almost 30 years ago, a group of Inuit middle school students and their teacher invented the Western Hemisphere’s first new number system in more than a century. The “Kaktovik numerals,” named after the Alaskan village where they were created, looked utterly different from decimal system numerals and functioned differently, too. But they were uniquely suited for quick, visual arithmetic using the traditional Inuit oral counting system, and they swiftly spread throughout the region.

The system looks like this:

Here is how simple arithmetic is done using Kaktovik numerals.

However, the main emphasis of the article is about the digitization of this numbering system.

Now support from Silicon Valley is helping to reignite the Kaktovik numerals. Thanks to efforts by linguists working with the Script Encoding Initiative at the University of California, Berkeley, the numerals were included in the September 2022 update of Unicode

References

Mathematicians discover shape that can tile a wall and never repeat, New Scientist, 21 March 2023

A Number System Invented by Inuit Schoolchildren Will Make Its Silicon Valley Debut, Scientific American, 10 April 2023