5 Replies - 229 Views - Last Post: 03 December 2017 - 12:05 AM Rate Topic: -----

#1 Kevsterking  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 02-December 17

This problem is hurting my brain... Please help

Posted 02 December 2017 - 08:31 PM

Hi, I've been sitting here for a while now thinking about a problem. It basically goes like this:

You receive a number of building blocks, they have all got both a height and a width. You may not put a wider block on top of a narrow one. And you may not put a shorter block on top of a taller one (no rotation allowed). You are trying to get as high as possible. The number of blocks goes up to 100000 I am just finding it really hard to find a way of solving this in a way which does not take way to long. So if you have an idea of how this could possibly be done, please give me a hint so that I can feel better about myself :D!

>Get the highest possible tower

>No rotation

>Up to 100,000 different blocks

>Only a few seconds execution

>There could be some sort of pattern??

Thank you!

Is This A Good Question/Topic? 0
  • +

Replies To: This problem is hurting my brain... Please help

#2 modi123_1  Icon User is online

  • Suitor #2
  • member icon



Reputation: 13659
  • View blog
  • Posts: 54,529
  • Joined: 12-June 08

Re: This problem is hurting my brain... Please help

Posted 02 December 2017 - 09:26 PM

What have you tried or considered?
Was This Post Helpful? 0
  • +
  • -

#3 snoopy11  Icon User is online

  • Engineering ● Software
  • member icon

Reputation: 1408
  • View blog
  • Posts: 4,459
  • Joined: 20-March 10

Re: This problem is hurting my brain... Please help

Posted 02 December 2017 - 10:11 PM

Make a list sorting by width and height.
Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12210
  • View blog
  • Posts: 45,289
  • Joined: 27-December 08

Re: This problem is hurting my brain... Please help

Posted 02 December 2017 - 10:51 PM

@snoopy11- We wouldn't have a linear order. For two blocks (w, h), (w', h'), we can order (w, h) >= (w', h') if and only if w >= w' and h >= h'.

@Kevsterking- Based on the order I described, perhaps you could set up a directed acyclic graph to model your problem. A largest-weight path in your graph would correspond to a solution for your problem.
Was This Post Helpful? 0
  • +
  • -

#5 snoopy11  Icon User is online

  • Engineering ● Software
  • member icon

Reputation: 1408
  • View blog
  • Posts: 4,459
  • Joined: 20-March 10

Re: This problem is hurting my brain... Please help

Posted 02 December 2017 - 11:49 PM

@mac I meant make two lists then sort then use the taller blocks last as you are trying to get as tall as possible. And use the wider blocks first. There should be some equilibrium in the lists that would allow you to build using a simple weighting system.

ie
step through lists

if (short&&wide)
   {
     use first

   }
next step


This post has been edited by snoopy11: 02 December 2017 - 11:57 PM

Was This Post Helpful? 0
  • +
  • -

#6 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12210
  • View blog
  • Posts: 45,289
  • Joined: 27-December 08

Re: This problem is hurting my brain... Please help

Posted 03 December 2017 - 12:05 AM

You could probably clean up that approach a little with dynamic programming. Because this problem doesn't have the optimal substructure property, it isn't immediately susceptible to the greedy algorithm.

Setting up a directed acyclic graph is still a better approach. We are looking for the longest weight path, weighted by the heights. For DAGs, the longest path problem has a linear time solution using a topological sort. That is probably the best possible solution for this problem.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1