use strict;
use warnings;

my $in_string = q(It should be clear to any frequent
air passenger that in order to reach one city from another the cost of the shorter flight may be more than the cost of longer flights.
In other words, it may pay you well to cool your heels in an airport waiting for a connecting flight rather than take a 
more direct flight or one in which the connecting time is shorter. For example, consider the following flight schedule.); 


#
# Work out how many spaces are needed in the text in total and divide by
# the number of lines to get an approximate number of spaces per line. 
# Break the text into lines on total word lengths assuming this number 
# of spaces is added to each line.
# Recalculate the break points after each line.
#

my $NO_OF_LINES   = 12;
my $CHAR_PER_LINE = 45;

# check it is not impossible
if ( length($in_string) > ($NO_OF_LINES * $CHAR_PER_LINE) ){ die "Can't be done\n" };

# split into words and calculate total characters
my @words = split /\s/,$in_string;
my $total_chars = 0;
for (@words){
  $total_chars += length($_);  ;
}

# how many spaces must there be in the text
my $spaces_to_add = ( $NO_OF_LINES * $CHAR_PER_LINE ) - $total_chars;

# initialize
my $line="";
my $lines_left  = $NO_OF_LINES;
my $space_avail = $CHAR_PER_LINE - int ( $spaces_to_add / $lines_left ) ;

# process
for my $w (@words){
   my $w_length = length($w); 

   if ( $w_length == $space_avail ){
     $line .= $w;
     $w = "";
   } else {
     if ( $w_length < $space_avail ){
       $line .= "$w ";
       $space_avail -= $w_length;
       --$spaces_to_add;
       next;
     }
   }
       
   # reduce by those that will be added when justified
   $spaces_to_add -= ( $CHAR_PER_LINE - length($line) );

   # print the result
   print &justify_line($line)."|\n";

   # recalculate space_available for characters for the next lines
   --$lines_left;
   if ($lines_left > 1){
     $space_avail = $CHAR_PER_LINE - int ( $spaces_to_add  / $lines_left ) ;
   } else {
     $space_avail = $CHAR_PER_LINE - $spaces_to_add ;
   }

   # prepare next line
   $line = $w;
   if ($w ne ""){
     $line .= " ";
     --$spaces_to_add;
     $space_avail -= length($w);
   } 

}

#
# add spaces between words to justify a line
#
sub justify_line {

  my @words = split ' ',shift;
  my $spaces_left = $CHAR_PER_LINE;  
  for (@words){$spaces_left -= length($_)};
  my $new_line = $words[0];

  # add equal space to each word 
  for my $i (1..$#words){
    # calc number a spaces per word
    my $no_of_spaces = int ($spaces_left / ($#words + 1 - $i));
    $spaces_left -= $no_of_spaces;
    $new_line .= " " x $no_of_spaces . $words[$i];
  }
  return $new_line; 
};