John Mercier

So what good is knowing all of the card combinations that have a solution of 24 without actually doing something with them. Well maybe this will eventually become a game. So I need to store this data so I can use it in the future. From the perspective of making a game it would be nice to pick a random combination (from 1 to 2133) and get the cards for that number. My first thought was to print these to a random access file with 4 integers per record but it kind of seems like a waste of space with numbers from 1 to 9 doesn't it? I mean a value of 9 takes 4 bits to represent while an integer is 32 bits. 4 cards will only take 16 bits rather than 128. Even if you use bytes for the cards it will take 32 bits, twice as much storage space. Here is a table:

There is a total savings of 238896 bit (233kb).

So this brings me to the point of this post, how to compress the 4 cards. Since I am dealing with 4 bit numbers and java does not have a 4 bit type I'm going to have to do some bit twiddling. There are two methods one called encode4Bit and the other called decode4Bit. encode4Bit takes 4 integers and encodes them into one short. decode4Bit takes a short and returns the 4 original integers.

Keep in mind that each integer can only have a value between 0 and 15 for this to work. So some validation code would be ideal (remember the illegal argument exception in java).

Encoding the integers is the easy part. Take each integer and use “or” to add it to a short. At each iteration move the bits left by 4. Here is the code:

    public static short encode4Bit(int... c) {
        short code = 0;
        if (c.length <= 4) {
            for (int i : c) {
                if (i < 0 || i > 15) {
                    throw new IllegalArgumentException("encode9Cards only accepts cards from 0 to 15");
                }
            }
        } else {
            throw new IllegalArgumentException("encode9Cards only accepts up to 4 integers");
        }
        Arrays.sort(c);
        System.out.println(Arrays.toString(c));
        int move = 0;
        for (int i : c) {
            i = i << move;
            move += 4;
            code = (short) (code | i);

        }

One thing you may have noticed is I added a sort before encoding the integers. This is so I can be absolutely sure I have no duplicate sets of 4 cards down the road. If any of the encoded numbers are the same then I know there are duplicates. I have a feeling that when the ordering of numbers does not matter there will be duplicate combinations. An example would be when all the operations are the same such as 1*1*3*8 and 9+9+4+2. So before saving these 16bit numbers I can make sure each one is unique.

Decoding the short into 4 integers gave me some trouble. For some reason right shifting with shorts does not work as expected. Here is some code as an example:

        System.out.println("number = " + number);
        number = (short) (number << 12);
        System.out.println("number = " + number);
        number = (short) (number >>> 12);
        System.out.println("number = " + number);
        number = (short) (number << 12);
        System.out.println("number = " + number);
        number = (short) (number >>> 12);
        System.out.println("number = " + number);

        int number2 = 15;
        System.out.println("number = " + number2);
        number2 = number2 << 12;
        System.out.println("number = " + number2);
        number2 = number2 >>> 12;
        System.out.println("number = " + number2);
        number2 = number2 << 12;
        System.out.println("number = " + number2);
        number2 = number2 >>> 12;
        System.out.println("number = " + number2);

The output is:

number = 15

number = -4096

number = -1

number = -4096

number = -1 <--- should be 15!

number = 15

number = 61440

number = 15

number = 61440

number = 15

So as you can see using shorts does not work. Right now I'm not sure why this is happening. I have a feeling it has something to do with everything with less bits than an integer always being promoted to a short. When you right shift the 0s are put in front of an integer instead of a short and are lost once the cast is made.

Here is the decode method:

    public static int[] decode4Bit(short c) {
        int cards[] = {0, 0, 0, 0};
        int card = 0;
        for (int j = 0; j <= 3; j++) {
            card = c;
            card = card >>> (4 * j + 16);
            card = card << (12 + 16);
            card = card >>> (12 + 16);
            cards[j] = card;
        }
        return cards;
    }

I had to add 16 to the shifts so the card is still treated like a short.

Overall this works the way it should. I have also tested it with all of the combinations. Now all I have to do is write the file... and the game.