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
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, Crafty, Geography, Geometry Joys, Murderous Maths, Simon's sketch book

Dijkstra’s pathfinding algorithm

“I have first built a maze, then I turned it into a graph and applied Dijkstra’s pathfinding algorithm!”

a maze to which Dijkstra’s pathfinding algorithm is applied

Simon learned this from the Computerphile channel. He later also attempted to solve the same maze using another pathfinding algorithm (A-Star).

Coding, Computer Science, Milestones, Murderous Maths, Python, RaspberryPi, Simon teaching, Simon's Own Code, Simon's sketch book

More Sorting Algorithms!

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

Part 7: Heapsort

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

Part 6: Shellsort

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.

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
chemistry, Experiments, Physics, Simon teaching, Simon's sketch book, Together with sis

Chemistry Experiments: Polarized light iridizes crystals

Today we have made beautiful rainbow chrystals! Polarized light iridizes sodium thiosulfate crystals, so we made the crystals in between two polarizing films and then observed them through the microscope. In the video, Simon also explains how polarizing film works.

From the scientific description at the MEL Science website: Sodium thiosulfate crystals contain five molecules of water per one unit of sodium thiosulfate Na2S2O3. Interestingly, when heated, the crystals release the water, while sodium thiosulfate dissolves in this water. This solution solidifies rapidly when cooling, forming beautiful crystals. If these crystals are put between polarizing films, they take on an iridescent sheen. This is because the polarizing films only let light with certain characteristics through, and this light in turn “iridizes” the otherwise-colorless sodium thiosulfate crystals.

Coding, Coding Everywhere, Computer Science, Milestones, Murderous Maths, Python, RaspberryPi, Simon's Own Code, Simon's sketch book

Simon creates a playlist with Sorting Algorithms tutorials in Python

Simon’s chart of sorting algorithms ranked by efficiency

Simon has started a huge new project: a series of video tutorials about sorting algorithms. In the videos, he codes on his RaspberryPi, but here is the link to the Python code available on his GitHub page (that he continuously updates): https://gist.github.com/simon-tiger/5be70247a066f69c2578be5bb8e41e59

Today, Simon has recorded the fifth part of the series, in which he explains and applies the Quicksort algorithm. [The coding part goes very smoothly and much quicker (hehe) than in the previous sorting videos we have made so far. Simon also came up with his own code, he didn’t look the code up].

the quicksort video

And here come the previous parts of Simon’s sorting algorithms series, also available via this link to a playlist on his YouTube channel (there will be more videos coming):

the bubble sort video
the selection sort video
the insertion sort video (took Simon two days to make)
the merge sort video (was the most painful one)

Simon is also fascinated by more exotic sorting algorithms, such as a sorting network:

Simon used the following resources: Daniel Shiffman’s tutorial on Quicksort, Timo Bingmann’s sort algorithms visualization, Must Know Sorting Algorithms in Python, a medium blog on sorting algorithms, Brilliant.org’s computer science courses, Wikipedia.