diff options
| -rw-r--r-- | challenge-236/shimon-ben-avraham/raku/ch-2.md | 125 | ||||
| -rwxr-xr-x | challenge-236/shimon-ben-avraham/raku/ch-2.raku | 47 | ||||
| -rw-r--r-- | challenge-236/shimon-ben-avraham/raku/ch-2.sl | 109 |
3 files changed, 182 insertions, 99 deletions
diff --git a/challenge-236/shimon-ben-avraham/raku/ch-2.md b/challenge-236/shimon-ben-avraham/raku/ch-2.md index 5fba7db498..17a7ad805d 100644 --- a/challenge-236/shimon-ben-avraham/raku/ch-2.md +++ b/challenge-236/shimon-ben-avraham/raku/ch-2.md @@ -8,6 +8,10 @@ [Example 2](#example-2) [Example 3](#example-3) [The Solution](#the-solution) +[The Basic Algorithm](#the-basic-algorithm) +[Initialize variables](#initialize-variables) +[The Main Loop](#the-main-loop) +[Print and return the number of loops found.](#print-and-return-the-number-of-loops-found) [AUTHOR](#author) [LICENCE AND COPYRIGHT](#licence-and-copyright) @@ -64,183 +68,211 @@ Loop is as below: +### The Basic Algorithm +We will create a pointer to the first index of the array and attempt to find a loop that starts with that element. +It's important to remember that each element can be a part of only _one_ loop, even if it is a loop by itself. +Every time we find an element, we will push it to a loop array and set the element to `Nil` so that we don't use it again. +If we find a loop, we will push it to an array of loops. If we don't find a loop, we will move the start pointer to the next defined element and try again. -``` - 1| subset UniqueIntArray of Array where .elems == 0 || - 2| .unique.elems == .elems and .all ~~ IntStr; - -``` - - +Note that a 'loop' is defined as a list of integers, not a list of indices. +First we will only accept input that is a list of unique integers. ``` - 3| multi MAIN (#| A list of unique integers - 4| *@input where .all ~~ Int && - 5| .unique.elems == .elems, - 6| - 7| ) { + 1| multi MAIN (#| A list of unique integers + 2| *@input where .all ~~ Int && + 3| .unique.elems == .elems, + 4| ) { ``` +### Initialize variables ``` - 8| my Int @ints = @input>>.Int; - 9| my Int $num-elems = @ints.elems; - 10| my Int $start-index = 0; - 11| my Int $cur-index = $start-index; + 5| my Int @ints = @input>>.Int; + 6| my Int $num-elems = @ints.elems; + 7| my Int $start-pointer = 0; + 8| my Int $cur-index = $start-pointer; ``` +The current loop we are working on is stored in `@cur-loop`. The list of all found loops is stored in `@all-loops`. + +Note that a loop can consist of a single element. + ``` - 12| my UniqueIntArray $cur-loop; - 13| my UniqueIntArray @all-loops; + 9| my @cur-loop = []; + 10| my @all-loops = []; ``` +### The Main Loop +As long as there is a defined element in the array, `$start-pointer`, we will try to find a loop that starts with that element. + ``` - 14| LOOP: - 15| while $start-index.defined { + 11| INDEX: + 12| while $start-pointer.defined { ``` +We get the value of the current element and use it as the index of the next element in the loop. + ``` - 16| my $cur-value = @ints[$cur-index]; - 17| my $next-index = $cur-value; + 13| my $cur-value = @ints[$cur-index]; + 14| my $next-index = $cur-value; ``` +Each value we are looking at gets pushed to the current loop array and set to `Nil` so that we don't use it again. + ``` - 18| $cur-loop.push: $cur-value; - 19| @ints[$cur-index] = Nil; - 20| + 15| @cur-loop.push: $cur-value; + 16| @ints[$cur-index] = Nil; + 17| ``` +At this point there are three possibilities: + ``` - 21| given $next-index { + 18| given $next-index { ``` +* We have reached an index that is greater than the number of elements in the original array. + +This means we have found a loop that is not closed. Each element we've found so far is a loop by itself. So we push each element to the list of all loops. + ``` - 22| when * ≥ $num-elems { - 23| @all-loops.push: for $cur-loop; - 24| } + 19| when * ≥ $num-elems { + 20| @all-loops.push: $_ for @cur-loop; + 21| } ``` +* We have found a closed loop + +When the next index is the same as the start pointer, we have found a closed loop. We push the current loop to the list of all loops. + ``` - 25| when $start-index { - 26| @all-loops.push: $cur-loop; - 27| } + 22| when $start-pointer { + 23| @all-loops.push: @cur-loop; + 24| } ``` +* We have found a value that is not in the current loop. + +So we continue looking for the next element in the loop by updating the current index. + ``` - 28| default { - 29| $cur-index = $cur-value; - 30| next LOOP; - 31| } - 32| } + 25| default { + 26| $cur-index = $cur-value; + 27| next INDEX; + 28| } + 29| } ``` +At this point we have found a loop or a singular loop. We need to find the next start pointer by looking for the next defined element in the array. + ``` - 33| $cur-loop = []; - 34| $start-index = $cur-index = @ints.first(*.defined, :k); - 35| - 36| } - 37| + 30| @cur-loop = []; + 31| $start-pointer = $cur-index = @ints.first(*.defined, :k); + 32| + 33| } + 34| ``` +### Print and return the number of loops found. ``` - 38| say @all-loops.elems; - 39| return @all-loops.elems; - 40| } + 35| say @all-loops.elems; + 36| return @all-loops.elems; + 37| } ``` @@ -266,4 +298,5 @@ This program is distributed in the hope that it will be useful, but WITHOUT ANY ---- -Rendered from at 2023-09-29T02:25:06Z +Rendered from at 2023-09-30T00:53:05Z +
\ No newline at end of file diff --git a/challenge-236/shimon-ben-avraham/raku/ch-2.raku b/challenge-236/shimon-ben-avraham/raku/ch-2.raku index 8f5cc070dd..489b237a89 100755 --- a/challenge-236/shimon-ben-avraham/raku/ch-2.raku +++ b/challenge-236/shimon-ben-avraham/raku/ch-2.raku @@ -2,7 +2,7 @@ # Perl Weekly Challenge #236 Task 2 # © 2023 Shimon Bollinger. All rights reserved. -# Last modified: Fri 29 Sep 2023 08:15:33 PM EDT +# Last modified: Fri 29 Sep 2023 08:48:19 PM EDT # Version 0.0.1 # always use the latest version of Raku @@ -12,65 +12,64 @@ use v6.*; multi MAIN (#| A list of unique integers *@input where .all ~~ Int && .unique.elems == .elems, - #| Show debug prints when True Bool :v($verbose) = False ) { - my Int @ints = @input>>.Int; - my Int $num-elems = @ints.elems; - my Int $start-index = 0; - my Int $cur-index = $start-index; + my Int @ints = @input>>.Int; + my Int $num-elems = @ints.elems; + my Int $start-pointer = 0; + my Int $cur-index = $start-pointer; - my $cur-loop = []; + my @cur-loop = []; my @all-loops = []; - LOOP: - while $start-index.defined { + INDEX: + while $start-pointer.defined { my $cur-value = @ints[$cur-index]; my $next-index = $cur-value; - $cur-loop.push: $cur-value; + @cur-loop.push: $cur-value; @ints[$cur-index] = Nil; if $verbose { dd @ints; - dd $start-index; + dd $start-pointer; dd $cur-index; dd $next-index; dd $cur-value; - dd $cur-loop; + dd @cur-loop; } # end of if $verbose given $next-index { when * ≥ $num-elems { say "\e[31mFound singular loop[s]:\e[0m ", - $cur-loop.map({"[$_]"}).join(' ') if $verbose; - @all-loops.push: $_ for |$cur-loop; + @cur-loop.map({"[$_]"}).join(' ') if $verbose; + @all-loops.push: $_ for @cur-loop; } - when $start-index { + when $start-pointer { say "\e[32mFound a loop:\e[0m ", - $cur-loop.join(" ") if $verbose; - @all-loops.push: $cur-loop; + @cur-loop.join(" ") if $verbose; + @all-loops.push: @cur-loop; } default { say "\e[33mContinuing loop:\e[0m ", - $cur-loop.join(" ") if $verbose; + @cur-loop.join(" ") if $verbose; $cur-index = $cur-value; - next LOOP; + next INDEX; } } # end of given $next-index - $cur-loop = []; - $start-index = $cur-index = @ints.first(*.defined, :k); + @cur-loop = []; + $start-pointer = $cur-index = @ints.first(*.defined, :k); - say "\e[34m\nStarting new loop at index $start-index\e[0m" - if $start-index.defined && $verbose; - } # end of while $start-index.defined + say "\e[34m\nStarting new loop at index $start-pointer\e[0m" + if $start-pointer.defined && $verbose; + } # end of while $start-pointer.defined say "\n\n\e[35mAll loops:\n" ~ @all-loops.join("\n") ~ "\e[0m\n" if $verbose; diff --git a/challenge-236/shimon-ben-avraham/raku/ch-2.sl b/challenge-236/shimon-ben-avraham/raku/ch-2.sl index 079c456f99..8f81d91c93 100644 --- a/challenge-236/shimon-ben-avraham/raku/ch-2.sl +++ b/challenge-236/shimon-ben-avraham/raku/ch-2.sl @@ -2,7 +2,7 @@ # Perl Weekly Challenge #236 Task 2 # © 2023 Shimon Bollinger. All rights reserved. -# Last modified: Fri 29 Sep 2023 08:15:33 PM EDT +# Last modified: Fri 29 Sep 2023 08:53:49 PM EDT # Version 0.0.1 # begin-no-weave @@ -74,44 +74,70 @@ Loop is as below: =begin pod +=head3 The Basic Algorithm + +We will create a pointer to the first index of the array and attempt to find +a loop that starts with that element. + +It's important to remember that each element can be a part of only I<one> loop, +even if it is a loop by itself. + +Every time we find an element, we will push it to a loop array and set the +element to C<Nil> so that we don't use it again. + +If we find a loop, we will push it to an array of loops. If we don't find a +loop, we will move the start pointer to the next defined element and try again. + +Note that a 'loop' is defined as a list of integers, not a list of indices. + +First we will only accept input that is a list of unique integers. + =end pod multi MAIN (#| A list of unique integers *@input where .all ~~ Int && .unique.elems == .elems, - #| Show debug prints when True Bool :v($verbose) = False # no-weave-this-line ) { -=begin pod +=begin pod +=head3 Initialize variables =end pod - my Int @ints = @input>>.Int; - my Int $num-elems = @ints.elems; - my Int $start-index = 0; - my Int $cur-index = $start-index; + my Int @ints = @input>>.Int; + my Int $num-elems = @ints.elems; + my Int $start-pointer = 0; + my Int $cur-index = $start-pointer; =begin pod -For type safety, we will create a subset to represent an array of unique -integers. + +The current loop we are working on is stored in C<@cur-loop>. The list of all +found loops is stored in C<@all-loops>. + +Note that a loop can consist of a single element. =end pod - my $cur-loop = []; + my @cur-loop = []; my @all-loops = []; =begin pod -We will create a pointer to the first index of the array and attempt to find -a loop that starts with that element. If we find a loop, we will push it to an array of loops. If we +=head3 The Main Loop + +As long as there is a defined element in the array, C<$start-pointer>, +we will try to find a loop that starts with that element. =end pod - LOOP: - while $start-index.defined { + INDEX: + while $start-pointer.defined { =begin pod +We get the value of the current element and use it as the index of the +next element in the loop. + =end pod my $cur-value = @ints[$cur-index]; @@ -119,75 +145,98 @@ a loop that starts with that element. If we find a loop, we will push it to an a =begin pod +Each value we are looking at gets pushed to the current loop array and +set to C<Nil> so that we don't use it again. + =end pod - $cur-loop.push: $cur-value; + @cur-loop.push: $cur-value; @ints[$cur-index] = Nil; #begin-no-weave if $verbose { dd @ints; - dd $start-index; + dd $start-pointer; dd $cur-index; dd $next-index; dd $cur-value; - dd $cur-loop; + dd @cur-loop; } # end of if $verbose #end-no-weave =begin pod +At this point there are three possibilities: =end pod given $next-index { =begin pod +=item We have reached an index that is greater than the number of elements in +the original array. + +This means we have found a loop that is not closed. Each element we've +found so far is a loop by itself. So we push each element to the list of +all loops. + =end pod when * ≥ $num-elems { #begin-no-weave say "\e[31mFound singular loop[s]:\e[0m ", - $cur-loop.map({"[$_]"}).join(' ') if $verbose; + @cur-loop.map({"[$_]"}).join(' ') if $verbose; #end-no-weave - @all-loops.push: $_ for |$cur-loop; + @all-loops.push: $_ for @cur-loop; } =begin pod +=item We have found a closed loop + +When the next index is the same as the start pointer, we have found +a closed loop. We push the current loop to the list of all loops. + =end pod - when $start-index { + when $start-pointer { # begin-no-weave say "\e[32mFound a loop:\e[0m ", - $cur-loop.join(" ") if $verbose; + @cur-loop.join(" ") if $verbose; # end-no-weave - @all-loops.push: $cur-loop; + @all-loops.push: @cur-loop; } =begin pod +=item We have found a value that is not in the current loop. + +So we continue looking for the next element in the loop by updating the current +index. =end pod default { #begin-no-weave say "\e[33mContinuing loop:\e[0m ", - $cur-loop.join(" ") if $verbose; + @cur-loop.join(" ") if $verbose; #end-no-weave $cur-index = $cur-value; - next LOOP; + next INDEX; } } # end of given $next-index =begin pod +At this point we have found a loop or singular loop[s]. We need to find the +next start pointer by looking for the next defined element in the array. + =end pod - $cur-loop = []; - $start-index = $cur-index = @ints.first(*.defined, :k); + @cur-loop = []; + $start-pointer = $cur-index = @ints.first(*.defined, :k); # begin-no-weave - say "\e[34m\nStarting new loop at index $start-index\e[0m" - if $start-index.defined && $verbose; + say "\e[34m\nStarting new loop at index $start-pointer\e[0m" + if $start-pointer.defined && $verbose; # end-no-weave - } # end of while $start-index.defined + } # end of while $start-pointer.defined #begin-no-weave say "\n\n\e[35mAll loops:\n" ~ @all-loops.join("\n") ~ "\e[0m\n" @@ -195,6 +244,8 @@ a loop that starts with that element. If we find a loop, we will push it to an a #end-no-weave =begin pod +=head3 Print and return the number of loops found. + =end pod |