Michael Birken lays out, in detail, a method for teaching a computer to draw arbitrary 8-bit images by playing Tetris, strategically deploying blocks of various colors to cause exactly the picture you want to emerge. The method is (as you'd imagine), starkly terrifying in its complexity, but the video speaks for itself.
The algorithm converts pixels from a source image into squares in the Tetris playfield, one row at a time from the bottom up. To generate an individual square, the algorithm assembles a structure consisting of a rectangular region fully supported by a single square protruding from the bottom. When the rectangular region is completed, its rows are cleared, leaving behind the protruding square. Three examples of the process appear below.
The algorithm can also generate multiple squares with a single structure as shown below.
During construction of a row, all of the squares produced by this method must be supported. In the images above, the generated squares are supported by the floor of the playfield. However, if an arbitrary row contains holes, it may not provide the support necessary for the construction of the row above it. The algorithm solves this problem by constructing a flat platform on top of the row with holes. In the animation below, a platform is built above a row comprising of a single red square. The platform is a temporary structure and inserting the final piece removes it.
Tetris Printer Algorithm
(via Hacker News)
Here's a 40-minute video in which Tom Stuart gives a talk summarizing one of the chapters from him new book Understanding Computation, describing the halting state problem and how it relates to bugs, Turing machines, Turing completeness, computability, malware checking for various mobile app stores, and related subjects. The Halting State problem -- which relates to the impossibility of knowing what a program will do with all possible inputs -- is one of the most important and hardest-to-understand ideas in computer science, and Stuart does a fantastic job with it here. You don't need to be a master programmer or a computer science buff to get it, and even if you only absorb 50 percent of it, it's so engagingly presented, and so blazingly relevant to life in the 21st century, that you won't regret it.
At Scottish Ruby Conference 2013 I gave a talk called Impossible Programs, adapted from chapter 8 of Understanding Computation. It’s a talk about programs that are impossible to write in Ruby — it covers undecidability, the halting problem and Rice’s theorem, explained in plain English and illustrated with Ruby code. The slides are available
Nate Anderson Dan Goodin follows up on Nate Anderson's excellent piece on the nuts and bolts of password cracking with a further attempt to decrypt an encrypted password file leaked from LivingSocial, this time with the aid of experts. The password file they were working on was encrypted with the relatively weak (and now deprecated) SHA1 hashing algorithm, and they were only attacking it with a single GPU on a commodity PC, and were able to extract over 90% of the passwords in the file.
The discussion of the guesswork and refinement techniques used in extracting passwords is absolutely fascinating and really is a must-read. However, the whole exercise is still a bit inconclusive -- in the end, we know that a badly encrypted password file is vulnerable to an underpowered password-cracking device. But what we need to know is whether a well-encrypted password file will stand up to a good password-cracking system.
The specific type of hybrid attack that cracked that password is known as a combinator attack. It combines each word in a dictionary with every other word in the dictionary. Because these attacks are capable of generating a huge number of guesses—the square of the number of words in the dict—crackers often work with smaller word lists or simply terminate a run in progress once things start slowing down. Other times, they combine words from one big dictionary with words from a smaller one. Steube was able to crack "momof3g8kids" because he had "momof3g" in his 111 million dict and "8kids" in a smaller dict...
What was remarkable about all three cracking sessions were the types of plains that got revealed. They included passcodes such as "k1araj0hns0n," "Sh1a-labe0uf," "Apr!l221973," "Qbesancon321," "DG091101%," "@Yourmom69," "ilovetofunot," "windermere2313," "tmdmmj17," and "BandGeek2014." Also included in the list: "all of the lights" (yes, spaces are allowed on many sites), "i hate hackers," "allineedislove," "ilovemySister31," "iloveyousomuch," "Philippians4:13," "Philippians4:6-7," and "qeadzcwrsfxv1331." "gonefishing1125" was another password Steube saw appear on his computer screen. Seconds after it was cracked, he noted, "You won't ever find it using brute force."
Anatomy of a hack: How crackers ransack passwords like “qeadzcwrsfxv1331”
Remember the gigantic data-center that the NSA is building in Utah in order to (illegally) process the electronic communications of the whole world? Turns out that the state of Utah plans on taxing the titanic amounts of electricity it will consume at 6%. The NSA is pissed.
"We are quite concerned [about] this," Harvey Davis, NSA director of installations and logistics, wrote in the April 26 email, obtained through a Utah open records law request.
In a follow-up email Davis sent 31 minutes later, he explained: "The long and short of it is: Long-term stability in the utility rates was a major factor in Utah being selected as our site for our $1.5 billion construction at Camp Williams. HB325 runs counter to what we expected."
HB325, which Herbert signed into law April 1, benefits the Utah Military Installation Development Authority (MIDA). It allows the entity, which was set up to put select military properties on the public tax rolls, to collect a tax of up to 6 percent on Rocky Mountain Power electricity used by the Utah Data Center.
In surprise to NSA, Utah Data Center may pay tax on electricity [Nate Carlisle/The Salt Lake Tribune]
Usborne's 1983 classic Introduction to Machine Code for Beginners is an astounding book, written, designed and illustrated by Naomi Reed, Graham Round and Lynne Norman. It uses beautiful infographics and clear writing to provide an introduction to 6502 and Z80 assembler, and it's no wonder that used copies go for as much as $600. I was reminded of it this morning when @amanicdroid tweeted me with a link to a PDF of the book's interior. I'd love to see this book updated for modern computers and reprinted.
Alex sez, "Algoraves are parties where people come together to dance to algorithms. It generally involves some live coding but any producers making music "wholly or predominantly characterised by the emission of a succession of repetitive conditionals' are welcome. Generally some aspect of the algorithmic processes are visible, but the focus is actually on the audience, and having serious fun.
We've had a few parties across the UK and Germany, and are spreading further afield in Mexico and Australia. The concept is still developing though, and is being defined by whoever turns up."
Here's the video of "It's not a fax machine connected to a waffle iron," the talk I gave at the Re:publica conference in Berlin this week: "Lawmakers treat the Internet like it's Telephone 2.0, the Second Coming of Video on Demand, or the World's Number One Porn Distribution Service, but it's really the nervous system of the 21st Century. Unless we stop the trend toward depraved indifference in Internet law, making – and freedom – will die."
re:publica 2013 - Cory Doctorow: It's not a fax machine connected to a waffle iron
The MIT Media Lab's Lifelong Kindergarten Group has shipped version 2.0 of Scratch, the justly famed and much-loved programming language for kids. Scratch makes it easy to create powerful simulations and games, even for small kids (basically, if you can read, you're ready for Scratch). The new version of Scratch runs right in a browser (no downloads or installs required), and is remarkable in its polish and power to excite. The programming environment is embedded in a sharing and shareable community, with millions of Scratch projects ready to be downloaded and remixed. It's just amazing
With Scratch, you can program your own interactive stories, games, and animations — and share your creations with others in the online community.
Scratch helps young people learn to think creatively, reason systematically, and work collaboratively — essential skills for life in the 21st century.
Share with others around the world
(via O'Reilly Radar)
Wagner James Au sez, "OpenWorm, as the name suggests, is a collaborative open source project to computationally create a simple artificial life form -- an earth worm -- from the cellular level to a point where it's sophisticated enough to solve basic problems. They're still in early stages, with the latest demo, a developer on the project tells me, being 'a particle simulation of five connected muscle segments moving together through a body of water.'"
An Open Source Artificial Life Project Called OpenWorm
Given a standard Tetris engine (which drops pieces in a pseudorandom order, has previews, and allows holding), this method will allow you to play Tetris forever. As always, the most fascinating thing about this is the specialized vocabulary used to describe the method:
Worst case bag distributions such as H?XX?X? and H?XXX?? deserve a special mention. The first piece 'H' denotes a piece which must be placed in Hold in order to follow the STZ loop procedure. Pieces from the LJO loop are denoted by '?', and the remaining pieces are denoted by 'X'. Using 3 previews and Hold, it is only possible to see the first 4 pieces of the bag before the second piece enters the screen. This means you only see H?XX, and only know the first piece of the LJO loop. Because H must be put in Hold, you are forced to make a decision without knowing the order of the rest of the LJO loop. If the O comes first, you can follow the procedure above without problems. The rest of the time you will run into complications like this:
(via Hacker News)
A Hal Pomeranz from 2010 suggests a great way to teach TCP/IP header structure to students: he builds header diagrams out of legos, then mixes them up and has the students reconstruct them.
The use of color here really highlights certain portions of the packet header. For example, the source and destination addresses and ports really jump out. But there are some other, more subtle color patterns that I worked in here. For example, if you look closely you’ll see that I matched the color of the ACK bit with the blue in the ACK number field. Similarly the colors of the SYN bit and the sequence number match, as do the URG bit and urgent pointer field.
Actually I wish I had a couple of more colors available. Yes, Lego comes in dozens of colors these days, but they only make 2×8 blocks (aka one “Lego Byte”) in six colors: White, Black, Red, Yellow, Blue, and Beige.
So while I tried to use Beige exclusively for size fields, Red for reserved bits, Yellow for checksums, and so on, I ultimately ended up having to use these colors for other fields as well– for example, the yellow sequence number fields in the TCP header. Maybe I should have just bought a bunch of “nibbles” (2×4 blocks) in other colors and not been so choosy about using full “Lego Bytes”.
Since 2010, the lego patent has expired and cheapish wire-extrusion 3D printing has become a reality -- and there's cool procedural models for generating arbitrary-sized bricks and labelling them with arbitrary type. Someone needs to make a printable TCP diagramming set on Thingiverse!
Practical, Visual, Three-Dimensional Pedagogy for Internet Protocol Packet Header Control Fields
(via Hacker News)
There's precious little info available about Mizirk "Boob Tracker," a computer vision project (based on a Kinekt?) that automatically detects boob-like objects and masks them with user-selectable bitmaps, following them as they move around the field of view. Mizirk's total delight in the performance of this little confection is what makes it.
(Thanks, Fipi Lele!)
Paul sez, "This past semester, three engineering grad students at the University of Toronto (myself and two others) created an Android app for a course project that allows for wireless and intuitive control of a robotic arm from an Android-powered smartphone. We're pretty proud of the results (the link is to a demo we put together) and have released the code open source."
Android Robotic Manipulator Demo
Thearn released a free/open program for detecting and monitoring your pulse using your webcam. The code is on github for you to download, play with and modify. If this stuff takes your fancy, be sure and read Eulerian Video Magnification for Revealing Subtle Changes in the World, an inspiring paper describing the techniques Thearn uses in his code:
This application uses openCV (http://opencv.org/) to find the location of the user's face, then isolate the forehead region. Data is collected from this location over time to estimate the user's heartbeat frequency. This is done by measuring average optical intensity in the forehead location, in the subimage's green channel alone. Physiological data can be estimated this way thanks to the optical absorbtion characteristics of oxygenated hemoglobin.
With good lighting and minimal noise due to motion, a stable heartbeat should be isolated in about 15 seconds. Other physiological waveforms, such as Mayer waves (http://en.wikipedia.org/wiki/Mayer_waves), should also be visible in the raw data stream.
Once the user's pulse signal has been isolated, temporal phase variation associated with the detected hearbeat frequency is also computed. This allows for the heartbeat frequency to be exaggerated in the post-process frame rendering; causing the highlighted forhead location to pulse in sync with the user's own heartbeat (in real time).
Support for pulse-detection on multiple simultaneous people in an camera's image stream is definitely possible, but at the moment only the information from one face is extracted for cardiac analysis
thearn / webcam-pulse-detector
(via O'Reilly Radar)
Dr. Tom Murphy VII gave a research paper called "The First Level of Super Mario Bros. is Easy with Lexicographic Orderings and Time Travel . . . after that it gets a little tricky," (PDF) (source code) at SIGBOVIK 2013, in which he sets out a computational method for solving classic NES games. He devised two libraries for this: learnfun (learning fuction) and playfun (playing function). In this accompanying video, he chronicles the steps and missteps he took getting to a pretty clever destination.
learnfun & playfun: A general technique for automating NES games
(via O'Reilly Radar)