# toucel

Member

117

188 Neutral

• Rank
Member
1. ## Google Interview Puzzle : 2 Egg Problem

or a little more simply: unsigned int getMaxNumberOfDrops(unsigned int floorsCount) { return (unsigned int)ceil( (sqrt( 1.0 + 8.0*floorsCount ) - 1.0) / 2.0 ); } this is simply solving the quadratic formula (and because we are dealing with integers rounding to the highest int) x(x + 1) / 2 >= 100 x*x + x >= 200 ax*x + bx + c >= 0 a = 1 b = 1 c = -200 ( -b +- sqrt( b*b - 4ac ) ) / 2 = ( -1 + sqrt( 1 - 4*-200 ) ) / 2 = (sqrt( 1 + 800 ) - 1) / 2 note we do not need to consider the alternate case given to us by the quadratic formula because we are dealing with positive whole numbers in this case.
2. ## Google Interview Puzzle : 2 Egg Problem

Here is kind of a cleaned up version... int getNumberOfDrops(unsigned int floor, unsigned int topFloor) { if (floor < 1 || floor > topFloor) return -1; unsigned int step = (int)ceil( (sqrt( 1.0f + 8.0f*(float)topFloor ) - 1.0f) / 2.0f ); unsigned int curFloor = step; unsigned int drops = 0; while (++drops) { if (curFloor >= floor) { for (unsigned int i = step - 1; i > 0 && step > 1; --i) { drops++; if ( curFloor - i >= floor) break; } return drops; } curFloor += --step; if (curFloor > topFloor) { step = topFloor - (curFloor - step); curFloor = topFloor; } } return drops; } ... getNumberOfDrops(13, 100); //returns 14 ... [Edited by - toucel on December 8, 2006 5:09:08 PM]
3. ## Google Interview Puzzle : 2 Egg Problem

That was an interesting problem. Thanks for sharing. Here's some example code demonstrating (what we have found to be) the optimal searching pattern for an arbitrary number of total floors: unsigned int topFloor = 100; unsigned int brakeFloor = 14; unsigned int maxStep = (unsigned int)ceil( (sqrt( 1.0f + 8.0f*(float)topFloor ) - 1.0f) / 2.0f ); unsigned int step = maxStep; unsigned int curFloor = step; unsigned int drops = 0; while (1) { drops++; cout << "1st egg from #" << curFloor; if (curFloor >= brakeFloor) { cout << " *\n"; if (step > 1) { for (unsigned int i = step - 1; i > 0; --i) { drops++; cout << "\t2nd egg from #" << curFloor - i; if ( curFloor - i >= brakeFloor) { cout << " *"; break; } cout << "\n"; } } break; } cout << "\n"; curFloor += --step; if (curFloor > topFloor) { step = topFloor - (curFloor - step); curFloor = topFloor; } } cout << "\n\nTotal number of drops: " << drops << "\n\n"; Obviously this could (and should) be cleaned up considerably, but I tossed it here, in this format, in case anyone wanted to see it working. edit: that should have been "sqrt( 1.0f + 8.0f ..." not "sqrt( 1.0f - 8.0f ..." [Edited by - toucel on December 8, 2006 5:52:36 PM]
4. ## ray/lineseg vs triangle collision

When you are updating the position cast a ray from the current position to the projected end position and check against that using techniques found here: http://www.cs.lth.se/home/Tomas_Akenine_Moller/code/ if a collision is found, find the point of collision and you end up with a "correct" end position.

6. ## Nebulae, part III

Would it be possible to see a picture with only the "emission" coloring and another with only the reflection coloring? I am curious about the influence each has on the final render. Also could you detail the workings of the lookups for the speed and angle? Is speed simply = previous - current? Is it normalized in some fashion? Is the angle = acos( normalize( previous - current ) DOT normalize( next - current )? What do the lookup tables look like? I apologize for the abundance of questions; the technical details here really interest me.

8. ## ode to oblivion

Throw up some screenshots for those of us at work ;)

10. ## Shoreline extraction from a heightmap

here are my thoughts, they will not solve all of your specific needs/wants but they may provide some inspiration/thought my idea would be to use image space techniques, use pixel shaders to create a generic black and white map (alpha) of the heightmap. anything below the water level would be black and anything above would be white (you could also encode the specific depth etc in another color channel for other effects) you would then blur this image using another pixel shader you would be left with an image that has the length from the shoreline encoded in alpha, ie full white would be no distance to land and full black would be fully away from the area of waves I was thinking that you could animate the flow using this distance along with a time parameter and a 1 dimensional wave/flow map (you could use a 2 dimensional one as well but I am not sure how you would find the other coordinate to index into it, I suppose it could be simply a repeatable texture that is indexed by a combination of the relative x/z coordinates and perhaps some noise...) also you could use a noise texture to make it more diverse, you could even encode it in another of the channels
11. ## Rendering vegetation

also... humus.ca has some source for reference
12. ## [MDX] Normal mapping clouds, generating a normal map on GPU [SOLVED, shader inside!]

If you want to soften the normal, simply scale the normal. v * 0.75f, etc... you could also look into blurring...
13. ## guess the game II

Quote:Original post by ViLiO Quote:Original post by ViLiO I'm really quite proud of this one. I think the drawing is a fair representation of the game and I spent ages drawing Uranus [lol] Maximum cookies to anyone who can guess [grin] Nobody has had a go at this one of mine either [sad] I'll give you a hint, it was a nes game [grin] To the Earth... I had it too
14. ## HOW can THIS cause an error?

is the ; intentional? ;)
15. ## [4E4] Post yer Screenshots

Quote:Original post by AnonymousPosterChild Quote:Original post by meganfox Entry: Kasei Any real reason your screenshots have to be nearly a meg in siz,e each? It's because they look awesome ... ;)