pwc189-2.raku

use v6;

# generate a range delimiting each possible sub array
#
multi sub gensub (@a, $min = 1) {
  gensub(@a.elems, $min)
}

multi sub gensub (Int $n where $n > 0, Int $min = 1) {
  gather {
    for $min..$n -> $len {
    	for 0..($n-$len) -> $start {
	    my $end = $start+$len-1;
	    take $start..$end;
	}
    }
  }
}

sub degree (@a) {
    @a.Bag.values.max;
}

sub smallest_subarray (@in) {

    my $limit = @in.elems;
    my $target = degree(@in);

    gather {

      for gensub(@in, $target) -> $i {

	  last if $i.elems > $limit;

     	  my @sub = @in[@$i];

	  if degree(@sub) == $target {
	     take @sub;
	     $limit = @sub.elems;
	  }
      }
   }
}

do -> @a {

   state $n = 1;
   
   say $n++, ": ", @a, " d:{degree(@a)}\t--> ", smallest_subarray(@a);

} for (
(1, 3, 3, 2),    # Output: (3, 3)
(1, 2, 1, 3),    # Output: (1, 2, 1)
(1, 3, 2, 1, 2), # Output: (2, 1, 2)
(1, 1, 2, 3, 2), # Output: (1, 1)
(2, 1, 2, 1, 1), # Output: (1, 2, 1, 1)
(2, 2, 1, 1),
(2, 1, 2, 1),
(1, 2, 3, 4),
<g a r a g e>,
)