[Back to index]

Puzzle: https://adventofcode.com/2015/day/4

My solution: https://codeberg.org/adfoucart/aocode15/src/branch/main/src/day4.c

We start with a little bit more tidying up: my makefile was really bugging me. I was basically just using it as a shortcut for gcc commands, but everything was “hardcoded”. After a bit of searching and reading through some tutorials, I get to this:

CFILES := $(wildcard ./src/*.c)
OFILES := $(patsubst ./src/%.c,./bin/%.o,$(CFILES))
MDFILES := $(wildcard ./notes/*.md)
HTMLFILES := $(patsubst ./notes/%.md,./pub/%.html,$(MDFILES))

day%: ./bin/day%.exe
    $<

./bin/day1.exe: ./bin/day1.o ./bin/futils.o
    gcc $^ -o $@

./bin/day2.exe: ./bin/day2.o ./bin/futils.o ./bin/parser.o 
    gcc $^ -o $@

./bin/day3.exe: ./bin/day3.o ./bin/futils.o ./bin/coords.o 
    gcc $^ -o $@

./bin/%.o: ./src/%.c
    gcc -c $< -o $@

html: $(HTMLFILES)

./pub/%.html: ./notes/%.md
    pandoc -t html -s -o $@ $<

test: test_parser test_pointers test_coords
    
test%: ./bin/test%.exe
    $<

./bin/test_parser.exe: ./bin/test_parser.o ./bin/parser.o
    gcc $^ -o $@

./bin/test_pointers.exe: ./bin/test_pointers.o
    gcc $^ -o $@

./bin/test_coords.exe: ./bin/test_coords.o ./bin/coords.o
    gcc $^ -o $@

I still have to do a bit of manual linking, but it allows me at least to do:

make day2

And have it run, and compile if necessary, everything for day2. Same for any other day, and make test to run all test files. And make html transforms my markdown notes into these beautiful web pages through the magic of pandoc. Much neater. Anyway, on to day 4 now.

A puzzling puzzle

This is a weird one, by my expectations from the two years of Advent of Code that I’ve done.

We have as an input a short string (8 characters). We need to find the smallest positive number to append to it so that the resulting MD5 hash has five leading zeros, in a bitcoin-mining fashion. I don’t see anything else to do than brute force. It seems to me that the whole point of the hashing function is that it’s not possible to guess what string will produce a particular output. And I don’t particularly want to reimplement MD5 myself.

To start, I took Bryce Wilson’s implementation and tested a bunch of numbers:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include "md5.h"

char* INPUT_STR = "input hidden";

int test_md5(int number){
    char buffer[100];
    sprintf(buffer, "%s%d", INPUT_STR, number);
    
    uint8_t result[16];
    md5String(buffer, result);
    for (int i=0; i < 5; i++){
        if (result[i] != 0)
            return i;
    }
    return 5;
}

int main(){
    int max = 0;
    for (int i=1; i < 10000000; i++){
        int c = test_md5(i);
        if (c > max){
            max = c;
            printf("New max: %d (%d)\n", max, i);
        }
        if(c == 5)
            printf("Found: %d\n", i);
    }
    printf("End.\n");
    exit(0);
}

In my new makefile, I have to add:

./bin/day4.exe: ./bin/day4.o ./bin/md5.o
    gcc $^ -o $@

And make day4 works as expected. I like that.

As for the puzzle, best I get after ten million numbers tested is three leading zeros. Let’s just try 100 million numbers just to see if we get something? No, still maximum three zeros.

Possibilities:

1. There’s a non brute-force way that I’m not seeing.
2. The MD5 implementation I used is suboptimal.
3. The MD5 implementation I used is wrong.
4. My code is wrong somewhere and I found the right one but I’m not detecting it.

Let’s test c) and d) first. I hope it’s d), as at least it means I may learn something from the experience.

Making a test:

void test_md5_sample(){
    char buffer[100];
    sprintf(buffer, "%s%d", INPUT_STR, 1234);
    
    printf("%s\n", buffer);
    
    uint8_t result[16];
    md5String(buffer, result);
    
    for (int i=0; i < 16; i++){
        printf("%d,", result[i]);
    }
}

And checking the results against the MD5 that md5hashgenerator gives me.

Everything is correct, except that I realize a mistake which may mean d): I am checking the uint8_t values, but in the hex string each uint8_t is encoded by two hexadecimal numbers. So if I want five leading zeros in the hex string, I actually need two 0s and then a number <16. So I have already passed through the right number, probably.

Let’s modify the test_md5 function, and have it return a boolean:

bool test_md5(int number){
    char buffer[100];
    sprintf(buffer, "%s%d", INPUT_STR, number);
    
    uint8_t result[16];
    md5String(buffer, result);
    for (int i=0; i < 2; i++){
        if (result[i] != 0)
            return false;
    }
    if (result[2] >= 16)
        return false;
    return true;
}

And the main:

int main(){
    int max = 0;
    for (int i=1; i < 100000000; i++){
        if(test_md5(i)){
            printf("Found: %d\n", i);
            break;
        }
    }
    printf("End.\n");
    exit(0);
}

And we’ve got our star, for the value 282749 for me.

Second part, more of the same

Now we need six leading zeros in the hex string, so three zeros in the uint8_t representation.

So we have:

bool test_md5_part_two(int number){
    char buffer[100];
    sprintf(buffer, "%s%d", INPUT_STR, number);
    
    uint8_t result[16];
    md5String(buffer, result);
    for (int i=0; i < 3; i++){
        if (result[i] != 0)
            return false;
    }
    return true;
}

And it takes a little bit more time, but it works.

As pointless as actual bitcoin mining.

By far my least favourite advent of code puzzle so far. Not much to learn, or do. Let’s move on.