#!/usr/local/bin/perl
# Took about 14637 sec to run on words.as
#            > 4 hours

use strict;
use warnings;
use Algorithm::Permute;

my $word1 = "xylidin";
my $word2 = "xylinid";

print min_chunks($word1, $word2), "\n";

sub min_chunks {
  my $str = lc "$_[0]:$_[1]";
  return 1 if $str =~ /^(\w+):\1$/;
  for my $c (2..length($_[0])-1) {
    my $capture = "(\\w+)" x $c;
    $capture = qr/^$capture:/;
    my $aref = [1..$c];
    my $skip = "@$aref";
    my $p = Algorithm::Permute->new($aref);
    while (my @res = $p->next) {
      next if "@res" eq $skip;
      my $backref = join('', map "\\$_", @res);
      if (my @arr = $str =~ /$capture$backref$/) {
        # If you want to see the divisions of the words
        # no strict 'refs';
        # print join("/", @arr), " ", join("/", map $$_, @res), "\n";
        return $c;
      }
    }
  }
  length $_[0];
}
