What's that code snippet?

[Swammerdami]

Snippet #5

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?

 

[Jayjay]

Snippet #5

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 }

 

[steve_bank]

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.

 

[steve_bank]

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.

 

[lpetrich]

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).

 

[lpetrich]

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]]

 

[Swammerdami]

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:

        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:

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:

        unsigned long  m = ~0;
        printf("%d\n", (int)((m)/((m)%255+1)/255%255*8 + 7-100/((m)%255+14)));

Snippet #11:

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:

/* 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);

 

[Jayjay]

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:

/* 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.

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?

 

[Swammerdami]

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:

/* 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.

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")

 

[lpetrich]

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

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

 

[lpetrich]

About Snipped #2, it is supposed to represent a quadtree? That's a binary tree extended to two dimensions.

Snippet #3
View attachment 32282

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

In Mathematica form:
{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}

I factored the numerators and denominators:
{(17)/(7*13), (2*3*13)/(5*17), (19)/(3*17), (23)/(2*19), (29)/(3*11), (7*11)/(29), (5*19)/(23), (7*11)/(19), (1)/(17), (11)/(13), (13)/(11), (3*5)/(2), (1)/(7), (5*11)/(1)}

I can detect some patterns, but not a lot.

 

[lpetrich]

Snippet #8:

        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;

Looks like a test for whether one can create some process.

Snippet #9:

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)));
}

Looks like a formula for distances on a sphere.

For radius rad, latitudes lat1, lat2, longitudes lat2, lng2, the formula is

dist = rad * arccos(dz)
where
dz = sin(lat1)*sin(lat2) + cos(lat1)*cos(lat2)*cos(lng2 - lng1)

The atan is from the identity arccos(x) = arctan( sqrt(1-x^2) / x )

This formula has an awkward cancellation for points near each other, so there are alternatives:

dist = rad * 2 * arcsin(dzx)

dzx = sqrt( sin( (lat1-lat2)/2 )^2 + cos(lat1)*cos(lat2)*sin( (lng1-lng2)/2 )^2 )

Or else

dx = cos(lat1)*sin(lat2) - sin(lat1)*cos(lat2)*cos(lng2 - lng1)

dy = cos(lat2)*sin(lng2 - lng1)

dist = rad * arctan(sqrt(dx^2+dy^2)/dz)

That also gives the bearing angle at point 1, from arctan(dy/dx)
The bearing angle at point 2 one calculates by reversing 1 and 2.

For close points,
dx = sin(lat2 - lat1) + 2*sin(lat1)*cos(lat2)*sin( (lng2-lng1)/2 )^2

 

[lpetrich]

Snippet #10:

        unsigned long  m = ~0;
        printf("%d\n", (int)((m)/((m)%255+1)/255%255*8 + 7-100/((m)%255+14)));

The term (int)((m)/((m)%255+1)/255%255*8 I can interpret:

~0 is all ones, and is 2^(nbts)-1 for (nbts) bits.

This is 2^(8*nbytes) - 1

255 = 2^8 - 1, and the quotient is sum of 2^(8*k) for k = 0 to (nbytes)-1. The remainder is 0.

Snippet #11:

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))

Seems like a test for polygon convexity. It works by taking sets of consecutive vertices and finding the area of each triangle that they make. Since this test uses rectangular coordinates, it uses the shoelace formula for each triangle's area.
(Area) = (unsigned area) * (winding number)

where the winding number is 1 or -1 depending on whether the points are in clockwise or counterclockwise order. Or the reverse: be careful about signs here.

If all the triangles have the same winding number, then the polygon is convex. Otherwise, it has at least one concave spot.

 

[Swammerdami]

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

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];
}

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

Yes, it is a pair of random selections. The challenge is to "reverse engineer" and guess how it is a very elegant solution. WHY do these two random selections provide a big shortcut for a common-place problem? This routine was used to generate the output shown in post #12.

Your concern about unif_rand() is appropriate for some implementations of unif_rand(). But that overflow does not arise in proper(!) implementations where unif_rand(a, b) returns x strictly a < x < b. (This is among the reasons that I, for one, always "roll my own" random subs.)

About Snipped #23, it is supposed to represent a quadtree? That's a binary tree extended to two dimensions.

I've already commented on Snippet #3 in post #17; it implements the Sieve of Eratosthenes in a whimsical language ( FRACTRAN).

 

[rousseau]

This is my favourite code snippet:

if(afterFourPM) {
    shutDownIDE();
    eatSteak();
    getLaid();
}

What is this one doing?

I kid. Mostly a comment on my avoidance of code puzzles. I like programming, but I like being paid to program. After 4 give me a steak.

 

[lpetrich]

Shoelace formula for the area of a triangle with vertex locations in rectangular coordinates x(i) for i in 1 to n

Area = (1/2) * sum over i of x(i).eps2.x(j)
where j = i + 1 for i < n, 1 for i = n

eps2 = antisymmetric symbol = {{0,1},{-1,0}}

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:

/* 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);

The specification there looks incomplete. What happens when any of the lowest digits are 1?

 

[steve_bank]

unsigned int foo(unsigned int x, int y){
unsinged int l = 0x10000000, m = 0x7fffffff; o = 0x00000001;
int i = 0, j = 0, k = 0;
while (++i < 31){ if((x & o) j++;o = o<<1;}
if(j%2 == 0) k =1;
if(y && k) return(x & m; else return(x | l);
if(!y && k) return(x | l); else return(x & m);
}

 

[Swammerdami]

As Ipetrich writes, #8 is indeed a test in the Linux kernel called for every attempt to create a process. And #9 does indeed calculate "great circle" distances on a sphere, or on specifically a spherical approximation to Earth. Well done!

Snippet #10:

        unsigned long  m = ~0;
        printf("%d\n", (int)((m)/((m)%255+1)/255%255*8 + 7-100/((m)%255+14)));

The term (int)((m)/((m)%255+1)/255%255*8 I can interpret:
... The remainder is 0.

Not quite. Hints:
(1) The code, however peculiar, actually does something useful! If (~0) is a constant, the code will print a constant. How can that be useful?
(2) The code does not rely on a 'long' comprising a whole number of 8-bit bytes.
(3) The highly peculiar arithmetic can be considered a fetish! There is similar fetishist code to, for example, derive day of the week from a date.

Snippet #11:

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))

Seems like a test for polygon convexity. It works by taking sets of consecutive vertices and finding the area of each triangle that they make.

Right for the wrong reason! Any "areas" calculated are not the areas you speak of. The code short-circuits one issue by relying on a property that polygons with more than 4 sides lack.

 

[steve_bank]

unsigned int foo(unsigned int x, int y){
unsinged int l = 0x10000000, m = 0x7fffffff; o = 0x00000001;
int i = 0, j = 0, k = 0;
while (++i < 31){ if((x & o) j++;o = o<<1;}
if(j%2 == 0) k =1;
if(y && k) return(x & m; else return(x | l);
if(!y && k) return(x | l); else return(x & m);
}

I knw the suspense is at the breaking point.

This is a single bit parity generator. Y = 0 odd parity, 1 even parity. Count the bits and set the parity bit accordingly. 4 possible logical combinations.

 

[Jayjay]

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:

/* 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.

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.

Finally got it.

int lastbit(int y)
{
    return ((x-1)^x)&x;
}

x-1 sets the last bit to 0, and all preceding bits before it to 1. XOR with original x to clear the irrelevant bits to zero. AND with original leaves only the desired bit active. It seems to work also for 0 and negative numbers, which is neat.