From fdd800775ca52e7600d78f38e5345a5197cc086c Mon Sep 17 00:00:00 2001 From: Andrew Shitov Date: Fri, 4 Dec 2020 09:17:37 +0100 Subject: Week 89 Issue 1 --- challenge-089/ash/bash/ch-1.bash | 37 +++++++++++++++++++++++++++++++ challenge-089/ash/c/ch-1.c | 37 +++++++++++++++++++++++++++++++ challenge-089/ash/cpp/ch-1.cpp | 29 +++++++++++++++++++++++++ challenge-089/ash/csharp/ch-1.cs | 26 ++++++++++++++++++++++ challenge-089/ash/d/ch1.d | 20 +++++++++++++++++ challenge-089/ash/dart/ch-1.dart | 18 ++++++++++++++++ challenge-089/ash/fortran/ch-1.f95 | 42 ++++++++++++++++++++++++++++++++++++ challenge-089/ash/go/ch-1.go | 35 ++++++++++++++++++++++++++++++ challenge-089/ash/java/ch-1.java | 29 +++++++++++++++++++++++++ challenge-089/ash/javascript/ch-1.js | 24 +++++++++++++++++++++ challenge-089/ash/julia/ch-1.julia | 15 +++++++++++++ challenge-089/ash/kotlin/ch-1.kt | 34 +++++++++++++++++++++++++++++ challenge-089/ash/lisp/ch-1.lisp | 18 ++++++++++++++++ challenge-089/ash/lua/ch-1.lua | 24 +++++++++++++++++++++ challenge-089/ash/pascal/ch-1.pas | 40 ++++++++++++++++++++++++++++++++++ challenge-089/ash/perl/ch-1.pl | 19 ++++++++++++++++ challenge-089/ash/php/ch-1.php | 27 +++++++++++++++++++++++ challenge-089/ash/python/ch-1.py | 14 ++++++++++++ challenge-089/ash/raku/ch-1.raku | 9 ++++++++ challenge-089/ash/readme.md | 31 ++++++++++++++++++++++++++ challenge-089/ash/ruby/ch-1.rb | 14 ++++++++++++ challenge-089/ash/rust/ch-1.rs | 40 ++++++++++++++++++++++++++++++++++ challenge-089/ash/scala/ch-1.scala | 22 +++++++++++++++++++ 23 files changed, 604 insertions(+) create mode 100644 challenge-089/ash/bash/ch-1.bash create mode 100644 challenge-089/ash/c/ch-1.c create mode 100644 challenge-089/ash/cpp/ch-1.cpp create mode 100644 challenge-089/ash/csharp/ch-1.cs create mode 100644 challenge-089/ash/d/ch1.d create mode 100644 challenge-089/ash/dart/ch-1.dart create mode 100644 challenge-089/ash/fortran/ch-1.f95 create mode 100644 challenge-089/ash/go/ch-1.go create mode 100644 challenge-089/ash/java/ch-1.java create mode 100644 challenge-089/ash/javascript/ch-1.js create mode 100644 challenge-089/ash/julia/ch-1.julia create mode 100644 challenge-089/ash/kotlin/ch-1.kt create mode 100644 challenge-089/ash/lisp/ch-1.lisp create mode 100644 challenge-089/ash/lua/ch-1.lua create mode 100644 challenge-089/ash/pascal/ch-1.pas create mode 100644 challenge-089/ash/perl/ch-1.pl create mode 100644 challenge-089/ash/php/ch-1.php create mode 100644 challenge-089/ash/python/ch-1.py create mode 100644 challenge-089/ash/raku/ch-1.raku create mode 100644 challenge-089/ash/readme.md create mode 100644 challenge-089/ash/ruby/ch-1.rb create mode 100644 challenge-089/ash/rust/ch-1.rs create mode 100644 challenge-089/ash/scala/ch-1.scala diff --git a/challenge-089/ash/bash/ch-1.bash b/challenge-089/ash/bash/ch-1.bash new file mode 100644 index 0000000000..cb3cd93dbb --- /dev/null +++ b/challenge-089/ash/bash/ch-1.bash @@ -0,0 +1,37 @@ +#!/usr/bin/bash + +# Usage: +# $ bash ch-1.bash 100 +# 13015 +# +# N. B. Try with smaller arguments, as computations +# for the input number of 100 can take a while (~ a minute). + +gcd() { + a=$1; + b=$2; + while [ $b -ne 0 ]; do + t=$b + b=`expr $a % $b` + a=$t + done + + gcd=$a +} + +n=${1:-3} # default is 3 + +s=0 +x=1 +while [ $x -le $n ]; do + next=`expr $x + 1`; + y=$next; + while [ $y -le $n ]; do + y=`expr $y + 1`; + gcd $x $y; + s=`expr $s + $gcd`; + done + x=$next; +done + +echo $s diff --git a/challenge-089/ash/c/ch-1.c b/challenge-089/ash/c/ch-1.c new file mode 100644 index 0000000000..efabf62f7f --- /dev/null +++ b/challenge-089/ash/c/ch-1.c @@ -0,0 +1,37 @@ +/* + Compile: + $ gcc ch-1.c + + Test run: + $ ./a.out 100 + 13015 +*/ + +#include +#include + +int gcd(int a, int b) { + while (b) { + int t = b; + b = a % b; + a = t; + } + + return a; +} + +int main(int argc, char** argv) { + int n = 3; + if (argc != 1) { + n = atoi(argv[1]); + } + + int s = 0; + for (int x = 1; x <= n; x++) { + for (int y = x + 1; y <= n; y++) { + s += gcd(x, y); + } + } + + printf("%i\n", s); +} diff --git a/challenge-089/ash/cpp/ch-1.cpp b/challenge-089/ash/cpp/ch-1.cpp new file mode 100644 index 0000000000..b2500a4630 --- /dev/null +++ b/challenge-089/ash/cpp/ch-1.cpp @@ -0,0 +1,29 @@ +// Compile as: +// $ g++ -std=c++17 ch-1.cpp + +// Test run: +// $ ./a.out 100 +// 13015 + +#include +#include +#include + +using namespace std; + +int main(int argc, char** argv) { + int n = 3; + if (argc != 1) { + stringstream input(argv[1]); + input >> n; + } + + int s = 0; + for (int x = 1; x <= n; x++) { + for (int y = x + 1; y <= n; y++) { + s += gcd(x, y); + } + } + + cout << s << endl; +} diff --git a/challenge-089/ash/csharp/ch-1.cs b/challenge-089/ash/csharp/ch-1.cs new file mode 100644 index 0000000000..2b2cc9a160 --- /dev/null +++ b/challenge-089/ash/csharp/ch-1.cs @@ -0,0 +1,26 @@ +// Compile and run on a Mac: +// $ csc -r:System.Numerics.dll ch-1.cs +// $ mono ch-1.exe 100 +// 13015 + +using System; +using System.Numerics; + +class Program { + static int Main(string[] args) + { + int n = 3; + if (args.Length == 1) n = int.Parse(args[0]); + + var s = new BigInteger(0); + for (int x = 1; x <= n; x++) { + for (int y = x + 1; y <= n; y++) { + s += BigInteger.GreatestCommonDivisor(x, y); + } + } + + System.Console.WriteLine(s); + + return 0; + } +} diff --git a/challenge-089/ash/d/ch1.d b/challenge-089/ash/d/ch1.d new file mode 100644 index 0000000000..ca05ffd74a --- /dev/null +++ b/challenge-089/ash/d/ch1.d @@ -0,0 +1,20 @@ +// How to run: +// $ rdmd ch1.d 100 +// 13015 + +import std.stdio; +import std.numeric; +import std.conv; + +void main(string[] args) { + auto n = args.length == 2 ? to!int(args[1]) : 3; + + auto s = 0; + for (auto x = 1; x <= n; x++) { + for (auto y = x + 1; y <= n; y++) { + s += gcd(x, y); + } + } + + writeln(s); +} diff --git a/challenge-089/ash/dart/ch-1.dart b/challenge-089/ash/dart/ch-1.dart new file mode 100644 index 0000000000..bce73b312a --- /dev/null +++ b/challenge-089/ash/dart/ch-1.dart @@ -0,0 +1,18 @@ +// To run: +// $ dart ch-1.dart 100 +// 13015 + +void main(List args) { + var n = 3; + if (args.length == 1) + n = int.parse(args[0]); + + var s = 0; + for (var x = 1; x <= n; x++) { + for (var y = x + 1; y <= n; y++) { + s += x.gcd(y); + } + } + + print(s); +} diff --git a/challenge-089/ash/fortran/ch-1.f95 b/challenge-089/ash/fortran/ch-1.f95 new file mode 100644 index 0000000000..71f766dbd0 --- /dev/null +++ b/challenge-089/ash/fortran/ch-1.f95 @@ -0,0 +1,42 @@ +! To compile and run: +! +! $ gfortran ch-1.f95 +! $ ./a.out 100 +! 13015 + +function mygcd(a, b) result(x) + integer, intent(in) :: a, b + integer :: x, y, t + + x = a + y = b + + do while (y /= 0) + t = y + y = mod(x, y) + x = t + end do +end function + +program hello + integer :: n, x, y, s + + character(len=20) :: arg + character(len=20) :: nstr + + if (iargc() == 1) then + call getarg(1, nstr) + read(nstr,*) n + else + n = 3 + end if + + s = 0 + do x = 1, n + do y = x + 1, n + s = s + mygcd(x, y) + end do + end do + + write(*,*) s +end program diff --git a/challenge-089/ash/go/ch-1.go b/challenge-089/ash/go/ch-1.go new file mode 100644 index 0000000000..8d3fb5dfb6 --- /dev/null +++ b/challenge-089/ash/go/ch-1.go @@ -0,0 +1,35 @@ +// To compile and run: +// $ go run ch-1.go 100 +// 13015 + +package main + +import ( + "fmt" + "os" + "strconv" +) + +func gcd(a, b int) int { + for b != 0 { + b, a = a%b, b + } + + return a +} + +func main() { + n := 3 + if len(os.Args) == 2 { + n, _ = strconv.Atoi(os.Args[1]) + } + + s := 0 + for x := 1; x <= n; x++ { + for y := x + 1; y <= n; y++ { + s += gcd(x, y) + } + } + + fmt.Println(s) +} diff --git a/challenge-089/ash/java/ch-1.java b/challenge-089/ash/java/ch-1.java new file mode 100644 index 0000000000..9e41cf211f --- /dev/null +++ b/challenge-089/ash/java/ch-1.java @@ -0,0 +1,29 @@ +// To run: +// $ java ch-1.java 100 +// 13015 + +class Main { + static int gcd(int a, int b) { + while (b != 0) { + int t = b; + b = a % b; + a = t; + } + + return a; + } + + public static void main(String[] args) { + int n = args.length == 1 ? Integer.parseInt(args[0]) : 3; + + int s = 0; + for (int x = 1; x <= n; x++) { + for (int y = x + 1; y <= n; y++) { + + s += gcd(x, y); + } + } + + System.out.println(s); + } +} diff --git a/challenge-089/ash/javascript/ch-1.js b/challenge-089/ash/javascript/ch-1.js new file mode 100644 index 0000000000..c090b44808 --- /dev/null +++ b/challenge-089/ash/javascript/ch-1.js @@ -0,0 +1,24 @@ +// Test run: +// $ node ch-1.js 100 +// 13015 + +let n = process.argv.length == 3 ? process.argv[2] : 3; + +let s = 0; +for (let x = 1; x <= n; x++) { + for (let y = x + 1; y <= n; y++) { + s += gcd(x, y); + } +} + +console.log(s); + +function gcd(a, b) { + while (b) { + let t = b; + b = a % b; + a = t; + } + + return a; +} diff --git a/challenge-089/ash/julia/ch-1.julia b/challenge-089/ash/julia/ch-1.julia new file mode 100644 index 0000000000..22f30004b4 --- /dev/null +++ b/challenge-089/ash/julia/ch-1.julia @@ -0,0 +1,15 @@ +# To run: +# $ julia ch-1.julia 100 +# 13015 + +n = length(ARGS) == 1 ? parse(Int, ARGS[1]) : 3 + +s = 0 +for x in range(1, stop = n) + for y in range(x + 1, stop = n) + global s + s += gcd(x, y) + end +end + +println(s) diff --git a/challenge-089/ash/kotlin/ch-1.kt b/challenge-089/ash/kotlin/ch-1.kt new file mode 100644 index 0000000000..b3b6607e1f --- /dev/null +++ b/challenge-089/ash/kotlin/ch-1.kt @@ -0,0 +1,34 @@ +// How to run: +// $ kotlinc ch-1.kt -include-runtime -d ch1.jar +// $ java -jar ch1.jar 100 +// 13015 + +fun gcd(a: Int, b: Int): Int { + var x = a + var y = b + + while (y != 0) { + val t = y + y = x % y + x = t + } + + return x +} + +fun main(args: Array) { + var n: Int + if (args.size == 1) + n = args[0].toInt() + else + n = 3 + + var s = 0 + for (x in 1..n) { + for (y in x + 1 .. n) { + s += gcd(x, y) + } + } + + println(s) +} diff --git a/challenge-089/ash/lisp/ch-1.lisp b/challenge-089/ash/lisp/ch-1.lisp new file mode 100644 index 0000000000..4bcdcceb36 --- /dev/null +++ b/challenge-089/ash/lisp/ch-1.lisp @@ -0,0 +1,18 @@ +;;; How to run: +;;; $ sbcl --script ch-1.lisp 100 +;;; +;;; 13015 + +(defvar n (parse-integer (nth 1 *posix-argv*))) + +(defvar s 0) + +(loop for x from 1 to n + do ( + loop for y from (+ 1 x) to n + do (setq s (+ s (gcd x y))) + ) +) + +(print s) +(terpri) diff --git a/challenge-089/ash/lua/ch-1.lua b/challenge-089/ash/lua/ch-1.lua new file mode 100644 index 0000000000..8d9ff3bdda --- /dev/null +++ b/challenge-089/ash/lua/ch-1.lua @@ -0,0 +1,24 @@ +-- How to run: +-- $ lua ch-1.lua 100 +-- 13015 + +function gcd(a, b) + while b > 0 do + t = b + b = a % b + a = t + end + + return a +end + +n = arg[1] and arg[1] or 3 + +s = 0 +for x = 1, n do + for y = x + 1, n do + s = s + gcd(x, y) + end +end + +print(s) diff --git a/challenge-089/ash/pascal/ch-1.pas b/challenge-089/ash/pascal/ch-1.pas new file mode 100644 index 0000000000..aeb64d4b38 --- /dev/null +++ b/challenge-089/ash/pascal/ch-1.pas @@ -0,0 +1,40 @@ +(* + To compile and run: + $ fpc ch-1.pas + $ ./ch-1 100 + 13015 +*) + +program Hello(input, output); + +uses sysutils; + +var + n, x, y, s: integer; + +function gcd(a, b: integer): integer; +var + t: integer; +begin + while b <> 0 do begin + t := b; + b := a mod b; + a := t; + end; + + gcd := a +end; + +begin + if paramCount() = 0 then + n := 3 + else + n := StrToInt(paramStr(1)); + + s := 0; + for x := 1 to n do + for y := x + 1 to n do + s += gcd(x, y); + + writeln(s); +end. diff --git a/challenge-089/ash/perl/ch-1.pl b/challenge-089/ash/perl/ch-1.pl new file mode 100644 index 0000000000..4eb4beac91 --- /dev/null +++ b/challenge-089/ash/perl/ch-1.pl @@ -0,0 +1,19 @@ +# To run, install Math::Utils first: +# $ cpanm Math::Utils +# $ perl ch-1.pl 100 +# 13015 + +use v5.12; + +use Math::Utils qw(gcd); + +my $n = $ARGV[0] // 3; + +my $s = 0; +for my $x (1 .. $n) { + for my $y ($x + 1 .. $n) { + $s += gcd($x, $y); + } +} + +say $s; diff --git a/challenge-089/ash/php/ch-1.php b/challenge-089/ash/php/ch-1.php new file mode 100644 index 0000000000..9209076d61 --- /dev/null +++ b/challenge-089/ash/php/ch-1.php @@ -0,0 +1,27 @@ + diff --git a/challenge-089/ash/python/ch-1.py b/challenge-089/ash/python/ch-1.py new file mode 100644 index 0000000000..b962d9c617 --- /dev/null +++ b/challenge-089/ash/python/ch-1.py @@ -0,0 +1,14 @@ +# Test run: +# $ python3 ch-1.py 100 +# 13015 + +import sys, math + +n = 3 if len(sys.argv) == 1 else int(sys.argv[1]) + +s = 0 +for x in range(1, n + 1): + for y in range(x + 1, n + 1): + s += math.gcd(x, y) + +print(s) diff --git a/challenge-089/ash/raku/ch-1.raku b/challenge-089/ash/raku/ch-1.raku new file mode 100644 index 0000000000..7738ca31ff --- /dev/null +++ b/challenge-089/ash/raku/ch-1.raku @@ -0,0 +1,9 @@ +#!/usr/bin/env raku + +# Test run: +# $ raku ch-1.raku 100 +# 13015 + +my $n = @*ARGS[0] // 3; + +say [+] (1..$n).combinations(2).map: {[gcd] $_}; diff --git a/challenge-089/ash/readme.md b/challenge-089/ash/readme.md new file mode 100644 index 0000000000..9870595c8c --- /dev/null +++ b/challenge-089/ash/readme.md @@ -0,0 +1,31 @@ +# Week 89, Issue 1 + +Implemenations of [Problem 1 of Week 89](https://perlweeklychallenge.org/blog/perl-weekly-challenge-089/#TASK1) of The Weekly Challenge in different programming languages. + +## Using built-in or library functions for GCD + +1. [Raku](raku/ch-1.raku) +1. [Python](python/ch-1.py) +1. [C++ (C++17)](cpp/ch-1.cpp) +1. [Perl](perl/ch-1.pl) +1. [Ruby](ruby/ch-1.rb) +1. [Lua](lua/ch-1.lua) +1. [Scala](scala/ch-1.scala) +1. [C#](csharp/ch-1.cs) +1. [Dart](dart.ch-1.dart) +1. [Julia](julia/ch-1.julia) +1. [D](d/ch-1.d) +1. [Lisp (SBCL)](lisp/ch-1.lisp) + +## With a custom implementation of GCD + +1. [C](c/ch-1.c) +1. [node.js (JavaScript)](javascript/ch-1.js) +1. [Java](java/ch-1.java) +1. [Rust](rust/ch-1.rs) +1. [Pascal (FreePascal)](pascal/ch-1.pas) +1. [Go](go/ch-1.go) +1. [Fortran (Fortran 95)](fortran/ch-1.f95) +1. [PHP](php/ch-1.php) +1. [Kotlin](kotlin/ch-1.kt) +1. [Bash](bash/ch-1.bash) diff --git a/challenge-089/ash/ruby/ch-1.rb b/challenge-089/ash/ruby/ch-1.rb new file mode 100644 index 0000000000..19b9d813fc --- /dev/null +++ b/challenge-089/ash/ruby/ch-1.rb @@ -0,0 +1,14 @@ +# Usage: +# $ ruby ch-1.rb 100 +# 13015 + +n = ARGV.length == 1 ? ARGV[0].to_i : 3 + +s = 0 +for x in 1 .. n + for y in x + 1 .. n + s += x.gcd(y) + end +end + +puts s diff --git a/challenge-089/ash/rust/ch-1.rs b/challenge-089/ash/rust/ch-1.rs new file mode 100644 index 0000000000..f72d85746a --- /dev/null +++ b/challenge-089/ash/rust/ch-1.rs @@ -0,0 +1,40 @@ +// To compile and run: +// $ rustc ch-1.rs +// $ ./ch-1 100 +// 13015 + +use std::env; + +fn gcd(a: u32, b: u32) -> u32 { + let mut x = a; + let mut y = b; + + while y != 0 { + let t = y; + y = x % y; + x = t; + } + + return x; +} + +fn main() { + let args: Vec = env::args().collect(); + + let n; + if args.len() == 2 { + n = args[1].parse().unwrap(); + } + else { + n = 3; + } + + let mut s = 0; + for x in 1 .. (n + 1) { + for y in (x + 1) .. (n + 1) { + s += gcd(x, y); + } + } + + println!("{}", s); +} diff --git a/challenge-089/ash/scala/ch-1.scala b/challenge-089/ash/scala/ch-1.scala new file mode 100644 index 0000000000..054e544f5f --- /dev/null +++ b/challenge-089/ash/scala/ch-1.scala @@ -0,0 +1,22 @@ +/* + To run: + $ scala ch-1.scala 100 + 13015 +*/ + +import math.BigInt + +object Main { + def main(args: Array[String]): Unit = { + var n: Int = if (args.size == 1) args(0).toInt else 3 + + var s: BigInt = 0 + for (x <- 1 to n) { + for (y <- x + 1 to n) { + s = s + BigInt(x).gcd(y) + } + } + + println(s) + } +} -- cgit From a2a75dcba0a606d0b251959490c8d701de91c972 Mon Sep 17 00:00:00 2001 From: Andrew Shitov Date: Fri, 4 Dec 2020 09:22:05 +0100 Subject: fix links --- challenge-089/ash/readme.md | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/challenge-089/ash/readme.md b/challenge-089/ash/readme.md index 9870595c8c..e21127020f 100644 --- a/challenge-089/ash/readme.md +++ b/challenge-089/ash/readme.md @@ -12,9 +12,9 @@ Implemenations of [Problem 1 of Week 89](https://perlweeklychallenge.org/blog/pe 1. [Lua](lua/ch-1.lua) 1. [Scala](scala/ch-1.scala) 1. [C#](csharp/ch-1.cs) -1. [Dart](dart.ch-1.dart) +1. [Dart](dart/ch-1.dart) 1. [Julia](julia/ch-1.julia) -1. [D](d/ch-1.d) +1. [D](d/ch1.d) 1. [Lisp (SBCL)](lisp/ch-1.lisp) ## With a custom implementation of GCD -- cgit From 78eed9e7149ff1d126fc5cb1bd59e3961c1ff5a2 Mon Sep 17 00:00:00 2001 From: Andrew Shitov Date: Fri, 4 Dec 2020 16:56:32 +0100 Subject: Blog post --- challenge-089/ash/index.md | 752 +++++++++++++++++++++++++++++++++++++++ challenge-089/ash/lisp/ch-1.lisp | 2 +- challenge-089/ash/readme.md | 46 +-- 3 files changed, 777 insertions(+), 23 deletions(-) create mode 100644 challenge-089/ash/index.md diff --git a/challenge-089/ash/index.md b/challenge-089/ash/index.md new file mode 100644 index 0000000000..38ba73df6a --- /dev/null +++ b/challenge-089/ash/index.md @@ -0,0 +1,752 @@ +Christmas time, and it’s time to talk to each and every one! It’s a great idea to approach people by speaking their languages. In today’s post, let me demonstrate a number of working solutions of [the first problem of Week 89](https://perlweeklychallenge.org/blog/perl-weekly-challenge-089/#TASK1) of The Weekly Challenge in 22 different programming languages. It is a kind of continuation of my last year’s Advent series ‘[A Language a Day](https://andrewshitov.com/2019/11/25/a-language-a-day-advent-calendar-2019/)’. + +# Problem + +The problem is to add up all the [GCD](https://en.wikipedia.org/wiki/Greatest_common_divisor)s of the series of unique pairs of numbers between `1` and `$N` including `$N`. + +For example, for the input number `100`, the summation chain is this one: + + GCD(1, 2) + GCD(1, 3) + GCD(1, 4) + ... + GCD(1, 99) + GCD(1, 100) + + GCD(2, 3) + GCD(2, 4) + GCD(2, 5) + ... + GCD(2, 99) + GCD(2, 100) + + ... + ... + GCD(98, 100) + GCD(99, 100) + +The answer for this case is `13015`; it will be our password that confirms that the person we speak to understood us clearly even if we spoke a foreign language. + +# Solutions + +The solutions are grouped into two parts. In the first group, either a built-in or a library function is used to compute the greatest common divisor. In the second group, the algorithm is implemented directly in the program. In each section, the solutions are listed in the order in which I solved them. + +All the programs can be run from the command line and accept the value of `$N` as the first parameter. If the number is missing, the default value `3` is used. The result of the program is always a single number printed in the console. You can see instructions of how to run the program exactly in the comment at the beginning of each program. + +## Using built-in or library functions for GCD + +1. [Raku](#1-raku) +1. [Python](#2-python) +1. [C++ (C++17)](#3-c-++) +1. [Perl](#4-perl) +1. [Ruby](#5-ruby) +1. [Scala](#6-scala) +1. [C#](#7-c) +1. [Dart](#8-dart) +1. [Julia](#9-julia) +1. [D](#10-d) +1. [Lisp (SBCL)](#11-lisp) + +## With a custom implementation of GCD + +1. [C](#12-c) +1. [JavaScript (node.js)](#13-JavaScript) +1. [Java](#14-java) +1. [Rust](#15-rust) +1. [Pascal (FreePascal)](#16-pascal) +1. [Go](#17-go) +1. [Lua](#18-lua) +1. [Fortran (Fortran 95)](#19-fortran) +1. [PHP](#20-php) +1. [Kotlin](#21-kotlin) +1. [Bash](#22-bash) + +## Part 1 + +### 1. Raku + +In Raku, we’ve got all the things required for a compact solution. Actually, the most compact among all the solutions below. So, we’ve got the [`combinations` method](https://docs.raku.org/routine/combinations) to convert a range into unique pairs of numbers and the built-in [`gcd` routine](https://docs.raku.org/routine/gcd). We also have the pleasure to use [reduction operators](https://docs.raku.org/language/operators#index-entry-[]_(reduction_metaoperators)) `[ ... ]` even if they can be easily replaced. For example, the first usage of it `[+]` can be replaced with the call of `sum`, and the second `[gcd] $_` with something like `$_[0] gcd $_[1]`. By the way, notice that in Raku, `gcd` is an infix operator, so you use it in the form of `$a gcd $b` and not as a function `gcd($a, $b)`. + + # Test run: + # $ raku ch-1.raku 100 + # 13015 + + my $n = @*ARGS[0] // 3; + + say [+] (1..$n).combinations(2).map: {[gcd] $_}; + +### 2. Python + +In Python, there’s no built-in `gcd` or `combinations`, but both are available in the standard library. For diversity, I used `math.gcd` but implemented the combination creation with two nested `for` loops. The first loop iterates over the whole range between `1` and `$N`, while the inner loop starts with the current value of the outer loop. + + # Test run: + # $ python3 ch-1.py 100 + # 13015 + + import sys, math + + n = 3 if len(sys.argv) == 1 else int(sys.argv[1]) + + s = 0 + for x in range(1, n + 1): + for y in range(x + 1, n + 1): + s += math.gcd(x, y) + + print(s) + + +### 3. C++ + +Here is a solution in C++. As the author of the language says, ‘C++ feels like a new language’, and even in this simple task, we can use the [library function `gcd`](https://en.cppreference.com/w/cpp/numeric/gcd) that is available since the standard C++17. + +In the rest, the program also includes two nested loops and accumulates the sum for each combination. + + // Compile as: + // $ g++ -std=c++17 ch-1.cpp + + // Test run: + // $ ./a.out 100 + // 13015 + + #include + #include + #include + + using namespace std; + + int main(int argc, char** argv) { + int n = 3; + if (argc != 1) { + stringstream input(argv[1]); + input >> n; + } + + int s = 0; + for (int x = 1; x <= n; x++) { + for (int y = x + 1; y <= n; y++) { + s += gcd(x, y); + } + } + + cout << s << endl; + } + +### 4. Perl + +Good old modern and future Perl is here! As, among the rest, it is famous for CPAN, let us use a [module `Math::Utils`](https://metacpan.org/pod/Math::Utils) from there. Actually, this is the only solution where I use a module that is not available in the default installation. + + # To run, install Math::Utils first: + # $ cpanm Math::Utils + # $ perl ch-1.pl 100 + # 13015 + + use v5.20; + + use Math::Utils qw(gcd); + + my $n = $ARGV[0] // 3; + + my $s = 0; + for my $x (1 .. $n) { + for my $y ($x + 1 .. $n) { + $s += gcd($x, $y); + } + } + + say $s; + +### 5. Ruby + +The program in Ruby is also quite compact, I would say. Notice how the `gcd` method is used here: `x.gcd(y)`. It is indeed is _a method,_ and it is called on one of the numbers. We’ll see more examples of such approach later. + + # Usage: + # $ ruby ch-1.rb 100 + # 13015 + + n = ARGV.length == 1 ? ARGV[0].to_i : 3 + + s = 0 + for x in 1 .. n + for y in x + 1 .. n + s += x.gcd(y) + end + end + + puts s + +### 6. Scala + +In Scala, we have to deal with Java’s legacy and create a class to start the day. But nevertheless, the program is not that big. What you may want to enjoy is possibly the syntax of loop headers: `for (x <- 1 to n)` with the left arrow. Also notice that the `gcd` routine is again a method, and it’s a method defined for `BigInt`s: `BigInt(x).gcd(y)`. + + /* + To run: + $ scala ch-1.scala 100 + 13015 + */ + + import math.BigInt + + object Main { + def main(args: Array[String]): Unit = { + var n: Int = if (args.size == 1) args(0).toInt else 3 + + var s: BigInt = 0 + for (x <- 1 to n) { + for (y <- x + 1 to n) { + s = s + BigInt(x).gcd(y) + } + } + + println(s) + } + } + +### 7. C# + +Here is the solution in C#. Welcome to the world of .NET, where many things are clearly spelt out: `BigInteger.GreatestCommonDivisor(x, y)`. In the rest, here we have the same two nested loops that build the pair of combinations. + + // Compile and run on a Mac: + // $ csc -r:System.Numerics.dll ch-1.cs + // $ mono ch-1.exe 100 + // 13015 + + using System; + using System.Numerics; + + class Program { + static int Main(string[] args) + { + int n = 3; + if (args.Length == 1) n = int.Parse(args[0]); + + var s = new BigInteger(0); + for (int x = 1; x <= n; x++) { + for (int y = x + 1; y <= n; y++) { + s += BigInteger.GreatestCommonDivisor(x, y); + } + } + + System.Console.WriteLine(s); + + return 0; + } + } + +### 8. Dart + +To me, languages built on C++ have their specific charm. On one side, it is the same known language, but on the other, it embeds the things that you were missing earlier (see, for example, how easy it is to deal with command-line arguments). The `gcd` here is again a method called on a number: `x.gcd(y)`. + + // To run: + // $ dart ch-1.dart 100 + // 13015 + + void main(List args) { + var n = 3; + if (args.length == 1) + n = int.parse(args[0]); + + var s = 0; + for (var x = 1; x <= n; x++) { + for (var y = x + 1; y <= n; y++) { + s += x.gcd(y); + } + } + + print(s); + } + +### 9. Julia + +Julia is another interesting language that actually has many similarities with Raku. For our today’s need, there’s a built-in `gcd` function that I am happily using. The only unexpected obstacle is, maybe, the need to explicitly refer to the accumulator `s` as to a `global` variable. + + # To run: + # $ julia ch-1.julia 100 + # 13015 + + n = length(ARGS) == 1 ? parse(Int, ARGS[1]) : 3 + + s = 0 + for x in range(1, stop = n) + for y in range(x + 1, stop = n) + global s + s += gcd(x, y) + end + end + + println(s) + + +### 10. D + +Acter C comes D. And here we are. In the program, you can see extensive use of the `auto` declarator. I believe, the situation here resembles how some elements of Raku entered back in Perl, even if Raku was a continuation of Perl historically. Similarly, `auto` is now available in C++ too (while you need to practice not to forget to use `auto` automatically). + + // How to run: + // $ rdmd ch1.d 100 + // 13015 + + import std.stdio; + import std.numeric; + import std.conv; + + void main(string[] args) { + auto n = args.length == 2 ? to!int(args[1]) : 3; + + auto s = 0; + for (auto x = 1; x <= n; x++) { + for (auto y = x + 1; y <= n; y++) { + s += gcd(x, y); + } + } + + writeln(s); + } + +### 11. Lisp + +Move on to a different world (for a bit). Here is the solution in a functional programming language. Well, Common Lisp adds some syntax sugar to help us build loops without manually manipulating loop counters and recursive calls. In any case, it also has the built-in `gcd` function, which, of course, you call as `(gcd x y)`. The below program works with the SBCL implementation (mostly because of how it reads the command-line arguments). + + ;;; How to run: + ;;; $ sbcl --script ch-1.lisp 100 + ;;; + ;;; 13015 + + (defvar n (parse-integer (nth 1 *posix-argv*))) + + (defvar s 0) + + (loop for x from 1 to n + do ( + loop for y from (+ 1 x) to n + do (setq s (+ s (gcd x y))) + ) + ) + + (print s) + (terpri) + +## Part 2 + +### 12. C + +OK, and now we start the second part of the solutions list. Now, the GCD algorithm is implemented directly in the program itself. Refer to this implementation in C; this algorithm is used in all other solutions below. + + int gcd(int a, int b) { + while (b) { + int t = b; + b = a % b; + a = t; + } + + return a; + } + +It is important to say that due to the loop organisation, we always call this function with such arguments that `b` is always bigger than `a`, so you don’t have to care about other cases. + +So, here is the complete program in C: + + /* + Compile: + $ gcc ch-1.c + + Test run: + $ ./a.out 100 + 13015 + */ + + #include + #include + + int gcd(int a, int b) { + while (b) { + int t = b; + b = a % b; + a = t; + } + + return a; + } + + int main(int argc, char** argv) { + int n = 3; + if (argc != 1) { + n = atoi(argv[1]); + } + + int s = 0; + for (int x = 1; x <= n; x++) { + for (int y = x + 1; y <= n; y++) { + s += gcd(x, y); + } + } + + printf("%i\n", s); + } + +### 13. JavaScript + +A Node.js slash JavaScript program is here for your further entertainment. It resembles a lot the previously shown C program. A similar pair of nested loops, and a similar implementation of `gcd`. Could you imagine 10-15 years ago that you would be able to run a JS program from command line? + + // Test run: + // $ node ch-1.js 100 + // 13015 + + let n = process.argv.length == 3 ? process.argv[2] : 3; + + let s = 0; + for (let x = 1; x <= n; x++) { + for (let y = x + 1; y <= n; y++) { + s += gcd(x, y); + } + } + + console.log(s); + + function gcd(a, b) { + while (b) { + let t = b; + b = a % b; + a = t; + } + + return a; + } + +### 14. Java + +Now, look at the solution in Java. Yes, we have to use classes again, but in the rest, a nice and clean program that doesn’t require many more comments, I think. + + // To run: + // $ java ch-1.java 100 + // 13015 + + class Main { + static int gcd(int a, int b) { + while (b != 0) { + int t = b; + b = a % b; + a = t; + } + + return a; + } + + public static void main(String[] args) { + int n = args.length == 1 ? Integer.parseInt(args[0]) : 3; + + int s = 0; + for (int x = 1; x <= n; x++) { + for (int y = x + 1; y <= n; y++) { + s += gcd(x, y); + } + } + + System.out.println(s); + } + } + +### 15. Rust + +The program in Rust is an interesting combination of elements that we are familiar with from both C, JavaScript, and even Perl and Raku (for example, ranges `..`). Also, a nice addition of built-in type system, and maybe an unusual concept of macros — those ‘functions’ with an exclamation mark in their name such as `println!`. + + // To compile and run: + // $ rustc ch-1.rs + // $ ./ch-1 100 + // 13015 + + use std::env; + + fn gcd(a: u32, b: u32) -> u32 { + let mut x = a; + let mut y = b; + + while y != 0 { + let t = y; + y = x % y; + x = t; + } + + return x; + } + + fn main() { + let args: Vec = env::args().collect(); + + let n; + if args.len() == 2 { + n = args[1].parse().unwrap(); + } + else { + n = 3; + } + + let mut s = 0; + for x in 1 .. (n + 1) { + for y in (x + 1) .. (n + 1) { + s += gcd(x, y); + } + } + + println!("{}", s); + } + +### 16. Pascal + +I have a question for you. When did you program in Pascal last time? My answer is ‘Something like 30 years ago’. But honestly, that nostalgic mood is a great thing for the evenings around Christmas time. And while there’s no `gcd` built in, you can implement it yourself if you remember to use `<>` instead of `!=` and a single `=` in comparisons: `if paramCount() = 0 then`. I also struggled a bit with semicolons, for example, no semicolon allowed before `else`. + + (* + To compile and run: + $ fpc ch-1.pas + $ ./ch-1 100 + 13015 + *) + + program Hello(input, output); + + uses sysutils; + + var + n, x, y, s: integer; + + function gcd(a, b: integer): integer; + var + t: integer; + begin + while b <> 0 do begin + t := b; + b := a mod b; + a := t; + end; + + gcd := a + end; + + begin + if paramCount() = 0 then + n := 3 + else + n := StrToInt(paramStr(1)); + + s := 0; + for x := 1 to n do + for y := x + 1 to n do + s += gcd(x, y); + + writeln(s); + end. + +### 17. Go + +And now fast forward to the present days. Here is Go with its strict requirements not to leave garbage in the code and use all variables and imported modules. Notice that I used multiple assignments and avoided a temporary variable in the implementation of `gcd`: `b, a = a%b, b`. Heh, and the Go standard formatter removed my spaces around the `%` operator. + + // To compile and run: + // $ go run ch-1.go 100 + // 13015 + + package main + + import ( + "fmt" + "os" + "strconv" + ) + + func gcd(a, b int) int { + for b != 0 { + b, a = a%b, b + } + + return a + } + + func main() { + n := 3 + if len(os.Args) == 2 { + n, _ = strconv.Atoi(os.Args[1]) + } + + s := 0 + for x := 1; x <= n; x++ { + for y := x + 1; y <= n; y++ { + s += gcd(x, y) + } + } + + fmt.Println(s) + } + +### 18. Lua + +Lua is the language that is loved by many people, and I believe there are many cases when its design with tables can be beneficial in many applications. For our practice, I used the standard approach: a few loops, and it’s done. I would still point your attention to the following line: `n = arg[1] and arg[1] or 3`, which is actually a ternary construction to assign the default value if the argument is missing. + + -- How to run: + -- $ lua ch-1.lua 100 + -- 13015 + + function gcd(a, b) + while b > 0 do + t = b + b = a % b + a = t + end + + return a + end + + n = arg[1] and arg[1] or 3 + + s = 0 + for x = 1, n do + for y = x + 1, n do + s = s + gcd(x, y) + end + end + + print(s) + +### 19. Fortran + +Going further to some science-related language. For a long time, Fortran was the language in which tons of algorithms were encoded for physics and mathematics. I believe it would be very beneficial to use this as the language to teach students (OK, consider that a joke with some elements of truth) :-) What would be really interesting is to browse into some sophisticated algorithms written decades ago — many of them may be unexpectedly efficient. + + ! To compile and run: + ! + ! $ gfortran ch-1.f95 + ! $ ./a.out 100 + ! 13015 + + function mygcd(a, b) result(x) + integer, intent(in) :: a, b + integer :: x, y, t + + x = a + y = b + + do while (y /= 0) + t = y + y = mod(x, y) + x = t + end do + end function + + program hello + integer :: n, x, y, s + + character(len=20) :: arg + character(len=20) :: nstr + + if (iargc() == 1) then + call getarg(1, nstr) + read(nstr,*) n + else + n = 3 + end if + + s = 0 + do x = 1, n + do y = x + 1, n + s = s + mygcd(x, y) + end do + end do + + write(*,*) s + end program + +### 20. PHP + +Let me introduce another solution with sigils, which, as you may see, is not too frequent part among the languages. Perl, Raku, PHP, and Bash in this list do use them though. I believe, if you are familiar with either Perl or Raku, you can understand every bit of this program in PHP (yeah, and no `my` declarators). + + + +### 21. Kotlin + +In the program in Kotlin, we see the use of typed variables, C-like functions and...double-dot ranges! What a surprise for the Perl and Raku lovers again. + + // How to run: + // $ kotlinc ch-1.kt -include-runtime -d ch1.jar + // $ java -jar ch1.jar 100 + // 13015 + + fun gcd(a: Int, b: Int): Int { + var x = a + var y = b + + while (y != 0) { + val t = y + y = x % y + x = t + } + + return x + } + + fun main(args: Array) { + var n: Int + if (args.size == 1) + n = args[0].toInt() + else + n = 3 + + var s = 0 + for (x in 1..n) { + for (y in x + 1 .. n) { + s += gcd(x, y) + } + } + + println(s) + } + +### 22. Bash + +And the last program on this page. At this point, I could add a poll to ask if you consider Bash a programming language or not. Honestly, I did not think it would be possible to solve today’s problem in Bash, but as you see, the result is not that much more complicated than the solutions in other languages. Enjoy it too! + + #!/usr/bin/bash + + # Usage: + # $ bash ch-1.bash 100 + # 13015 + # + # N. B. Try with smaller arguments, as the computations + # for 100 as the input can take a while (~ a minute). + + gcd() { + a=$1; + b=$2; + while [ $b -ne 0 ]; do + t=$b + b=`expr $a % $b` + a=$t + done + + gcd=$a + } + + n=${1:-3} # default is 3 + + s=0 + x=1 + while [ $x -le $n ]; do + next=`expr $x + 1`; + y=$next; + while [ $y -le $n ]; do + y=`expr $y + 1`; + gcd $x $y; + s=`expr $s + $gcd`; + done + x=$next; + done + + echo $s + +And that’s it for today. Tomorrow, there’s another post in this Advent Calendar, but don’t forget that there are more calendars this year, and there are more Weekly Challenges coming soon! diff --git a/challenge-089/ash/lisp/ch-1.lisp b/challenge-089/ash/lisp/ch-1.lisp index 4bcdcceb36..ffa62769dd 100644 --- a/challenge-089/ash/lisp/ch-1.lisp +++ b/challenge-089/ash/lisp/ch-1.lisp @@ -10,7 +10,7 @@ (loop for x from 1 to n do ( loop for y from (+ 1 x) to n - do (setq s (+ s (gcd x y))) + do (setq s (+ s (gcd x y))) ) ) diff --git a/challenge-089/ash/readme.md b/challenge-089/ash/readme.md index e21127020f..dd1b8fa592 100644 --- a/challenge-089/ash/readme.md +++ b/challenge-089/ash/readme.md @@ -4,28 +4,30 @@ Implemenations of [Problem 1 of Week 89](https://perlweeklychallenge.org/blog/pe ## Using built-in or library functions for GCD -1. [Raku](raku/ch-1.raku) -1. [Python](python/ch-1.py) -1. [C++ (C++17)](cpp/ch-1.cpp) -1. [Perl](perl/ch-1.pl) -1. [Ruby](ruby/ch-1.rb) -1. [Lua](lua/ch-1.lua) -1. [Scala](scala/ch-1.scala) -1. [C#](csharp/ch-1.cs) -1. [Dart](dart/ch-1.dart) -1. [Julia](julia/ch-1.julia) -1. [D](d/ch1.d) -1. [Lisp (SBCL)](lisp/ch-1.lisp) +1. [Raku](ch-1.raku) +1. [Python](ch-1.py) +1. [C++ (C++17)](ch-1.cpp) +1. [Perl](ch-1.pl) +1. [Ruby](ch-1.rb) +1. [Scala](ch-1.scala) +1. [C#](ch-1.cs) +1. [Dart](ch-1.dart) +1. [Julia](ch-1.julia) +1. [D](ch1.d) +1. [Lisp (SBCL)](ch-1.lisp) ## With a custom implementation of GCD -1. [C](c/ch-1.c) -1. [node.js (JavaScript)](javascript/ch-1.js) -1. [Java](java/ch-1.java) -1. [Rust](rust/ch-1.rs) -1. [Pascal (FreePascal)](pascal/ch-1.pas) -1. [Go](go/ch-1.go) -1. [Fortran (Fortran 95)](fortran/ch-1.f95) -1. [PHP](php/ch-1.php) -1. [Kotlin](kotlin/ch-1.kt) -1. [Bash](bash/ch-1.bash) +1. [C](ch-1.c) +1. [node.js (JavaScript)](ch-1.js) +1. [Java](ch-1.java) +1. [Rust](ch-1.rs) +1. [Pascal (FreePascal)](ch-1.pas) +1. [Go](ch-1.go) +1. [Lua](ch-1.lua) +1. [Fortran (Fortran 95)](ch-1.f95) +1. [PHP](ch-1.php) +1. [Kotlin](ch-1.kt) +1. [Bash](ch-1.bash) + +Also read a [big article](index.md) about all the solutions and the task. -- cgit From 2628416383fa0a5d4b372853c32b9b7225c7e8f5 Mon Sep 17 00:00:00 2001 From: Andrew Shitov Date: Fri, 4 Dec 2020 17:03:25 +0100 Subject: fix link --- challenge-089/ash/index.md | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/challenge-089/ash/index.md b/challenge-089/ash/index.md index 38ba73df6a..1082ae5adf 100644 --- a/challenge-089/ash/index.md +++ b/challenge-089/ash/index.md @@ -23,7 +23,7 @@ All the programs can be run from the command line and accept the value of `$N` a 1. [Raku](#1-raku) 1. [Python](#2-python) -1. [C++ (C++17)](#3-c-++) +1. [C++ (C++17)](#3-c) 1. [Perl](#4-perl) 1. [Ruby](#5-ruby) 1. [Scala](#6-scala) -- cgit From 76b651cc674201b9dd49be770e6ae27246eceae0 Mon Sep 17 00:00:00 2001 From: Andrew Shitov Date: Fri, 4 Dec 2020 18:30:41 +0100 Subject: fix filename extension --- challenge-089/ash/julia/ch-1.jl | 15 +++++++++++++ challenge-089/ash/julia/ch-1.julia | 15 ------------- challenge-089/ash/readme.md | 44 +++++++++++++++++++------------------- 3 files changed, 37 insertions(+), 37 deletions(-) create mode 100644 challenge-089/ash/julia/ch-1.jl delete mode 100644 challenge-089/ash/julia/ch-1.julia diff --git a/challenge-089/ash/julia/ch-1.jl b/challenge-089/ash/julia/ch-1.jl new file mode 100644 index 0000000000..22f30004b4 --- /dev/null +++ b/challenge-089/ash/julia/ch-1.jl @@ -0,0 +1,15 @@ +# To run: +# $ julia ch-1.julia 100 +# 13015 + +n = length(ARGS) == 1 ? parse(Int, ARGS[1]) : 3 + +s = 0 +for x in range(1, stop = n) + for y in range(x + 1, stop = n) + global s + s += gcd(x, y) + end +end + +println(s) diff --git a/challenge-089/ash/julia/ch-1.julia b/challenge-089/ash/julia/ch-1.julia deleted file mode 100644 index 22f30004b4..0000000000 --- a/challenge-089/ash/julia/ch-1.julia +++ /dev/null @@ -1,15 +0,0 @@ -# To run: -# $ julia ch-1.julia 100 -# 13015 - -n = length(ARGS) == 1 ? parse(Int, ARGS[1]) : 3 - -s = 0 -for x in range(1, stop = n) - for y in range(x + 1, stop = n) - global s - s += gcd(x, y) - end -end - -println(s) diff --git a/challenge-089/ash/readme.md b/challenge-089/ash/readme.md index dd1b8fa592..b4cc9eb301 100644 --- a/challenge-089/ash/readme.md +++ b/challenge-089/ash/readme.md @@ -4,30 +4,30 @@ Implemenations of [Problem 1 of Week 89](https://perlweeklychallenge.org/blog/pe ## Using built-in or library functions for GCD -1. [Raku](ch-1.raku) -1. [Python](ch-1.py) -1. [C++ (C++17)](ch-1.cpp) -1. [Perl](ch-1.pl) -1. [Ruby](ch-1.rb) -1. [Scala](ch-1.scala) -1. [C#](ch-1.cs) -1. [Dart](ch-1.dart) -1. [Julia](ch-1.julia) -1. [D](ch1.d) -1. [Lisp (SBCL)](ch-1.lisp) +1. [Raku](raku/ch-1.raku) +1. [Python](python/ch-1.py) +1. [C++ (C++17)](cpp/ch-1.cpp) +1. [Perl](perl/ch-1.pl) +1. [Ruby](ruby/ch-1.rb) +1. [Scala](scala/ch-1.scala) +1. [C#](csharp/ch-1.cs) +1. [Dart](dart/ch-1.dart) +1. [Julia](julia/ch-1.jl) +1. [D](d/ch1.d) +1. [Lisp (SBCL)](lisp/ch-1.lisp) ## With a custom implementation of GCD -1. [C](ch-1.c) -1. [node.js (JavaScript)](ch-1.js) -1. [Java](ch-1.java) -1. [Rust](ch-1.rs) -1. [Pascal (FreePascal)](ch-1.pas) -1. [Go](ch-1.go) -1. [Lua](ch-1.lua) -1. [Fortran (Fortran 95)](ch-1.f95) -1. [PHP](ch-1.php) -1. [Kotlin](ch-1.kt) -1. [Bash](ch-1.bash) +1. [C](c/ch-1.c) +1. [node.js (JavaScript)](javascript/ch-1.js) +1. [Java](java/ch-1.java) +1. [Rust](rust/ch-1.rs) +1. [Pascal (FreePascal)](pascal/ch-1.pas) +1. [Go](go/ch-1.go) +1. [Lua](lua/ch-1.lua) +1. [Fortran (Fortran 95)](fortran/ch-1.f95) +1. [PHP](php/ch-1.php) +1. [Kotlin](kotlin/ch-1.kt) +1. [Bash](bash/ch-1.bash) Also read a [big article](index.md) about all the solutions and the task. -- cgit From 3e52554432838b88a13f0ed92506162984c50b09 Mon Sep 17 00:00:00 2001 From: Andrew Shitov Date: Fri, 4 Dec 2020 18:32:16 +0100 Subject: fix run instruction --- challenge-089/ash/julia/ch-1.jl | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/challenge-089/ash/julia/ch-1.jl b/challenge-089/ash/julia/ch-1.jl index 22f30004b4..c24b280740 100644 --- a/challenge-089/ash/julia/ch-1.jl +++ b/challenge-089/ash/julia/ch-1.jl @@ -1,5 +1,5 @@ # To run: -# $ julia ch-1.julia 100 +# $ julia ch-1.jl 100 # 13015 n = length(ARGS) == 1 ? parse(Int, ARGS[1]) : 3 -- cgit From f055931d386b70c7153d1736a6ebdd29f0456e0a Mon Sep 17 00:00:00 2001 From: Andrew Shitov Date: Fri, 4 Dec 2020 18:33:26 +0100 Subject: fix run instruction --- challenge-089/ash/index.md | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/challenge-089/ash/index.md b/challenge-089/ash/index.md index 1082ae5adf..e0862060db 100644 --- a/challenge-089/ash/index.md +++ b/challenge-089/ash/index.md @@ -246,7 +246,7 @@ To me, languages built on C++ have their specific charm. On one side, it is the Julia is another interesting language that actually has many similarities with Raku. For our today’s need, there’s a built-in `gcd` function that I am happily using. The only unexpected obstacle is, maybe, the need to explicitly refer to the accumulator `s` as to a `global` variable. # To run: - # $ julia ch-1.julia 100 + # $ julia ch-1.jl 100 # 13015 n = length(ARGS) == 1 ? parse(Int, ARGS[1]) : 3 -- cgit From ebbc057eb000e3929024be56ae4e737c78678a39 Mon Sep 17 00:00:00 2001 From: Andrew Shitov Date: Sat, 5 Dec 2020 09:27:39 +0100 Subject: Syntax highlighting --- challenge-089/ash/index.md | 990 ++++++++++++++++++++++++--------------------- 1 file changed, 518 insertions(+), 472 deletions(-) diff --git a/challenge-089/ash/index.md b/challenge-089/ash/index.md index e0862060db..da00e5affb 100644 --- a/challenge-089/ash/index.md +++ b/challenge-089/ash/index.md @@ -53,33 +53,36 @@ All the programs can be run from the command line and accept the value of `$N` a In Raku, we’ve got all the things required for a compact solution. Actually, the most compact among all the solutions below. So, we’ve got the [`combinations` method](https://docs.raku.org/routine/combinations) to convert a range into unique pairs of numbers and the built-in [`gcd` routine](https://docs.raku.org/routine/gcd). We also have the pleasure to use [reduction operators](https://docs.raku.org/language/operators#index-entry-[]_(reduction_metaoperators)) `[ ... ]` even if they can be easily replaced. For example, the first usage of it `[+]` can be replaced with the call of `sum`, and the second `[gcd] $_` with something like `$_[0] gcd $_[1]`. By the way, notice that in Raku, `gcd` is an infix operator, so you use it in the form of `$a gcd $b` and not as a function `gcd($a, $b)`. - # Test run: - # $ raku ch-1.raku 100 - # 13015 +```perl +# Test run: +# $ raku ch-1.raku 100 +# 13015 - my $n = @*ARGS[0] // 3; +my $n = @*ARGS[0] // 3; - say [+] (1..$n).combinations(2).map: {[gcd] $_}; +say [+] (1..$n).combinations(2).map: {[gcd] $_}; +``` ### 2. Python In Python, there’s no built-in `gcd` or `combinations`, but both are available in the standard library. For diversity, I used `math.gcd` but implemented the combination creation with two nested `for` loops. The first loop iterates over the whole range between `1` and `$N`, while the inner loop starts with the current value of the outer loop. - # Test run: - # $ python3 ch-1.py 100 - # 13015 +```python +# Test run: +# $ python3 ch-1.py 100 +# 13015 - import sys, math +import sys, math - n = 3 if len(sys.argv) == 1 else int(sys.argv[1]) +n = 3 if len(sys.argv) == 1 else int(sys.argv[1]) - s = 0 - for x in range(1, n + 1): - for y in range(x + 1, n + 1): - s += math.gcd(x, y) - - print(s) +s = 0 +for x in range(1, n + 1): + for y in range(x + 1, n + 1): + s += math.gcd(x, y) +print(s) +``` ### 3. C++ @@ -87,228 +90,247 @@ Here is a solution in C++. As the author of the language says, ‘C++ feels like In the rest, the program also includes two nested loops and accumulates the sum for each combination. - // Compile as: - // $ g++ -std=c++17 ch-1.cpp +```cpp +// Compile as: +// $ g++ -std=c++17 ch-1.cpp - // Test run: - // $ ./a.out 100 - // 13015 +// Test run: +// $ ./a.out 100 +// 13015 - #include - #include - #include +#include +#include +#include - using namespace std; +using namespace std; - int main(int argc, char** argv) { - int n = 3; - if (argc != 1) { - stringstream input(argv[1]); - input >> n; - } +int main(int argc, char** argv) { + int n = 3; + if (argc != 1) { + stringstream input(argv[1]); + input >> n; + } - int s = 0; - for (int x = 1; x <= n; x++) { - for (int y = x + 1; y <= n; y++) { - s += gcd(x, y); - } + int s = 0; + for (int x = 1; x <= n; x++) { + for (int y = x + 1; y <= n; y++) { + s += gcd(x, y); } - - cout << s << endl; } + cout << s << endl; +} +``` + ### 4. Perl Good old modern and future Perl is here! As, among the rest, it is famous for CPAN, let us use a [module `Math::Utils`](https://metacpan.org/pod/Math::Utils) from there. Actually, this is the only solution where I use a module that is not available in the default installation. - # To run, install Math::Utils first: - # $ cpanm Math::Utils - # $ perl ch-1.pl 100 - # 13015 +```perl +# To run, install Math::Utils first: +# $ cpanm Math::Utils +# $ perl ch-1.pl 100 +# 13015 - use v5.20; +use v5.20; - use Math::Utils qw(gcd); +use Math::Utils qw(gcd); - my $n = $ARGV[0] // 3; +my $n = $ARGV[0] // 3; - my $s = 0; - for my $x (1 .. $n) { - for my $y ($x + 1 .. $n) { - $s += gcd($x, $y); - } +my $s = 0; +for my $x (1 .. $n) { + for my $y ($x + 1 .. $n) { + $s += gcd($x, $y); } +} - say $s; +say $s; +``` ### 5. Ruby The program in Ruby is also quite compact, I would say. Notice how the `gcd` method is used here: `x.gcd(y)`. It is indeed is _a method,_ and it is called on one of the numbers. We’ll see more examples of such approach later. - # Usage: - # $ ruby ch-1.rb 100 - # 13015 +```ruby +# Usage: +# $ ruby ch-1.rb 100 +# 13015 - n = ARGV.length == 1 ? ARGV[0].to_i : 3 +n = ARGV.length == 1 ? ARGV[0].to_i : 3 - s = 0 - for x in 1 .. n - for y in x + 1 .. n - s += x.gcd(y) - end +s = 0 +for x in 1 .. n + for y in x + 1 .. n + s += x.gcd(y) end +end - puts s +puts s +``` ### 6. Scala In Scala, we have to deal with Java’s legacy and create a class to start the day. But nevertheless, the program is not that big. What you may want to enjoy is possibly the syntax of loop headers: `for (x <- 1 to n)` with the left arrow. Also notice that the `gcd` routine is again a method, and it’s a method defined for `BigInt`s: `BigInt(x).gcd(y)`. - /* - To run: - $ scala ch-1.scala 100 - 13015 - */ - - import math.BigInt - - object Main { - def main(args: Array[String]): Unit = { - var n: Int = if (args.size == 1) args(0).toInt else 3 - - var s: BigInt = 0 - for (x <- 1 to n) { - for (y <- x + 1 to n) { - s = s + BigInt(x).gcd(y) - } - } +```scala +/* + To run: + $ scala ch-1.scala 100 + 13015 +*/ + +import math.BigInt - println(s) +object Main { + def main(args: Array[String]): Unit = { + var n: Int = if (args.size == 1) args(0).toInt else 3 + + var s: BigInt = 0 + for (x <- 1 to n) { + for (y <- x + 1 to n) { + s = s + BigInt(x).gcd(y) + } } + + println(s) } +} +``` ### 7. C# Here is the solution in C#. Welcome to the world of .NET, where many things are clearly spelt out: `BigInteger.GreatestCommonDivisor(x, y)`. In the rest, here we have the same two nested loops that build the pair of combinations. - // Compile and run on a Mac: - // $ csc -r:System.Numerics.dll ch-1.cs - // $ mono ch-1.exe 100 - // 13015 +```csharp +// Compile and run on a Mac: +// $ csc -r:System.Numerics.dll ch-1.cs +// $ mono ch-1.exe 100 +// 13015 - using System; - using System.Numerics; - - class Program { - static int Main(string[] args) - { - int n = 3; - if (args.Length == 1) n = int.Parse(args[0]); - - var s = new BigInteger(0); - for (int x = 1; x <= n; x++) { - for (int y = x + 1; y <= n; y++) { - s += BigInteger.GreatestCommonDivisor(x, y); - } - } - - System.Console.WriteLine(s); +using System; +using System.Numerics; - return 0; +class Program { + static int Main(string[] args) + { + int n = 3; + if (args.Length == 1) n = int.Parse(args[0]); + + var s = new BigInteger(0); + for (int x = 1; x <= n; x++) { + for (int y = x + 1; y <= n; y++) { + s += BigInteger.GreatestCommonDivisor(x, y); + } } + + System.Console.WriteLine(s); + + return 0; } +} +``` ### 8. Dart To me, languages built on C++ have their specific charm. On one side, it is the same known language, but on the other, it embeds the things that you were missing earlier (see, for example, how easy it is to deal with command-line arguments). The `gcd` here is again a method called on a number: `x.gcd(y)`. - // To run: - // $ dart ch-1.dart 100 - // 13015 +```rust +// To run: +// $ dart ch-1.dart 100 +// 13015 - void main(List args) { - var n = 3; - if (args.length == 1) - n = int.parse(args[0]); +void main(List args) { + var n = 3; + if (args.length == 1) + n = int.parse(args[0]); - var s = 0; - for (var x = 1; x <= n; x++) { - for (var y = x + 1; y <= n; y++) { - s += x.gcd(y); - } + var s = 0; + for (var x = 1; x <= n; x++) { + for (var y = x + 1; y <= n; y++) { + s += x.gcd(y); } - - print(s); } + print(s); +} +``` + ### 9. Julia Julia is another interesting language that actually has many similarities with Raku. For our today’s need, there’s a built-in `gcd` function that I am happily using. The only unexpected obstacle is, maybe, the need to explicitly refer to the accumulator `s` as to a `global` variable. - # To run: - # $ julia ch-1.jl 100 - # 13015 +```julia +# To run: +# $ julia ch-1.jl 100 +# 13015 - n = length(ARGS) == 1 ? parse(Int, ARGS[1]) : 3 +n = length(ARGS) == 1 ? parse(Int, ARGS[1]) : 3 - s = 0 - for x in range(1, stop = n) - for y in range(x + 1, stop = n) - global s - s += gcd(x, y) - end +s = 0 +for x in range(1, stop = n) + for y in range(x + 1, stop = n) + global s + s += gcd(x, y) end +end - println(s) - +println(s) +``` ### 10. D Acter C comes D. And here we are. In the program, you can see extensive use of the `auto` declarator. I believe, the situation here resembles how some elements of Raku entered back in Perl, even if Raku was a continuation of Perl historically. Similarly, `auto` is now available in C++ too (while you need to practice not to forget to use `auto` automatically). - // How to run: - // $ rdmd ch1.d 100 - // 13015 - - import std.stdio; - import std.numeric; - import std.conv; - - void main(string[] args) { - auto n = args.length == 2 ? to!int(args[1]) : 3; - - auto s = 0; - for (auto x = 1; x <= n; x++) { - for (auto y = x + 1; y <= n; y++) { - s += gcd(x, y); - } +```d +// How to run: +// $ rdmd ch1.d 100 +// 13015 + +import std.stdio; +import std.numeric; +import std.conv; + +void main(string[] args) { + auto n = args.length == 2 ? to!int(args[1]) : 3; + + auto s = 0; + for (auto x = 1; x <= n; x++) { + for (auto y = x + 1; y <= n; y++) { + s += gcd(x, y); } - - writeln(s); } + writeln(s); +} +``` + ### 11. Lisp -Move on to a different world (for a bit). Here is the solution in a functional programming language. Well, Common Lisp adds some syntax sugar to help us build loops without manually manipulating loop counters and recursive calls. In any case, it also has the built-in `gcd` function, which, of course, you call as `(gcd x y)`. The below program works with the SBCL implementation (mostly because of how it reads the command-line arguments). +Move on to a different world (for a bit). Here is the solution in a functional programming language. Well, Common Lisp adds some syntax sugar to help us build loops without manually manipulating loop counters and recursive calls. (Not to say about `setq` that sets the new value of a variable.) + +In any case, it also has the built-in `gcd` function, which, of course, you call as `(gcd x y)`. The below program works with the SBCL implementation (mostly because of how it reads the command-line arguments). - ;;; How to run: - ;;; $ sbcl --script ch-1.lisp 100 - ;;; - ;;; 13015 +```lisp +;;; How to run: +;;; $ sbcl --script ch-1.lisp 100 +;;; +;;; 13015 - (defvar n (parse-integer (nth 1 *posix-argv*))) +(defvar n (parse-integer (nth 1 *posix-argv*))) - (defvar s 0) +(defvar s 0) - (loop for x from 1 to n - do ( - loop for y from (+ 1 x) to n - do (setq s (+ s (gcd x y))) - ) +(loop for x from 1 to n + do ( + loop for y from (+ 1 x) to n + do (setq s (+ s (gcd x y))) ) +) - (print s) - (terpri) +(print s) +(terpri) +``` ## Part 2 @@ -316,437 +338,461 @@ Move on to a different world (for a bit). Here is the solution in a functional p OK, and now we start the second part of the solutions list. Now, the GCD algorithm is implemented directly in the program itself. Refer to this implementation in C; this algorithm is used in all other solutions below. - int gcd(int a, int b) { - while (b) { - int t = b; - b = a % b; - a = t; - } - - return a; +```c +int gcd(int a, int b) { + while (b) { + int t = b; + b = a % b; + a = t; } + return a; +} +``` + It is important to say that due to the loop organisation, we always call this function with such arguments that `b` is always bigger than `a`, so you don’t have to care about other cases. So, here is the complete program in C: - /* - Compile: - $ gcc ch-1.c - - Test run: - $ ./a.out 100 - 13015 - */ +```c +/* + Compile: + $ gcc ch-1.c - #include - #include + Test run: + $ ./a.out 100 + 13015 +*/ - int gcd(int a, int b) { - while (b) { - int t = b; - b = a % b; - a = t; - } +#include +#include - return a; +int gcd(int a, int b) { + while (b) { + int t = b; + b = a % b; + a = t; } - int main(int argc, char** argv) { - int n = 3; - if (argc != 1) { - n = atoi(argv[1]); - } + return a; +} - int s = 0; - for (int x = 1; x <= n; x++) { - for (int y = x + 1; y <= n; y++) { - s += gcd(x, y); - } - } +int main(int argc, char** argv) { + int n = 3; + if (argc != 1) { + n = atoi(argv[1]); + } - printf("%i\n", s); + int s = 0; + for (int x = 1; x <= n; x++) { + for (int y = x + 1; y <= n; y++) { + s += gcd(x, y); + } } + printf("%i\n", s); +} +``` + ### 13. JavaScript A Node.js slash JavaScript program is here for your further entertainment. It resembles a lot the previously shown C program. A similar pair of nested loops, and a similar implementation of `gcd`. Could you imagine 10-15 years ago that you would be able to run a JS program from command line? - // Test run: - // $ node ch-1.js 100 - // 13015 +```javascript +// Test run: +// $ node ch-1.js 100 +// 13015 - let n = process.argv.length == 3 ? process.argv[2] : 3; +let n = process.argv.length == 3 ? process.argv[2] : 3; - let s = 0; - for (let x = 1; x <= n; x++) { - for (let y = x + 1; y <= n; y++) { - s += gcd(x, y); - } +let s = 0; +for (let x = 1; x <= n; x++) { + for (let y = x + 1; y <= n; y++) { + s += gcd(x, y); } +} - console.log(s); - - function gcd(a, b) { - while (b) { - let t = b; - b = a % b; - a = t; - } +console.log(s); - return a; +function gcd(a, b) { + while (b) { + let t = b; + b = a % b; + a = t; } + return a; +} +``` + ### 14. Java Now, look at the solution in Java. Yes, we have to use classes again, but in the rest, a nice and clean program that doesn’t require many more comments, I think. - // To run: - // $ java ch-1.java 100 - // 13015 - - class Main { - static int gcd(int a, int b) { - while (b != 0) { - int t = b; - b = a % b; - a = t; - } +```java +// To run: +// $ java ch-1.java 100 +// 13015 - return a; +class Main { + static int gcd(int a, int b) { + while (b != 0) { + int t = b; + b = a % b; + a = t; } - public static void main(String[] args) { - int n =