Merge pull request #1519 from noudald/challenge-054-noud

Solution to challenge 054 task 1 and 2 in Raku by Noud

2 files changed, 111 insertions, 0 deletions

diff --git a/challenge-054/noud/raku/ch-1.p6 b/challenge-054/noud/raku/ch-1.p6
new file mode 100644
index 0000000000..da27e09e3a
--- /dev/null
+++ b/challenge-054/noud/raku/ch-1.p6
@@ -0,0 +1,19 @@
+# kth Permutation Sequence
+#
+# Write a script to accept two integers n (>=1) and k (>=1). It should print
+# the kth permutation of n integers. For more information, please follow the
+# wiki page.
+#
+# For example, n=3 and k=4, the possible permutation sequences are listed below:
+#
+# 123
+# 132
+# 213
+# 231
+# 312
+# 321
+#
+# The script should print the 4th permutation sequence 231.
+
+my $k-per-seq = -> $n, $k { (1..$n).permutations()[$k - 1].join('') };
+say $k-per-seq(3, 4);
diff --git a/challenge-054/noud/raku/ch-2.p6 b/challenge-054/noud/raku/ch-2.p6
new file mode 100644
index 0000000000..ae16eedb7f
--- /dev/null
+++ b/challenge-054/noud/raku/ch-2.p6
@@ -0,0 +1,92 @@
+# Collatz Conjecture
+# Contributed by Ryan Thompson
+#
+# It is thought that the following sequence will always reach 1:
+#
+#     $n = $n / 2 when $n is even
+#     $n = 3*$n + 1 when $n is odd
+#
+# For example, if we start at 23, we get the following sequence:
+#
+# 23 → 70 → 35 → 106 → 53 → 160 → 80 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
+#
+# Write a function that finds the Collatz sequence for any positive integer.
+# Notice how the sequence itself may go far above the original starting number.
+#
+# Extra Credit
+#
+# Have your script calculate the sequence length for all starting numbers up to
+# 1000000 (1e6), and output the starting number and sequence length for the
+# longest 20 sequences.
+
+sub collatz-seq($n) {
+    if ($n == 1) {
+        [1];
+    } elsif ($n % 2 == 0) {
+        [$n, |(collatz-seq($n / 2))];
+    } else {
+        [$n, |(collatz-seq(3 * $n + 1))];
+    }
+}
+
+say collatz-seq(23);
+
+
+# Extra Credit
+
+# I have no good idea how to do this smart. I don't even know if there is a
+# faster way. The Collatz Conjecture is a Conjecture for a reason of course.
+# Therefore, I do it the lazy way:
+#
+# 1. Parallelize the whole search. Depending on the amount of threads this
+#    speeds up tremendously.
+# 2. Use cached to store older results. (I'm surprised this works well with
+#    multi-threading)
+#
+# On my Intel i7 (4 cores, 8 threads) it still takes half an hour to compute.
+# Results:
+#
+# 922524 444
+# 922525 444
+# 922526 444
+# 938143 444
+# 615017 446
+# 410011 448
+# 818943 449
+# 820022 449
+# 820023 449
+# 546681 451
+# 970599 457
+# 767903 467
+# 796095 467
+# 511935 469
+# 910107 475
+# 927003 475
+# 704623 503
+# 939497 506
+# 626331 508
+# 837799 524
+
+use experimental :cached;  # My favourite Raku feature!
+
+sub collatz-length($n) is cached {
+    if ($n == 1) {
+        0;
+    } elsif ($n % 2 == 0) {
+        collatz-length($n / 2) + 1;
+    } else {
+        collatz-length(3 * $n + 1) + 1;
+    }
+}
+
+my $collatz-list = Channel.new;
+await (1..1e6).map: -> $n {
+    start {
+        $collatz-list.send((collatz-length($n), $n));
+    }
+}
+$collatz-list.close();
+
+for $collatz-list.list.sort.tail(20) -> ($l, $n) {
+    say $n, ' ', $l;
+}