...making Linux just a little more fun!

Ben Okopnik [ben at linuxgazette.net]

Wed, 4 Jul 2007 22:50:50 -0400

[ 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? I found it a very interesting exercise, myself.

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

Top    Back

Karl-Heinz Herrmann [khh at khherrmann.de]

Thu, 5 Jul 2007 09:06:30 +0200

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.

Top    Back

Kapil Hari Paranjape [kapil at imsc.res.in]

Thu, 5 Jul 2007 12:51:14 +0530

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 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....
```

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. --

Top    Back

Neil Youngman [ny at youngman.org.uk]

Thu, 5 Jul 2007 08:28:19 +0100

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?  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....
```

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

Top    Back

Ben Okopnik [ben at linuxgazette.net]

Thu, 5 Jul 2007 09:24:47 -0400

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?  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....
>
> 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.
```

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 * http://LinuxGazette.NET *
```

Top    Back

Ben Okopnik [ben at linuxgazette.net]

Thu, 5 Jul 2007 10:17:40 -0400

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?  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....
>
> 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.
```

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 * http://LinuxGazette.NET *
```

Top    Back

Neil Youngman [ny at youngman.org.uk]

Thu, 5 Jul 2007 15:26:53 +0100

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

Top    Back

Ben Okopnik [ben at linuxgazette.net]

Thu, 5 Jul 2007 11:08:28 -0400

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  Would something like
>
>   toms_in_gap[g] = round(((g+1) *fill) - toms_used);
>
> fix it?
```

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 4
```
Very, 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! 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.

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

Top    Back

Ben Okopnik [ben at linuxgazette.net]

Thu, 5 Jul 2007 11:14:40 -0400

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 * http://LinuxGazette.NET *
```

Top    Back

Neil Youngman [ny at youngman.org.uk]

Thu, 5 Jul 2007 16:54:21 +0100

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  Would something like
> >
> >   toms_in_gap[g] = round(((g+1) *fill) - toms_used);
> >
> > fix it?
>
> 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 );
}
```
```> 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. There's nothing in there that I would call deep math. All the fancy crypto stuff loses me in no time flat.

Neil

Top    Back

Ben Okopnik [ben at linuxgazette.net]

Thu, 5 Jul 2007 12:46:31 -0400

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 *
```

Top    Back