From 82d812d593954b31a8187c65277e29363225dd55 Mon Sep 17 00:00:00 2001
From: Abigail <abigail@abigail.be>
Date: Thu, 20 May 2021 15:18:52 +0200
Subject: Python solutions for week 113

---
 challenge-113/abigail/python/ch-1.py | 31 +++++++++++++++++++++++++++++++
 1 file changed, 31 insertions(+)
 create mode 100644 challenge-113/abigail/python/ch-1.py

(limited to 'challenge-113/abigail/python/ch-1.py')

diff --git a/challenge-113/abigail/python/ch-1.py b/challenge-113/abigail/python/ch-1.py
new file mode 100644
index 0000000000..7bf1b0db11
--- /dev/null
+++ b/challenge-113/abigail/python/ch-1.py
@@ -0,0 +1,31 @@
+#!/opt/local/bin/python
+
+#
+# See ../README.md
+#
+
+#
+# Run as: python ch-1.py < input-file
+#
+
+import fileinput
+
+tens = [0, 0, 1, 2, 1, 0, 2, 6, 3, 8]
+
+for line in fileinput . input ():
+    (N, D) = line . split ();
+    N = int (N)
+    D = int (D)
+    D10 = 100 if D == 0 else 10 * D
+    if N >= D10 or (D == 0 and N % 10 == 0) or (D > 0 and N % D == 0):
+        print (1)
+        continue
+    done = False
+    for i in range (1, tens [D] + 1):
+        T = N - 10 * i - D
+        if T >= 0 and T % D == 0:
+            print (1)
+            done = True
+            break
+    if not done:
+        print (0)
-- 
cgit 


From 9043a1b2b6b9d2a1ca0bcf814210f84b0655aa45 Mon Sep 17 00:00:00 2001
From: Abigail <abigail@abigail.be>
Date: Sat, 22 May 2021 18:19:05 +0200
Subject: Slightly improved algorithm for week 113, part 1.

Also added a reference to a page with a proof of the algorithm.
---
 challenge-113/abigail/python/ch-1.py | 17 +++++++++++++----
 1 file changed, 13 insertions(+), 4 deletions(-)

(limited to 'challenge-113/abigail/python/ch-1.py')

diff --git a/challenge-113/abigail/python/ch-1.py b/challenge-113/abigail/python/ch-1.py
index 7bf1b0db11..ebb8821ddc 100644
--- a/challenge-113/abigail/python/ch-1.py
+++ b/challenge-113/abigail/python/ch-1.py
@@ -8,20 +8,29 @@
 # Run as: python ch-1.py < input-file
 #
 
+#     
+# 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
+#  
+
 import fileinput
 
-tens = [0, 0, 1, 2, 1, 0, 2, 6, 3, 8]
+gcds = [0, 1, 2, 1, 2, 5, 2, 1, 2, 1]
 
 for line in fileinput . input ():
     (N, D) = line . split ();
     N = int (N)
     D = int (D)
-    D10 = 100 if D == 0 else 10 * D
-    if N >= D10 or (D == 0 and N % 10 == 0) or (D > 0 and N % D == 0):
+    if D == 0:
+        print (1 if N >= 100 or N % 10 == 0 else 0)
+        continue
+
+    if N >= D * 10:
         print (1)
         continue
+
     done = False
-    for i in range (1, tens [D] + 1):
+    for i in range (0, D // gcds [D]):
         T = N - 10 * i - D
         if T >= 0 and T % D == 0:
             print (1)
-- 
cgit