Programmers Contest: Fit pictures on a page

Discussion in 'Ruby' started by hicinbothem@ems.att.com, Jun 29, 2005.

  1. Guest

    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)
     
    , Jun 29, 2005
    #1
    1. Advertisements

  2. Randy Kramer Guest

    On Wednesday 29 June 2005 10:30 am, 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
     
    Randy Kramer, Jun 29, 2005
    #2
    1. Advertisements

  3. marcus baker Guest

    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 <> wrote:
    > On Wednesday 29 June 2005 10:30 am, 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
    >
     
    marcus baker, Jun 29, 2005
    #3
  4. Randy Kramer Guest

    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
     
    Randy Kramer, Jun 29, 2005
    #4
  5. 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, 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
     
    Karl von Laudermann, Jun 29, 2005
    #5
  6. 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?
     
    gabriele renzi, Jun 29, 2005
    #6
  7. Phrogz Guest

    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.
     
    Phrogz, Jun 29, 2005
    #7
  8. On 6/29/05, Phrogz <> 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?
     
    Michael Campbell, Jun 29, 2005
    #8
  9. Chung Leong Guest

    Isn't that an NP-complete problem or am I crazy?
     
    Chung Leong, Jun 29, 2005
    #9
  10. Belorion Guest

    > 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.
     
    Belorion, Jun 29, 2005
    #10
  11. Bill Guindon Guest

    On 6/29/05, Michael Campbell <> wrote:
    > On 6/29/05, Phrogz <> wrote:
    >=20
    > > 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.

    >=20
    > 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.
    > Not even sure how you'd measure that; minimize the magnitude of the of
    > the length of the perimiter?


    Yeah, I read it as maximizing the remaining "usable" space - but I
    don't see how you would define that either.
    =20
    > 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?


    Well, there was the clause "up to 26 pictures", so possibly it's a
    comparison of algorithms based on how many of the 26 you could fit.=20
    If their total area is larger than the sheets total area, then it
    would get interesting.

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


    Used to love reading the pop-sci plywood contests. Watching people
    build spiral staircases out of 4 sheets of plywood and other
    silliness. good stuff :)

    --=20
    Bill Guindon (aka aGorilla)
     
    Bill Guindon, Jun 29, 2005
    #11
  12. Guest

    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?
     
    , Jun 29, 2005
    #12
  13. Randy Kramer Guest

    On Wednesday 29 June 2005 05:00 pm, mathew wrote:
    > That's not a trivial solution at all, as almost the entire sheet of
    > paper is then leftover space, assuming the pictures start off with a
    > typical 3:2 aspect ratio. It's very easy to do far better than that.


    I guess it depends on how much distortion you're willing to accept. ;-)

    Randy Kramer
     
    Randy Kramer, Jun 29, 2005
    #13
  14. Don Guest

    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
     
    Don, Jun 30, 2005
    #14
  15. Don Guest

    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
     
    Don, Jun 30, 2005
    #15
  16. Belorion Guest

    On 6/30/05, 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 h=

    ow
    > to implement this sort of thing, though.
    >=20
    > -Don


    Genetic algorithms are well suited for this. I've implemented a GA to
    work on the Traveling Salesman
    (http://www.tsp.gatech.edu/problem/index.html) problem(which I do
    beleive is also NP complete) with pretty decent success.

    Matt
     
    Belorion, Jun 30, 2005
    #16
  17. Hi,
    I have used GA for a TSP project and it worked fine for me.i think in
    this case also,this should work well.

    Do keep posted

    Thanks n Regards
    Dibya Prakash

    On 7/1/05, Belorion <> wrote:
    > On 6/30/05, Don <> wrote:
    > > I was thinking maybe you could use a genetic algorithm, where the fitne=

    ss
    > > function would caluclate the amount of waste. I'm not very familar with=

    how
    > > to implement this sort of thing, though.
    > >
    > > -Don

    >=20
    > Genetic algorithms are well suited for this. I've implemented a GA to
    > work on the Traveling Salesman
    > (http://www.tsp.gatech.edu/problem/index.html) problem(which I do
    > beleive is also NP complete) with pretty decent success.
    >=20
    > Matt
    >=20
    >
     
    Dibya Prakash, Jul 1, 2005
    #17
    1. Advertisements

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Piet
    Replies:
    0
    Views:
    630
  2. Replies:
    16
    Views:
    509
  3. Replies:
    0
    Views:
    284
  4. Replies:
    0
    Views:
    289
  5. Martin Raychev
    Replies:
    1
    Views:
    327
    Alvin Bruney [MVP]
    Mar 2, 2004
Loading...

Share This Page