Re: Programmers Contest: Fit pictures on a page

[tassach]

Don wrote:
> Chung Leong wrote:
>
> > 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

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.

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Programmers Contest: Fit pictures on a page

[Terry Hancock]

On Friday 01 July 2005 06:25 pm, Brian van den Broek wrote:
> 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.

--
Terry Hancock ( hancock at anansispaceworks.com )
Anansi Spaceworks  http://www.anansispaceworks.com

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Programmers Contest: Fit pictures on a page

[Brian van den Broek]

Robert Kern said unto the world upon 01/07/2005 17:24:
> Brian van den Broek wrote:
> 
> 
>>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?
> 

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


-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Programmers Contest: Fit pictures on a page

[Robert Kern]

Brian van den Broek wrote:

> 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
[EMAIL PROTECTED]

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

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Programmers Contest: Fit pictures on a page

[Brian van den Broek]

Peter Hansen said unto the world upon 01/07/2005 11:47:
> Dan Sommers wrote:
> 
>>Peter Hansen <[EMAIL PROTECTED]> wrote:
>>
>>>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.
> 
> 
> 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

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Programmers Contest: Fit pictures on a page

[Peter Hansen]

Dan Sommers wrote:
> Peter Hansen <[EMAIL PROTECTED]> wrote:
>>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.

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
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Programmers Contest: Fit pictures on a page

[Edvard Majakari]

Dan Sommers <[EMAIL PROTECTED]> writes:

> 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";
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Programmers Contest: Fit pictures on a page

[Dan Sommers]

On Thu, 30 Jun 2005 13:09:02 -0400,
Peter Hansen <[EMAIL PROTECTED]> wrote:

> 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

-- 
Dan Sommers

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Programmers Contest: Fit pictures on a page

[Peter Hansen]

Don wrote:
> 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
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Programmers Contest: Fit pictures on a page

[Don]

[EMAIL PROTECTED] wrote:

> 
> 
> Chung Leong wrote:
>> 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?

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

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Programmers Contest: Fit pictures on a page

[Dan Sommers]

On Wed, 29 Jun 2005 19:43:33 -0400,
Roy Smith <[EMAIL PROTECTED]> wrote:

> 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

-- 
Dan Sommers

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Programmers Contest: Fit pictures on a page

[Roy Smith]

In article <[EMAIL PROTECTED]>,
 Don <[EMAIL PROTECTED]> wrote:

> Chung Leong wrote:
> 
> > 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

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 :-)
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Programmers Contest: Fit pictures on a page

[[EMAIL PROTECTED]]

Don wrote:
> Chung Leong wrote:
>
> > 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.

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.

> 
> -Don

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Programmers Contest: Fit pictures on a page

[Don]

Chung Leong wrote:

> 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

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Programmers Contest: Fit pictures on a page

[[EMAIL PROTECTED]]

Chung Leong wrote:
> 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?

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Programmers Contest: Fit pictures on a page

[Chung Leong]

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

-- 
http://mail.python.org/mailman/listinfo/python-list

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)

-- 
http://mail.python.org/mailman/listinfo/python-list