NYCJUG/2022-03-08
Meeting Agenda for NYCJUG 20220308
Beginner's regatta
Counting Things in Order
Let's say we want to count the letters in a piece of text.
text=. 'Fourscore and seven years ago, our fathers brought forth upon this continent a new nation conceived in liberty and dedicated to the proposition that all men are created equal.' #/.~text 1 14 5 11 6 6 18 28 13 14 7 2 2 2 1 2 15 6 2 3 9 1 4 1 1 1
We counted something but this looks like a useless answer unless we can link the counts to what is being counted. Since what we mean to count are the unique items, what are these?
~.text Foursce andvyg,fthbpiwlmq.
The Key Piece
The key to this problem is using key (/.). Key is an adverb that takes two or three arguments. is most concisely defined here.
x u/.y ↔ (=x) u@# y , that is, items of x specify keys for corresponding items of y and u is applied to each collection of y having identical keys.
In this case, our verb u is tally (#); both x and y are the same thing: we are using the letters in the text as the keys to the letters in the text.
Let's also append the unique letters to the counts to clarify the relation between the two.
(<"0 ~.text),:<"0 #/.~text +-+--+-+--+-+-+--+--+--+--+-+-+-+-+-+-+--+-+-+-+-+-+-+-+-+-+ |F|o |u|r |s|c|e | |a |n |d|v|y|g|,|f|t |h|b|p|i|w|l|m|q|.| +-+--+-+--+-+-+--+--+--+--+-+-+-+-+-+-+--+-+-+-+-+-+-+-+-+-+ |1|14|5|11|6|6|18|28|13|14|7|2|2|2|1|2|15|6|2|3|9|1|4|1|1|1| +-+--+-+--+-+-+--+--+--+--+-+-+-+-+-+-+--+-+-+-+-+-+-+-+-+-+
Comparing Counts of Different Texts
There, done, but maybe not entirely. What if we want to compare these counts to those for another piece of text which has a different set of unique letters?
text2=. 'Now we are engaged in a great civil war, testing whether that nation, or any nation so conceived and so dedicated, can long endure.'
Let's tacitly define our expression above to line up the unique items with their counts.
(([: <"0 ~.) ,: [: <"0 #/.~) text2 NB. Summarize the above, avoid duplicating the argument +-+-+-+--+--+--+-+--+-+-+-+-+-+-+-+-+-+-+-+-+-+ |N|o|w| |e |a |r|n |g|d|i|t|c|v|l|,|s|h|y|u|.| +-+-+-+--+--+--+-+--+-+-+-+-+-+-+-+-+-+-+-+-+-+ |1|8|4|23|14|12|6|13|5|7|8|9|5|2|2|3|3|3|1|1|1| +-+-+-+--+--+--+-+--+-+-+-+-+-+-+-+-+-+-+-+-+-+
We must have the alphabet already defined somewhere...
names_j_ 0 Alpha AlphaNum Boxes Browser Browser_nox CasePaths Cwh DirTreeX Displayload EPSReader Editor Editor_nox ... Alpha_j_ ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
We have both Alpha and AlphaNum in the j namespace.
Let's use this alphabet to order and restrict the domain of what we are counting; also, let's work just with uppercase letters.
ALPH=: 26{.Alpha_j_
sumIC=: (([: <"0 ~.) ,: [: <"0 #/.~) NB. Summarize items, counts
We also have a standard verb to convert text to uppercase:
toupper
3 : 0`((a. (97+i.26)}~'ABCDEFGHIJKLMNOPQRSTUVWXYZ') { ~ a. i. ])@.(2 = 3!:0)
x=. I. 26 > n=. ((97+i.26){a.) i. t=. ,y
($y) $ ((x{n) { (65+i.26){a.) x}t
)
We define a verb to uppercase our argument and eliminate any characters not in our uppercase alphabet.
restrictDomain=: (26{.Alpha_j_)&(]-. -.~)@:toupper
restrictDomain text
FOURSCOREANDSEVENYEARSAGOOURFATHERSBROUGHTFORTHUPONTHISCONTINENTANEWNATIONCONCEIVEDINLIBERTYANDDEDICATEDTOTHEPROPOSITIONTHATALLMENARECREATEDEQUAL
The (]-. -.~) trick is a good one. Explicitly it looks like this: 3 : 'y-.y-.x' . This removes all the items of x from y, giving us all the characters we want to dis-allow, then removes those from y so we end up with only the things in y we want. This way we only have to specify what we need, not what we don't need. So, in our use of it, we remove all the uppercase letters from our text to specify all the characters we don't want, then remove these from our text so we have only uppercase letters remaining.
Finishing Up
Bringing together the definitions above and applying them to both our texts:
sumIC&>restrictDomain&.>text;text2 +--+--+-+--+--+-+--+--+--+-+-+-+-+--+-+-+-+-+-+-+-+-+ |F |O |U|R |S |C|E |A |N |D|V|Y|G|T |H|B|P|I|W|L|M|Q| +--+--+-+--+--+-+--+--+--+-+-+-+-+--+-+-+-+-+-+-+-+-+ |3 |14|5|11|6 |6|18|13|14|7|2|2|2|15|6|2|3|9|1|4|1|1| +--+--+-+--+--+-+--+--+--+-+-+-+-+--+-+-+-+-+-+-+-+-+ +--+--+-+--+--+-+--+--+--+-+-+-+-+--+-+-+-+-+-+-+-+-+ |N |O |W|E |A |R|G |D |I |T|C|V|L|S |H|Y|U| | | | | | +--+--+-+--+--+-+--+--+--+-+-+-+-+--+-+-+-+-+-+-+-+-+ |14|8 |4|14|12|6|5 |7 |8 |9|5|2|2|3 |3|1|1| | | | | | +--+--+-+--+--+-+--+--+--+-+-+-+-+--+-+-+-+-+-+-+-+-+
This points up another problem: we are obscuring the common basis on which we want to count. We can enforce this common basis by appending the letters we want to count to each text list, counting their occurrences, then subtracting one from the counts to reduce by the common basis we added, one of each.
sumIC=: (26{.Alpha_j_)&(13 : '(<"0 x),:<"0 <:#/.~ x,y') NB. Summarize items, counts for uppercase letters.
sumIC&>restrictDomain&.>text;text2
+--+-+-+-+--+-+-+-+-+-+-+-+-+--+--+-+-+--+-+--+-+-+-+-+-+-+
|A |B|C|D|E |F|G|H|I|J|K|L|M|N |O |P|Q|R |S|T |U|V|W|X|Y|Z|
+--+-+-+-+--+-+-+-+-+-+-+-+-+--+--+-+-+--+-+--+-+-+-+-+-+-+
|13|2|6|7|18|3|2|6|9|0|0|4|1|14|14|3|1|11|6|15|5|2|1|0|2|0|
+--+-+-+-+--+-+-+-+-+-+-+-+-+--+--+-+-+--+-+--+-+-+-+-+-+-+
+--+-+-+-+--+-+-+-+-+-+-+-+-+--+--+-+-+--+-+--+-+-+-+-+-+-+
|A |B|C|D|E |F|G|H|I|J|K|L|M|N |O |P|Q|R |S|T |U|V|W|X|Y|Z|
+--+-+-+-+--+-+-+-+-+-+-+-+-+--+--+-+-+--+-+--+-+-+-+-+-+-+
|12|0|5|7|14|0|5|3|8|0|0|2|0|14|8 |0|0|6 |3|9 |1|2|4|0|1|0|
+--+-+-+-+--+-+-+-+-+-+-+-+-+--+--+-+-+--+-+--+-+-+-+-+-+-+
Now we can count different sets of items but easily compare them on a common basis.
Show-and-tell
Dan showed us some work he's done on HackerRank that showcases the beauty of J.
The Beauty of J
Both solutions are examples of the beauty of J (and other array languages).
Specifically, being able to work with an array or matrix of data without first knowing its size.
HackerRank functions J script Media:NYCJUG_2022-03-08_HackerRank.ijs and test data Media:Test_Data_f_HackerRank.txt
HackerRank Array Manipulation
https://www.hackerrank.com/challenges/crush/problem Media:crush-English.pdf
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.
This really looks like something better done as a matrix.
From the HackerRank problem:
(the problem also included a first line giving the maximum number of columns, and the number of operations--which will become rows. We will see that using a matrix we do not need this information)
1 5 3 4 8 7 6 9 1
The matrix above becomes this:
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
We'll do it line by line
In the first line (1 5 3) positions 1 through 5 will be 3's
We can look at this as making a vector of 5 3's, 1 is added to the difference of the 2 numbers and is used to reshape the last number.
(>: -~/ 1 5) $ 3 3 3 3 3 3
We may need to add leading 0's (for lines that don't start with 1)
_8{. (>: -~/ 4 8) $ 7
0 0 0 7 7 7 7 7
Writing this as a function:
{{(- 1 { y) {. (>: -~/ 2{. y) $ (2 { y)}} 4 8 7
]abk=. 3 3 $ 1 5 3 4 8 7 6 9 1
1 5 3
4 8 7
6 9 1
{{(- 1 { y) {. (>: -~/ 2{. y) $ (2 { y)}} each < " 1 abk
┌─────────┬───────────────┬─────────────────┐
│3 3 3 3 3│0 0 0 7 7 7 7 7│0 0 0 0 0 1 1 1 1│
└─────────┴───────────────┴─────────────────┘
We don't need to know the max size, we just unbox. The number of rows is dictated by the number of rows from the input.
>{{(- 1 { y) {. (>: -~/ 2{. y) $ (2 { y)}} each < " 1 abk
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
Then it's plus reduce and scan for the max value
>./ +/ >{{(- 1 { y) {. (>: -~/ 2{. y) $ (2 { y)}} each < " 1 abk
10
As a function:
solveCrush=: {{>. / +/ > {{(- 1 { y) {. (>: -~/ 2{. y) $ (2 { y)}} each < " 1 y}}
solveCrush 1 2 100,2 5 100,:3 4 100
200
Code to show the steps: (we'll use infix to allow the data to be passed as a vector instead of a matrix)
showSteps=: {{ {{ ,. (< y), (<>y), (<+/>y), (< >./ +/ >y)}} {{(- 1 { y) {. (>: -~/ 2{. y) $ (2 { y)}} each _3 <\ y}}
First, we'll use our matrix, abk
showSteps ,abk ┌─────────────────────────────────────────────┐ │┌─────────┬───────────────┬─────────────────┐│ ││3 3 3 3 3│0 0 0 7 7 7 7 7│0 0 0 0 0 1 1 1 1││ │└─────────┴───────────────┴─────────────────┘│ ├─────────────────────────────────────────────┤ │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 │ ├─────────────────────────────────────────────┤ │3 3 3 10 10 8 8 8 1 │ ├─────────────────────────────────────────────┤ │10 │ └─────────────────────────────────────────────┘
We'll do the other 2 sample inputs
showSteps 1 2 100 2 5 100 3 4 100 ┌───────────────────────────────────────┐ │┌───────┬─────────────────┬───────────┐│ ││100 100│0 100 100 100 100│0 0 100 100││ │└───────┴─────────────────┴───────────┘│ ├───────────────────────────────────────┤ │100 100 0 0 0 │ │ 0 100 100 100 100 │ │ 0 0 100 100 0 │ ├───────────────────────────────────────┤ │100 200 200 200 100 │ ├───────────────────────────────────────┤ │200 │ └───────────────────────────────────────┘ showSteps 2 6 8 3 5 7 1 8 1 5 9 15 ┌──────────────────────────────────────────────────────────────┐ │┌───────────┬─────────┬───────────────┬──────────────────────┐│ ││0 8 8 8 8 8│0 0 7 7 7│1 1 1 1 1 1 1 1│0 0 0 0 15 15 15 15 15││ │└───────────┴─────────┴───────────────┴──────────────────────┘│ ├──────────────────────────────────────────────────────────────┤ │0 8 8 8 8 8 0 0 0 │ │0 0 7 7 7 0 0 0 0 │ │1 1 1 1 1 1 1 1 0 │ │0 0 0 0 15 15 15 15 15 │ ├──────────────────────────────────────────────────────────────┤ │1 9 16 16 31 24 16 16 15 │ ├──────────────────────────────────────────────────────────────┤ │31 │ └──────────────────────────────────────────────────────────────┘
And for fun, we'll increase the number of rows in the previous problem from 9 to 12 (second to last item in vector)
showSteps 2 6 8 3 5 7 1 8 1 5 12 15 ┌───────────────────────────────────────────────────────────────────────┐ │┌───────────┬─────────┬───────────────┬───────────────────────────────┐│ ││0 8 8 8 8 8│0 0 7 7 7│1 1 1 1 1 1 1 1│0 0 0 0 15 15 15 15 15 15 15 15││ │└───────────┴─────────┴───────────────┴───────────────────────────────┘│ ├───────────────────────────────────────────────────────────────────────┤ │0 8 8 8 8 8 0 0 0 0 0 0 │ │0 0 7 7 7 0 0 0 0 0 0 0 │ │1 1 1 1 1 1 1 1 0 0 0 0 │ │0 0 0 0 15 15 15 15 15 15 15 15 │ ├───────────────────────────────────────────────────────────────────────┤ │1 9 16 16 31 24 16 16 15 15 15 15 │ ├───────────────────────────────────────────────────────────────────────┤ │31 │ └───────────────────────────────────────────────────────────────────────┘
HackerRank Encryption
https://www.hackerrank.com/challenges/encryption/problem Media:encryption-English.pdf
An English text needs to be encrypted using the following encryption scheme. First, the spaces are removed from the text. Put the characters into a matrix that is nearly square. Where the number of characters does not form a perfect square, the number of columns can be greater than the number of rows. Each column becomes a 'word'
have a nice day
becomes
haveaniceday
then a matrix
have anic eday
(spaced out to make the columns easier to read)
h a v e a n i c e d a y
and the columns become the 'words'
hae and via ecy
The problem says to take the number of characters, take the square root of that number and apply floor to get the rows, and ceiling to get the columns. (already this looks like something for J or APL.)
First perform a test to see if the rows x columns is larger than the number of characters. (an example of where this procedure fails is a number slightly smaller than a square: 8, 399, etc.)
With J, it's a bit easier. We will use the ceiling of the square root of the length to get the columns. Infix will do the rest of making the matrix.
Remove spaces
' ' -.~ 'if man was meant to stay on the ground god would have given us roots' ifmanwasmeanttostayonthegroundgodwouldhavegivenusroots
To get the number of columns, round up the square root of the length
{{>. (#y) ^ 0.5}} ' ' -.~ 'if man was meant to stay on the ground god would have given us roots'
8
Use that number to reformat into a matrix (using infix)
{{ (- >. (#y) ^ 0.5) [ \ y }} ' ' -.~ 'if man was meant to stay on the ground god would have given us roots'
ifmanwas
meanttos
tayonthe
groundgo
dwouldha
vegivenu
sroots
Transpose
|: {{ (- >. (#y) ^ 0.5) [ \ y }} ' ' -.~ 'if man was meant to stay on the ground god would have given us roots'
imtgdvs
fearwer
mayoogo
anouuio
ntnnlvt
wttddes
aohghn
sseoau
Box on rows and remove spaces again (some rows will have trailing spaces).
(' ' -.~ ]) each < " 1 |: {{ (- >. (#y) ^ 0.5) [ \ y }} ' ' -.~ 'if man was meant to stay on the ground god would have given us roots'
┌───────┬───────┬───────┬───────┬───────┬───────┬──────┬──────┐
│imtgdvs│fearwer│mayoogo│anouuio│ntnnlvt│wttddes│aohghn│sseoau│
└───────┴───────┴───────┴───────┴───────┴───────┴──────┴──────┘
Add spaces between items and raze.
; {{<(>x), ' ', (>y)}}/ (' ' -.~ ]) each < " 1 |: {{ (- >. (#y) ^ 0.5) [ \ y }} ' ' -.~ 'if man was meant to stay on the ground god would have given us roots'
imtgdvs fearwer mayoogo anouuio ntnnlvt wttddes aohghn sseoau
As a function
hackerencode=: {{; {{<(>x), ' ', (>y)}}/ (' ' -.~ ]) each < " 1 |: {{ (- >. (#y) ^ 0.5) [ \ y }} ' ' -.~ y}}
hackerencode 'if man was meant to stay on the ground god would have given us roots'
imtgdvs fearwer mayoogo anouuio ntnnlvt wttddes aohghn sseoau
hackerencode 'haveaniceday'
hae and via ecy
hackerencode 'chillout'
clu hlt io
Now let's make a function to display the steps.
showEncrypt=: {{ {{,. (<y),(<|: y),(<(' ' -.~ ]) each < " 1 |: y),(<;{{<(>x), ' ', (>y)}}/ (' ' -.~ ]) each < " 1 |: y)}} {{{{ (- >. (#y) ^ 0.5) [ \ y }} ' ' -.~ y}} y}}
showEncrypt 'if man was meant to stay on the ground god would have given us roots'
┌───────────────────────────────────────────────────────────────┐
│ifmanwas │
│meanttos │
│tayonthe │
│groundgo │
│dwouldha │
│vegivenu │
│sroots │
├───────────────────────────────────────────────────────────────┤
│imtgdvs │
│fearwer │
│mayoogo │
│anouuio │
│ntnnlvt │
│wttddes │
│aohghn │
│sseoau │
├───────────────────────────────────────────────────────────────┤
│┌───────┬───────┬───────┬───────┬───────┬───────┬──────┬──────┐│
││imtgdvs│fearwer│mayoogo│anouuio│ntnnlvt│wttddes│aohghn│sseoau││
│└───────┴───────┴───────┴───────┴───────┴───────┴──────┴──────┘│
├───────────────────────────────────────────────────────────────┤
│imtgdvs fearwer mayoogo anouuio ntnnlvt wttddes aohghn sseoau │
└───────────────────────────────────────────────────────────────┘
showEncrypt 'have a nice day'
┌─────────────────┐
│have │
│anic │
│eday │
├─────────────────┤
│hae │
│and │
│via │
│ecy │
├─────────────────┤
│┌───┬───┬───┬───┐│
││hae│and│via│ecy││
│└───┴───┴───┴───┘│
├─────────────────┤
│hae and via ecy │
└─────────────────┘
showEncrypt 'feed the dog'
┌───────────────┐
│feed │
│thed │
│og │
├───────────────┤
│fto │
│ehg │
│ee │
│dd │
├───────────────┤
│┌───┬───┬──┬──┐│
││fto│ehg│ee│dd││
│└───┴───┴──┴──┘│
├───────────────┤
│fto ehg ee dd │
└───────────────┘
showEncrypt 'chill out'
┌────────────┐
│chi │
│llo │
│ut │
├────────────┤
│clu │
│hlt │
│io │
├────────────┤
│┌───┬───┬──┐│
││clu│hlt│io││
│└───┴───┴──┘│
├────────────┤
│clu hlt io │
└────────────┘
Genetic Algorithm
We started to look at genetic algorithms (GAs) at an earlier meeting but punted on actually implementing one because the problem given was so easy to solve by looking at all possible solutions. However, this doesn't help someone who wants an example of a GA in J so we addressed this long overdue lack by implementing an algorithm based on the C# code referenced in the earlier meeting.
The Problem
As stated on the website:
...for this example, I have used a simple card splitting exercise, which is as detailed here:
- You have 10 cards numbered 1 to 10
- You have to divide them into two piles so that:
- The sum of the first pile is as close as possible to 36.
- And the product of all in the second pile is as close as possible to 360.
In our earlier approach to this problem, we were running short on time to implement a proper GA, so, upon noticing how very small the search space is, we instead showed how to implement a brute-force version that runs very quickly. However, implementing the GA in J was not that difficult and it highlighted some subtleties in the C# implementation we translated into J. We completed our initial implementation in J fairly quickly, in about an hour and a half, but this was due in large part to having the existing implementation to guide us through a number of ambiguities in the algorithm.
Necessity of GA as Simple Problem Grows Larger
So we see that we two fundamentally different details in our two versions: simpleGA0 more closely mimics the C# versions by works on only a pair of randomly-chosen genes at a time whereas the more J-like version - simpleGA called by iterateGA - works on the whole set of genes at once.
We see that the original universe, from the article, of only 10 numbers is trivially easy to solve without a genetic algorithm:
SPsolution (>:i.10);36;360;5
+----------+
|2 7 8 9 10|
+----------+
|1 3 4 5 6 |
+----------+
6!:2 'SPsolution (>:i.10);36;360;5'
0.0001558
Where SPsolution here is similar to what we came up with the last time we looked at this problem. We see that it also reaches a solution very quickly.
SPsolution=: 3 : 0
'set sumtarg prodtarg nps'=. y NB. Set of numbers, targets for sum and product, #/set
set=. ,set
cmb=. <"1 set{~nps comb #set NB. All combinations
ccmb=. (<set)-.&.>cmb NB. Complement of cmb
approxSum=. ((>:sumtarg)&>:*.(<:sumtarg)&<:)&>(+/&>cmb)
approxProd=. ((10+prodtarg)&>:*.(prodtarg-10)&<:)&>(*/&>ccmb)
whsoln=. I. approxProd*.approxSum
whsoln&{&>(<cmb),<ccmb
)
However, this exhaustive methods exhausts itself pretty quickly as our universe increases in size.
(10) 6!:2 'SPsolution (>:i.15);50;27941760'
0.0117826
(10) 6!:2 'SPsolution (>:i.20);64;12125707776000'
0.84209
0.84209%0.0117826
71.4689
SPsolution (>:i.30);332;11412430848
|out of memory: SPsolution
| pairs=.}.&.>(0 1,"1 abc) </."1]0 0,set
|SPsolution[3]
7!:0''
171692986240
10^.7!:0''
11.2348
We see here that increasing the solution space from 15 to 20, an increase of 1/3, increases the time required by more than a factor of 70. Increasing the universe to 30 causes this solution to run out memory entirely. We will use the universe of size 30 for our testing to show an advantage of genetic algorithms.
Initial J Implementation
We defined the deck of number cards like this even though it turns out that the C# example never explicitly does this.
]CARDS=: >:i.10 1 2 3 4 5 6 7 8 9 10
However, doing it this way gives more flexible code in case we want to try other similar examples whereas changing the C# example would require code changes in multiple places.
In keeping with our idea of closely mimicking the example, we first define a number of global variables:
TARGETS=: 36 360 NB. C# code does not do this: it hard-codes the two values throughout the code. 'POP LEN MUT REC END'=: 30,(#CARDS),0.1,0.5,1000 NB.
Per the article, these are:
- POP: Size of gene pool
- LEN: length of genome
- MUT: mutation likelihood
- REC: recombination likelihood
- END: maximum number of trials (called "tournaments" in the article).
We represent the genes as Boolean partition vectors. Using the above globals we can create a set of genes like this:
$genes=. (POP,LEN)?@$2
30 10
3{.genes NB. Look at first three genes
1 1 1 0 0 1 1 1 1 0
0 0 0 1 0 1 0 1 0 0
1 0 1 1 0 1 1 1 0 1
]xx=. (3{.genes)</."1 CARDS
+--------------+------+
|1 2 3 6 7 8 9 |4 5 10|
+--------------+------+
|1 2 3 5 7 9 10|4 6 8 |
+--------------+------+
|1 3 4 6 7 8 10|2 5 9 |
+--------------+------+
{{(+/>0{y),*/>1{y}}"1 xx NB. Sum and product of each pair
36 200
37 192
39 90
Initializing Parameters
The parameters mentioned above are initialized this way in C#:
//population size
private int POP = 30;
//geneotype
private int LEN = 10;
//mutation rate, change it have a play
private double MUT = 0.1;
//recomination rate
private double REC = 0.5;
//how many tournaments should be played
private double END = 1000;
//the sum pile, end result for the SUM pile
//card1 + card2 + card3 + card4 + card5, MUST = 36 for a good GA
private double SUMTARG = 36;
//the product pile, end result for the PRODUCT pile
//card1 * card2 * card3 * card4 * card5, MUST = 360 for a good GA
private double PRODTARG = 360;
//the genes array, 30 members, 10 cards each
private int[,] gene = new int[30, 10];
//used to create randomness (Simulates selection process in nature)
//randomly selects genes
Random rnd = new Random();
Notice how the assignment of the genes "gene = new int[30, 10]" uses hard-coded values of "30" and "10". These are in fact the same as the values for POP and LEN above but, due to the limitations of compiled languages, the information in those variables cannot be re-used in the instantiation without more code so we get duplicated values, hence more chance for errors when we update the parameters.
In J, this initialization might be something like this:
if. -.nameExists 'CARDS' do. CARDS=: >:i.10 end. if. -.nameExists 'POP' do. 'POP LEN MUT REC END'=: 30,(#CARDS),0.1,0.5,1000 NB. Parms per article: NB. Population, length of genotype, mutation probability, recombination probability, NB. end of number of iterations to try. end. TARGETS=: 36 360 NB. sum and product targets
The if statements allow us to set different values for these globals, then reload the code without overwriting them. Notice too how the value of LEN is tied to the number of "cards" to avoid unnecessary repetition of values that should be the same.
Scoring
Here we take a look at the C# scoring code versus the initial J version.
C#
//evaluate the the nth member of the population
//@param n : the nth member of the population
//@return : the score for this member of the population.
//If score is 0.0, then we have a good GA which has solved
//the problem domain
private double evaluate(int n)
{
//initialise field values
int sum = 0, prod = 1;
double scaled_sum_error, scaled_prod_error, combined_error;
//loop though all genes for this population member
for (int i = 0; i < LEN; i++)
{
//if the gene value is 0, then put it in the sum (pile 0),
//and calculate sum
if (gene[n,i] == 0)
{
sum += (1 + i);
}
//if the gene value is 1, then put it in the product (pile 1),
//and calculate sum
else
{
prod *= (1 + i);
}
}
//work out how good this population member is, based on an overall error
//for the problem domain
//NOTE : The fitness function will change for every problem domain.
scaled_sum_error = (sum - SUMTARG) / SUMTARG;
scaled_prod_error = (prod - PRODTARG) / PRODTARG;
combined_error = Math.Abs(scaled_sum_error) + Math.Abs(scaled_prod_error);
return combined_error;
}
J
eval=: 4 : '(+/y#x),*/(-.y)#x' NB. Evaluate in TARGETS order score=: 3 : '+/|TARGETS%~(CARDS eval y)-TARGETS'"1
The J version suffers from infestation by globals (as taken from the C# code) but we can refine that later.
Recombination and Mutation
The two basic transforms we apply to our "genes" are recombination and mutation. Recombination substitutes some bits from a more highly scored variant into one with a lower score. Mutation randomly flips bits in a gene, more if MUT is a higher number, fewer if it is lower.
Here we look briefly at the C# implementation, then the J one.
C#
This is the core of the main run method chosen to most closely correspond to our J version of it below.
for (int tournamentNo = 0; tournamentNo < END; tournamentNo++)
{
//pull 2 population members at random
a = (int)(POP * rnd.NextDouble());
b = (int)(POP * rnd.NextDouble());
//have a fight, see who has best genes
if (evaluate(a) < evaluate(b))
{
Winner = a;
Loser = b;
}
else
{
Winner = b;
Loser = a;
}
//Possibly do some gene jiggling, on all genes of loser
//again depends on randomness (simulating the
//natural selection
//process of evolutionary selection)
for (int i = 0; i < LEN; i++)
{
//maybe do some recombination
if (rnd.NextDouble() < REC)
gene[Loser, i] = gene[Winner, i];
//maybe do some muttion
if (rnd.NextDouble() < MUT)
gene[Loser, i] = 1 - gene[Loser, i];
//then test to see if the new population member
//is a winner
if (evaluate(Loser) == 0.0)
display(tournamentNo, Loser);
}
}
J
Again, this code is infested with globals in order to more closely shadow the C# from which it was copied.
Notice how the J code is considerably more concise than the C# code because of the ease with which we can handle arrays.
NB.* recombine: losers recombine winners -> better losers
recombine=: 4 : 0"1
wh2c=. I. REC>:0?@$~{:$y NB. Which to combine
x=. (wh2c{y) wh2c}x NB. some winner genes->loser
)
NB.* mutate: randomly flip some bits based on global MUT.
mutate=: 3 : 0"1
wh2m=. MUT>:0?@$~#y NB. Which to mutate
y~:wh2m
)
A Note on the Original Algorithm
Notice how the C# code above randomly selects a pair of genes at a time to compare, recombine, and mutate. In our J implementation, it was much easier to break the entire gene pool into winners and losers then do this gene jiggling en-masse. This introduces some important discrepancies between the implementation which we will explore later.
Also, when I was testing the original version of this code, I noticed that duplicate genes would show up randomly. Since the C# code works through the "scalar keyhole", that author probably never noticed the wasted effort from using unnecessary duplicates but I did because I was looking at the entire population of genes at a time. For this reason, I improved the J rendition of that code by nubbing the genes and topping them off with new random genes.
J Version of Original
Here we try to replicate the C# code closely in J.
NB.* simpleGA0: more closely mimic the algo from the article by randomly
NB. selecting pairs of genes to combine and mutate; we still differ from
NB. that algo because we stop once we find a solution. Also, we make the
NB. maximum number of iterations a parameter instead of relying on global "END".
simpleGA0=: 3 : 0
'max genes'=. y NB. Max iterations, set of genes, index of iteration
for_ix. i. max do. NB. at which solution found.
g2=. genes{~w2=. 2?#genes NB. 2 random genes
ord=. \:score g2 NB. ordered
g2=. g2{~ord NB. worse to better
new=. mutate recombine/g2 NB. gene jiggling
genes=. new ({.ord{w2)}genes NB. Replace worse with new
if. 0=score new do. NB. Finish if perfect score
ix;<genes NB. return # of earliest success & genes
return.
end.
end.
max;<genes
NB.EG 'ct genes'=. simpleGA0 (POP,LEN)?@$2
)
Notice that the C# version prints a result if it finds a winner but keeps on processing whereas our J version of this algorithm halts once it finds a perfect score. Notice too that the C# code is checking the score after every single gene recombination instead of applying the complete recombination, then checking.
More J-like Version
Compare the above with the more natural J formulation here where we mutate and recombine all the winners with all the losers in one go instead of a random pair at a time.
simpleGA=: 3 : 0
pop=. #genes=. y
wix=. (<.pop%2){./:score genes NB. winner indexes of best half
lix=. (i.pop)-.wix NB. loser indexes of worst half
new=. (lix{genes) recombine wix{genes NB. Assume (#lix)=#wix
new=. mutate new
genes=. (wix{genes),new
NB.EG simpleGA (POP,LEN)?@$2
)
The above code represents only a single pass. We handle the iteration with the following adverb.
NB.* iterateGA: apply genetic algo repeatedly until we have a winner or
NB. have repeated as much as we have specified.
iterateGA=: 1 : 0
'max genes'=. y
pop=. #genes [ ct=. 0
while. (-.0 e. score genes) *. (ct<max) do.
genes=. ~.u genes NB. Unique genes
if. pop>#genes do.
genes=. genes,((pop-#genes),{:$genes)?@$2 NB. add random new genes to maintain population
end.
if. 0 e. score genes do. break. end. NB. Break early if we have a solution
ct=. >:ct
end.
ct;<genes
NB.EG 'ct genes'=. (simpleGA iterateGA) 1000;<(POP,LEN)?@$2 NB. No more than 1000 iterations.
)
The "NB.EG" comment at the end gives an example of how we can iterate this code until we either reach a solution or hit the maximum number of runs. Notice how we reduce the gene pool to only the unique instances but top it off with new random genes if the pool falls below the stipulated population level.
We will compare the performance of these two variants and another a little further on.
Tuning Parameters
We have seen that we set a number of arbitrary values for some parameters, set as global variables, which control how quickly we reach a solution on average. For our testing these are
POP 2000 LEN 30 MUT 0.05 REC 0.7 END 2e6 TARGETS 332 11412430848
The important parameters MUT and REC, the likelihoods of mutation and recombination, are quite different from those chosen for the original essay on the C# implementation of a genetic algorithm for this toy problem. However, these are values that my testing has convinced me are better starting points for the algorithm to reach a solution most quickly.
Comparing Versions
One difference we notice right away between the version coded to be (nearly) the same as the C# implementation is that it takes a great many iterations to reach a solution.
C# Algorithm
The way this algorithm is designed, it does very little work per iteration so each iteration runs very quickly. However, this means that it also requires many iterations to stand a chance of finding an exact solution.
6!:2 '''ct genes0''=. simpleGA01 1e6;<(POP,LEN)?@$2' NB. No more than a million iterations.' 17.5661 ct 1000000
We see that we hit the maximum number of iterations. Taking a look at the best set of genes so far, we see that we are close to a solution.
(]i.<./) score genes0 NB. Where is first best score?
175
CARDS eval 175{genes0
332 11417656320
TARGETS
332 11412430848
So we are pretty close, but not exact and we know this problem has an exact solution because we chose the targets from a randomly generated set of genes. Fortunately we return the evolved set of genes so we can continue from where we left off with another set of iterations.
6!:2 '''ct genes0''=. simpleGA01 1e6;genes0' NB. Another maximum million iterations starting from previous
3.12089
ct
177476
(]i.<./) score genes0 NB. Where is first best score?
1074
CARDS eval 1074{genes0
332 11412430848
TARGETS
332 11412430848
Now we have an exact solution but it took over a million iterations, as is typical for this version.
Original J Algorithm
The version of this designed to be more J-like does a lot more work every iteration as it scores all the genes every time, ranks them from winners to losers, then combines each loser with a winner.
6!:2 '''ct genes1''=. (simpleGA iterateGA) 2e4;<(POP,LEN)?@$2 NB. No more than 20,000 iterations.' 8.42645 ct 1043
We see that this took about 8 1/2 seconds to run 1,043 iterations. We also see that our solution is exact.
0 e. score genes1
1
(score genes1)i.0
1701
CARDS eval 1701{genes1
332 11412430848
TARGETS
332 11412430848
So this more expensive algorithm compensates for its expense by finding a solution in fewer iterations.
Advanced topics
Solving the Traveling Salesman Problem with Genetic Algorithms
The earlier GA above solved a made-up problem with little practical use. However, the Traveling Salesman Problem is a well-known, difficult problem with practical applications. Here we will see how to develop a genetic algorithm to solve it.
The Problem
Given a set of "cities" or locations to visit, what is the most efficient path to take, visiting each location once, to visit all of them?
For instance, here we see 20 randomly-generated points arbitrarily sorted in ascending order plotted to show a path through all of them from beginning to end.
|:pts=. /:~20 2?@$100 NB. Show points transposed for more efficient use of screen space
5 7 10 20 22 30 32 32 35 41 65 66 71 73 82 85 85 92 93 99
81 22 78 0 72 68 15 39 92 81 87 39 98 97 91 7 37 79 62 57
showPts ('Random Path, Distance^2 = ',":totdis2 pts);pts
This gives us this picture:
Where showPts is this:
showPts=: 3 : 0 'tit pts'=. y pd 'itemcolor green;type point;pensize 3;backcolor white' [ pd 'reset' pd j./|:circuit pts NB. First show the points themselves pd 'itemcolor blue;type line;pensize 2' NB. then draw a line through all of them pd j./|:circuit pts [ pd 'title ',tit pd 'show' )
We ensure that the line goes back to the starting point by the application of the "circuit" verb:
NB.* circuit: complete circuit by adding start to end
circuit=: (],[:{.])
We calculate the sum of the square of the distances between each set of points, then total these to get the "distance squared" metric. An accurate distance measure would take the square root of the sum of the distances squared but we avoid the extra cost of taking the square root as a minor economy measure. We can compare distances squared as well as distances since all the numbers are positive so if one distance is greater than another, the square of that distance will also be greater than the square of the other distance.
NB.* dis2adjacent: distance^2 between adjacent points in a list. dis2adjacent=: 13 : '+/"1 *:2-/\ y' NB.* totdis2: total distance^2 for a complete circuit of points. totdis2=: (+/@:dis2adjacent@:circuit)"2
Representing Solutions
What is the range of solutions we might expect? Let's first look at the result of mimicking the parameters given in the C# code we used as a reference. We see here that the best path is substantially better than the worst one. The values of the best path are shown in the first row of complex numbers, where we represent the point pairs as complex numbers for ease of plotting, and the worst path is the second row. However for the purposes of specifying a path, we will work with permutation vectors as our "genes". A permutation vector is a list of integers from zero to one less than the length of the universe in any possible ordering of those indexes into the list of points.
When we looked at this example with only 10 points in an earlier meeting, we solved it with an exhaustive search because that's easy to do with only 10 points, since there are less than !10 (3,628,800) solutions. There are at most !10 because this is the number of permutations of the paths among 10 nodes. Actually, the number of unique paths is quite a bit less than this since there are at least 20 equivalent variants for any given path; i.e. the path "0 1 2 3 4 5 6 7 8 9" has the same length as "1 2 3 4 5 6 7 8 9 0", which is the same as "2 3 4 5 6 7 8 9 0 1" and so on, as well as the same as "9 8 7 6 5 4 3 2 1 0", "8 7 6 5 4 3 2 1 0 9", and so on. Representing the paths as permutation vectors gives us an order in which to visit the points for the problem.
Initial Parameters
As with the other GA above, we set a few global parameters like this:
'POP MUT FLIPMUT REC'=: 1000 0.1 0.1 0.5 NB. population (# of genes to work with at a time), mutation probability, NB. flip mutation probability, recombination probability.
Once we have set these, we can run our basic "evolve" to generate a better path.
6!:2 'genes=. evolve 1000;pts'
1.20714
$genes
1000 20
totdis2 pts{~{.genes NB. Genes (path permutations) are ordered from best to worst.
13532
totdis2 pts{~{:genes NB. versus the worst.
56744
We see that 1000 steps for 1000 genes at a time takes a little over a second and the improvement, from 50,532 to 13,532, is substantial.
One thing I noticed in running this code repeatedly to improve the path length on larger datasets is that line crossings, like the one we see in the upper-right corner above, always seem to indicate that there is improvement to be had in the neighborhood of the crossing.
Further Work
We have only scratched the surface of this promising application of genetic algorithms. There are examples of some of this in the code referenced in the Materials section below. We may extend this work more fully in a future meeting.
Also, the existing code would benefit by getting away from the sloppy practice of relying on numerous global variables which we did to more closely mimic some of the code on which this was based. Even with the little bit of testing I did, varying some of these parameters, I ran into problems impossible to solve because of inadvertent inconsistency between these globals. Some of the recent forum discussions on dictionaries raises an intriguing possibility of at least centrally consolidating these globals.
Learning and Teaching J
Only Writing Programming Languages
We have spoken in the past about how some people in the J community, and elsewhere, seem more interested in writing new programming languages than in using existing ones. We see a similar tendency where people, often J novices, want to change J often in some radical way. This is not limited to J, as we can see in this essay "Fixing APL's trigonometric notation"; this reference is also notable for including an APL character in the URL. The essay also makes mention of the "b." alternatives in J as an example of bad notation. I tend to agree with the author's point on this.
As a recent example of this "radical change" mindset, there was small flurry of J Forum traffic recently about the possibility of making the shape vector of an array be able to take on higher dimensions.
From: Elijah Stone <elronnd@elronnd.net> Date: Thu, Mar 3, 2022 at 5:13 AM Subject: [Jprogramming] Higher-order arrays? To: <programming@jsoftware.com> A little thought exercise I embarked upon. Probably not very clearly expressed, and certainly of no practical use, but I think there are some interesting ideas: Why must the result of $y always be a vector? What would happen if we let it be a higher-ranked array? What would that _mean_? ...
John Randall's reply to this chain may have mercifully cut it off. I was tempted to chime in before he did with the observation that the simplicity of representing the shape of arrays with a vector, especially the inclusion of the empty vector for the shape of a scalar, was one of the first startling and useful insights I remember learning from APL.
This essay about why one should not write a programming language seems somewhat pertinent to the discussion. The warning hinges on the observation that "...once you design a programming language you fall down a rabbit hole so deep you can't even see the light when you look up anymore." I think we see a bit of this all-consuming passion exhibited by these "only-write" programming language advocates.
Limitations of Human Memory
This essay on sources of confusion in coding lays out some of the different obstacles we encounter when writing code. One of these, which the author calls "Capacity-based Confusion" touches on themes well-known to those of us who extoll the virtues of terse code. In particular, the author distinguishes between three types of memory which limit our cognitive capacity:
- Long-term memory (LTM)
- Short-term memory (STM)
- Working memory (WM)
He relates these to some of his previous types of confusion. In the community of terse-language advocates, we often emphasize the last one of these since terse notation helps us better grasp larger concepts by giving us a very small handle with which to represent them. However, the other two types of memory are also helped not only by terseness but by regularity of a notation. If we have to keep track of fewer exceptions, we have cleaner tools of thought which improve our use of memory beyond just our working memory.
Materials
* File:SimpleGA.ijs Complete code for our initial simple genetic algorithm
* File:TSPGA.ijs Complete code for our genetic algorithm to solve the Traveling Salesman Problem
To refine the TSP GA we explain above, we can look at work done on different ways to implement the recombination step, here called crossover:
* Genetic Algorithm for Traveling Salesman Problem with Modified Cycle Crossover Operator
Looking at the types of crossover they mention, it looks like every one of them can be implemented as a very short J expression.
Also, to test our TSP routines for correctness, we can look at a large set of solved datasets:
* TSPLIB datasets with optimal path lengths