• Advertisement

toucel

Member
  • Content count

    117
  • Joined

  • Last visited

Community Reputation

188 Neutral

About toucel

  • 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.
  5. Lucid dreams

    I tend to have lucid dreams fairly regularly, though they normally seem to occur near the time I will be waking anyways. I have gotten fairly good at being able to control the dreams though I too fight to maintain the control. Ususally when I find that I am part of a dream I do not tend to "play god," though I have done this too on occasion ( flying above a city, bouncing off of walls, doing all kinds of crazy aerobatics etc ;) ). Because I am normally within an already running dream I tend to actively "steer" the current story of the dream. I often put myself in interesting situations, even some that are quite scary (in the end I really enjoy most of them though) Sometimes my mind works against me in this lucid state. I will be reforming the direction of the dream and in doing so doubts will enter my mind. These doubts can cloud and overtake the positive elements. For example: I'm in a hallway running away from something, I am lucid but still within the restrictions I have placed upon the dream world. If I were to begin thinking about how scary it would be if the lights all went out, even if I realized that I should not think about that (because I am aware within my lucid state (thru experience, I guess) that these thoughts my interfere with my intent) and begin attempting to push them out, the very act of thinking these thoughts and thinking to not think about them causes a chain reaction and it can be quite difficult to regain full control at that point. Of course at that time, the lights would ususally go out. I have had a very vivid false awakening: My father woke me up for school, as he did every morning. I didnt want to get up initially, but I did. I proceeded to get ready with the normal routine. I changed clothes, brushed, did my hair, etc. This took about 15 minutes. Then, from far away, I heard someone yelling. I was confused because it was so distant but definitely directed towards me. I suddenly awoke in my bed, extremely confused. I wondered how I got back there, why I didnt have my school clothes on, etc. I then heard the yelling again and found that my father had been yelling at me because I had NOT gotten up and was about to miss my bus. It was hard to dismiss what had happened, it had felt so real. It was an amazing experience that I still remember well. Once I did figure out what had happened, I was quite annoyed, given the situation. In my mind I had just spent about 15 minutes getting ready - now that time was gone and I wasnt even prepared for the bus that was almost there. ;) I had another strange dream that is perhaps tangential to the topic here but could be relevant: I was feeling really sick one day, and I was having a hard time sleeping. I eventually was able to but I was right on the edge of being asleep and awake (or at least it felt like that) and I remember looking at myself (after falling asleep but not realizing it) I watched what was essentially a hud overlay over my entire body. It detailed (thru individal sprites) the body's immune systems' response to the cold I had. I watched as thousands of sprites would attack. Once I had realized what was happening I was able to take some control of the system. I noticed key areas that were not receiving enough attention from my immune system, so I redeployed some to compensate (it felt almost like an rts) I did this for what seemed to be quite a long time. I then woke somewhat abruptly in the middle of the night. I remember being astounded by how much better I felt :) One more, while we are at it: I once had a dream where I was in a library. There were many books in bookcases and a lone librarian. I could tell something was not right about the place and I approached the man. I asked him about the place. He basically smiled, set down a book he was holding, and explained that I was not in a library. He said that this was all in my head. He went further and explained that he was a representation of my subconcious. I talked with him further and though I dont remember all that was said I recall him describing how even though I might not be actively/conciously working on the solution to a problem in my head that "he" was often working on it for me. I have been trying, off and on, to induce some of these things and have done extensive research on the subject. Interested parties may wish to look into binural beats, and perhaps saltcube.com's timer or something similar good dreaming, -toucel
  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.
  7. I rewrote what you offered here. Functionally it is almost identical (so I dont think you'd get any real appreciable speed difference). In the end the focus was on more encapsulation and a cleaner coding style. quadtree.h //////////////////////////////////////////////////////////// class cNode { public: vec3 b[4], center; cNode *child[4]; bool leaf; cNode() { for (int i = 0; i < 4; ++i) child[i] = NULL; leaf = false; } }; //////////////////////////////////////////////////////////// class cQuadTree { private: cNode *root; cNode *initNode(vec3 bound[4]); void closeNode(const cNode *pcNode); void renderNode(const cNode *pcNode); unsigned int patchVertexSize; public: cQuadTree() { patchVertexSize = 0; root = NULL; } ~cQuadTree(){ if (root != NULL) delete root; } void init(float size, unsigned int finalVertSize); void render(); }; //////////////////////////////////////////////////////////// and quadtree.cpp //////////////////////////////////////////////////////////// void getBounds(vec3 out[4], vec3 offset, float size, unsigned int i) { vec3 shift; if (i == 1) shift = vec3(size, 0.0f, 0.0f); else if (i == 2) shift = vec3(0.0f, 0.0f, size); else if (i == 3) shift = vec3(size, 0.0f, size); out[0] = offset + shift; out[1] = offset + vec3(size, 0.0f, 0.0f) + shift; out[2] = offset + vec3(0.0f, 0.0f, size) + shift; out[3] = offset + vec3(size, 0.0f, size) + shift; } //////////////////////////////////////////////////////////// cNode *cQuadTree::initNode(vec3 bound[4]) { float size = bound[1].x - bound[0].x; unsigned int i; cNode *newcNode = new cNode; newcNode->center = (bound[3] - bound[0]) * 0.5 + bound[0]; for (i = 0; i < 4; ++i) newcNode->b[i] = bound[i]; if ((int)size == patchVertexSize) { newcNode->leaf = true; //insert leaf data } else { vec3 b[4]; for (int i = 0; i < 4; ++i) { getBounds(b, bound[0], size/2.0f, i); newcNode->child[i] = initcNode(b); } } return newcNode; } //////////////////////////////////////////////////////////// void cQuadTree::closeNode(const cNode *pcNode) { for (int i = 0; i < 4; ++i) if (pcNode->child[i] != NULL) closecNode(pcNode->child[i]); delete pcNode; } //////////////////////////////////////////////////////////// void cQuadTree::renderNode(const cNode *pcNode) { if (pcNode == NULL) return; if (!pcNode->leaf) for (int i = 0; i < 4; ++i) rendercNode(pcNode->child[i]); else { //render leaf data } } //////////////////////////////////////////////////////////// void cQuadTree::render() { rendercNode(root); } //////////////////////////////////////////////////////////// void cQuadTree::init(float size, unsigned int finalVertSize) { vec3 b[4]; patchVertexSize = finalVertSize; getBounds(b, vec3(0.0f, 0.0f, 0.0f), size, 0); root = initcNode(b); } //////////////////////////////////////////////////////////// note that I have taken out the initial requirement of specifying the bounds - this was intentional; as I see it, almost all applications of a quadtree would require a square shape (as opposed to some arbitrary quad) also in this example we could put the quadtree::init code into the constructor instead (and it would probably be a bit cleaner) but I kept it seperated in case there was an issue of "timing" later down the line (ie the data to fill the leafs was not yet loaded etc) depending on the end result you are looking for it may be better to initially construct this (within the constructor) and then add any data ("parsing" it as it comes down among the quadtree nodes and placing it within the correct nodes) Another thing, if you wish to make this general purpose you are going to have to look at the possibility of a piece of leaf data spanning more than one node and evaluate what you want to do with it. It may be possible to split the data amongst the overlap, or to simply add the data to the node that encompasses it whilst maintaining the ability for other data to drop to the other node children - this would effectively allow nodes to contain leaf information as well as children. so, anyway, to create the quadtree we simply do this: cQuadTree qTree; qTree.init(512, 64); ... qTree.render(); If anyone has any questions / comments please share...
  8. ode to oblivion

    Throw up some screenshots for those of us at work ;)
  9. Kevin J. Anderson [rant warning]

    I had the "opportunity" to go see Brian Herbert give a small presentation at a local Barnes and Noble. I was greatly unimpressed, and left feeling quite saddened. His general manner and attitude seemed to suggest that all of his stories were thrown together and they were working towards volume instead of quality. The story arcs were set within much shorter attention spans. I had read a couple of his books, prequels to Dune. I really wanted to like them, but was thoroughly disappointed. The only really interesting part of the talk was when he was talking about his father and what life was like growing up in there household. Near the end, one gentlemen asked about the yellow in the eyes of some creature from some other Dune book of his (obviously I havent read it) and wondered if there was a connection with the Honored Matres (later in the original Dune series) Brian paused, then responded that he had never thought about that and thought it was a really good idea. I was slightly surprised that the author hadnt thought about this - great attention has been devoted to the eyes of characters in the series. Also the way he seemed to adopt the idea and run with it made me really question his "long term" ideas. It's kind of hard for me to explain exactly and I understand that inspiration will come from many places etc, but the demeanor was simply offsetting. He was not condescending or anything, he just didnt seem like he was really at the wheel or at the very least had no clue where he was going.
  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. 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 ... ;)
  • Advertisement