072186c1d12e

Problem 112
[view raw] [browse files]
author Steve Losh <steve@stevelosh.com>
date Mon, 25 Sep 2017 20:39:47 -0400
parents 3629dbe4d8ff
children bb44fd64f2d2
branches/tags (none)
files src/problems.lisp src/utils.lisp

Changes

diff -r 3629dbe4d8ff -r 072186c1d12e src/problems.lisp
--- a/src/problems.lisp	Mon Sep 25 20:14:29 2017 -0400
+++ b/src/problems.lisp	Mon Sep 25 20:39:47 2017 -0400
@@ -1748,23 +1748,56 @@
   ;;
   ;; NOTE: The first two examples in the file represent the triangles in the
   ;; example given above.
-  (labels ((parse-file (file)
-             (iterate
-               (for (ax ay bx by cx cy) :in-csv-file file :key #'parse-integer)
-               (collect (list (vec2 ax ay)
-                              (vec2 bx by)
-                              (vec2 cx cy)))))
-           (check-triangle (a b c)
-             ;; A point is within a triangle if its barycentric coordinates
-             ;; (with respect to that triangle) are all within 0 to 1.
-             (multiple-value-bind (u v w)
-                 (barycentric a b c (vec2 0 0))
-               (and (<= 0 u 1)
-                    (<= 0 v 1)
-                    (<= 0 w 1)))))
+  (flet ((parse-file (file)
+           (iterate
+             (for (ax ay bx by cx cy) :in-csv-file file :key #'parse-integer)
+             (collect (list (vec2 ax ay)
+                            (vec2 bx by)
+                            (vec2 cx cy)))))
+         (check-triangle (a b c)
+           ;; A point is within a triangle if its barycentric coordinates
+           ;; (with respect to that triangle) are all within 0 to 1.
+           (multiple-value-bind (u v w)
+               (barycentric a b c (vec2 0 0))
+             (and (<= 0 u 1)
+                  (<= 0 v 1)
+                  (<= 0 w 1)))))
     (iterate (for (a b c) :in (parse-file "data/102-triangles.txt"))
              (counting (check-triangle a b c)))))
 
+(defun problem-112 ()
+  ;; Working from left-to-right if no digit is exceeded by the digit to its left
+  ;; it is called an increasing number; for example, 134468.
+  ;;
+  ;; Similarly if no digit is exceeded by the digit to its right it is called
+  ;; a decreasing number; for example, 66420.
+  ;;
+  ;; We shall call a positive integer that is neither increasing nor decreasing
+  ;; a "bouncy" number; for example, 155349.
+  ;;
+  ;; Clearly there cannot be any bouncy numbers below one-hundred, but just over
+  ;; half of the numbers below one-thousand (525) are bouncy. In fact, the least
+  ;; number for which the proportion of bouncy numbers first reaches 50% is 538.
+  ;;
+  ;; Surprisingly, bouncy numbers become more and more common and by the time we
+  ;; reach 21780 the proportion of bouncy numbers is equal to 90%.
+  ;;
+  ;; Find the least number for which the proportion of bouncy numbers is exactly
+  ;; 99%.
+  (flet ((bouncyp (integer)
+           (iterate
+             (for digit :in-digits-of integer)
+             (for prev :previous digit)
+             (unless-first-time
+               (oring (< prev digit) :into increasing)
+               (oring (> prev digit) :into decreasing))
+             (thereis (and increasing decreasing)))))
+    (iterate
+      (for i :from 1)
+      (for total :from 1)
+      (counting (bouncyp i) :into bouncy)
+      (finding i :such-that (= (/ bouncy total) 99/100)))))
+
 (defun problem-145 ()
   ;; Some positive integers n have the property that the sum [ n + reverse(n) ]
   ;; consists entirely of odd (decimal) digits. For instance, 36 + 63 = 99 and
diff -r 3629dbe4d8ff -r 072186c1d12e src/utils.lisp
--- a/src/utils.lisp	Mon Sep 25 20:14:29 2017 -0400
+++ b/src/utils.lisp	Mon Sep 25 20:39:47 2017 -0400
@@ -53,6 +53,16 @@
          (,kwd ,var :next (mapcar ,key (cl-strings:split (next ,line) ,delimiter)))))))
 
 
+(defmacro when-first-time (&body body)
+  `(if-first-time
+     (progn ,@body)))
+
+(defmacro unless-first-time (&body body)
+  `(if-first-time
+     nil
+     (progn ,@body)))
+
+
 (defun digits-length (n &optional (radix 10))
   "Return how many digits `n` has in base `radix`."
   (if (zerop n)