NYCJUG/2020-11-10
Meeting Agenda for NYCJUG 20201110
1. Beginner's Regatta: N00b question on how to generate all combinations of four Xs and six Ys 2. Show-and-tell: o John Baker on JOD o David Lambert on J in Python o Will Gajate wrapping up the Fold conjunction 3. Advanced Topics: 4. Learning and Teaching J:
Beginner's regatta
A Question About Combinations
This question was posted on Reddit under r/ProgrammingLanguages:
Question from a noobie I’ve just began looking into permutations and how to consider different combinations of two elements, I was wondering if anyone could run me through it without overclocking my brain :) I’m more specifically trying to find ways of combining 4 Xs and 6 Ys, and Python would be the preferable language :))) Thank you in advance
Here is my reply, starting out in J and ending up with a Python equivalent.
Well, J is my preferred language so I will illustrate this with it but you should be able to implement the idea in your language of choice. So, 4 Xs and 6 Ys are 10 things altogether. Since you have two different things, you can think of all combinations of them as all the 10-digit binary numbers where you have 4 zeros (where zero represents X). The 6 ones represent the 6 Ys. Since there are only two different things and each entry in your list is 10 Boolean digits long, any number with 4 zeros will automatically have 6 ones. In J, we generate the table of all 10-digit binary numbers like this, assigning it to the variable "all10":
all10=. #:i.2^10 NB. All ways to combine two things
This is a 1024x10 table of binary digits, where 1024=2^10. To find all entries that have exactly 4 zeros, we can do this and sum the result to see how many there are:
+/4=0 +/ . = "1 all10 210
So there are 210 entries with 4 zeros (Xs) and 6 ones (Ys). If we extract just these entries, we get a 210x10 table of ones and zeros which we can convert to Xs and Ys by using each of these 210 entries as indexes into a 2-element vector 'XY'. Since this is too long to print in this message, we'll just look at the size of the resulting table using J's shape operator "$":
$'XY'{~all10#~4=0 +/ . = "1 all10 210 10
You should be able to apply this method in Python quite easily once you figure out how to generate the list of 10-digit Booleans. Here is an example of how you might do this, using a list of only 4-digit Booleans so the example will fit in this message. Since there are only 4 digits in this example, we will select all the ones with 2 zeros and 2 ones (= 2 Xs and 2 Ys):
import numpy as np someBools= np.array([(0,0,0,0),(0,0,0,1),(0,0,1,0),(0,0,1,1),(0,1,0,0),(0,1,0,1),(0,1,1,0),(0,1,1,1),(1,0,0,0),(1,0,0,1),(1,0,1,0),(1,0,1,1),(1,1,0,0),(1,1,0,1),(1,1,1,0),(1,1,1,1)]) xy=np.array(['X','Y']) [xy[someBools[x]] for x in range(0,16) if sum(someBools[x])==2] [array(['X', 'X', 'Y', 'Y'], dtype='<U1'), array(['X', 'Y', 'X', 'Y'], dtype='<U1'), array(['X', 'Y', 'Y', 'X'], dtype='<U1'), array(['Y', 'X', 'X', 'Y'], dtype='<U1'), array(['Y', 'X', 'Y', 'X'], dtype='<U1'),array(['Y', 'Y', 'X', 'X'], dtype='<U1')]...
Python "itertools" Solution
The original question was flagged as being inappropriate to the "programmingLanguages" group so was subsequently posted on the r/learningpython group where the single answer was to look at the "itertools" package.
Show-and-tell
JOD
John Baker will walk us through his JOD tool. The material covered can be found here and here.
Examples of jodliterate generated LaTeX is on OverLeaf.com here.
Current JOD resources are available on The JOD Page.
The JOD book is available on Amazon here.
J Language Function Composition for Python
David Lambert will show us work he has been doing to bring something like J's functional composition to Python.
Finishing Up Fold
Will Gajate will fill us in on the final few entries in his table of different kinds of functional folding.
Advanced topics
Sample Programming Interview Question
There's a staircase with N steps, and you can climb 1 or 2 steps at a time. Given N, write a function that returns the number of unique ways you can climb the staircase. The order of the steps matters. For example, if N is 4, then there are 5 unique ways:
- 1,1,1,1
- 2,1,1
- 1,2,1
- 1,1,2
- 2,2
What if, instead of being able to climb 1 or 2 steps at a time, you could climb any number from a set of positive integers X? For example, if X = {1, 3, 5}, you could climb 1, 3, or 5 steps at a time. Generalize your function to take in X.
J Solution
Here is some J code to do the trick:
NB.* nSteps: enumerate possible ways to climb y steps taking them some NB. combination from x allowable steps at a time. nSteps=: 4 : 0 NB. x: vec of allowable step sizes, y: total steps to climb base=. #x=. 0,x NB. One more than # allowable steps at a time lim=. base^y allPoss=. x{~(y$base)#:i.lim ~.(<"1 allPoss#~y=+/"1 allPoss)-.&.>0 )
Here's how it does:
1 2 nSteps 4 +---+-----+-----+-----+-------+ |2 2|1 1 2|1 2 1|2 1 1|1 1 1 1| +---+-----+-----+-----+-------+ 1 3 5 nSteps 8 +---+---+-------+-------+-------+-------+-------+-------+-------+-------+-------+-------+-... |3 5|5 3|1 1 1 5|1 1 3 3|1 1 5 1|1 3 1 3|1 3 3 1|1 5 1 1|3 1 1 3|3 1 3 1|3 3 1 1|5 1 1 1|1... +---+---+-------+-------+-------+-------+-------+-------+-------+-------+-------+-------+-... #1 3 5 nSteps 8 19
However, the performance leaves much to be desired:
6!:2 'aa=. 1 3 5 nSteps 8' 0.0707713 6!:2 'aa=. 1 3 5 nSteps 10' 1.32811 6!:2 'aa=. 1 3 5 nSteps 12' 25.209 2%/\25.209 1.32811 0.0707713 18.9811 18.7662
Each increment of two in the number of steps takes almost 20 times as long as the previous one.
Python Solution
This problem is posted as an interview problem and we know how unlikely it is that most interviewers would allow a J solution so here's the same solution rendered in Python:
def nSteps(x, nsteps): x.insert(0,0) base=len(x) curr=[0 for i in range(nsteps)] # Zero in base 3 with 4 digits lim=base**nsteps ctr=0 tmp=[] while ctr<lim: # count to lim in base (little-endian) for ix in range(0,nsteps): if ix==0: curr[ix]=curr[ix]+1 if base==curr[ix]: curr[ix]=0 if len(curr)>ix+1: curr[ix+1]=curr[ix+1]+1 # Carry one to next column tot=sum([x[ix] for ix in curr]) if tot==nsteps: tmp.append([x[ix] for ix in curr if 0!=x[ix]]) ctr+=1 return set(tuple(rr) for rr in tmp
This gives the same results we saw with J:
nSteps([1,2],4) {(1, 2, 1), (2, 1, 1), (1, 1, 1, 1), (1, 1, 2), (2, 2)} nSteps([1,3,5],8) {(1, 5, 1, 1), (1, 3, 1, 3), (1, 1, 1, 3, 1, 1), (3, 1, 3, 1), (1, 1, 1, 5), (1, ... len(nSteps([1,3,5],8)) 19
The timings are as dismal as those in J:
import time tm0=time.perf_counter() aa=nSteps([1,3,5],8) tm1=time.perf_counter() tm1-tm0 16.18204590003006 tm0=time.perf_counter() aa=nSteps([1,3,5],10) tm1=time.perf_counter() tm1-tm0 26.41135489998851 tm0=time.perf_counter() aa=nSteps([1,3,5],12) tm1=time.perf_counter() tm1-tm0 403.3533136000042 26.41135489998851/16.18204590003006 1.632139413220886 403.3533136000042/26.41135489998851 15.271965983092358
Offered Solution
The solution offered on the site where this problem was posted was the following.
It's always good to start off with some test cases. Let's start with small cases and see if we can find some sort of pattern.
N = 1: [1] N = 2: [1, 1], [2] N = 3: [1, 2], [1, 1, 1], [2, 1] N = 4: [1, 1, 2], [2, 2], [1, 2, 1], [1, 1, 1, 1], [2, 1, 1]
What's the relationship?
The only ways to get to N = 3, is to first get to N = 1, and then go up by 2 steps, or get to N = 2 and go up by 1 step. So f(3) = f(2) + f(1).
Does this hold for N = 4? Yes, it does. Since we can only get to the 4th step by getting to the 3rd step and going up by one, or by getting to the 2nd step and going up by two. So f(4) = f(3) + f(2).
To generalize, f(n) = f(n - 1) + f(n - 2). That's just the Fibonacci sequence!
def staircase(n): if n<=1: return 1 return staircase(n-1)+staircase(n-2)
Of course, this is really slow (O(2^N)) — we are doing a lot of repeated computations! We can do it a lot faster by just computing iteratively:
def staircase(n): a,b = 1,2 for _ in range(n-1): a,b = b,a+b return a
Now, let's try to generalize what we've learned so that it works if you can take a number of steps from the set X. Similar reasoning tells us that if X = {1, 3, 5}, then our algorithm should be f(n) = f(n - 1) + f(n - 3) + f(n - 5). If n < 0, then we should return 0 since we can't start from a negative number of steps.
def staircase(n,X): if n<0: return 0 elif n==0: return 1 else: return sum(staircase(n-x,X) for x in X)
This is again, very slow (O(|X|^N)) since we are repeating computations again. We can use dynamic programming to speed it up.
Each entry cache[i] will contain the number of ways we can get to step i with the set X. Then, we'll build up the array from zero using the same recurrence as before:
def staircase(n,X): cache = [0 for _ in range(n+1)] cache[0] = 1 for i in range(1,n+1): cache[i] += sum(cache[i-x] for x in X if i-x >= 0) return cache[n]
This now takes O(N * |X|) time and O(N) space.
Amuse-Bouche
Estimating Area
Here's a bunch of J code to estimate the area of the red versus the green portion of the circle.
qts'' 2020 10 21 13 45 26.568 load '~Code/imageProcessing.ijs' fsize flnm=. 'E:\amisc\forecasting\BayesVisualization\estimating areas prone to error-colored.jpg' 31215 $img=. read_image flnm 323 378 $img=. 3 rgb img 323 378 3 $2{"1 img 323 378 load 'mystats' grn=. 1{"1 img ~.,grn 251 253 252 250 255 247 249 254 248 246 241 245 244 242 243 150 75 62 58 91 74 65 88 60 67 90 141 69 64 86 159 56 77 152 73 61 70 85 127 144 66 63 87 240 59 89 232 72 76 233 78 93 68 83 145 84 151 148 204 153 238 239 237 103 224 106 181 125 126 80 110 165 ... usus ,grn 0 255 187.448 106.558 323%8 40.375 grn=. 2{"1 img usus ,42}.grn 0 255 165.24 117.512 'Green Plane Bottom 80%' plotHistoMulti ,42}.grn
+/100<,42}.grn 70336 (+/100<,42}.grn)%#,grn 0.576081 (+/100<,grn)%#,grn 0.67928 $grn 323 378 42%323 0.130031 -.42%323 0.869969 (+/100<,42}.grn)%0.87*#,grn 0.662162 red=. 1{"1 img (+/100<,42}.red)%0.87*#,red 0.737692 5 5{.red 251 251 251 251 251 251 251 251 251 251 251 251 251 251 251 251 251 251 251 251 251 251 251 251 251 5 5{.grn 5 5{.grn 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 NB. circleRed=. red* $*./"1 img>240 323 378 +/,*./"1 img>240 79268 #,red 122094 maskWhite=. *./"1 img>240 ((+/ % #)@:,) maskWhite NB. 65% of the image is white 0.649237 grnNW=. grn*-.maskWhite NB. Exclude green plane for white redNW=. red*-.maskWhite NB. Exclude red plane for white (+/100<,grnNW)%#(,-.maskWhite)#,grnNW 0.274647 (+/100<,redNW)%#(,-.maskWhite)#,redNW 0.790696 (],-.)0.274647%0.274647+0.790696 0.257801 0.742199