sub min_chunks {
  my($w1, $w2) = @_;

  # this hash will be sent through the recursive function
  #  to short-circuit non-optimal solutions
  my(%data_collection) = (
                      BEST => length($w1) + 1,
                     );

  # perform the comparision
  recursive_compare(lc $w1, lc $w2, 1, [ ], \%data_collection);

  # indicates that we found at least one anagram
  if ($data_collection{BEST} <= length($w1)) {
    # print "Smallest decomposition: $data_collection{BEST}\n";
    # print join('', map { "($_)" } @{$data_collection{CHUNKS}}), "\n";
    return $data_collection{BEST};
  } else {
    # print "Hey, they weren't anagrams at all!!\n";
    return undef;
  }
}

sub recursive_compare {
  my($w1, $w2, $depth, $words, $shared_ref) = @_;

  for (my $i = length($w1) ; $i >= 1 ; $i--) {
    # fragment we are looking for in second string
    my $test_word = substr($w1, 0, $i);

    # rest of fragment to send recursively
    my $next_w1 = substr($w1, $i);

    # go through all instances of word fragment in second word - this
    while($w2 =~ /$test_word/g) {
      # form the next word - the space is required so that further
      #  chunks can't be made over the gap of the chunk we are removing
      my $next_w2= $` . " " . $';

      # indicates that entire second word has been replaced
      if ((" " x $depth eq $next_w2) and (not $next_w1)) {
        # note the new best score, and save the words for later
        $shared_ref->{BEST} = $depth;
        $shared_ref->{CHUNKS} = [ @$words, $test_word ]
      } elsif (($depth + 1) < $shared_ref->{BEST}) {
        # go down a level only if its a potential optimal solution
        #  - keep track of seen word list and depth
        recursive_compare($next_w1, $next_w2, $depth + 1,
                          [ @$words, $test_word ], $shared_ref);
      }
    }
  }
}

