Out of Lives: pushover

Pushover is a puzzle game about an ant pushing over dominos. I played it when I was a kid, and more recently I got a Steam copy of it from a cheap bundle of old games. I didn't really start playing this Steam copy until this week, at which point I remembered that, like many games of the time, Pushover has no save system. Each time the player reaches a new level, the game provides a password which can be used to return to that point.

As I played the first few levels, I noticed something interesting. The first four level passwords were as follows:

Level Password 01 00512 02 01536 03 01024 04 03072

Two of the passwords being powers of two immediately caught my attention. If we convert each password to binary (using sixteen bits just because bits usually come in groups of eight), we get this:

Level Password Binary 01 00512 0000001000000000 02 01536 0000011000000000 03 01024 0000010000000000 04 03072 0000110000000000

Following this pattern, I expected the password for level 05 to be 0000100000000000, or 02048, but using this password brought me to level 07 instead. Going back to level 04, I played up to level 08 and found that, while there was still clearly some kind of pattern, it was a bit more complicated than I had thought. Converting the first eight level passwords to binary, we have:

Level Password Binary 01 00512 0000001000000000 02 01536 0000011000000000 03 01024 0000010000000000 04 03072 0000110000000000 05 03584 0000111000000000 06 02560 0000101000000000 07 02048 0000100000000000 08 06144 0001100000000000

At this point, we can already start to see what's going on, if we look at the binary in columns. There seems to be a pattern emerging:

The 2⁹ bit column (10th from the right) has 2 ones, 2 zeros, 2 ones, and 2 zeros; we might expect this to continue indefinitely.
The 2¹⁰ bit column (11th from the right), after a single zero, has 4 ones in a row, followed by some zeros; we might expect this column to have a pattern of 4 ones, 4 zeros, and so on, albeit offset by a single zero at the beginning.

However, I didn't really see it until I had played through another eight levels. Converting the first sixteen level passwords to binary, we have:

Level Password Binary 01 00512 0000001000000000 02 01536 0000011000000000 03 01024 0000010000000000 04 03072 0000110000000000 05 03584 0000111000000000 06 02560 0000101000000000 07 02048 0000100000000000 08 06144 0001100000000000 09 06656 0001101000000000 10 07680 0001111000000000 11 07168 0001110000000000 12 05122 0001010000000010 13 05634 0001011000000010 14 04610 0001001000000010 15 04098 0001000000000010 16 12290 0011000000000010

Focusing only on the higher-order (leftmost) bits, we can now clearly see that:

The 2⁹ bit, starting at level 01, has a pattern of 2 ones, 2 zeros, and so on.
The 2¹⁰ bit, starting at level 02, seems to have a pattern of 4 ones, 4 zeros, and so on.
The 2¹¹ bit, starting at level 04, has 8 ones in a row, and has presumably started a pattern of 8 ones, 8 zeros, and so on.
The 2¹² bit, starting at level 08, is all ones all the way through level 16, and may have started a pattern of 16 ones, 16 zeros, and so on.
The 2¹³ bit first becomes one at level 16.

But something is also happening in the 2¹ bit (second from the right), where a one suddenly appears starting at level 12. This doesn't seem related to the rest of the pattern, and I think I know why.

It was after completing level 11 that the little ant protagonist found... a bag of Quavers...? (Did I mention that Pushover was sponsored by a snack food company? I've never had Quavers; apparently they're British.) On the menu screen which appears between levels, I could see after completing level 11 that a little sprite representing a bag of Quavers had been added to the bottom of the screen where there appear to be nine spaces available. So it's probably safe to assume that nine virtual bags of Quavers are pointlessly awarded throughout the game.

The fact that the 2¹ bit changed after level 11 suggests that some of the lower-order bits are used for tracking the bags collected, independently of the higher-order bits which indicate the level number. As an experiment, I took the password for level 12 and flipped the 2¹ bit to zero, resulting in 0001010000000000 or 05120. Sure enough, entering the password 05120 took me to level 12, and upon completing the level, the inter-level menu screen did not show the bag that was there when I had beaten levels 11 through 15 before. Moreover, the password it gave me for level 13 this time was 05632, which is the previously obtained level 13 password with the 2¹ bit flipped to zero. However, taking the level 02 password and flipping the 2¹ bit to one did not result in a valid password. So I cannot cheat my way into already having a bag prior to level 12, but it seems I can enter levels 12 or later without one.

If some bits are only for tracking bags collected, and if any level can be entered without any bags, then we should be able to get a complete set of level passwords just by predicting the pattern of the bits indicating level number. The passwords of levels 01 through 16 suggested that only the higher-order bits (starting with 2⁹) encoded the level number. So at this point, I predicted that the full pattern (if it continued indefinitely) would be as follows:

The 2⁹ bit will start with one at level 01 and then change every 2 levels.
The 2¹⁰ bit will become one at level 02 and then change every 4 levels.
The 2¹¹ bit will become one at level 04 and then change every 8 levels.
The 2¹² bit will become one at level 08 and then change every 16 levels.
The 2¹³ bit will become one at level 16 and then change every 32 levels.
The 2¹⁴ bit will become one at level 32 and then change every 64 levels.
The 2¹⁵ bit will become one at level 64 and then change every 128 levels.

This algorithm does predicts the values of the seven highest-order bits for the first sixteen level passwords. Unfortunately, I realized later that it's not quite correct. While looking around in the game's files for goodies, I found that the Steam version of Pushover comes with a file called PUSHCODE.TXT — which, bizarrely, contains most but not all level passwords, and seems to have been written not by the developer or publisher but by someone from a demogroup known as Tristar & Red Sector Incorporated. The file begins:

TRISTAR & RED SECTOR PRESENTS PUSHOVER (LEVELCODES) LEVEL 1 00512 LEVEL 2 01536 LEVEL 3 01024 ...

It continues all the way through level 67:

... LEVEL 65 17023 LEVEL 66 18047 LEVEL 67 17535 NOTE: THERE ARE MISSING A FEW CODES!!!! TIME BANDIT/TRSI

Pushover apparently has 100 levels, so I guess the player who wrote this file gave up about two-thirds of the way through the game. However, they got far enough to show me that the 2¹⁵ bit does not get flipped to one at level 64. Any number with a one in the 2¹⁵ place would be at least 32768, and none of the passwords in PUSHCODE.TXT are that high!

So I wrote a few lines of Python to convert all the passwords in PUSHCODE.TXT to binary. The results are as follows:

Level Password Binary 01 00512 0000001000000000 02 01536 0000011000000000 03 01024 0000010000000000 04 03072 0000110000000000 05 03584 0000111000000000 06 02560 0000101000000000 07 02048 0000100000000000 08 06144 0001100000000000 09 06656 0001101000000000 10 07680 0001111000000000 11 07168 0001110000000000 12 05122 0001010000000010 13 05634 0001011000000010 14 04610 0001001000000010 15 04098 0001000000000010 16 12290 0011000000000010 17 12802 0011001000000010 18 13826 0011011000000010 19 13314 0011010000000010 20 15362 0011110000000010 21 15878 0011111000000110 22 14854 0011101000000110 23 14342 0011100000000110 24 10246 0010100000000110 25 10758 0010101000000110 26 11782 0010111000000110 27 11270 0010110000000110 28 09222 0010010000000110 29 09734 0010011000000110 30 08718 0010001000001110 31 08206 0010000000001110 32 24590 0110000000001110 33 25102 0110001000001110 34 26126 0110011000001110 35 25614 0110010000001110 36 27662 0110110000001110 37 28174 0110111000001110 38 27150 0110101000001110 39 26638 0110100000001110 40 30734 0111100000001110 41 31246 0111101000001110 42 32270 0111111000001110 43 31758 0111110000001110 44 29726 0111010000011110 45 30238 0111011000011110 46 29214 0111001000011110 47 28702 0111000000011110 48 20510 0101000000011110 49 21022 0101001000011110 50 22046 0101011000011110 51 21534 0101010000011110 52 23582 0101110000011110 53 24094 0101111000011110 54 23070 0101101000011110 55 22558 0101100000011110 56 18494 0100100000111110 57 19006 0100101000111110 58 20030 0100111000111110 59 19518 0100110000111110 60 17470 0100010000111110 61 17982 0100011000111110 62 16958 0100001000111110 63 16510 0100000001111110 64 16511 0100000001111111 65 17023 0100001001111111 66 18047 0100011001111111 67 17535 0100010001111111

This is all consistent with my predictions about bits 2⁹ through 2¹⁴, but it's the 2⁰ bit — not the 2¹⁵ bit — which gets flipped to one at level 64. So we can revise the earlier prediction:

The 2⁹ bit starts with one at level 01 and then changes every 2 levels.
The 2¹⁰ bit becomes one at level 02 and then changes every 4 levels.
The 2¹¹ bit becomes one at level 04 and then changes every 8 levels.
The 2¹² bit becomes one at level 08 and then changes every 16 levels.
The 2¹³ bit becomes one at level 16 and then changes every 32 levels.
The 2¹⁴ bit becomes one at level 32 and then changes every 64 levels.
The 2⁰ bit becomes one at level 64 and then changes every 128 levels.

This isn't quite as elegant as what I had initially predicted, because the "level bits" are no longer contiguous, but it appears to be correct. The last rule is already unlike the others anyway, in that we would never actually see the 2⁰ bit change from one back to zero after 128 levels because there are only 100 levels in the game. I predicted that bit to flip at a frequency of once per 128 levels to continue the power-of-two pattern. So that last rule could just be written as:

The 2⁰ bit is one at level 64 and up.

The passwords in PUSHCODE.TXT also give us a hint about how bags are tracked. It seems that each one has its own dedicated bit. If we enter the level 67 password above (17535 or 0100010001111111) and then quit back to the menu screen, we see that we have the first six bags. But if we flip a few bits to get 0100010001010101, and enter the corresponding decimal password 17493, quitting back to the menu shows that we have only the second, fourth, and sixth bags.

If there are nine bags, and if each bag has its own bit, then we need nine bits to represent them all. Meanwhile, if bits 2⁰ and 2⁹ through 2¹⁴ and are used to determine the level, then the nine bits remaining to represent bags are 2¹ through 2⁸ and 2¹⁵.

From another source (the description on this YouTube video), I've found that level 100 is actually a bonus level, and that its password is 44543 (or, in binary, 1010110111111111). This is is still consistent with the above rules regarding bits 2⁹, 2¹⁰, 2¹¹, 2¹², 2¹³, 2¹⁴, and 2⁰; additionally, bits 2¹, 2², 2³, 2⁴, 2⁵, 2⁶, 2⁷, 2⁸, and 2¹⁵ are all flipped to one.

By starting with the level 100 password, individually setting the 2¹, 2², 2³, 2⁴, 2⁵, 2⁶, 2⁷, 2⁸, and 2¹⁵ bits back to zero, entering the resulting passwords to start level 100, and then quitting to the menu to see which bags are shown, I've confirmed that each of these bits corresponds to a particular bag. Interestingly, setting 2¹⁵ to zero in particular, resulting in the password 11775, has the effect of making level 100 easier by revealing the special domino types which are normally hidden on this bonus level. More importantly, though, I'm pretty sure we have now fully decoded the game's level passwords.

The 2⁰ bit is one at level 64 and up.
The 2¹ bit is one after the first bag is collected (level ≥ 12).
The 2² bit is one after the second bag is collected (level ≥ 21).
The 2³ bit is one after the third bag is collected (level ≥ 30).
The 2⁴ bit is one after the fourth bag is collected (level ≥ 44).
The 2⁵ bit is one after the fifth bag is collected (level ≥ 56).
The 2⁶ bit is one after the sixth bag is collected (level ≥ 63).
The 2⁷ bit is one after the seventh bag is collected (level ≥ 78).
The 2⁸ bit is one after the eighth bag is collected (level ≥ 89).
The 2⁹ bit starts with one at level 01 and then changes every 2 levels.
The 2¹⁰ bit becomes one at level 02 and then changes every 4 levels.
The 2¹¹ bit becomes one at level 04 and then changes every 8 levels.
The 2¹² bit becomes one at level 08 and then changes every 16 levels.
The 2¹³ bit becomes one at level 16 and then changes every 32 levels.
The 2¹⁴ bit becomes one at level 32 and then changes every 64 levels.
The 2¹⁵ bit is one after the ninth bag is collected (level = 100).

The above assumes that bags are awarded for completion of levels 11, 20, 29, 43, 55, 62, 77, and 88, based on the binary representations of the first 67 passwords passwords found in PUSHCODE.TXT and of the remaining passwords found on this page. I don't feel inclined to play through the entire game to confirm it myself before publishing this post. Given that we can enter any level just by setting the "level bits" (2⁹, 2¹⁰, 2¹¹, 2¹², 2¹³, 2¹⁴, and 2⁰) — without turning on any of the "bag bits" — there's actually more than enough information here to allow me to amuse myself by writing a little Python script that gives me a valid password for any level I want to play:

import sys def get_level_bit(frequency, level): offset = frequency // 2 return (level + offset) // frequency % 2 def generate_password(level): bits = 0 for index in reversed(range(16)): bits = bits << 1 if 9 <= index <= 14: bits += get_level_bit(2 ** (index - 8), level) if index == 0: bits += get_level_bit(128, level) return bits if __name__ == "__main__": print(generate_password(int(sys.argv[1])))

Is this really useful when I could just look up the passwords on the internet? Not really. But reverse engineering the game's passwords was more fun.

Out of Lives

Thursday, April 16, 2020

Decoding the Level Passwords in Pushover