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;
}

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];
}

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 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

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;
}

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;
}

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

  # 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