2 Challenges for the C Programmer in U...

[Ben Bacarisse]

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.

That's essentially how I got to my solution though the idea is lost
because I decided to simplify the expressions.

 

[Moi]

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

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]

Finally, uploaded the original solution to the Mystery Spiral...
(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/