2 Challenges for the C Programmer in U...
Chinmay S
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>
Branimir Maksimovic
Chinmay S <2.6kil...@gmail.com> wrote:
>
> 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'
Greets
Sometimes online sometimes not
spinoza1111
> If...then...else... A simple challenge.http://2600hertz.wordpress.com/2010/03/18/if-then-else/
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!!");
}
>
> <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/
spinoza1111
>
> <a href="http://2600hertz.wordpress.com/2010/03/18/if-then-
> else/">http://2600hertz.wordpress.com/2010/03/18/if-then-else/</a>
>
>
> <a href="http://2600hertz.wordpress.com/2010/03/20/the-mystery-
> spiral/">http://2600hertz.wordpress.com/2010/03/20/the-mystery-spiral/
> </a>
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.
BruceS
> On Mar 22, 2:29 pm, Chinmay S <2.6kilohe...@gmail.com> wrote:
>
> > If...then...else... A simple challenge.http://2600hertz.wordpress.com/2010/03/18/if-then-else/
>
> 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!!");
>
> }
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.
BruceS
> 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?
Willem
) -----
) In the following code, what should be put after "if" to make the code
) produce the output "Hello-World!!"?
)
) if
) printf ("Hello-");
) 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
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.
>
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.
--
Andrew Poelstra
http://www.wpsoftware.net/andrew
Willem
) On Mar 22, 11:53?am, Branimir Maksimovic <bm...@hotmail.com> wrote:
)> On Sun, 21 Mar 2010 23:29:40 -0700 (PDT)
)>
)> Chinmay S <2.6kilohe...@gmail.com> wrote:
)>
)> > 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.
Branimir Maksimovic
We had matrices lectures in programming. Simply form matrix
and walk spirally. We were 17 years old, then.
BruceS
wrote:
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.
Ben Bacarisse
> BruceS wrote:
> ) On Mar 22, 11:53?am, Branimir Maksimovic <bm...@hotmail.com> wrote:
> )> On Sun, 21 Mar 2010 23:29:40 -0700 (PDT)
> )>
> )> Chinmay S <2.6kilohe...@gmail.com> wrote:
> )>
> )> > 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.
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>
--
Ben.
Samel - Luchino
> 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>
> --
> Ben.
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");
}
}
Ben Bacarisse
<snip>
> 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);
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]);
I presume the use of atoi(argv[1]) is deliberate?
> }
<snip>
> N=atoi(argv[1]);
> for(n=0;n<N*N;n++)
> {
> printf("|%.4d",M[n]);
If you print N * N - M[n] - 1 you get the same numbering as the
original puzzle.
> if(n%N==N-1)
> printf("|\n");
> }
> }
--
Ben.
spinoza1111
Willem is always full of surprises. So we don't need recursion.
Moi
if (fork() || sleep(1) )
/* not standard :-) */
AvK
Ben Bacarisse
> On Tue, 23 Mar 2010 09:27:25 -0700, BruceS wrote:
<snip>
>> 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!!");
>> -----
<snip>
>
> if (fork() || sleep(1) )
>
> /* not standard :-) */
Slightly more predictable:
if (!fork() && wait(0))
--
Ben.
Willem
) 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).
Willem
) 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
)
) 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.
Ben Bacarisse
> 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.
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).
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)).
--
Ben.
Ben Bacarisse
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.
--
Ben.
Willem
) Willem <wil...@turtle.stack.nl> writes:
)> 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.
Ben Bacarisse
That's essentially how I got to my solution though the idea is lost
because I decided to simplify the expressions.
--
Ben.
Moi
One thing: the xy2spiral() function does not need to know N.
N can be derived as Max(Abs(x), Abs(y)).
And you could possibly call it 'radius'.
(and call '4' the value of pi for a square circle ;-)
AvK
CVS
(Squeezed it into a “lean-mean” 99 liner...)
http://2600hertz.wordpress.com/2010/03/20/the-mystery-spiral-part2/
Please Comment if any further optimisations can be made...
THE MYSTERY SPIRAL:
http://2600hertz.wordpress.com/2010/03/20/the-mystery-spiral/
SOLUTION:
http://2600hertz.wordpress.com/2010/03/20/the-mystery-spiral-part2/