Simon has written a short Python code solving the Towers of Hanoi puzzle: https://repl.it/@simontiger/Towers-of-Hanoi

# Category Archives: Python

# Why the Golden Ratio and not -1/the Golden Ratio?

Take any real number and call it x. Then plug it into the equation f(x) = 1 + 1/x and keep doing it many times in a row, plugging the result back into the equation.

At some point you will see that you arrive at a value that will become stable and not change anymore. And that value will be… φ, the golden ratio!

But this equation also has another answer, -1/φ. If you plug that value into the equation, it will be the same, too. The real magic happens once you have rounded the -1/φ down (or up), i.e. once what you plug into the equation is no longer exactly -1/φ. What happens is that, if you keep going, you will eventually reach… φ as your answer!

Simon saw this interesting fact in a video by 3Blue1Brown and then came up with a proof as to why it happens.

Simon also sketched his proof in GeoGebra: https://www.geogebra.org/classic/zxmqdspb

# Prime Generation Algorithm in Python

Simon has written a code in Python that generates primes using the finite list from Euclid’s proof that there are infinitely many primes. “Starting with one prime (2) the code uses the finite list to generate a couple more numbers that aren’t in the list but are primes. It may not even get to all the primes in the long run!” There is only one problem with Simon’s algorithm…

Simon has written down Euclid’s proof in his own words first https://imgur.com/ML2tI6n

and then decided to program it in Python.

Resources:

https://www.programiz.com/python-programming/methods/list/remove

https://www.geeksforgeeks.org/iterate-over-a-set-in-python/

https://www.youtube.com/watch?v=OWJCfOvochA

https://numbermatics.com/n/10650056950807/

https://defuse.ca/big-number-calculator.htm

# It takes the sun to the ground, and violet on the observer’s eye.

Simon writes:

This amazing sentence is generated by a Markov Text-Generation Algorithm. What is a Markov Algorithm? Simply put, it generates the rules from a

source text, and it generates a new text that also follows those rules. The rules are often called theMarkov Blanket, and the new text is also called theMarkov Chain. OK, how does this all work?

Let’s take an example: let’s consider the source text to be “Hello, world!”. Then we pick a number called the

order. The higher the number, the more sense the text makes. We’ll pick 1 for the first examples, we’ll examine what happens with higher numbers later.

Then we generate the

Markov Blanket. This is a deterministic process. We start from the beginning: “H”. So we put H in our Markov Blanket. Then we come across “e”. So we put e in our Markov Blanket, but to specify that it’s next from H, we connect H to e by an arrow. Then we stumble on “l”. So we put l in our Markov Blanket, but again, to specify that it’s next from e, we connect e to l by an arrow.

Now, here’s where it gets interesting. What’s next? Well, it’s “l” again. So now we connect l to

itself, by an arrow. This is interesting because it’s no longer a straight line!

And we keep going. Once we’re done, our Markov Blanket will look something like this:

Once we’ve created our Markov Blanket, then we start generating the

Markov Chainfrom it. Unlike the Markov Blanket, generating the Markov Chain is a stochastic process.

This is just a process of wandering about the Markov Blanket, and noting down where we go. One way to do this, is just to start from the beginning, and follow the path. And whenever we come across some sort of fork, we just spin a wheel to see where we go next. For example, here are some possible Markov Chains:

```
Held!
Helld!
Hellld!
Helorld!
Hello, world!
Helllo, wo, wo, world!
```

That was an easy one, so let’s do something more complex with code.

First, just an interface to enter in the text, and the order:

text = "" # Variable to hold the text print("Type your text here (type END to end it):") while True: line = input("") # Read a line of text from standard input if line != "END": text += line + "\n" # If we didn't enter END, add that line to the text else: break # If we entered END, signify that the text has ended text = text[:len(text)-1] # Remove the last line break order = int(input('Type the order (how much it makes sense) here: ')) input("Generate me a beautiful text") # Just to make it dramatic, print this message, and ask the user to hit ENTER to proceed

Next, the Markov Blanket. Here, we store it in a

dictionary, and store every possible next letter in alist:

def markov_blanket(text, order): result = {} # The Markov Blanket for i in range(len(text) - order + 1): # For every n-gram ngram = "" for off in range(order): ngram += text[i+off] if not ngram in result: # If we didn't see it yet result[ngram] = [] if i < len(text) - order: # If we didn't reach the end result[ngram].append(text[i+order]) # Add the next letter as a possibility return result # Give the result back

Huh? What is this code?

This is what happens when we pick a number >1. Then, instead of making the Markov Blanket for every character, you make it for every couple of characters.

For example, if we pick 2, then we make the Markov Blanket for the 1st and 2nd letter, the 2nd and 3rd, the 3rd and 4th, the 4th and 5th, and so on. When we generate the Markov Chain, we

squashthe ngrams that we visit together. So next, the Markov Chain:

def markov_chain(blanket): keys = blanket.keys() ngram = random.choice(list(keys)) # Starting Point new_text = ngram while True: try: nxt = random.choice(blanket[ngram]) # Choose a next letter new_text += nxt # Add it to the text ngram += nxt # Add it to the ngram and remove the 1st character ngram = ngram[1:] except IndexError: # If we can't choose a next letter, maybe because there is none break return new_text # Give the result back # Now that we know how to do the whole thing, do the whole thing! new_text = markov_chain(markov_blanket(text, order), num) print(new_text) # Print the new text out

OK, now let’s run this:

```
Type your text here (type END to end it):
A rainbow is a meteorological phenomenon that is caused by reflection, refraction and dispersion of light in water droplets resulting in a spectrum of light appearing in the sky. It takes the form of a multicoloured circular arc. Rainbows caused by sunlight always appear in the section of sky directly opposite the sun.
Rainbows can be full circles. However, the observer normally sees only an arc formed by illuminated droplets above the ground, and centered on a line from the sun to the observer's eye.
In a primary rainbow, the arc shows red on the outer part and violet on the inner side. This rainbow is caused by light being refracted when entering a droplet of water, then reflected inside on the back of the droplet and refracted again when leaving it.
In a double rainbow, a second arc is seen outside the primary arc, and has the order of its colours reversed, with red on the inner side of the arc. This is caused by the light being reflectedtwice on the inside of the droplet before leaving it.
END
Type the order (how much it makes sense) here: 5
Generate me a beautiful text
```

And……..it..stops.

Why did it do that?

You see, this is not such a good method. What if our program generated a Markov Blanket that didn’t have an end? Well, our program wouldn’t even get to the end, and it would just wander around and around and around, and never give us a result! Or even if it did, it would be

infinite!

So how do we avoid this?

Well, we set another much bigger number , let’s say 5000, to be a

callout value. If we don’t get to the end within 5000 steps, we give up and output early. Let’s run this again…

And now, it doesn’t stop anymore! Snippets of example generated text:

*It takes the sun to the ground, and violet on the observer’s eye.*

*This rainbow, a second arc formed by illuminated droplets resulting it.In a primary rainbow is a meteorological phenomenon the back of the ground, and has the sky. It takes the order of its coloured circles. However, the sun.*

*Rainbow, a second arc shows red on a line from the section of light in water droplet and has the sun.*

*In a double rainbow is caused by illuminated droplet on the outer part and refracted when leaving in a spectrum of a multicoloured circles. However, the droplet of water droplets resulting it.In a double rainbow is a meteorological phenomenon the droplets resulting in a spectrum of a multicoloured circular arc. Rainbow is caused by the inner side the observer’s eye*

Play with this project online at: https://repl.it/@simontiger/Markov-Text

# More Fibonacci

# Number Guessing Game

Simon writes: Made a little game where the computer thinks of a number 1-100, and you try to guess it within 7 takes! Hint: the algorithm is called “Binary Search”. https://repl.it/@simontiger/NumberGuessingGame

You can also play the fullscreen version here: https://numberguessinggame.simontiger.repl.run/

Now also a reversed version, where you think of a number and the computer guesses it: https://repl.it/@simontiger/BinaryNumGuessingGame

# Encoding and Cracking Codes in Python

Had great fun learning how to crack codes using Python! Simon is currently following the Programming with Python course on Brilliant.org and showed me how to see whether an encrypted piece is gibberish or a real text is hidden behind it.

Simon writes:

A Caesar Shift is a simple cipher, which was a standard in Roman times. It works like this: shift every character by some fixed amount in the alphabet. Something like this:

Example: Suppose some professor writes his name on his board:

ES. TNJUI

It’s encoded with a caesar shift. Because it’s a professor’s name, it probably starts with “Dr.”, so it’s probably a shift that turns

DintoE, andRintoS. So we can work backwards from that shift, and get:DR. SMITH

That was an easy one, so let’s do something more complex with code.

One of the messages below is a real text, encoded using a Caesar Shift, the other one is just a random sequence of letters. Can you tell which one is which?

Text 1:yfdpcpoplhhwdpssbjnsqvtlcpzpxqugtjphvgotuvwxufgoqigxwgkskduooyeuoue fjlnmsqpgxrmcseeliswdheywseqgcbeothskxdzekgxmmkildjnaqbukprpfaaknsu qpdwayqaqfxsoapvsgreqydqjnkpjghvrkygtidzibhrqkmocukhcunpjcazzvomtsc fgycwfltmiegaejwcqrgsnxxcbtcrckufwsdxdhbxgppxcuzapbdhftzmugryfseavv bssqlxanvmfwwzityziixasivzkmvtfczqmdgkabcnjbyhaoealengfptuedlmvryeb titbwqkekzdpmbtiphdkwwiduassvbgalxgrfhrjrjplxpujrprqzcpcdqsjorigazt kwwlnwbjryrzhgcttroyemuwwixwufymnknirzmexyowobvardlqktzajzoijwulomg ztefdpftjealzapcgipgaaspuzxklvdText 2:

swodkdbkfovvobpbywkxkxdsaeovkxngrycksndgyfkcdkxndbexuvoccvoqcypcdyx ocdkxnsxdronocobdxokbdrowyxdrockxnrkvpcexukcrkddobonfsckqovsocgrycop bygxkxngbsxuvonvszkxncxoobypmyvnmywwkxndovvdrkdsdccmevzdybgovvdrycoz kccsyxcbokngrsmriodcebfsfocdkwzonyxdrocovspovoccdrsxqcdrorkxndrkdwym uondrowkxndrorokbddrkdponkxnyxdrozonocdkvdrocogybnckzzokbwixkwoscyji wkxnskcusxqypusxqcvyyuyxwigybuciowsqrdikxnnoczksbxydrsxqlocsnobowksx cbyexndronomkiypdrkdmyvycckvgbomulyexnvocckxnlkbodrovyxokxnvofovckxn ccdbodmrpkbkgki

Simon has explained a way to see whether the encrypted piece contains meaningful (real) text: one can plot the frequency of each letter as it’s used in the encrypted piece. If all letters have generally similar frequency, it’s not a real text, because in real texts, certain letters are encountered much more often than others. Below are the frequency plots Simon made for the texts above, using a Python package called `matplotlib`

:

Frequencies for text 1:

Frequencies for text 2:

As you can see, the second plot depicts a greater variety in frequencies. “For example, *o* appears the most, but *g* does not appear that much. And *t* does not appear at all!” Simon showed me.

As it turned out, we could actually use our knowledge about which letters naturally appear more frequently in English-language texts to crack the code! “Which letter is the most frequent one in English writing?” Simon asked me. “Letter *e*!” I guessed. “So now we know that the letter *o* in the encrypted text stands for *e* in the real text!” Simon exclaimed. “All we have to do to decode it now is simply shift the letters by 10 letters back, because *e* is 10 letters behind the *o*!”

Simon Writes:

So, what is the message about? Simon tweaked Brilliant’s code to make sure it shifted by the amount of 10…

imetatravellerfromanantiquelandwhosaidtwovastandtrunklesslegsofstonestandinthedesertnearthemonthesandhalfsunkashatteredvisagelieswhosefrownandwrinkledlipandsneerofcoldcommandtellthatitssculptorwellthosepassionsreadwhichyetsurvivestampedontheselifelessthingsthehandthatmockedthemandtheheartthatfedandonthepedestalthesewordsappearmynameisozymandiaskingofkingslookonmyworksyemightyanddespairnothingbesideremainsroundthedecayofthatcolossalwreckboundlessandbaretheloneandlevelsandsstretchfaraway

…put the spaces and punctuation in appropriately…

I met a traveller from an antique land

Who said: “Two vast and trunkless legs of stone

Stand in the desert . . . Near them, on the sand,

Half sunk, a shattered visage lies, whose frown,

And wrinkled lip, and sneer of cold command,

Tell that its sculptor well those passions read

Which yet survive, stamped on these lifeless things,

The hand that mocked them, and the heart that fed:

And on the pedestal these words appear:

‘My name is Ozymandias, king of kings:

Look on my works, ye Mighty, and despair!’

Nothing beside remains. Round the decay

Of that colossal wreck, boundless and bare

The lone and level sands stretch far away.”

So, it’s about Archeology! This is the poem

Ozymandiasby Percy Shelley (1818).

## Source Code

Encoder / Decoder:

alphabet = "abcdefghijklmnopqrstuvwxyz" # convert between letters and numbers up to 26 def number_to_letter(i): return alphabet[i%26] def letter_to_number(l): return alphabet.find(l) # How to encode a single character (letter or not) def caesar_shift_single_character(l, amount): i = letter_to_number(l) if i == -1: # character not found in alphabet: return "" # remove it, it's spaces or punctuation else: return number_to_letter(i + amount) # Caesar shift # How to encode a full text def caesar_shift(text, amount): shifted_text = "" for char in text.lower(): # also convert uppercase letters to lowercase shifted_text += caesar_shift_single_character(char, amount) return shifted_text ### MAIN PROGRAM ### message = """ paste the text here """ code = caesar_shift(message, 2) print(code)

Code for Plots:

import matplotlib.pyplot as plt alphabet = "abcdefghijklmnopqrstuvwxyz" code = """ paste the text here """ letter_counts = [code.count(l) for l in alphabet] letter_colors = plt.cm.hsv([0.8*i/max(letter_counts) for i in letter_counts]) plt.bar(range(26), letter_counts, color=letter_colors) plt.xticks(range(26), alphabet) # letter labels on x-axis plt.tick_params(axis="x", bottom=False) # no ticks, only labels on x-axis plt.title("Frequency of each letter") plt.savefig("output.png")

# Drawing with Turtle

Here we are, on the day of my 40th birthday, while recording a lesson of drawing with turtle in Python. It was meant to be my birthday present, a beginner-friendly hour of code, in which Neva would also be able to take an active part. We ended up recording two beautiful sessions only to find out later that our screen capture video was irreparably corrupted (never record in mp4 in OBS). Simon was inconsolable. We also thought this webcam recording was gone but rediscovered it a day later. So nice to have it as a memory.

And I’m relieved to say that we have managed to redo the whole project from scratch today (sadly without Neva’s participation this time as she had better things to do, so I look rather redundant sitting there next to Simon giving the lesson). Once Simon is done with the editing (which is another two days of work I’m afraid), he will upload the hour of code on YouTube. He also plans to create a website for this project to enable his “students” to draw in a built-in application.

From our session today:

And here is an example of Simon drawing with turtle for his own pleasure, a Serpinski triangle in Python (a few days ago):

# The Van Eck Sequence

Simon explains that the Van Eck Sequence is and shows the patterns he has discovered in the sequence by programming it in Python and plotting it in Wolfram Mathematica. Simon’s project in Wolfram is online at: https://www.wolframcloud.com/objects/4066d93a-893b-4a99-9fdc-54e265d27888

He also shows Neil Sloane’s proof of why the sequence is not periodic and adds an extra bit to make the proof more complete.

This video is inspired by the Numberphile video about the Van Eck sequence.

# More Sorting Algorithms!

An update to Simon’s new project: a series of video tutorials on sorting algorithms! See the full playlist here.

Finally, parts 6 and 7 of Simon’s exciting series of video tutorials about sorting algorithms are done! In the videos, Simon codes on his RaspberryPi, but here is the link to the Python code (parts 6 – 7) available on his GitHub page:

https://gist.github.com/simon-tiger/be3864b36f6d89fecd06f150063a6321

The code of the sorting algorithms discussed in the previous videos (parts 1 – 5) is available here: https://gist.github.com/simon-tiger/5be70247a066f69c2578be5bb8e41e59

Simon wrote the Shellsort code himself. He tried to run his own code for Heapsort as well, but didn’t get the list fully sorted, so in the end he implemented the heapsort code that he learned from Brilliant.

“Then, with VERY much relief, I MASSIVELY condensed the code (to just 3 lines!), using Zax Rosenberg’s blog“, Simon adds.