Perl, 75 + 18 = 93 bytes
This program contains nonprintable characters, so here's a hexdump:
00000000: 245f 3d31 3b73 7c30 2a28 2e29 7c24 263d $_=1;s|0*(.)|$&=
00000010: 7e79 3d20 2d7e 3d21 2d7e 203d 722e 3178 ~y= -~=!-~ =r.1x
00000020: 2124 317c 6520 7768 696c 6520 6d64 3528 !$1|e while md5(
00000030: 245f 296e 6527 92a7 c911 6fa5 2eb8 3cf4 $_)ne'....o...<.
00000040: c291 9599 c24a 273b 7361 79 .....J';say
This program requires the command line argument
-MDigest::MD5=md5 (an 18 byte penalty, 17 for the argument and 1 for the space separating it from the other arguments).
Here's the program with whitespace and comments added and the binary string replaced with
$_ = 1; # $_ is the string to check; start at '1'
s|0*(.)| # replace a string of leading 0s plus 1 character
$& =~ y= -~=!-~ =r # by rotating 1 printable ASCII character forward
. 1 x !$1 # and appending a 1 if the replaced section ends in 0
|e # (the previous two lines are a Perl expression)
while md5($_) ne '…'; # while it has the wrong md5
say # print out the value of $_ we found
The basic trick here is that although we want to check from shortest to longest, there's no particular reason to check the characters in ASCIIbetical order. As a result, we check in the order from
0. To do this, we repeatedly increment the first character after the leading 0s, and reset the leading 0s back to leading 1s (which we can do by incrementing every character up to and including the character after the leading 0s). If the string consists entirely of 0s, we need to append a new 1 to the end; we do this via checking to see if the string consists entirely of 0s via seeing if the last matched character in the regex is
0 (as the
0* match is greedy, this will only happen if there are no non-
0 characters in the string).
0 are picked as the first and last character in the range is that a) they don't need quoting (the string
"1" can be written as
1 because Perl doesn't really distinguish between strings and integers), and b) that Perl has a very short way (
!) of checking a single-character string for equality with
0 (Perl has three falsey values:
"0", with all other values being truthy).
Note that we have no reason to translate the MD5 hash in question into hexadecimal; it's specified in the question, and so we can pack it into binary ourselves and just compare the binary representations directly. Perl's builtin for producing an md5 hash in binary has a shorter name than the hexadecimal equivalent, and the binary representation takes up half the space in the source, so this is a win in two different ways.
I tested the program with the hash of the string
abc inserted into the source code rather than the hash of the string
code-golf, and it found the correct answer in 1.3 seconds. (It's unlikely to be able to reverse the hash of
code-golf in a reasonable length of time, due to the need to check a substantial subset of the printable ASCII range.)