Advent Of Code 2016 day 14 part two

[Piet Souris]

It is about Advent of Code 2016, day 14 part two. I cannot get that part solved, and I cannot get the example given. Here is a link to that exercise:  link to aoc2016_14_2

In the example they say that 10 is the first index, and that is what I get as well. However, they state that 22551 is the index of the 64th key, its hash containing "fff" and the hash of "abc22859" has "fffff".

My code however says that 22551 is not a key. The hash I get from index 22551 is "2df6e9378c3c53abed6d3508b6285fff", indeed containing "fff", but the hash of "abc22859" is "d489b5d5080a10bed5f4924dfcb1ab4f", so it does not contain "fffff". I looked on internet, but found no clear explanations. Some had the same problem as I, some had no problems at all, and some pointed out that you had to watch the order of the keys found (but I think they were using a Set to store the keys, and I am using an ArrayList).

Has anyone made this exercise, or can anyone shed some light into my darkness? This is the code I use:

private static int day = 14;
private static boolean test = true;

private static String salt = test ? "abc" : "ahsbgdzn";
private static Map<Integer, String> hashes;
private static Pattern pattern = Pattern.compile("(.)\\1\\1");

public static void main(String... args) {
    hashes = IntStream.iterate(0, i -> i <= 100_000, i -> i + 1)
        .boxed().collect(toMap(i -> i, i -> getMD5(salt + i)));
    var index = 22551;
    var temp = getMD5(salt + index);
    for (int i = 1; i <= 2016; i++) temp = getMD5(temp);
    System.out.println(temp);
    var m = pattern.matcher(temp);
    if (!m.find()) System.out.println("niks gevonden");
    else {
        var s3 = m.group();
        var s5 = s3.substring(0, 1).repeat(5);
        var result = String.format("gevonden: %s, te zoeken: %s, is sleutel: %b%n", s3, s5, isKey(s5, index));
        System.out.println(result);
        System.out.println(hashes.get(22859));
    }
}

private static boolean isKey(String toFind, int index) {
    for (int i = 1; i <= 1000; i++) {
        if (hashes.get(index + i).contains(toFind)) return true;
    }
    return false;
}

private static String getMD5(String input) {
    // code I got from GeeksForGeeks
    try {
        // Static getInstance method is called with hashing MD5
        MessageDigest md = MessageDigest.getInstance("MD5");

        // digest() method is called to calculate message digest
        // of an input digest() return array of byte
        byte[] messageDigest = md.digest(input.getBytes());

        // Convert byte array into signum representation
        BigInteger no = new BigInteger(1, messageDigest);

        // Convert message digest into hex value
        String hashtext = no.toString(16);
        while (hashtext.length() < 32) {
            hashtext = "0" + hashtext;
        }
        return hashtext;
    }

    // For specifying wrong message digest algorithms
    catch (NoSuchAlgorithmException e) {
        throw new RuntimeException(e);
    }
}

and this is the output:

2df6e9378c3c53abed6d3508b6285fff
gevonden: fff, te zoeken: fffff, is sleutel: false

d489b5d5080a10bed5f4924dfcb1ab4f
BUILD SUCCESSFUL (total time: 1 second)

[Tim Cooke]

Ok I'm hooked. I haven't done this one yet but I've made a start and I'll get back to you if I figure something out.

[Tim Cooke]

I have arrived at the puzzle you are working on Piet. While I am having compute time problems, I think I can see where you're going wrong.

You are finding the "stretched" hash of the original key "abc22551" with a triple character sequence correctly, but when you are checking the next 1000 hashes for a five character sequence you are not checking stretched hashes, only normal one time md5 hashes.

"abc22859" Normal hash: d489b5d5080a10bed5f4924dfcb1ab4f
"abc22859" Stretch hash: 2e559978fffff9ac9c9012eb764c6391

[Tim Cooke]

I sorted out my time problems with some function memoization.

I did it in Python and was using @functools.cache for memoization which is an unbounded cache but it failed ("Killed" was the message) due to what I can only assume is momory space problems. I put some bounds on the cache with @functools.lru_cache(1000) and all was good. It took about 45 seconds to run which is good enough for me today.

[Piet Souris]

Thanks Tim!

I interpreted this part wrong: "The rest of the process remains the same (...)"

I put 100.00 normal hashes and 50.000 stretched hashes in a HashMap upfront, took more than a minute. Isn't there some clever theorem about repeated hashes?

[Tim Cooke]

You could replace the up front hash cache generation by using getOrDefault followed by a putIfAbsent. For example:

String salt = "abc";
int index = 22859;
String key = hashes.getOrDefault(index, getMD5(salt + index));
hashes.putIfAbsent(index, key);

You might of course run into memory space problems as you have just rolled your own unbounded cache, which is generally not a good idea.

It's fun to play though.

[Piet Souris]

Good idea! I'll keep that in mind.