Showing posts with label pushover. Show all posts
Showing posts with label pushover. Show all posts

Thursday, April 16, 2020

Decoding the Level Passwords in 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 29 bit column (10th from the right) has 2 ones, 2 zeros, 2 ones, and 2 zeros; we might expect this to continue indefinitely.
  • The 210 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 29 bit, starting at level 01, has a pattern of 2 ones, 2 zeros, and so on.
  • The 210 bit, starting at level 02, seems to have a pattern of 4 ones, 4 zeros, and so on.
  • The 211 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 212 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 213 bit first becomes one at level 16.

But something is also happening in the 21 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 21 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 21 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 21 bit flipped to zero. However, taking the level 02 password and flipping the 21 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 29) encoded the level number. So at this point, I predicted that the full pattern (if it continued indefinitely) would be as follows:

  • The 29 bit will start with one at level 01 and then change every 2 levels.
  • The 210 bit will become one at level 02 and then change every 4 levels.
  • The 211 bit will become one at level 04 and then change every 8 levels.
  • The 212 bit will become one at level 08 and then change every 16 levels.
  • The 213 bit will become one at level 16 and then change every 32 levels.
  • The 214 bit will become one at level 32 and then change every 64 levels.
  • The 215 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 215 bit does not get flipped to one at level 64. Any number with a one in the 215 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 29 through 214, but it's the 20 bit — not the 215 bit — which gets flipped to one at level 64. So we can revise the earlier prediction:

  • The 29 bit starts with one at level 01 and then changes every 2 levels.
  • The 210 bit becomes one at level 02 and then changes every 4 levels.
  • The 211 bit becomes one at level 04 and then changes every 8 levels.
  • The 212 bit becomes one at level 08 and then changes every 16 levels.
  • The 213 bit becomes one at level 16 and then changes every 32 levels.
  • The 214 bit becomes one at level 32 and then changes every 64 levels.
  • The 20 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 20 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 20 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 20 and 29 through 214 and are used to determine the level, then the nine bits remaining to represent bags are 21 through 28 and 215.

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 29, 210, 211, 212, 213, 214, and 20; additionally, bits 21, 22, 23, 24, 25, 26, 27, 28, and 215 are all flipped to one.

By starting with the level 100 password, individually setting the 21, 22, 23, 24, 25, 26, 27, 28, and 215 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 215 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 20 bit is one at level 64 and up.
  • The 21 bit is one after the first bag is collected (level ≥ 12).
  • The 22 bit is one after the second bag is collected (level ≥ 21).
  • The 23 bit is one after the third bag is collected (level ≥ 30).
  • The 24 bit is one after the fourth bag is collected (level ≥ 44).
  • The 25 bit is one after the fifth bag is collected (level ≥ 56).
  • The 26 bit is one after the sixth bag is collected (level ≥ 63).
  • The 27 bit is one after the seventh bag is collected (level ≥ 78).
  • The 28 bit is one after the eighth bag is collected (level ≥ 89).
  • The 29 bit starts with one at level 01 and then changes every 2 levels.
  • The 210 bit becomes one at level 02 and then changes every 4 levels.
  • The 211 bit becomes one at level 04 and then changes every 8 levels.
  • The 212 bit becomes one at level 08 and then changes every 16 levels.
  • The 213 bit becomes one at level 16 and then changes every 32 levels.
  • The 214 bit becomes one at level 32 and then changes every 64 levels.
  • The 215 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" (29, 210, 211, 212, 213, 214, and 20) — 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.