[TAG] Max-spread algorithm

[Ben Okopnik]

On Thu, Jul 05, 2007 at 04:54:21PM +0100, Neil Youngman wrote:
> On or around Thursday 05 July 2007 16:08, Ben Okopnik reorganised a bunch of 
> electrons to form the message:
> >
> > I don't have a 'round', but I can use a 'floor' ("largest integer value
> > less than or equal to the argument) - I think it's what you mean. That
> > one requires the POSIX module, which just happens to be part of Perl.
> 
> floor isn't quite the same as round, e.g. floor( 0.9 ) != round( 0.9 ). You 
> can use floor to simulate round
> 
> float round( float x )
> {
>   return floor( x+0.5 );
> }
 
Since I only used it in one place, I just added 0.5 to the equation.

``
$toms_in_gap[$g] = floor((($g + 1) * $fill) - $toms_used + 0.5);
''
 
> > This is fun! :) Although when I try to figure out how you came up with
> > that algorithm, it's a dark, impenetrable forest to me. You math people
> > are amazing; I wish I spoke the language.
> 
> It's just a question of figuring out the average number of tomatoes you need 
> in each gap and then dealing with the problem that you can't actually slice 
> them up.

[laugh] Well, *yes*, that _is_ the question. Where I have a problem is
in coming up with that question! As I often tell my students, "once
you've stated the problem clearly, the solution should be obvious." In
this case, it was the statement of the problem (not the terms of the
"puzzle", but the mathematical problem inherent in it) that I had to
wrestle with.

Oh - here's the solution from Perlmonks.org. Besides doing it correctly,
this one also tends to produce the most esthetically pleasing results
(nicely balanced distribution of leftover items):

```
#!/usr/bin/perl -w
# "max-spread" algorithm by BrowserUk (perlmonks.org)
# http://perlmonks.org/?node_id=171588)
# Modified by Ben Okopnik on Wed Jul  4 23:31:23 EDT 2007

use strict;

die "Usage: ", $0 =~ /([^\/]+)$/, " <length_of_list_1> <length_of_list_2>\n"
	unless @ARGV == 2 && join("", @ARGV) =~ /^\d+$/;

sub interleave {
    my( $a, $b ) = qw[ a b ];
    my( $as, $bs ) = @_;
    return $a x $as . $b x $bs unless $as >1 and $bs;

    if( $as > $bs ) {
        ++$bs;
        my $aPerB = int( $as / $bs );
        my $aRem = $as - $bs * $aPerB;
        my @as = ( $a x $aPerB ) x $bs;
        my $n = 0;
        $as[ $n ] .= $a, $as[ - ++$n ] .= $a, $aRem -= 2 while $aRem > 1;
        $as[ @as / 2 ] .= $a if $aRem > 0;
        return join $b, @as;
    }
    else {
        --$as;
        my $bPerA = int( $bs / $as );
        my $bRem = $bs - $as * $bPerA;
        my @bs = ( $b x $bPerA ) x $as;
        my $n = 0;
        $bs[ $n ] .= $b, $bs[ - ++$n ] .= $b, $bRem -= 2 while $bRem > 1;
        $bs[ @bs / 2 ] .= $b if $bRem > 0;
        return $a . join( $a, @bs ) . $a;
    }
}

print interleave(@ARGV), "\n";
'''

People on the list are already finding uses for it - e.g., distributing
the spaces in justified text, etc.


-- 
* Ben Okopnik * Editor-in-Chief, Linux Gazette * http://LinuxGazette.NET *