1 #!/usr/bin/perl
  2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-212/#TASK2
  3 #
  4 # Task 2: Rearrange Groups
  5 # ========================
  6 #
  7 # You are given a list of integers and group size greater than zero.
  8 #
  9 # Write a script to split the list into equal groups of the given size where
 10 # integers are in sequential order. If it can’t be done then print -1.
 11 #
 12 ## Example 1:
 13 ##
 14 ## Input: @list = (1,2,3,5,1,2,7,6,3) and $size = 3
 15 ## Output: (1,2,3), (1,2,3), (5,6,7)
 16 #
 17 ## Example 2:
 18 ##
 19 ## Input: @list = (1,2,3) and $size = 2
 20 ## Output: -1
 21 #
 22 ## Example 3:
 23 ##
 24 ## Input: @list = (1,2,4,3,5,3) and $size = 3
 25 ## Output: (1,2,3), (3,4,5)
 26 #
 27 ## Example 4:
 28 ##
 29 ## Input: @list = (1,5,2,6,4,7) and $size = 3
 30 ## Output: -1
 31 #
 32 ############################################################
 33 ##
 34 ## discussion
 35 ##
 36 ############################################################
 37 #
 38 # We can basically sort the elements of the array, then always try
 39 # to (group size) elements from that array starting at the smallest
 40 # element. If we can always do that, we return those results. If we
 41 # can't in any point, we can return -1.
 42 # In order to make this easier, we can count each element and keep the
 43 # count in a hash table the keys of which equate the elements from the
 44 # original list and the value is the count of this element in that
 45 # list.
 46 
 47 use strict;
 48 use warnings;
 49 use List::Util qw(min);
 50 
 51 rearrange_groups([1,2,3,5,1,2,7,6,3], 3);
 52 rearrange_groups([1,2,3], 2);
 53 rearrange_groups([1,2,4,3,5,3], 3);
 54 rearrange_groups([1,5,2,6,4,7], 3);
 55 rearrange_groups([1,5,2,6,4,7], 2);
 56 
 57 sub rearrange_groups {
 58    my ($list, $size) = @_;
 59    print "Input: (" . join(",", @$list) . "); $size\n";
 60    my $data;
 61    # count all elements into the hash %$data
 62    foreach my $elem (@$list) {
 63       $data->{$elem}++;
 64    }
 65    # start with the minimum key
 66    my $min = min(keys(%$data));
 67    my @result = ();
 68    # as long as there is still some data
 69    while(defined($min)) {
 70       my @tmp = ();
 71       # find up to "size" sequential elements
 72       foreach my $cur (0..$size-1) {
 73          if($data->{$min+$cur}) {
 74             # if there is such an element, add it to our
 75             # current temporary sub-result, decrease the
 76             # counter in this hash element, and remove
 77             # the element from the hash altogether if it
 78             # was the last for this key.
 79             push @tmp, ($min+$cur);
 80             $data->{$min+$cur}--;
 81             delete $data->{$min+$cur} unless $data->{$min+$cur};
 82          } else {
 83             # not enough sequential elements found, we're done here
 84             print "Output: -1\n";
 85             return;
 86          }
 87       }
 88       # OK, we found one result set to put on our result, then
 89       # we can continue with the new minimum key in the hash
 90       push @result, [ @tmp ];
 91       $min = min(keys(%$data));
 92    }
 93    # Let's output the result that we found
 94    print "Output: ";
 95    my $first = 1;
 96    foreach my $arr (@result) {
 97       print ", " unless $first;
 98       print "(" . join(",", @$arr) . ")";
 99       $first = 0;
100    }
101    print "\n";
102 }
103