> Only once you know for a fact that a better solution is possible can you actually think of that solution
This section reminded me of something a friend posited about space travel.
There are some inventions that just being exposed to the idea of them is enough to invent them. For instance, it seems that cultures that encounter others that have written language fairly quickly invent their own, even without knowledge of how the others work. The Cherokee syllabary was invented by an illiterate silversmith in the 1820s after he saw other people communicating via paper and knew that they represented a way to transmit information (https://en.wikipedia.org/wiki/Sequoyah#Sequoyah_and_Cherokee...). The writing system that he invented was a syllabary, not an alphabet like the people he'd been observing or a logographic system like some other Native American languages. Having a writing system is a contagious idea all its own and knowing that they exist is sufficient to invent one.
It may be that efficient space travel is one of these inventions: just seeing someone else do it may be enough to invent it ourselves. I don't mean in the sense that we may observe details that give us hints as to how it works (though that's probably also true), I mean in the way that the article says "If nobody had gotten to the score of 180 before me, I couldn’t have thought of any faster way of solving this puzzle. Without that piece of information, the brain just comes up with reasons why the score is already optimal". Simply observing working space travel may be enough for us to invent it ourselves. We may even invent a system entirely unlike the one we observed.
The idea of using a fake result to break a paradigm has been used in a number of science fiction stories. I believe that the earliest is "Noise Level" (1952) by Raymond F. Jones, though the idea originated with John W. Campbell [0]. I first came across this concept in Robert Silverberg's "Double Dare" (1956) [1].
It has been used in reality as well. The Manhattan project is a well known example, where the US military lied to the scientists telling them the Germans were ahead in the game.
And even in computer science you have that kind of inequality of difficulty of problem and solution: NP is the class of problems in which solutions can be checked if they are correct in polinomial time.
Something a bit stronger than the Egg of Columbus, I think. With the Egg, anybody can do it once they see how it is done. Here, anybody can do it once they see that it can be done.
>The writing system that he invented was a syllabary, not an alphabet like the people he'd been observing or a logographic system like some other Native American languages.
For some reason, the alphabet seems to be extremely difficult to invent. IIRC it only happened once, with the Jews laying down the foundations and then the Greeks actually taking it all the way with vowels (I shudder to think what the world would look like if the Bronze Age collapse hadn't wiped out literacy in Greece). OTOH syllabaries/logographic systems have been invented independently a _lot_ of times all over the world.
Writing has developed independently between two and five times (Mesoamerica and Sumer for sure, maybe China, Egypt, India in decreasing order of likeliness). All of these start with a logographic script, which then gets filtered into a syllabalic component. Egypt dropped the vowels from its representation, having its characters represent only consonants--this was adapted by the Phoenicians. The Greeks took the Phoenician script, repurposed some of the characters representing consonants they didn't have into vowels, and created the first true alphabet (whence Latin, Cyrillic, Georgian, and Armenian, basically every true alphabet in the world). The Arabics and Hebrews adapted the script into their modern abjads (where vowels are marked, if ever, by diacritics), while the abugidas developed (where vowels are indicated by systematic manipulation of consonants) in India by debatable means.
Alphabets, abjads, and abugidas were effectively independently invented only once (it's debatable to what degree the creators of Hangul were aware of other alphabets). Syllabries appear to be the very natural development of writing.
It was the Phoenicians who invented alphabetic writing (well, actually an abjad), not the Israelites, who, as with the Greeks, borrowed and adapted the Phoenician script.
For some reason, the alphabet seems to be extremely difficult to invent.
You might be right, although the one known invention of it spread around pretty well, seeing as the Phoenicians primarily got around by sea. And I'm not sure it's always needed: while I'm not familiar with Cherokee, to the extent I understand Japanese, at the lowest levels it's encoded as a syllabary because that's the way their language works, and the ideographs they borrowed from China known as kanji in part help to distinguish between the many homonyms that are inherent in such a language, with the relatively few exceptions to strict use of syllables either easily encoded or a matter of spoken dialect.
Japanese was first written in kanji (borrowed Chinese characters), with the syllabaries created hundreds of years later. Though you could say modern Japanese is encoded as a syllabary.
Do you happen to know how japanese input methods generally work?
I have seen chinese and japanese steno machines before, e.g. chorded strokes that cover one or more sillables. That takes specific hardware and a bunch of training, though, so I'd guess it isn't the primary one.
I'm a beginning Japanese learner. I really know nothing about the language. But here is how it might be typed (at least by a non-expert like me):
Suppose you're sitting at a keyboard with Roman letters. If you want to type a sentence, you might first type the "anofuyuhataihensamui" keys. The IME would convert that into a stream of Hiragana characters as you type to get あのふゆはたいへんさむい.
To do that with a cell phone, you would have to press keypad keys to get the character you want. This isn't too bad since there are only 46 basic Hiragana characters. iOS and android have nice "flick" interfaces for this: https://www.youtube.com/watch?v=2LY0-8-PXSc#t=125s These interfaces are efficient because they're adapted to the small set of Hiragana characters you write. Some teenagers can (painstakingly) write entire novels on the cell phone like that.
Hiragana characters can express all the sounds of the Japanese language. Unfortunately, they're not very readable because there are no visible word breaks and because Japanese has lots of homonyms. To make the above readable, you need to make a second pass over the sentence you wrote, converting ふゆ into 冬 and たいへん into 大変 and さむい into 寒い with the arrow keys and space bar. I think it's common to do this after every word so you don't get too far behind. At the end, you get the sentence you want: あの冬は大変寒い, after a dozen or so keystrokes of overhead.
Some modern IMEs try their best to convert kana to kanji as you type. Apple's Japanese IME, for example, converts that sentence without any extra input. But frequently you have to do at least a little bit of post-processing.
I think it's common for actual Japanese people to type using an American keyboard by inputting the romanization of the words they use. There are keyboards that have one key per hiragana character, but I think they're not as common.
From what I understand, Chinese is frequently typed with Pinyin, another romanization scheme. There are more challenges though: first, the lack of a syllabry like Hiragana means there's no intermediate representation. Second, Mandarin uses tones on each syllable which aren't captured in Latin letters. This can also be different between different dialects and geographic locations. Taiwan, for example, has some interesting differences compared to mainland China: https://www.quora.com/Do-Taiwanese-use-Pinyin
I'm jealous you found such a great friend to play the game with. ;-) I found the game interesting but without social interaction it wasn't able to keep me engaged... So I uninstalled it after a day or so.
Secondly... I reinstalled the game and opened up the second puzzle to see what my score was. Surely _my_ solution must have been better than the standard 240? Nope! Now I'm scratching my head trying to figure out how you did it. You bastard! ;-)
> I'm jealous you found such a great friend to play the game with. ;-) I found the game interesting but without social interaction it wasn't able to keep me engaged... So I uninstalled it after a day or so.
I'm in a university, surrounded by people who do this sort of thing for fun, and no one I know will play the game. We've come to jokingly call it "work-simulator" and most people I've talked to who should enjoy this game just see "oh no it's work".
My reaction was pretty much the same. Not really "oh no, it's work", but "if I'm going to code, I want to code something other people (and I) can use. For example, a friend and I had a few spare hours, so we made this:
That sort of thing seems like a better use of my time than playing a game. Then again, there are times when I just want to play a game, and I don't want to code, so I don't begrudge anyone how they choose to spend their time.
For both of you I recommend Factorio. It's more game-like and you don't realise as easily that you're (essentially) programming, since it feels like you're just building conveyor belts to move materials around.
Yeh, I haven't tried Shenzen I/O yet, though I intend to. But I've played TIS-100 and I actually got into it because I saw people on IRC competing via leaderboards with one another. It's quite fun.
I cracked open this game when a friend was visiting. We pair programmed on it for hours and it was a blast. Now I can't quite bring myself to play it alone.
A few of the lessons he talked about I've seen repeated on Casey Muratori's "Handmade Hero" series. Specifically point #3, he talked early on about writing simple code that fulfills one metric: it works. Afterwards you can see the implicit parts that should be made into functions, remove code duplication, and clean things up. However having that "full view" of a chunk of code makes the process easier.
Also point #4, he writes an interactive write-compile-test system using an executable hooking into a shared library which contains all of your code. That way you can compile and see the results quickly on a still running executable of your game. Very fast feedback without having to "respawn" to a part of your game to test.
The tests are an important part of the lesson for certain. Even better is the lesson that throwing a test spec over the wall to your development team may result in them writing code that passes the test but isn't necessarily ideal for production.
I've played many hours of this game and have committed many grievous programming sins to improve my scores.
> throwing a test spec over the wall to your development team may result in them writing code that passes the test but isn't necessarily ideal for production.
That sounds similar to an XY problem. You actually need help with X, but you think you already know how to go about it so you ask about your approach, Y, instead... resulting in whatever answers you get being much worse than if you had actually clearly explained what you were doing in the first place.
This is why I love learning and writing in multiple programming languages. The abstractions and advantages in each language push me to search out the best in whatever language I'm working in at the time, rather than being limited by the common paradigms in that language.
I don't really see the point of these TIS-100 style games that use made-up instruction sets. Wouldn't it be more interesting if the game used a real instruction set (e.g. AVR, x86)? Then we could be learning something useful while playing, and make use of the results.
Real ISAs are too complex. SIO assumes one cycle for all instructions, and discards binary, among other affordances. This makes the game more accessible. Also, the instruction set is optimized so that you can't do too much in a single instruction, so as to keep the space constraints meaningful.
Now, if you were talking about the DCPU-16, I'd agree.
The instruction set is finely tuned to make interesting puzzles. Most of my time in each puzzle was spent trying to cram 1 more instruction into a chip here or there.
Since real instruction sets have to be practical for production use, I imagine it would be harder to get the same effect.
Plus you wouldn't get cool features like being able to conditionally execute every instruction.
> Plus you wouldn't get cool features like being able to conditionally execute every instruction.
You would be very close if it were ARM :)
My wild guess is that the developer wisely chose to sidestep imbalance towards parts of his public and any possible IP issues on the IS. Plus if he writes this kind of games he probably had fun writing his own IS.
> Since real instruction sets have to be practical for production use, I imagine it would be harder to get the same effect.
I'm not so sure. Have you ever hand-optimised asm? I recall spending hours if not days trying to reduce the instruction count by 1 or 2 instructions in a tight DSP loop (Motorola 56k). It always seems like an interesting puzzle to me.
I remember when a friend and I started optimizing a DES library in C at university in 1990. We had the same dynamics of the post, each other skimming off some cycles even when we thought that one of us got to an unbeatable implementation. We obviously had tests to prove correctness and measure speed. Bizarrely there weren't many tests around in the industry back then. I can't remember when I wrote my first unit test after then.
For those wondering (spoilers), the puzzle he's talking about in section 2 ("the second puzzle in the game") is a simple puzzle where you just have to double the values provided as input to produce an output. The naive solution at 240 points he mentions is extremely straightforward:
mov p0 acc # place input value into internal register
mul 2 # multiply register by 2
mov acc p1 # place register value into output
slp 1 # sleep 1 cycle, wait for next input
The only way (I can think of) to optimize this is by cheating, i.e. by writing an algorithm specifically fitted for the kind of input we have to deal with. Looking at the input, we see that for example there are only 3 input values (0, 25 and 50) and there seems to be more zeros than other values. Based on this info we can try to predict what value is likely to show up as input and follow a dedicated path to handle it, in order to be as efficient as possible.
I must admit I was happy with the 240 solution and never thought there was a better way until I read this article. Now I feel obliged to at least go down to 156 :D
>The only way (I can think of) to optimize this is by cheating, i.e. by writing an algorithm specifically fitted for the kind of input we have to deal with.
Programmers must stop equating cheating with engineering.
It really is an interesting game. I'd first started with this sort of genre playing Human Resource Machine, which simulates a single accumulator architecture, and very interesting set of puzzles. The puzzles really are just standard sorting, string reversal, prime factorization. The best part I find about it is the way Pointers and Memory allocation/access and stack access is done. I'd recommend this game very much as the puzzles aren't very hard and the progress is really satisfying.
Shenzhen I/O is a great game too! But I got stuck at one point and as another comment points out, I also gave up on it. Maybe it's time to log into Steam. :)
In all seriousness, I was expecting the article to be like "on nov 5th, I went to Shenzhen to attend the annual Shenzhen I/O hardware hacker conference.. and boy was I blown away.. lots of cool stuff people are working on..".. then I'm like, um, a game? what?
Excuse the intrusion, but there's no PM system on HN...
I've noticed your recent, prolific rise to prominence here on HN. You seem to have come out of nowhere and shot past most other users whose accounts are much older. I would be interested in reading an article from you on what you've learned and observed over the past year.
[Boy, harsh. It's not like there's an email address on the guy's profile. Guess I should have contacted him telepathically. Yet another reminder to keep showdead on.]
Gee. I had a prolific rise to prominence? I didn't notice. I'm certainly one of the less interesting and skilled people on this forum, so I'm frankly baffled.
Well, since you asked...
The most important thing that I've learned is that it's a good idea to put yourself out there: Say what you think, be honest, and be ready to defend your ideas (but also be ready to admit you were wrong if you find out that you are).
Also, don't worry about the possibility saying something stupid. Some of the best conversations I've had on HN happened because I said something stupid: If you say something stupid, that usually means that you aren't well educated in that area, and hold misconceptions. It's best to get those misconceptions out there, so that you'll know that they're wrong.
Remember to attack ideas, not people. Even when you really, really, want to attack people. It's not worth it.
Don't focus on your karma too much: just because you got downed doesn't mean it wasn't worth saying.
Do you have any thoughts about the voting system on HN? Not that it's going to change, but I am becoming quite tired of seeing worthwhile, interesting comments downvoted into grayness. It feels like a kind of anonymous shaming, like a group of people put on masks, gather around someone, and wag their fingers at them until they are shamed into silence. It only takes a few people to downvote a comment into obscurity, and it may happen by chance that the first few people to see it are censorious, preventing others who would upvote it from even seeing it. I strongly think that there should only be two options: upvote, or flag for rule violations.
He makes one observation in which makes a small but important mistake: When he mentions tests he calls them first unit tests, then automated tests.
And yes, unit tests usually are automated. They are however just one type of automated test, and at the smallest scale too. Integration and system tests are just as important and can give much more bang for much less buck.
You can't optimize for all three judged outputs (production cost, power usage, lines of code) at once. For this reason, you can replay every level three times with a different optimization goal.
Some of the optimization techniques I found before life took my interest away from the game (we[0] are building a real embedded system of significant complexity, and actually visited Shenzhen a few months ago) were judicious use of leading @SLP (usually as a final optimization), use of memory (acquired later in the game) instead of processing inputs, careful investigation of the limited use of conditionals to split codepaths, and basic addition using shared buses.
I'd say TIS-100 is the better game. But I think that's just because it favors a style of optimization that I really enjoy. Ultimately that's what I think it will come down to.
TIS-100 felt more like building some interconnected pipeline but Shenzhen feels more microcontroller-y
Some of the related videos for their intro video on their site are great and make me want to try it. There was one of a guy who created a old school 3D maze with random generated levels and one wich played the whole "rick roll" song . It amazes me we can simulated computers and hardware in a computer with this depth ...inception level 1
Great article, I too loved this game. In fact the article prompted me to fire it up again and figure out the tricks to match his 148 on the 2nd problem and it was really fun.
This section reminded me of something a friend posited about space travel.
There are some inventions that just being exposed to the idea of them is enough to invent them. For instance, it seems that cultures that encounter others that have written language fairly quickly invent their own, even without knowledge of how the others work. The Cherokee syllabary was invented by an illiterate silversmith in the 1820s after he saw other people communicating via paper and knew that they represented a way to transmit information (https://en.wikipedia.org/wiki/Sequoyah#Sequoyah_and_Cherokee...). The writing system that he invented was a syllabary, not an alphabet like the people he'd been observing or a logographic system like some other Native American languages. Having a writing system is a contagious idea all its own and knowing that they exist is sufficient to invent one.
It may be that efficient space travel is one of these inventions: just seeing someone else do it may be enough to invent it ourselves. I don't mean in the sense that we may observe details that give us hints as to how it works (though that's probably also true), I mean in the way that the article says "If nobody had gotten to the score of 180 before me, I couldn’t have thought of any faster way of solving this puzzle. Without that piece of information, the brain just comes up with reasons why the score is already optimal". Simply observing working space travel may be enough for us to invent it ourselves. We may even invent a system entirely unlike the one we observed.