Highest possible pyramid












1
















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







share|improve this question




















  • 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
















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







share|improve this question




















  • 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








1









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







share|improve this question

















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






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Nov 24 at 16:37

























asked Nov 22 at 10:18









georgeel

24




24








  • 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




    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












1 Answer
1






active

oldest

votes


















3














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:




  1. Loop over blocks and swap width and height only if width > height.

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


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







share|improve this answer





















  • 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











Your Answer






StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});














draft saved

draft discarded


















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

























1 Answer
1






active

oldest

votes








1 Answer
1






active

oldest

votes









active

oldest

votes






active

oldest

votes









3














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:




  1. Loop over blocks and swap width and height only if width > height.

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


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







share|improve this answer





















  • 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
















3














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:




  1. Loop over blocks and swap width and height only if width > height.

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


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







share|improve this answer





















  • 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














3












3








3






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:




  1. Loop over blocks and swap width and height only if width > height.

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


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







share|improve this answer












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:




  1. Loop over blocks and swap width and height only if width > height.

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


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








share|improve this answer












share|improve this answer



share|improve this answer










answered Nov 22 at 10:55









Bishal Gautam

774517




774517












  • 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










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


















draft saved

draft discarded




















































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.




draft saved


draft discarded














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





















































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







-

Popular posts from this blog

Berounka

Image
Berounka.mw-parser-output .entete.map{background-image:url("//upload.wikimedia.org/wikipedia/commons/7/7a/Picto_infobox_map.png")} Caractéristiques Longueur 139  km Bassin 8 861  km 2 Bassin collecteur Elbe Débit moyen ? Cours Source Confluence de la Mže et de la Radbuza · Localisation Pilsen · Altitude 305  m · Coordonnées 49° 45′ 13″ N, 13° 23′ 24″ E Confluence Vltava · Localisation Prague · Altitude 187  m · Coordonnées 49° 59′ 43″ N, 14° 24′ 04″ E Géographie Pays traversés   République tchèque modifier   La Berounka est une rivière de la République tchèque. Elle porte le nom de Mže depuis sa source en Allemagne près de la frontière jusqu'à sa confluence avec la Radbuza à Plzeň. Elle continue ensuite sous le nom de Berounka jusqu'à sa confluence avec la Vltava, près de Prague. La rivière est une destination prisée pour les amateurs de canoë, qui appréc...
Read more

Sphinx de Gizeh

Image
Pour les articles homonymes, voir Sphinx. Sphinx de Gizeh.mw-parser-output .entete.egypte-antique{background-image:url("//upload.wikimedia.org/wikipedia/commons/c/cc/Picto_infobox_ancient_Egypt.png")} Site d'Égypte antique Le visage du sphinx de Gizeh. Noms en arabe أبو الهول , Abou al-Hôl Localisation Région Basse-Égypte Coordonnées 29° 58′ 31″ nord, 31° 08′ 16″ est Géolocalisation sur la carte : Égypte Sphinx de Gizeh modifier   Le sphinx de Gizeh est la statue thérianthrope qui se dresse devant les grandes pyramides du plateau de Gizeh, en Basse-Égypte. Sculpture monumentale monolithique la plus grande du monde [ 1 ] avec 73,5 mètres de longueur, 14 mètres de largeur et 20,22 mètres de hauteur, elle représente un sphinx couchant. Réalisée vers -2500, elle serait attribuée à Djédefrê, l'un des pharaons de la IV e  dynastie, représentant son père le pharaon Khéops. Sommaire 1 Étymologie 2 Desc...
Read more

Different font size/position of beamer's navigation symbols template's content depending on regular/plain...

Image
3 Let's suppose I'd like to divert the navigation symbols template (e.g. in order replace them by the frame numbers, see this bug report ;) I would be facing troubles regarding the font size/position, depending on regular/plain frames, as shown by the following MCE. How could I get rid of these troubles? documentclass{beamer} usetheme{PaloAlto} setbeamertemplate{navigation symbols}{insertframenumber/inserttotalframenumber} begin{document} begin{frame} frametitle{A regular frame} end{frame} begin{frame}[plain] frametitle{A plain frame} end{frame} end{document} beamer header-footer share | improve this question asked Dec 10 '18 a...
Read more