Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Ruby > Programmers Contest: Fit pictures on a page

Reply
Thread Tools

Programmers Contest: Fit pictures on a page

 
 
hicinbothem@ems.att.com
Guest
Posts: n/a
 
      06-29-2005
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)

 
Reply With Quote
 
 
 
 
Randy Kramer
Guest
Posts: n/a
 
      06-29-2005
On Wednesday 29 June 2005 10:30 am, http://www.velocityreviews.com/forums/(E-Mail Removed) wrote:
> 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.


Do you want to constrain the solutions a little more? A trivial solution that
wastes no paper (regardless of paper size) is to print 2 rows of 13 pictures,
and resize each picture to fit in that space.

Randy Kramer


 
Reply With Quote
 
 
 
 
marcus baker
Guest
Posts: n/a
 
      06-29-2005
It'd be pretty facetious resizing the images - I mean, if you're going
to resize at all just to win you might as well just every image to one
or two pixels squared and fit it on the paper.

The point of the sport is obviously to stick with the original,
unresized images of arbitrary dimensions and coming up with an
algorithm to conserve as much canvas as possible laying them down.

On 6/29/05, Randy Kramer <(E-Mail Removed)> wrote:
> On Wednesday 29 June 2005 10:30 am, (E-Mail Removed) wrote:
> > 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.

>=20
> Do you want to constrain the solutions a little more? A trivial solution=

that
> wastes no paper (regardless of paper size) is to print 2 rows of 13 pictu=

res,
> and resize each picture to fit in that space.
>=20
> Randy Kramer
>=20
>



 
Reply With Quote
 
Randy Kramer
Guest
Posts: n/a
 
      06-29-2005
On Wednesday 29 June 2005 12:12 pm, marcus baker wrote:
> It'd be pretty facetious resizing the images - I mean, if you're going
> to resize at all just to win you might as well just every image to one
> or two pixels squared and fit it on the paper.
>
> The point of the sport is obviously to stick with the original,
> unresized images of arbitrary dimensions and coming up with an
> algorithm to conserve as much canvas as possible laying them down.


Ok!

Randy Kramer


 
Reply With Quote
 
Karl von Laudermann
Guest
Posts: n/a
 
      06-29-2005
marcus baker wrote:
> It'd be pretty facetious resizing the images - I mean, if you're going
> to resize at all just to win you might as well just every image to one
> or two pixels squared and fit it on the paper.
>
> The point of the sport is obviously to stick with the original,
> unresized images of arbitrary dimensions and coming up with an
> algorithm to conserve as much canvas as possible laying them down.


But that doesn't make sense either; if all pictures remain at their
original size, then all possible solutions will have the same amount of
leftover space. That is, the amount of leftover space will be equal to
the area of the page minus the sum of the areas of all of the pictures,
regardless of how they're arranged. And what if a particular picture is
to big to fit on the page at all? Randy was right, the problem is
poorly defined.

> On Wednesday 29 June 2005 10:30 am, (E-Mail Removed) wrote:
> > 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.


> Do you want to constrain the solutions a little more? A trivial solution that
> wastes no paper (regardless of paper size) is to print 2 rows of 13 pictures,
> and resize each picture to fit in that space.


> Randy Kramer


 
Reply With Quote
 
gabriele renzi
Guest
Posts: n/a
 
      06-29-2005
marcus baker ha scritto:
> It'd be pretty facetious resizing the images - I mean, if you're going
> to resize at all just to win you might as well just every image to one
> or two pixels squared and fit it on the paper.
>
> The point of the sport is obviously to stick with the original,
> unresized images of arbitrary dimensions and coming up with an
> algorithm to conserve as much canvas as possible laying them down.


emh.. sorry, but I have the feeling this is a rephrasing of the Knapsack
problem, am I wrong?
 
Reply With Quote
 
Phrogz
Guest
Posts: n/a
 
      06-29-2005
Karl, I think you are (incorrectly) assuming that all the pictures have
the same size or aspect ratio. It's a bin-packing problem. Given a
fixed-size space and differing-sized objects, the ways in which they
are placed very much affect the amount of leftover space.

 
Reply With Quote
 
Michael Campbell
Guest
Posts: n/a
 
      06-29-2005
On 6/29/05, Phrogz <(E-Mail Removed)> wrote:

> Karl, I think you are (incorrectly) assuming that all the pictures have
> the same size or aspect ratio. It's a bin-packing problem. Given a
> fixed-size space and differing-sized objects, the ways in which they
> are placed very much affect the amount of leftover space.


How so? Given that any suitable, rule-conforming arrangement of
objects has them all inside the bin, no overlapping, etc., the volume
of the bin - the sum of the volume of the objects =3D leftover volume;
how they are placed nor how they are shaped has any bearing on the
problem. It SOUNDS like the OP is trying to maximize the
"contiguousness" of the leftover space, but that's not how it reads.=20
Not even sure how you'd measure that; minimize the magnitude of the of
the length of the perimiter?

Is the problem then to see HOW one might place 'n' rectangular shapes
inside a rectangular boundry such that none of the placed shapes
overlap each other, nor exceed the perimeter of the boundry?

Or is it possibly, what's the minimum number of (uniformly
dimensioned?) boundries required to FIT the n shapes? THIS sort of
problem is one I come across regularly in woodworking; how do I
minimize the number of sheets of plywood (etc.) needed to cut out all
the pieces of a given construction?


 
Reply With Quote
 
Chung Leong
Guest
Posts: n/a
 
      06-29-2005
Isn't that an NP-complete problem or am I crazy?

 
Reply With Quote
 
Belorion
Guest
Posts: n/a
 
      06-29-2005
> Or is it possibly, what's the minimum number of (uniformly
> dimensioned?) boundries required to FIT the n shapes? THIS sort of
> problem is one I come across regularly in woodworking; how do I
> minimize the number of sheets of plywood (etc.) needed to cut out all
> the pieces of a given construction?


I *think* that is probably what they were trying to get at. Lets say
you have 50 pictures of varying sizes. The problem then is to try to
minimize the number of pages that are needed to print all 50 pictures.


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Do most programmers know where the fit in the larger scope of things? DaveB C++ 3 05-17-2010 01:17 PM
Programmers Contest: Fit pictures on a page hicinbothem@ems.att.com Python 16 07-06-2005 04:13 PM
Programming Contest: Fit pictures on a page hicinbothem@ems.att.com C++ 0 06-29-2005 02:26 PM
Programming Contest: Fit pictures on a page hicinbothem@ems.att.com C Programming 0 06-29-2005 02:26 PM
Make wxListCtrl fit around contents and parent frame fit around listctrl Piet Python 0 07-18-2004 08:27 AM



Advertisments