Melvin's digital garden

FB posts 2022

Dec 28: TIL secondary school posting in Singapore uses the serial dictatorship algorithm. It is strategy-proof and Pareto-efficient. We have a special tie-breaker for the last places. This problem is known as the https://en.wikipedia.org/wiki/House_allocation_problem https://www.moe.gov.sg/secondary/s1-posting/how-posting-works

Dec 27: In the spirit of Advent of Code, here is a neat little problem. Given a union of k disjoint matchings where every node on the left is matched to a different node on the right, is there an efficient way to split it back into k matchings? The example below is the union of the red and blue matching.

Dec 23: The most beautiful package received this year from an e-commerce store. Wonder if it is a year end thing? I’ve bought the exact same item a few times and never had such nice packaging.

Dec 15: TIL the world’s largest mind map was created by one person over 25 years and contains more than half a million nodes. It is also publicly available at https://www.jerrysbrain.com/ https://www.jerrysbrain.com/home

Nov 20: Will be heading down for ABGF on the 26th morning and then to Learning Day at Serangoon Public Library in the afternoon. https://www.origame.co/asian-board-games-festival-2022 https://www.eventbrite.sg/e/learning-day-nov-2022-registration-432427360877

Nov 13: Making props for LearnX Marketplace @ Tampines Regional Library, 19th Nov (Sat) 1-4pm. There will be 7 booths for different LearnX communities. I’ll be at the Learning Day booth. See https://www.eventbrite.sg/e/learnx-marketplace-tampines-regional-library-tickets-438854524697 for more details.

Oct 22: TIL the ranking system in Karate/Judo originated from the Go levels formalized by Hon’inbō Dōsaku. The 9 levels of dan ranks is likely inspired by the Chinese 九品制. https://www.youtube.com/watch?v=MiQnwLRWdrU

Oct 12: Managed a win as black, against the weakest level of AhQ Go in an even game with komi of 7 points. By giving extra points or using handicap stones, it is possible to have a fair game against a stronger opponent and slowly work your way up.

Sep 27: Playing white against Hactar Go https://gowrite.net/hactar/ in a game of Capture Go (first to capture wins). Despite the name of the game, the best way to win is to occupy more territory rather than try to capture the opponent’s stones.

Sep 26: Me, Makie, and kitten vs angry snake in Procedural Realms http://www.proceduralrealms.com/ A MUD with a procedurally generated world, turn-based combat, base-building, and a beautiful Web UI. There are no graphics but I’m having a good laugh imagining a kitten punching a snake.

Aug 30: Working through the excellent intro to Go lessons by Michael Redmond, the only Western 9-dan pro. Coupled with KataGo as a training partner using KaTrain to analyze the moves. https://www.youtube.com/watch?v=KTWujSwL2bQ&list=PLW5_cMTm0wvamCNX7qNoUqbXxeHt9n67i

Aug 20: Had a small scare when my desktop failed to boot after updating systemd. Turns out it added a mount option for cgroup which isn’t supported on the installed kernel. Fixed by booting from USB, chroot into the host system, and installing a new kernel. Whew!

Aug 16: “The alarms were saying there’s no more storage space, we’re going to flush everything and sort of reconstruct it. Do what you would call a restart.” – Don Eyles https://www.youtube.com/watch?v=z4cn93H6sM0

Jul 30: “This 21-minute film was prepared for Ron Graham’s 80th birthday. It celebrates Graham’s remarkable career as a mathematician and magician, as well as his important leadership roles in many of the institutions that support the pursuit of mathematics throughout the world.” Source: http://www.zalafilms.com/films/something.html https://vimeo.com/136044050

Jul 17: Yet another stochastic process with a food metaphor. The Indian buffet process is as follows: The first customer samples Poisson(α) dishes. The ith customer samples each dish k with prob m_k/i, where m_k is the number of previous customers who sampled this disk, and then tries an additional Poisson(α/i) new dishes.

Jul 14: TIL there is a distribution over partitions known as the Chinese restaurant process. When the ith customer arrives, he/she joins a table with k people with prob k/(i-1+α) and a new table with prob α/(i-1+α). https://www.lancaster.ac.uk/stor-i-student-sites/daniel-dodd/2021/03/27/the-chinese-restaurant-process/

Jul 06: Private txns on a public blockchain sounds like an oxymoron but it is possible by sprinkling some “crypto magic”. Prof Dan Boneh reveals how it works in this MOOC lecture. Course materials are on https://defi-learning.org/f21 https://www.youtube.com/playlist?list=PLS01nW3RtgorEzMOg2dpg7KwB5nhQHhSw

Jun 26: Sentient furniture! From the release notes, “When a piece of furniture that a dynamic quest expects you to place something in or on spawns as a newly sentient being, you are now always allowed to trade with that being regardless of whether they have anything in their inventory.” https://store.steampowered.com/news/app/333640/view/3343374889363594727 https://store.steampowered.com/news/app/333640/view/3343374889363594727

Jun 26: An interesting tidbit about the discovery of smoothed analysis. Spielman: “Part of it was that we’d been coding up all these examples. And we noticed if we weren’t really careful with the numerical precision, then suddenly things that were supposed to break the simplex method didn’t. So that’s how we got the idea that if there was a little randomness in the inputs, the method would be fine.” source: https://www.quantamagazine.org/the-computer-scientist-who-parlays-failures-into-breakthroughs-20220613/ https://www.quantamagazine.org/the-computer-scientist-who-parlays-failures-into-breakthroughs-20220613/

Jun 22: TIL Google Drive on mobile has the ability to create scanned PDF using the camera. Activate by selecting “Scan” when creating a new document. Used it to digitize the notes I took from yesterday’s PyCon SG 2022 Edu Summit. I shared about using Python instead of Javascript for web scripting. https://melvinzhang.keybase.pub/calc/

May 22: Will be demoing how to fold an origami envelope at the next in-person Learning Day! Save paper by writing your wishes and then folding the paper into an envelope :)

May 21: Great title, direct and without any jargon. TLDR: Household cats looked longer at the monitor when the cat that appeared on the screen did not match the name that was called out. https://www.nature.com/articles/s41598-022-10261-5

May 14: TIL that as a pendulum I have a period of 2.25s. Used to measure dead hang duration by counting the number of swings.

May 04: When your implementation based on the equations in an article matches the example exactly (after some debugging).

May 02: TIL mean cumulative function is a method for non-parametric analysis of recurrent events. In particular, it can be used to estimate retention from user sessions. Unlike survival analysis, MCF does not need to know when a user churns, an event which may not be observable. https://ieeexplore.ieee.org/abstract/document/8950075

Apr 27: “The power of shit. Our excrement is a natural, renewable and sustainable resource – if only we can overcome our visceral disgust of it.” https://aeon.co/essays/a-short-biography-of-human-excrement-and-its-value

Apr 24: A challenging block-pushing puzzle with 50 levels. I was stuck on level 9 for several days and finally cleared it with the help of hints. https://gate.itch.io/ghost

Apr 24: “The whole thinking process is still rather mysterious to us, but I believe that the attempt to make a thinking machine will help us greatly in finding out how we think ourselves.” https://aeon.co/essays/why-we-should-remember-alan-turing-as-a-philosopher

Apr 19: TIL why a problem is in NP implies it has an efficient verifier. NP means solvable by a nondeterministic algorithm in polynomial time. Think of nondeterminism as exploring multiple paths at the same time. The key is that the execution trace of the algorithm which leads to the solution is polynomial in length. We can create an efficient verifier that takes as input the execution trace and check that it is valid run of the algorithm.

Apr 14: Finally figured out what this playground equipment does! Or at least I have a decent hypothesis, hard to find any hard evidence though. Has anyone seen something like this and knows more about it?

Apr 13: In-person Learning Day is back after a two years break! We have been holding it online in the meantime. Thanks to NLB for the venue. TLDR: each participant shares something for 15mins, anything goes. https://www.eventbrite.sg/e/learning-day-april-2022-registration-293671398057

Apr 05: I have a bit of a problem with bookmarking, close to 4k bookmarks. I’ve started moving them to https://archivebox.io/, the killer feature is that it takes a snapshot of the page and allows me to search the contents. https://archivebox.io/

Apr 02: The inner lives of dwarves in Dwarf Fortress. Looking forward to the improved UX. https://store.steampowered.com/news/app/975370/view/3182363591878108006

Mar 29: TIL Sokoban allowing both push and pull is as hard as the original. Details: Sokoban is PSPACE-complete (Culberson 1997, emulate a linear bounded automata). Sokoban with pull instead of push and Sokoban with both push and pull are also PSPACE-complete (Pereira et al. 2016, reduction from Nondeterministic Constraint Logic). PSPACE-complete are the hardest problems in PSPACE, i.e. uses polynomial space to solve without any bounds on the time.

Mar 27: It is with great sadness that I’ve completed Robin Johnson’s excellent time-traveling Sokoban https://versificator.itch.io/block-pushing-puzzle-game-but-you-can-time-travel. Lots of interesting designs, especially Level 16 and 20. Other variations seem interesting as well, for example, allowing other-selves to see the current self but requiring them to reach the portal.

Mar 26: It is a wonderful feeling when someone has already made the thing you want to play. Time travel as a mechanic has always fascinated me and the simplest place to start is probably adding it to Sokoban. https://versificator.itch.io/block-pushing-puzzle-game-but-you-can-time-travel

Mar 20: “A passionate team of engineers from the company OpenAI is challenged to develop an artificial intelligence capable of defeating the World Champions of DOTA 2, a video game more complex than anything attempted by AI in the past — and given only one year to do it. The outcome could alter the way we think about advanced AI systems.” https://www.youtube.com/watch?v=AZQeaUyNVsw

Mar 16: Good to have in-person maker activities resumed. Hopefully, in time we will be able to take part in Maker Faire Singapore again. The event runs from 10am to 6pm at Jurong Spring CC, this Fri/Sat/Sun.

Mar 13: “In a nutshell, the main idea behind this course is that the development of the digital computer, together with the theory of computation, is also one of the most important developments in mathematics in the 20th century. Consequently, this course takes a fresh look at some of the standard concepts of discrete mathematics, with strong and consistent emphasis on computation and algorithms.” https://www.cs.cmu.edu/~sutner/CDM/index.html

Mar 10: “As game developers we want to create new worlds, not to destroy the one we have. That’s why we’ve banded together to present this charity bundle to help Ukrainians survive this ordeal and thrive after the war ends.” https://itch.io/b/1316/bundle-for-ukraine

Mar 09: While reviewing my Minsky machine activity for outreach, I thought about making it more open-ended. Instead of drawing the flowchart to do X, come up with a flowchart to end up with the largest sum of all counters. There are two variants, 1) all counters start at zero 2) starting with n in counter 1. Some initial results are on the linked page for up to 11 instructions. https://github.com/melvinzhang/counter-machine

Mar 01: Such a wholesome thing for Gabe to hand-deliver the first batch of Steam Decks. Valve has done an excellent job making Linux gaming a viable alternative. https://www.youtube.com/watch?v=9Dy-KWjp-m0

Feb 25: Replaced slow Bayesian optimization with fast Ternary search to find an MLE of h, since the log-likelihood is probably unimodal. Unfortunately, I’m unable to prove it. log(p(T|h)) is the log-likelihood for unknown positive parameter h and a known set of real numbers T. Is this known to be unimodal wrt to h? Note: this comes from using a memory model where the probability of recall is 2^(-t/h) where t is the time elapsed and h is the memory half-life. Negative t represents an instance where the learner forgot.

Feb 22: KeyForge is a card game that I wouldn’t have expected to work. Every printed deck is procedurally generated and unique. You cannot mix cards from different decks. It bears some resemblance to MagArena’s random duels, where both decks are procedurally generated before each game. https://www.fantasyflightgames.com/en/products/keyforge/

Feb 20: Seven MYTHS about metabolism from New Scientist Vol 249, Issue 3323 by Herman Pontzer: Myth 1. Exercise burns through calories and boosts metabolism Myth 2. Exercise will make you lose weight Myth 3. Your workout programme isn’t succeeding unless you are losing weight Myth 4. Calories don’t matter Myth 5. Humans evolved to eat a Paleo diet Myth 6. A slow metabolism dooms you to obesity Myth 7. Obesity and weight gain are a sign of personal failure Link below for the full article and the findings. https://www.swt.org/oshare/newscientist/MetabolismMyths-2021-0227.pdf

Feb 19: Three things that stand out in Guild Wars 2: 1) the helpful community, 2) the mounts and their unique movement, 3) the awesome soundtrack. https://www.youtube.com/watch?v=-A58r8V7-SQ

Feb 13: Ray core is a great replacement for Python’s multiprocessing module. It even supports the Pool API for a direct drop-in replacement. Its own API is well designed and works both locally and in a cluster. https://www.ray.io/ray-core

Feb 09: TIL Python can be used to customize Vim. I probably don’t need it for what I’m doing but it feels great modifying the editor using a familiar language. I’m changing the ‘jump to tag’ to create a new note if the tag does not exist instead of showing an error. https://vimhelp.org/if_pyth.txt.html

Feb 05: Joining the coffee crowd after many years of drinking mostly tea. Got a pack of Trung Nguyen’s S blend and phin (metal filter). https://meile.com.sg/coffee-filter-coffee-maker/trung-nguyen-filter

Feb 01: AFAIK public FB profile posts are only visible to logged in FB users despite being described as “Anyone on or off FB” Thankfully there is an option to export all posts. I’ve put them up on my digital garden for better accessibility. Correction: you can view public posts if you know the link, but they don’t show up on the public profile page. https://garden.melvinzhang.net/posts/social_media_posts/

Jan 30: Starting a digital garden 🌱 to slowly consolidate my writings in one place. At the moment, it contains my past sharings from Learning Day, https://www.facebook.com/groups/praxiumlearning https://garden.melvinzhang.net/

Jan 22: “Computer scientist Amit Sahai, PhD, is asked to explain the concept of zero-knowledge proofs to 5 different people; a child, a teen, a college student, a grad student, and an expert.” https://www.youtube.com/watch?v=fOGdb1CTu5c

Jan 15: TIL Cuttle is a combat card game from the 1970s, played with a standard 52-card deck. It predates Magic: the Gathering but has similar mechanics such as units and effects. A simple alternative to the ever-growing complexities of MTG and the like. https://github.com/shmup/card-game-rules/blob/master/cuttle.md

Links to this note