Geek Challenge

[NickBerry]

Seems like maybe there are some people in here who are expert in coding ?

I’m not at all expert but find it really interesting, and have been learning python alongside my sons.

When you live in the sticks like us, you have to make your own entertainment and so we have having a crack at the following challenge:

“A caterpillar starts at the top left corner of a square grid. Caterpillar biscuits are placed randomly in the grid. But the caterpillar can only see a certain number of squares in any direction. Write a program to guide the caterpillar to find all the biscuits in the shortest time.”

Any thoughts? Initially I was thinking of moving systematically through the grid on the shortest path (?spiral) with out and back detours to pick up the biscuits as they come into view.

My son seems to be taking the approach of mapping out the minimum number of waypoints the caterpillar needs to visit to see all the grid, then using a travelling salesman algorithm to optimize the route. With the added twist that whenever a biscuit comes into view, that is added as a new waypoint and the travelling salesman calculations repeated.

Who’s right and is there a better way?

[JibberJim]

My initial thought is it will depend on the number of biscuits, and if you know when you’ve found them all (as then you don’t need to look into the areas you’ve not already visited), 'cos the see all squares and minimum route to see all squares is the same ifyou’re not diverting, so the time sensitivity depends on how much time you spend leaving the path to pick up a biscuit.

I imagine the divert to pick up and adjust the route to see the remaining area in most efficient way is sufficient, but likely the optimisation over simply pre-defined route and divert seems minimal.

[GRamsay]

This is actually a very difficult problem to solve. Would guess its probably a NP hard problem, like the 3d bin packing problem. So you are not going to easily know if you’ve taken the shortest route.

Using the TSP algorithm is a good approach, however in the traditional TSP programme you’ll already know all the waypoints. But in this problem we are dealing with a much smaller area. Because the area is small my first approach would be an ugly attempt to run every possible scenario. Find the closest biscuit each time and move to each on in turn. But then what are the rules of the challenge? Is the placement of biscuits allowed to be the same each time, or would each run require a new random placement? If ita random each time then this approach won’t work.

I was going to spend the day coding the PFD for my airbus A320 sim I’m building but now I am going to be consumed by this.

I’ll come back later and see what I’ve found.

[GRamsay]

Is that the full text of the challenge? If I was given that in a JIRA I would return it to product not R4D (Ready 4 Development).

How big is the grid?
It can only move a certain number of squares, how many is that?

I am going to say a 10x10 grid and you can only see in the 8 immediate squares surrounding your current position.

How many biscuits? Its that random?

[NickBerry]

@GRamsay

It was passed on verbally to junior, I am interpreting the constraints as something like this:

Grid is a 10*10 square.
Caterpillar can see for v squares, its field of vision is a square of side 2v+1 with caterpillar in the centre.
Biscuits are placed randomly at the start of each round, there is at least 1 biscuit but no more than 20 biscuits.

Woke up in the night thinking about it!

[GRamsay]

Not getting very far. I am using Processing 3 as its quick to mock up and draw. (https://processing.org/)

Code below will draw a 10x10 square and place a random no of biscuits between 1 and 20 in random squares.

Next step will be start with some algorithms to find all the biscuits. I assume the caterpillar doesn’t know the number of biscuits up front but we can exit the algorithm once we hit the number.

int recSize = 50;
int rows = 10;
int cols = 10;
int space = 0;

int v = 4;
int fieldOfView = 2*v+1;

ArrayList grid = new ArrayList();

void setup()
{
size(768, 768);
background(0);
stroke(0);
fill(255);

ellipseMode(CENTER);
Square s;

for(int x = 0; x <= rows-1; x++)
{
for (int y=0; y <= cols-1; y++)
{
fill(255);
rect(space + x * (recSize + space), space + y *(recSize + space), recSize, recSize);
s = new Square();
s.x = x;
s.y = y;
grid.add(s);
}

}
PlaceBiscuits();
text("~", 25, 25);
}

void loop()
{

}

void PlaceBiscuits()
{
int minBiscuits = 1;
int maxBiscuits = 20;

int noBiscuits = (int)random(minBiscuits, maxBiscuits);

for(int x = minBiscuits; x <= noBiscuits; x++)
{
int rndX = (int)random(1,10) * recSize;
int rndY = (int)random(1,10) * recSize;

 fill(0);
 circle(rndX + (recSize/2), rndY + (recSize/2), 6);
 SetGridHasBiscuit(rndX, rndY);

}

}

void SetGridHasBiscuit(int x, int y)
{
for(int i=0;i<grid.size(); i++)
{
if(grid.get(i).x == x && grid.get(i).y == y)
{
grid.get(i).hasBiscuit = true;
}
}
}

class Square
{
int x;
int y;
boolean hasBiscuit = false;
}

[Poet]

So, the search path of a foraging animal?

You tried the Random Walk Theory as a starting point?

But…you’re not going know if you’ve seen all of the biscuits until you’ve seen all of the squares, or 20 biscuits.
As you don’t know how many biscuits there are.

Can the caterpillar move diagonally?
Or just up/down, left/right?

Start off with v=0, or a partially sighted caterpillar.

I’d draw it out in my notebook with one biscuit in the bottom right.
Then work out the shortest way to eat that biscuit seeing all of the squares.

Then code that.
And work from there.

[GRamsay]

There isn’t enough info to know how to do it. As you say how does it move, and do we keep going until we have 20 or visit all squares.

I’m tempted to give up and get one of my devs to solve it.

[GRamsay]

Although this is a great introduction to software development for Nicks son.

A nebulous request
Insufficient requirements
No one can agree on how best to do it.

All he needs is a project manager asking hum every 10 minutes if he’s finished yet.

[Poet]

I just booted it up Jupyter to start doing it and presenting it nicely
Jumped into The Jungle on Zwift where @NickBerry gave me a ride on.

I then realised there’s not enough info…

…but;
v=0
you can only move up/down left/right
Keep going until b=20 or s=0 (where b=biscuits and s=squares left to see)

Still leaves; do you need to eat the biscuits or just see them?

If I see a biscuit, I’ll eat it, but not if it’s too far away and there might be another biscuit sooner.
What’s the caterpillars delayed gratification response?

[Poet]

Send the caterpillar round to see all of the squares, therefore seeing all of the biscuits.
Once you’ve done that, you’ll know the shortest route to eat all of the biscuits!

So, the shortest route (using the info given) is the shortest way to see all of the squares.

It’s field of vision is a square of sides 2v+1.
Starting in the top left with a v=4 means our caterpillar can see all of the squares by moving to the centre (or he eats all of the biscuits on his way there, which he won’t know until he is there)

When v=8 the caterpillar can see all of the squares and determine the shortest route immediately.

When v=0 you need to see all of the squares (or eat 20 biscuits)

[GRamsay]

That isn’t going to work. 95% of the time you will have b < 20 so you are going to have to run until s=0 most of the time. So you’ll never know if you have taken the shortest route.

Also I don’t think caterpillars eat biscuits.

Some one is on a piss take with this

[magnacarter]

@GRamsay

Although this is a great introduction to software development for Nicks son.

A nebulous request
Insufficient requirements
No one can agree on how best to do it.

All he needs is a project manager asking hum every 10 minutes if he’s finished yet.

Hah hah. If he wants to really make it lifelike, he also needs to complete a test of his code against the wrong criteria he’s been given, be forced to write a 10 page document on how it works that will immediately be filed away and forgotten about, and then be blamed for it not working in 6 weeks time. Preferably, he should also be given a substantially revised spec about 40 mins before he is due to complete his final code, and be told that the repository it was checked into was deleted last night, as it was the wrong one, and no one is quite sure why he wasn’t told.

[Poet]

@magnacarter

[GRamsay]

Developers testing their own code? Marking their own homework? Oh dear.

But product want leaves and not biscuits now, and the grid needs to be pink

[GRamsay]

Right I’m going to tackle this bitch in the morning. It’s in my head now and I need to solve it.

[NickBerry]

We kind of got somewhere with this today

The code is proper fugly I’m sure

Also instead of training for an Ironman I have been sat on my a$$ in front of a PC all day

[NickBerry]

It’s an implementation of my son’s idea. In this case the caterpillar knows there are 3 biscuits but not where they are. It can see 2 squares away from where it is.

On the grid above “seen” squares are represented by dots.

The unseen squares are represented by question marks.

The shortest route ABCDE which will let the caterpillar “see” all these squares is mapped out using a travelling salesman problem approach.

If a biscuit comes into view, this is added as an extra waypoint.

Then the caterpillar moves one square down that route, and repeats all the calculations from than new starting point. And so on until the last biscuit is reached.

It kind of seems to work but uses a brute force approach to theTSP (does this make it n! complexity??). It is only good for about 10 waypoints then it times out. To do more I think it might be helpful to branch and bound, or optimize in some other way, but this is not something I know how to do yet & looks full geek: simulated annealing, logarithmic cooling rates …

[mw22]

Where can one purchase caterpillar biscuits??

[NickBerry]

You just have to mine them. Like bitcoin except it will take longer, if today’s experience is anything to go by…

Lets call it a rest day