#! /usr/bin/env raku

subset GENESTRING where * ~~ /^ <[ACGT]> ** 8 $/;

unit sub MAIN (GENESTRING $start,
               GENESTRING $end,
               *@bank where @bank.elems > 0 && all(@bank) ~~ GENESTRING,
               :v(:$verbose));

if $start eq $end
{
  say ": start=end" if $verbose;
  say 0;
  exit;
}

my %bank = @bank.Bag;

unless %bank{$end}
{
  say ": $end is not in the bank" if $verbose;
  say -1;
  exit;
}

my @queue      = $start;
my @seen-order = $start;
my %seen       = $start => 1;
my %parent;
my $steps = 0;

while @queue
{
  $steps++;
  my @next;

  for @queue -> $gene
  {
    for $gene.comb.kv -> $i, $orig
    {
      for <A C G T> -> $c
      {
        next if $c eq $orig;
        my $mut = $gene.substr(0, $i) ~ $c ~ $gene.substr($i + 1);
        next unless %bank{$mut} && !%seen{$mut};
        %parent{$mut} = $gene;

        if $mut eq $end
        {
          my @path = $end;
          my $g    = $end;
          while %parent{$g}
          {
            $g = %parent{$g};
            @path.push: $g;
          }
          for @path.reverse -> $g
          {
            say ": $g" if $verbose;
          }
          say $steps;
          exit;
        }

        @seen-order.push: $mut;
        %seen{$mut} = 1;
        @next.push: $mut;
      }
    }
  }

  @queue = @next;
}

for @seen-order -> $g
{
  say ": $g" if $verbose;
}

say -1;