Just a funny piece from a member-only Coding Train session ðŸ˜‰

# Category Archives: Milestones

# 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”

# 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:

# 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’s earlier video about the math behind the Towers of Hanoi puzzle:

# 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:

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.

# Simon’s Computer Science Algorithm Suggestions

Simon’s suggestion for the Coding Train on GitHub:

Because I like computer science these days, here are some computer science algorithm suggestions:

- Data Structures
- Array
- Linked List
- Hash Table
- Stack
- Queue
- Priority Queue (Binary heap)
- Suffix Array
- Graph Theory
- Graph (general)
- Tree
- Binary Tree
- Full vs. Complete
- BST
- Binary Heap
- AVL Tree
- Red-Black Tree
- Segment Tree
- DFA

- Biparite
- UFDS
- Fenwick Tree
- Min Spanning Tree
- Suffix Tree

- Computational Geometry
- Polygon, etc.

- Algorithms
- Shuffling
- Fisher-Yates Algorithm

- Sorting
- Bubble Sort
- Selection Sort
- Insertion Sort
- Merge Sort
- Quicksort
- Counting Sort
- Radix Sort
- More?
- Even More? (Scroll down to see a GIANT table)

- Traversal / Pathfinding / SSSP
- Basic
- Pre-order
- In-order
- Post-order
- Depth-first
- Breadth-first
- More?

- Shortest Pathfinding
- Dijkstra’s Shortest Path
- A*

- More?
- Even More?

- Basic
- Substring Finding
- Brute-force
- DFA
- KMP
- More?

- Min Spanning Tree
- Brute-force
- Kruskal’s Algorithm
- Prim’s Algorithm(s)

- Max-flow
- Graph Matching
- Cycle Finding
- Convex Hull
- Gift Wrapping
- Graham Scan
- Quickhull
- “The Ultimate Planar Convex Hull Algorithm”
- More?

- Min Vertex Cover
- Brute-force
- MVC
- Approximation

- Traveling Salesman
- Brute-force
- Dynamic Programming
- Approximation

- Steiner Tree

- Shuffling

If you’re brave, Do you want more even after *all of this*?

One last note: **you’re not going to do all of them (probably!)**.

# Vladimir Krasnoukhov at MathsJam Antwerp!

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 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’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

# Is Nothing a Thing?

# Experimenting with random walks in Wolfram Mathematica

Simon’s code is published online at:

https://www.wolframcloud.com/objects/monajune0/Published/Random_walk_distribution.nb

https://www.wolframcloud.com/objects/monajune0/Published/Random_walk_distribution2D.nb

“If I take many random walks and see what the endpoints of those random walks are, what I’ll find is a Gaussian distribution!” Simon says. In the video, he programs 1D and 2D random walks and 2D and 3D histograms to show the distribution of the endpointsâ€‹ in Wolfram Mathematica.

# 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.