Programming on my Birthday

As an extension of the last post, I’ve been ramping up applying Python to solving more and more difficult puzzles I find from the puzzle-makers on Twitter, especially Yohaku and 1to9Puzzle. The simple ones are just too easy for the solver to zip through randomly and print out the solution. The challenging work is already done, so it’s time to move on to a more difficult challenge. Thankfully, the puzzlers have us covered.

Here’s a Yohaku puzzle which requires you to fill in the squares with 9 consecutive numbers, with the totals of the rows and columns given.

yohaku_May_27.png

How should we start? Pick random collections of 9 consecutive numbers and crank through all their possible combinations? That would take a while. There’s a way to find out the starting number, as I was reminded by a fellow puzzler who replied to one of the posts. The row totals are 15, 22 and 26. That means if you add up all nine numbers, you get 15 + 22 + 26 = 63. The total of the column sums is also 63. There’s a formula for the sum of an arithmetic sequence:

puzzle_post1.png

S is the sum of the sequence, which we know is 63. n is the number of numbers, which is 9. The only unknowns are a1, which is the first number in the sequence, and an, which is the last number. But the last number we know will be the first number plus 8, so we can fill in the values we know and solve for a1:

puzzle_post2.png

Our starting number is 3. For those of you who may not like the algebraic way of finding the starting number, you can easily add up 9 consecutive numbers using Python, and find out which starting number gives you 63. Like this:

puzzle_post3.png

This confirms the starting number is 3. Now I can just solve the puzzle the same way I did before, by making Python choose a random order of the numbers 3 through 11 and check if they give the correct row and column totals. But this is taking a while! How many different combinations, I mean permutations of those numbers could there be? 9 factorial is only 362,000.

Permutations to the Rescue

We’re probably getting a lot of repetition in the random lists, so there’s a way to generate all the permutations of the numbers 3 through 11 one by one, check them, and move on to the next one without repeating ourselves. First you have to import the permutations function from Python’s itertools package and tell it the list you want to sample from:

from itertools import permutations
...
perms = permutations(list(range(start_num,start_num+9)),9)

Then, in the infinite loop, we’ll generate the next permutation and check it as before.

a,b,c,d,e,f,g,h,i = next(perms)

Randomly assigning numbers didn’t get me a solution within a reasonable amount of time. This method found the solution instantly:

Our solution, in 0.1 seconds!

Our solution, in 0.1 seconds!

Check the row and column totals and sure enough, they all work. What an accomplishment to solve a more difficult problem using more powerful tools! We had to do a little searching (algebraically or otherwise) to find the starting number, then we were waiting and waiting for our answer, so we used itertools to search through the permutations without repeating ourselves.

Another puzzle falls to the mighty power of Python! Next: Backtracking to “guess and check” square by square.

And it’s my birthday.

Puzzling with Python

Every day I challenge myself to code something in Python. On those days when I don’t have students at The Coder School who would help me keep to my coding schedule, I have to find inspiration elsewhere. Sometimes I find Processing sketches to try to clone, or I go on programming sites like Hackerrank or CodeSignal. But there are a couple of accounts on Twitter who post puzzles that make great programming exercises. The puzzles from 1 to 9 Puzzle and Yohaku are intended to be solved by hand, and I wasn’t sure if they’d like to have their puzzles cracked by coders. But I’m happy the puzzle-creators are flattered that I come back often and find their puzzles so challenging to code.

Here’s an example:

puzzle190408.png

The directions are clear: place all the digits 1 to 9 (6 is already given in the center) so that the sums of the rows, columns and diagonals are the given values. What if we just took the remaining 8 numbers and placed them randomly in the remaining spaces, then check the row/column/diagonal totals? If any don’t work out, generate a new bunch of numbers, and so on. Sounds like an infinite loop! First we’ll import the random module to take random samples of our numbers, and the time module so we can measure how fast our solution is:

import random
import time

#save the starting time
start = time.time()

Now we need the list of numbers from 1 to 9. We’ll take out the one we were given in the middle, and assign the given totals of the rows, columns and diagonals.

#generate the numbers from 1 to 9
NUMS = list(range(1,10))

#the center number is given. This changes
e = 6
NUMS.remove(e)

#row, column, diagonal totals given. These change:
rows = [12,11,22]
cols = [14,16,15]
diagonals = [15,21] #down, up

Now we start an infinite loop where we’ll assign random numbers to the remaining spaces in the 3x3 grid, then go through the rows, columns and diagonals and check if there’s any error. “Continue” means “Start the loop over,” and if a total doesn’t add up, the numbers are wrong and we don’t need to check them any further.

#Infinite loop
while True:
    #randomly assign remaining numbers to letters
    a,b,c,d,f,g,h,i = random.sample(NUMS,8)
    #check if they work
    if a + b + c != rows[0]:
        continue #start the loop over
    if d + e + f != rows[1]:
        continue
    if g + h + i != rows[2]:
        continue
    if a + d + g != cols[0]:
        continue
    if b + e + h != cols[1]:
        continue
    if c + f + i != cols[2]:
        continue
    if a + e + i != diagonals[0]:
        continue
    if c + e + g != diagonals[1]:
        continue
    break

#print the solution:
print('{} {} {}'.format(a,b,c))
print('{} {} {}'.format(d,e,f))
print('{} {} {}'.format(g,h,i))

print("Time elapsed:",round(time.time() - start,1),"seconds")

Running this will give us the answer in a matter of seconds:

4 1 7
2 6 3
8 9 5
Time elapsed: 1.5 seconds

It works! Check the rows, columns and diagonals for yourself. Yes, all the coding and debugging took much longer than 1.5 seconds, but the good news is 1 to 9 Puzzle cycles through a handful of challenging types of puzzles, and another one of the same format will appear in a week or so. Like this one. It’s the same rules, it’s just the totals and the center number have changed:

puzzle190404.png

All you have to do is change the lists we wrote for the rows, columns and diagonals, and variable for the center number.

#the center number is given. This changes
e = 7
NUMS.remove(e)

#row, column, diagonal totals given. These change:
rows = [14,13,18]
cols = [18,14,13]
diagonals = [15,24] #down, up

The output should give the solution in no time.

5 1 8
4 7 2
9 6 3
Time elapsed: 1.1 seconds

So to solve the second (and third, and fourth…) puzzle, it only took us a minute or so of changing values in the original program. Talk about automating repetitious tasks! Now we can solve other puzzles!

The Monte Carlo Method

A recent post on Twitter contained a probability challenge:

powSept13.jpg

I’ve fallen in love with the Monte Carlo method of using computers to simulate repeated random experiments. It’s a great way to get to the heart of what’s happening in a probability problem. It’s like being able to flip a coin or roll a die a million times using a computer. I went to work modeling the situation in Python:

from random import random

N_TRIALS = 1000000

trialList = [] #empty list for all the trials
for i in range(N_TRIALS):
    trial = [] # single Trial
    randA = random() #generate a couple of random numbers
    randB = random()
    if randA <= 0.2: #if A is successful:
        trial.append(1) #add it to the trial
    else:
        trial.append(0)
    if randB <= 0.3: #same with B
        trial.append(1)
    else:
        trial.append(0)
    #so that's going to be like [1,0] or [1,1] for example
    trialList.append(trial) #add the trial to the trialList

So now we’ll have a million random trials. We’ll check for the ones in which A succeeded but B didn’t and so on. Now all we have to do is check for each possibility and we should get close to the real probability:

As = 0 #number of times A occurs
Bs = 0 #number of times B occurs
Cs = 0 #at least 1 of A or B
Ds = 0 #exactly 1 of A or B
A_given_D = 0
B_given_D = 0

#iterate over trialList and sum up the scores
for trial in trialList:
    if trial[0]: #[1,0] or [1,1]
        As += 1
    if trial[1]: #[0,1] or [1,1]
        Bs += 1
    if 1 in trial: #[0,1],[1,0] or [1,1]
        Cs += 1
    if sum(trial) == 1: #[0,1] or [1,0]
        Ds += 1
        if trial[0]: #[1,0] 
            A_given_D += 1
        if trial[1]: #[0,1]
            B_given_D += 1

P_D = Ds/N_TRIALS

#print the results

print("P(A):",As/N_TRIALS)
print("P(B):",Bs/N_TRIALS)
print("P(C):",Cs/N_TRIALS)
print("P(Exactly 1):",P_D)
print("P(A|D):",(A_given_D/(N_TRIALS*P_D)))
print("P(B|D):",B_given_D/(N_TRIALS*P_D))

The outcome is given below. The Center of Math posted the answers and mine came very close!

Results:
P(A): 0.1994
P(B): 0.2996
P(C): 0.4393
P(Exactly 1): 0.3794
P(A|D): 0.3679
P(B|D): 0.6320

Circles of Circles with Sines

Last night a student and I set out to clone a sketch I found on Twitter:

beads.gif

The first task, as always, is to analyze the sketch to break it down into its repeated components. In this case, the repeated component is a circle that oscillates back and forth along a line. I challenged my student to create that in Processing. He needed a refresher on the sine function. You don't have to sit through a year-long trig class to know sine can be used to make things oscillate between a minimum and maximum value. It includes the whole range of values in between, too. The general form of the equation for a sine wave is

f(t) = a*sin(b*t - c)

where t is the time variable, a is the height of the wave, b is the frequency of the oscillation and c is the phase shift. The equation for making the x-value oscillate between -300 and 300 (for a 600-pixel screen) is 

x = 300*sin(0.05*frameCount)

because frameCount is a built-in value in Processing that returns the number of frames that the program has looped through already. With that we could create a line and oscillate one ball back and forth across it:

oneBall.gif

Using a loop and the rotate function, we could create that ball, rotate the screen a little, and loop over again and again. However, All the balls would be the same distance down the line, and it wouldn't look as cool. 

oscillateTry.gif

We had to mess with the phase shift to get it to look right. Here's the line of code:

shift = i * PI / num

where num is the total number of balls we want (8) and i is the variable (between 0 and 7) for which ball we're drawing. With that we'd succeeded at cloning the Twitter sketch. But we had one trick left. Since we were smart and used variables for the number of balls, we could vary that manually by mapping the location of the mouse. That meant we could move our mouse and dynamically change the number of balls we drew! Very cool!

multiBalls2.gif

Random + Symmetry = Art!

I have the nerdiest, artsiest Twitter feed. Every day I’m blown away by some creation by techy artists Saskia Freeke, Jessica “Nervous System” Rosenkrantz, Anders “Inconvergent” Hoff or somebody with the handle “Atticus Bones.” Atticus Bones often posts grids of randomly generated designs, and today’s really caught my attention:

atticus1.jpg
atticus2.jpg

I was inspired to clone these figures today. But how? There’s no way Atticus writes out the code for 484 designs; it must be done with random generation. I looked more closely at the individual designs for clues. I noticed every design has rotation symmetry. For instance, this design can be broken up into four identical quadrants.

I zoomed in on the top right quadrant:

atticus3.jpg

Looking more closely at this quadrant, I could tell there’s more symmetry, reflectional symmetry about the diagonal. So we could chop it down even further to this:

fourgrid4.png

So it’s just a matter of creating a random collection of segments, and reflecting them over the diagonal and then rotating them to the other quadrants. Some of Atticus’ figures give me a clue as to how many points would be needed to connect the segments. It seems to me there are “nodes” forming squares at a 45 degree angle. So in our example, here’s where I think we need nodes:

fourgridnodes.jpg

So we need 9 nodes, all with their own location. This is a job for a Node class, where each node has an x- and y-value and a distinguishing number “num.” I fired up the Python mode of the Processing graphics software:

class Node:
    def __init__(self,x,y,num):
        self.x = x
        self.y = y
        self.num = num

I created a “nodes” list to store all the nodes, and a Grid class to draw a whole quadrant of nodes. Here are the first four nodes:

class Grid:
    def __init__(self,sz):
        #create the nodes in the grid
        nodes.append(Node(0,0,1))
        nodes.append(Node(0,-sz,2))
        nodes.append(Node(0,-2*sz,3))
        nodes.append(Node(sz/2.0,-sz/2.0,4))

The vertical and horizontal distance between the nodes is “sz” (since “size” is already a keyword in Processing), so the x- and y-values of the nodes are easy to calculate.

Ready to Reflect

20170628_153840.jpg

The nodes on the other side of the diagonal line needed their own locations. Was this going to be a mess? Not really. 5 out of the nine nodes are on the diagonal, so their locations don’t change. The other 4 took a little thinking and a little “back of the envelope” calculating. I didn’t have an envelope but I had a whiteboard. I drew a point (1, 2) and its reflection, which turned out to be (2,1):

So the pattern is the node at (x,y) is reflected to a node at (y, x). I easily made those changes after copying and pasting!

The next challenge was how to randomly draw a segment between two nodes (or not to). I wrote a list of the nodes and all the possible connections between them:

#list of connections between nodes
connections = [[1,2],[1,4],
               [2,3],[2,4],[2,5],
               [3,5],[3,7],
               [4,5],[4,6],
               [5,6],[5,7],
               [6,7],[6,8],
               [7,8],[7,9],
               [8,9]]

Now I created a list of randomly generated 0’s and 1’s that would determine whether each connection would be drawn or not:

self.connectChoice = [choice([0,1]) for x in range(16)]

Now a simple “if” statement would tell the program to draw the segment if the number in that spot is a 1.

def connect(self):
     #for every node that's connecting:
     for i,c in enumerate(self.connectChoice):
         if c == 1: #if the connection is active
             #connect the first node in the 2-list with the second
             nodes[connections[i][0]].connect(nodes[connections[i][1]])
             #also connect the reflections of those nodes
             mirrornodes[connections[i][0]].\
             connect(mirrornodes[connections[i][1]])

The “mirrornodes” part makes sure the reflection happens with the reflections of the nodes, too. So the quadrant is done! This code rotates the grid 90 degrees four times so we get our whole design:

def display(self):
    #copy the upper right quadrant
    # to all 4 quadrants by rotating
    for i in range(4):
        rotate(radians(90*i))
        self.connect()
atticus2.jpg

Now we need to scale down the size of each design and arrange a bunch of them in rows and columns. Sounds like we need a few loops!

#add the grid to rows and columns 
for j in range(22):     
    for k in range(22):
        pushMatrix()
        #go to the location
        translate(j*6*sz, k*6*sz)
        #display 1 grid
        grids[k+22*j].display()
        popMatrix()

It took a little trial and error to get the right amount of spacing, but I finally had my “Atticus Clone:”

atticusclone2.png

I posted it on Twitter and only got one like. But guess who it was from?

atticuslike.png

All my code is available on github. Have fun making Art!

Enter the Unknown

One of my (grown-up) students at JobTrain wasn’t impressed with my Shakespeare-writing organisms since we knew the phrase we were trying to make it write. He has a point, and that’s what’s wrong with a lot of problems we assign in Math: we already know the answer. It reminded me of the Simpson’s episode where Lisa steals all the Teachers’ Editions of the schoolbooks. Without the answers, the teachers panic!

Making sure a formula or a program works is important and that’s why we test it with something we know the answer to. But once we know it works correctly, we should be extending it and using it on questions we don’t know the answer to!

There’s a famous problem in math and programming called the Traveling Salesman Problem (TSP), in which a salesperson has to travel to a bunch of cities and is of course looking for the shortest route. Even introducing it is a terrific math problem: how many routes are there between 3 cities? 4 cities? 10 cities? It really starts to add up!

Between n cities there are (n-1)! routes, and you need to divide that by 2 because half of them are duplicates, just in the opposite direction.

So between 10 cities there are 181,440 unique routes, and between 20 cities there are 60,822,550,204,416,000 routes! If you could check a million routes randomly every second, that would still take you 1,928 years.

In programming it’s challenging enough to draw the routes between the cities randomly and test their total distance. That’s what I did, following one of Dan Shiffman’s excellent Code Challenges on YouTube. But then you leave it running and it just chooses random routes. The best route improves a little now and then. To apply the genetic algorithm, I gave each organism a score, a length, and a list of numbers signifying a route through the cities. If there were 10 cities, the “cities” list would just be the numbers 0 through 9, shuffled randomly:

class Organism:          
    def __init__(self):                  
        self.score = 0                  
        self.length = 0                  
        self.cities = nums[:]        
        random.shuffle(self.cities)

Just like the Shakespeare program, but with numbers instead of letters. But how do you score the organism if you don’t know the answer? You give the highest score to the route with the lowest distance.

def calcScore(self):           
    #calculate the length of the route: 
    myLength = self.calculateLength()           
    #give a score. Lower distance --> higher score 
    self.score = 1000000.0/myLength              
    return self.score

Those organisms with “better genes” get more copies put into the mating pool and little by little the surviving routes improve. I added in some helpful mutations, where a random number of genes get switched.

USATSP.gif

It isn’t a foolproof system, though: the pool of genes could get stuck in a non-optimal route, but it does a great job for 10,000 organisms (in this model) starting with random routes. In this GIF you can see the process of improving the route in increments of 100 generations per frame. The white number is the best distance in the first generation: 13,537 units. By the end of 1000 generations or so of the organisms evolving better and better genes (which are just lists of numbers), we’ve improved the distance to 3,808 units.

My entire code is on Github.

Your students might be fascinated to know they (and their virtual helpers) are solving problems that have never been solved before! Is their solution the best one? There’s no answer in the back of the book!

Have fun and Go Organisms!