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 !

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

# This problem is hurting my brain... Please help

Page 1 of 1## 5 Replies - 229 Views - Last Post: 03 December 2017 - 12:05 AM

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

### #2

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

Posted 02 December 2017 - 09:26 PM

What have you tried or considered?

### #3

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

Posted 02 December 2017 - 10:11 PM

Make a list sorting by width and height.

### #4

## 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.

@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.

### #5

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

Posted 02 December 2017 - 11:49 PM

@mac I meant make

ie

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

### #6

## 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.

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.

Page 1 of 1