2 Challenges for the C Programmer in U...

C

Chinmay S

S

spinoza1111

If...then...else... A simple challenge.http://2600hertz.wordpress.com/2010/03/18/if-then-else/

<a href="http://2600hertz.wordpress.com/2010/03/18/if-then-
else/">http://2600hertz.wordpress.com/2010/03/18/if-then-else/</a>

Here's the Mystery Spiral?? Can U code it in C??...http://2600hertz.wordpress.com/2010/03/20/the-mystery-spiral/

<a href="http://2600hertz.wordpress.com/2010/03/20/the-mystery-
spiral/">http://2600hertz.wordpress.com/2010/03/20/the-mystery-spiral/
</a>
Click to expand...

Here is pseudo code.

Traverse(A[N,N], I):

/* Traverse the mystery spiral in an N*N square array
using I to populate cells: I is initially 1 */

If N > 1
{
Visit each column from A[0,0] up to A[0,N-1] decrementing I
(after depositing its value in A)
Visit each row from A[1,N-1] up to A[N-1, N-1] decrementing I
(after depositing its value in A)
Visit each column from A[N-1, N-2] back to A[N-1, 0] decrementing
I
(after depositing its value in A)
Visit each row from A[N-2] down to A[1] decrementing I
(after depositing its value in A)
If N > 2
Traverse the N-1*N-1 square array that starts at A[2,2]
and contains N-1 rows and N-1 columns
}
else set A[0,0] to I

Translating this to C is not completely trivial, and the above may be
incorrect. The basic idea, however, will work, I believe: solve the
problem recursively on smaller and smaller squares. Each square will
be the "tile" bordered by the outer row and column of the previous
square. When you get down to a two by two square this "tile" is zero
in size so you're done. The else clause is executed when you have an
odd I value, I think.

Let me know if I've made any errors.
 
B

BruceS

I haven't looked at any answers yet, but did you forget the
parentheses in the if? If so, it is simple:

#include <stdio.h>

#define else

int main()
{
if ("condition")
printf ("Hello-");
else
printf("World!!");

}
Click to expand...

Like a lot of puzzles, this one didn't make the rules as clear as it
should have, but the clear intent was to replace only the condition,
not other parts of the statement. The solution is quite simple, of
course. I don't claim to be great at stating puzzles either, but I
would have said it more like:

-----
In the following code, what should be put after "if" to make the code
produce the output "Hello-World!!"?

if
printf ("Hello-");
else
printf("World!!");
-----

This would avoid the confusion about "condition" being part of the
code, rather than being what needs to be replaced. I've seen a lot of
puzzles with similarly misleading or poorly stated conditions. I'm
fairly confident that the intent of the puzzle was as I represent, but
maybe not. Chinmay S may wish to clarify.
 
W

Willem

BruceS wrote:
) -----
) In the following code, what should be put after "if" to make the code
) produce the output "Hello-World!!"?
)
) if
) printf ("Hello-");
) else
) printf("World!!");
) -----

Sounds like a trick question.

For example, you could put '(printf('Hello-World!!'), exit(0))' in there.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
 
A

Andrew Poelstra

BruceS wrote:
) -----
) In the following code, what should be put after "if" to make the code
) produce the output "Hello-World!!"?
)
) if
) printf ("Hello-");
) else
) printf("World!!");
) -----

Sounds like a trick question.

For example, you could put '(printf('Hello-World!!'), exit(0))' in there.
Click to expand...

I was going to add a single :)

if(printf("Hello-"));
else printf ("World");

But this feels like cheating because I had to add a )
after the first printf.
 
W

Willem

BruceS wrote:
)> On Sun, 21 Mar 2010 23:29:40 -0700 (PDT)
)>
)>
)> > Here's the Mystery Spiral?? Can U code it in C??...
)> >http://2600hertz.wordpress.com/2010/03/20/the-mystery-spiral/
)>
)> I remember this had as exercise in high school back in 1986'
)
) Do you recall it well enough to post your solution?

I recall a similar question, where you only had to print a 3x3 sub square
from the spiral, and it had to be smaller than O(N) in memory.

Furthermore, the exercise should probably also have O(N) memory, or smaller.

As it is, it is a trivial matter of allocating an N*N array and simply
walking around it, counting down from N*N-1 to 0:

int size, cnt, pos, next, step, x, y, *grid;

size = N*N;
pos = 0;
step = +1;
cnt = size;
grid = calloc(size, sizeof(*grid));

while (cnt--) {
grid[pos] = cnt;
next = pos + step;
if ((next == N && step == +1) || next >= size || grid[next] > 0) {
if (step == +1) { step = +N }
else if (step == +N) { step = -1 }
else if (step == -1) { step = -N }
else if (step == -N) { step = +1 }
next = pos + step;
}
pos = next;
}

for (y = 0; y < N; y++) {
for (x = 0; x < N; x++) {
printf("%4d", grid[N*y+x]);
}
printf("\n");
}

free(grid);


Which cost me about ten minutes to type in.

I suppose it would cost me another ten to run it and find the bugs
which are doubtlessly in there.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
 
B

BruceS

I was going to add a single :)

if(printf("Hello-"));
else printf ("World");

But this feels like cheating because I had to add a )
after the first printf.
Click to expand...

I think what the OP was going for was simply making (!
printf("Hello-")) the condition. The printf() will return a non-zero
value, so the test will drop to the else clause, thus printing the
"World!!" part. I agree, these things are trick questions, as they
encourage "cute" coding that wouldn't be of much value in the real
world. Then again, I recall having to do things like the eight queens
problem in college, so neither triviality nor pointlessness is out of
the question in academia.
 
B

Ben Bacarisse

Willem said:
BruceS wrote:
)> On Sun, 21 Mar 2010 23:29:40 -0700 (PDT)
)>
)>
)> > Here's the Mystery Spiral?? Can U code it in C??...
)> >http://2600hertz.wordpress.com/2010/03/20/the-mystery-spiral/
)>
)> I remember this had as exercise in high school back in 1986'
)
) Do you recall it well enough to post your solution?

I recall a similar question, where you only had to print a 3x3 sub square
from the spiral, and it had to be smaller than O(N) in memory.

Furthermore, the exercise should probably also have O(N) memory, or smaller.
Click to expand...

Yes, it's not much of a problem unless the space is limited. The
trouble (for me) is that I can't get excited about it. A no-array
solution seems eminently feasible, but I think it's unlikely to be
elegant -- lots of fussy arithmetic. I hope I'm wrong and there is an
ingenious, pleasing, solution.

<snip>
 
S

Samel - Luchino

Yes, it's not much of a problem unless the space is limited.  The
trouble (for me) is that I can't get excited about it.  A no-array
solution seems eminently feasible, but I think it's unlikely to be
elegant -- lots of fussy arithmetic.  I hope I'm wrong and there is an
ingenious, pleasing, solution.

<snip>
Click to expand...

The funny way 8)

#include <stdio.h>
#include <stdlib.h>
int main(int argc,char** argv)
{
if(argc<2)
exit(-1);
int N=atoi(argv[1]);
int* M=malloc(sizeof(int)*N);
int i=0;
int n=0;
int k=0;
printf("Filling a board of %dx%d cell with a spiral ...",N,N);
while(N>0)
{
//move your hands to the right!
while(k++<N)
{
M[n++]=i++;
}
k=0;
N--;
//put your hands on the floor!
while(k++<N)
{
M[n+atoi(argv[1])-1]=i++;
n+=atoi(argv[1]);
}
k=0;
//move your hands to the left!
while(k++<N)
{
M[--n-1]=i++;
}
k=0;
N--;
//move your hands to the sky!
while(k++<N)
{
M[n-atoi(argv[1])-1]=i++;
n-=atoi(argv[1]);
}
k=0;
}
printf(" done\n");
N=atoi(argv[1]);
for(n=0;n<N*N;n++)
{
printf("|%.4d",M[n]);
if(n%N==N-1)
printf("|\n");
}
}
 
B

Ben Bacarisse

Samel - Luchino said:
The funny way 8)

#include <stdio.h>
#include <stdlib.h>
int main(int argc,char** argv)
{
if(argc<2)
exit(-1);
int N=atoi(argv[1]);
int* M=malloc(sizeof(int)*N);
Click to expand...

I think you meant N * N. I.e. (using c.l.c approved method):

int *M = malloc(N * N * sizeof *M);
int i=0;
int n=0;
int k=0;
printf("Filling a board of %dx%d cell with a spiral ...",N,N);
while(N>0)
{
//move your hands to the right!
while(k++<N)
{
M[n++]=i++;
}
k=0;
N--;
//put your hands on the floor!
while(k++<N)
{
M[n+atoi(argv[1])-1]=i++;
n+=atoi(argv[1]);
Click to expand...

I presume the use of atoi(argv[1]) is deliberate?
}
Click to expand...
N=atoi(argv[1]);
for(n=0;n<N*N;n++)
{
printf("|%.4d",M[n]);
Click to expand...

If you print N * N - M[n] - 1 you get the same numbering as the
original puzzle.
 
S

spinoza1111

BruceS wrote:

)> On Sun, 21 Mar 2010 23:29:40 -0700 (PDT)
)>
)>
)> > Here's the Mystery Spiral?? Can U code it in C??...
)> >http://2600hertz.wordpress.com/2010/03/20/the-mystery-spiral/
)>
)> I remember this had as exercise in high school back in 1986'
)
) Do you recall it well enough to post your solution?

I recall a similar question, where you only had to print a 3x3 sub square
from the spiral, and it had to be smaller than O(N) in memory.

Furthermore, the exercise should probably also have O(N) memory, or smaller.

As it is, it is a trivial matter of allocating an N*N array and simply
walking around it, counting down from N*N-1 to 0:

 int size, cnt, pos, next, step, x, y, *grid;

 size = N*N;
 pos = 0;
 step = +1;
 cnt = size;
 grid = calloc(size, sizeof(*grid));

 while (cnt--) {
   grid[pos] = cnt;
   next = pos + step;
   if ((next == N && step == +1) || next >= size || grid[next] > 0) {
     if (step == +1) { step = +N }
     else if (step == +N) { step = -1 }
     else if (step == -1) { step = -N }
     else if (step == -N) { step = +1 }
     next = pos + step;
   }
   pos = next;
 }

 for (y = 0; y < N; y++) {
   for (x = 0; x < N; x++) {
     printf("%4d", grid[N*y+x]);
   }
   printf("\n");
 }

 free(grid);

Which cost me about ten minutes to type in.

I suppose it would cost me another ten to run it and find the bugs
which are doubtlessly in there.

SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
Click to expand...

Willem is always full of surprises. So we don't need recursion.
 
M

Moi

Like a lot of puzzles, this one didn't make the rules as clear as it
should have, but the clear intent was to replace only the condition, not
other parts of the statement. The solution is quite simple, of course.
I don't claim to be great at stating puzzles either, but I would have
said it more like:

-----
In the following code, what should be put after "if" to make the code
produce the output "Hello-World!!"?

if
printf ("Hello-");
else
printf("World!!");
-----

This would avoid the confusion about "condition" being part of the code,
rather than being what needs to be replaced. I've seen a lot of puzzles
with similarly misleading or poorly stated conditions. I'm fairly
confident that the intent of the puzzle was as I represent, but maybe
not. Chinmay S may wish to clarify.
Click to expand...


if (fork() || sleep(1) )

/* not standard :) */

AvK
 
W

Willem

Ben Bacarisse wrote:
) Yes, it's not much of a problem unless the space is limited. The
) trouble (for me) is that I can't get excited about it. A no-array
) solution seems eminently feasible, but I think it's unlikely to be
) elegant -- lots of fussy arithmetic. I hope I'm wrong and there is an
) ingenious, pleasing, solution.

Perhaps a semi-elegant solution could be made if you find a neat function
that maps a grid position + size to the number that should go there in the
spiral. An O(1) memory and speed function, mind.

int spiral(int x, int y, int size)
{
/* ... */
}

I think a reasonably elegant solution exists.

The original program would then become simply:

for (y = 0; y < N; y++) {
for (x = 0; x < N; x++) {
printf("%04d", spiral(x, y, N));
}
printf("\n");
}

One approach would be to find the quadrant, then find the distance
from the edge, and then use some clever arithmetics to find the number.

Now that's a challenge!
(I think I solved something similar some time ago, though).


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
 
W

Willem

Willem wrote:
) Perhaps a semi-elegant solution could be made if you find a neat function
) that maps a grid position + size to the number that should go there in the
) spiral. An O(1) memory and speed function, mind.
)
) int spiral(int x, int y, int size)
) {
) /* ... */
) }
)
) I think a reasonably elegant solution exists.
)
) The original program would then become simply:
)
) for (y = 0; y < N; y++) {
) for (x = 0; x < N; x++) {
) printf("%04d", spiral(x, y, N));
) }
) printf("\n");
) }
)
) One approach would be to find the quadrant, then find the distance
) from the edge, and then use some clever arithmetics to find the number.
)
) Now that's a challenge!
) (I think I solved something similar some time ago, though).

Yup, quite easy, and even semi-elegant:

int spiral(int x, int y, int N)
{
int d, o = 2;
/* Map down to up, left to right */
if (x < y) {
x = N-x-1;
y = N-y-1;
o -= 2;
}
/* Map right to up */
if (x+y >= N) {
int tx = x;
x = y;
y = N-tx-1;
o -= 1;
}
/* Length of the line we're on */
d = (N-(2*y)-1);

return d*o + d*d - x + y;
}

This is based on the observation that the lower right diagonal
is a succession of square numbers. The rest comes naturally.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
 
B

Ben Bacarisse

Willem said:
Ben Bacarisse wrote:
) Yes, it's not much of a problem unless the space is limited. The
) trouble (for me) is that I can't get excited about it. A no-array
) solution seems eminently feasible, but I think it's unlikely to be
) elegant -- lots of fussy arithmetic. I hope I'm wrong and there is an
) ingenious, pleasing, solution.

Perhaps a semi-elegant solution could be made if you find a neat function
that maps a grid position + size to the number that should go there in the
spiral. An O(1) memory and speed function, mind.

int spiral(int x, int y, int size)
{
/* ... */
}

I think a reasonably elegant solution exists.

The original program would then become simply:

for (y = 0; y < N; y++) {
for (x = 0; x < N; x++) {
printf("%04d", spiral(x, y, N));
}
printf("\n");
}

One approach would be to find the quadrant, then find the distance
from the edge, and then use some clever arithmetics to find the
number.
Click to expand...

That's what I was thinking of. Wrapping the arithmetic in a function
does not, of itself, make the solution elegant -- it tidies up the
mess. Are you saying that you know/suspect there is a neat and elegant
expression to go in the spiral function? If so, that might tempt me to
think on it.
Now that's a challenge!
(I think I solved something similar some time ago, though).
Click to expand...

I used to set similar things as exercises. There are lots of problems
for which a good pattern is the one you've outlined (for example,
drawing an ASCII-art graph of f(x)).
 
B

Ben Bacarisse

Willem said:
Willem wrote:
) Perhaps a semi-elegant solution could be made if you find a neat function
) that maps a grid position + size to the number that should go there in the
) spiral. An O(1) memory and speed function, mind.
)
) int spiral(int x, int y, int size)
) {
) /* ... */
) }
)
) I think a reasonably elegant solution exists.
)
) The original program would then become simply:
)
) for (y = 0; y < N; y++) {
) for (x = 0; x < N; x++) {
) printf("%04d", spiral(x, y, N));
) }
) printf("\n");
) }
)
) One approach would be to find the quadrant, then find the distance
) from the edge, and then use some clever arithmetics to find the number.
)
) Now that's a challenge!
) (I think I solved something similar some time ago, though).

Yup, quite easy, and even semi-elegant:

int spiral(int x, int y, int N)
{
int d, o = 2;
/* Map down to up, left to right */
if (x < y) {
x = N-x-1;
y = N-y-1;
o -= 2;
}
/* Map right to up */
if (x+y >= N) {
int tx = x;
x = y;
y = N-tx-1;
o -= 1;
}
/* Length of the line we're on */
d = (N-(2*y)-1);

return d*o + d*d - x + y;
}

This is based on the observation that the lower right diagonal
is a succession of square numbers. The rest comes naturally.
Click to expand...

Well, I got interested after all. The best I could come up with is
this:

int isquare(int x) { return x * x; }
int imax(int a, int b) { return a > b ? a : b; }
int imin(int a, int b) { return a < b ? a : b; }

int spiral(int x, int y, int N)
{
/* The expressions are simpler in terms of x+1. */
int X = x + 1;
if (N - X < y) {
int square = isquare(N - 2*imax(X, y));
if (X <= y)
return square + 3*y + X - 2*N;
else return square - 3*X - y + 2*N;
}
else return isquare(N - 2*imin(X, y)) - X + y;
}

This was done by inspection and algebra. I suspect the two
expressions returned in the inner 'if' can be written as one with some
suitable substitution of variables and more uses of imax and/or imin
but my interest started to flag.

Not to detract from your solution, but both of these fit my concern
that there'd be "fussy arithmetic". Yours probably reveals more about
the problem, but I don't think there is much structure to reveal.
 
W

Willem

Ben Bacarisse wrote:
)> Yup, quite easy, and even semi-elegant:
)>
)> int spiral(int x, int y, int N)
)> <snip>
)>
)> This is based on the observation that the lower right diagonal
)> is a succession of square numbers. The rest comes naturally.
)
) Well, I got interested after all. The best I could come up with is
) this:
)
) int spiral(int x, int y, int N)
) <snip>
)
) This was done by inspection and algebra. I suspect the two
) expressions returned in the inner 'if' can be written as one with some
) suitable substitution of variables and more uses of imax and/or imin
) but my interest started to flag.

Yeah, same on my end.

) Not to detract from your solution, but both of these fit my concern
) that there'd be "fussy arithmetic". Yours probably reveals more about
) the problem, but I don't think there is much structure to reveal.

Well, I think mine is reasonably straightforward:
1 - Translate the x/y coordinates to the upper quadrant
2 - Calculate the length of the 'leg' from the y coordinate
3 - Note that the start of the third of each set of four legs
is equal to the square of the length of those legs.
4 - The result is the length of the leg, squared, plus the position on
that leg, plus or minus some leg lengths depending on which quadrant
we originally were on.


Anyway, I think the original problem could also be quite simply solved
by using a function that determines the difference between a given cell
and the cell to the left of it:

- For the upper quadrant, that's +1
- For the lower quadrant, that's -1
- For the left quadrant, that's -(4*N-3-8*x)
- For the right quadrant, that's -(4*N-1-8*x)

The factors for the left and right quadrants needed a bit of algebra,
other than that it's rather straightforward.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

The RUN CHASE: A Challenge for the C Programmer in U... 1
Sort by number of characters 1
[PAID][REMOTE] Hiring programmer/dev for indie game 2
Problem with codewars. 5
Problems with using event handlers for button and textarea input 1
Php combine identical lines in text file 4
New to python - parse data into Google Charts 2
Help with code 0

Members online

No members online now.
Total: 29 (members: 0, guests: 29)
Robots: 497

Forum statistics

Threads
473,769
Messages
2,569,579
Members
45,053
Latest member
BrodieSola

Latest Threads

Top