2 Challenges for the C Programmer in U...

Discussion in 'C Programming' started by Chinmay S, Mar 22, 2010.

  1. Chinmay S

    Chinmay S Guest

    Chinmay S, Mar 22, 2010
    #1
    1. Advertising

  2. Chinmay S

    spinoza1111 Guest

    On Mar 22, 2:29 pm, Chinmay S <> 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!!");
    }
    >
    > <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>
     
    spinoza1111, Mar 23, 2010
    #2
    1. Advertising

  3. Chinmay S

    spinoza1111 Guest

    On Mar 22, 2:29 pm, Chinmay S <> wrote:
    > 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>


    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.
     
    spinoza1111, Mar 23, 2010
    #3
  4. Chinmay S

    BruceS Guest

    On Mar 23, 9:47 am, spinoza1111 <> wrote:
    > On Mar 22, 2:29 pm, Chinmay S <> 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, Mar 23, 2010
    #4
  5. Chinmay S

    BruceS Guest

    On Mar 22, 11:53 am, Branimir Maksimovic <> wrote:
    > On Sun, 21 Mar 2010 23:29:40 -0700 (PDT)
    >
    > Chinmay S <> 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?
     
    BruceS, Mar 23, 2010
    #5
  6. Chinmay S

    Willem Guest

    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
     
    Willem, Mar 23, 2010
    #6
  7. On 2010-03-23, Willem <> wrote:
    > 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
     
    Andrew Poelstra, Mar 23, 2010
    #7
  8. Chinmay S

    Willem Guest

    BruceS wrote:
    ) On Mar 22, 11:53?am, Branimir Maksimovic <> wrote:
    )> On Sun, 21 Mar 2010 23:29:40 -0700 (PDT)
    )>
    )> Chinmay S <> 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.


    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
     
    Willem, Mar 23, 2010
    #8
  9. Chinmay S

    BruceS Guest

    On Mar 23, 11:16 am, Andrew Poelstra <>
    wrote:
    > On 2010-03-23, Willem <> wrote:
    >
    > > 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.


    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.
     
    BruceS, Mar 23, 2010
    #9
  10. Willem <> writes:

    > BruceS wrote:
    > ) On Mar 22, 11:53?am, Branimir Maksimovic <> wrote:
    > )> On Sun, 21 Mar 2010 23:29:40 -0700 (PDT)
    > )>
    > )> Chinmay S <> 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.
     
    Ben Bacarisse, Mar 23, 2010
    #10
  11. > 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.


    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");
    }
    }
     
    Samel - Luchino, Mar 23, 2010
    #11
  12. Samel - Luchino <> writes:
    <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.
     
    Ben Bacarisse, Mar 24, 2010
    #12
  13. Chinmay S

    spinoza1111 Guest

    On Mar 24, 1:18 am, Willem <> wrote:
    > BruceS wrote:
    >
    > ) On Mar 22, 11:53?am, Branimir Maksimovic <> wrote:
    > )> On Sun, 21 Mar 2010 23:29:40 -0700 (PDT)
    > )>
    > )> Chinmay S <> 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.
    >
    > 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


    Willem is always full of surprises. So we don't need recursion.
     
    spinoza1111, Mar 24, 2010
    #13
  14. Chinmay S

    Moi Guest

    On Tue, 23 Mar 2010 09:27:25 -0700, BruceS wrote:

    > On Mar 23, 9:47 am, spinoza1111 <> wrote:
    >> On Mar 22, 2:29 pm, Chinmay S <> 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.



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

    /* not standard :) */

    AvK
     
    Moi, Mar 24, 2010
    #14
  15. Moi <> writes:

    > 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.
     
    Ben Bacarisse, Mar 24, 2010
    #15
  16. Chinmay S

    Willem Guest

    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
     
    Willem, Mar 24, 2010
    #16
  17. Chinmay S

    Willem Guest

    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
     
    Willem, Mar 24, 2010
    #17
  18. Willem <> writes:

    > 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, Mar 24, 2010
    #18
  19. Willem <> writes:

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


    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.
     
    Ben Bacarisse, Mar 24, 2010
    #19
  20. Chinmay S

    Willem Guest

    Ben Bacarisse wrote:
    ) Willem <> 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.


    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
     
    Willem, Mar 25, 2010
    #20
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Tony Burch
    Replies:
    0
    Views:
    771
    Tony Burch
    Jul 15, 2004
  2. Phrederik

    Re: SUN challenges Microsoft

    Phrederik, Sep 16, 2003, in forum: HTML
    Replies:
    3
    Views:
    376
    Trevor
    Sep 17, 2003
  3. andy johnson

    Re: SUN challenges Microsoft

    andy johnson, Sep 16, 2003, in forum: HTML
    Replies:
    6
    Views:
    384
    Toby A Inkster
    Sep 17, 2003
  4. Replies:
    0
    Views:
    404
  5. Romeo Colacitti

    Programming challenges leading to a job?

    Romeo Colacitti, Jun 26, 2006, in forum: C Programming
    Replies:
    11
    Views:
    497
Loading...

Share This Page