[For Fun] How to: solve a riddle using BYOND! in Off Topic

ID:181323
 
Dec 5 2010, 8:02 pm (Edited on Dec 5 2010, 8:20 pm)
First of all, I believe that this riddle best fit into the "Developer How-To" forum instead of any other because, well, it fits the description/requirements of the forum!

If it's meant to be somewhere else, however, please do move it. (As if I had to ask for that, heh).

NASA is trying to launch two robots onto mars so they can construct a station. This is a two robot job, so both robots must work together to build the station. However, they do not have a spaceship big enough to fit both, so decide to launch them separately. Although both rockets will be following the same launch protocols, some error will be inevitable and the robots will land in different positions. Now assume that mars is an endless array of trillions and zillions of squares, stretched side-by-side. Basically, it is an infinite two-dimensional space. Your goal is to program the same algorithm on both robots so when they land, they will start looking for each other, and construct the station together. The robots CANNOT be programmed with different algorithms, and have no means of communication to earth or each other or any entity whatsoever. However, the robots will deploy a parachute when landing, and that parachute will remain in the square they land forever. The robot can detect whether they have found a parachute in the square it is in. Come up with an algorithm so that they will be guaranteed to find each other. (Normal restrictions in programming apply, such as integer overflow: any number larger than 2^32 will be undefined, so if you are keeping a counter and it reaches above that, it will render your algorithm useless.)

Can you solve it using DM?
#1 Dec 5 2010, 8:59 pm
Just be sure:
Array is infinite 2D plane, or like a planet - round, so I can walk in circles without changing direction?
#2 Dec 5 2010, 9:09 pm
The best means to solve this is to give the robots the same set of destination coordinates. If they land in a different place, they have to go to the agreed-upon construction site. This is a prerequisite anyway if they'll be building, since obviously not every site is suitable. The only algorithm that can be designed for this is a simple high-level one, with lower-level algorithms necessarily handling navigation of the terrain.

There is another option available if the robots have the ability to scout the terrain from orbit. If so, then the algorithm is that if the robot did not spot a parachute when it arrived, it would stay put. Otherwise, it would head for the location of the parachute it saw. This algorithm however is no more suitable than the first and basically means the construction site is random. Also if you wanted to scale to include a third robot, the robots would have to be told that if they spotted multiple chutes they should scout out one at a time until they encountered their fellow robots. Aside from the aforementioned considerations, this uses more fuel and puts the robots at greater risk, while also forcing programmers to implement a a lower-level algorithm to solve the traveling salesman problem.

Lummox JR
#3 Dec 5 2010, 9:20 pm
In response to Ripiz (#1)
Let's assume it is an infinite 2D plane that is not round like a planet.
#4 Dec 5 2010, 10:44 pm
In response to Gooseheaded (#3)
Then one more question. Is it plane like in maths (coordinate can be 1; 1,1; 1,0001; 10^(-9)) or like array index - only integer?
#5 Dec 5 2010, 11:09 pm
No, this isn't something you can solve using BYOND in any way, shape, or form. The answer is simple: robots do whatever the crap they feel like to cover terrain (spirals would be appropriate, but walking randomly would also work). When they find the second parachute, move to the midpoint of the two. That's it.
#6 Dec 5 2010, 11:55 pm
In response to Ripiz (#4)
Integers only, I'd assume?
Although Garthor has reached the same conclusion I have.
#7 Dec 6 2010, 7:13 am
In response to Garthor (#5)
Garthor wrote:
No, this isn't something you can solve using BYOND in any way, shape, or form. The answer is simple: robots do whatever the crap they feel like to cover terrain (spirals would be appropriate, but walking randomly would also work). When they find the second parachute, move to the midpoint of the two. That's it.

I don't think the midpoint solution is ideal because while the two options I came up with scaled to accommodate more robots, this won't. It's your only option if the robots have no ability to survey the planet beforehand and if they aren't given coordinates, but it's still a complete waste of fuel and time. If this was the robots' only option for finding each other then the mission should be scrapped.

But you're right that this has nothing to do with BYOND.

Lummox JR
#8 Dec 6 2010, 11:25 am
In response to Lummox JR (#7)
Well, the only information in the problem is:
1) There are two robots
2) There are two parachutes which can only be seen from a zero distance
3) Both robots must behave in exactly the same manner
4) How do the robots find each other?
That's the only solution. Anything else is just meaningless fluff. Exceptionally meaningless, in this case.
#9 Dec 6 2010, 11:42 am (Edited on Dec 6 2010, 11:56 am)
Similarly, two robots on a line:


Two robots are placed at different points on a straight line of infinite length. When they are first placed down, they each spray out some oil to mark their starting points.
You must program each robot to ensure that the robots will eventually crash into each other. A program can consist of the following four instructions:
  • Go left one space
  • Go right one space
  • Skip the next instruction if there is oil in my current spot
  • Go to a label

[Note that a "label" is a name that refers to a line of your code. For example, you could label the third line of your program "surveying". Then, the instruction "goto surveying" would jump to line 3 and start executing from there on the next cycle.]
A robot will carry out one instruction per second. Both robots need not have the same program. Note that you won't know ahead of time which robot is on the left and which is on the right.