Coding, Computer Science, JavaScript, Simon teaching, Simon's Own Code, Simon's sketch book

Back to the sorting algorithms: Beadsort (and a short lecture about the generator function)

Link to the project: https://editor.p5js.org/simontiger/sketches/7gLA0u4KF
Made my Beadsort step-by-step with a generator function! https://editor.p5js.org/simontiger/full/ilZXV9Dp0 (Scroll down to see the “Next” button!) Code: https://editor.p5js.org/simontiger/sketches/ilZXV9Dp0
The video also contains a bonus tutorial about what a generator function is!
Coding, Computer Science, English and Text-Based Data, Python, Simon teaching

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 D into E, and R into S. 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
ztefdpftjealzapcgipgaaspuzxklvd
Text 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 Ozymandias by 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")
Computer Science, Logic, Milestones, Murderous Maths, Notes on everyday life, Set the beautiful mind free, Simon teaching, Simon's sketch book

Why mathematics may become computer science

Walking home from the swimming pool (where he and Neva had been jumping into the water exactly 24 times, calling out all the permutations of 1,2,3 and 4), Simon suddenly stopped to tell me that some day, mathematics may become engulfed by computer science. Apparently, this was what he was thinking about the whole time he kept silent on the way. Once we got home I sat down to listen to the elaborate proof he had coined for his hypothesis. Here is comes, in his own words:

Someday mathematics may become computer science because most of mathematics uses simple equations and stuff like that, but computer science uses algorithms instead. And of course, algorithms are more powerful than equations. Let me just give you an example.

There’s this set of numbers called algebraic numbers, and there’s this set of numbers called computable numbers. The algebraic numbers are everything you can make with simple equations (finite polynomials), so not like trig numbers, which are actually infinite polynomials, just simple finite equations with arithmetic and power. Computable numbers, however, are a set of numbers that you can actually make with a finite algorithm. It may not represent a finite equation, but the rules for the equation have to be finite. So the algorithm that generates that equation has to be finite. It’s pretty easy to see that every algebraic number is by definition computable. Because the algorithm would just basically be the equation itself.

Is every computable number algebraic? Well, we can easily disprove that. It took very long to prove that Pi is not algebraic, that it is transcendental, as it’s called. But Pi is computable, of course, because, well, that’s how we know what Pi is, to 26 trillion decimal places. So there you go. That’s a number that is computable but not algebraic. So the Euler diagram now looks like this:

Simon drew this illustration later the same evening, when he presented his proof in Russian to his grandma via FaceTime

Now we look back at the beginning and we see that algebraic numbers have to do with equations and computable numbers have to do with algorithms. And because the set of all algebraic numbers is in the set of all computable numbers as we’ve just proved, the set of computable numbers will have more numbers than algebraic numbers. We have given just one example of how algorithms are more powerful than equations.

What about the mathematics that deals with numbers that are incomputable? – I asked.

Well, that’s set theory, a different branch of mathematics. I meant applied mathematics, the mathematics that has application.

Coding, Community Projects, Computer Science, Contributing, JavaScript, Milestones, Notes on everyday life, Simon teaching, Simon's Own Code

Simon’s new “giant project”: Sorting Visualizations

this video sums up more than one week of hard work

Simon writes: I’ve built a giant project; a website / community project / platform for making algorithms! I’ve built in this video Bubble Sort, Selection Sort, Insertion Sort, Mergesort, Quicksort, Heapsort, Shell Sort and Radix Sort. So I’m done with the sorting part of the project. In the next video I’ll show you the making of the Pathfinding part of the project, and then, I’m going to put it on GitHub, and pass it on to the community, to put more algorithms on there, and even new types of algorithms!

Play with Simon’s visualizations on Repl.it at: https://repl.it/@simontiger/SortingImproved

Simon’s tweet about the project

Simon has already recorded a series of video tutorials about sorting algorithms earlier this spring. In the videos, he codes on his RaspberryPi, but here are the links to the Python code available on his GitHub page: Parts 1 – 5; Parts 6 – 7.

Coding, Computer Science, Crafty, Geography, Murderous Maths, Notes on everyday life, Simon's sketch book

Pathfinding algorithms: Dijkstra’s and Breadth-first search

The photos below show Simon playing with Breadth-first search and Dijkstra’s algorithms to find the most efficient path from S to E on a set of graphs. The two more complex graphs are weighed and undirected. To make it more fun, I suggest we pretend we travel from, say, Stockholm to Eindhoven and name all the intermediate stops as well, depending on their first letters. And the weights become ticket prices. Just to make it clear, it was I who needed to add this fun bit with the pretend play, Simon was perfectly happy with the abstract graphs (although he did enjoy my company doing this and my cranking up a joke every now and then regarding taking a detour to Eindhoven via South Africa).

this was an example of how an algorithm can send you the wrong way if it has data of the “right” way being weighted more (due to traffic jams, for example)
Computer Science, Milestones, Murderous Maths, Notes on everyday life, Set the beautiful mind free

E-mail from Ron Graham

Wow! We have received an e-mail from his mathematical majesty Ron Graham today! In reaction to Simon’s Graham Scan project:

“Hi Sophia and Simon, I love the video on Graham’s Scan. I’m sure it was not so easy to make! Simon, you are certainly special! Keep up the good work and keep me posted! Best regards, Ron Graham”

Coding, Community Projects, Computer Science, Contributing, JavaScript, Murderous Maths, Physics, Simon's Own Code, Simon's sketch book

Simon’s Community Contribution: Variation of 2D Casting Coding Challenge in p5.js

This is Simon’s version of Daniel Shiffman’s 2D Casting code, made on Wednesday last week right after the live session. Link to the live session including the coding challenge.

Code and interactive animation are online at: https://editor.p5js.org/simontiger/sketches/ugHX4yKQC
Play with the animation online at:
https://editor.p5js.org/simontiger/present/ugHX4yKQC
https://editor.p5js.org/simontiger/full/ugHX4yKQC

Simon’s suggestions during a patron-only live session yesterday
a screenshot of Simon’s community contribution published on the Coding Train website

Simon has also made one more, optimized version of this project (with fewer rays, runs faster): https://editor.p5js.org/simontiger/present/F6TCHAZs_
https://editor.p5js.org/simontiger/sketches/F6TCHAZs_

Both of Simon’s versions have been added to the community contributions on the Coding Train website: https://thecodingtrain.com/CodingChallenges/145-2d-ray-casting.html

screenshot of the optimized version
Coding, Computer Science, Contributing, Group

Example of Simon contributing an issue on GitHub

Below is Simon’s issue/ topic suggestion he contributed to the Coding Train GitHub yesterday, addressed to Daniel Shiffman:

Function Overloading

Nah.

Operator Overloading

OK, first, we have to understand the valueOf() function. valueOf() is a function, that typically performs on a string, that converts it into a “primitive” data type.

A number is a primitive data type, because it’s not an object. And, you can see that by opening a Terminal window, running node and type:

> 2 + 2 // and get
4

Because JS doesn’t have any “real” overloading, you can’t put + in between two objects, in between two objects, and get an answer!

Well, with one slight exception, which is the valueOf() function. It will tell JS how to interpret an instance of an object as a primitive data type, whenever you want to add them together or something. If you put a valueOf() function into the prototype (or class, if you will) of an object, and it converts it into a number, or some other primitive data type, you can suddenly do arithmetic on these objects!

This does have a limitation, though. Say you write a class:

class Vector {
  constructor(x=0, y=0) {
    this.x = x;
    this.y = y;
  }

  // Maybe you want a valueOf() function to add them together
  valueOf() {
    // TL;DR What goes here???
  }
}

Maybe you want to add the individual components of a vector to add two vectors together.
It turns out, the answer is, nothing can go in the place of the question mark!

Here’s why: There’s no real primitive data type, with further components. That’s because that’s what a primitive data type is! It doesn’t have data, it is it’s own data! A Vector does have further components, however, and so we arrive at a contradiction. Because a vector has further components, and valueOf() must return something without further components, this situation is impossible!

String Overloading

Well, it’s really the same as Operator Overloading, except you need to use the toString() function instead of the valueOf() function. It converts it into a string. I don’t really know why you’d want to do this, maybe you would affect how you print it. I actually don’t even know if toString() can do this.

[TL;DR] Overloading

Look at this messy video about Matrix Math that you made: https://www.youtube.com/watch?v=NgZAIkDcPkI, at 23:15.

Guess what, there’s a way to fix that!

I don’t know how this one is called. When you say this, it’s an object. But, because objects are associative arrays, you can actually treat this as an associative array! Something like this:

class Matrix {
  constructor(rows, cols) {
    this.rows = rows;
    this.cols = cols;
    // this.data = []

    for (let i = 0; i < this.rows; i++) {
      this[i] = []; // OMG
      for (let j = 0; j < this.cols; j++) {
        this[i][j] = 0; // OMG
      }
    }
  }
  // .
  // .
  // .
}

It’s as easy as that!
If you want to, you could even add a this.length variable, and suddenly, you would even be able to iterate over it, with a for..of loop!