An exercise on polyglossy: the same problem solved on multiple languages
Revert "Updated the Rust and the Go implementations to fit the new algorthm."
This reverts commit 3fd6bd1adb62ee1365a27e075a514bb28f3f2ed3.
2 files changed, 120 insertions, 129 deletions
| Status | File Name | N° Changes | Insertions | Deletions |
| Added | Go/conjecture.go | 120 | 120 | 0 |
| Deleted | Go/main.go | 129 | 0 | 129 |
diff --git a/Go/conjecture.go b/Go/conjecture.go @@ -0,0 +1,120 @@ +package main + +// This 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 interger. + +import ( + "os" + "strconv" +) + +type iter struct { + Start uint + Max uint + Interval uint +} + +const success = 0 +const fail = 1 +const invalidInput = 2 + +func main() { + if len(os.Args) > 0 { + nThreads := uint(1) + + if len(os.Args) > 1 { + if arg, err := strconv.ParseUint(os.Args[2], 10, 64); err == nil && arg >= 1 { + nThreads = uint(arg) + } + } + + if max, err := strconv.ParseUint(os.Args[0], 10, 64); err == nil { + if getCounterexample(uint(max), nThreads) { + os.Exit(fail) + } else { + os.Exit(success) + } + } else { + os.Exit(invalidInput) + } + } else { + os.Exit(invalidInput) + } + +} + +func getCounterexample(max uint, nThreads uint) bool { + sums := getSums(max) + + if nThreads > 1 { + channels := make([](chan bool), nThreads) + + // Compute the result of each sub-range + for i := 0; i < int(nThreads); i++ { + channels[i] = make(chan bool) + it := iter{uint(i), max, nThreads} + + go getCounterIter(it, &sums, channels[i]) + } + + // Listen for the computation to finish + for _, c := range channels { + if msg := <-c; msg { + return true + } + } + } else { + c := make(chan bool) + it := iter{0, max, 1} + + go getCounterIter(it, &sums, c) + + return <-c + } + + return false +} + +func getCounterIter(it iter, sums *[]int, c chan bool) { + for a := it.Start; a <= it.Max; a += it.Interval { + for b := a; b <= it.Max; b++ { + diff := (*sums)[a+b] - (*sums)[a] - (*sums)[b] + + if diff%9 != 0 { + c <- true + close(c) + + return + } + } + } + + c <- false + close(c) +} + +func getSums(max uint) []int { + maxRange := 2*max + 1 + sums := make([]int, maxRange) + + for i := range sums { + sums[i] = sumDigits(uint(i)) + } + + return sums +} + +func sumDigits(n uint) int { + var sum uint + + for { + if n <= 0 { + return int(sum) + } + + sum += n % 10 + n /= 10 + } +}
diff --git a/Go/main.go b/Go/main.go @@ -1,129 +0,0 @@ -package main - -// This 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 interger. - -import ( - "os" - "strconv" - "sync" -) - -const success = 0 -const fail = 1 -const invalidInput = 2 - -var lock = sync.RWMutex{} -var sumsCache = map[uint]int{} -var max uint = 1 -var nGoRoutines uint = 1 - -func main() { - if len(os.Args) > 0 { - if len(os.Args) > 1 { - if arg, err := strconv.ParseUint(os.Args[2], 10, 64); err == nil && arg >= 1 { - nGoRoutines = uint(arg) - } - } - - if val, err := strconv.ParseUint(os.Args[0], 10, 64); err == nil { - max = uint(val) - - if counterexample() { - os.Exit(fail) - } else { - os.Exit(success) - } - } else { - os.Exit(invalidInput) - } - } else { - os.Exit(invalidInput) - } - -} - -func counterexample() bool { - if nGoRoutines > 1 { - channels := make([](chan bool), nGoRoutines) - - // Compute the result of each sub-range - for i := uint(0); i < nGoRoutines; i++ { - channels[i] = make(chan bool) - go counterIter(i, channels[i]) - } - - // Listen for the computation to finish - for _, c := range channels { - if msg := <-c; msg { - return true - } - } - } else { - c := make(chan bool) - go counterIter(0, c) - - return <-c - } - - return false -} - -func counterIter(start uint, c chan bool) { - for a := start; a <= max; a += nGoRoutines { - for b := a; b <= max; b++ { - sumAB := lookupOrInsert(a + b) - sumA := lookupOrInsert(a) - sumB := lookupOrInsert(b) - diff := sumAB - sumA - sumB - - if diff%9 != 0 { - c <- true - close(c) - - return - } - } - } - - c <- false - close(c) -} - -// Searches for the value of `sumDigits(n)` in the global -// `sumsCache` store. -// If the value is found, it gets returned. -// Otherwise, the value is calculated, stored and then returned. -func lookupOrInsert(n uint) int { - lock.RLock() - defer lock.RUnlock() - sumN, included := sumsCache[n] - - if included { - return sumN - } - - sumN = sumDigits(n) - - lock.Lock() - defer lock.Unlock() - sumsCache[n] = sumN - - return sumN -} - -func sumDigits(n uint) int { - var sum uint - - for { - if n == 0 { - return int(sum) - } - - sum += n % 10 - n /= 10 - } -} -