Highest possible pyramid
up vote
1
down vote
favorite
I tried everything, but I still can't solve this problem without brute force:
I get N blocks with a known height and width. I can rotate them (height become width and width become height) and I have to build the tallest possible pyramid from them (of course I can change the order of blocks).
The problem is that you can't put a block of width X onto a block with width smaller than X.
EDIT:
The problem is, that you can't put a block onto a block of the same width.
Any ideas?
algorithm logic 2d
asked Nov 22 at 10:18
georgeel
44
|
show 7 more comments
up vote
1
down vote
favorite
I tried everything, but I still can't solve this problem without brute force:
I get N blocks with a known height and width. I can rotate them (height become width and width become height) and I have to build the tallest possible pyramid from them (of course I can change the order of blocks).
The problem is that you can't put a block of width X onto a block with width smaller than X.
EDIT:
The problem is, that you can't put a block onto a block of the same width.
Any ideas?
algorithm logic 2d
asked Nov 22 at 10:18
georgeel
44
1
If the blocks can directly be stacked on each other (without any constraints), then iterate over them and sum(max(block.height, block.width)) and it will be the maximum possible height. Which is a linear algorithm, you can't do any better since you need to inspect every block... or your question is something else entirely?
– Aleksei Maide
Nov 22 at 10:22
@AlekseiMaide The problem is that you can't put a block of width X onto a block with a width smaller than X.
– georgeel
Nov 22 at 10:29
5
Your question seems unclear. Would you please show brute force code you did and provide some testcases for expected input/output.
– Bishal Gautam
Nov 22 at 10:30
Could you provide the definition of pyramid, how could we know that the pyramid is valid? Any constraints for N?
– Pham Trung
Nov 22 at 10:42
2
This question, as asked, is too easy. I think you've probably made a mistake in transcribing it.
– Matt Timmermans
Nov 22 at 13:16
|
show 7 more comments
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I tried everything, but I still can't solve this problem without brute force:
I get N blocks with a known height and width. I can rotate them (height become width and width become height) and I have to build the tallest possible pyramid from them (of course I can change the order of blocks).
The problem is that you can't put a block of width X onto a block with width smaller than X.
EDIT:
The problem is, that you can't put a block onto a block of the same width.
Any ideas?
algorithm logic 2d
asked Nov 22 at 10:18
georgeel
44
I tried everything, but I still can't solve this problem without brute force:
I get N blocks with a known height and width. I can rotate them (height become width and width become height) and I have to build the tallest possible pyramid from them (of course I can change the order of blocks).
The problem is that you can't put a block of width X onto a block with width smaller than X.
EDIT:
The problem is, that you can't put a block onto a block of the same width.
Any ideas?
algorithm logic 2d
algorithm logic 2d
asked Nov 22 at 10:18
georgeel
44
asked Nov 22 at 10:18
georgeel
44
edited Nov 24 at 16:37
asked Nov 22 at 10:18
georgeel
44
asked Nov 22 at 10:18
georgeel
44
asked Nov 22 at 10:18
georgeel
44
44
1
If the blocks can directly be stacked on each other (without any constraints), then iterate over them and sum(max(block.height, block.width)) and it will be the maximum possible height. Which is a linear algorithm, you can't do any better since you need to inspect every block... or your question is something else entirely?
– Aleksei Maide
Nov 22 at 10:22
@AlekseiMaide The problem is that you can't put a block of width X onto a block with a width smaller than X.
– georgeel
Nov 22 at 10:29
5
Your question seems unclear. Would you please show brute force code you did and provide some testcases for expected input/output.
– Bishal Gautam
Nov 22 at 10:30
Could you provide the definition of pyramid, how could we know that the pyramid is valid? Any constraints for N?
– Pham Trung
Nov 22 at 10:42
2
This question, as asked, is too easy. I think you've probably made a mistake in transcribing it.
– Matt Timmermans
Nov 22 at 13:16
|
show 7 more comments
1
If the blocks can directly be stacked on each other (without any constraints), then iterate over them and sum(max(block.height, block.width)) and it will be the maximum possible height. Which is a linear algorithm, you can't do any better since you need to inspect every block... or your question is something else entirely?
– Aleksei Maide
Nov 22 at 10:22
@AlekseiMaide The problem is that you can't put a block of width X onto a block with a width smaller than X.
– georgeel
Nov 22 at 10:29
5
Your question seems unclear. Would you please show brute force code you did and provide some testcases for expected input/output.
– Bishal Gautam
Nov 22 at 10:30
Could you provide the definition of pyramid, how could we know that the pyramid is valid? Any constraints for N?
– Pham Trung
Nov 22 at 10:42
2
This question, as asked, is too easy. I think you've probably made a mistake in transcribing it.
– Matt Timmermans
Nov 22 at 13:16
1
1
If the blocks can directly be stacked on each other (without any constraints), then iterate over them and sum(max(block.height, block.width)) and it will be the maximum possible height. Which is a linear algorithm, you can't do any better since you need to inspect every block... or your question is something else entirely?
– Aleksei Maide
Nov 22 at 10:22
If the blocks can directly be stacked on each other (without any constraints), then iterate over them and sum(max(block.height, block.width)) and it will be the maximum possible height. Which is a linear algorithm, you can't do any better since you need to inspect every block... or your question is something else entirely?
– Aleksei Maide
Nov 22 at 10:22
@AlekseiMaide The problem is that you can't put a block of width X onto a block with a width smaller than X.
– georgeel
Nov 22 at 10:29
@AlekseiMaide The problem is that you can't put a block of width X onto a block with a width smaller than X.
– georgeel
Nov 22 at 10:29
5
5
Your question seems unclear. Would you please show brute force code you did and provide some testcases for expected input/output.
– Bishal Gautam
Nov 22 at 10:30
Your question seems unclear. Would you please show brute force code you did and provide some testcases for expected input/output.
– Bishal Gautam
Nov 22 at 10:30
Could you provide the definition of pyramid, how could we know that the pyramid is valid? Any constraints for N?
– Pham Trung
Nov 22 at 10:42
Could you provide the definition of pyramid, how could we know that the pyramid is valid? Any constraints for N?
– Pham Trung
Nov 22 at 10:42
2
2
This question, as asked, is too easy. I think you've probably made a mistake in transcribing it.
– Matt Timmermans
Nov 22 at 13:16
This question, as asked, is too easy. I think you've probably made a mistake in transcribing it.
– Matt Timmermans
Nov 22 at 13:16
|
show 7 more comments
1 Answer
1
active
oldest
votes
up vote
3
down vote
What I understand reading your problem statement and comments is that you want to build tallest pyramid with width from bottom to top in decreasing order.
If this is the case, then what we can do is simply the following steps:
- Loop over blocks and swap
widthandheightonly ifwidth > height. Now, sort the array of blocks in decreasing order of width which is the order used for stacking blocks from bottom to top in pyramid.
Answer is summation of all heights.
Note: step -2 is only needed if you want to display order of blocks
from bottom to top in pyramid.
answered Nov 22 at 10:55
Bishal Gautam
516416
So the first stage is to rotate blocks making them "higher than wider" ??
– MBo
Nov 22 at 11:19
@MBo, yes. First step ensure taller pyramid.
– Bishal Gautam
Nov 22 at 11:26
@BishalGautam The problem is, that you can't put a block onto a block of the same width.
– georgeel
Nov 24 at 16:35
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
What I understand reading your problem statement and comments is that you want to build tallest pyramid with width from bottom to top in decreasing order.
If this is the case, then what we can do is simply the following steps:
- Loop over blocks and swap
widthandheightonly ifwidth > height. Now, sort the array of blocks in decreasing order of width which is the order used for stacking blocks from bottom to top in pyramid.
Answer is summation of all heights.
Note: step -2 is only needed if you want to display order of blocks
from bottom to top in pyramid.
answered Nov 22 at 10:55
Bishal Gautam
516416
So the first stage is to rotate blocks making them "higher than wider" ??
– MBo
Nov 22 at 11:19
@MBo, yes. First step ensure taller pyramid.
– Bishal Gautam
Nov 22 at 11:26
@BishalGautam The problem is, that you can't put a block onto a block of the same width.
– georgeel
Nov 24 at 16:35
add a comment |
up vote
3
down vote
What I understand reading your problem statement and comments is that you want to build tallest pyramid with width from bottom to top in decreasing order.
If this is the case, then what we can do is simply the following steps:
- Loop over blocks and swap
widthandheightonly ifwidth > height. Now, sort the array of blocks in decreasing order of width which is the order used for stacking blocks from bottom to top in pyramid.
Answer is summation of all heights.
Note: step -2 is only needed if you want to display order of blocks
from bottom to top in pyramid.
answered Nov 22 at 10:55
Bishal Gautam
516416
So the first stage is to rotate blocks making them "higher than wider" ??
– MBo
Nov 22 at 11:19
@MBo, yes. First step ensure taller pyramid.
– Bishal Gautam
Nov 22 at 11:26
@BishalGautam The problem is, that you can't put a block onto a block of the same width.
– georgeel
Nov 24 at 16:35
add a comment |
up vote
3
down vote
up vote
3
down vote
What I understand reading your problem statement and comments is that you want to build tallest pyramid with width from bottom to top in decreasing order.
If this is the case, then what we can do is simply the following steps:
- Loop over blocks and swap
widthandheightonly ifwidth > height. Now, sort the array of blocks in decreasing order of width which is the order used for stacking blocks from bottom to top in pyramid.
Answer is summation of all heights.
Note: step -2 is only needed if you want to display order of blocks
from bottom to top in pyramid.
answered Nov 22 at 10:55
Bishal Gautam
516416
What I understand reading your problem statement and comments is that you want to build tallest pyramid with width from bottom to top in decreasing order.
If this is the case, then what we can do is simply the following steps:
- Loop over blocks and swap
widthandheightonly ifwidth > height. Now, sort the array of blocks in decreasing order of width which is the order used for stacking blocks from bottom to top in pyramid.
Answer is summation of all heights.
Note: step -2 is only needed if you want to display order of blocks
from bottom to top in pyramid.
answered Nov 22 at 10:55
Bishal Gautam
516416
answered Nov 22 at 10:55
Bishal Gautam
516416
answered Nov 22 at 10:55
Bishal Gautam
516416
answered Nov 22 at 10:55
Bishal Gautam
516416
516416
So the first stage is to rotate blocks making them "higher than wider" ??
– MBo
Nov 22 at 11:19
@MBo, yes. First step ensure taller pyramid.
– Bishal Gautam
Nov 22 at 11:26
@BishalGautam The problem is, that you can't put a block onto a block of the same width.
– georgeel
Nov 24 at 16:35
add a comment |
So the first stage is to rotate blocks making them "higher than wider" ??
– MBo
Nov 22 at 11:19
@MBo, yes. First step ensure taller pyramid.
– Bishal Gautam
Nov 22 at 11:26
@BishalGautam The problem is, that you can't put a block onto a block of the same width.
– georgeel
Nov 24 at 16:35
So the first stage is to rotate blocks making them "higher than wider" ??
– MBo
Nov 22 at 11:19
So the first stage is to rotate blocks making them "higher than wider" ??
– MBo
Nov 22 at 11:19
@MBo, yes. First step ensure taller pyramid.
– Bishal Gautam
Nov 22 at 11:26
@MBo, yes. First step ensure taller pyramid.
– Bishal Gautam
Nov 22 at 11:26
@BishalGautam The problem is, that you can't put a block onto a block of the same width.
– georgeel
Nov 24 at 16:35
@BishalGautam The problem is, that you can't put a block onto a block of the same width.
– georgeel
Nov 24 at 16:35
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53428682%2fhighest-possible-pyramid%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
If the blocks can directly be stacked on each other (without any constraints), then iterate over them and sum(max(block.height, block.width)) and it will be the maximum possible height. Which is a linear algorithm, you can't do any better since you need to inspect every block... or your question is something else entirely?
– Aleksei Maide
Nov 22 at 10:22
@AlekseiMaide The problem is that you can't put a block of width X onto a block with a width smaller than X.
– georgeel
Nov 22 at 10:29
5
Your question seems unclear. Would you please show brute force code you did and provide some testcases for expected input/output.
– Bishal Gautam
Nov 22 at 10:30
Could you provide the definition of pyramid, how could we know that the pyramid is valid? Any constraints for N?
– Pham Trung
Nov 22 at 10:42
2
This question, as asked, is too easy. I think you've probably made a mistake in transcribing it.
– Matt Timmermans
Nov 22 at 13:16