a-conjecture-of-mine

An exercise on polyglossy: the same problem solved on multiple languages

git clone: git://git.pablopie.xyz/a-conjecture-of-mine
Log
Files
Refs

Commit: 58dab933c84bed23a74bd8b86003c1435f0ba771
Parent: 33f698448da2f46ef2ee3aaefdb789a6af2d2cd2
Author: Pablo Escobar Gaviria <gark.garcia@protonmail.com>
Date: Sat, 4 Jan 2020 15:50:12 -0200

Cleaned the Kotlin implementation.

Diffstat

1 file changed, 40 insertions, 20 deletions

Status	File Name	N° Changes	Insertions	Deletions
Modified	Kotlin/src/main.kt	60	40	20

diff --git a/Kotlin/src/main.kt b/Kotlin/src/main.kt
@@ -2,49 +2,52 @@ package conjecture
 
 import kotlin.math.absoluteValue
 import kotlin.system.exitProcess
+import kotlin.collections.HashMap
 
 // The following program is a simple test for the following conjecture:
 
 // Let S: N -> N be the sum of the digits of a positive integer.
 // For all A and B in N, S(A + B) = S(A) + S(B) - 9k, where k is an integer.
 
+val OK = 0
+val FAIL = 1
+val INVALID_INPUT = 2
+
 fun main(args: Array<String>) {
     try {
         val max = args[0].toInt()
+        if (max <= 0) throw IllegalArgumentException()
 
-        if (counterexample(max)) exitProcess(1)
-        else exitProcess(0)
+        if (counterexample(max, HashMap(max * 2))) exitProcess(FAIL)
+        else exitProcess(OK)
 
     } catch (_: Exception) {
-        exitProcess(2)
+        exitProcess(INVALID_INPUT)
     }
 }
 
-internal fun counterexample(max: Int): Boolean {
-    val sum = sums(max)
-
+/**
+ * Searches for a counterexample for the theorem in
+ * `{(a, b) in N^2 | a <= max, b <= a}`.
+ */
+fun counterexample(max: Int, sums_cache: HashMap<Int, Int>): Boolean {
     for (a in 0..max)
         for (b in a..max) {
-            val diff = sum[a + b] - sum[a] - sum[b]
+            val sumAB = sums_cache.getSum(a + b)
+            val sumA  = sums_cache.getSum(a)
+            val sumB  = sums_cache.getSum(b)
+            val diff  = sumAB - sumA - sumB
 
-            if (diff % 9 != 0)
-                return true
+            if (diff % 9 != 0) return true
         }
 
     return false
 }
 
-fun sums (max: Int): IntArray {
-    val maxRange = 2 * max + 1
-    val sums = IntArray(maxRange)
-
-    for (i in 0 until maxRange)
-        sums[i] = sumDigits(i)
-
-    return sums
-}
-
-fun sumDigits(n: Int): Int {
+/**
+ * Calculates the sum of the digits of a positive integer.
+ */
+fun sum(n: Int): Int {
     var sum = 0
     var num = n.absoluteValue
 
@@ -54,4 +57,21 @@ fun sumDigits(n: Int): Int {
     }
 
     return sum
+}
+
+/**
+ * Attempts to lookup the sum of the digits of `key`.
+ * 
+ * If the lookup fails, calculate the sum of the digits
+ * of `key`, store it in the map and return it.
+ */
+fun HashMap<Int, Int>.getSum(key: Int): Int {
+    if (containsKey(key)) {
+        return getValue(key)
+    } else {
+        val value = sum(key)
+        put(key, value)
+
+        return value
+    }
 } 
\ No newline at end of file