Merge pull request #10766 from packy/master

Challenge 285 solutions by Packy Anderson

10 files changed, 471 insertions, 1 deletions

diff --git a/challenge-285/packy-anderson/README.md b/challenge-285/packy-anderson/README.md
index ad8fe837a8..af883912e0 100644
--- a/challenge-285/packy-anderson/README.md
+++ b/challenge-285/packy-anderson/README.md
@@ -22,4 +22,4 @@
 
 ## Blog Post
 
-[Perl Weekly Challenge: Relatively Lucky](https://packy.dardan.com/b/QX)
+[Perl Weekly Challenge: Exact Change Only!](https://packy.dardan.com/b/Qq)
diff --git a/challenge-285/packy-anderson/blog.txt b/challenge-285/packy-anderson/blog.txt
new file mode 100644
index 0000000000..5f2c4d5caf
--- /dev/null
+++ b/challenge-285/packy-anderson/blog.txt
@@ -0,0 +1 @@
+https://packy.dardan.com/b/Qq
\ No newline at end of file
diff --git a/challenge-285/packy-anderson/elixir/ch-1.exs b/challenge-285/packy-anderson/elixir/ch-1.exs
new file mode 100755
index 0000000000..a61c3669ff
--- /dev/null
+++ b/challenge-285/packy-anderson/elixir/ch-1.exs
@@ -0,0 +1,44 @@
+#!/usr/bin/env elixir
+
+defmodule PWC do
+  def noConnection(routes) do
+    starts = routes
+    |> Enum.map(fn x -> List.first(x) end)
+    |> MapSet.new
+    ends   = routes
+    |> Enum.map(fn x -> List.last(x) end)
+    |> MapSet.new
+    noConnection = MapSet.difference(ends, starts)
+    cond do
+      MapSet.size(noConnection) == 0 ->
+        "no terminal destinations"
+      MapSet.size(noConnection) > 1 ->
+        "multiple terminal destinations"
+      true ->
+        noConnection |> MapSet.to_list |> List.first
+    end
+  end
+
+  def tupleJoin(list) do
+    list
+    |> Enum.map(fn x -> "[#{List.first(x)}, #{List.last(x)}]" end)
+    |> Enum.join(", ")
+  end
+
+  def solution(routes) do
+    IO.puts("Input: @routes = (#{ tupleJoin(routes) })")
+    IO.puts("Output: #{noConnection(routes)}")
+  end
+end
+
+IO.puts("Example 1:")
+PWC.solution([["B","C"], ["D","B"], ["C","A"]])
+
+IO.puts("\nExample 2:")
+PWC.solution([["A","Z"], ])
+
+IO.puts("\nBad Input: multiple terminal destination")
+PWC.solution([["A","B"], ["C", "D"]])
+
+IO.puts("\nBad Input: no terminal destinations")
+PWC.solution([["A","Z"], ["Z", "A"]])
diff --git a/challenge-285/packy-anderson/elixir/ch-2.exs b/challenge-285/packy-anderson/elixir/ch-2.exs
new file mode 100755
index 0000000000..25df1c48a6
--- /dev/null
+++ b/challenge-285/packy-anderson/elixir/ch-2.exs
@@ -0,0 +1,93 @@
+#!/usr/bin/env elixir
+
+defmodule PWC do
+  # establish the values of the coins
+  @coin_types %{ 50 => "HD", 25 => "Q", 10 => "D", 5 => "N", 1 => "P" }
+
+  # make a sorted list of coin values
+  @coin_values @coin_types |> Map.keys |> Enum.sort |> Enum.reverse
+
+  def formatCoin(coin, count) do
+    if count > 1 do
+      "#{to_string(count)}#{coin}"
+    else
+      coin
+    end
+  end
+
+  def joinCoins(x, y) do
+    Enum.join([ x, y ], " + ")
+  end
+
+  def addCoins(count, coin, amount, _, output) when amount == 0 do
+    output ++ [ formatCoin(coin, count) ]
+  end
+
+  def addCoins(count, coin, amount, value, output) do
+    # make a recursive call to get the combinations
+    # for that remaining amount, excluding any coins
+    # of equal or greater value to $value
+    {_, output} = makeChange(amount, value)
+    |> Enum.map_reduce(output, fn combo, output ->
+      this_coin = formatCoin(coin, count)
+      {
+        combo,
+        output ++ [ joinCoins(this_coin, combo) ]
+      }
+    end)
+    output
+  end
+
+  def makeChange([value | remaining], amount, exclude, output)
+      when (value > amount) or (exclude > 0 and value >= exclude) do
+    # if this type of coin is worth more than the total,
+    # we can't use it OR
+    # if we're excluding this coin value or greater, skip it
+    makeChange(remaining, amount, exclude, output)
+  end
+
+  def makeChange([value], amount, _, output)
+      when value == 1 do
+    # we're adding pennies
+    output ++ [ formatCoin("P", amount) ]
+  end
+
+  def makeChange([value | remaining], amount, exclude, output) do
+    coin = @coin_types |> Map.get(value) # get the coin name
+    # loop from max number of this coin we can use down to 1
+    {_, output} = 1 .. Integer.floor_div(amount, value)
+    |> Enum.reverse
+    |> Enum.map_reduce(output,
+      fn count, output2 ->
+        # figure out how much change we need after we've used
+        # $count many of coin $coin
+        left = amount - (count * value)
+        { count, addCoins(count, coin, left, value, output2) }
+      end)
+    makeChange(remaining, amount, exclude, output)
+  end
+
+  def makeChange(amount, exclude \\ 0) do
+    makeChange(@coin_values, amount, exclude, [])
+  end
+
+  def solution(amount) do
+    IO.puts("Input: @amount = #{ amount }")
+    ways = makeChange(amount)
+    IO.puts("Output: #{ length(ways) }")
+    Enum.map_reduce(ways, 0, fn c, i ->
+      i = i + 1
+      IO.puts("#{i}: #{c}")
+      { c, i }
+    end)
+  end
+end
+
+IO.puts("Example 1:")
+PWC.solution(9)
+
+IO.puts("\nExample 2:")
+PWC.solution(15)
+
+IO.puts("\nExample 3:")
+PWC.solution(100)
diff --git a/challenge-285/packy-anderson/perl/ch-1.pl b/challenge-285/packy-anderson/perl/ch-1.pl
new file mode 100755
index 0000000000..bb105df7b4
--- /dev/null
+++ b/challenge-285/packy-anderson/perl/ch-1.pl
@@ -0,0 +1,39 @@
+#!/usr/bin/env perl
+use v5.40;
+
+use Set::Scalar;
+
+sub noConnection(@routes) {
+  my $starts = Set::Scalar->new(map { $_->[0] } @routes);
+  my $ends   = Set::Scalar->new(map { $_->[1] } @routes);
+  my $noConnection = $ends - $starts;
+  return 'no terminal destinations'
+    if $noConnection->is_empty;
+  return 'multiple terminal destinations'
+    if $noConnection->size > 1;
+  return ($noConnection->elements)[0];
+}
+
+sub tupleJoin(@list) {
+  return join(
+    ', ',
+    map { '[' . $_->[0] . ', ' . $_->[1] .  ']' } @list
+  );
+}
+
+sub solution($routes) {
+  say 'Input: @routes = (' . tupleJoin(@$routes) . ')';
+  say 'Output: ' . noConnection(@$routes);
+}
+
+say "Example 1:";
+solution([["B","C"], ["D","B"], ["C","A"]]);
+
+say "\nExample 2:";
+solution([["A","Z"], ]);
+
+say "\nBad Input: multiple terminal destinations";
+solution([["A","B"], ["C", "D"]]);
+
+say "\nBad Input: no terminal destinations";
+solution([["A","Z"], ["Z", "A"]]);
diff --git a/challenge-285/packy-anderson/perl/ch-2.pl b/challenge-285/packy-anderson/perl/ch-2.pl
new file mode 100755
index 0000000000..9070ec739b
--- /dev/null
+++ b/challenge-285/packy-anderson/perl/ch-2.pl
@@ -0,0 +1,80 @@
+#!/usr/bin/env perl
+use v5.40;
+
+use Memoize;
+memoize('makeChange');
+
+# establish the values of the coins
+my %types = (50 => 'HD', 25 => 'Q', 10 => 'D', 5 => 'N', 1 => 'P');
+
+# make a sorted list of coin values
+my @values = sort { $a <=> $b } keys %types;
+
+# handle formatting coins to not display the number 1
+sub formatCoin($coin, $count) {
+  return ( ($count == 1 ? "" : $count) . $coin );
+}
+
+sub makeChange($amount, $exclude = 0) {
+  my @output;
+  foreach my $value (reverse @values) {
+    # if this type of coin is worth more
+    # than the total, we can't use it
+    next if $value > $amount;
+
+    # if we're excluding this coin value or greater, skip it
+    next if $exclude && $value >= $exclude;
+
+    my $coin = $types{$value}; # get the coin name
+
+    if ($value == 1) {
+      # pennies are easy!
+      push @output, formatCoin($coin, $amount);
+    }
+    else {
+      # loop from max number of this coin we can use down to 1
+      foreach my $count ( reverse 1 .. int($amount / $value) ) {
+        # figure out how much change we need after we've used
+        # $count many of coin $coin
+        my $left = $amount - ($count * $value);
+
+        if ($left > 0) { # we need more change
+          # make a recursive call to get the combinations
+          # for that remaining amount, excluding any coins
+          # of equal or greater value to $value
+          my @combinations = makeChange($left, $value);
+          foreach my $combo ( @combinations ) {
+            my $this_coin = formatCoin($coin, $count);
+            push @output, join(" + ", $this_coin, $combo);
+          }
+        }
+        else { # this is exact change!
+          push @output, formatCoin($coin, $count);
+        }
+      }
+    }
+  }
+
+  return @output;
+}
+
+sub solution($amount) {
+  say 'Input: $amount = ' . $amount;
+  my @ways = makeChange($amount);
+  say 'Output: ' . scalar(@ways);
+  say '';
+  my $i = 0;
+  foreach my $c ( @ways ) {
+    $i++;
+    say "$i: $c";
+  }
+}
+
+say "Example 1:";
+solution(9);
+
+say "\nExample 2:";
+solution(15);
+
+say "\nExample 3:";
+solution(100);
diff --git a/challenge-285/packy-anderson/python/ch-1.py b/challenge-285/packy-anderson/python/ch-1.py
new file mode 100755
index 0000000000..18d8eb136f
--- /dev/null
+++ b/challenge-285/packy-anderson/python/ch-1.py
@@ -0,0 +1,32 @@
+#!/usr/bin/env python
+
+def noConnection(routes):
+  starts = set([ x[0] for x in routes ])
+  ends   = set([ x[1] for x in routes ])
+  noConnection = ends - starts
+  if len(noConnection) == 0:
+    return 'no terminal destinations'
+  if len(noConnection) > 1:
+    return 'multiple terminal destinations'
+  return list(noConnection)[0]
+
+def tupleJoin(listVar):
+  return ', '.join([
+     f'[{x[0]}, {x[1]}]' for x in listVar
+  ])
+
+def solution(routes):
+  print(f'Input: @routes = ({ tupleJoin(routes) })')
+  print(f'Output: {noConnection(routes)}')
+
+print('Example 1:')
+solution([["B","C"], ["D","B"], ["C","A"]])
+
+print('\nExample 2:')
+solution([["A","Z"], ])
+
+print('\nBad Input: multiple terminal destination')
+solution([["A","B"], ["C", "D"]])
+
+print('\nBad Input: no terminal destinations')
+solution([["A","Z"], ["Z", "A"]])
diff --git a/challenge-285/packy-anderson/python/ch-2.py b/challenge-285/packy-anderson/python/ch-2.py
new file mode 100755
index 0000000000..01cc096f29
--- /dev/null
+++ b/challenge-285/packy-anderson/python/ch-2.py
@@ -0,0 +1,68 @@
+#!/usr/bin/env python
+
+from functools import cache
+
+# establish the values of the coins
+types = { 50: 'HD', 25: 'Q', 10: 'D', 5: 'N', 1: 'P' }
+
+# make a sorted list of coin values
+values = sorted(types.keys(), reverse=True)
+
+def formatCoin(coin, count):
+  return f"{count}{coin}" if count > 1 else coin
+          
+@cache
+def makeChange(amount, exclude = 0):
+  output = []
+  for value in values:
+    # if this type of coin is worth more
+    # than the total, we can't use it
+    if value > amount:
+      continue
+
+    # if we're excluding this coin value or greater, skip it
+    if exclude and value >= exclude:
+      continue
+
+    coin = types[value] # get the coin name
+
+    if value == 1:
+      # pennies are easy!
+      output.append( formatCoin(coin, amount) )
+    else:
+      # loop from max number of this coin we can use down to 1
+      for count in range(int(amount / value), 0, -1):
+        # figure out how much change we need after we've used
+        # $count many of coin $coin
+        left = amount - (count * value)
+
+        if left > 0: # we need more change
+          # make a recursive call to get the combinations
+          # for that remaining amount, excluding any coins
+          # of equal or greater value to $value
+          combinations = makeChange(left, value)
+          for combo in combinations:
+            this_coin = formatCoin(coin, count)
+            output.append(" + ".join([this_coin, combo]))
+        else: # this is exact change!
+          output.append( formatCoin(coin, count) )
+  return output
+
+def solution(amount):
+  print(f'Input: $amount = {amount}')
+  ways = makeChange(amount)
+  print(f'Output: {len(ways)}')
+  print('')
+  i = 0
+  for c in ways:
+    i += 1
+    print(f'{i}: {c}')
+
+print('Example 1:')
+solution(9)
+
+print('\nExample 2:')
+solution(15)
+
+print('\nExample 3:')
+solution(100)
diff --git a/challenge-285/packy-anderson/raku/ch-1.raku b/challenge-285/packy-anderson/raku/ch-1.raku
new file mode 100755
index 0000000000..8965b70dfe
--- /dev/null
+++ b/challenge-285/packy-anderson/raku/ch-1.raku
@@ -0,0 +1,35 @@
+#!/usr/bin/env raku
+use v6;
+
+sub noConnection(@routes) {
+  my $starts = set @routes.map({ .[0] });
+  my $ends   = set @routes.map({ .[1] });
+  my $noConnection = $ends (-) $starts;
+  return 'no terminal destinations'
+    if $noConnection.elems == 0;
+  return 'multiple terminal destinations'
+    if $noConnection.elems > 1;
+  return $noConnection;
+}
+
+sub tupleJoin(@list) {
+  return @list.map({ '[' ~ .[0] ~ ', ' ~ .[1] ~  ']'})
+              .join(', ');
+}
+
+sub solution(@routes) {
+  say 'Input: @routes = (' ~ tupleJoin(@routes) ~ ')';
+  say 'Output: ' ~ noConnection(@routes);
+}
+
+say "Example 1:";
+solution([["B","C"], ["D","B"], ["C","A"]]);
+
+say "\nExample 2:";
+solution([["A","Z"], ]);
+
+say "\nBad Input: multiple terminal destinations";
+solution([["A","B"], ["C", "D"]]);
+
+say "\nBad Input: no terminal destinations";
+solution([["A","Z"], ["Z", "A"]]);
diff --git a/challenge-285/packy-anderson/raku/ch-2.raku b/challenge-285/packy-anderson/raku/ch-2.raku
new file mode 100755
index 0000000000..2a3d01747f
--- /dev/null
+++ b/challenge-285/packy-anderson/raku/ch-2.raku
@@ -0,0 +1,78 @@
+#!/usr/bin/env raku
+use v6;
+
+use experimental :cached;
+
+# establish the values of the coins
+my %types = 50 => 'HD', 25 => 'Q', 10 => 'D', 5 => 'N', 1 => 'P';
+
+# make a sorted list of coin values
+my @values = %types.keys.sort(*.Int);
+
+# handle formatting coins to not display the number 1
+sub formatCoin($coin, $count) {
+  return ( ($count == 1 ?? "" !! $count) ~ $coin );
+}
+
+sub makeChange($amount, $exclude = 0) is cached {
+  my @output;
+  for @values.reverse -> $value {
+    # if this type of coin is worth more
+    # than the total, we can't use it
+    next if $value > $amount;
+
+    # if we're excluding this coin value or greater, skip it
+    next if $exclude && $value >= $exclude;
+
+    my $coin = %types{$value}; # get the coin name
+
+    if ($value == 1) {
+      # pennies are easy!
+      @output.push( formatCoin($coin, $amount) );
+    }
+    else {
+      # loop from max number of this coin we can use down to 1
+      for Int($amount / $value) ... 1 -> $count {
+        # figure out how much change we need after we've used
+        # $count many of coin $coin
+        my $left = $amount - ($count * $value);
+
+        if ($left > 0) { # we need more change
+          # make a recursive call to get the combinations
+          # for that remaining amount, excluding any coins
+          # of equal or greater value to $value
+          my @combinations = makeChange($left, $value);
+          for @combinations -> $combo {
+            my $this_coin = formatCoin($coin, $count);
+            @output.push([$this_coin, $combo].join(" + "));
+          }
+        }
+        else { # this is exact change!
+          @output.push( formatCoin($coin, $count) );
+        }
+      }
+    }
+  }
+
+  return @output;
+}
+
+sub solution($amount) {
+  say 'Input: $amount = ' ~ $amount;
+  my @ways = makeChange($amount);
+  say 'Output: ' ~ @ways.elems;
+  say '';
+  for @ways.kv -> $i, $c {
+    my $i2 = $i + 1;
+    say "$i2: $c";
+  }
+}
+
+say "Example 1:";
+solution(9);
+
+say "\nExample 2:";
+solution(15);
+
+say "\nExample 3:";
+solution(100);