how do i solve this problem?

Not an official ACM page
[ Problem B | 1999 ACM Finals problem set | My ACM problem archive | my home page] The 23rd Annual
ACM International Collegiate
Programming Contest
WORLD FINALS
sponsored by http://www.karrels.org/Ed/ACM/99/bigblue.gif

Problem A
Bee Breeding

Professor B. Heif is conducting experiments with a species of South American bees that he found during an expedition to the Brazilian rain forest. The honey produced by these bees is of superior quality compared to the honey from European and North American honey bees. Unfortunately, the bees do not breed well in captivity. Professor Heif thinks the reason is that the placement of the different maggots (for workers, queens, etc.) within the honeycomb depends on environmental conditions, which are different in his laboratory and the rain forest. As a first step to validate his theory, Professor Heif wants to quantify the difference in maggot placement. For this he measures the distance between the cells of the comb into which the maggots are placed. To this end, the professor has labeled the cells by marking an arbitrary cell as number 1, and then labeling the remaining cells in a clockwise fashion, as shown in the following figure.

Code:

__ __ __ __ __/ \__/ \__/ \__/ \__ __/ \__/ \__/53\__/ \__/ \__ / \__/ \__/52\__/54\__/ \__/ \ \__/ \__/51\__/31\__/55\__/ \__/ / \__/50\__/30\__/32\__/56\__/ \ \__/49\__/29\__/15\__/33\__/57\__/ / \__/28\__/14\__/16\__/34\__/ \ \__/48\__/13\__/ 5\__/17\__/58\__/ /..\__/27\__/ 4\__/ 6\__/35\__/ \ \__/47\__/12\__/ 1\__/18\__/59\__/ /..\__/26\__/ 3\__/ 7\__/36\__/ \ \__/46\__/11\__/ 2\__/19\__/60\__/ /..\__/25\__/10\__/ 8\__/37\__/ \ \__/45\__/24\__/ 9\__/20\__/61\__/ /..\__/44\__/23\__/21\__/38\__/ \ \__/70\__/43\__/22\__/39\__/62\__/ / \__/69\__/42\__/40\__/63\__/ \ \__/ \__/68\__/41\__/64\__/ \__/ / \__/ \__/67\__/65\__/ \__/ \ \__/ \__/ \__/66\__/ \__/ \__/ \__/ \__/ \__/ \__/ \__/ \__/ \__/ \__/ \__/

For example, two maggots in cells 19 and 30 are 5 cells apart. One of the shortest paths connecting the two cells is via the cells 19 - 7 - 6 - 5 - 15 - 30, so you must move five times to adjacent cells to get from 19 to 30. Professor Heif needs your help to write a program that computes the distance, defined as the number of cells in a shortest path, between any pair of cells.

Input

The input consists of several lines, each containing two integers a and b (a,b <= 10000), denoting numbers of cells. The integers are always positive, except in the last line where a=b=0 holds. This last line terminates the input and should not be processed. Output

For each pair of numbers (a,b) in the input file, output the distance between the cells labeled a and b. The distance is the minimum number of moves to get from a to b. Sample Input

19 30
0 0
Output for the Sample Input

The distance between cells 19 and 30 is 5.
This page maintained by Ed Karrels.
Last updated December 7, 1999

i was just looking for some programing problems, when i got this site, which contains several archived programing contest problems.
this problem is from 1999. i just have no idea what needs to be known to solve this problem. although i suspect that it has to
with graph or network theory. but i am not a CS major. can someone help me?

EDIT:
Oops! I copy-pasted the page here, and it is distorting the thread layout, you can see the page here: http://www.karrels.org/Ed/ACM/99/prob_a.html
EDIT2: Fixed! Thanks Todd! :)
EDIT3: Duh! Now the hive gets distorted! Adding code tags again! :(
EDIT4: Finally! :)

Don't put the text within code tags and it will auto wrap.

First approach that i can think of :

Create the honeycomb layout by simple simulation. Store what cells are reachable from each cell in an adjacency list as from one cell, maximum 6 others could be reachable. Then do a bfs from cell1 to cell2. Maximum number of cells visited is 10000. There could be a faster mathematical way of generating the honeycomb other than simple simulation but i'm too tired to think it out right now. :(

I also searched for "shortest path" and found "Dijkstra's algorithm"
but the explanation is not so simple, as, i could understand it! :(

Quote:

ACM International Collegiate
Programming Contest
WORLD FINALS

If you are just starting out with algorithmics, id suggesnt starting with something simpler..Most problems in the ACM ICPC world finals are very tough.

thanks PING!
can you suggest any similar site where i can find simpler programming problems?

Sphere Online Judge
Topcoder
ACM UVA

Wow people. You don't need Dijkstra's algorithm for this. You are making it waaaay too complicated.

The real problem here is figuring out how to deal with the spiral coordinate system. And it's not that hard a problem. It would be nice not to discourage somebody attempting a perfectly good problem..

EDIT: The ACM programming problems are like elementary school world problems. There is stuff in there which is meant to throw you off what is actually a very simple solution. Clearly, that stuff worked!

My first thought was to do Dijkstra's algorithm as well. I don't know of another way right off of the top of my head.

Well I just figured out how to tell the distance from any node on a certain level of the honeycomb and the last node of that level. Although it does not solve the problem completely, it is a step in the right direction.

The distances of all nodes in a specific ring to the last node of that ring can be found as follows:

- Find the level of the ring. (Ex. node 15 is in level 3, node 5 is in level 2)
- The distances of each node in the ring to the last node of the ring (Ex. distances of all nodes on level 3 (nodes 15-30) to the last node on level 3 (node 30)) are:

Code:

int n = level; int d = 1; int i = 0; for ( int k = 0; k < (n * 2 - 1); k++, i++, d++ ) node[i].distance = d; for ( int k = 0; k < n; k++, i++ ) node[i].distance = d; d--; for ( int k = 0; k < n; k++, i++ ) node[i].distance = d; d--; for ( int k = 0; k < (n * 2 - 2); k++, i++, d-- ) node[i].distance = d;

if you look at any coordinate system, they are simply patterns where each node can be easily predicted or its position evaluated. You just need to find the pattern on this one, in order to compute solutions to the problem.

The pattern is simple. The core (ring 0) is node 1. The ring around it (ring 1) is 2 through 7, 6 cells. Every subsequent ring consists of 6 cells more than its inner ring. Ring 2 has 12 cells, ring 3 18, ring 4 24, which brings us to cell 62 and the last partial ring in the example.

Quote:

The ACM programming problems are like elementary school world problems.

I assume that is a joke. Comparing ACM ICPC world final's problems to 'elementary school world problems' is something i cannot fathom.

I have been playing around with this for the last couple of hours. I'm nearly there but got myself stuck at one last point, and I cant be bothered to think about it any more.

Basically the program converts the number to 2d co-ords, then moves in a direction according to difference in x, y positions from location to target. My problem is finding a simple way of getting the number of the adjacent tile to the current location. Anyone got any ideas?

Code:

#include <stdio.h> #include <math.h> #define MAX_RING 6 #define DEG_TO_RAD 0.0174532925 enum {DOWN, DOWN_LEFT, UP_LEFT, UP, UP_RIGHT, DOWN_RIGHT} adjacent; // Gets the current ring int GetRing(int pos) { static const int rings[MAX_RING] = { 1, 7, 19, 37, 61, 91 }; for(int i=0; i<MAX_RING; i++) if(pos <= rings[i]) return i; return -1; } void SpiralTo2D(int pos, int *x, int *y) { static const int ring_offset[MAX_RING+1]= { 0, 1, 7, 19, 37, 61, 91 }; static const int ring_size[MAX_RING] = { 1, 6, 12, 18, 24, 30 }; int ring = GetRing(pos); int step = pos - ring_offset[ring]; int sector_size = 360 / ring_size[ring]; int deg = (sector_size * step) - 240; *x = (int)(sin(deg*DEG_TO_RAD) * ring *10); *y = (int)(cos(deg*DEG_TO_RAD) * ring *10); //printf("%2d> x:%lf y:%lf", pos, x, y); //printf(" ring:%d, step:%d, sector:%d deg:%d\n", ring, step ,sector_size, deg); } int GetTile(int pos, const int move) { int ring = GetRing(pos); switch(move) { case UP: break; case DOWN: break; case DOWN_LEFT: break; case DOWN_RIGHT: break; case UP_LEFT: break; case UP_RIGHT: break; } return 1; } // Gets next step int GetNextTile(int location, int target) { int l_x, l_y, t_x, t_y; // Location and target co-ords SpiralTo2D(location, &l_x, &l_y); SpiralTo2D(target, &t_x, &t_y); printf("Loaction: %d %d\n", l_x, l_y); printf("Target: %d %d\n", t_x, t_y); if(l_x == t_x) // Move up or down only if(l_y == t_y) return -1; // Target found! else if(l_y < t_y) return GetTile(location, UP); // Tile above else return GetTile(location, DOWN); // Tile below else if(l_x > t_x)// Move left if(l_y > t_y) return GetTile(location, DOWN_LEFT); else return GetTile(location, UP_LEFT); else //Move Right if(l_y > t_y) return GetTile(location, DOWN_RIGHT); else return GetTile(location, UP_RIGHT); } int main() { int pos = 34; int target = 2; GetNextTile(pos, target); getchar(); return 0; }

The solution, I'm pretty sure, must not be obtained by defeating the original coordinates system. By mapping the cells to the cartesian system, you will be obtaining distances according to that coordinates system. The problem however asks you to do it with the proposed spiral coordinates.

In fact, the problem solves itself rather easily if you stick to that coordinate system. Much more easily than with the Cartesian coordinates. And the text even gives you an hint as to how you should solve it.

As I mentioned before you should first try to determine the pattern behind those coordinates. For this effect, take CornedBee earlier observation and then read the problem carefully again. At one point you read "For example, two maggots in cells 19 and 30 are 5 cells apart."

Can you see a general formula to calculate all distances regardless of the start and end cells as being the most obvious answer to the problem? Naturally you can, because even if the coordinate system was different, that is a characteristic of every 2d system you can come up with in which distances between two consecutive points is fixed. You just have to find the formula for this one.

I'm not going to try and solve it myself. Too lazy for that and math challenged enough for it to take me more than it should. But you guys enjoying the fine school years should have no trouble. Just don't complicate what is simple.

Well, I came up with a pretty dumb solution that goes through the Cartesian coordinates and finds the coordinates and their distance in a rather brain-dead way. At least it seems to give the correct output:

Code:

//hive.cpp #include <iostream> #include <cmath> struct Coord { int x, y; }; Coord coord_from_num(unsigned n) { const unsigned turn_count = 6; Coord turns[turn_count] = {{-1, 0}, {0, -1}, {1, -1}, {1, 0}, {0, 1}, {-1, 1}}; unsigned level = 0; unsigned level_start = 1; unsigned level_end = 1; //determine level on the spiral while (n > level_end) { level_start = level_end; ++level; level_end += level * 6; } //find coordinates by moving along the spiral Coord result = {0, level}; for (unsigned i = 0; i != turn_count; ++i) { for (unsigned j = 0; j != level; ++j) { if (level_start == n) return result; result.x += turns[i].x; result.y += turns[i].y; ++level_start; } } return result; // 1 } int get_move(int a, int b) { //what should be added to a, to advance the value towards b if (a < b) return 1; else if (a > b) return -1; return 0; } int get_distance(Coord start, const Coord& target) { //start advancing towards the target and count steps //move both in x and y direction, unless increments are (1, 1) or (-1, -1) int distance = 0; while (!(start.x == target.x && start.y == target.y)) { ++distance; int xInc = get_move(start.x, target.x); int yInc = get_move(start.y, target.y); start.x += xInc; if (abs(xInc + yInc) != 2) start.y += yInc; } return distance; } int main() { int a = 0, b = 0; while (std::cin >> a >> b && a && b) { Coord ac = coord_from_num(a); Coord bc = coord_from_num(b); std::cout << "The distance between cells " << a << " and " << b << " is " << get_distance(ac, bc) << '\n'; } }

anon: Yeah, nice. My distances are a bit short because I'm getting the distance from point to target in a direct line, however it should be accurate enough to set the path in the right direction each move.

mario: Although moving between squares will pretty much have to be done using the original co-ord system its not as easy as it may look. the side the outer/inner rings are on depends on the locations rotation on the ring which make it kind of tricky to deal with. All the solutions I can think of are so complicated I can't even be bothered to attempt them. If theres a simple equation for dealing with this I would still be interested to know. I can't see one.

Quote:

Originally Posted by mike_g

the side the outer/inner rings are on depends on the locations rotation on the ring which make it kind of tricky to deal with.

Not sure what you mean, but if I'm following you, it has no relevance sicne you can draw the hexagons on a piece of paper, rotate that piece of paper and the result is obviously the same.

All you need is a formula that tells you how much is 30 minus 19 on that coordinate system (as an example). Any attempt at using a cartesian system really would not going to be accepted by the judges :)

What you have in there is essentially an arithmetic progression. A slightly more complex one at that. But still an arithmetic progression, of which you need to find d.

edit: or geometric progression? I told you, i math challenged :)

I agree; I don't think the rotations matter. It seems clear (maybe I'm giving the game away) that the shortest path will get to/stay in the smaller ring, go around on the small ring, and then if necessary go out to get to the target. So you need to know how to get in and out. See if you can find a pattern for which outer cells you can get to from an inner.

Edit: And now looking again, that seems to work only if the cells are on the same half (or close enough to the center so it doesn't matter which way you go). Otherwise, you'll want to go through. Hmm....

Quote:

Originally Posted by tabstop

It seems clear [...] that the shortest path will get to/stay in the smaller ring

Were you to build an algorithm dependent on the smallest ring, would it still work if you didn't have to cross over to the opposite side of the honey comb to get from A to B? For instance, in the example, going from 58 to 54 is an easy four-step path, but if you don't build carefully you'll probably get a really silly answer.

54 and 58 are in the same ring, so you wouldn't change rings at all. (I don't mean the smallest ring down in the center, I mean the smaller of the two rings -- start and finish.)

28 and 37 are in the same ring, too, but if you don't go through the center, you'll never get the shortest path.

Another solution that I thought about is that it is easy to find the distance from the centre. So, the problem might be how to calculate the number of the end position if the centre is shifted to the start position.

Yeah, thats basically how my version woks. The ring is the distance from the center. The sector is the step on the ring and the x/y co-ords are got by doint sin/cos on the sector multiplied by the distance.

If I can get the adjacent tile numbers, then it should be possible to step towards the the target each iteration until its reached. I might get back to this later on.

map the coordinates of the center of each cell, then draw a line from cell A to cell B, the shortest path is defined by the cells the line passes through, if the line passes alogn the line between 2 cells, randomly pick on of the two, as either route will be the same distance.

Well, as I said in the post above I already have that part. I just need to find a way to move using the radial co-ordinate system. It should be possible to step in and out of rings by adding /subtracting a ring size with a modifier to take into account the spiral effect. Some sectors will have more paths to the outer ring than others as the image shows, and whether moving up, is: in, out or along the ring depends at which angle the current position is on the ring.
http://i92.photobucket.com/albums/l1...ndel/pic_a.png
Seems like a bloody nightmare :/

Think of polar coordinates. And think of the Archimedean Spiral equation. The proposed coordinate system is nothing more, nothing less, than an archimedean spiral in a polar coordinate system.

I keep telling you, it's not that hard.

Quote:

Originally Posted by PING

I assume that is a joke. Comparing ACM ICPC world final's problems to 'elementary school world problems' is something i cannot fathom.

I didn't say they were easy like elementary problems. I said they contain deceptive information, like elementary problems.

Ok I think I cracked it, although I took the mentally challenged route (I know, its sad) ;)

Edit: oh whoops, it will give a compile error. To fix it remove the 'else' from the 'else if' at the start of the line and it will work.

mike_g, wasn't one requirement that it should handle positions up to 10000?

Oh yeah, bummer. I forgot about that. Still, while mindlessly writing out the array content I realised that it probably wouldent be to hard to get adjacent tile as there are 6 sides and 6 corners thats only 12 cases to deal with. Anyway, at least it works on a small scale.

Ok, I came up with a version that can work with any co-ords (in an int). I also fixed a bug that occasionally caused the path to take one step more than necessary. Its kind of dumb of me but I completely misinterpreted the task. For some reason I thought it had to print out the steps along the path to get to the target o_O. Anyway this does that as well as finding the move cost. Took me a long time, lol.