Page 1 of 5 123 ... LastLast
Results 1 to 10 of 48

Thread: What's that code snippet?

  1. Top | #1
    Squadron Leader
    Join Date
    Dec 2017
    Location
    Land of Smiles
    Posts
    1,462
    Rep Power
    16

    What's that code snippet?

    There are several programmers here at TFT. Let's play a game. (I might have posted this in the Games subforum but there doesn't seem to be one.)

    Post a code snippet (in any programming language) and/or guess the intent or context of a prior submission. Submissions may be made in any language, and with whatever level of obfuscation etc. seem most appropriate. Consider the problem space to be quite flexible: if you wish you can reverse the puzzling and pose a task, asking for a code snippet. Or the snippet might have a bug, with identifying or fixing the bug being the puzzle.

    I'll start. The cute and useful algorithm that this snippet helps implement is mentioned in one of Knuth's books. If unfamiliar with that algorithm, careful contemplation of this snippet MIGHT lead you to guess the context and re-discover an elegant algorithm.

    Snippet #1
    Code:
    ITEM item_rand(struct rhtable *rhp, int size)
    {
           double f = unif_rand(0.0, 1.0) * size;
           rhp += (int)f;
           return rhp->rh_item[f > rhp->rh_splitp];
           // return rhp->rh_item[f - (int)f > rhp->rh_splitp ? 1 : 0];
    }
    An alternative (somewhat less obfuscated?) return statement is shown commented-out.

  2. Top | #2
    Elder Contributor barbos's Avatar
    Join Date
    Nov 2005
    Location
    Mlky Way galaxy
    Posts
    11,939
    Archived
    8,047
    Total Posts
    19,986
    Rep Power
    70
    unif_rand() looks like a random number generator

    It selects random element from structure array and then use relative position and split level to return first or second element of some two element array.

    Do I get half prize for that? I have never read Knuth's books.

  3. Top | #3
    Squadron Leader
    Join Date
    Dec 2017
    Location
    Land of Smiles
    Posts
    1,462
    Rep Power
    16
    Quote Originally Posted by barbos View Post
    unif_rand() looks like a random number generator

    It selects random element from structure array and then use relative position and split level to return first or second element of some two element array.

    Do I get half prize for that? I have never read Knuth's books.
    You're correct about unif_rand(), but what useful task is being implemented here? While 99+% of programmers would never have reason to use this function, the task for which it provides a simple fast approach has broad application. When might you want to "select a random element from an array"? Why might the task be tediously slow without a special cleverness (as the approach Snippet #1 supports will be seen to possess)?

    It would be permitted in the game to write xxx() or foo() instead of unif_rand() to make a snippet more difficult. But guessing the detailed purpose of this particular snippet is already a big challenge, and I didn't want snippet #1 to be too obnoxious. :-)

    I'll post hints tomorrow, but meanwhile: Please submit other interesting code snippets using any criteria: elegance, efficiency, amusement, concisement, stupidity, novelty, etc.

  4. Top | #4
    Elder Contributor barbos's Avatar
    Join Date
    Nov 2005
    Location
    Mlky Way galaxy
    Posts
    11,939
    Archived
    8,047
    Total Posts
    19,986
    Rep Power
    70
    What's the prize anyway? And I don't think commented part is equivalent to the current one. I suspect commented version is correct one.



    And the whole thing just selects random subboxes of boxes of equal sizes split unevenly into 2 subboxes.

    rh_splitp= Random Hole Split Probability.

    I think I have got it.
    probability to fall into random sub-hole.



    Give me my prize!

  5. Top | #5
    Squadron Leader
    Join Date
    Dec 2017
    Location
    Land of Smiles
    Posts
    1,462
    Rep Power
    16
    Quote Originally Posted by barbos View Post
    What's the prize anyway? And I don't think commented part is equivalent to the current one. I suspect commented version is correct one.
    There is a setup() routine needed to initialize the appropriate values into R[].rh_splitp, R[].rh_item[0] and R[].rh_item[1]. That setup() routine will need to know whether the silly micro-optimization in the uncommented 'return' is used or not.

    And the whole thing just selects random subboxes of boxes of equal sizes split unevenly into 2 subboxes.
    But WHY? Is there some special reason why a selection would be organized this way? How many distinct ITEMS do you think are in the table anyway?


    Let's get some more interesting snippets! No further hints on Snippet #1 until there are more snippets enlivening the thread!

  6. Top | #6
    Contributor
    Join Date
    Apr 2002
    Location
    Finland
    Posts
    5,173
    Archived
    6,261
    Total Posts
    11,434
    Rep Power
    77
    I agree that the commented out return statement is not equivalent to the one that's not. The former checks if the decimal part of f is larger than splitp, implying that splitp is a floating point between 0 and 1. The latter checks if f is greater than splitp. Hmm.



    The question of my snippet is, what the heck is it and what does it do?

  7. Top | #7
    Super Moderator
    Join Date
    Sep 2000
    Location
    Nevada
    Posts
    32,341
    Archived
    96,752
    Total Posts
    129,093
    Rep Power
    100
    Quote Originally Posted by Jayjay View Post
    I agree that the commented out return statement is not equivalent to the one that's not. The former checks if the decimal part of f is larger than splitp, implying that splitp is a floating point between 0 and 1. The latter checks if f is greater than splitp. Hmm.



    The question of my snippet is, what the heck is it and what does it do?
    Is your picture supposed to be an answer??


    Anyway, my guess: Bleeding together zones of two different colors. Since I refuse to learn C I'm not at all sure of this.

  8. Top | #8
    Contributor
    Join Date
    Apr 2002
    Location
    Finland
    Posts
    5,173
    Archived
    6,261
    Total Posts
    11,434
    Rep Power
    77
    Quote Originally Posted by Loren Pechtel View Post
    Quote Originally Posted by Jayjay View Post
    I agree that the commented out return statement is not equivalent to the one that's not. The former checks if the decimal part of f is larger than splitp, implying that splitp is a floating point between 0 and 1. The latter checks if f is greater than splitp. Hmm.



    The question of my snippet is, what the heck is it and what does it do?
    Is your picture supposed to be an answer??


    Anyway, my guess: Bleeding together zones of two different colors. Since I refuse to learn C I'm not at all sure of this.
    No. Just to clarify, the picture is a new snippet, unrelated to the algorithm in the opening post. Should have made that more clear.

  9. Top | #9
    Squadron Leader
    Join Date
    Dec 2017
    Location
    Land of Smiles
    Posts
    1,462
    Rep Power
    16
    Snippet #2


    My initial reaction is that this was a snippet of a Mondrian painting, but Google Images suggests that Piet Mondrian economised on paint and never used esoteric colors like cyan or violet!

    In a similar vein, I submit

    Snippet #3


    17/91; 78/85; 19/51; 23/38; 29/33; 77/29; 95/23; 77/19; 1/17; 11/13; 13/11; 15/2; 1/7; 55/1

  10. Top | #10
    Squadron Leader
    Join Date
    Dec 2017
    Location
    Land of Smiles
    Posts
    1,462
    Rep Power
    16
    Quote Originally Posted by Jayjay View Post
    I agree that the commented out return statement is not equivalent to the one that's not. The former checks if the decimal part of f is larger than splitp, implying that splitp is a floating point between 0 and 1. The latter checks if f is greater than splitp. Hmm.
    This was addressed in the post immediately before yours. Let me be more explicit:

    (1) item_rand() utilizes TWO random numbers: (a) an integer in the range {0, 1, 2, ..., size-1} and a "splitting" probability 0 < p < 1.
    (2) item_rand() derives BOTH the random numbers it needs from a SINGLE call to a random-number generator.
    (3) Since item_rand() may be called millions of times while setup() is called only once, a TINY bit of time can be saved by adding K to R[K].rh_splitp. Obviously setup() and item_rand() must agree on whether this micro-optimization is in use or not! setup() is a MUCH longer routine than item_rand() and is NOT shown.

    The optimizations (2) and (3) are much less interesting than the algorithm implemented by setup()/item_rand(). It can be used by MANY simulation programs and does what it does MUCH faster than a naive approach.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •