AoC 2015 Puzzle 4

2015 puzzle 04: The Ideal Stocking Stuffer

Full source available in the repository.

Part 1

Santa needs help mining some AdventCoins (very similar to bitcoins) to use as gifts for all the economically forward-thinking little girls and boys.

To do this, he needs to find MD5 hashes which, in hexadecimal, start with at least five zeroes. The input to the MD5 hash is some secret key (your puzzle input, given below) followed by a number in decimal. To mine AdventCoins, you must find Santa the lowest positive number (no leading zeroes: 1, 2, 3, …) that produces such a hash.

Solution

Initially you might think that in order to solve this puzzle a hash needs to be calculated and then converted to a hex string from which the first 5 characters can be compared to 0. This is in fact not necessary.

A MD5 hash can be calculated by using the MessageDigest class in Java. This will result in an array of the type byte. A byte can be anywhere between -128 and 127.

This small difference (why not -128 to 128?) might strike you as odd, but this is due to a mechanism called Two's complement, which is the way Java represents integers internally.

In order to turn the byte value into a hex string the value will be converted to an int value. If the int value is less then 16 the hex string will be a 0 followed by a number or A through F.

So if the int value is 0, then the hex string will be 00. If the int value is less then 16, the hex string will be a 0 followed by a number or A through F.

Converting a byte to int is a little messy though, due to the Two's Complement. Take a look at this example:

byte value = 0xfe; 
int result = value & 0xff;
  1. value is promoted to an int (ff ff ff fe), which carries the signed bit from the byte as an 0xff value.
  2. 0xff is an int literal (00 00 00 ff).
  3. The & is applied to yield the desired value for result as it masks out all the carried over 0xff values.

So all we need to do is to determine if the first 2 byte values are 0 and the 3rd is less then 15 by doing this conversion ourselves.

To get started a MessageDigest is needed with the MD5 algorithm.

@Override
public String part1(List<String> input) {
    try {
        MessageDigest md = MessageDigest.getInstance("MD5");

The puzzle calls for an input string that will be followed by a number. This number is a integer that is incremented until we find a suitable candidate.

int i = 0;
do {
    String text = input.get(0) + i;

The candidate is passed to the message digest and a hash is created. This results in an array of byte.

md.update(text.getBytes());
byte[] digest = md.digest();

The first 2 byte values need to be 0 in order to get a hex value of 00. The 3rd byte needs to be less then 15 (0x10), so a conversion to int (which is implicitly done through the &) followed by the mask (&) with 0xFF.

If this is the case, the value is returned of i to answer the puzzle.

if (digest[0] == 0 && digest[1] == 0 && (digest[2] & 0xFF) < 0x10) {
    return String.valueOf(i);
}

If not, i is incremented and the loop goes into another iteration.

            ++i;
        } while (true);

    } catch (NoSuchAlgorithmException ex) {
        ex.printStackTrace();
    }
    return null;
}

Puzzle, part 2

Now find one that starts with six zeroes.

Solution, part 2

This case is easy now that the logic is clear. Now all the 3 byte values need to be 0 in order to pass.

if (digest[0] == 0 && digest[1] == 0 && digest[2] == 0) {
    return String.valueOf(i);
}