diff options
| author | Mohammad S Anwar <mohammad.anwar@yahoo.com> | 2023-10-02 00:26:11 +0100 |
|---|---|---|
| committer | Mohammad S Anwar <mohammad.anwar@yahoo.com> | 2023-10-02 00:26:11 +0100 |
| commit | bee1410ae61e5765b4101a84655e89ebfce295a7 (patch) | |
| tree | 50ac667860c6944cd6ff4f749fd256f9452f33fe | |
| parent | 155aabb3e8a776b78009bd9b9cee28dad59908c3 (diff) | |
| download | perlweeklychallenge-club-bee1410ae61e5765b4101a84655e89ebfce295a7.tar.gz perlweeklychallenge-club-bee1410ae61e5765b4101a84655e89ebfce295a7.tar.bz2 perlweeklychallenge-club-bee1410ae61e5765b4101a84655e89ebfce295a7.zip | |
- Added solutions by Arne Sommer.
- Added solutions by Packy Anderson.
32 files changed, 3384 insertions, 2527 deletions
diff --git a/challenge-236/arne-sommer/blog.txt b/challenge-236/arne-sommer/blog.txt new file mode 100644 index 0000000000..296aa0618e --- /dev/null +++ b/challenge-236/arne-sommer/blog.txt @@ -0,0 +1 @@ +https://raku-musings.com/changing-loops.html diff --git a/challenge-236/arne-sommer/raku/array-loops b/challenge-236/arne-sommer/raku/array-loops new file mode 100755 index 0000000000..b7b5417ea0 --- /dev/null +++ b/challenge-236/arne-sommer/raku/array-loops @@ -0,0 +1,38 @@ +#! /usr/bin/env raku + +unit sub MAIN (*@ints where all(@ints) ~~ Int && @ints.elems == @ints.unique.elems, :i(:$index), :v(:$verbose)); + +die "Use the index values (0..{@ints.end}) only" if $index && @ints.min != 0 && @ints.max != @ints.end; + +say ":Index:Value: ", (^@ints).map({ $_ ~ ":" ~ @ints[$_] }).join(", ") if $verbose; + +my $loop-count = 0; +my %seen; + +FORLOOP: +for ^@ints.elems -> $start +{ + next if %seen{$start}++; + + my $pos = $start; + my @loop = "[$start]"; + + loop + { + unless 0 <= $pos <= @ints.end + { + say ":Non-Loop: { @loop.join(" ") }" if $verbose; + next FORLOOP; + } + + $pos = @ints[$pos]; + @loop.push: $pos; + %seen{$pos}++; + last if $pos == $start; + } + + $loop-count++; + say ":Loop { @loop.join(" ") }" if $verbose; +} + +say $loop-count; diff --git a/challenge-236/arne-sommer/raku/array-loops-all b/challenge-236/arne-sommer/raku/array-loops-all new file mode 100755 index 0000000000..0773e13e7f --- /dev/null +++ b/challenge-236/arne-sommer/raku/array-loops-all @@ -0,0 +1,25 @@ +#! /usr/bin/env raku + +unit sub MAIN (*@ints where all(@ints) ~~ UInt && @ints.elems == @ints.unique.elems, :v(:$verbose)); + +say ":Index:Value: ", (^@ints).map({ $_ ~ ":" ~ @ints[$_] }).join(", ") if $verbose; + +my $loop-count = 0; + +for ^@ints.elems -> $start +{ + my $pos = $start; + my @loop = "[$start]"; + + loop + { + $pos = @ints[$pos]; + @loop.push: $pos; + last if $pos == $start; + } + + $loop-count++; + say ":Loop { @loop.join(" ") }" if $verbose; +} + +say $loop-count; diff --git a/challenge-236/arne-sommer/raku/array-loops-unique b/challenge-236/arne-sommer/raku/array-loops-unique new file mode 100755 index 0000000000..1687b11846 --- /dev/null +++ b/challenge-236/arne-sommer/raku/array-loops-unique @@ -0,0 +1,28 @@ +#! /usr/bin/env raku + +unit sub MAIN (*@ints where all(@ints) ~~ UInt && @ints.elems == @ints.unique.elems, :v(:$verbose)); + +say ":Index:Value: ", (^@ints).map({ $_ ~ ":" ~ @ints[$_] }).join(", ") if $verbose; + +my $loop-count = 0; +my %seen; + +for ^@ints.elems -> $start +{ + next if %seen{$start}++; + my $pos = $start; + my @loop = "[$start]"; + + loop + { + $pos = @ints[$pos]; + @loop.push: $pos; + %seen{$pos}++; + last if $pos == $start; + } + + $loop-count++; + say ":Loop { @loop.join(" ") }" if $verbose; +} + +say $loop-count; diff --git a/challenge-236/arne-sommer/raku/ch-1.raku b/challenge-236/arne-sommer/raku/ch-1.raku new file mode 100755 index 0000000000..865e1bbbc3 --- /dev/null +++ b/challenge-236/arne-sommer/raku/ch-1.raku @@ -0,0 +1,36 @@ +#! /usr/bin/env raku + +unit sub MAIN (*@bills where all(@bills) ~~ Int && all(@bills) == any(<5 10 20>), :v(:$verbose)); + +my $cash = BagHash.new(); +my $transaction = 0; + +for @bills -> $bill +{ + my $change = $bill - 5; + print ":Transaction { ++$transaction } | Payment: $bill | Change: $change" if $verbose; + $cash{$bill}++; + + if $change + { + for $cash.keys.sort.reverse -> $note + { + while $change >= $note && $cash{$note} + { + $cash{$note}--; + $change -= $note; + } + } + } + + if $change + { + say " | Unable to give change" if $verbose; + say 'false'; + exit; + } + + say " | Cash Register: { $cash.kxxv.sort.join(",") }" if $verbose; +} + +say "true"; diff --git a/challenge-236/arne-sommer/raku/ch-2.raku b/challenge-236/arne-sommer/raku/ch-2.raku new file mode 100755 index 0000000000..b7b5417ea0 --- /dev/null +++ b/challenge-236/arne-sommer/raku/ch-2.raku @@ -0,0 +1,38 @@ +#! /usr/bin/env raku + +unit sub MAIN (*@ints where all(@ints) ~~ Int && @ints.elems == @ints.unique.elems, :i(:$index), :v(:$verbose)); + +die "Use the index values (0..{@ints.end}) only" if $index && @ints.min != 0 && @ints.max != @ints.end; + +say ":Index:Value: ", (^@ints).map({ $_ ~ ":" ~ @ints[$_] }).join(", ") if $verbose; + +my $loop-count = 0; +my %seen; + +FORLOOP: +for ^@ints.elems -> $start +{ + next if %seen{$start}++; + + my $pos = $start; + my @loop = "[$start]"; + + loop + { + unless 0 <= $pos <= @ints.end + { + say ":Non-Loop: { @loop.join(" ") }" if $verbose; + next FORLOOP; + } + + $pos = @ints[$pos]; + @loop.push: $pos; + %seen{$pos}++; + last if $pos == $start; + } + + $loop-count++; + say ":Loop { @loop.join(" ") }" if $verbose; +} + +say $loop-count; diff --git a/challenge-236/arne-sommer/raku/exact-change b/challenge-236/arne-sommer/raku/exact-change new file mode 100755 index 0000000000..865e1bbbc3 --- /dev/null +++ b/challenge-236/arne-sommer/raku/exact-change @@ -0,0 +1,36 @@ +#! /usr/bin/env raku + +unit sub MAIN (*@bills where all(@bills) ~~ Int && all(@bills) == any(<5 10 20>), :v(:$verbose)); + +my $cash = BagHash.new(); +my $transaction = 0; + +for @bills -> $bill +{ + my $change = $bill - 5; + print ":Transaction { ++$transaction } | Payment: $bill | Change: $change" if $verbose; + $cash{$bill}++; + + if $change + { + for $cash.keys.sort.reverse -> $note + { + while $change >= $note && $cash{$note} + { + $cash{$note}--; + $change -= $note; + } + } + } + + if $change + { + say " | Unable to give change" if $verbose; + say 'false'; + exit; + } + + say " | Cash Register: { $cash.kxxv.sort.join(",") }" if $verbose; +} + +say "true"; diff --git a/challenge-236/packy-anderson/README.md b/challenge-236/packy-anderson/README.md index f957013c00..54468a7f26 100644 --- a/challenge-236/packy-anderson/README.md +++ b/challenge-236/packy-anderson/README.md @@ -8,20 +8,16 @@ Sample output ``` $ perl/ch-1.pl Example 1: -Input: @ints = (0, 2, 9, 4, 6) +Input: @bills = (5, 5, 5, 10, 20) Output: true Example 2: -Input: @ints = (5, 1, 3, 2) +Input: @bills = (5, 5, 10, 10, 20) Output: false Example 3: -Input: @ints = (2, 2, 3) +Input: @bills = (5, 5, 5, 20) Output: true - -Example 4 from James Curtis-Smith: -Input: @ints = (1, 2, 3, 4, 1, 2, 3) -Output: false ``` * [Task 2](perl/ch-2.pl) @@ -30,16 +26,32 @@ Sample output ``` $ perl/ch-2.pl Example 1: -Input: @ints = (1, 0, 2, 3, 0, 4, 5, 0) -Output: (1, 0, 0, 2, 3, 0, 0, 4) +Input: @ints = (4,6,3,8,15,0,13,18,7,16,14,19,17,5,11,1,12,2,9,10) +Output: 3 + +Loops are as below: +[4 15 1 6 13 5 0] +[3 8 7 18 9 16 12 17 2] +[14 11 19 10] Example 2: -Input: @ints = (1, 2, 3) -Output: (1, 2, 3) +Input: @ints = (0,1,13,7,6,8,10,11,2,14,16,4,12,9,17,5,3,18,15,19) +Output: 6 + +Loops are as below: +[0] +[1] +[13 9 14 17 18 15 5 8 2] +[7 11 4 6 10 16 3] +[12] +[19] Example 3: -Input: @ints = (0, 3, 0, 4, 5) -Output: (0, 0, 3, 0, 0) +Input: @ints = (9,8,3,11,5,7,13,19,12,4,14,10,18,2,16,1,0,15,6,17) +Output: 1 + +Loop is as below: +[9 4 5 7 19 17 15 1 8 12 18 6 13 2 3 11 10 14 16 0] ``` ## Raku @@ -50,20 +62,16 @@ Sample output ``` $ raku/ch-1.raku Example 1: -Input: @ints = (0, 2, 9, 4, 6) +Input: @bills = (5, 5, 5, 10, 20) Output: true Example 2: -Input: @ints = (5, 1, 3, 2) +Input: @bills = (5, 5, 10, 10, 20) Output: false Example 3: -Input: @ints = (2, 2, 3) +Input: @bills = (5, 5, 5, 20) Output: true - -Example 4 from James Curtis-Smith: -Input: @ints = (1, 2, 3, 4, 1, 2, 3) -Output: false ``` * [Task 2](raku/ch-2.raku) @@ -72,16 +80,32 @@ Sample output ``` $ raku/ch-2.raku Example 1: -Input: @ints = (1, 0, 2, 3, 0, 4, 5, 0) -Output: (1, 0, 0, 2, 3, 0, 0, 4) +Input: @ints = (4,6,3,8,15,0,13,18,7,16,14,19,17,5,11,1,12,2,9,10) +Output: 3 + +Loops are as below: +[4 15 1 6 13 5 0] +[3 8 7 18 9 16 12 17 2] +[14 11 19 10] Example 2: -Input: @ints = (1, 2, 3) -Output: (1, 2, 3) +Input: @ints = (0,1,13,7,6,8,10,11,2,14,16,4,12,9,17,5,3,18,15,19) +Output: 6 + +Loops are as below: +[0] +[1] +[13 9 14 17 18 15 5 8 2] +[7 11 4 6 10 16 3] +[12] +[19] Example 3: -Input: @ints = (0, 3, 0, 4, 5) -Output: (0, 0, 3, 0, 0) +Input: @ints = (9,8,3,11,5,7,13,19,12,4,14,10,18,2,16,1,0,15,6,17) +Output: 1 + +Loop is as below: +[9 4 5 7 19 17 15 1 8 12 18 6 13 2 3 11 10 14 16 0] ``` ## Guest Language: Python @@ -94,4 +118,4 @@ Output: (0, 0, 3, 0, 0) ## Blog Post -[Perl Weekly Challenge: Remove and Duplicate, Challenge Edition](https://packy.dardan.com/2023/09/18/perl-weekly-challenge-remove-and-duplicate-challenge-edition/) +[Perl Weekly Challenge: Exact Change and Array Loops](https://packy.dardan.com/2023/09/25/perl-weekly-challenge-exact-change-and-array-loops/) diff --git a/challenge-236/packy-anderson/blog.txt b/challenge-236/packy-anderson/blog.txt new file mode 100644 index 0000000000..03acc3f7de --- /dev/null +++ b/challenge-236/packy-anderson/blog.txt @@ -0,0 +1 @@ +https://packy.dardan.com/2023/09/25/perl-weekly-challenge-exact-change-and-array-loops/ diff --git a/challenge-236/packy-anderson/java/Ch1.java b/challenge-236/packy-anderson/java/Ch1.java new file mode 100644 index 0000000000..678631bf8d --- /dev/null +++ b/challenge-236/packy-anderson/java/Ch1.java @@ -0,0 +1,75 @@ +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Collections; +import java.util.stream.Collectors; +import java.util.HashMap; +import java.util.List; + +public class Ch1 { + public static boolean isExactChangePossible(int[] bills) { + // we keep the bills in a "till" + HashMap<Integer, Integer> till = + new HashMap<Integer, Integer>(); + + for (int collected : bills) { + // put the bill we collected in the "till" + // + // using .getOrDefault(collected, 0) yields the value + // in the map for the key 'collected' if it exists, or + // the specified default (in this case, 0) if it doesn't + till.put( + collected, + till.getOrDefault(collected, 0) + 1 + ); + + // calculate the required change + int change_required = collected - 5; + + // loop through the bills we have on hand, making sure + // we go from largest to smallest bill + List<Integer> keys = new ArrayList<>(till.keySet()); + Collections.sort(keys, Collections.reverseOrder()); + for (Integer bill : keys) { + // as long as we have more of this bill and + // using it would not yield TOO MUCH change + while (till.get(bill) > 0 && + change_required - bill >= 0) { + // deduct the amount from the required change + change_required -= bill; + + // remove the bill from the till + till.put(bill, till.get(bill) - 1); + } + } + // if we weren't able to make change, fail + if (change_required > 0) { + return false; + } + } + return true; + } + + public static String joined(int[] ints) { + // we're using it more than once, make it a method + return Arrays.stream(ints) + .mapToObj(String::valueOf) + .collect(Collectors.joining(", ")); + } + + public static void solution(int[] bills) { + System.out.println("Input: @bills = (" + joined(bills) + ")"); + boolean output = isExactChangePossible(bills); + System.out.println("Output: " + output); + } + + public static void main(String[] args) { + System.out.println("Example 1:"); + solution(new int[] {5, 5, 5, 10, 20}); + + System.out.println("\nExample 2:"); + solution(new int[] {5, 5, 10, 10, 20}); + + System.out.println("\nExample 3:"); + solution(new int[] {5, 5, 5, 20}); + } +} diff --git a/challenge-236/packy-anderson/java/Ch2.java b/challenge-236/packy-anderson/java/Ch2.java new file mode 100644 index 0000000000..3ce68300e8 --- /dev/null +++ b/challenge-236/packy-anderson/java/Ch2.java @@ -0,0 +1,108 @@ +import java.util.ArrayList; +import java.util.Arrays; +import java.util.HashMap; +import java.util.stream.Collectors; + +public class Ch2 { + public static ArrayList<Integer> loopExistsAt( + int start, int[] ints, HashMap<Integer, Integer> seen + ) { + // bail early if we're in a loop we've seen before + if (seen.get(start) != null) { + // return an empty ArrayList + return new ArrayList<Integer>(); + } + + // initialize an empty list to start + ArrayList<Integer> loop = new ArrayList<Integer>(); + // initialize i to starting point + int i = start; + while (true) { + // keep track of the values in the order we visit them + loop.add(ints[i]); + + // track where we've already been + // to avoid double-counting loops + seen.put(i, 1); + + // get the next index + i = ints[i]; + + // make sure the index is in bounds + if (i < 0 || i >= ints.length) { + break; + } + + // make sure we haven't seen the index before + if (seen.get(i) != null) { + break; + } + } + + // if the last element points back to + // the start, it's a loop! + if (loop.get(loop.size() - 1) == start) { + return loop; + } + + // otherwise, return an empty ArrayList + return new ArrayList<Integer>(); + } + + public static ArrayList<ArrayList<Integer>> identifyLoops(int[] ints) { + ArrayList<ArrayList<Integer>> loops = + new ArrayList<ArrayList<Integer>>(); + HashMap<Integer, Integer> seen = + new HashMap<Integer, Integer>(); + + for (int i = 0; i < ints.length; i++) { + ArrayList<Integer> loop = loopExistsAt(i, ints, seen); + if (loop.size() > 0) { + loops.add(loop); + } + } + return loops; + } + + public static String comma_joined(int[] ints) { + // we're using it more than once, make it a method + return Arrays.stream(ints) + .mapToObj(String::valueOf) + .collect(Collectors.joining(",")); + } + + public static void solution(int[] ints) { + System.out.println("Input: @ints = (" + comma_joined(ints) + + ")"); + ArrayList<ArrayList<Integer>> loops = identifyLoops(ints); + int count = loops.size(); + System.out.println(String.format("Output: %1$d", count)); + if (count > 0) { + String loop_noun = (count == 1) ? "Loop" : "Loops"; + String are_verb = (count == 1) ? "is" : "are"; + System.out.println("\n" + loop_noun + " " + are_verb + + " as below:"); + + for (ArrayList<Integer> loop : loops) { + String as_list = loop.stream() + .map(String::valueOf) + .collect(Collectors.joining(" ")); + System.out.println("[" + as_list + "]"); + } + } + } + + public static void main(String[] args) { + System.out.println("Example 1:"); + solution(new int[] {4,6,3,8,15,0,13,18,7,16,14, + 19,17,5,11,1,12,2,9,10}); + + System.out.println("\nExample 2:"); + solution(new int[] {0,1,13,7,6,8,10,11,2,14,16, + 4,12,9,17,5,3,18,15,19}); + + System.out.println("\nExample 3:"); + solution(new int[] {9,8,3,11,5,7,13,19,12,4,14, + 10,18,2,16,1,0,15,6,17}); + } +} diff --git a/challenge-236/packy-anderson/perl/ch-1.pl b/challenge-236/packy-anderson/perl/ch-1.pl new file mode 100644 index 0000000000..88740457ec --- /dev/null +++ b/challenge-236/packy-anderson/perl/ch-1.pl @@ -0,0 +1,61 @@ +#!/usr/bin/env perl + +use v5.38; +use Data::Dumper::Concise; + +sub isExactChangePossible { + my @bills = @_; + my %till; # we keep the bills in a "till" + BILLS: foreach my $collected ( @bills ) { + # put the bill we collected in the "till" + $till{$collected}++; + + # calculate the required change + my $change_required = $collected - 5; + + # if we don't need to make change, + # skip to the next bill collected! + next BILLS unless $change_required; + + # loop through the bills we have on hand + # in descending size (try to make change + # with the largest bills possible) + foreach my $bill ( reverse sort { $a <=> $b } keys %till ) { + + # as long as we have more of this bill and + # using it would not yield TOO MUCH change + while ( $till{$bill} > 0 && $change_required - $bill >= 0 ) { + # deduct the amount from the required change + $change_required -= $bill; + + # remove the bill from the till + $till{$bill}--; + } + + # move on if we managed to make exact change! + next BILLS unless $change_required; + } + + # if we weren't able to make change, fail + return 0 if $change_required; + } + + # we successfully made change for all transactions! + return 1; +} + +sub solution { + my @bills = @_; + say 'Input: @bills = (' . join(', ', @bills) . ')'; + my $output = isExactChangePossible(@bills); + say 'Output: ' . ($output ? 'true' : 'false'); +} + +say "Example 1:"; +solution(5, 5, 5, 10, 20); + +say "\nExample 2:"; +solution(5, 5, 10, 10, 20); + +say "\nExample 3:"; +solution(5, 5, 5, 20); diff --git a/challenge-236/packy-anderson/perl/ch-2.pl b/challenge-236/packy-anderson/perl/ch-2.pl new file mode 100644 index 0000000000..512b361802 --- /dev/null +++ b/challenge-236/packy-anderson/perl/ch-2.pl @@ -0,0 +1,86 @@ +#!/usr/bin/env perl + +use v5.38; + +use Lingua::EN::Inflexion qw( inflect ); + +sub loopExistsAt { + my %params = @_; + my $ints = $params{ints}; + my $start = $params{start}; + my $seen = $params{seen}; + + # bail early if we're in a loop we've seen before + return if exists $seen->{$start}; + + my @loop; + my $i = $start; + for (;;) { + # keep track of the values in the order we visit them + push @loop, $ints->[$i]; + + # track where we've already been + # to avoid double-counting loops + $seen->{$i} = 1; + + # get the next index + $i = $ints->[$i]; + + # make sure the index is in bounds + last unless $i >= 0 && $i <= $#{$ints}; + + # make sure we haven't seen the index before + last if exists $seen->{$i}; + } + + # if the last element points back to + # the start, it's a loop! + if ($loop[-1] == $start) { + return @loop; + } + # otherwise, return an empty list + return; +} + +sub identifyLoops { + my @ints = @_; + my @loops; + my %seen; # keep track of indices we've seen + # to avoid duplicating loops + foreach my $start ( 0 .. $#ints ) { + my @loop = loopExistsAt( + start => $start, + ints => \@ints, + seen => \%seen + ); + if (@loop) { + push @loops, \@loop; + } + } + return @loops; +} + +sub solution { + my @ints = @_; + say 'Input: @ints = (' . join(',', @ints) . ')'; + my @loops = identifyLoops(@ints); + say 'Output: ' . scalar(@loops); + + if (@loops) { + my $count = scalar(@loops); + + say inflect "\n<#d:$count><N:Loop> <V:is> as below:"; + foreach my $loop ( @loops ) { + say '[' . join(' ', @$loop) . ']'; + } + } +} + +say "Example 1:"; +solution(4,6,3,8,15,0,13,18,7,16,14,19,17,5,11,1,12,2,9,10); + +say "\nExample 2:"; +solution(0,1,13,7,6,8,10,11,2,14,16,4,12,9,17,5,3,18,15,19); + +say "\nExample 3:"; +solution(9,8,3,11,5,7,13,19,12,4,14,10,18,2,16,1,0,15,6,17); diff --git a/challenge-236/packy-anderson/python/ch-1.py b/challenge-236/packy-anderson/python/ch-1.py new file mode 100644 index 0000000000..22cd31b036 --- /dev/null +++ b/challenge-236/packy-anderson/python/ch-1.py @@ -0,0 +1,48 @@ +#!/usr/bin/env python + +def isExactChangePossible(bills): + till = {}; # we keep the bills in a "till" + for collected in bills: + # put the bill we collected in the "till" + # + # using .get(collected, 0) yields the value in the + # dict for the key 'collected' if it exists, or the + # specified default (in this case, 0) if it doesn't + till[collected] = till.get(collected, 0) + 1 + + # calculate the required change + change_required = collected - 5 + + # loop through the bills we have on hand + for bill in sorted(till, reverse=True): + # as long as we have more of this bill and + # using it would not yield TOO MUCH change + while till[bill] > 0 and change_required - bill >= 0: + # deduct the amount from the required change + change_required -= bill + + # remove the bill from the till + till[bill] -= 1 + + # if we weren't able to make change, fail + if change_required: + return 0 + + # we successfully made change for all transactions! + return 1 + +def solution(bills): + as_list = ', '.join(map(lambda i: str(i), bills)) + print(f'Input: @bills = ({as_list})') + output = isExactChangePossible(bills) + print(f'Output: {"true" if output else "false"}') + + +print('Example 1:') +solution([5, 5, 5, 10, 20]) + +print('\nExample 2:') +solution([5, 5, 10, 10, 20]) + +print('\nExample 3:') +solution([5, 5, 5, 20]) diff --git a/challenge-236/packy-anderson/python/ch-2.py b/challenge-236/packy-anderson/python/ch-2.py new file mode 100644 index 0000000000..e28b646fc6 --- /dev/null +++ b/challenge-236/packy-anderson/python/ch-2.py @@ -0,0 +1,73 @@ +#!/usr/bin/env python + +def loopExistsAt(ints=[], seen={}, start=0): + # bail early if we're in a loop we've seen before + if start in seen: + return [] + + loop = [] # initialize an empty list to start + i = start # initialize i to starting point + while True: + # keep track of the values in the order we visit them + loop.append(ints[i]) + + # track where we've already been + # to avoid double-counting loops + seen[i] = 1 + + # get the next index + i = ints[i] + + # make sure the index is in bounds + if i < 0 or i >= len(ints): + break + + # make sure we haven't seen the index before + if i in seen: + break + + # if the last element points back to + # the start, it's a loop! + if loop[-1] == start: + return loop + + # otherwise, return an empty list + return [] + +def identifyLoops(ints): + loops = [] + seen = {}; # keep track of indices we've seen + # to avoid duplicating loops + for start in range(0, len(ints)): + loop = loopExistsAt( + start = start, + ints = ints, + seen = seen + ) + if loop: + loops.append(loop) + return loops + +def solution(ints): + as_list = ','.join(map(lambda i: str(i), ints)) + print(f'Input: @ints = ({as_list})') + loops = identifyLoops(ints) + count = len(loops) + print(f'Output: {count}') + if count: + loop_noun = "Loops" if count != 1 else "Loop" + are_verb = "are" if count != 1 else "is" + print(f'\n{loop_noun} {are_verb} as below:') + for loop in loops: + as_list = ' '.join(map(lambda i: str(i), loop)) + print(f'[{as_list}]') + + +print('Example 1:') +solution([4,6,3,8,15,0,13,18,7,16,14,19,17,5,11,1,12,2,9,10]) + +print('\nExample 2:') +solution([0,1,13,7,6,8,10,11,2,14,16,4,12,9,17,5,3,18,15,19]) + +print('\nExample 3:') +solution([9,8,3,11,5,7,13,19,12,4,14,10,18,2,16,1,0,15,6,17]) diff --git a/challenge-236/packy-anderson/raku/ch-1.raku |
