MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn moreOpportunities for recent engineering grads.

Apply TodayFlags are distributed randomly on a large board. Starting from the corner position your goal is to capture as many flags as possible in at most N moves.

**Description**:

The board is described by a matrix **B** with 1's at the flag positions, and 0's otherwise.

E.g.

B = [0 0 1 1; 0 0 1 1; 0 0 1 0];

N = 6;

You are starting at the top-left corner (row=1, col=1) and are allowed **N** steps (steps are up/down/left/right movements, no diagonal movements allowed).

Return a trajectory attempting to maximize the number of flags captured. The output of your function should be a *Nx2* matrix of the form *[row, col]* (not including the initial [1,1] position) visiting as many flags as possible.

E.g.

path = [1 2; 1 3; 1 4; 2 4; 2 3; 3 3];

This solution captures all 5 flags on the board.

**Scoring**:

Your function will receive a score equal to the number of non-visited flags across all 50 of the testsuite problems. You need to leave at most 10,000 flags univisited (among 50,000 total flags) to pass this problem.

**Note**:

The boards and number of movements allowed will be large. Optimizing over all possible trajectories is very likely to time out.

9 correct solutions
5 incorrect solutions

Last solution submitted on May 07, 2014

1 player likes this problem

1 Comment

Paul Berglund
on 1 Oct 2013

OK, at the cost of taking twice the running time I was able to squeeze into Cody's tiny memory. Now I can think about improving the heuristic...

1 Comment

Paul Berglund
on 1 Oct 2013

This runs fine on my machine but I guess Cody is running without very much memory, so it can't handle it...well it was only scoring about 3000 anyway.

1 Comment