Slightly improved algorithm for week 113, part 1.

Also added a reference to a page with a proof of the algorithm.

1 files changed, 14 insertions, 4 deletions

diff --git a/challenge-113/abigail/ruby/ch-1.rb b/challenge-113/abigail/ruby/ch-1.rb
index 4f44bf5130..dadd1f1a9c 100644
--- a/challenge-113/abigail/ruby/ch-1.rb
+++ b/challenge-113/abigail/ruby/ch-1.rb
@@ -8,20 +8,30 @@
 # Run as: ruby ch-1.rb < input-file
 #
 
-tens = [0, 0, 1, 2, 1, 0, 2, 6, 3, 8]
+#     
+# For a description of the algorithm, and the proof why this is correct:
+# https://abigail.github.io/HTML/Perl-Weekly-Challenge/week-113-1.html
+#  
+
+gcds = [0, 1, 2, 1, 2, 5, 2, 1, 2, 1]
 
 ARGF . each_line do
     | line |
     n, d = line . split
     n = n . to_i
     d = d . to_i
-    d10 = d == 0 ? 100 : d * 10
-    if   n >= d10 || n % (d == 0 ? 10 : d) == 0
+    if   d == 0
+         puts (n >= 100 || n % 10 == 0 ? 1 : 0)
+         next
+    end
+
+    if   n >= d * 10
     then puts (1)
          next
     end
+
     done = false
-    for i in 1 .. tens [d] do
+    for i in 0 .. d / gcds [d] - 1 do
         t = n - 10 * i - d
         if   t >= 0 && t % d == 0
         then puts (1)