From ab09497e15a0f2aa8cbfca46b7c82f3b8c82bbe0 Mon Sep 17 00:00:00 2001
From: Timofey Potapov <timofey.potapov@otrs.com>
Date: Mon, 21 Nov 2022 20:31:34 +0100
Subject: ch-2 done.

---
 challenge-192/tim-potapov/perl/ch-2.pl | 128 +++++++++++++++++++++++----------
 1 file changed, 90 insertions(+), 38 deletions(-)

diff --git a/challenge-192/tim-potapov/perl/ch-2.pl b/challenge-192/tim-potapov/perl/ch-2.pl
index c1ed1b9a81..12e1a6b03c 100755
--- a/challenge-192/tim-potapov/perl/ch-2.pl
+++ b/challenge-192/tim-potapov/perl/ch-2.pl
@@ -3,61 +3,113 @@
 use strict;
 use warnings;
 use Test::More;
+use List::Util qw( sum uniq );
+use feature    qw(say);
 
 =pod
 
 Task 2: Equal Distribution
 You are given a list of integers greater than or equal to zero, @list.
 
-Write a script to distribute the number so that each members are same. If you succeed then print the total moves otherwise print -1.
-
-Example 1:
-Input: @list = (1, 0, 5)
-Output: 4
-
-Move #1: 1, 1, 4
-(2nd cell gets 1 from the 3rd cell)
-
-Move #2: 1, 2, 3
-(2nd cell gets 1 from the 3rd cell)
-
-Move #3: 2, 1, 3
-(1st cell get 1 from the 2nd cell)
-
-Move #4: 2, 2, 2
-(2nd cell gets 1 from the 3rd cell)
-Example 2:
-Input: @list = (0, 2, 0)
-Output: -1
-
-It is not possible to make each same.
-Example 3:
-Input: @list = (0, 3, 0)
-Output: 2
-
-Move #1: 1, 2, 0
-(1st cell gets 1 from the 2nd cell)
-
-Move #2: 1, 1, 1
-(3rd cell gets 1 from the 2nd cell)
+Write a script to distribute the number so that each members are same.
+If you succeed then print the total moves otherwise print -1.
 
 =cut
 
-sub function {
-    my ( $input ) = @_;
-
+sub equal_shares {
+    my ( $list ) = @_;
+    my $sum      = sum @$list;
+    my $elems    = @$list;
+
+    # Cant's be split since remainder.
+    return -1 if $sum % $elems;
+
+    my $goal_size_per_cell = $sum / $elems;
+    my $count              = 0;
+    my $first_index        = 0;
+    my $last_index         = $#$list;
+    my $n;
+    my $run = sub { uniq( @$list ) > 1 };
+
+    LOOP:
+    while ( $run->() ) {
+        say "";
+        say "loop: (@$list)";
+        for my $i ( $first_index .. $last_index ) {
+            my $val = $list->[$i];
+            next if $val == $goal_size_per_cell;
+
+            # Tool big so lets split the cell.
+            if ( $val > $goal_size_per_cell ) {
+                if ( $i > $first_index ) {
+                    $list->[$i]--;
+                    $list->[ $i - 1 ]++;
+                    $count++;
+                    say "  <-- (@$list)";
+                    last LOOP if not $run->();
+                }
+                if ( $i < $last_index ) {
+                    $list->[$i]--;
+                    $list->[ $i + 1 ]++;
+                    $count++;
+                    say "  --> (@$list)";
+                    last LOOP if not $run->();
+                }
+            }
+        }
+        last if $n++ > 10;    # Stop infinite loop.
+    }
+
+    # After writing this, then I came up with the idea
+    # to use a balanced binary tree approach...
+    # maybe one day.
+
+    $count;
 }
 
 my @cases = (
+
+    {
+        Name   => 'Example 1',
+        Input  => [ 1, 0, 5 ],
+        Output => 4,
+
+        # Move #1: 1, 1, 4
+
+        # (2nd cell gets 1 from the 3rd cell)
+        #
+        # Move #2: 1, 2, 3
+        # (2nd cell gets 1 from the 3rd cell)
+        #
+        # Move #3: 2, 1, 3
+        # (1st cell get 1 from the 2nd cell)
+        #
+        # Move #4: 2, 2, 2
+        # (2nd cell gets 1 from the 3rd cell)
+
+    },
+    {
+        Name   => 'Example 2',
+        Input  => [ 0, 2, 0 ],
+        Output => -1,
+
+        # It is not possible to make each same.
+    },
     {
-        Name   => 'Example1',
-        Input  => 1,
-        Output => 1,
+        Name   => 'Example 3',
+        Input  => [ 0, 3, 0 ],
+        Output => 2,
+
+        # Move #1: 1, 2, 0
+        # (1st cell gets 1 from the 2nd cell)
+        #
+        # Move #2: 1, 1, 1
+        # (3rd cell gets 1 from the 2nd cell)
     },
 );
 
 for ( @cases ) {
-    is function( $_->{Input} ), $_->{Output}, "$_->{Name} - $_->{Input}";
+    is equal_shares( $_->{Input} ), $_->{Output}, $_->{Name};
 }
 
 done_testing();
-- 
cgit