Gotta Collect 'Em All
PHP, 385 335 307 270 256 bytes
function c(&$m,$x,$r=-1,$d=0){if($r<0)$r=array_search(P,$m);$m[$r]=V;if(!in_array(T,$m))die;foreach([$r%$x?$r-1:-1,$m[$r-$x]?$r-$x:-1,$m[$r+$x]?$r+$x:-1,$r%$x<$x-1?$r+1:-1]as$o=>$n)if($n>=0&$m[$n]!=M&$m[$n]!=V){echo LUDR[$o];c($m,$x,$n,$o);}echo RDUL[$d];}
Try it online!
Uses a recursive depth-first search to crawl the map until all treasures are found.
Input is a one-dimensional array map and number of columns, example: c( $map, 13 );
.
Output is to STDOUT
as L,R,U and D
.
Or 242 bytes to output as numbers (but I prefer the letters).
Ungolfed
function c( &$m, $x, $r=-1, $d=0 ) {
// locate starting room ($r) on first move
if( $r < 0 )
$r = array_search( 'P', $m );
// mark square on map ($m) with V to show it has been visited
$m[ $r ] = 'V';
// end if no more treasures
if ( ! in_array( 'T', $m ) )
exit;
// generate list of adjacent squares
$dirs = [
$r % $x ? $r - 1 : -1, // Left
$m[ $r - $x ] ? $r - $x : -1, // Up
$m[ $r + $x ] ? $r + $x : -1, // Down
$r % $x < $x - 1 ? $r + 1 : -1 // Right
];
// consider valid directions for next move
foreach ( $dirs as $o => $n )
// if not a Wall or Mountain and not Visited
if ( $n >= 0 and $m[ $n ] != 'M' and $m[ $n ] != 'V' ) {
// display the direction
echo 'LUDR'[ $o ];
// and recursively keep crawling
c( $m, $x, $n, $o );
}
// reached a dead end, go back to previous square
echo 'RDUL'[ $d ]; // display the reverse direction
}
Basic Case
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|P| | | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | |T| | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | |M|M|M|T| | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | |T| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
DDDDDRUUUUURDDRUURDDRUURDDDLDLLLDRRRRURUUUURDDDDDLRRU
Locked Up
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|P| | | | |M| | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | |M| | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | |T| | |M| | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|M|M|M|M|M|M| | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
DDRUURDD
No Treasure:
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|M|M|M|M|M|M|M|M|M|M|M|M|M|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|M|M|M|M|M|M|M|M|M|M|M|M|M|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|M|M|M|M|M|M|M|M|M|M|M|M|M|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|M|M|M|M|M|M|M|M|M|M|M|M|M|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|M|M|M|M|M|M|M|M|M|M|M|M|M|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|M|M|M|M|M|M|M|M|M|M|M|M|P|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
(no output)
No way to move
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|M|M|M|M|M|M|M|M|M|M|M|M|M|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|M|M|M|M|M|M|M|M|M|M|M|M|M|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|M|M|M|M|M|M|M|M|M|M|M|M|M|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|M|M|M|M|M|M|M|M|M|M|M|M|M|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|M|M|M|M|M|M|M|M|M|M|M|M|M|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|M|M|M|M|M|M|M|M|M|M|M|M|P|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
(no output)
The world is a giant treasure
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|T|T|T|T|T|T|T|T|T|T|T|T|T|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|T|T|T|T|T|T|T|T|T|T|T|T|T|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|T|T|T|T|T|T|P|T|T|T|T|T|T|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|T|T|T|T|T|T|T|T|T|T|T|T|T|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|T|T|T|T|T|T|T|T|T|T|T|T|T|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|T|T|T|T|T|T|T|T|T|T|T|T|T|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
LLLLLLUURDRURDRURDRURDDDLLLLLLLDDRURDRURDRURDRURUUUURDDDDDLRRUUUUURDDDDDRUUUUU
1x1
+-+
|P|
+-+
(no output)
Back Alley
DDDDDRUUUUURDDDDDRUUUUURDDDDDRUUUUURDDDDDRUUUUURRRRRLLLLLDDRRRRRLLLLLDDRRRRR
Hedge Maze (an original creation)
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|P|M| |T|M| | | |M| |M|M|T|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |M| |M| | |M|T|M|T| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|T| | |M| |M| |T|M|M|M| |M|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|M|M| | | |M| |M|M| | | |M|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|T| | |M| |M| | | | |M| |M|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|M|M| |T| | |M|M|M|M|M| |T|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
DDRRUURLDDDDLLRRDRRUULRUURURRDDLDDRRRURRUULLUDRRRUDLDDDDR
JavaScript (ES6), 187 183 173 bytes
Takes input as a matrix of characters. Returns an array of signed integers: -2 = down, -1 = right, 1 = left and 2 = up.
ff=(m,X,Y,p=[])=>/T/.test(m)?(g=u=>m.some((r,y)=>r.some((c,x)=>(r[o=c=='M'|c>u|(h=X-x)*h+(v=Y-y)*v^c!='P'?0:f(m,x,y,1/X?[...p,h+2*v]:p,r[x]=3-~r[x]),x]=c,o)))?O:g(-~u))``:O=p
Try it online! (with the output translated back to L, R, U, D)
How?
This AI:
Is definitely more artificial than intelligent.
Rushes like a mad man in the map (i.e. implements a depth-first search).
Stops as soon as there are no more treasures, but otherwise does not care about the positions of the remaining treasures. This test is done with a regular expression.
/T/.test(m)
Compares the quadrance between its current position \$(X,Y)\$ and a new position \$(x,y)\$ with \$1\$ to know whether it can move there. Or tests if the cell contains
"P"
if its position is not yet defined.(h = X - x) * h + (v = Y - y) * v ^ c != 'P'
Writes \$4N\$ on a cell that has been visited \$N\$ times and uses this threshold combined with an internal counter \$u\$ to decide -- in a sudden flash of lucidity -- whether it should backtrack over already visited cells when everything else failed.
Python 2, 233 bytes
G=input()
e=enumerate
P=T=M=E=frozenset()
for i,k in e(G):
for j,l in e(k):exec l+'|={(i,j)}'
G={0}
c=-1
while T-G|G&M|G-E-T:
G-=G;e=list(P)[0];x=c=c+1;r=()
while x:m=x%5%4;x/=5;r+=m,;e=~-m%2*~-m+e[0],m%2*(m-2)+e[1];G|={e}
print r
Try it online!
Very slow. Most of the test cases would probably time out.
MPTLRUD
→ EMPT1302
. Any other characters should be considered to be prefixes, separators or postfixes.