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)
Murderous Maths, Geometry Joys, Notes on everyday life, Crafty, motor skills, Simon's sketch book

A Knot Theory Puzzle

Simon has shown us a curious puzzle: if you hang a poster on a string using two pins, what is the way to arrange the string so that the poster definitely falls once you remove any pin? The math behind the trick involves Knot Theory. Simon has learned the trick from this video by Jade, the creator of the science and phlosophy Up an Atom channel that Simon loves.

It’s relatively easy to solve the puzzle for one particular pin. The picture below shows the solution for removing the right pin:

But the puzzle asks us to think of a configuration that makes the poster fall once ANY pin is removed, doesn’t matter which! And that’s way more difficult. Simon said that we should simplify the problem by removing the poster altogether and replacing the pins with two small loops of string.

What Simon did next was show us the math behind the trick, trying to come up with such a combination of the three loops that would stay connected but, if you remove any of the three, the rest of the construction would fall apart. “Wait, that sound familiar! We’ve actually turned the problem into Borromean rings!”

The letters x and y stand for the ways to intertwine the strings, with x wrapping around 1 and y wrapping around 3. The regular x and y are clockwise (x or y) and the inverse x and y are anticlockwise (x^-1 or y^-1). Obviously, a sequence of clockwise-anticlockwise of the same string should be avoided as it unties itself.
the moment of truth!
performing in front of our guests the day after (in Dutch)
the solution
Biology, Murderous Maths

The All Common Ancestors Generation

This project is a simulation of how many people can stem from the same ancestor, something Simon has learned from James Grime’s “Every Baby is a Royal Baby” video on Numberphile. In this simplified version, there’re only 6 people per generation. Simon was throwing two dice to determine who the two parents were for every person (in the case when both dice came out to be the same number, this was considered “virgin birth” or simply that the father had come from outside the limited sample Simon was working with).

the present generation
Simon marking who the children of a person were in pink pencil
Some parents don’t have the digits corresponding to their children written next to them, but letters N and E: N means that that person from the parent generation had no children and is therefore related to no one from the future generations; E on the conrrary, means that that person “has been busy” and is related to everyone in the next generation!
identifying the most recent common ancestor generation and the identical ancestors generation
the all common ancestors generation
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, JavaScript, Machine Learning, Milestones, Murderous Maths, neural networks, Notes on everyday life, Set the beautiful mind free, Simon teaching, Simon's Own Code, Simon's sketch book

What Simon did instead of taking the SAT on Saturday

On Saturday morning, Simon didn’t go to the SAT examination location, although we had registered him to try taking the SAT (with great difficulties, because he is so young). In the course of the past few weeks, after trying a couple of practice SAT tests on the Khan Academy website, we have discovered that the test doesn’t reveal the depth of Simon’s mathematical talent (the tasks don’t touch the fields he is mostly busy with, like trigonometry, topology or calculus and require that instead, he solves much more primitive problems in a strictly timed fashion, while Simon prefers taking time to explore more complex projects). This is what happens with most standardized tests: Simon does have the knowledge but not the speed (because he hasn’t been training these narrow skills for hours on end as his older peers at school have). Nor does he have the desire to play the game (get that grade, guess the answers he deosn’t know), he doesn’t see the point. What did he do instead on his Saturday? He had a good night sleep (instead of having to show up at the remote SAT location at 8 a.m.) and then he…

built an A.I. applying a genetic algorithm, a neural network controlling cars moving on a highway! The cars use rays to avoid the walls of the highway. Implementing neuroevolution. What better illustration does one need to juxtapose true achievement and what today’s school system often wants us to view as achievemnt – getting a high grade on a test? The former is a beautiful page from Simon’s portfolio, showing what he really genuinely can do, a real life skill, something he is passionately motivated to explore deeper, without seeking a reward, his altruist contribution to the world, if you will. The latter says no more than how well one has been trained to apply certain strategies, in a competitive setting.

Simon’s code is online: https://repl.it/@simontiger/Raytracing-AI

Simon has put this version on GitHub: https://github.com/simon-tiger/Raycasting-A.I.

He has also created an improved version with an improved fitness function. “In the improved version, there’s a feature that only shows the best car (and you can toggle that feature on and off). And most importantly, I am now casting relative to where it’s going (so the linearity is gone, but it jiggles a lot, so I might linear interpolate it)”, – Simon explains. You can play with the improved version here: https://repl.it/@simontiger/Raycasting-AI-Improved

Finally, Simon is currently working on a version that combines all the three versions: the original, the improved and the version with relative directions (work in progress): https://repl.it/@simontiger/Raytracing-AI-Full

“I am eventually going to make a version of this using TensorFlow.js because with the toy library I’m using now it’s surprisingly linear. I’m going to put more hidden layers in the network”.

The raytracing part of the code largely comes from Daniel Shiffman.

Simon’s two other videos about this project, that was fully completed in one day:

Part 1
Part 2


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!

Milestones, Murderous Maths

Tower of Hanoi moves plotted under a binary log plot

What you see here is the sequence of moves to solve the Towers of Hanoi puzzle. The sequence goes up to 2 to the power of the number of rings in your puzzle. The picture here is the sequence for 8 discs, so 256 moves. “If you plot log_2 (binary log), this shape (in red) would be under that log plot, except for the powers of 2 which would be exactly on the log plot!” Simon has noticed.

Simon has plotted this sequence including 256 moves using Paint

detail of the plot, including 2^4
Simon explaining his “discovery”


Simon’s earlier video about the math behind the Towers of Hanoi puzzle: