4 replies to this topic

[last_stand]

Hello,please i need help on Ant in a Chessboard problem which state that:One day, an ant called Alice came to an M*M chessboard. She wanted to go around all the grids. So she began to walk along the chessboard according to this way: (you can assume that her speed is one grid per second)
At the first second, Alice was standing at (1,1). Firstly she went up for a grid, then a grid to the right, a grid downward. After that, she went a grid to the right, then two grids upward, and then two grids to the left…in a word, the path was like a snake.
For example, her first 25 seconds went like this:
( the numbers in the grids stands for the time when she went into the grids)

At the 8th second , she was at (2,3), and at 20th second, she was at (5,4).
Your task is to decide where she was at a given time.
(you can assume that M is large enough)

i wanna have the sudo code which solve this problem,thx.

[WingedPanther]

I can think of two different ways to solve the problem. The real question is, can you trace out where she is on a piece of paper? Once you do that, look at how you are moving.

I would store the following information if you want to trace her route for n seconds: x-coord, y-coord, direction of motion, current time.

[`Alex]

Not really sure what your talking about.

[PythonPower]

Eventually, following that pattern, she will reach the end of the board. In that case, what happens?

Assuming the board is infinite in size, I have a solution that can find the (x, y) coordinates given a t value in O(1) complexity. I'll post it if this isn't homework and you just need an answer.

If you want to see it for yourself, consider breaking the position up into what L-shape portion the ant is on and the offset from the start of the L-shape. There is some symmetry with the x and y coordinates, also.

[PythonPower]

It is also possible to map any (x, y) back to a t in O(1). This reminds me of finding the cardinality of a set since essentially I have formed a bijection between the counting numbers and coordinates (x, y). Hence there are aleph-zero coordinates, but that was "obvious" without a bound.