Problem 1907. Capture the flag(s)

Created by Alfonso Nieto-Castanon

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Flags 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.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Description</w:t></w:r><w:r><w:t>:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The board is described by a matrix</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>B</w:t></w:r><w:r><w:t> with 1's at the flag positions, and 0's otherwise.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>E.g.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ B = [0 0 1 1; \n 0 0 1 1;\n 0 0 1 0];\n\n N = 6;]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>You are starting at the top-left corner (row=1, col=1) and are allowed</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>N</w:t></w:r><w:r><w:t> steps (steps are up/down/left/right movements, no diagonal movements allowed).</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Return a trajectory attempting to maximize the number of flags captured. The output of your function should be a</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>Nx2</w:t></w:r><w:r><w:t> matrix of the form</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>[row, col]</w:t></w:r><w:r><w:t> (not including the initial [1,1] position) visiting as many flags as possible.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>E.g.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ path = [1 2;\n 1 3;\n 1 4;\n 2 4;\n 2 3;\n 3 3];]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This solution captures all 5 flags on the board.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Scoring</w:t></w:r><w:r><w:t>:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>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.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Note</w:t></w:r><w:r><w:t>:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The boards and number of movements allowed will be large. Optimizing over all possible trajectories is very likely to time out.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Flags 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.<pre> B = [0 0 1 1; 
 0 0 1 1;
 0 0 1 0];</pre><pre> N = 6;</pre>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.<pre> path = [1 2;
 1 3;
 1 4;
 2 4;
 2 3;
 3 3];</pre>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.

Solve

Solution Stats

18 Solutions
7 Solvers

Last Solution submitted on Jan 17, 2020

Last 200 Solutions

Problem Comments

1 Comment

1 Comment

Paul Berglund on 1 Oct 2013

I love the fact that you put an animation option in. It's not just helpful to see where your heuristic is messing up, it's fun to watch too.

Solution Comments

Solution 327239

1 Comment

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...

Solution 327224

1 Comment

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.

Problem Recent Solvers7

Problem Tags

flag greedy search

Problem 1907. Capture the flag(s)

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers7

Suggested Problems

More from this Author38

Problem Tags

Problem 1907. Capture the flag(s)

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers7

Suggested Problems

More from this Author38

Problem Tags

Players