Programmers Contest: Fit pictures on a page

[hicinbothem@ems.att.com]

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]

Re: Programmers Contest: Fit pictures on a page

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

[mensanator@aol.com]

Re: Programmers Contest: Fit pictures on a page



Chung Leong wrote:[color=blue]
> Isn't that an NP-complete problem or am I crazy?[/color]

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]

Re: Programmers Contest: Fit pictures on a page

Chung Leong wrote:
[color=blue]
> Isn't that an NP-complete problem or am I crazy?[/color]

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

[Don]

Re: Programmers Contest: Fit pictures on a page

mensanator@aol. com wrote:
[color=blue]
>
>
> Chung Leong wrote:[color=green]
>> Isn't that an NP-complete problem or am I crazy?[/color]
>
> 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?[/color]

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