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: 231a2b0c16af7c8ce001ad8d480f72d0ada6b87c
Parent: 6460f6000205d7e2be2d872b1a5b1bb2cb65f932
Author: Pablo Emilio Escobar Gaviria <pablo-escobar@riseup.net>
Date: Sat, 12 Dec 2020 12:15:20 -0300

Updated the OCaml implementation

Diffstat

6 files changed, 54 insertions, 59 deletions

Status	File Name	N° Changes	Insertions	Deletions
Modified	Makefile	4	4	0
Modified	c++/main.cpp	4	2	2
Modified	c/main.c	10	0	10
Renamed	script.pl -> knowledge-base.pl	0	0	0
Added	mercury/main.m	16	16	0
Modified	ocaml/main.ml	79	32	47

diff --git a/Makefile b/Makefile
@@ -40,3 +40,7 @@ rust-bin:
 wasm-bin:
 	wat2wasm ./wasm/main.wat -o ./bin/wasm.wasm
 
+mercury-bin:
+	mmc mercury/main.m -o bin/mercury
+	rm bin/*.o bin/*.c
+

diff --git a/c++/main.cpp b/c++/main.cpp
@@ -21,7 +21,7 @@ inline int sum_digits(unsigned int n)
     return sum;
 }
 
-bool counterexpl(unsigned int max, std::map<unsigned int, int> sums_cache)
+bool counterexpl(unsigned int max, std::vector<int> sums_cache)
 {
     for (auto a = 0; a <= max; a ++)
         for (auto b = a; b <= max; b++)
@@ -36,7 +36,7 @@ int main(int argc, char *argv[])
     if (argc < 2) return INVALID_INPUT;
     unsigned int max = std::stoul(argv[1]);
 
-    std::map<unsigned int, int> sums_cache;
+    std::vector<int> sums_cache;
     
     // Builds the sums cache
     for (int i = 0; i <= 2 * max; i++)

diff --git a/c/main.c b/c/main.c
@@ -1,16 +1,6 @@
 #include <stdlib.h>
 #include <stdio.h>
 
-// Imports to get system information
-#ifdef _WIN32
-#include <windows.h>
-#elif MACOS
-#include <sys/param.h>
-#include <sys/sysctl.h>
-#else
-#include <unistd.h>
-#endif
-
 #define SUCCESS 0
 #define FAIL 1
 #define INVALID_INPUT 2

diff --git a/script.pl b/knowledge-base.pl

diff --git a/mercury/main.m b/mercury/main.m
@@ -0,0 +1,16 @@
+:- module main.
+:- interface.
+:- import_module io.
+:- import_module int.
+:- pred main(io::di, io::uo) is det.
+:- implementation.
+
+:- func sum_digits_acc(int, int) = int.
+sum_digits_acc(N, Acc) = (if N = 0 then Acc else sum_digits_acc(N div 10, Acc + (N mod 10))).
+
+:- func sum_digits(int) = int.
+sum_digits(N) = sum_digits_acc(N, 0).
+
+main(!IO) :-
+  io.write_int(sum_digits(55), !IO),
+  io.nl(!IO).

diff --git a/ocaml/main.ml b/ocaml/main.ml
@@ -4,64 +4,49 @@
    For all A and B in N, S(A + B) = S(A) + S(B) - 9k, where k is an 
    interger. *)
 
-let failure: int = 1
-let invalid_input: int = 2
+let failure = 1
+let invalid_input = 2
 
 (** Returns the sum of the digits of `n`, where `n` is a positive integer. *) 
-let sum_digits (n: int) : int =
-    let rec sum_digits_tail n acc =
-        match n with
-        | 0 -> acc
-        | _ -> sum_digits_tail (n / 10) (acc + n mod 10)
-    in sum_digits_tail n 0
+let sum_digits n =
+  let rec sum_digits_tail n acc =
+    match n with
+    | 0 -> acc
+    | _ -> sum_digits_tail (n / 10) (acc + n mod 10)
+  in sum_digits_tail n 0
 
 (** Precompute the values of `sum_digits`.*)
-let get_sums (max: int) : int array =
-    Array.init (2 * max + 1) sum_digits
+let get_sums max =
+  Array.init (2 * max + 1) sum_digits
+
+(** Returns true if a counterexample (a, b) with 0 <= a, b <= max exists **)
+let counterexempl max =
+  let rec sums_cache = get_sums max (* Cache the results of sum_digists *)
+  and sum_digits n = Array.get sums_cache n 
 
-let test (a: int) (b: int) (sums_cache: int array) : bool =
-    let sum_digits n = Array.get sums_cache n in
+  (* Returns true if (a, b) is a counterexemple *)
+  and test a b = 
     0 <> (sum_digits (a + b) - sum_digits a - sum_digits b) mod 9
 
-let rec listen (c: bool Event.channel) (n: int) : unit =
-    match n with
-    | 0 -> ()
-    | _ when Event.sync (Event.receive c) -> exit failure 
-    | _ -> listen c (n - 1)
+  (* Returns true if there is b with 0 <= b <= a such that (a, b) is a
+      counterexample *)
+  and aux a = aux_tail a a false
+  and aux_tail a b acc =
+    if b <= 0 then acc else aux_tail a (b - 1) (acc || test a b)
 
-let counterexempl (max: int) (n_threads: int) : unit =
-    let sums_cache = get_sums max
-    and c = Event.new_channel () in
-    let counterexempl_range start =
-        let send b = let () = Event.sync (Event.send c b) in Thread.exit () in
-        let rec aux a = 
-            let () = 
-                for b = 0 to a do
-                    if test a b sums_cache then send true 
-                done 
-            and a_ = a + n_threads in
-            if a_ <= max then aux a_ else send false in
+  and counterexempl_tail a acc =
+    if a <= 0 then acc else counterexempl_tail (a - 1) (acc || aux a)
 
-        aux start in
-    let spawn = Thread.create counterexempl_range in
-    
-    let _ = Array.init n_threads spawn in
-    listen c n_threads 
+  in counterexempl_tail max false
 
 let main () =
-    let arg n = 
-        if Array.length Sys.argv > n then int_of_string_opt Sys.argv.(n) 
-        else None in
-    let max = arg 1 
-    and n_threads =
-        match arg 2 with
-        | Some n -> n
-        | None -> 1 in
-    
-    match max with
-    | Some max when max > 0 && n_threads > 0 -> counterexempl max 2
-    | _ -> exit invalid_input
+  let max_opt = 
+    if Array.length Sys.argv > 1 then int_of_string_opt Sys.argv.(1) 
+    else None in
+  match max_opt with
+  | Some max when max > 0 -> if counterexempl max then exit failure else ()
+  | _ -> exit invalid_input
 
 let () = 
-    main ()
+  main ()