# Gotta Collect 'Em All

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

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

• Is the parsing tag really suitable if we're allowed to take input as a matrix? Also, allowing input as a matrix seems to conflict with Map must be parsed. – Arnauld Mar 18 at 12:14
• Feel free to edit tags. – Ven Mar 18 at 12:14
• Related – Kevin Cruijssen Mar 18 at 14:59
• @Ven I know. In my challenge the most optimal path has to be found from the entrance to the exit. In yours any one valid path should be output from the starting point through all treasures. I just added it as a related challenge for people to draw inspiration from, since both challenges require the path to be output and have backtracking involved. :) – Kevin Cruijssen Mar 18 at 15:07

# 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!

• Would love an explanation :-). – Ven Jun 4 at 11:19

# PHP, 385335307270 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.

• +1 for the "Is definitely more artificial than intelligent." xD And it may not be intelligent, but based on the run-time it's definitely fast. – Kevin Cruijssen Mar 20 at 10:49

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

 MPTLRUDEMPT1302. Any other characters should be considered to be prefixes, separators or postfixes.

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

• Can reduce it by 5 bytes by using e=enumerate, and adjusting 1 space after any(T) – ABridgeTooFar Mar 20 at 14:04
• You can often put an if statement and the line to execute on the same line e.g. if any(T)or not m in D:E[m]=T. – lirtosiast May 31 at 15:35