NYCJUG/2021-11-09

From J Wiki
Jump to: navigation, search

Beginner's regatta

Building a GUI Interface in J: What it Looks Like

We have a window like this, on the left which is mostly defined by the code on the right which uses J's window driver module wd to instantiate it.

Generate password - v3.jpg
GPSW=: 0 : 0                              NB. Generate password window
pc gpsw escclose;pn "Generate password";
bin v;
    bin v; bin h;
               cc pwdlen static;cn "Password length";
               cc lenInp edit;
	   bin z;
           cc size scrollbar 4 1 0 50 8;
    bin z;
    bin v;bin h;
            cc rbgenAlt radiobutton; cn "Alternating hands";
            cc rbgenRand radiobutton; cn "Generate randomly";
        bin z;
        groupbox "Random Generation Parameters";
        bin h;
            cc ckab checkbox; cn "All below";
            cc ckes checkbox; cn "E&xclude similar characters";
        bin z;
        cc ckal checkbox;cn "&lowercase";
        cc ckau checkbox;cn "&uppercase";
        cc ckad checkbox;cn "&digits (0-9)";
        cc ckah checkbox;cn "&special characters";
        groupboxend;

        bin h;
            cc strength static;cn "Strength: ";
	    cc strenval static;cn "0";
        bin z;
        cc pwdLabel static; cn "Generated password:";
        cc pwd edit readonly;
    bin z; bin z;
cc gp button;cn "&Generate";
pas 3 3;pcenter;
rem form end;
)

What the Code Means

The above code is arguably not code because it does not run until the wd verb as applied to GPSW, the noun defined by everything between the initial "0 : 0" and the final lone closing parenthesis. However, it provides a simple text version of the window on the left which we will explain here.

Start of Defining a Form

The form definition lays out the appearance of the window from top to bottom, after the initial line creates the form. This line consists of two statements terminated by semi-colons:

pc gpsw escclose;pn "Generate password";

These two statements establish the parent control (pc) and its title. The parent control is defined with the name gpsw, using the method escclose, to close the form with the Escape key. The title of the form, the parent name (pn), is "Generate password". This generates the top line of the form shown on the left above.

The next bunch of lines,

bin v;
    bin v; bin h;
               cc pwdlen static;cn "Password length";
               cc lenInp edit;
	   bin z;
           cc size scrollbar 4 1 0 50 8;
    bin z;

is notable mostly for all the bin directives. These establish vertical or horizontal alignments for the following group of graphic items. Each alignment group is ended by a bin z;.

Note the semi-colon terminator after each statement. A significant portion of my earliest errors were when I left off a statement terminator, particularly at the end of a line of text.

So, the first major bin, bin v;, aligns every following item, graphic element or bin, vertically. This is followed immediately by a bin h; to begin a short horizontal bin consisting of the two child controls (cc) named pwdlen and lenInp. The first of these is set to be static to indicate it will not change. The next statement, setting the child's name (cn) to be "Password length:", changes it.

The first bin z; ends the horizontal bin and resumes the vertical one for what follows, which is the child control scrollbar named size. Interestingly, this seems to mean that the value of a global size is available for subsequent code as will be shown in a later section. The scrollbar starts at a low value of 4, going by steps of 1, 0?, up to 50 though the display does not help with any of these numeric parameters.

We can see these alignments in the next few elements down from the top of the window: the text Password length is aligned horizontally with the edit field into which the user can enter a small integer value. The horizontal alignment ends after these two because of the bin z; terminator and the vertical alignment resumes, positioning the scrollbar below the password length text entry section.

Middle of the Form

The layout of most of the rest of form is governed by the vertical bin starting with the radio buttons at the top to the Generate button at the bottom. The first vertical component is a horizontal section for the two radio buttons titled Alternating hands and "Generate randomly"; this horizontal component then ends with bin z; and the outer, vertical alignment continues.

The depth of nesting of the statements indicates to which alignment a set of GUI items belongs.

bin v;bin h;
            cc rbgenAlt radiobutton; cn "Alternating hands";
            cc rbgenRand radiobutton; cn "Generate randomly";
        bin z;

Here we see that the radio buttons are indented within their horizontal section.

Most of the form real-estate is consumed by the next section below these radio buttons. This large section applies only to the "Generate randomly" button but I do not know how to indicate this by doing something like graying out that section when its button is not selected.

"Alternating hands" versus "Generate randomly"

The two major variants of password reflect my addition of the alternating hands version to the (translation of) code presented earlier by Nikitin. Most of the rest of the window is very similar to what was originally presented in that essay. However, the alternating hands type of password is my novel contribution to the generator.

"Alternating hands" refers to using the fingers of one hand, then the other, when typing a password on a standard keyboard. We can divide the keys on a standard Windows keyboard like this:

Left-Right dividing line on keyboard.jpg

The J code to accomplish this uses a two-element vector noun defined like this:

LRsets=: 'qwertasdfgzxcvb~`12345!@#$%' ; 'yuiophjklnm67890-_=+\|^&*()[{]};:''",.<>?/'

0{LRsets are the characters typed with the left hand and 1{LRsets are those for the right.

This division of characters is used to find a set of words that can be typed with consecutive letters alternating between left and right ones. This kind of word is usually easy to type so it's easier to tolerate a longer password. However, the settings in the "random generation parameter" section are orthogonal to the passwords generated by this method, so we would like to incorporate those considerations.

Some of these parameters, like upper versus lower case, are easy to apply to what we generate since we can randomly change the case of letters. However, inserting nonalphabetic characters, like numerals and special symbols, is more involved. This is handled in the makeShims code seen below.

Bottom of the Form

The last 4 lines of the window mostly reflect the output of the settings chosen, except for the "Generate" button which generates a password.

Show-and-tell

GUI-based Password Generator

I'm re-using some of the code I found here: https://code.jsoftware.com/wiki/User:Andrew_Nikitin/Literate. This uses the windows driver wd but the underlying windowing commands have changed, probably due to the switch to a Qt interface.

Unfortunately for Nikitin's point of literate programming in the essay, I have also started to remove some of that as I do not find it helpful and think the idea in general is over-sold.

Setting up the Form and the Most Basic Controls

This basically works but there are places this could be cleaned up. The dialog looks as shown above in the Beginner's Regatta section, so we will assume that and show only code following that.

The password length is controlled by the input field and the slider, which goes down to four on the far left side to a maximum of 50 (though it's not labeled so how would we know this?) Labeling this is something I have yet to figure out.

Here we set up the buttons to cancel or exit out of the dialog. The cancel button is defined to invoke the pclose method and the other buttons to exit or cancel are simply assigned to this button.

After these crucial buttons are set up, the form is defined using the large noun shown in the previous section above and displayed by invoking the pshow method to display the parent form.

gpsw_cancel_button=: wd bind 'pclose;'
gpsw_exit_button=: gpsw_cancel_button
gpsw_close=: gpsw_cancel_button

gpsw_run=: 3 : 0
    wd GPSW
    wd 'pshow;'
)

gpsw_run ''

Since we want to generate different passwords each time this code is loaded and run, we must set the random seed to be unique each time. Here it is based on the current timestamp though this way of doing it is not the best, as indicated by the comment.

The various checkboxes, with names beginning ck, are initialized here. A checkbox can either be zero (unchecked) or one (checked). The radio button indicating we will use the alternating-hands method of password generation is also turned on by setting it to one. The non-Boolean values of 16 are set for the two controls for the password length. Since these controls set the same value, they also set each other when either one is invoked in order to keep them in synch.

NB. Poor initialization of the random seed: fix this!
9!:1 [ 60 60 24 #. |. _3 {. <. (6!:0 '')

NB. Initialize default settings:
([: wd 'set ' , ])&> 'rbgenAlt 1';'ckab 1';'ckes 0';'ckal 1';'ckau 1';'ckad 1';'ckah 1';'size 16';'lenInp text 16'

NB. Length or number of characters in the password. Limits set for
NB. scrollbar size implicitly define limits on allowed password sizes.
NB. Length is displayed in static lenInp.

gpsw_size_button=: 3 : 0
  wd 'set lenInp text ',size
  gpsw_generatePassword_button ''
)

gpsw_lenInp_button=: 3 : 0
   newsz=. wd 'get lenInp text'
   wd 'set size ',newsz            NB. Set same value for scrollbar.
   newsz=. wd 'get size value'     NB. scrollbar enforces min/max
   wd 'set lenInp text ',newsz     NB. Ensure actual value shows.
   gpsw_generatePassword_button ''
)
The Alphabets

This next section explains the meaning of the Exclude similar checkbox, initialized to zero to be turned off, and sets up the various sets of letters, numerals, and characters indicated by the other checkboxes, as well as a few utility functions.

NB. SIMILAR noun lists characters that look similar and can be easily confused
NB. with each other. Definition of "look similar" depends on one's handwriting
NB. and is therefore user configurable. If exclude similar is checked, then
NB. password will not contain any of those characters, so there cannot be mistake
NB. in transcription.

note=. 0 : 0
Note, how SIMILAR is explained here, where it belongs, but inserted in the code in the beginning of the file, so it can be tweaked by the user.
)

SIMILAR=:'OQ0Do';'Il1';'2Zz';'5Ss';'8B';'9g';'6G'

rsel=: ;@:(({~ ?@#)&.>)@(-.&a:)
flt=: ;@[ -. ;@[ -. ]
rrsame =: 3 : 0
   x=.(flt&y)&.>SIMILAR
   (y -. ;x) , rsel x
)

ALPH_LOW=:a.{~ (a.i.'a')+i.26
ALPH_UP=:a.{~ (a.i.'A')+i.26
ALPH_DIG=:a.{~ (a.i.'0')+i.10
ALPH_HEX=:a.{~ (a.i.'a')+i.6
Strength Calculation

The original code set up the alphabets determined by which checkboxes were selected and uses the length of the available character set to calculate a password strength number.

Much of the original documentation of this calculation was left it here even though it appears to be incorrect. The author states that the number calculated is "the negative logarithm of the probability to guess the password..." but the J code does not have a negation in it. All the more ironic is the inclusion of some kind of attempt to display the formula mathematically since this does not translate properly here and casts doubt on the "literate programming" idea it is intended to illustrate. It's also unclear if the mathematical expression would be any clearer than the J version of it.

calcStrength=: 3 : 0
   alph=.;("."0 ckal,ckau,ckad,ckah)#(ALPH_LOW;ALPH_UP;ALPH_DIG;ALPH_HEX)
   alph=.alph -.~^:(ckes-:,'1')~ ; (#~ (1 < +/@e.&alph)&>) SIMILAR
   alph=.~.alph,'01'#~0=#alph

NB. Entropy is calculated as {\displaystyle e=\lceil {n\times \log _{2}\#\alpha }\rceil }
NB. It can be used to estimate password "strength" in bits.
NB. Please note that formula is included in its natural form. This removes
NB. limitation of including formulas and diagrams into in-source comment
NB. only in the form of ascii art.
NB. Here "strength" is the negative logarithm of the probability to guess
NB. the password first time.
   alph;<<.(".size)*2^.#alph
)
Password Generation

The Generate button at the bottom of the form runs the code to generate a password according to the criteria specified by the various settings above it. Actually, these criteria are only honored by the "Random generation" method, as indicated by their placement on the form. The alternate-hands method attempts to include special characters, mixed case letters, and numerals but does this without regard to the settings for the other generation method.

NB.* gpsw_generatePwd_button: Either generate alternating-hands password OR
NB. select set of characters allowed in the password, weeding out similar
NB. characters if requested.
gpsw_generatePwd_button=: 3 : 0
   svSz=. wd 'get size value'
   if. rbgenAlt do. pwd=. genAltPwd ''
   else.
      'alph strength'=. calcStrength ''
       pwd=. alph {~ ? (". size)##alph
   end.
    wd 'set pwd text ',pwd
    wd 'set strenval text ',":strength
    wd 'set size ',svSz
    wd 'set lenInp text ',svSz
NB.   wdclipwrite pwd  NB. work on this
)

Most of the checkboxes are assigned to the password generation button so that the display on the form will remain consistent (for random generation) whenever any of these criteria are changed.

NB. Any click on any of the checkboxes that changes allowed character set generates new password.

gpsw_ckau_button=: gpsw_generatePwd_button
gpsw_ckal_button=: gpsw_generatePwd_button
gpsw_ckah_button=: gpsw_generatePwd_button
gpsw_ckad_button=: gpsw_generatePwd_button
gpsw_ckes_button=: gpsw_generatePwd_button
Alternating-hands Password Generation

The alternating-hands passwords rely on a list of words that are typed with consecutive letters from alternating hands with the exception that doubled letters are allowed. The word list was culled from many sources on the internet and includes a number of non-English words out of necessity since this criterion greatly limits the words we can use. A group of these words are selected and non-alphabetic characters are inserted and the junction of a word that ends on one hand but is followed by a word beginning with the same hand. These are called shims.

There are neutral shims which may be placed between two words that do not need to be adjusted because one ends with a character typed by the hand opposite of the hand used for the first character of the next word. These neutral shims are always two characters long as they need to get back to where they started. We calculate these because it simplifies the placement of shims between words and, if we force the first shim to always be used, we are more likely to generate a password incorporating non-alphabetic characters.

NB.* LRAltWords.ijs: find words typed by alternating left and right hands; use this
NB. list to help generate easily-typeable, long passwords.

NB.* LRsets: Left/right-hand sets of characters.
LRsets=: 'qwertasdfgzxcvb~`12345!@#$%' ; 'yuiophjklnm67890-_=+\|^&*()[{]};:''",.<>?/'

genAltPwd=: 3 : 0
   svSz=. wd 'get size value' [ svPwd=. wd 'get pwd text' [ 'alph strength'=. calcStrength ''
   wd 'set lenInp text 20'
   wd 'set size 20'
   gpsw_gp_button ''
   seedStr=. wd 'get pwd text'
   wd 'set size ',svSz
   wd 'set lenInp text ',svSz
   wd 'set pwd text ',svPwd
   wd 'set strenval text ',":strength
   nw=. #WORDS
   wrds=. (]{~[:?~#) WORDS{~((<.>:nw^.nn)$nw) #: nn=. (#;LRsets)#.x:(;LRsets) i. tolower 4 (] $~ [ >. [:#]) seedStr
   wrds=. (randUppercase wrds),&.>(#wrds){.makeShims wrds   
   newpwd=. (".size){.;wrds
   wd 'set pwd text ',newpwd
   'alph strength'=. calcStrength ''
   wd 'set strenval text ',":strength
   newpwd
NB.EG genAltPwd ''
)

We see that the key to this scheme is dividing all relevant characters into a left-hand or right-hand side of the keyboard by setting up a two-element vector LRsets categorizing each character on one side or the other.

One slightly tricky thing the above code does is to generate a random character-based seed by using the random password generator. To do this, we save the state of a few fields we have to change briefly, set the length of our seed to be 20, generate it, then set the fields back to what they were before using the seed to generate our list of words.

Our list of words relies on a fairly lengthy noun WORDS defined at the bottom of this code but not shown here.

Some Final Utilities

Below are three utilities used by the above code. The makeShims routine is the most involved. The randUppercase routine can probably be done without looping but, since it involves insertion which is always slightly tricky, I resorted to a simple loop to change some of the letters of words in a list to upper-case.

selRand=: ] { ~ [: ? #     NB.* selRand: select 1 item randomly from vec arg.
NB.* makeShims: maintain hand alternation by inserting shims between a word
NB. that ends on one side and a following word the begins on same side; the
NB. shim is on the hand alternating between the two consecutive same hand chars.
makeShims=: 3 : 0
   nonalp=. (-.&.>*./\&.>LRsets e.&.><Alpha_j_)#&.>LRsets
   last1st=. <"1 ([: }: {:&> (,.) 1 |. {.&>) tolower&.>wrds=. y
   juncture=. #.>0{"1 last1st e.&.>/LRsets            NB. (0,3)->needs shim; (1,2)->OK as is.
NB. However, generate double shims for OK transitions and insert a few for variety.
   shims=. selRand&>&.>(juncture{0;0 1;1 0;1){&.><nonalp
   useWhich=. (1) 0}(juncture e. 0 3)+.(#juncture)?@$2   NB. Randomly select but always 1st
   shims=. useWhich#&.>shims                             NB. so we include a non-alpha char.
NB.EG  wrds=. wrds,&.>makeShims wrds
)

randUppercase=: 3 : 0
   wrds=. y
   randUCix=. ?@:#&>wrds                NB. Random letter in each word to uppercase
   ww=. (# ?~ [: >. [: -: #) randUCix   NB. Which words chosen to have letter uppercased
   wh=. ww{randUCix                     NB. Where the letter is for each chosen word
   newLets=. toupper&.>wh{&.>ww{wrds    NB. Upper case letters to insert
   for_ix. i.#wh do.
       wrds=. (<(>ix{newLets)(ix{wh)}>ix{ww{wrds) ix}wrds
   end.
   wrds
)

WORDS=: <;._2 ] LF (] , [ #~ [ ~: [: {: ]) CR-.~0 : 0
akey
akka
algy
...
offkey
syzygy
vivify
)

The full word list is available in the code package here.

Advanced topics

Finance and Actuarial Work in J

We will hear from Bill about the work he's been doing on financial and actuarial calculations in J as seen here.

Learning and Teaching J

There are many sites offering problems to be solved programmatically. Some of these are geared toward improving one's skill in a language, others are more purely recreational. However what nearly all the language-specific ones have in common is ignoring J and APL, like this one, for instance.

We'll take a look at this problem and show how simple it is to solve in J since it is not one of the languages offered for this test.

The problem is said to be one of Array Manipulation and is explained like this:

Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in the array.

Example Problem [from HackerRank]

Queries are interpreted as follows:

    a b k
    1 5 3
    4 8 7
    6 9 1

Add the values of between the indices and inclusive:

index->	 1 2 3  4  5 6 7 8 9 10
	[0,0,0, 0, 0,0,0,0,0, 0]
	[3,3,3, 3, 3,0,0,0,0, 0]
	[3,3,3,10,10,7,7,7,0, 0]
	[3,3,3,10,10,8,8,8,1, 0]

The largest value is 10 after all operations are performed.

Function Description

Complete the function arrayManipulation in the editor below.

arrayManipulation has the following parameters:

int n - the number of elements in the array int queries[q][3] - a two dimensional array of queries where each queries[i] contains three integers, a, b, and k.

Returns

int - the maximum value in the resultant array

Input Format

The first line contains two space-separated integers and , the size of the array and the number of operations. Each of the next lines contains three space-separated integers , and , the left index, right index and summand.

Constraints

ConstraintsForProblem.jpg

Sample Input

5 3
1 2 100
2 5 100
3 4 100

Sample Output

200

Explanation

  • After the first update the list is 100 100 0 0 0.
  • After the second update list is 100 200 100 100 100.
  • After the third update list is 100 200 200 200 100.

The maximum value is 200.

A J solution

Set up the array.

  ]abk=. 1 5 3,4 8 7,:6 9 1
1 5 3
4 8 7
6 9 1

We are going to want indexes to cover each range defined by the first two columns of abk.

   ixs=. (0{"1 abk)+&.>i.&.>>:-/"1]1 0{"1 abk
   ixs
+---------+---------+-------+
|1 2 3 4 5|4 5 6 7 8|6 7 8 9|
+---------+---------+-------+

How wide should the range be to accomodate all our vectors?

   'min max'=. (<./,>./),0 1{"1 abk
   min+i.>:max-min
1 2 3 4 5 6 7 8 9
   ]v=. min+i.>:max-min
1 2 3 4 5 6 7 8 9

Now deal with the values to insert for each set of indexes.

   2{"1 abk
3 7 1

Generate the indexes at which to insert these values.

   ((i.#ixs),.&.><:&.>ixs)
+---+---+---+
|0 0|1 3|2 5|
|0 1|1 4|2 6|
|0 2|1 5|2 7|
|0 3|1 6|2 8|
|0 4|1 7|   |
+---+---+---+
   <"1&.>((i.#ixs),.&.><:&.>ixs)
+---------------------+---------------------+-----------------+
|+---+---+---+---+---+|+---+---+---+---+---+|+---+---+---+---+|
||0 0|0 1|0 2|0 3|0 4|||1 3|1 4|1 5|1 6|1 7|||2 5|2 6|2 7|2 8||
|+---+---+---+---+---+|+---+---+---+---+---+|+---+---+---+---+|
+---------------------+---------------------+-----------------+
   #&>ixs
5 5 4
   ]vals=. (#&>ixs)#2{"1 abk
3 3 3 3 3 7 7 7 7 7 1 1 1 1

Where will we be inserting? Do the lengths match for what we are inserting and how many indexes we have?

   
   #whIns=. ;<"1&.>((i.#ixs),.&.><:&.>ixs)
14
   #vals
14

Start with a table of zeros:

   ((#ixs),#v)$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

Insert the repetitions where they are supposed to go:

   (vals) whIns}((#ixs),#v)$0
3 3 3 3 3 0 0 0 0
0 0 0 7 7 7 7 7 0
0 0 0 0 0 1 1 1 1

Sum the rows and find the maximum:

   +/(vals) whIns}((#ixs),#v)$0
3 3 3 10 10 8 8 8 1
   >./+/(vals) whIns}((#ixs),#v)$0
10

Bringing it all together:

solveCrush=: 3 : 0
   ixs=. (0{"1 y)+&.>i.&.>>:-/"1]1 0{"1 y
   'min max'=. (<./,>./),0 1{"1 y
   v=. min+i.>:max-min
   vals=. (#&>ixs)#2{"1 y
   whIns=. ;<"1&.>((i.#ixs),.&.><:&.>ixs)
   >./+/(vals) whIns}((#ixs),#v)$0
)

Checking our work:

  solveCrush abk

10

  solveCrush 1 2 100,2 5 100,:3 4 100

200

Python Boilerplate for Solution

#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'arrayManipulation' function below.
#
# The function is expected to return a LONG_INTEGER.
# The function accepts following parameters:
#  1. INTEGER n
#  2. 2D_INTEGER_ARRAY queries
#

def arrayManipulation(n, queries):
    # Write your code here

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')
    first_multiple_input = input().rstrip().split()
    n = int(first_multiple_input[0])
    m = int(first_multiple_input[1])
    queries = []
    for _ in range(m):
        queries.append(list(map(int, input().rstrip().split())))
    result = arrayManipulation(n, queries)
    fptr.write(str(result) + '\n')
    fptr.close()

Languages Supported

Here is the list of languages currently supported by the HackerRank competitions. There are 26 in all but not an array language in sight.

Languages supported by HackerRank.jpg