How to get a job with 70 lines of code

After my recent post How to get a job with 250 lines of code there is a new challenge available, cf. followthewhiterabbit:

challengemd5

They kindly provide a list of words containing the building blocks of the solution as well as an “anagram hint”. One can use this hint at the very beginning by preprocessing the file with some grep acrobatics:

dos2unix wordlist
grep -Ei '^[poultry outwits ants]+$' wordlist | grep -Eiv '*[y].*[y]' | grep -Eiv '*[p].*[p]'  | grep -Eiv '*[o].*[o].*[o]' |  grep -Eiv '*[l].*[l]' |  grep -Eiv '*[u].*[u].*[u]' | grep -Eiv '*[r].*[r]' | grep -Eiv '*[w].*[w]' | grep -Eiv '*[i].*[i]' | grep -Eiv '*[a].*[a]'  | grep -Eiv '*[n].*[n]' | grep -Eiv '*[s].*[s].*[s]' | sort --unique > wordlist_clean

This step is important since it reduces the number of candidate words to 1659 (compared to 99175 in its untouched form).

Without further ado, using the reduced file let me spoil the solution written in go:

package main

import (
  "crypto/md5"
  "errors"
  "fmt"
  "io/ioutil"
  "log"
  "strings"
)

const (
  targetMd5        = "4624d200580677270a54ccff86b9610e"
  anagramLetters   = "poultry outwits ants"
  wordlistFilename = "wordlist_clean"
)

func main() {
  log.Printf("Target md5 is                    : %s", targetMd5)
  log.Printf("Anagram letters are              : %s", anagramLetters)
  content, err := ioutil.ReadFile(wordlistFilename)
  if err != nil {
    log.Fatalln("Cannot read wordlist "+wordlistFilename, err)
  }
  lines := strings.Split(string(content), "\n")
  numWords := uint64(len(lines))
  log.Printf("Number of words read             : %d", numWords)
  log.Printf("Number of permutations to process: %d", numWords*numWords*numWords)

  phrase, err := findMd5(lines, targetMd5)
  if err != nil {
    log.Fatalln("No matching md5 found!", err)
  }
  log.Printf("Found correct phrase: '%s'", phrase)
}

func findMd5(lines []string, expectedMd5 string) (string, error) {
  for c1, word1 := range lines {
    for _, word2 := range lines {
      for _, word3 := range lines {
        phrase := strings.Join([]string{word1, word2, word3}, " ")
        if isAnagram(anagramLetters, phrase) {
          phraseAsBytes := []byte(phrase)
          md5 := fmt.Sprintf("%x", md5.Sum(phraseAsBytes))
          if md5 == expectedMd5 {
            fmt.Println(" ...done")
            return phrase, nil
          }
        }
      }
    }
    pctage := fmt.Sprintf("%.3f", 100.0*float64(c1)/float64(len(lines))) + "%"
    fmt.Printf("\r%s of permutations processed", pctage)
  }
  fmt.Println(" ...done")
  return "", errors.New("No phrase found for md5 " + expectedMd5)
}

func isAnagram(one string, another string) bool {
  if len(one) != len(another) {
    return false
  }
  for _, character := range one {
    if strings.Count(one, string(character)) != strings.Count(another, string(character)) {
      return false
    }
  }
  return true
}

The output of the program will look something like

2016/10/17 22:24:28 Target md5 is                    : 4624d200580677270a54ccff86b9610e
2016/10/17 22:24:28 Anagram letters are              : poultry outwits ants
2016/10/17 22:24:28 Number of words read             : 1660
2016/10/17 22:24:28 Number of permutations to process: 4574296000
27.470% of permutations processed ...done
2016/10/17 22:26:55 Found correct phrase: 'pastils turnout towy'
Advertisements

About goobypl5

pizza baker, autodidact, particle physicist
This entry was posted in Hash functions, Programming and tagged , , , , , . Bookmark the permalink.

3 Responses to How to get a job with 70 lines of code

  1. B. Doyle says:

    This is cool. I think I’m going to attempt it in Scala, because I’m trying to learn that language, and I think it’d be an interesting exercise.

  2. Pingback: Find the correct phrase | Brandon Doyle

Share your thoughts

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s