# HG changeset patch
# User Steve Losh <steve@stevelosh.com>
# Date 1507077602 14400
# Node ID 31594a0e04395d6c62557b6b6acc5f44b9237f80
# Parent  bb44fd64f2d21e434c12a5e953e9c230b68624aa
Problem 206

diff -r bb44fd64f2d2 -r 31594a0e0439 src/problems.lisp
--- a/src/problems.lisp	Mon Sep 25 20:39:56 2017 -0400
+++ b/src/problems.lisp	Tue Oct 03 20:40:02 2017 -0400
@@ -1825,6 +1825,29 @@
         (when reversible
           (sum (if (= i j) 1 2)))))))
 
+(defun problem-206 ()
+  ;; Find the unique positive integer whose square has the form
+  ;; 1_2_3_4_5_6_7_8_9_0, where each “_” is a single digit.
+  (flet ((targetp (i)
+           (and (= 0 (nth-digit 0 i))
+                (= 9 (nth-digit 2 i))
+                (= 8 (nth-digit 4 i))
+                (= 7 (nth-digit 6 i))
+                (= 6 (nth-digit 8 i))
+                (= 5 (nth-digit 10 i))
+                (= 4 (nth-digit 12 i))
+                (= 3 (nth-digit 14 i))
+                (= 2 (nth-digit 16 i))
+                (= 1 (nth-digit 18 i)))))
+    ;; The square ends with a 0, which means the original number must also end
+    ;; in 0.  This means the original number has to be divisible by 10, so we
+    ;; can take bigger steps.
+    (iterate
+      (with min = (round-to (sqrt 1020304050607080900) 10))
+      (with max = (floor (sqrt 1929394959697989990)))
+      (for i :from min :to max :by 10)
+      (finding i :such-that (targetp (square i))))))
+
 (defun problem-323 ()
   ;; Let y0, y1, y2,... be a sequence of random unsigned 32 bit integers (i.e.
   ;; 0 ≤ yi < 2^32, every value equally likely).
@@ -1893,12 +1916,12 @@
            (for prob = (probability-of-finishing-on runners n))
            (summing (* n prob))))
        (sanity-check (runners)
-         (assert (= (round-to (run-empirical-tests runners) 1)
-                    (round-to (expected-value runners) 1)))))
+         (assert (= (round-decimal (run-empirical-tests runners) 1)
+                    (round-decimal (expected-value runners) 1)))))
     (when nil
       (iterate (for i :from 1 :to 6)
                (sanity-check i)))
-    (round-to (expected-value 32) 10)))
+    (round-decimal (expected-value 32) 10)))
 
 (defun problem-345 ()
   ;; We define the Matrix Sum of a matrix as the maximum sum of matrix elements
@@ -2078,6 +2101,7 @@
 (test p99 (is (= 709 (problem-99))))
 (test p102 (is (= 228 (problem-102))))
 (test p145 (is (= 608720 (problem-145))))
+(test p206 (is (= 1389019170 (problem-206))))
 (test p323 (is (= 6.3551758451d0 (problem-323))))
 (test p345 (is (= 13938 (problem-345))))
 (test p357 (is (= 1739023853137 (problem-357))))
diff -r bb44fd64f2d2 -r 31594a0e0439 src/utils.lisp
--- a/src/utils.lisp	Mon Sep 25 20:39:56 2017 -0400
+++ b/src/utils.lisp	Tue Oct 03 20:40:02 2017 -0400
@@ -75,6 +75,11 @@
            (collect d :at :beginning)))
 
 
+(defun-inline nth-digit (n integer &optional (radix 10))
+  "Return the `n`th digit of `integer` in base `radix`, counting from the right."
+  (mod (truncate integer (expt radix n)) radix))
+
+
 (defun digits-to-number (digits)
   (if digits
     (reduce (lambda (total digit)
@@ -549,12 +554,25 @@
   (- 1 (expt (- 1 success-probability) trials)))
 
 
-(defun round-to (number precision &optional (rounder #'round))
+(defun round-decimal (number decimal-places &optional (rounder #'round))
   ;; http://www.codecodex.com/wiki/Round_a_number_to_a_specific_decimal_place#Common_Lisp
-  (coerce (let ((div (expt 10 precision)))
+  (coerce (let ((div (expt 10 decimal-places)))
             (/ (funcall rounder (* number div)) div))
           (type-of number)))
 
+(defun round-to (number precision)
+  "Round `number` to the given `precision`.
+
+  Examples:
+
+    (round-to 13 10)      ; => 10
+    (round-to 15 10)      ; => 20
+    (round-to 44 25)      ; => 50
+    (round-to 457/87 1/2) ; => 11/2
+
+  "
+  (* precision (round number precision)))
+
 
 (defun vec2 (x y)
   (vector x y))