Solve a Tron Game

Tron is a great game, and if you haven't played it the internet has MANY online versions available. A fun challenge is to try to write an AI that plays Tron, which is normally much better than any human, thanks to their frame perfect dodging.

Even with their perfect dodging of walls, they still get themselves trapped easily.

Your task, is to write a script that when fed a map containing a single tron bike, that may already be partially filled, and output the actions required to fill it as much as possible.

The Task

From the letter p in the input, find the best moves to fill the most space in the maze, in as few iterations as possible, then output as a string of r(ight)u(p)l(eft)d(own), describing that path.

If you attempt to move into wall, your run is ended.

if you attempt to move where you have already been, your run is ended.

if your run contains an unexpected character, it is ended at that character.

Filling space refers to passing over it in your run. Your starting position is counted.

Input / Output

Your input will be through any valid method,

A maze, consisting of the characters # p (Pounds (0x23), Literal space (0x20) and the letter p lowercase (0x70)) one of the following forms

  • A single multiline string
  • An array of strings, split by lines
  • An array of arrays, each containing a single character

You must output exactly

  • A string or array of strings containing only the characters rlud case sensitive, describing your path through the maze.

You may use any reasonable permutation of these input and output format as well, such as bytes instead of characters.

Test Cases

Straight Forward.

Input:

#######
#p    #
#######

Example Output: rrrr

A Turn.

Input:

#######
#p    #
##### #
    # #
    ###

Example Output: rrrrdd

Box Filling.

Input:

#######
#p    #
#     #
#     #
#######

Example Output: rrrrdlllldrrrr

Complicated

Input:

#######
#p    #
#     #
#     #
##### #
    ###

Unfillable

Input:

 ########
 #p     #
 #     ##
###### #
#      #
##     #
 #######

Scoring

Your score is a combination of how fast your code runs and how many squares you fill of all the test cases.

Score is Total successful moves across Test Cases / Algorithmic Complexity Across Test Cases

So if your Algorithm has a complexity of O(a*b) Where 'a' is Maze Width and 'b' is Maze Height, then your Algorithm Complexity Total is (TestCase1Width * TestCase1Height) + (TestCase2Width * TestCase2Height)...

See More on Big O Notation

Highest score Wins!

Notes

  • The input will always be an enclosed surrounding the p
  • There will always be atleast 1 space to move from the start
  • The area may not always be possible to fill completely.
  • Your code should still work competitively on a random valid input. That is, do not cater just to the test cases.
  • Standard Loopholes Apply
  • this is a mutation, where both speed and space filled matters, not code length. Go ham.
  • I'm particularly interested in a Java solution.
  • Have fun!

Solution tester

var storedMap = "";
	function restoreMap(){
		document.getElementById("maze").value = storedMap;
	}
	function trymaze(){
		var score = "";
		var maze = document.getElementById("maze");
		storedMap = maze.value;
		var commands = document.getElementById("methodin");
		var converts = {r:{r:"─",u:"┌",d:"└",l:"─"},u:{r:"┘",u:"│",d:"│",l:"└"},d:{r:"┐",u:"│",d:"│",l:"┌"},l:{r:"─",u:"┐",d:"┘",l:"─"}}
		var dirs={l:{x:-1,y:0},u:{x:0,y:-1},r:{x:1,y:0},d:{x:0,y:1}};
		var last = "";
		var boxes = commands.value.replace(/./g, function(c){
			if(last==""){
				last = c;
				return {r:"╶",u:"╵",d:"╷",l:"╴"}[c];
			}
			var s = converts[c][last];
			last = c;
			return s;
		})
		var mMaze = maze.value.replace("p"," ").split("\n");
		var pp = maze.value.indexOf("p")
		var y = (maze.value.substring(1,pp).match(/\n/g)||[]).length;
		var x = ((maze.value.match(/.*p/)||[""])[0].length)-1;
		var path = commands.value.split("");
		for(s in path){
			tx = x + dirs[path[s]].x;
			ty = y + dirs[path[s]].y;
			mMaze[y] = mMaze[y].replaceAt(x, boxes[s]);
			if(!mMaze[ty]){
				alert("NO MAZE SEGMENT "+ty);
				break;
			}
			if(mMaze[ty].substring(tx,tx+1)!=" "){
				alert("HIT A WALL: "+tx+" "+ty+" \""+mMaze[ty].substring(tx,tx+1)+"\"")
				break;
			}
			score++;
			x=tx;
			y=ty;
			mMaze[y] = mMaze[y].replaceAt(x, "O");
		}
		if(document.getElementById("score").value){
			document.getElementById("score").value = document.getElementById("score").value + ", " + score;
		}else{
			document.getElementById("score").value = score;
		}
		maze.value = mMaze.join("\n");
	}

	String.prototype.replaceAt=function(index, character) {
	    return this.substr(0, index) + character + this.substr(index+character.length);
	}
*{
		font-family: monospace;
	}
	textarea{
		width:30em;
		height:15em;
	}
<textarea id = "maze"></textarea>
	<form>
	  <input type="text" id="methodin"></input>
	  <input type="button" onclick="trymaze()" value="Try Maze"></input>
	  <input type="button" onclick="restoreMap()" value="Reset Maze"></input><br/>
	  <input type="text" id="score"></input>
	</form>

closed as unclear what you're asking by Level River St, xnor, Post Left Ghost Hunter, Conor O'Brien, manatwork Nov 10 '16 at 8:38

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    What do you mean by an iteration? If you mean a move, the space filled will be equal to the number of moves plus 1. The best way to solve this problem would be to do a huge recursive search of all possible paths before making any moves - does that count as "iterations" or not? At the other end of the scale is a dumb solution that just walks forward until it crashes into a wall without even checking. In the middle, are many other possibilities of movement and level of checking the environment as to what counts as an "iteration" and what doesn´t. The scoring needs more definition. – Level River St Nov 10 '16 at 2:08
  • Should have explained it a bit better. – ATaco Nov 10 '16 at 2:30
  • Can the maze have interior holes? – xnor Nov 10 '16 at 2:48
  • For reference, this is asking for a known-start Hamiltonian path on a grid graph. It's known that Ham cycle on a general grid graph is NP-complete, whereas for ones without internal holes, a polynomial time algorithm exists. These both likely convert to paths and fixed-start. It's not clear if this is asking for unfillable graphs to be maximally filled, in which case I suspect it's NP-hard in both cases. – xnor Nov 10 '16 at 2:53
  • Holes are possible, and the idea isn't to find the perfect solution, however, to find a balance between efficiency and space filling. – ATaco Nov 10 '16 at 3:47