3 kyu
Fabergé Easter Eggs crush test
165 of 1,870Ivana
Loading description...
Mathematics
Dynamic Programming
Performance
Algorithms
This comment has been reported as {{ abuseKindText }}.
Show
This comment has been hidden. You can view it now .
This comment can not be viewed.
- |
- Reply
- Edit
- View Solution
- Expand 1 Reply Expand {{ comments?.length }} replies
- Collapse
- Spoiler
- Remove
- Remove comment & replies
- Report
{{ fetchSolutionsError }}
-
-
Your rendered github-flavored markdown will appear here.
-
Label this discussion...
-
No Label
Keep the comment unlabeled if none of the below applies.
-
Issue
Use the issue label when reporting problems with the kata.
Be sure to explain the problem clearly and include the steps to reproduce. -
Suggestion
Use the suggestion label if you have feedback on how this kata can be improved.
-
Question
Use the question label if you have questions and/or need help solving the kata.
Don't forget to mention the language you're using, and mark as having spoiler if you include your solution.
-
No Label
- Cancel
Commenting is not allowed on this discussion
You cannot view this solution
There is no solution to show
Please sign in or sign up to leave a comment.
I think something wrong with tests. For n=311 m=10131 the test says Expected : 71692423655005205742475058887780204076478173193756056534361211129546043664445431944499667343853437837654574420941236308628252496657306440547150042542033422966836724604589618585313406081996653652790266390363056344043348948460554622622321171105487547727180837279888801878208802638642014343289117270679561876255479945479493366274871820692161157345919355451766369038588713612753294660349103505913526811646787927664100720765220490895831907659845589011856751027720648370221163404996407536536129106286633176735546895953041399202973489205488615661260572453354171008663345444479871804393330314581222773072596927 to equal : 3
Worst description i've ever read. sorry.
I agree, but I will say that the issues tag is meant for when the kata's test codes are entirely incorrect, not issues you have with the kata as a whole. (I am just giving you a heads up, some moderators are not the best at communicating this.)
That's not really true. "The description is bad" is a valid premise for an issue, but could be executed better (for example by explainign what is so bad about it and suggesting a better one).
This comment has been hidden.
Looks like there is wrong mark in description in maxmimum word
Dead problem 💀
Extremely poorly explained. Misses the point of programming exercises entirely, as programming knowledge is completely secondary to the task at hand.
If you're interested in Katas that involve programming, skip this one.
assume we have 2 eggs and 4 try
from what i understand, the decision tree behind the answer is that
the answer is 9
but if it did not break at 3 or 6 or 8, we know its 1 above it since we already tested 2 above it so the decision tree should be
the answer should be 12
im not sure if i misunderstand it or i should put it into issue
Exactly - if it does not break at 3, you know it will break at 4 since you tested it. If you alter the decision tree, you'd have no idea whether floor 4 breaks eggs, you only know that floor 5 breaks eggs and floor 3 does not.
If it helps, extend your tree with the result - if you have more tries then eggs, you'll reach a result once the last egg breaks, eg. down from 1 you get the result 0, down from 2 you get the result 1,... and to the very right, next to the 10-throw you omitted if no break occurs at 9, the results are 9 or 10.
Am I doing something wrong or are we restricted to using only BigInteger?
Took me a minute to understand the question, but the test values helped. The values are:
So for example if the values were
n = 1, m = 100, the answer would be 100. Just start dropping your one egg at floor 1 and continue up until it either breaks or you run out of tries. So you can give the exact number for any floor up to 100. The actual floor might be 2000, but you can only verify up to 100 with one egg. If you start on any other number, for example floor 2, the egg might break. Then you know that floor 2 isn't safe, but you aren't sure if floor 1 is safe or not, so you can't give a correct answer.thanks
I have a problem with random test My code work with all values
so you're saying there's no issue?
Whether there is an issue or not, this isn't the way to describe it.
Which language? Which random test? What's the issue with it?
Oh right, none of that is provided, so... closing.
This comment has been hidden.
This comment has been hidden.
That is really silly then. This should be on mathwars.com, not codewars.com.
suggestion closed
OK. So, I finally solved it in python with dynamic prorgramming and gmpy2 library. But it turned out there are simplier solutions if solved mathematically (facepalm).
How many random tests? I beat 7 random tests maximum.
In Python there's 50 random tests with values going up to 20k.
I've read there were made only 69 Fabergé eggs of which 57 survive today. So if you do a test with more than n>57 some of them are not real Fabergé eggs ;-).
I have solved the problem in golang. Optimised it using 2D array caching. But it is failing for last two data input only in the test code. They are (310, 512) and (494, 500). Not sure why. It must be something to do with golang math/big library. Not sure what. Any ideas?
I fixed it. All test passed. But when attemted, it failed with Execution Timed Out (12000 ms). I guess I have to optimise it more.
Sorry it's my fault for sure but I can't understand the explanation of this kata. at a certain point the text states "[...] if they(the eggs)'re thrown from a certain floor or below, they won't crack. Otherwise they crack. [...]" Should I desume this height just from the value of N and M?
but nobody help lol
Description should better explain how the number of eggs N is different from the number of tries M. As far as I understand it, it's not a problem with two parameters, it's a problem with one parameter: min(M, N) Or do we get M tries per each egg, so it's M * N?
You don't know in advance how many eggs you have, neither the number of trials. There is nothing to explain about how one is different from another. They can be any random values.
The description is absolutely unambiguous:
That means you have in total
neggs, and in totalmtries. Once an egg is broken you cannot use it anymore. From there you must reason, what you have begun to do, but no need to share it publicly (that's why I marked your comment with a spoiler flag), and find the solution.This comment has been hidden.
This comment has been hidden.
This is not a suggestion. The users are supposed to make the correct reasonning from the information provided. Don't do it for them.
It doesn't mean the description cannot be improved, but please not this.
oops srroy!
D translation
Start 0 floor.
0 tries. A(0,1), A (0,2),...,A(0,n) = 0.
0 eggs. A(0,0), A(1,0),... A(m, 0) = 0.
1 eggs. 1 tries. A(1,1) = (A(0,0) + 1)
1 eggs. 2 tries. A(2,1) = (A(0,0) + 1) + (A(1,0) + 1).
.....
i - tries, j - eggs.
А(i,j) + X = A(i+1,j)
X = A(i, j-1) + 1
Kata hint != kata suggestion
I count two nested loops. Array A for m attempts with j eggs. I calculate array B for eggs (j+1). I transfer the elements B to A and compute B for eggs (j+2). .. .
Timed out. Passed 8.
How to optimize the code, I do not understand
We have N eggs and M attempts, Who determines when an egg will break?
Read carefully the description. We don't know about when egg breaks, it could never break actually, and you don't need to care about that.
English is not my native language maybe that's why,no matter how much I read this "that takes 2 arguments - the number of eggs n and the number of trys m - you should calculate maximum scyscrapper height (in floors), in which it is guaranteed to find an exactly maximal floor from which that an egg won't crack it." understanding does not come.Maybe the task is completely different, but this is not clear from the description of the task.
You don't know and cannot know when the egg will break and whether it will break. What you must find is the maximum height you can make sure the egg won't crack in any case with the number of trials.
Let's take the simplest example: if you have 0 trials. The egg could be very fragile and break at any height. Or it could be very resistant and never break. It also could break at floor 1, floor 2, floor 3, at any floor actually, but you don't know that. Since you have no trials, you are not able to know anything. So the answer would be zero, even though the egg may never break. That's what you must figure out: the egg could break at any floor and you don't know anything in advance, your must give an answer valid for any possibilities.
I also dont understand the puzzle. could you give a explanation with lets say 3 egs and 5 tires. or something like that. Can I trow same egg multiple times if it doesnt break? I also doesnt understand how floor number odesnt affect a number of tires? when finding that out, should you just trow egg from random floor and then go up or down depending if it breaks or not?
Tough but nice one !
I solved it recursively using memoization, but I don't know how to use the BigNumbers module. I just have to figure out how to do that and hten i can submit
Rust translation.
I got a question... I know there are some different ways somenone can solve this problem... I choose the dynamic programming just to practise it. Despite the fact that, I follow very carefully the theory and some articles I always take time execution error. Is there any way to solve this problem using dynamic programming or i should look for another way to approach the problem?
yes you can solve it with dynamic programming BUT it worked for me only on basic and advanced. in serious tests I get Execution Timed Out
The more eggs and tries you have the higher floor it will be... So I guess the specific math formula is supposed here other than that I see no sense.
height 2 14 = 105height 7 20 = 137979. And what's gonna be the floor ifeggs: 10, tries: 3? This is a pass, sorry...This comment has been hidden.
This seriousTests case is killing me. I can't figure out how to optimize my solution enough to pass.
I've got the obvious case of m <= n covered to knock out half the calculations. I've also got m - n == 1, m -n ==2 and m = 2n + 1 to knock out more calculations but I cannot figure out how to reduce the calculations when m is much greater than n.
Can someone give me a hint?
I have brute forced my wait into a solution by doing performance analysis and thinking of clever ways to reduce the calculations which you have also done. (Side note, when doing performance analysis/debugging I noticed that I had bug on my optimizations which you could also double check) Still, there are generic ways to improve performance of any algorithm which you could try.
For people who may also be confused by the "target floor can be any floor between 1 to this maximum height" => in cases when it is not possible to throw an egg, the answer is not 1, but 0 - existence of the target floor from which the egg will not break is not guaranteed. There may be 0 such floors. The description seems misleading.
Thank you! I agree that the description is ambiguous, I specifically went to the discussion board hoping that it wasn't just me xD
This comment has been hidden.
This comment has been hidden.
This is a very difficult kata. I solved it only ... after solving 1kyu continuatin of this kata. So my advice for anyone else struggling (like I did for days) would be to think how you would solve the related 1kyu kata which would enable to rule out some of the standard approaches that should be more than sufficient for this 3kyu kata but which in fact are not. Also tags on ths kata are incorrect and while you might/should start with writing the equations that would be used for Linear Programming this kata is not solved by Linear Programming.
How do you throw an egg?!
https://www.youtube.com/watch?v=yPYxQQglBGM
I can't understand the description...
Then go solve another kata. Over 1000 completions say that it's understandable enough, and your comment with no examples or suggestions doesn't count as a kata issue.
what a condescending reply
Description code blocks made only for haskell, missing other languages.
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
Respectable approach for sure, but I still feel that being able to prove the answer is what you suspect it to be is also a pretty important skill (not sure if that's what you meant or not).
It’s called “Fabergé” not “Fabergè”.
:D
This comment has been hidden.
No, it is 1. How could you know if the answer is 0, 1 or 2 with one try? (the egg may crack if thrown from first floor).
The Description is too bad! I can't understand what it mean……
I have no idea how to get 105 out of 2 eggs and 14 tries. Is it allowed to give some explanation?
same question
This comment has been hidden.
Comment removed. Made a mistake
Question says: target floor can be any floor between 1 to this maximum height? Some of the answers are '0'
This doesn't make any sense. For the case where you have no eggs, the max height should be 1. Either that or the target floor should be any floor between 0 and the max height.
With 0 eggs and 1 floor you don't know if the egg would break while dropping from floor #1 or not, as you have 0 eggs to test. So it's proper to return zero here as if a house would have 0 floors, we can say that throwing eggs from that height won't break them even having no eggs.
The 0 answers do make sense, but that the target floor can't be 0 is weird: what if the egg breaks even if dropped from floor 1? then there is no maximum floor from which the egg won't crack and the logical answer (to the actual floor determination problem) would be 0.
And all of this is sort of a problem because it can lead to some off-by-one errors due to this 'floor zero' thing. I think this has to be clarified somehow in the description.
I agree 100% that this is an off-by-one error. If, as the description suggests, the
target_floor(highest floor before the egg breaks) is1 <= target_floor <= max_floor, and we are to findmax_floor, then(n, m) = (0, 0)implies thatmax_floor = 1.If you instead use the definition that
0 <= target_floor <= max_floorthen this is equivalent to solving the problem from the other perspective and then subtracting1from the resultingmax_floor. Indeed, if you consider the algorithm for finding thetarget_floor, and if from the start it is assumed thatk <= target_floorfor somek, then it is useless for the algorithm to check any floors at or belowk. This effectively shifts the algorithm's search byk - 1places and thus shifts the resultingmax_floorby the same amount.its too vague, could you please add another example (below 7 eggs 20 tries) i get 105 for 14 tries 2 eggs but for 7 eggs and 20 tries, i get a little more than 137979, i tested some cases and it seems to work. could it be that 137979 is not the actual maximum? maybe the boundaries(where an egg, each try is supposed to be dropped from) werent counted?
I'm having issues trying to understand this problem in C#. We have a infinite number of floors, m eggs and n trys. Previous comments suggest that 1 try = 1 egg. Since, there is no data on how to determine whether or not a egg breaks. We need to determine the maximum section we can clear accurately incase the egg does break.
For example, the data suggests that 7 eggs with 20 tries = 137979 floors???
However, if you have 7 eggs the maximum amount of floors you can test & have a accurate number is 70...70 x 20 = 1,400 < 137,979
EXAMPLE: Say you are coming up from floor 70 and throw the egg at floor 140 (70 floors), it cracks...so you go half way floor 105, it cracks...so you go half way...you do this until you have 1 egg left which would mean that etheir it cracks on 71 and floor 70 is your highest or floor 71 is your highest floor.
20 tries, clearing 70 floors each time, egg never breaks, = 1,400 floors
So, now that I have presented my thought process, my question are as follows.
How exactly are you guys determining whether or not the egg breaks? At the moment I can only assume that somehow 84 people who solved this came up with the same arbitrary numbers which is impossible.
How are you getting numbers like 137,979 and still be accurate, to the exact floor?
I am aware that I am probably thinking about the solution incorrectly. However, with the information presented I do not see how this is solvable under these conditions. The skyscaper is endless and we have no way of determining the egg breaking.
I think the idea is that for each time you throw you lose one try, and each time an egg cracks you lose one egg. So if the egg didn't crack you just lose one try and you get to use the egg again. You need to find the floor while keeping within both the number of tries and eggs.
Did this a while ago so couldn't remember exactly. There might be off-by-one errors above.
Yea, I understand this part... However this is exactly what I'm explaining. If you can only accurately clear 70 floors because you have 7 eggs to work with, if none break than the most accurate number is 1,400, because you have 20 tries. Anything above this would result in a potentially wrong answer, because it could be off by 1 floor or multiple.
The number of tries and eggs decrement together. I'm not sure where you are getting 70*20 from, but that's not what's being asked
I don't really see where you got 70 from and why multiplying by 20 makes sense here.
Maybe an example would help? You currently have 7 eggs and 20 tries. If you throw an egg at floor 70 and it breaks, you know the answer < 70 and you have 6 eggs and 19 tries left. If it doesn't break you know it's >= 70 and also have 19 tries left but still have 7 eggs.
I explained the logic above, please refer to it, with 7 eggs you can only clear a section of 70 floors accurately...If the egg never breaks you clear 70 floors 20 times, hence 1,400 floors
So first I'm either too bad at reading to understand this (does happen from time to time, especially when I'm sleep, so sorry if that's what happened), but I'm mainly concerned about the fact that you didn't really explain why 20 tries means multiplying by 20 (as this is very likely a misunderstanding of the problem). The other thing is that I'm not sure where 70 came from, because again I feel like we aren't even talking about the same question at this point.
Well the thing is you don't have 20 tries 'of' 7 eggs. You have 20 tries and 7 eggs, and each throw consumes a try and may, depending on the outcome, consume an egg by cracking and breaking it.
It's like if you have 20 tomatoes and 7 eggs, and some dishes require only a tomato and others require a tomato and an egg. You can't say that since 7 eggs can feed 70 people, by adding 20 tomatoes you can feed 1400 people. That's not how the 'resources' work.
I try and attempt to make the explaination simpler using 64 floors, as 70 i'm seeing doesn't make sense.
The reason you can only clear a maximum of 64 floors is because of this: Congrats you reached floor 64 -> you throw your egg, it breaks...ok = -1egg, 6 eggs left 19 tries Split the floors in half to be efficient. Congrats you are at floor 32 -> you throw your egg, it breaks...ok = -1egg, 5 eggs left 18 tries Congrats you are at floor 16 -> you throw your egg, it breaks...ok = -1egg, 4 eggs left 17 tries Congrats you are at floor 8 -> you throw your egg, it breaks...ok = -1egg, 3 eggs left 16 tries Congrats you are at floor 4 -> you throw your egg, it breaks...ok = -1egg, 2 eggs left 15 tries Congrats you are at floor 2 -> you throw your egg, it breaks...ok = -1egg, 1 egg left 14 tries Congrats you are at floor 1 -> you throw your egg, it either breaks & your at floor 0 or floor 1 is your maximum floor...ok = -1egg, 0 eggs left 13 tries
So let's say your egg never breaks: 64 + 64 + 64 + 64 + 64 + 64 + 64 + 64 + 64 + 64 + 64 + 64 + 64 + 64 + 64 + 64 + 64 + 64 + 64 + 64 = 64floors x 20tries = 1,280 maximum floors
In conclusion the maximum floors able to be cleared, reliablely & accurately is 1,280 with 7 eggs and 20 tries
However, going back to my original questions...The problem never states how egg breaking is determined, leaving this critical part up the air.
Additionally, at least with the logic above a number like 137,979 is impossible While still being accurate.
This part is still unexplained. Even if you think it's obvious, I think you should try to spell out the procedure because my hunch is that it doesn't make sense as well.
There are two problems:
Not sure what you mean by 'determined', but you need to handle both the case where the egg breaks and the case where it doesn't, within the limits of eggs and tries. If you are talking about something like a function to call to determine whether the egg breaks when thrown from a certain floor here's no need for that. Otherwise conceptually you'll just throw and the eggs will behave according to the height.
Fair enough, so just minus 6 tries, easy = 64 x 14 = 896 floors
Determined means to decide or resolve. The problem never states how egg breaking is done, AKA we can only assume that the egg might break, so 896 floors would be our safest bet. Like you stated above, however this is still a far cry from 137,979
I think you got how this kata works, but you still have not shown your reasoning about why any of the answers you gave above are really the maximum.
I encourage you to come up with a more systematic way of calculating the maximum number of floors, instead of just saying random stuff without showing the reason why you calculated like this.
Well 896 would accurately be the maximum. This is backed up my the math and reasoning listed in previous comments.
If you are calling into question why would I divide the floors by half when determining exact floor. This is simple, by dividing the floors in half you have a equal chance of determining whether the floor is above or below. if we had 8 eggs to work with we could clear 128 floor sections
But again, 137,979 is no where near 896
That only makes sense in some special cases. I'll leave figuring out the details to you.
Also, not really a second question because I'm asking about your reasoning as a whole, but why did you multiply by 14? Why is multiplying the right thing to do? Why is multiplying by one more than the number of tries minus the number of eggs right? That's still unexplained.
I ask for your reasoning, your thought process, on this: Why would you consider what you proposed to be the optimal strategy?
I am sure that 896 is not the maximum. There are ways to accurately work with more floors. But unless you explain your reason I cannot really even begin to explain it to you because I don't know where you did wrong. Do understand that even if what you wrote may look obvious to yourself, to me it's just putting the numbers in the question together in a random way, because I have no idea what you are thinking.
You're not really explaining it to me either. You just need to, as said, think more systematically.
I'm sorry, but we have gone over the logic and refined it many times in this thread. I cannot break down the steps further.
Second, I would consider this the most optimal strategy, because again as stated previously...spliting the floors by half gives you equal probability of determing the correct floor. There by, giving you the most optimal chance of determining correct floors within new ranges.
Please refer to how we refine 64 floor sections to 1, if we only have 7 eggs.
Edit: I guess you could be suggesting that 896 cannot be the maximum, because that means the egg didnt break and why wouldn't you just clear another 64 floors, so I suppose the new formula would be (2^(Eggs - 1) x (Tries - (Eggs - 1)) - 1) = 895 in this case
If you do think this is already broken down into the most detailed reasoning possible, then okay.
The thing is, this is wrong. It only applies if you're not limited by the number of breaks you can tolerate (i.e. number of eggs.) Then:
It seems you're trying to adjust for the fact that you're limited in number of eggs by multiplying by
Tries - (Eggs - 1). You have never explained why a multiplication is here, but alas it's also wrong. It's just not the optimal way to do this. Please explain why you think it's optimal.Your entire line of thought is not going in the way the optimal solution works. I'm not saying that you need small adjustments here and there. In fact, that's why I want you to think more systematically. You already made like 3 adjustments, and you're still a long way off from the answer. You need a different approach. As for the reason that your approach isn't optimal, well I await a response from you on the things mentioned above.
I'm thinking of a way to demostrate you a method that work with a higher number of floors, but at the same time not spoiling the solution. I like the kata a lot and I think the description should have one just to show how things are done. That's also partly why I keep replying. But until then I really want you to address what I mentioned above, just so I can know where exactly went wrong, whether the description can be made clearer (it could be a simple misunderstanding!), and by the way I suggest you also make up your mind about the answer.
What do you mean by "...not limited by the number of breaks you can tolerate" you are limited hence why you can only clear a certain amount of floors reliablely, I'm confused.
"You have never explained why a multiplication is here" this is shown earlier in the thread. and I have already repeatedly explained why using probability this is optimal.
"You already made like 3 adjustments" Adjustments have been made, because I realized that the original math didn't work and could be more accurate/reliable when you pointed out that the x20tries didn't account for eggs breaking.
Hence
2^(Eggs - 1)is the wrong way to think about this.But I know you didn't say that, you said
(2^(Eggs - 1) x (Tries - (Eggs - 1)) - 1).Why does multiplying by
Tries - (Eggs - 1)and subtracting one fix this? You never said anything about this and keep referring to the part2^(Eggs - 1)instead. This is why I was asking about the multiplication.Also, there's no probabality to be found in this problem. There's no randomness and every case has to work, exactly.
So the "Tries - (Eggs - 1)" is to calculate the maximum floor while staying reliable, if we are spliting the section in half after every egg break. I'm seeing what you are saying about the "-1", as it will not work for many cases. In my eyes there is probabality, however the chance is consitant between a 50/50 because you split the floors.
Okay, you want to do it in sections. Why is this the optimal way? It sure does sound like you can do better than a linear search through the sections right?
The other way I had in mind was exponetially spliting, but this loses accuracy. So I'm currently unaware of a better way.
Unaware doesn't mean it doesn't exist, so it does not constitute a reason.
Can you come up with a way to calculate exactly what strategy to use exactly instead of just coming up with random ones and see if they work?
If I could, I wouldn't be asking questions for clarification.
Well that I can't really help too much because it's your job after all
You did sound like you were serious doubting the correctness of the given tests. I hope I at least partially addressed that.
This comment has been hidden.
This is kind of a sub optimal method to solve the problem no? there is a TedEd video on something similar to this. so if you want to find out what exactly the methodology for obtaining the number of floors is, look it up (The problem on the teded youtube channel has a fixed number of floors but you have to find minimum tries).
Another question in the same vein as some below: running this in C#, getting correct answers, but the full test suite times out. For n=20000, m=30000 (above the test limit), this still only takes 808ms. How much faster does it need to be? Edit: down to 640ms, still no luck.
I'm afraid there is something bad with your golang runtime env. When I ran my code locally (e.g. Height(311, 10131) ) it calculated the proper result 71692....6927, but in codewars environment the same code gave 0.
Random tests are broken for golang. Also test Height(311, 10131) expecting incorrect result (mine is "716924...", expecting "378359...") Somebody made really bad translation for this kata and also same kata for 1 kyu Very disappointing
Yes I think something wrong with tests. For n=311 m=10131 the test say Expected : 71692423655005205742475058887780204076478173193756056534361211129546043664445431944499667343853437837654574420941236308628252496657306440547150042542033422966836724604589618585313406081996653652790266390363056344043348948460554622622321171105487547727180837279888801878208802638642014343289117270679561876255479945479493366274871820692161157345919355451766369038588713612753294660349103505913526811646787927664100720765220490895831907659845589011856751027720648370221163404996407536536129106286633176735546895953041399202973489205488615661260572453354171008663345444479871804393330314581222773072596927 to equal : 3
I have a solution in Python that in the worst case (n = 20000 and m = 20000) it takes 1.08s (measured with timeit). Still can't beat the timeout error. Can someone tell me at least how far am I to an acceptable solution (in time)??? How fast should I be aiming on this?
20000/20000 is easy, worst case is actually 10000/20000.
This comment has been hidden.
This comment has been hidden.
You don't, u r asked to return the maximum height of skyscraper you can check. e.g. when you got only 1 egg and 7 tries if u will throw it from 1000 (for ex. sake) and it will break the test will end at once and you won't have a solution, so your best method is to throw it from level 1, if it doesnt break go to level 2 and so on till you got to level 7 and that's why the solution for that will be 7.
Read above :)
Well answering that will be a spoiler I guess... but rest assured there is a reason.
By the way I'm still struggling with this problem... I solved the math but the solution is too slow... will be solved eventually :)
Okay thanks that helped already! :)
.
This comment has been hidden.
Haskell version is broken - there's a case where n=99999 (n is supposed to be 20000 max).
Julia translation F# translation
SCALA VERSION got this error when attempting to push my solution:
fixture.scala:33: warning: method + in class Int is deprecated (since 2.13.0): Adding a number and a String is deprecated. Use the string interpolation
s"$num$str"FabergeTest.test(random.nextInt(20000) + "", random.nextInt(20000) + "") ^ fixture.scala:33: warning: method + in class Int is deprecated (since 2.13.0): Adding a number and a String is deprecated. Use the string interpolations"$num$str"FabergeTest.test(random.nextInt(20000) + "", random.nextInt(20000) + "")How are you suppose to do this without Excution Timeout. How efficient could it get? Does the algorithem need to be linear ? My approach can calculate (477,10000) but if there is more than one test trials with input integar larger than 10000, it causes timeout.
Rip Kobe.
Maybe, there is some inspiration to find here: https://www.codewars.com/kata/53d40c1e2f13e331fc000c26
https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.4
This comment has been hidden.
This situation is unrealistic. Even with the fastest elevator in the world, there is no way you'll manage to go 10 to the power 3000 (which is roughly the answer to height(4477,10000)...) floors up multiple times so that you can re-use unbroken eggs. (Even just once actually...)
Is this a part two to another kata? Because I'm very confused as to why there is little to no information to work with.
This is a standalone kata and the other kata sharing same title is a performance version of this. The description contains enough information to solve the task, and if you don't grasp it then re-read it multiple times and if you still don't get it then do some more research. If you made your remarks because of some ambiguous wording then ask right away.
There is something unclear in the problem description. It says the eggs are almost identical (emphasis added), meaning they are not identical, so tries with one egg would not apply to another one: any series of try with one egg is independent from the series with another egg. Is this actually what is meant here ? In the issues thread, someone claims to assume they are actually identically behaving.
They might be slightly different but all the eggs break when they are thrown from a certain floor or above, see statement 1, a bit further in the description:
This comment has been hidden.
Your analogy is the worst case scenario (eggs always break). This question is asking for the best case scenario (how high can you go if eggs didn't break (meaning you can reuse the eggs as many times as you want)), while still making sure that you can find the exact critical floor should the eggs break.
I think if you have only two eggs and m tries, the answer would always be (m/2)*(m+1). The pattern would be 14, (14+13), (14 + 13 + 12)...I don't know how the pattern changes if you have more than 2 eggs; that's very tricky!!
I don't think it's very realistic. If you drop an egg it surely gets some microtrauma even if it doesn't crack, making it more susceptible to crack in another throw.
This comment has been hidden.
What is your approach? If you use doubles instead of big integers you obviously will have precision problems
this is added in harder version, closing
Somebody can tell me if this problem is related with any situation in practice life. I haven't solve it yet, maybe that's why I don't see the point with this problem.
The hardest parts seem to (0) understand the problem in a meaningful way, (1) to optimize the solution so long that it passes all tests without timeout.
This comment has been hidden.
I really don't understand where to start with this, given the . number of eggs and tries, how can I possibly know the height of the floors?
I hope you would have got that now, please tell me if yes.
This comment has been hidden.
Hi, for the Haskell version, there is a typo in the function name:
heigthshould beheightHi, how does one store such high values in Python?
Get a bigger python.
how should I know when egg cracks, this isnt explained in the question?
This comment has been hidden.
Um, how do you delete a comment?
Idris:
Incorrect function name:
heigthinstead ofheight.exportshould be added tospecSuitein Sample Tests.export.Not sure how to fix the
partialwarnings.Idris translation
I'm having troubles understanding this kata.
All we get is N eggs, and max M tries. How am I supposed to know when do I know that an egg cracks?
Am I completely misunderstanding it?
Thinking about a simpler case makes it easier to understand:
with 1 egg and M tries, you can test up to floor M. Even if it doesn't crack on that floor, M would be the answer
This comment has been hidden.
The question was more about maths. I had a hard time figuring it though.
After completing the kata, I believe it's more about math. Although, it's inspiring to see nice pythonistic solutions
This comment has been hidden.
No, the first drop will be at a level that provides you have a full coverage of all floors below in the worst case scenario i.e. all egs will brake one after another. If the first egg brakes, the seacond drop is not in the middle of all levels below. It's closer to the bottom, than the top (level the fist egg broke). So, the spacing is not halved at every attempt as one may think.
Does m = total tries or tries per egg?
total tries
Its mostly a math problem I think. I had some problems getting the Javascript version to work, as the BigNumber documentation mentioned 'multipliedBy', while only 'times' and 'mul' work??? Maybe add some more documentation to reflect the working methods on BigNumber
this is still the case for this Kata. THank you for giving an alternative
Time: 1361ms Passed: 7 Failed: 0 Exit Code: 1 I have increased recursion depth and passed all cases with nice time, but still see exit code! How to solve this problem?
and what's the error message, at the bottom?
This comment has been hidden.
So, what i need to do?
Use
sys.setrecursionlimit, or rewrite your algorithm to not use recursion, or rethink the appropriate algorithm for this problem ;-)I think there is an issue with java solution. I have optimized all what are possible. I tryed two way of algorithm - from start and from end. But there is "Execution Timed Out (16000 ms)" I found another solution of this Kata in the Git and it also have the timeout error. Can anyone test your java-solution? Is it problem of this site or my problem?
You get that when your code takes too long.
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
Anyone?
This comment has been hidden.
I've forked the go translation to fix the issue here, if someone could approve it?
Already approved by someone.
ah, yeah, I forgot to come mark this resolved; thanks
This comment has been hidden.
Right now on the python version I am passing 36 tests and failing 24. All the failing tests are the randomly generated ones. Like:
1498152621787493509656129759259203897865598852423L should equal 5846006549323611672814739330865132078623730171903L.
Could someone give me some random test cases that would result in numbers like that so I can find my issue? I seem to somewhat consistently be off by a factor of 3.9 for these, but I pass the regular tests just fine.
Figured it out using some tests from the harder version of the this problem.
when you say "when the target floor can be any floor between 1 to this maximum height?", does it mean that eggs never crack when falling from the first floor ?
no, that doesn't follow from that statement
Actually, it does follow from that statement. It seems (sorry but the description of this kata is extremely confusing) that the "target floor" is the highest floor from which an egg would not break. If an egg breaks from floor 1, then target floor is 0 which is not "between 1 to this maximum height".
The question asks for the highest skyscraper where you can guarantee the highest floor you can drop an egg from. It's possible you cannot even determine if you can throw an egg from the first floor (if you have no eggs or no throws), so in that case you can't guarantee any floors, so the maximum skyscraper height is 0, or no skyscraper. The 'target floor' represents a floor where you can toss the egg from. You can't toss an egg from floor 0 (the first floor is floor 1), but you can report 0 meaning you can't determine the floor for any skyscraper with more than 0 floors.
Hello! I have written two solution which make with DP and combinations in javascript, but it can't pass the serious test: '4477,10000', '9477,10000'.
And I found that the serious case is removed in Java.
Would you like to help me?
Not an issue. It's a question ;-)
Also, no, those 2 tests are intended. We were talking about something among
m, n <= 10^5in the previous Java version:Besides, random tests will test numbers in the full input range stated in the descriptions.
Description is unclear. What's the function to throw an egg? As I understand, it takes a integer (height) and returns boolean (if egg got broken).
I have a problem with the explanation on tries: Can you throw multiple eggs at once per try? In the example of 2;14, in the first try, can I throw my eggs at the same time or its only ONE egg per try? So if I have 10 eggs and 10 tries, will I get 100 drops (10 per try) OR 10 egg drops (one per try)?
You throw one egg at a time. If it breaks it's gone.
Then what's a "try"? I'm also confused by this. How are eggs not tries?
I was struggling with this but this comment chain has clarified it - you can re-use an egg if it doesn't break. So for example if n = 2 and m = 14, if on your first two tries your eggs break then you don't get any more tries.
This comment has been hidden.
Different languages have different language features.
Also, this is not a suggestion ;-)
Great kata. I'll try to create better solution than this which I posted. Thanks.
Hello! I'm new here, maybe don't know something, but there is no possibility to create 20000 x 20000 big.Int array in Go. Could you please reduce it to 10000 x 10000?
No.
Also, that's not an issue. If you don't get the required algorithm, try harder and don't post an issue about something on your side.
I have an algorithm, array (20000 x 20000) is required to be created for buffering calculations.
This comment has been hidden.
A general tip for dynamic programming:
Do you actually need all the rows at any time when you do the state transition from one row to the next?
Usually you don't, and so you don't need quadratic space ;-)
For all, who writes, that description is too unclear. Maybe you know, there is a good tradition in russian (and I think, it isnt much depends from the country) olimpiadic programming - put a task description in a such joke and unclear manner. Try out any contest/task and you will see it :) In that case, to understand a formal task is a part of whole task. Anywhere, this cata has been solved by 57 users, and I think they have understanded what are they have to do. So, I guess, it will be not good idea to explain all formal description in details. Thow, you may post issues and minuses, but I think so.
If I'll ever resolve this I will give it a negative review. After all I am here for programming not guessing. Good the fact I decided to read here. Now I know that it is not about the solution but about the question. The difficulty must be in programming not in guessing what funny someone wants.
This comment has been hidden.
Resolved (edited the test cases myself).
This comment has been hidden.
Java translation had some test cases that are outside the specified data range, which makes it much harder than the other language versions are.
I've fixed it.
Thanks for your quick answer.
Now I have passed the tests.
Can you explain the relation. I have been trying to figure out why you add together. I did get that the choice represents whether or not the egg breaks.
I don't understand if I can throw n eggs at every try or not. So let's suppose I throw 2 eggs and just one cracks, next try I have 2 eggs again or just one remains?
A broken egg is, obviously, broken, so you can't use it again.
This comment has been hidden.
This comment has been hidden.
Sorry, I can't see the reply, and interestingly I can't even see my own post now since I marked it as spoiler. Interesting, I'd assumed I could read the thread as the author even though I marked it as spoiler. Any chance of a reply I can see (again, not asking for spoilers)? Thanks.
Edit: Odd, once I posted a reply the thread became visible.
Thanks for the feedback, I'm working in Java, and will continue to optimize.
Java translation had some test cases that are outside the specified data range, which makes it much harder than the other language versions are.
I've fixed it.
I have no idea what is requested in this Kata. The description is unclear.
O, it is nice to see, that this my cata is wide-discussed and translated on many other languidges! I only hope, that my other catas (not only 2, that are approoved) will be such popular or ever be solved by anybody in near future - try they, they are interesting too :)
Wait, don't go, I need you. I'm modifying my translation (code style issue) and I need you to approve the forks :D
Here it is, the Groovy one
Where I must push a button to approve the forks, that is needed?
Scala
Open the link given, and find the green button on the right top side :D
Done, on Groovy / Scala links above.
Thanks! Your Kata is really welcomed. You never know.
And I've made an extreme performance version of this kata, maybe you could try? :D
Yeah, only 2 year (or near it) have passed from the time I published it, and now it is wellcomed :) I have seen your extreme varian of this cata, maybe try it if I will have time. But I was surprised, that some my other cata are not finished (and even not much tried`) yet :)
I'll tell my powerful friends to try them :D
Scala translation
Kotlin translation
Groovy translation
This comment has been hidden.
This comment has been hidden.
I think the label "DYNAMIC PROGRAMMING" is improper. I can't make it with DP.
In fact I think it is more like a math problem.
I don't know whether the reason is that I use python so I can't make it with DP.
You can make it with DP if you're observant enough and make enough tables to look at. (That's how I initially solved this kata. Though OEIS and other previous experiences of sequences also helped.)
The more performance heavy linear version, though, actually requires mathematics.
This comment has been hidden.
I threw the egg 1000000 meters up on first try and it didn´t crack. Whats the logic behind this?
They're hard boiled.
'Cause it's drifting around in outer space, maybe orbiting the earth ;)
This comment has been hidden.
Please raise questions about a Kata as a question, not an issue.
That being said, I haven't completed the Kata but likely eggs decrement when one gets cracked, while tries decrement every time.
I feel like if I'm the only one unclear, it would be a question, but since there are so many comments about the vagueness of the problem, I feel like it is a genuine issue
All eggs are identical, it's like a countable resource. You can drop an egg any number of times as long as it hasn't broken. With 2 eggs and 14 tries you can drop until 2 eggs have broken or you reached 14 tries.
We all know that the description is not very good, but unless someone has a good idea how to improve it (and actually edit the kata to replace it), there's not much we can do. I don't think I'm qualified to do this either.
Codewars says 2 people have successfully completed this in ruby, could one of those people confirm the description?
Yes.
I changed the last part of the description, it should be better now.
This comment has been hidden.
It's not, because you can't drop more than one eggs per try ;-)
That means that instructions are wrong:
"Which means,
You can throw multiple eggs in a single try. You are guaranteed to find the exactly maximal floor that the egg won't crack(the floor above this one will crack the egg). You have n eggs and m tries. What's the maximum height?"
You can throw multiple eggs if you want, but only from one floor. Since they are identical, I can't think of a reason to do so unless in (2,14) you just want to throw two eggs from floor 105 at the end so you don't have to carry the last one down.
I'm also baffled by the unclear description; what for instance is the definition of a 'try'? What does it mean to throw multiple eggs during one 'try'? I don't have a problem if your English is bad, but use a more formal description in that case.
You can figure out wtf it's talking about by reading other people's discussion in the discussion area. Many other people have the same problem as yours, and their questions are solved by other power users.
If you cannot understand wtf they're talking about you can ask them. Most of them are still active on CodeWars.
Originally there're lots of grammar mistakes. I've already corrected them. The original description is even more unreadable.
Please suggest as to how to improve the descriptions ;-) I know it's still kinda bad but just telling "you need to improve it" isn't going to help much. I know that already.
Dropping an egg and seeing if it breaks.
> You can throw one egg in a single try."Dropping an egg and seeing if it breaks." -> what does that mean in terms of the function? "you can throw one egg in a single try" -> that does not answer the question on multiple eggs
@ice1000 when so many people don't even understand what the kata is about, maybe the problem is not on them. It has nothing to do with grammar, it's just really poorly explained.
I'll pass.
Hi,
I'd really like to train with this kata, but I must admit I don't understand the basic of it. How am I supposed to evaluate that an egg cracked ?
You should consider all the possibilities(say, the worst condition)
If you see an egg breaks at floor n, you know it will broken at floors above n
I, too, was stumped when first reading this. But a little research on the web shows that this is actually a fairly common challenge, so there's plenty of material out there on it. But also recognize that this kata solves a slightly different part of the problem; Similar to the relationship between exponents, roots and logrithms (no, they're not used in this kata, that's just a metaphor).
@hufftheweevil Please try the performance version :D
That's the performance version? I thought this was! LOL I haven't even finished this kata. I've passed the first 3 tests, but can't get passed 4th. Still refactoring though...
Have you seen the data range?
This Kata:
That Kata:
For the record, the data range for
nis actuallyn <= 20000(it's like that in the original language too).I think this kata asks the maximum height that can be evaluated by n eggs and m trys. In other words, with a higher skycraper, there is no strategy to locate the exact floor through n eggs and m trys.
Go translation added.
Dart translation kumited!
Java translation kumited!
This comment has been hidden.
I still don't get it.
Why would I throw more than one egg at a time? What does it mean to throw two eggs? Do I have to throw them from the same floor? If so, how does it help to throw more than one? They'll either just both break or both survive, won't they? If not, what ?!? I can throw eggs from different floors at the same time?
I just don't see this puzzle.
And the examples don't help.
Without eggs, or if I can't drop 'em, sure, I won't be able to tell a thing. But 2 eggs, 14 drops, 105 floors isn't helpful. I don't see how many times you'd have to drop how many eggs from what floor to end up at 105.
https://www.codewars.com/kata/56d3f1743323a8399200063f
Maybe this kata will help explaining the process?
This solution is good and easy to understand.
Thank you.
This comment has been hidden.
Hi Voile, Could you pls change in the description (Haskell): from "You can throw multiple eggs in a single try." to "You can throw a single egg in a single try."
Done
I found same solution after a long time. I think the label "DYNAMIC PROGRAMMING" is kind of confusing. All the solutions in python are the same way. maybe the label "math" or something else is better?
Well, you can use memoization on this kata (Not the linear version though), so DP is a valid tag.
I guess I can add the mathematics tag to the kata.
Edit: Done
Typo fixed, Description modified, it's time to approve.
Would someone approve my Ruby translation please or indicate what needs changing?
Approved.
Thank you!
This kata's description is terrible! Please fix it.
Some grammatical mistakes are fixed.
It seems easier to understand now.
Haskell
I enjoyed that kata. I like how many times I thought I had cracked it, only to be told that my solution was still not fast enough. I would have stopped optimising long before the final solution, had it not been for the limited execution time. It's amazing that you can always squeeze out more performant code when you have to.
Irritating typo in the function name:
heigthshould beheight.I used an alias to solve this(so the typo is fixed and the old solutions won't be invalidated).
Closed.
Fix the typo in the function's name! (in Haskell)
Ask a native speaker to proofread your text - there are grammar mistakes.
I'd recommend to give a formal description of the problem after your informal introduction, which is not very clear.
Sorry, I know that my English is bad. One man slightly correct my description of this kata, and a can replace it this evening. But I need to republish kata to do this - I think it will not loss your solutions.
PS what about my second kata (Waring's problem) description?
I am not a native speaker too :) If you speak Russian, tezka, add me in Skype (bodigrim).
On Waring's problem. I'd rewrite it in the following way:
Beware, I'm not a native speaker!
Great kata, by the way.
I think it's Fabergé (acute accent).
I don't understand the problem description at all. How can you have 2 eggs and 14 tries ? What does that mean ?
To understand what does that mean is a part of task. I can explain this moment, but it would be a prompt. Anyway, kata was completed 3 times without any additional help from me. You must just think a little.
The description still needs some work. I can't provide one this time, since I'm not sure what the hell I'm supposed to do (yet).
Wow! Quite a challenging kata. I must have tried at least a half dozen approaches before I found a way to compute it that was fast enough. Well done!
Why I can not submit final my solution, which passed all tests?
UPD after 40 minutes I submit my solution - I think it was a site bag...