AoC 2015.4 p1+2

5 files changed, 132 insertions, 12 deletions

diff --git a/report-repair/rr.scm b/report-repair/rr.scm
index 11c4bcd..d96fa20 100644
--- a/report-repair/rr.scm
+++ b/report-repair/rr.scm
@@ -1,20 +1,19 @@
 (define-module (rr)
   #:use-module (combinations)
   #:use-module (srfi srfi-1)
-  #:use-module (ice-9 format)
   #:use-module (ice-9 exceptions)
   #:export (rr
-	    get-2020-terms
-	    includes-all?
-	    generate-sets
-	    make-complete-set))
+            get-2020-terms
+            includes-all?
+            generate-sets
+            make-complete-set))
 
 (define (rr str len)
   (apply * (get-2020-terms (map string->number
-				(string-split
-				 (string-trim-both str char-set:whitespace)
-				 char-set:whitespace))
-			   len)))
+                                (string-split
+                                 (string-trim-both str char-set:whitespace)
+                                 char-set:whitespace))
+                           len)))
 
 (define (get-2020-terms lst len)
   "Given a list of numbers, returns a list
@@ -24,8 +23,8 @@ Throws input-exception if none are found."
   (let loop ((sets (generate-sets lst len)))
     (cond
      ((null? sets) (raise-exception
-		    (make-exception-with-message
-		     (format #f "Could not find ~s arguments that add to 2020 in inputs!" len))))
+                    (make-exception-with-message
+                     (format #f "Could not find ~s arguments that add to 2020 in inputs!" len))))
      ((includes-all? (car sets) lst) (car sets))
      (#t (loop (cdr sets))))))
 
@@ -33,7 +32,7 @@ Throws input-exception if none are found."
   "Returns #t if all elements in LST1
 are present in LST2, #f otherwise."
   (equal? lst1
-	  (lset-intersection eqv? lst1 lst2)))
+          (lset-intersection eqv? lst1 lst2)))
 
 (define (generate-sets lst len)
   (map make-complete-set (combinations lst (1- len))))
diff --git a/the-ideal-stocking-stuffer/README.org b/the-ideal-stocking-stuffer/README.org
new file mode 100644
index 0000000..8e1edb8
--- /dev/null
+++ b/the-ideal-stocking-stuffer/README.org
@@ -0,0 +1,26 @@
+See: https://adventofcode.com/2015/day/4
+** Part 1
+*** Purpose
+The idea is simple. Given a key:
+
+#+begin_example
+iwrupvqb
+#+end_example
+
+Append an integer to it, starting from 0:
+
+#+begin_example
+iwrupvqb0
+#+end_example
+
+And run it through the [[https://en.wikipedia.org/wiki/MD5][MD5 hash function]]. When the result starts with "00000", return that number!
+
+*** Method
+
+The algorithm is given to us. Simply implement MD5, and an environment that will allow us to brute-force test various keys.
+
+** Part 2
+*** Purpose
+Part two asks us to do the same thing---but look for a different output. Instead of five zeros in the resultant hash, we want six! By making this a variable, we can now look for any output!
+
+Beware, the more specific the desired output, the longer it takes to find!
diff --git a/the-ideal-stocking-stuffer/main.scm b/the-ideal-stocking-stuffer/main.scm
new file mode 100644
index 0000000..caa0fcb
--- /dev/null
+++ b/the-ideal-stocking-stuffer/main.scm
@@ -0,0 +1,16 @@
+;; -*- compile-command: "guix shell guile guile-hashing -- guile -L . -e main -s main.scm abcdef 000"; -*-
+(use-modules (tiss)
+             ((ice-9 rdelim))
+             (ice-9 binary-ports))
+
+
+(define (stdin-to-str)
+  (let loop ((result ""))
+    (let ((line (read-line)))
+      (if (eof-object? line)
+          result
+          (loop (string-append result line "\n"))))))
+
+(define (main args)
+  (display (tiss (cadr args) (caddr args) 0))
+  (newline))
diff --git a/the-ideal-stocking-stuffer/tiss-test.scm b/the-ideal-stocking-stuffer/tiss-test.scm
new file mode 100644
index 0000000..a85371b
--- /dev/null
+++ b/the-ideal-stocking-stuffer/tiss-test.scm
@@ -0,0 +1,40 @@
+;; -*- compile-command: "guix shell guile-hashing guile -- guile -L . tiss-test.scm"; -*-
+(use-modules (srfi srfi-64)
+             (tiss))
+
+(test-begin "harness")
+
+
+(test-equal "hash ''"
+  "d41d8cd98f00b204e9800998ecf8427e"
+  (get-hash "" ""))
+
+(test-equal "hash 'ab' + 'c'"
+  "900150983cd24fb0d6963f7d28e17f72"
+  (get-hash "ab" "c"))
+
+(test-equal "hash 'abcdef' + '609043'"
+  "000001dbbfa3a5c83a2d506429c7b00e"
+  (get-hash "abcdef" "609043"))
+
+(test-assert "starts-with is false"
+  (not (starts-with? "prefix" "ref")))
+
+(test-assert "starts-with is true"
+  (starts-with? "prefix" "pref"))
+
+(test-assert "hash starts with 00000"
+  (starts-with? "000001dbbfa3a5c83a2d506429c7b00e" "00000"))
+
+(test-assert "pre-picked correct (pre/suf)fix"
+  (starts-with? (get-hash "abcdef" "609043") "00000"))
+
+(test-equal "abcdef is 609043"
+  609043
+  (tiss "abcdef" "00000" 609030))
+
+(test-equal "pqrstuv is 1048970"
+  1048970
+  (tiss "pqrstuv" "00000" 0))
+
+(test-end "harness")
diff --git a/the-ideal-stocking-stuffer/tiss.scm b/the-ideal-stocking-stuffer/tiss.scm
new file mode 100644
index 0000000..5162b40
--- /dev/null
+++ b/the-ideal-stocking-stuffer/tiss.scm
@@ -0,0 +1,39 @@
+(define-module (tiss)
+  #:use-module (ice-9 string-fun)
+  #:use-module (hashing md5)
+  #:use-module (rnrs bytevectors)
+  #:use-module (ice-9 exceptions)
+  #:export (tiss
+            get-hash
+            starts-with?))
+
+
+(define (tiss prefix output-prefix suffix)
+  "Given KEY puzzle key and the desired
+OUTPUT-PREFIX, and the current suffix,
+incrementally tries hash inputs until
+the desired output is achieved.
+
+Throws an exception after 150000 iterations."
+  ;; (display (format #f "suffix is now: ~s\n" suffix))
+  (when (> suffix 1000000000)
+    (raise-exception
+     (make-exception-with-message
+      (format #f "Exceeded maximum attempts for key ~s!" prefix))))
+  (let ((output (get-hash prefix (number->string suffix))))
+    (if (starts-with? output output-prefix)
+        suffix
+        (tiss prefix output-prefix (1+ suffix)))))
+
+(define (get-hash prefix suffix)
+  "Computes the MD5 hash of prefix
+combined with suffix."
+  (md5->string
+   (md5 (string->utf8
+         (string-append prefix suffix)))))
+
+(define (starts-with? str prefix)
+  "Returns #t if STR starts with PREFIX."
+  (let ((prefix-length (string-length prefix)))
+    (and (>= (string-length str) prefix-length)
+         (equal? (substring str 0 prefix-length) prefix))))