One thing I always wondered is: what makes dynamic programming more "dynamic" than regular programming? Why is recursion "static" but it becomes "dynamic" if you store results?
According to wikipedia: https://en.wikipedia.org/wiki/Dynamic_programming#History_of...
The word dynamic was chosen by Bellman to capture the time-varying aspect of the problems, and because it sounded impressive.The word programming referred to the use of the method to find an optimal program, in the sense of a military schedule for training or logistics. This usage is the same as that in the phrases linear programming and mathematical programming, a synonym for mathematical optimization.
Also, Harold J. Kushner stated in a speech that, "On the other hand, when I asked [Bellman] the same question, he replied that he was trying to upstage Dantzig's linear programming by adding dynamic.
For example let's look at the fibonacci sequence, F(n) = F(n-1) + F(n-2), naively you just fill in a (1 dimensional) table with the results [1, 1, 2, 3, 5, 8, 13...] and it feels static because there's nothing to choose or decide.
In contrast for example the longest common subsequence looks like this:
lcs[m, n] = 0 if m = 0 or n = 0
lcs[m, n] = lcs[m-1, n-1] + 1 if X[m] = Y[n]
lcs[m, n] = max(lcs[m-1, n], lcs[m, n-1]) if X[m] != Y[n]
I still have no idea why it's called "dynamic".
Neither did I – until I read TFA :)
Our industry has a bad habit of this, where we name things in such a way that make them harder to explain.
See for example one of my other pet peeves: "lambdas". Sounds fancy and difficult! Sounds like a concept you may read about in a research paper! The reality is that it's really quite simple, and we do ourselves a disservice when we name things like this.
2. Naming things
3. Off-by-one errors
[Welcome to Coffee Talk, with Linda Richman. Todays topic: Wave Function Collapse is neither quantum physics, particles, waves, nor collapsing functions. Discuss amongst yourselves, while I am constrained to solve all these Sudoko puzzles. Oh, I am so verklempt!]
https://news.ycombinator.com/item?id=42749675
DonHopkins 6 months ago | parent | context | favorite | on: Generating an infinite world with the Wave Functio...
Ha ha, great comment! You're right, WFC's name just refers to quantum mechanics because it sounds cool, not because the algorithm has anything to do with physics, waves, or collapsing functions (it's more just a constraint based Sudoko solver). But I perceive it more as a playful buzzword for a useful algorithm, and not as maliciously deceptive like Deepak Chopra, who I was just commenting on recently (Quantum was cool until Deepak Chopra ruined it for everybody):
https://news.ycombinator.com/item?id=42714477
I do think it's useful combined with other techniques like procedural programming, cellular automata, Voronoi diagrams / jump flooding, noise, etc, to steer the higher and lower level structures. Check out Maxim Gumin's work on Markov Junior!
https://twitter.com/ExUtumno/status/1531992699997507586
Maxim Gumin @ExUtumno: I published a new project about combining rewrite rules and solving constraint problems made of rewrite rules
https://github.com/mxgmn/MarkovJunior
I think the really nice property of WFC is that it's very naturally and easily artist-driven. It doesn't require programming skills to use, you just supply it with a bunch of concrete before and after examples. (Like "Programming by Example".) That makes it much easier for a wide range of people to use, which is an important feature for democratizing custom world generation. Especially when you can construct or discover the examples in-world, and have it operate kind of like a 2-d tile or 3-d cube auto-complete, that looks at the rest of the stuff you've built or seen, like Canvas does with 1-d code.
https://news.ycombinator.com/item?id=42751176
DonHopkins 6 months ago | parent | context | favorite | on: Generating an infinite world with the Wave Functio...
The difference between Deepak Chopra's abuse of Quantum Physics terminology and WFC's is that WFC actually works and is useful for something, and its coiner publishes his results for free as open source software and papers, so he deserves more poetic license than a pretentious new-age shill hawking books and promises of immortality for cash like Deepak.
Here are some notes I wrote and links I found when researching WFC (which is admittedly a catchier name than "Variable State Independent Decaying Sum (VSIDS) branching heuristics in conflict-driven clause-learning (CDCL) Boolean satisfiability (SAT) solvers"):
https://donhopkins.com/home/wfc-notes.txt
Here are some notes I wrote and links I found when researching Wave
Function Collapse (WFC). -Don Hopkins
Wave Function Collapse
Maxim Gumin
Paul Merrell
https://paulmerrell.org/research/
https://paulmerrell.org/model-synthesis/
Liang et al
Jia Hui Liang, Vijay Ganesh, Ed Zulkoski, Atulan Zaman, and
Krzysztof Czarnecki. 2015. Understanding VSIDS branching heuristics
in conflict-driven clauselearning SAT solvers. In Haifa Verification
Conference. Springer, 225–241.
WaveFunctionCollapse is constraint solving in the wild
https://escholarship.org/content/qt1f29235t/qt1f29235t.pdf?t=qwp94i
Constraint Satisfaction Problem (CSP)
Machine Learning (ML)
Even more fun stuff about WFC, AgentSheets, and defining cellular automata rules by example:
https://news.ycombinator.com/item?id=42749578
And now about "Extreme Learning Machines" and "Liquid State Machines":
https://news.ycombinator.com/item?id=42750857
DonHopkins 6 months ago | parent | context | favorite | on: Generating an infinite world with the Wave Functio...
Like calling random vector functional link networks and single-layer feed-forward networks with random hidden weight an "Extreme Learning Machine".
https://en.wikipedia.org/wiki/Extreme_learning_machine#Contr...
>Controversy
>There are two main complaints from academic community concerning this work, the first one is about "reinventing and ignoring previous ideas", the second one is about "improper naming and popularizing", as shown in some debates in 2008 and 2015.[33] In particular, it was pointed out in a letter[34] to the editor of IEEE Transactions on Neural Networks that the idea of using a hidden layer connected to the inputs by random untrained weights was already suggested in the original papers on RBF networks in the late 1980s; Guang-Bin Huang replied by pointing out subtle differences.[35] In a 2015 paper,[1] Huang responded to complaints about his invention of the name ELM for already-existing methods, complaining of "very negative and unhelpful comments on ELM in neither academic nor professional manner due to various reasons and intentions" and an "irresponsible anonymous attack which intends to destroy harmony research environment", arguing that his work "provides a unifying learning platform" for various types of neural nets,[1] including hierarchical structured ELM.[28] In 2015, Huang also gave a formal rebuttal to what he considered as "malign and attack."[36] Recent research replaces the random weights with constrained random weights.[6][37]
But at least it's easier to say, rolls off the tongue smoothly, and makes better click bait for awesome blog postings!
I also love how the cool buzzwords "Reservoir Computing" and "Liquid State Machines" sounds like such deep stuff.
https://news.ycombinator.com/item?id=40903302
>"I'll tell you why it's not a scam, in my opinion: Tide goes in, tide goes out, never a miscommunication." -Bill O'Reilly
How about rebranding WFC as "Extreme Liquid Quantum Sudoko Machines"? ;)
Then there's "Crab Computing"!
https://news.ycombinator.com/item?id=42701560
[...] If billiard balls aren't creepy enough for you, live soldier crabs of the species Mictyris guinotae can be used in place of the billiard balls.
https://web.archive.org/web/20160303091712/https://www.newsc...
https://www.wired.com/2012/04/soldier-crabs/
http://www.complex-systems.com/abstracts/v20_i02_a02.html
Robust Soldier Crab Ball Gate
Yukio-Pegio Gunji, Yuta Nishiyama. Department of Earth and Planetary Sciences, Kobe University, Kobe 657-8501, Japan.
Andrew Adamatzky. Unconventional Computing Centre. University of the West of England, Bristol, United Kingdom.
Abstract
Soldier crabs Mictyris guinotae exhibit pronounced swarming behavior. Swarms of the crabs are tolerant of perturbations. In computer models and laboratory experiments we demonstrate that swarms of soldier crabs can implement logical gates when placed in a geometrically constrained environment.
https://www.futilitycloset.com/2017/02/26/crab-computing/
And of course "Moveable Feast Machines":
https://news.ycombinator.com/item?id=15560845
https://news.ycombinator.com/item?id=24157104
https://news.ycombinator.com/item?id=34561910
The most amazing mind blowing MFM demo is Robust-first Computing: Distributed City Generation:
You'd hardly see people rallying behind concepts like pure functions or clean code if they were called brown functions or moist code.