Coding Challenges

[Hooman]

I just thought I'd post a few things for people to think about. Most of these will be C++ related, but not all.


1) Output a program that outputs all of it's source code. The compiled program must output the source code with no input files. This source code must then be capable of being compiled back into the program you just ran.

Basically, if you send someone the exe, they can run it, get the source, compile it, and send the exe back on to someone else who can then do the same thing.

As an added rule to make sure people do this as is intended, you are also not allowed to tell the compiler to insert your source code into the the exe. (Kinda like an incbin "filename" for asm, which just dumps the contents of that file into the exe.)


2) In C++, the result of:
i = ++i + 1;
is ...?


3) In C++, the result of writing the following code:
cout << "Hello World"[2] << endl;
will be ...?


4) Getting the compiler to do work for you
Let's say you have some constant c, and you want to output the value of sin( c ). How can you get the compiler to output this value without calling runtime functions, and without having to precompute this value yourself. (In other words, don't get out a calculator, figure out the answer, and just cout the answer). The compiler must do the calculation for you. (Yes, the compiler, not your compiled program). You may make use of whatever features the compiler supports if needed. The ultimate goal is to have the compiler output code along the lines of:

Code: [Select]

MOV x, d

where d = sin( c ), given input code along the lines of:

Code: [Select]

x = sin( c );

More to come later....

[HaXtOr]

asm questions would be more fun

[Hooman]

5) In intel assembly, how would you get the instruction pointer into the EAX register?
 

[Eddy-B]

5) In intel assembly, how would you get the instruction pointer into the EAX register?

come'on coders .. don't let ME solve everything!!

it got something to do with a CALL and a POP .. thats all i'm saying .. now get going and solve this!!

[Hooman]

Looks like I have a few challenges to repost.

6) How do you compute the absolute value without using a jump/branch? For assembly, assume the input is in EAX, and the output is also in EAX. No jumps (branches/calls, etc.) are allowed.

7) Reset the least significant 1 bit in a 32 bit value to 0. If the value is 0 (all 32 bits are 0) then the output should be 0. The must be done brance free. (Again, no jumps/branches/calls). If you answer this in a high level language, it must be done in a way that's guaranteed not to compile to jumps/branches/calls.
Ex. 1: (for 8 bits)
Input: 01001101
Output: 01001100

Ex. 2: (for 8 bits)
Input: 01011000
Output: 01010000

Edit: This last challenge is meant to be read as: The least significant bit that is set to a 1 needs to be reset to 0. As in, the first 1 bit from the right. Not the LSB.
 

[Eddy-B]

7) Reset the least significant 1 bit in a 32 bit value to 0. If the value is 0 (all 32 bits are 0) then the output should be 0. The must be done brance free. (Again, no jumps/branches/calls). If you answer this in a high level language, it must be done in a way that's guaranteed not to compile to jumps/branches/calls.
Ex. 1: (for 8 bits)
Input: 01001101
Output: 01001100

Ex. 2: (for 8 bits)
Input: 01011000
Output: 01010000

Edit: This last challenge is meant to be read as: The least significant bit that is set to a 1 needs to be reset to 0. As in, the first 1 bit from the right. Not the LSB.

I'm not sure this is the most efficient code, but then again, you dont want me to use jumps or branches, so how efficient can you get ?
input and output are memory addresses.

Code: [Select]

; initialization
MOV	CX,0
MOV	EAX,input

; bit processing - repeat these lines 32 times  
SHR	EAX,1
RCL	BL,1
MOV	CH,BL
AND	BL,CL
SHR	BL,1
RCR	output,1
OR	CL,CH

A little explaination:
SHR - shift out a single bit -> will be stored in Carry Flag
RCL - put the Carry Flag into BL
MOV - store this bit value into CH, we'll need it later on
AND - depends on the bit from the previous process; if it was 1, nothing changes, if it was 0, BL is set to 0
SHR - again, shift out the bit, store it in Carry
RCR - and insert it into the output field
OR - if bit from the previous process was already 1 nothing happens; otherwise it stores the bit from this last operation into CL
 

[Hooman]

Yes, I do believe that will work. Nice answer.

I'm not sure this is the most efficient code, but then again, you dont want me to use jumps or branches, so how efficient can you get ?

It's not.
You can do this in one line of C++ or 2 lines of assembly (maybe 3 depending on the instructions you choose to use, or if you have a different architecture). I doubt it can be done better than that though.

So, a question now would be, how is this done better?  
 

[Eddy-B]

So, a question now would be, how is this done better?

and i leave that up to you.
The question was to DO it, and not to do it efficiently, or fast, or small code or whatever.
You want small, efficient code, use branches!


as for your other coding thing:

Code: [Select]

MOV	EAX,input
MOV	ECX,0

PUSH	EAX
RCL	EAX,1
RCL	ECX,1
POP	EAX
PUSH	ECX
NEG	ECX
XOR	EAX,ECX
POP	ECX
ADD	EAX,ECX

MOV	output,EAX

[Eddy-B]

Code: [Select]

char *s[]={
"#include <stdio.h>",
"#include <string.h>",
"char *translate(char *s)",
"{",
" int x=0;",
" while (s[x])",
" {",
"  switch (s[x])",
"  {",
"   case 38: s[x]=34; break;",
"   case 47: s[x]=92; break;",
"   case 36: s[x]=37; break;",
"  }",
"  ++x;",
" }",
" return s;",
"}",
"void main()",
"{",
" int i=-1,j=-1;",
" char ss[80];",
" printf(&char *s[]={/n&);",
" while (s[++i]!=0) printf(&/&$s/&,/n&,s[i]);",
" printf(&0/n};/n&);",
" while (++j<i) { strcpy(ss,s[j]); printf(&$s/n&,translate(ss)); }",
"}",
0
};
#include <stdio.h>
#include <string.h>
char *translate(char *s)
{
 int x=0;
 while (s[x])
 {
  switch (s[x])
  {
   case 38: s[x]=34; break;
   case 47: s[x]=92; break;
   case 36: s[x]=37; break;
  }
  ++x;
 }
 return s;
}
void main()
{
 int i=-1,j=-1;
 char ss[80];
 printf("char *s[]={\n");
 while (s[++i]!=0) printf("\"%s\",\n",s[i]);
 printf("0\n};\n");
 while (++j<i) { strcpy(ss,s[j]); printf("%s\n",translate(ss)); }
}

Reposted this, cause it was removed when the server went down. Also edited it to accomodate Hooman's complaint about the Microsoft Compiler crashing on my code

[Eddy-B]

5) In intel assembly, how would you get the instruction pointer into the EAX register?

Doesn't anybody know the answer to this simple one ?

CALL this subroutine to get EIP:

POP EAX
PUSH EAX
RET

[Hooman]

Well, looks like you've answered 1, 5, 6, 7.

QUOTE 
So, a question now would be, how is this done better? 

and i leave that up to you.
The question was to DO it, and not to do it efficiently, or fast, or small code or whatever.
You want small, efficient code, use branches!

About the question, yes true, but....
The point of branch free code is sorta to be efficient. The idea is that branches are terrible for pipelined processors (which all modern CPUs are). So if you can code something equivalently, but avoid branches, you can often get a gain in efficiency.



So, since those problems are solved, I'd like to up the ante a little.  :ph34r:

Solve challenge 1, but this time without overwriting any data that you've defined or allocated space for (you being the important part here). Relating this to the solution of problem 1, the string array that is modified and reprinted will be in violation of the rules for challenge #8. Also, the loop index which is defined and modified by that solution will also be in violation of the rules for challenge #8. Now, that's not to say your program can't make use of variables. You just can't *modify* any that YOU have defined (this includes both data you've defined, and the data pointed to by pointers you've defined). Calling a library function like printf will use some of it's own local variables, but this should be of no concern and will not be considered against the rules. You must not call a library function that writes to a buffer you've defined. Ex:

Code: [Select]

char buff[64];
snprintf(buff, 64, "Writing data to a buffer you've defined!"); // Against the rules!

printf("Hello World!"); // Nothing wrong with this
char string1 = "This is a string";
printf("%s", string1); // Nothing wrong with this either

As an added difficulty (maybe?), I'd like to add a rule against using using library functions that allocate a buffer and fill it before returning the pointer to you. That is, something along the lines of:

Code: [Select]

char *string2 = CopyString(string1); // Against the rules
string2[1] = "\n"; // Clearly against the above rules about writing to data through a pointer you've defined.

char *string3 = CopyAndTranslate(string1); // Also against the rules

Basically, all this is to say any memory being written to at run time MUST be done by standard C++ library functions, and you must gain no direct access to such memory. (All such memory has it's use confined to the standard C++ library function that uses it, and no pointers to such memory are returned).

Note: This challenge is likely much harder than the original, and will definately require some rethinking for a solution.



9) Solve challenge #6 with at most 5 assembly instructions. (You *should* need less than this).

10) Solve challegne #7 with at most 5 assembly instructions. (You *should* need less than this).



*Following is a repost of a challenge that was lost when the forums went down*
(Let's see if anyone remembers the answer
11) In C++, the result of writing the following code:
cout << 2["Hello World"] << endl;
will be ...?
 

[Eddy-B]

ok - then let someone else solve these.
simple: just change the one i've written up there^ adding the new rules hooman created
9) takes a little bit of work on the code
10) i'd like to see YOU do that hooman, with just 5 opcodes, you cannot process 32 bits. therefor i think it be impossible without using jumps.
11) well .. i DO remember this C 'quirk'  It looks outright stupid the way you put it, but i guess ur right about it .. lol


oh, branches are inefficient ?  i need to find the pentium opcode list that includes processorcycles, to believe that.  I never got into that stuff since after 1990, but i do remember from earlier assembly coding with the 6502 a branch took 2 or 3 cycles (depending in the jump was taken or not), as compared to a Load Accu Immediate, taking also 2 cycles, or a Load Accu from memory (16bit) taking 4 cycles. This just as an example.

[Hooman]

Pipelined processors don't handle branches well. It wasn't the same back in the day of dinosaurs!    J/k. But serious, once the pentium was introduced, that's when this becomes valid. You'll also notice that the pentium manuals was about where they stopped including the number of clock cycles each instruction took. You can't really include these things when they vary greatly based on pipeline stalls/flushes. The idea is, the next few instructions would have already been fetched from memory by the time the processor realised the instruction was a jump, and where it's supposed to jump to. (Lag is especially bad if it needs to calculate the address using offset constants, etc.) Thus, those extra instruction that have been read in must be cleared, and so you essential get bubbles of NOPs flowing through the pipeline.

As for working on 32 bits at a time....
ADD EAX, EAX
AND EAX, EDX
NOT EAX
etc.
All those certainly work on 32 bits at a time. You just have to be a little more creative.  

And don't worry, I'm not posting impossible challenges. I haven't posted anything I don't already know the answer to.


As for #8. I think it needs a fair bit of rethinking. Probably not so easy to mod the code you already have. But hey, maybe you know of some ingenious way I haven't thought of.


So, do you really want me to answer #10? Or should I leave it an open question for now?
 

[Eddy-B]

As for #8. I think it needs a fair bit of rethinking. Probably not so easy to mod the code you already have. But hey, maybe you know of some ingenious way I haven't thought of.

as i said: modify it just slightly.. i should've done this earlier. I was thinking about it, but i thought it was too much work, for just a simple coding test, that you designed. But since you put so much weight on it - i did it anyway: change all text into bytes  It saves the 'translate' function altogether, and sticks to your rules. Plus it circumvents the MS compiler "bug" as i call it

Code: [Select]

char *s="\x23\x69\x6E\x63\x6C\x75\x64\x65\x20\x3C\x73\x74\x64\x69\x6F\x2E\x68\x3E\x0A\x76\x6F\x69\x64\x20\x6D\x61\x69\x6E\x28\x29\x0A\x7B\x0A\x20\x69\x6E\x74\x20\x69\x3D\x2D\x31\x3B\x0A\x20\x70\x72\x69\x6E\x74\x66\x28\x22\x63\x68\x61\x72\x20\x2A\x73\x3D\x5C\x22\x22\x29\x3B\x0A\x20\x77\x68\x69\x6C\x65\x20\x28\x73\x5B\x2B\x2B\x69\x5D\x21\x3D\x30\x29\x20\x70\x72\x69\x6E\x74\x66\x28\x22\x5C\x5C\x78\x25\x30\x32\x58\x22\x2C\x73\x5B\x69\x5D\x29\x3B\x0A\x20\x70\x72\x69\x6E\x74\x66\x28\x22\x5C\x22\x3B\x5C\x6E\x25\x73\x22\x2C\x73\x29\x3B\x0A\x7D";
#include <stdio.h>
void main()
{
 int i=-1;
 printf("char *s=\"");
 while (s[++i]!=0) printf("\\x%02X",s[i]);
 printf("\";\n%s",s);
}

oh, that first line char *s ... until just before the #include is ONE line, do not put linebreaks in it! Oh, and i wouldn't call it "ingenious" :lol:

So, do you really want me to answer #10? Or should I leave it an open question for now?

(...)
well, if you can do better: show me .. or let someone else do it. I'm going to continue with more important stuff - like my Renegades project, and my AI project.

[Eddy-B]

9) Solve challenge #6 with at most 5 assembly instructions. (You *should* need less than this).

Code: [Select]

int absolute(int input)
{
  _asm
  {
    MOV	EAX,input
    SHR	EAX,31
    SUB	input,EAX
    NEG	EAX
    XOR	input,EAX
  };
  return input;
}

[Hooman]

For challenge #8, you defined int i = -1, and used i++. So technically, it breaks the rules.  

Challenge #9 is solved. That was nice. Here is my solution in case you were wondering:

Code: [Select]

CDQ
SUB EAX, EDX
XOR EAX, EDX

Oh, and also, my solution for #5 was essentially:

Code: [Select]

CALL dummyLabel
dummyLabel:
POP EAX

It's also nice to note that since CALL instruction are relative (to the end of the instruction/start of the next instruction), the constant built into the CALL instruction is 0. So even if you wanted to avoid using a label, you could just force the offset part to be 0.


As for #10, you're probably gonna laugh at how simple it actually is. In C++, you can code the following:

Code: [Select]

i = i & (i-1);

Which of course if written in assembly might have been:

Code: [Select]

LEA EDX, [EAX - 1]
AND EAX, EDX

Or, if you object to the LEA (perhaps adapting code to a different architecture?)

Code: [Select]

MOV EDX, EAX
DEC EDX
AND EAX, EDX

I love that one.
 (thumbsup)
 

[RockNavator]

The simple ones dont seem to be getting any attention so Im gonna just try to get them outa the way...

2)i=++i+1; == i=i+2; where i is an  int

3)"Hello World" is a char[] so the subscript of 2 would designated the third element of the array... the letter l (el)

11)2["Hello World"]=="Hello World"[2] due to the way in which pointer multiplication works.  

[Hooman]

Ohh, fresh meat!  B)

Answer 3 is correct. Good job.

Answer 11 is correct. Again, good job. (Note: this one was answered before but the post was lost.)

Answer 2.... at best, maybe. At worst, nope. Try again.  

[Eddy-B]

Answer 11 is correct. Again, good job. (Note: this one was answered before but the post was lost.)

..and he remembered not 100%, it is addition, not multiplication

hooman: i was wondering WHY you wanted that weird thing with the LS-1-B. But it was just a way of telling us, "hey i found something neat, can anyone reproduce it?"  It was fun while it lasted!  (thumbsup)

[edit] oh, about answer 2) , rock is correct, and hooman: USE BRACKETS for crying outloud. It not only makes things more readable, it also prevents the compiler from doing things you don't expect:

it should read: i=(++i)+1;    and not  i=++(i+1) which is invalid, coz you can't increase an expression.

equals: i+=2;  or more to the ground:  i=i+2;
 

[Hooman]

So far no correct answer for #2 has been given.  :ph34r:

As for why...? Well, let's just say you're gonna hate me when you hear it. Challenge #2 is indeed a trick question. Can anyone see what's wrong with it?  

It isn't a question about bracketing. The question was posted as intended. There should be no brackets, and it doesn't matter how you break up whitespace (or remove it completely) it works the same.
 

[LupusShearhart]

The answer to number 2:

Assuming i is an integer initialized to 0:

i = 2.

Now let's see what happens when we put i into a loop of 6.

i would be 12.

Each time i = ++i + 1; passes, i is incremented by 2.

So saying i = ++i + 1; would be similar to saying i = i + 2.

[Hooman]

Wow hey. I wasn't expecting an answer from you. How's it going?

Unfortuneatly, I'd have to say that's not quite the right answer. (Although, it is what I expected most people to think, and is the logical thing to assume, and likely what your comiler will do). I remind people this one is a trick question.

So far, 3 people have given me that answer, so I feel I should hint at what is wrong. Think about the order in which the updates to the variable i are performed. (*cough* *cough* if you're not sure about this, it might be an idea to check into some C++ specs *cough* *cough*).
 

[LupusShearhart]

Actually, I plugged the code directly into MSVC++ and got those outputs, then the same outputs from a compiled Java program, and just traced the outputs per iteration. It all came to the same conclusion of it being i = i + 2. And yeah - I've not been around very much compliments of school and work.

PS: The only other logical way of thinking of how that could come out would be how  Fortran would run it:

i = i+i+1. Though that's not how C++ runs it.

So the iterations, where i starts at zero would be:

i = 0 + 0 + 1
i = 1 + 1 + 1
i = 3 + 3 + 1
i = 7 + 7 + 1
i = 15 + 15 + 1
i = 31 + 31 + 1
etc.
etc.


But if you run i = ++i + 1; in C++, it incriments by two per iteration of the loop. Try it. Put this in a main for a console app and put a line break (debug mark) on the output line of code to show the integer value.

Code: [Select]

int i=0;
int z=0;
for(z=0;z<6;z++)
{
i = ++i + 1;
}
printf ("The return is: %1d \n", i);
return 0;

Guaranteed, the output would be 12.

So the following:

Code: [Select]

#include "stdafx.h"

int main(int argc, char* argv[])
{
	int i=0;
	int z=0;
	int w=0;
	for(z=0;z<1000;z++)
	{
  i = ++i + 1;
	}
	printf ("The return is: %1d \n", i);
	i=0;
	for (w=0;w<1000;w++)
	{
  i= i + 2;
	}
	printf ("The return is: %1d \n", i);
	return 0;
}

returns the following:

Code: [Select]

The return is: 2000
The return is: 2000
Press any key to continue

This is a coding challenge, after all. Any free C compiler will produce the same result. Even code compiled in Java or under a linux machine will still produce the same result.
(Reason Edited: Adding code.)

[Hooman]

Well, I guess I should spill this one before people kill me.

This is a coding challenge, after all. Any free C compiler will produce the same result. Even code compiled in Java or under a linux machine will still produce the same result.

Not necessarily.

So the answer to #2 then....

2) In C++, the result of:
i = ++i + 1;
is ...?

Undefined!  

While looking at some article on the C++ specification, I noticed the following line:

i = ++i + 1;                    // the behavior is unspecified

Which of course begs some reasoning. I know.

4 Except  where noted, the order of evaluation of operands of individual
  operators and subexpressions of individual expressions, and the  order
  in  which side effects take place, is unspecified.  Between the previ-
  ous and next sequence point a scalar  object  shall  have  its  stored
  value  modified at most once by the evaluation of an expression.  Fur-
  thermore, the prior value shall be  accessed  only  to  determine  the
  value  to  be stored.  The requirements of this paragraph shall be met
  for each allowable ordering of the subexpressions of  a  full  expres-
  sion; otherwise the behavior is undefined.

Another example which more clearly illustrates the problem that was given is:

i = v[i++];                     // the behavior is unspecified

Does the i++ change the value of i before or after the assignment?

Similarly, does the ++i change the value of i before or after the assignment in i = ++i + 1; ? If it change it before, the value is overwritten by the assignment and the effect is i = i + 2. But it is apparently perfectly legal for the compiler to have the storage from ++i after the assignment, leading to code that works as i = i + 1 (the assignment result is discarded).


So yeah, I believe you in what you say about MSVC. I know. I've tried it myself. I got the same result you did.


I hope nobody wants to kill me over that one.  :unsure: I don't think any of ther others were trick questions like that.
 

[Eddy-B]

/me kills Hooman

I know i have found problems with the ++ operator LONG before you were even coding (i think). When using the object inspector of Borland's C-Builder, you can move your mouse over a variable.  When moving over this expressing (any expression using ++) the debugger access "++i", and so in inspecting the variable INCREASING its contents. When moving your mouse out, and over it again, you'd see and that the value got increased. An anooyance to say the least.

But to say the result of a line like i = ++i + 1 is undefined is rediculous.

Look at the order of things:
C reads expressions from left-to-right, honouring the precedence of the operators. * and / go before + and -.  Unary operators like *, ++ and -- go before even the binary operators, like + and -. If there's no rule  (if they are equally leveled operators), C will simply execute them from left-to-right.

The first thing C will do is the (++i). It reads in i and increases it, storing the value back into i. To be more specific: INC [DWORD] will be the result: just 1 instruction.
The next step will be to take the result of the previous step, and do the next step:  +1, again increasing the value of i.
The last step is the assignment =, and the final result will be stored back again into i.

Precedence works fine, even a sick line like  ++i++ increases i by 2, and if used as an array value, like you have:  v[++i++] it uses i after the first INC, and before the second INC!


And, Hooman, please: these are NOT "C challanges", these are interpretation issues. If ALL C compilers do the job the exact same way, but the specification by Kernighan and Ritchie might be written in such a way, it could opun a discussion about what they meant, it doesn't mean  that all compilers are wrong, or produce undefined results.