Page 3 of 5 FirstFirst 12345 LastLast
Results 21 to 30 of 45

Thread: What's that code snippet?

  1. Top | #21
    Veteran Member
    Join Date
    Dec 2017
    Location
    Land of Smiles
    Posts
    1,068
    Rep Power
    15
    Snippet #5
    Code:
    unsigned char conundrum(unsigned char x)
    {
            static int booger[21] = {
                    0, 0, 0, 0, 0, 13, -13, 0, 13, -13 };
            return x + booger[(x + 7 * (x > 96)) / 13];
    }
    (1) What well-known(?) "useful" task does Snippet #5 do?
    (2) What simple changes make it equivalent to Steve Bank's Snippet #4?

  2. Top | #22
    Contributor
    Join Date
    Apr 2002
    Location
    Finland
    Posts
    5,111
    Archived
    6,261
    Total Posts
    11,372
    Rep Power
    76
    Quote Originally Posted by Swammerdami View Post
    Snippet #5
    Code:
    unsigned char conundrum(unsigned char x)
    {
            static int booger[21] = {
                    0, 0, 0, 0, 0, 13, -13, 0, 13, -13 };
            return x + booger[(x + 7 * (x > 96)) / 13];
    }
    (1) What well-known(?) "useful" task does Snippet #5 do?
    (2) What simple changes make it equivalent to Steve Bank's Snippet #4?
    That was a fun puzzle.

    (1) ROT13 encryption.
    (2) Replace booger with {0, 0, 0, 0, 0, 32, 32, 0, -32, -32 }

  3. Top | #23
    Contributor
    Join Date
    Nov 2017
    Location
    seattle
    Posts
    6,613
    Rep Power
    20
    Quote Originally Posted by Loren Pechtel View Post
    Quote Originally Posted by steve_bank View Post
    char conundrum(char x){
    if( (x >= 65) && (x <= 90) ) return (x | 0x20);
    if( (x >= 97) && (x <= 122) ) return x(x & 0xDF);
    return(x);
    }

    0x is hexadecimal
    I'm pretty sure this flips the case of the character, doesn't alter anything else.

    And anyone that can follow that code would know what 0x means.
    Just pretty sure?

    There is really nothing new.

  4. Top | #24
    Contributor
    Join Date
    Nov 2017
    Location
    seattle
    Posts
    6,613
    Rep Power
    20
    Quote Originally Posted by steve_bank View Post
    char conundrum(char x){
    if( (x >= 65) && (x <= 90) ) return (x | 0x20);
    if( (x >= 97) && (x <= 122) ) return x(x & 0xDF);
    return(x);
    }

    0x is hexadecimal
    In 8 bit ASCII but 6 indicates case for letters. Bit wise AND to clear a bit and OR to set a bit.

  5. Top | #25
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    14,870
    Archived
    16,829
    Total Posts
    31,699
    Rep Power
    93
    I have oodles of examples that I've accumulated over the years.

    For instance, this algorithm makes the Sierpinski gasket. It's in Mathematica, but it should not be very difficult to understand.

    SGNextArray = ConstantArray[1,{3,3}]; SGNextArray[[2,2]] = 0;
    SGNext[arr_] := Module[{dims,k1,k2},
    dims = Dimensions[arr];
    ArrayFlatten[Table[arr[[k1,k2]]*SGNextArray,{k1,dims[[1]]},{k2,dims[[2]]}]]
    ]
    SGCpt[n_] := NestList[SGNext,{{1}},n]
    ArrayPlot /@ SGCpt[4]


    It makes each new array in sequence with:
    {{a, a, a}, {a, 0, a}, {a, a, a}}
    {{full, full, full}, {full, empty, full}, {full, full, full}}
    and then flattens it in each array dimension

    Here, a is the previous array that the algorithm generated, and its initial state is {{1}} (all full).

  6. Top | #26
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    14,870
    Archived
    16,829
    Total Posts
    31,699
    Rep Power
    93
    Here's how to make the Koch snowflake.

    One starts with a triangle:

    forward, 120d right, forward, 120d right, forward, 120d right

    Then replaces each edge with

    forward, 60d left, forward, 120d right, forward, 60d left, forward

    and then repeats this operation

    Functions
    (* Construct the points with 3*3 matrices: {rotation | translation - 0 | 1 } *)
    (* Primitives are translation and rotation -- can also do reflection if desired *)
    PrZero = {{{1,0},{0,1}},{0,0}};
    PrTrans[x_] := {{{1,0},{0,1}},x}
    PrRot[a_] := {{{Cos[a],-Sin[a]},{Sin[a],Cos[a]}},{0,0}}
    (* Data format: init (initial), next (production rules: symbols become lists of symbols), geom (geometrical interpretations) *)
    (* Functions for making a curve *)
    LSNext[params_,curve_] := Flatten[curve /. params["next"],1]
    LSSeq[params_,nmax_] := NestList[LSNext[params,#]&,params["init"],nmax]
    LSTraverse[pr1_,pr2_] := {pr1[[1]].pr2[[1]],pr1[[2]]+pr1[[1]].pr2[[2]]}
    LSGeom[params_,curve_] := FoldList[LSTraverse,PrZero,curve /. params["geom"]]
    LSGeomSeq[params_,nmax_] := LSGeom[params,#]& /@ LSSeq[params,nmax]
    LSPoints[curve_] := First /@ Split[#[[2]]& /@ curve]
    LSMakeCurves[params_,nmax_] := LSPoints /@ LSGeomSeq[params,nmax]
    ColoredLine[pts_] := Module[{npts,k},
    npts = Length[pts];
    Line[pts,VertexColors->If[npts>=3,Table[Hue[(k-1)/(npts-1)],{k,npts}],None]]
    ]
    ShowLines[ptsets_] := Graphics[Line[#]]& /@ ptsets
    ShowColoredLines[ptsets_] := Graphics[ColoredLine[#]]& /@ ptsets

    Koch Snowflake Curve
    (* 1: F segment, 2: +, 3: -- Angle: 60d *)
    KochSnowParams["init"] ={1,3,1,3,1,3};
    KochSnowParams["next"] = {1->{1,2,1,3,1,2,1},2->{2},3->{3}};
    KochSnowParams["geom"] = {1->PrTrans[{1,0}], 2->PrRot[Pi/3], 3->PrRot[-2Pi/3]};
    ShowColoredLines[LSMakeCurves[KochSnowParams,4]]

  7. Top | #27
    Veteran Member
    Join Date
    Dec 2017
    Location
    Land of Smiles
    Posts
    1,068
    Rep Power
    15
    Working commented code is good, but that's not what this game thread is about. Let me show what I had in mind. I'll use C for these examples.

    In Snippets #8-#11, we're asked to guess what function the code implements, or at least in what application it arises.
    #8 is from real code. #9-#11 have had names degraded to make the purpose less obvious.

    Snippet #8:
    Code:
            retval = -EAGAIN;
            if (atomic_read(&p->real_cred->user->processes) >=
                            task_rlimit(p, RLIMIT_NPROC)) {
                    if (p->real_cred->user != INIT_USER &&
                        !capable(CAP_SYS_RESOURCE) && !capable(CAP_SYS_ADMIN))
                            goto bad_fork_free;
            }
            current->flags &= ~PF_NPROC_EXCEEDED;
    Snippet #9:
    Code:
    double foo(double to[2], double fro[2])
    {
            double  z = cos(to[0]) * cos(fro[1] - to[1]);
            double  y = sin(to[0]);
            y = - sqrt(y*y + z*z) * cos(atan2(y, z) - fro[0]);
            return 6371 * (3.14159 / 2 + atan2(y, sqrt(1 - y*y)));
    }
    Snippet #10:
    Code:
            unsigned long  m = ~0;
            printf("%d\n", (int)((m)/((m)%255+1)/255%255*8 + 7-100/((m)%255+14)));
    Snippet #11:
    Code:
    struct     { double x, y; }     A[4];
    #define     B(a,b,q)           (A[a].q - A[b].q)
    #define     C(a,b,c)           (B(a,b,x) * B(c,a,y) > B(c,a,x) * B(a,b,y))
    #define     DD                 (1 ^ C(0,1,2) ^ C(1,2,3) ^ C(2,3,0) ^ C(3,0,1))
    The next Snippet is the opposite. We're told what the snippet does and asked to write it.
    I still remember when someone showed me the solution 52 years ago. I thought it was neat!
    I suppose it is well known.

    Snippet 12:
    Code:
    /* y = lastbit(x) should return
     *    00000000000010000 when x is
     *    01101110110010000
     * or more generally
     *    0000000010000... when z is
     *    xxxxxxxx10000... where 'x' means don't care.
     *
     * Note that either
     *          x ^= lastbit(x);
     * or
     *          x &= ~lastbit(x);
     * will delete the right-most bit from x.
     */
    int lastbit(int y);

  8. Top | #28
    Contributor
    Join Date
    Apr 2002
    Location
    Finland
    Posts
    5,111
    Archived
    6,261
    Total Posts
    11,372
    Rep Power
    76
    Quote Originally Posted by Swammerdami View Post
    The next Snippet is the opposite. We're told what the snippet does and asked to write it.
    I still remember when someone showed me the solution 52 years ago. I thought it was neat!
    I suppose it is well known.

    Snippet 12:
    Code:
    /* y = lastbit(x) should return
     *    00000000000010000 when x is
     *    01101110110010000
     * or more generally
     *    0000000010000... when z is
     *    xxxxxxxx10000... where 'x' means don't care.
     *
     * Note that either
     *          x ^= lastbit(x);
     * or
     *          x &= ~lastbit(x);
     * will delete the right-most bit from x.
     */
    int lastbit(int y);
    Seems rather easy, so I think what you are looking for is some elegant but non-obvious solution.

    Code:
    int lastbit(int y)
    {
        int ret = 1;
        if (y == 0)
            return 0;
        for (; y & 1 == 0; y = y >> 1)
            ret << 1;
        return ret;
    }
    Is there a better way?

  9. Top | #29
    Veteran Member
    Join Date
    Dec 2017
    Location
    Land of Smiles
    Posts
    1,068
    Rep Power
    15
    Quote Originally Posted by Jayjay View Post
    Quote Originally Posted by Swammerdami View Post
    The next Snippet is the opposite. We're told what the snippet does and asked to write it.
    I still remember when someone showed me the solution 52 years ago. I thought it was neat!
    I suppose it is well known.

    Snippet 12:
    Code:
    /* y = lastbit(x) should return
     *    00000000000010000 when x is
     *    01101110110010000
     * or more generally
     *    0000000010000... when z is
     *    xxxxxxxx10000... where 'x' means don't care.
     *
     * Note that either
     *          x ^= lastbit(x);
     * or
     *          x &= ~lastbit(x);
     * will delete the right-most bit from x.
     */
    int lastbit(int y);
    Seems rather easy, so I think what you are looking for is some elegant but non-obvious solution.

    Code:
    int lastbit(int y)
    {
        int ret = 1;
        if (y == 0)
            return 0;
        for (; y & 1 == 0; y = y >> 1)
            ret << 1;
        return ret;
    }
    Is there a better way?
    A simple one-liner suffices. No loop is needed.

    ~ ~ ~ ~ ~ ~ ~ ~ ~
    By the way, with C's operator precedence rules
    . . . . y & 1 == 0
    is treated as
    . . . . y & (1 == 0)
    I think you want your parentheses elsewhere.

    (I often make the same mistake. This precedence rule seems quite wrong, though it comes with an easy-to-remember mnemonic. You also need to add a keystroke to "ret << 1")

  10. Top | #30
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    14,870
    Archived
    16,829
    Total Posts
    31,699
    Rep Power
    93
    Quote Originally Posted by Swammerdami View Post
    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.
    It looks like a pair of random selections:

    Items in the list rhp: indices 0 to (size-1)
    Items in the list rhp->rh_item: indices 0 or 1

    In the first one, it's best to do something like
    int fint = (int)f
    if (fint >= size) fint = size - 1

    in case unif_rand returns exactly 1.0

Posting Permissions

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