Gotta Collect 'Em All

Question

Your task here will be to write a very dumb AI capable of fetching all treasures on a map.

Map

The map is defined as follow: (artist-mode™-powered)

Basic case:

+-+-+-+-+-+-+-+-+-+-+-+-+-+
|P| | | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | |T| | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | |M|M|M|T| | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | |T| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+

---

Locked up:

+-+-+-+-+-+-+-+-+-+-+-+-+-+
|P| | | | |M| | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | |M| | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | |T| | |M| | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|M|M|M|M|M|M| | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+

---

No treasures

+-+-+-+-+-+-+-+-+-+-+-+-+-+
|P| | |M|M|M| | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | |M|M|M|M|M|M|M| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | |M| | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | |M|M|M|M| | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+

---

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

---

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

---

Back alley

+-+-+-+-+-+-+-+-+-+-+-+-+-+
|P| | | | | | | | | | | |T|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | |M|M|M|M|M|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | |M|M|M|M|M|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | | |T|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | |M|M|M|M|M|
+-+-+-+-+-+-+-+-+-+-+-+-+-+

---

1x1

+-+
|P|
+-+

Cells

• Empty cases are empty
• M cells are mountains and cannot be walked on.
• T cells are treasures that need to be collected.

Goal

• You will generate a "path string" describing the movements needed to obtain all the treasures. No extraneous moves after treasures were all collected are allowed.
• Moves can be: "Left" "Right" "Up" "Down".
• Generating a move that'd result in an attempt to clib a mountain (M) or hit a wall (Out Of Bounds) is an error (it's not simply ignored).

General Rules

• Map must be read. (this is not a compression challenge, there are an infinite possible number of maps).
• There will always be one and only one player, P.
• There will always be a path to go get all the treasures, T.
• Map size may vary, but it'll always be at least 1x1.
• The AI starts at P, the player.
• There might not be a treasure on the map. In this case, you're allowed to exit any falsy value (that isn't a valid path)
• Your algorithm pick -- it needn't be the most efficient.
• You must solve it before the heat death of the universe
• It is not guaranteed you'll be able to access every non-mountain cell on the map. Just enough to fetch all treasures.
• The AI may see the whole map.
• Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
• Default Loopholes are forbidden.
• If possible, please add a link with a test for your code (i.e. TIO).
• Also, adding an explanation for your answer is highly recommended.

Format

Input

• You can decide to take inputs as a multi-line string with or without the ASCII separators I included (same for the space between cells)
• Passed via stdio or a function argument or on your program's stack(s)
• You can other identifiers instead of " ",M,P -- so long they are uniquely identifiable and not a separator (you need it specified in your answer)
• You can decide to take an 2-dimensional array, or matrix, or the equivalent in your language, with the cells, as [['P', ' ', ' '...], [...], [' ', ' ', 'T'...]...].
• You are also allowed to take an array of strings, such as ["P ...", ..., " T..."...].
• You are allowed to take the length as an extra input (width/height).

Output

• The output must look like "LLRRUUDD" (Left/Left/Right/Right/Up/Up/Down/Down)
• You can decide to intersperse spaces, newlines, etc, so long they don't mix with your instructions.
• You can other identifiers instead of L,R,U,D -- so long they are uniquely identifiable and not a separator (you need it specified in your answer)
• There might be different solutions (i.e. DR vs RD), it doesn't matter which you output in this case.

Scoring

This is a code-golf challenge.

Answer 1

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

Answer 2

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.

Answer 3

APL (Dyalog Extended), 132 bytes

Saved 16 bytes by having the function ouput 1 0,0 1,¯1 0,0 ¯1 instead of U,L,D,R. TIO link below decodes output back to letters.

I may write an explanation later, but most of the work is creating a graph in a format that the dfns path function likes, then using it to find successive shortest paths between the start and all treasures. Quite efficient, but because treasures are pathed left-to-right, top-to-bottom instead of being based on proximity, the answers are not optimal.

{z←×`/d←⍴⍵⋄g←z⍴⊂⍬⋄s t m←(⍸∘∊⍵=⊢)¨'PTM'⋄f←{(⍵∊m)∨0=⍺:⍬⋄g[⍺],←⍵}⋄h←(f`⍨,f)⋄⍬≡t⊣{2h`/⍵⊣2h`⌿⍵}x←d⍴⍳z:⍬⋄⊃,/⊃,/2-/¨{⍸x=⍵}¨¨2(g⌂path,)/s,t}

Try it online!

Answer 4

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.

Answer 5

Python 3, 766 622 bytes

def f(s,W,H):
 Z=enumerate;I=[("L",-1),("R",1),("D",1j),("U",-1j)];o="";P,M,T=map(lambda t:{x+y*1jfor y,l in Z(s)for x,c in Z(l)if c==t},'PMT');E=D={c:{t:0}for t,c in Z(T)}
 while len(E):
  E={}
  for m,N in[(c+d,D[c])for c in D for _,d in I if not c+d in M]:
   if 0<=m.real<W and 0<=m.imag<H:
    T={t:N[t]+1for t in N if not m in D or not t in D[m]}
    if any(T)or not m in D:
     E[m]=T
  for m in E:
   if m in D:
    D[m].update(E[m])
   else:
    D[m]=E[m]
 for m in P:
  if m in D:
   for g in D[m]:
    while D[m][g]:
     for i,d in I:
      if m+d in D and D[m+d][g]<D[m][g]:
       o+=i;m=m+d;break
 return o

Try it online!

Fairly certain after this that I will never win code-golf, but contributing because I enjoyed the exercise.

This version works by building a dictionary of reachable locations, with each entry being a dictionary whose keys are a unique ID for the treasure, and whose value is the shortest distance to that treasure. The code supports multiple values for P: for each one it outputs a path that collects the treasures. No optimization is attempted.. it picks the nearest treasure from its current location until all treasures are collected.