Slightly improved algorithm for week 113, part 1.

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

1 files changed, 20 insertions, 11 deletions

diff --git a/challenge-113/abigail/bash/ch-1.sh b/challenge-113/abigail/bash/ch-1.sh
index 7183523485..d3e60eddf4 100644
--- a/challenge-113/abigail/bash/ch-1.sh
+++ b/challenge-113/abigail/bash/ch-1.sh
@@ -8,22 +8,31 @@
 # Run as: bash ch-1.sh < 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)
 
 while read N D
-do    ((D10 = D == 0 ? 100 : 10 * D))
-      if ((N >= D10 || (N % (D == 0 ? 10 : D) == 0)))
+do    if   ((D == 0))
+      then if ((N >= 100 || N % 10 == 0))
+           then echo 1
+           else echo 0
+           fi
+           continue
+      fi
+      if   ((N >= D * 10))
       then echo 1
            continue
       fi
-      for ((i = 1; i <= ${tens[$D]}; i ++))
-      do  ((T = N - 10 * i - D))
-          if  ((T >= 0 && T % D == 0))
-          then echo 1
-               continue 2
-          fi
+      for  ((i = 0; i < D / gcds[D]; i ++))
+      do   ((T = N - 10 * i - D))
+           if  ((T >= 0 && T % D == 0))
+           then echo 1
+                continue 2
+           fi
       done
       echo 0
 done
-           
-