TWC285

Challenge Link

Task1

We are basically looking for a node in the graph with zero out degree:

#!/usr/bin/env perl
use strict;
use warnings;

sub no_connection{
  my ($arr) = @_;
  my (%destinations,%sources);
  foreach my $r(@{$arr}){
    $sources{$r->[0]} = $destinations{$r->[1]} = 1;
  }
  foreach my $d(keys %destinations){
    return $d unless exists $sources{$d}
  }
  ""
}

printf "%s\n",no_connection([["B","C"],["D","B"],["C","A"]]);
printf "%s\n",no_connection([["A","Z"]]);

Task2

We can use a tree to check for all the possible solutions, but dynamic programming is more efficient:

#!/usr/bin/env perl
use strict;
use warnings;

sub making_change{
  my ($amount) = @_;
  my @coins = (1,5,10,25,50);
  my @dp = (0) x ($amount+1);
  $dp[0] = 1;
  foreach my $c(@coins){
    foreach my $i($c..$amount) {
      $dp[$i] += $dp[$i-$c]
    }
  }
  $dp[$amount]
}

printf "%d\n",making_change(9);
printf "%d\n",making_change(15);
printf "%d\n",making_change(100);