# The Eagle Has Landed

The year was 1984. Apple Macintosh was just introduced, as well as our own shiny new computer called “Orao” (Eagle). It ended up being chosen as a standard primary school computer in Croatia from 1985 to 1991. For many of us, kids back then, this was one of the first opportunities to ever use a computer. Simple and rudimentary by today’s standards, Orao was brilliantly designed to avoid using specialized components - only simple TTL logic and off-the-shelf parts were used.

I wanted to write a cross-platform emulator, and after making one in Python, decided to go a step further and port it to Javascript. This is perhaps the most convenient way to use it, even though not all features were ported. To invoke BASIC, enter “BC” after booting. It can fetch one of the available tape images as .wav files via AJAX and load them. Loading takes time, computers were slow back then. :-)

For a slightly more complete version, check the Python version, but if you just want a quick dose of nostalgia - HERE it is!

TL;DR: enter BC at the * (star) prompt, press ENTER when asked about the memory size and try one of the following:

Double quotes = shift + 2. To erase something, use ctrl + H or left arrow.

# Ghost Ship

Lately I’ve been solving some problems on CheckiO, a really addictive programming site, and stumbled upon a very interesting golf mission. So, you might ask: “What are golf missions?!”. The idea is to solve the problem using as little code as theoretically possible. Your score is inversely related to code length and transforms a mildly challenging problem into a very addictive one.

One of the most interesting missions is called Ghost Detect. It might not seem special at first, but it gets tricky as solutions get shorter. The mission goal is to write the shortest possible code to recognize if three consecutive signals sent in binary are of the same length. 11000001100011 is a good signal while 111000100011 is a bad one. There is at least one zero between every group of ones. For each character used (less than 200) you earn 1 point. So, how do we do this?

#### 1. Use regex (77 characters, 123 points)

We find and group zeros at the beginning, followed by at least one zero, and then find exactly one occurence of the first group, then some more zeros etc. Not too complicated, but only 123 points. Can we do better?

#### 2. Use the sets, Luke (63 characters, 137 points)

Here we combine regex and sets to check how many different groups of repeating ones are present in binary representation.

#### 3. Ditch the regex (57 characters, 143 points)

This is about as far as a “Pythonic” road will take you. Split on zeros, convert to sets, remove empty set to avoid messing with the count and check if less than two.

### Now what?

To further shorten it, we need to try a different approach - binary. In binary, when you multiply by 2, you shift all the bits one position to the left. So, for example, 00010 multiplied by 2 becomes 00100. A valid signal, according to the task, is a number with three groups of ones equally long with zeros inbetween. This actually means it’s made of a number multiplied by a power of two, then the same number was multiplied by some other power of two and added, and then the same number was added again. For example, $111000111000111$ is actually $111_2 \cdot 2^{12} + 111_2 \cdot 2^{6} + 111_2$.

Therefore, we can write a generalized form for such a number n being equal to

The number should, then, be divisible by both k and r without reminder. First variant that comes to mind is to test if n divided by k equals r. But we have neither k nor r, and the only thing we have to work with is the number given to our function. We have to think of a way to get the number using bit manipulation.

So, now we have k with some bit tricks expressed like n AND n XOR n+1. To find r, we divide n by k and realize it’s basically the original number with sequences of ones reduced to a single 1. We can achieve this too with a little bit manipulation.

#### 4. Bit banging:

We are testing for this simple expression.

Down to 39 characters and 161 points. Can we do even better? Suprisingly, yes!

#### 5. Getting rid of k

If we test divisibility by k, it is easy to construct a number divisible by k which doesn’t satisfy the constraint - e.g. 110011110011. Therefore, we must test divisibility by the other factor, r. Since zeros between the ones are ensured by initial conditions, divisibility by r guarantees the required form.

Our solution is now only 33 characters long (function definition takes 19), and we scored 167 points. There is a trick to get 2 more points which I’m not going to disclose. Can you find it?

#### Can we go above 169?

I don’t think so, but please tell me if you think of a way! :) Hopefully you enjoyed reading about it as much as I’ve enjoyed solving it! If you have another, original solution to this problem feel free to email me and help my curiosity!

Cheers.

There was a very interesting presentation at the last 31C3 conference given by two very talented security researchers: Shahar Tal and Lior Oppenheim. The vulnerability they found targets many different routers from various manufacturers and was, apparently, patched 10 years ago (!) by the software company who made RomPager, the software in question. Let’s just say vendors are slow in deploying patches, leaving tens of millions of routers vulnerable to potential remote bricking, turning into botnets or who knows what else. It was named Misfortune Cookie for a good reason, but what does that have to do with math?

Apparently, there is a preallocated array in the webserver capable of storing 10 cookies, 40 bytes each. The cookie number is used as array index - converted to integer, multiplied by 40 and added to a memory address to read or write the correct location without ever checking boundaries.

You can pass an arbitrary number and address any memory location relative to a certain fixed point in memory. The only catch is that it gets multiplied by 40. What can you do if you need better precision to avoid overwriting something else near the memory location you are targeting?

This can be written in a form of ax ≡ y (mod m) and it’s called a Linear Congruence. Obviously, a is 40 since we move in steps of 40. We need to find such x that multiplied by 40 gives us a desired y modulo m we need to move in memory relative to the present location. M is $2^{32}$ (the size of a 32 bit number could fit 0-4294967295, anything more than that and it will overflow and start from zero again, just like a clock face starts from 1 when it reaches 12), making the equation 40 xy (mod $2^{32}$).

For this to have a solution, x needs to be divisible with the greatest common divisor of both 40 and $2^{32}$, which is 8 - that’s how many unique solutions we’ll get. Now we can say $z= \frac{y}{8}$, and reduce the expression to 5x ≡ z (mod 536870912). The way to solve it is to find the multiplicative inverse modulo m - a number we can multiply both sides with so that it gives 1 when multiplied by 5 in this modular algebra.

To get the other solutions, we need to keep adding the modulus value (536870912) to the result and reduce when needed. The referer is located at 0x2e48 to the LEFT of the cookie array. Since we cannot go backwards, we would like to add 0xffffd1b8 to overflow 32 bit number and end up at the desired address.

Now let’s try it on my router!

### Is there another way?

It’s not necessary to find a general solution, sometimes thinking differently can work too.

How many additional bits can multiplying by 40 add to a number’s binary representation? It’s between 32 (that’s $2^{5}$) and 64 (that’s $2^{6}$), so we have to assume 6 bits. The question becomes, which number multiplied by 40 and with 6 most significant bits discarded is equal to our input variable y? The router CPU might be stuck with 32 bits, but Python isn’t. Why not simply reconstruct these discarded bits by testing each case? Guess what the discarded value might have been and divide by 40 to check if the assumption was correct. For just 6 bits added, it isn’t terribly inefficient to check all possibilities and it goes to prove there are many ways to address a problem. Pun intended! :)

The 100111 is simply too much to store in a 32 bit memory unit so it gets discarded, and the rest we called y. We now need to do this in reverse, starting from y, guessing the discarded part and checking if division by 40 gives the starting value. If it does - that’s it.

So the next time you complain learning math is silly when studying for a CS degree, just remember you might actually need it!

# Tic-Tac-Toe in … MySQL

If you ever attended a boring lecture, you probably know this game by heart. Frequently scribbled on textbook margins and school desks, it’s insanely popular and fun to play. Talking to a friend about MySQL made me wonder if such a respectable, high performance database can be misused and tricked into being a gaming platfom. While it isn’t likely going to run Quake, maybe a simple game of Tic-Tac-Toe would be just right.

Why would anyone do this? Well, making floppy drives play The Imperial March isn’t very useful either, but it’s darn entertaining. MySQL is a powerful tool with strong scripting capabilities and Turing complete as well, so implementing this game in a single player mode is possible.

### Implementation

First, we need a board. To keep things simple, we’ll keep it as a 9 letter string - matrix element with position (1,1) will be the first element, then element (1,2) and so on .

After defining something to store and describe the board in, we declare AI is using ‘o’ and the player will be playing with ‘x’. Underscores are used to represent unclaimed fields. Since MySQL isn’t Perl or Python, we’ll have to improvise a little and create a function to check what’s placed on the board at a specific (row,column) position.

Now we need to think of a way to display the board to the player. There is no simple print function and we are trying to display a string as a table, so this is what I could think of.

We declare a temporary table, extract characters from our board-string and select it. This will print it (somewhat) nicely to the player.

### AI - making a respectable oponent

This is a good time to talk about the AI. Taking the classic approach isn’t something you do when coding for fun, so I decided to do something different. When doing something weird in a database engine, why not use it in your advantage? Basic combinatorics tells us each field can be either ‘o’, ‘x’ or empty, and there are 9 fields so that’s 39 = 19,683 possible board positions. Also, many positions are invalid - you can’t have all x’s because players take turns, you can’t play after you’ve lost etc. so the real number of valid board is much smaller (it’s 5477).

Game theory teaches us Tic-Tac-Toe can never actually be won if you pick optimal moves, so we’ll run it once to generate a tree of best computer moves given a certain position, store it permanently in the database, and use it to defeat the puny human.

Each optimal move for a certain position will be stored as a table row along with its predecessor’s id, so we can look it up and know where to move.

An example of a move stored in a database - this is a finished game which a computer (‘o’ player) won. Let’s implement a function for making a move.

### Constructing the optimal move tree

If you ever saw Wargames, you probably remember the scene where the kid saves the world by making the computer play Tic-Tac-Toe with itself. The same thing is done here (minus saving the world part). Computer plays both sides, but when impersonating a human it checks all moves, not just the best one, because a human might make a mistake. To determine the best move, a recursive minimax algorithm is used, checking long-term consequence of a move (‘move’ function) and choosing the one with a best outcome.

This python algorithm is ran only once; it recursively traverses the moves tree and inserts nodes as database rows. Our database could also be imported from external file, effectively eliminating any external dependencies, even if they are only a one-time thing. A single database row also contains state flags to determine if the game is over or not.

### Making it fancy

That’s all nice, it works, but one more thing… can we make it 3D, just for fun? Mysql can execute shell commands, but apparently you can’t pipe anything through shell scripts. Let’s use a trick - very often it produces long, long tables, and to facilitate looking at the data you can set a pager - something it will pipe your output through, like less or your favorite editor. Why not using that and piping it through … figlet! One apt-get install figlet later, finding a cool looking 3d font and a little sed to strip everything not important and we’re left with this.

Check out the video (HTML5 - webm, ogg or mp4):

Awesome!

# My Friend’s 2048 Version

Recently I tried implementing a cool game called 2048 in Python and make it as short as possible. Thinking I did a decent job, I challenged a friend to give it a go. Blown away how much shorter it turned out to be, all I can say is - kudos to Veky.

# A Simple 2048 Clone in Python

Every now and then a viral game shows up. It is difficult to name a particular quality which makes a game popular, but most people would probably describe it as addictive. 2048 is just that, despite its remarkable simplicity.

Soon, I started wondering how many lines of code would it take to write it and what are the bare essentials of the game, and tried writing my own version. To keep things short, movements are implemented in a single direction only. For the rest of the moves to work you have to rotate the matrix a few times first, perform the move and rotate it some more to return to your starting point. Not ideal, but simple it is. Game over detect simply checks if movement in any direction affects the board.

Tile creation needed to be short, so a list of zero-valued matrix elements’ coordinates was made, one picked out at random and a 2 or 4 placed there. To color the backgrounds differently, its background color is derived from its value. A dictionary could have been used as well, but it would be slightly longer.

That’s pretty much it - no score, no menu, no restart, no keypress error handling… just the bare essentials, but - it works. And it’s kind of fun, too!

…and it looks like this: