|
Hey folks, I don't generally post on these forums, but I do enjoy the CP newsletters. Anyways, I wanted to share a lovely snippet I wrote a little while ago. Maybe get some opinions? It's a bubble sort in C. It generates 20 random numbers from 0 to 99, and sorts them! Of course, it's fairly straightforward, so I'm sure you could guess that.
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#define ARRAY_SIZE 20
#define PNT(s, l, a) fprintf(std##s, l, a)
#define PNT2LINES(s, l1, l2, e) PNT(s, #l1#e#l2#e, 0)
void print_array(int *array) {
int x = ARRAY_SIZE;
char* fmts[] = { "%d, ", "%d\n" };
--array;
LBL0:
if (PNT(out, ((x == 1) & 1)[fmts], *(array = ++array)), --x > 0)
goto LBL0;
}
main() {
int iarray[ARRAY_SIZE];
int x, y;
int ofs = iarray - &ofs;
void (*prnt_func)(int*) = &print_array;
srand((unsigned int)time(NULL));
x ^= x;
LBL1:
if ((y = rand(), x < ARRAY_SIZE) && ((((x = x + 1) - 1)[iarray] = (y - (y / 100) * 100)) || 1))
goto LBL1;
PNT2LINES(out, Before sort, ---------------, \n);
(*prnt_func)(&ofs + ofs);
LBL2:
y = x &= ~x;
LBL3:
if (y + 1 < ARRAY_SIZE) {
if ((++y, iarray[y] < (y-1)[iarray]) && (y[iarray] ^= iarray[y-1] ^= iarray[y] ^= *(iarray + y - 1), x |= y));
goto LBL3;
}
if (x = x) goto LBL2;
PNT2LINES(out, After sort, ---------------, \n);
(*prnt_func)(&ofs + ofs);
}
|
|
|
|
|
Raise your hands, and step away from the keyboard, sir.
Did you know:
That by counting the rings on a tree trunk, you can tell how many other trees it has slept with.
|
|
|
|
|
I think my breakfast just revisited.
Why-oh-why-oh-why would you want to do that?
|
|
|
|
|
Yup. It's a horror.
Regards
David R
---------------------------------------------------------------
"Every program eventually becomes rococo, and then rubble." - Alan Perlis
The only valid measurement of code quality: WTFs/minute.
|
|
|
|
|
This was for an obfuscated C contest, right?
RIGHT?
(Must resist the urge to trace through it...)
He said, "Boy I'm just old and lonely,
But thank you for your concern,
Here's wishing you a Happy New Year."
I wished him one back in return.
|
|
|
|
|
nah, just felt like doing it
|
|
|
|
|
We're not taking our meds now, are we?
|
|
|
|
|
Wow... that's kind of a tour de force.
|
|
|
|
|
SirTimothy wrote: Anyways, I wanted to share a lovely snippet I wrote a little while ago.
How long is a "little while ago"?
|
|
|
|
|
mmm... last week? maybe the week before?
|
|
|
|
|
it sure has a modern je-ne-sais-quoi.
|
|
|
|
|
Are you by any chance a teacher by profession?
"When did ignorance become a point of view" - Dilbert
|
|
|
|
|
Awesome. Not obfuscated at all if you de-obfuscate it in your mind. I particularly liked your all-the-loop-inside-the-if's-conditional-expression concept.
|
|
|
|
|
Aside from the preprocessor directives and macros, the formatting of that code reminds me of one of the output from one of my C compilers (which compiles code to an intermediate form, optimizes it, and then shows the equivalent C format).
|
|
|
|
|
I personally liked the use of function pointers for a simple method call
The shout of progress is not "Eureka!" it's "Strange... that's not what i expected". - peterchen
|
|
|
|
|
That, of course, is so that I can change the function name, and only need to change one place where it's used. Gotta think about maintainability and future modifications!
|
|
|
|
|
... maintainability and future modifications ... hahaha very funny! Can you tell us why you wrote this code? Are you a teacher showing "bad practice"? If one of my programmers would come up with a piece of code like this ->
|
|
|
|
|
Nah, not a teacher. Actually, just graduated from university. Why'd I write it? Bored, felt like taking some reasonably clean code and totally butchering it, thought I'd see how ugly I could make it Of course, it could be much worse, but whatever, it was fun!
|
|
|
|
|
|
Wow! For loops are neat! I rewrote my code, got rid of the gotos, used for loops, and put in some comments like in the article you linked to. I think it's much improved now. I'm especially proud of my reduction of the number of loops. The main sorting part used to involve two nested loops (one inside the other), but I was able to reduce it to a single loop!
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#define ARRAY_SIZE 20
#define PNT(s, l, a) fprintf(std##s, l, a)
#define PNT2LINES(s, l1, l2, e) PNT(s, #l1#e#l2#e, 0)
void print_array(int *array) {
int x = ARRAY_SIZE;
char* fmts[] = { "%d, ", "%d\n" };
for (--array; PNT(out, ((x == 1) & 1)[fmts], *(array = ++array)), --x > 0;);
for (;;) break;
}
main() {
int iarray[ARRAY_SIZE];
int x, y;
int ofs = iarray - &ofs;
void (*prnt_func)(int*) = &print_array;
"Here's how I would have had to annotate code before. It's kind of a pain.";
srand((unsigned int)time(NULL));
x ^= x;
for(;((y = rand(), x < ARRAY_SIZE) && ((((x
= x + 1) - 1)[iarray] = (y - (y / 100) * 100)) || 1)););
PNT2LINES(out, Before sort, ---------------, \n);
for((*prnt_func)(&ofs+ofs),y^=y,x&=~x;(y+1>=ARRAY_SIZE&&(x&&!(y=x&=~x)))||y+1<ARRAY_SIZE;(++y,iarray[y]<(y-1)
[iarray])&&(y[iarray]^=iarray[y-1]^=iarray[y]^=*(iarray+y-1),x|=y));
PNT2LINES(out, After sort, ---------------, \n);
(*prnt_func)(&ofs + ofs);
}
|
|
|
|
|
SirTimothy wrote:
for((*prnt_func)(&ofs+ofs),y^=y,x&=~x;(y+1>=ARRAY_SIZE&&(x&&!(y=x&=~x)))||y+1<ARRAY_SIZE;(++y,iarray[y]<(y-1)
[iarray])&&(y[iarray]^=iarray[y-1]^=iarray[y]^=*(iarray+y-1),x|=y));
I checked it and it gives correct results. I't amazing. Especially, I don't get why
y[iarray]
does not cause SEGFAULT or something. Where the O(n^2) complexity is hidden?
BTW. I had to implement all sorting algorithms as one of projets on my university. Bubble Sort was among them, but I did not care about performance so much.
void Bubble::Sort(Table &table, bool descending)
{
bool swapped;
int size = table.size();
int bound = size - 1;
int lastSwap = 0;
do {
swapped = false;
for (int i = 0; i < bound; i++)
{
TableElement t1 = table[i], t2 = table[i + 1];
if (descending ? t1 < t2 : t1 > t2) {
swap(table[i], table[i+1]);
swapped = true;
lastSwap = i;
}
}
bound = lastSwap;
} while (swapped);
}
Greetings - Jacek
|
|
|
|
|
It is kinda amazing, isn't it? The y[iarray] thing, I've seen in a few different websites, basically the compiler just expands it to *(y + iarray) which is the same as iarray[y] and it carries on its merry way. The O(n^2) complexity is hidden in the single loop, I reset the values of x and y in the conditional (the y=x&=~x bit) when y gets past the array length and x is non-zero. Pretty near impossible to prove n^2 runtime, or to prove correctness, or even to prove that it terminates, but it's fun and it works. I thought about writing some more sorts like this, but haven't gotten to it...
|
|
|
|
|
SirTimothy wrote: the compiler just expands it to *(y + iarray) which is the same as iarray[y]
It relies on a C-specific feature, where size of int is the same as size of an address, doesn't it? In C# int is always a 32-bit integer...
I suppose proving n^2 runtime isn't hard. Each obfuscation can be transformated to a more readable form, which is fully equivalent. Step by step, one could get something similar to my code posted above. I suppose. Sometimes when I have a trouble with theory I generate a chart and write "The chart says, that the algorithm is quadratic, isn't it?". Unfortunately not every teacher was satisfied with such report...
Greetings - Jacek
|
|
|
|
|
I think you've got way too much time on your hands
There is only one satisfying way to boot a computer.
|
|
|
|
|
Recently found this in one of our stored procs. I think they really wanted to make sure the values are not null.
SELECT
IsNull(CASE WHEN Sum(IsNull(I.Value1,0)) IS NULL THEN 0 ELSE Sum(IsNull(I.Value1,0)) END, 0) - (Sum(IsNull(I.Value1,0)) + Sum(IsNull(I.Value2, 0)) - Sum(IsNull(I.Value3, 0))))) * 100 / ((100 * @Vatrate) + 100) AS Net
FROM I
I have renamed the table and field names.
And don't even get me started on the problems with the vatrate.
|
|
|
|
|