...making Linux just a little more fun!
Ben Okopnik [ben at linuxgazette.net]
[ If you're not a programmer or a mathematician, you might want to hit
the 'delete' key right about now. Either that, or risk being bored to
tears. Remember, I warned you! ]
As I've just mentioned in my previous post, I've been fiddling with a "max-spread" algorithm - i.e., if I have two lists, and I want the items in the first list to be spread as widely as possible (using the items in the second list as the "padding"), how do I interpolate them?
This can also be stated as follows: given a barbecue, a bunch of pork cubes, and a number of cherry tomatoes, how would you arrange the skewers in such a way that a) there's a pork chunk at the beginning and the end of every skewer, b) each skewer is arranged in as even a manner as possible, and c) you use up all the pork and all the tomatoes?
I got most of the way to a solution - essentially reinventing the Bresenham line algorithm [1] (and the wheel... and fire... sheesh. I'm a very poor mathematician, and a worse statistician), but got scooped by a fellow Perl monk from the Monastery (perlmonks.org) - really nice work on his part. I rewrote his script to actually sort arrays rather than strings and added some guard conditions. Sample output looks like this:
ben@Tyr:~/devel/0$ ./skewer 2 2 pork1|tmt1|tmt2|pork2 ---#00#--- ben@Tyr:~/devel/0$ ./skewer 3 3 pork1|tmt1|tmt2|pork2|tmt3|pork3 ---#00#0#--- ben@Tyr:~/devel/0$ ./skewer 4 4 pork1|tmt1|tmt2|pork2|tmt3|pork3|tmt4|pork4 ---#00#0#0#--- ben@Tyr:~/devel/0$ ./skewer 5 4 pork1|tmt1|pork2|tmt2|pork3|tmt3|pork4|tmt4|pork5 ---#0#0#0#0#--- ben@Tyr:~/devel/0$ ./skewer 7 4 pork1|tmt1|pork2|tmt2|pork3|tmt3|pork4|tmt4|pork5|pork6|pork7 ---#0#0#0#0###---Can you reproduce this algorithm?
[1] https://en.wikipedia.org/wiki/Special:Search?search=Bresenham%20line%20algorithm
-- * Ben Okopnik * Editor-in-Chief, Linux Gazette * https://LinuxGazette.NET *
Karl-Heinz Herrmann [khh at khherrmann.de]
On Wed, 4 Jul 2007 22:50:50 -0400 Ben Okopnik <ben@linuxgazette.net> wrote:
> Can you reproduce this algorithm?I found it a very interesting > exercise, myself.
Hm.... line up all porks, start puting in one tomato in the gaps until tomate are out or alternatively gaps are out. If gaps are out start again at the beginning putting an additional tomato in the gaps. Repeat till tomatoes are gone....
K.-H.
Kapil Hari Paranjape [kapil at imsc.res.in]
Hello,
On Thu, 05 Jul 2007, Karl-Heinz Herrmann wrote:
> On Wed, 4 Jul 2007 22:50:50 -0400 > Ben Okopnik <ben@linuxgazette.net> wrote: > > > Can you reproduce this algorithm?
I think Ben is thinking of a skewer as a LIFO (or perhaps FIFO). So this means that you can't "insert" elements. Some sort of estimate of the rate at which meat/tomato becomes available seems to be required in that case.
Regards,
Kapil. --
Neil Youngman [ny at youngman.org.uk]
On or around Thursday 05 July 2007 08:06, Karl-Heinz Herrmann reorganised a bunch of electrons to form the message:
> On Wed, 4 Jul 2007 22:50:50 -0400 > > Ben Okopnik <ben@linuxgazette.net> wrote: > > Can you reproduce this algorithm?
That's potentially quite uneven, e.g. 8 pork cubes, 2 tomatoes, leaves all tomatoes at one end. I would try something like
assert( pork_cubes > 1 );
gaps = pork_cubes - 1;
fill = tomatoes/gaps;
toms_used = 0;
for( g = 0; g < gaps; ++g )
{
toms_in_gap[g] = ((g+1) *fill) - toms_used;
toms_used += toms_in_gap[g];
}
I think this still biases a little towards one end, but it shouldn't be too
hard to add a little tweak that fixes that.
Neil
Ben Okopnik [ben at linuxgazette.net]
On Thu, Jul 05, 2007 at 12:51:14PM +0530, Kapil Hari Paranjape wrote:
> Hello, > > On Thu, 05 Jul 2007, Karl-Heinz Herrmann wrote: > > On Wed, 4 Jul 2007 22:50:50 -0400 > > Ben Okopnik <ben@linuxgazette.net> wrote: > > > > > Can you reproduce this algorithm?
Actually, the number of tomatoes and meat cubes is known ahead of time (otherwiwise, you're right - you'd have to know the rate - but at that point, it's pretty trivial: figure out the ratio for each item and insert it at that rate.) But Neil is right about Karl-Heinz' suggestion; it fails where the ratios are skewed that way.
-- * Ben Okopnik * Editor-in-Chief, Linux Gazette * https://LinuxGazette.NET *
Ben Okopnik [ben at linuxgazette.net]
On Thu, Jul 05, 2007 at 08:28:19AM +0100, Neil Youngman wrote:
> On or around Thursday 05 July 2007 08:06, Karl-Heinz Herrmann reorganised a > bunch of electrons to form the message: > > On Wed, 4 Jul 2007 22:50:50 -0400 > > > > Ben Okopnik <ben@linuxgazette.net> wrote: > > > Can you reproduce this algorithm?
It's a nice approach - it creates a list of gaps and details how many
tomatoes should be inserted into each gap. However, it still has a
problem - both the tomatoes and the pork chunks are integers (cutting a
tomato to 0.666666666666667 of its original size is a little difficult -
and recombining the remainder with the next tomato down the line is even
more so. Besides, I'm struggling a bit to see how I'd convert that to
an actual interleaved array (it may just be because I'm a bit slow on
the uptake this morning...)
#!/usr/bin/perl -w
# Created by Ben Okopnik on Wed Jul 4 23:31:23 EDT 2007
# Algorithm by Neil Youngman
use strict;
sub interleave {
my ($pork_cubes, $tomatoes) = @_;
# Let's test the tomatoes as well
die "Bad args to interleave\n" unless $pork_cubes > 1 && $tomatoes > 0;
my $gaps = $pork_cubes - 1;
my $fill = $tomatoes/$gaps;
my $toms_used = 0;
my @toms_in_gap;
for (my $g = 0; $g < $gaps; ++$g){
$toms_in_gap[$g] = (($g+1) * $fill) - $toms_used;
$toms_used += $toms_in_gap[$g];
}
return @toms_in_gap;
}
######################## Test section ####################
my @TEST = (
[ 2, 1 ],
[ 2, 2 ],
[ 3, 2 ],
[ 4, 2 ],
[ 4, 3 ],
[ 4, 7 ]
);
for my $ref (@TEST){
print "interleave(@$ref): ", join(" ", interleave(@$ref)), "\n";
}
ben@Tyr:~/devel/0$ ./neil interleave(2 1): 1 interleave(2 2): 2 interleave(3 2): 1 1 interleave(4 2): 0.666666666666667 0.666666666666667 0.666666666666667 interleave(4 3): 1 1 1 interleave(4 7): 2.33333333333333 2.33333333333333 2.33333333333333
-- * Ben Okopnik * Editor-in-Chief, Linux Gazette * https://LinuxGazette.NET *
Neil Youngman [ny at youngman.org.uk]
On or around Thursday 05 July 2007 15:17, Ben Okopnik reorganised a bunch of electrons to form the message:
> On Thu, Jul 05, 2007 at 08:28:19AM +0100, Neil Youngman wrote:
> > I would try something like
> >
> > assert( pork_cubes > 1 );
> > gaps = pork_cubes - 1;
> > fill = tomatoes/gaps;
> > toms_used = 0;
> > for( g = 0; g < gaps; ++g )
> > {
> > toms_in_gap[g] = ((g+1) *fill) - toms_used;
> > toms_used += toms_in_gap[g];
> > }
> >
> > I think this still biases a little towards one end, but it shouldn't be
> > too hard to add a little tweak that fixes that.
>
> It's a nice approach - it creates a list of gaps and details how many
> tomatoes should be inserted into each gap. However, it still has a
> problem - both the tomatoes and the pork chunks are integers (cutting a
> tomato to 0.666666666666667 of its original size is a little difficult -
> and recombining the remainder with the next tomato down the line is even
> more so. Besides, I'm struggling a bit to see how I'd convert that to
> an actual interleaved array (it may just be because I'm a bit slow on
> the uptake this morning...)
Yeah. I didn't really make the mixing of integers and floating point numbers
clear enough. Variables toms_in_gap and toms_used were always meant to be
integers Would something like
toms_in_gap[g] = round(((g+1) *fill) - toms_used);fix it?
Neil
Ben Okopnik [ben at linuxgazette.net]
On Thu, Jul 05, 2007 at 03:26:53PM +0100, Neil Youngman wrote:
> > Yeah. I didn't really make the mixing of integers and floating point numbers > clear enough. Variables toms_in_gap and toms_used were always meant to be > integers
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.
...
use strict;
use POSIX;
...
# $toms_in_gap[$g] = (($g+1) * $fill) - $toms_used;
$toms_in_gap[$g] = floor((($g + 1) * $fill) - $toms_used);
...
# Add a couple more tests
my @TEST = (
[ 2, 1 ],
[ 2, 2 ],
[ 3, 2 ],
[ 4, 2 ],
[ 4, 3 ],
[ 4, 7 ],
[ 5, 14 ],
[ 6, 1 ],
[ 3, 7 ]
);
ben@Tyr:~/devel/0$ ./neil interleave(2 1): 1 interleave(2 2): 2 interleave(3 2): 1 1 interleave(4 2): 0 1 1 interleave(4 3): 1 1 1 interleave(4 7): 2 2 3 interleave(5 14): 3 4 3 4 interleave(6 1): 0 0 0 0 1 interleave(3 7): 3 4Very, very nice! (This isn't what I'd call exhaustive testing, but it's doing what it's supposed to so far.) I guess hacking it into an array isn't all that difficult:
for my $ref (@TEST){
my ($p, $t, @final);
for my $toms (interleave(@$ref)){
push @final, "pork" . ++$p;
push @final, ("tmt" . ++$t) x $toms;
}
push @final, "pork" . ++$p;
# Let's see what it looks like:
print "interleave(@$ref): ", join("|", @final), "\n";
# And, just for fun:
print "\t\t---", join("", grep s/(pork|tmt).*/${{pork => '#', tmt => 0}}{$1}/e,
@final), "---\n\n";
}
...and now we have our skewers, too:
ben@Tyr:~/devel/0$ ./neil
interleave(2 1): pork1|tmt1|pork2
---#0#---
interleave(2 2): pork1|tmt1|tmt1|pork2
---#00#---
interleave(3 2): pork1|tmt1|pork2|tmt2|pork3
---#0#0#---
interleave(4 2): pork1|pork2|tmt2|pork3|tmt3|pork4
---##0#0#---
interleave(4 3): pork1|tmt1|pork2|tmt2|pork3|tmt3|pork4
---#0#0#0#---
interleave(4 7):
pork1|tmt1|tmt1|pork2|tmt2|tmt2|pork3|tmt3|tmt3|tmt3|pork4
---#00#00#000#---
interleave(5 14):
pork1|tmt1|tmt1|tmt1|pork2|tmt2|tmt2|tmt2|tmt2|pork3|tmt3|tmt3|tmt3|pork4|tmt4|tmt4|tmt4|tmt4|pork5
---#000#0000#000#0000#---
interleave(6 1): pork1|pork2|pork3|pork4|pork5|tmt5|pork6
---#####0#---
interleave(3 7): pork1|tmt1|tmt1|tmt1|pork2|tmt2|tmt2|tmt2|tmt2|pork3
---#000#0000#---
This is fun! -- * Ben Okopnik * Editor-in-Chief, Linux Gazette * https://LinuxGazette.NET *
Ben Okopnik [ben at linuxgazette.net]
On Thu, Jul 05, 2007 at 11:08:28AM -0400, Benjamin Okopnik wrote:
Whoops - one correction:
> ```
> for my $ref (@TEST){
> my ($p, $t, @final);
> for my $toms (interleave(@$ref)){
> push @final, "pork" . ++$p;
> push @final, ("tmt" . ++$t) x $toms;
That should be
push @final, "tmt" . ++$t for 1 .. $toms;Can't just repeat the 'tmt$number' part, gotta actually increment it.
-- * Ben Okopnik * Editor-in-Chief, Linux Gazette * https://LinuxGazette.NET *
Neil Youngman [ny at youngman.org.uk]
On or around Thursday 05 July 2007 16:08, Ben Okopnik reorganised a bunch of electrons to form the message:
> On Thu, Jul 05, 2007 at 03:26:53PM +0100, Neil Youngman wrote: > > Yeah. I didn't really make the mixing of integers and floating point > > numbers clear enough. Variables toms_in_gap and toms_used were always > > meant to be integers
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 );
}
> This is fun!
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. There's nothing in there that I would call deep math. All the fancy crypto stuff loses me in no time flat.
Neil
Ben Okopnik [ben at linuxgazette.net]
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!
[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) # https://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 * https://LinuxGazette.NET *