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
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, 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, Community Projects, Computer Science, Contributing, Geometry Joys, Group, Milestones, Murderous Maths, Notes on everyday life

More examples of Simon’s chat contributions on math and coding

Simon is always extremely active in the discussions about the current projects made by/ lectures given by NYU’s Asdociate Professor Daniel Shiffman during his live sessions on the Coding Train channel. He also enjoys “initiating discussions” among the channel’s patrons (grown-up programmers) and Daniel. “Mom, the discussion I initiated is still going on!” I couldn’t possibly post all the coding and math comments/ suggestions that Simon makes in the chats on YouTube, Slack and GitHub (and I don’t believe I should either), but every now and then, I like collecting samples of Simon’s contributing to the discussion:

Simon contributing to a discussion prior to a live session on ray tracing
Simon contributing to Daniel Shiffman’s tutorial on the computational geometry “minimum spanning tree” problem

The small font above says:

Correction: The MST problem does not allow any loops (like A->B, B->C, C->D, D->A again.) So the solution at 2:30 is wrong! In fact, _no wonder it does that_, because Prim’s Algorithm will never find a loop. Here’s why:

Let’s suppose that it could find a loop (let’s say, a loop of 4, so A->B, B->C, C->D, D->A again, but this argument would work the same each way.) Ok, so it will start from A, and mark it as reached. It will check A against B, C and D, find B, and mark B as reached. Then, it will check A against C and D, and B against C and D. and it will find that it should connect B and C, and mark C as reached. Then, it will check A, B and C all against D, and find that it should connect C and D, and mark D as reached. But now, we reach a problem. It will not connect D and A, because both are already reached!

Why was it designed like that? Because that’s what the problem says! It’s a Minimum Spanning _Tree_, so it can’t have any loops.

So there you go, that’s why Prim’s algorithm will not find a loop.

Crafty, Geometry Joys, Group, Logic, Milestones, Murderous Maths, Notes on everyday life, Together with sis

Vladimir Krasnoukhov at MathsJam Antwerp!

all these beautiful puzzles we have received from Vladimir Krasnoukhov

When we arrived at the MathsJam last Tuesday, we heard a couple of people speak Russian. One of them turned out to be a well known Russian puzzle inventor Vladimir Krasnoukhov, who presented us with one colorful puzzle after another, seemingly producing them out of thin air. What a feast! Simon got extremely excited about several puzzles, especially one elegant three-piece figure (that turned out to have no possible solution, and that’s what Simon found particularly appealing) and a cube that required graph theory to solve it (Simon has tried solving the latter in Wolfram Mathematica after we got home, but hasn’t succeeded so far).

Vladimir told us he had been making puzzles for over 30 years and had more than 4 thousand puzzles at home. Humble and electricized with childlike enthusiasm, he explained every puzzle he gave to Simon, but without imposing questions or overbearing instructions. He didn’t even want a thank-you for all his generosity!

Vladimir Krasnoukhov and Simon

Vladimir also gave us two issues of the Russian kids science magazine Kvantik, with his articles published in them. One of the articles was an April fools joke about trying to construct a Penrose impossible triangle and asked to spot the step where the mistake was hidden:

Simon was very enthusiastic about trying to actually physically follow the steps, even though he realized it would get impossible at some point:

Simon and Neva constructing the shape that “allows” to convert it into Penrose impossible triangle (as seen in the optical illusion in the Kvantik magazine)
the next step was already impossible

Simon’s also working on other math problems from the magazine, so more blog posts about Kvantik will follow. We’re very happy to have discovered the website https://kvantik.com

You can find out more about Vladimir Krasnoukhov’s puzzles on planetagolovolomok.ru

Computer Science, Geometry Joys, Milestones, Murderous Maths, Notes on everyday life, Simon teaching, Simon's sketch book

Graham Scan Algorithm

“Connect some points into a convex polygon such that all of the remaining points are inside that convex polygon. The algorithm that will find it for me is called the Graham Scan Algorithm (actually invented by Ronald Graham),” Simon told me as he printed out a sheet dotted with points. He had also prepared some paper cards with numbers on them. “In general, a Convex Hull is the smallest set (in this case, of points) that contains your original set”.

In the video, Simon manually applies the Graham Scan Algorithm (using the print-out, a protractor and paper cards to create a stack). He measured the angles between the P point and the rest of the points and sorted them (“If you want to do this, you can use any sorting algorithm,” Simon adds).

Simon first learned about the algorithm from a Visualgo visualization but that resource didn’t explain how the algorithm actually works, so he looked it up on Wikipedia.

Simon got his set of points from this site.

the final result

Busy with the same algorithm during the Easter break at the summer house:

wrote the steps of the algorithm in chalk and repeated the whole procedure with fewer points
Astronomy, Milestones, Notes on everyday life, Physics

Black Hole Breakthrough

Simon recorded this video right after the news was announced on April 10

Caught Simon’s reaction to Wednesday’s breaking news on video: the first-ever image of a black hole published, made by the Event Horizon Telescope project team. Simon explains why, if you stood next to the black hole, you would be able to see the back of your own head.

Simon loved this video by Veritasium about how the image of the black hole was made (he had watched this one day prior to the actual publication of the black hole image).

Yesterday, wee also watched this beautiful TEDx contribution by Katie Bouman (one of the leading figures behind the algorithm that helped stitch the M87 black hole image data together). The video is from three years ago, when the project was just getting started. Katie is such an inspiration: a computer scientist helping astrophysicists!

Scientists report ‘groundbreaking’ black hole findings from the Event Horizon Telescope: link to the actual press conference.