Programmers Contest: Fit pictures on a page

[hicinbothem]

GLOSSY: The Summer Programmer Of The Month Contest is underway!
Deadline is September 30, 2005
http://dinsights.com/POTM
--------------------------------------------------------------------------------
I love taking digital pictures, but that nice glossy photo paper
is expensive! So when my lovely wife asks for prints of a bunch
of pictures, I always try and fit them onto a single piece of paper.

The summer POTM challenges you to write a program that will place up to
26 pictures on a sheet of paper with the least amount of leftover
space.
--------------------------------------------------------------------------------
The Programmer Of The Month (POTM) is a just-for-fun programming
contest with an active forum and over 1100 members (we usually
get 40-50 entries for each POTM challenge). Supported languages
include C/C++/Perl/Ruby/PHP/Python/awk/shell.
Emphasis is on the algorithms and the joy of programming.

If it sounds like fun, please visit at http://dinsights.com/POTM ...
=Fred (a.k.a. The POTM-MASTER)

 

[Chung Leong]

Isn't that an NP-complete problem or am I crazy?

 

[mensanator]

Isn't that an NP-complete problem or am I crazy?

That makes it a more realistic challange, doesn't it?

Suppose it was something simple, like calculating a
minimal spanning tree. Every program would produce the
same output. What kind of contest would that be?

 

[Don]

Isn't that an NP-complete problem or am I crazy?

It is NP complete. Its known as the "cutting stock problem" (aka "Knapsack
problem"). Here's a Wikipedia page that describes it:

http://en.wikipedia.org/wiki/Cutting_stock_problem

There are commerical applications available that "solve" the problem in 2D
for use in the woodworking industry (among others). This is generally done
to minimize waste when cutting down panels (plywood, etc) into smaller
pieces for cabinets, etc.

-Don

 

[mensanator]

It is NP complete. Its known as the "cutting stock problem" (aka "Knapsack
problem"). Here's a Wikipedia page that describes it:

http://en.wikipedia.org/wiki/Cutting_stock_problem

There are commerical applications available that "solve" the problem in 2D
for use in the woodworking industry (among others). This is generally done
to minimize waste when cutting down panels (plywood, etc) into smaller
pieces for cabinets, etc.

Not the same. Read the contest rules. You are allowed to change the
size
and shape (do a certain degree). You certainly can't arbitrarily change
the sizes in a woodworking environment.

 

[Roy Smith]

It is NP complete. Its known as the "cutting stock problem" (aka "Knapsack
problem"). Here's a Wikipedia page that describes it:

http://en.wikipedia.org/wiki/Cutting_stock_problem

There are commerical applications available that "solve" the problem in 2D
for use in the woodworking industry (among others). This is generally done
to minimize waste when cutting down panels (plywood, etc) into smaller
pieces for cabinets, etc.

-Don

Not just plywood panels, but sheets of paper, bolts of cloth, sheet metal,
plate glass, etc. A slight complication is that some materials have a
preferred orientation (i.e. plywood has a grain, textiles have warp vs.
weft, etc) and some don't (or it doesn't matter for the application).

It gets even more interesting when you're restricted to making cuts that
start at an edge, or go all the way through the sheet to the other side.

My first introduction to the problem was helping my grandmother cut cookies
out of a sheet of dough. I can't think of a better way to get introduced
to higher math

 

[Dan Sommers]

Not just plywood panels, but sheets of paper, bolts of cloth, sheet
metal, plate glass, etc. A slight complication is that some materials
have a preferred orientation (i.e. plywood has a grain, textiles have
warp vs. weft, etc) and some don't (or it doesn't matter for the
application).

It gets even more interesting when you're restricted to making cuts
that start at an edge, or go all the way through the sheet to the
other side.

I ran into this problem when I worked at a small computer store back in
1979 or 1980. One of our customers owned a plastics plant, and found
such a program, and wanted us to install it and maintain it (on an 8080
or a Z-80 running CP/M, no less).

The first release only did rectangles, and assumed flawless material, so
his first trial was to tell the program about a 4 x 8 foot sheet of
plastic, and ask for two 4 x 4 pieces. The program refused, because a
saw blade has a non-zero width. But he had mis-specified the problem,
because a 4 x 8 sheet of plastic was really a half-inch (or some small
amount) bigger in both directions.

Anyway, after a couple more years and a few more releases, the program
could handle arbitrary polygons, shapes with various types of curved
edges, arbitrary flaws in the material (mostly for knots in sheets of
plywood), and I'm sure a few more things I don't remember right now. It
could also beat his "best guy."

Regards,
Dan

 

[Don]

That makes it a more realistic challange, doesn't it?

Suppose it was something simple, like calculating a
minimal spanning tree. Every program would produce the
same output. What kind of contest would that be?

I was thinking maybe you could use a genetic algorithm, where the fitness
function would caluclate the amount of waste. I'm not very familar with how
to implement this sort of thing, though.

-Don

 

[Peter Hansen]

I was thinking maybe you could use a genetic algorithm, where the fitness
function would caluclate the amount of waste. I'm not very familar with how
to implement this sort of thing, though.

This problem is well suited to the abilities of genetic algorithms, and
this would probably be an excellent way to learn more about them, even
if you don't get the best solution.

-Peter

 

[Dan Sommers]

This problem is well suited to the abilities of genetic algorithms,
and this would probably be an excellent way to learn more about them,
even if you don't get the best solution.

There's some sort of irony or something in there about not writing the
best genetic algorithm, but I can't quite put my finger on it.

Regards,
Dan

 

[Edvard Majakari]

There's some sort of irony or something in there about not writing the
best genetic algorithm, but I can't quite put my finger on it.

+1 QOTW

--
# Edvard Majakari Software Engineer
# PGP PUBLIC KEY available Soli Deo Gloria!

$_ = '456476617264204d616a616b6172692c20612043687269737469616e20'; print
join('',map{chr hex}(split/(\w{2})/)),uc substr(crypt(60281449,'es'),2,4),"\n";

 

[Peter Hansen]

There's some sort of irony or something in there about not writing the
best genetic algorithm, but I can't quite put my finger on it.

Maybe your irony sensor is getting muddled over the fact that genetic
algorithms generally *don't* find the best solutions, just relatively
good ones. They aren't an exhaustive search, they're basically a random
search with some features thought to focus the search on more fruitful
parts of the solution space, thus optimizing it. Unless *my* irony
processors are malfunctioning, I don't think there's anything ironic
about this. (If anything it looks like the exact opposite of irony, to me.)

-Peter

 

[Brian van den Broek]

Peter Hansen said unto the world upon 01/07/2005 11:47:

Maybe your irony sensor is getting muddled over the fact that genetic
algorithms generally *don't* find the best solutions, just relatively
good ones. They aren't an exhaustive search, they're basically a random
search with some features thought to focus the search on more fruitful
parts of the solution space, thus optimizing it. Unless *my* irony
processors are malfunctioning, I don't think there's anything ironic
about this. (If anything it looks like the exact opposite of irony, to me.)

-Peter

Well, I found it ironic, but only when you add that the genetic
algorithm approach came up in the context of a "best fit" problem.
Survival of the fittest indeed

Best,

Brian vdB

 

[Robert Kern]

Well, I found it ironic, but only when you add that the genetic
algorithm approach came up in the context of a "best fit" problem.
Survival of the fittest indeed

Optimization codes don't always succeed. What's the irony?

--
Robert Kern
(e-mail address removed)

"In the fields of hell where the grass grows high
Are the graves of dreams allowed to die."
-- Richard Harter

 

[Brian van den Broek]

Robert Kern said unto the world upon 01/07/2005 17:24:

Brian van den Broek wrote:




Optimization codes don't always succeed. What's the irony?

Well, the punning on 'fit' (fittest in the sense of "most suitable, or
best adapted", appropriate to Darwinian theory vs. fit in the sense of
"to be of the right measure or proper shape and size for") amused me.

There is at least shades of irony in that the best fit in the
Darwinian sense appropriate to genetic algorithms needn't be the best
fit in the sense of proper size and shape. So, in suitable
circumstances, the meaning of "best fit" in one sense being the
opposite of what was intended in the other. (As in, my sense that it
was ironic didn't reside solely in the genetic algorithm's possible
failure to find the optimal solution, but how the semantic ambiguity
of fit plugs into that in the context of the original problem.) I'd
call that at least semi-irony.

(Yes, I get that the best fit for both evolutionary theory and the
genetic algorithm isn't the absolutely best adapted, but best adapted
as measured relative to the contrast class of available
alternatives--a local maximum if you like.)

All in all, I wish I'd not hit send in the first place. This is
perilously close to sending me into fits ;-)

Best,

Brian vdB

 

[Terry Hancock]

All in all, I wish I'd not hit send in the first place. This is
perilously close to sending me into fits ;-)

Well, I thought it was funny, anyway. Of course, not when you
have to explain it. ;-)

I guess you just have to have a strong sense of humor to
appreciate it.

 

[tassach]

It is NP complete. Its known as the "cutting stock problem" (aka "Knapsack
problem"). Here's a Wikipedia page that describes it:

http://en.wikipedia.org/wiki/Cutting_stock_problem

There are commerical applications available that "solve" the problem in 2D
for use in the woodworking industry (among others). This is generally done
to minimize waste when cutting down panels (plywood, etc) into smaller
pieces for cabinets, etc.

-Don

For photos, it's a lot simpler, assuming you only want make standard
size prints (IE: 8x10, 5x7, 4x6, 2.5x3.5). There are a very limited
number of combinations of the standard print sizes which will fit on an
8.5x11 sheet of paper. This could probably be solved pretty easily
with just a lookup table.

Also, you have to remember that paper cost is only part of the equation
when printing photos -- you also have to consider ink costs. In the
stock cutting problem, it's assumed that the cutting cost is
insignificant. Given the insane cartidge costs for inkjet printers,
wasting a little paper -- even expensive paper -- is likely to be a
more economical than wasting ink.