A Mouse with Dynamite

Perl, 216 215 bytes

Includes +2 for -0p

Give input on STDIN. Use % for external walls, # for internal walls, 0 for empty spaces, 8 for mice and r for the starting position. The whole boards must be padded so it forms a rectangle. You can transform and run the examples as:

cat dynamite.txt | perl -p0e 's/.+/$a^=$&/egr;s//sprintf"%-*s",length$a,$&/eg;1while/\n/,s/^ *\K#|#(?= *$)|^ *.{@{-}}\K#|\A[^\n]*\K#|#(?=[^\n]*\n\z)|#(?=.{@{-}} *$)/%/sm;y/ EM/0x2/' | dynamite.pl

dynamite.pl:

#!/usr/bin/perl -0p
sub f{@a{@_}||=push@{$%+($&?$1?50:$&=~8?0:$&&"5"?2:1:0)},@_}f$_;for(@{$%}){f y/xr|/ytx/r;{f s/\pL\d/$&^(E&$&)x2/er}{f s/(q|s|y)#/$&^"\x01\x13"/er}my$o;{$\|=/x/>/2/;$o.="
"while s/.$/$o.=$&,""/meg}f$o}$%++>999|$\||redo}{

Replace the \xhh escapes for the claimed score.

The program can't realistically handle complex cases. In particular it can't handle any of the failure cases. This is because there are just too many different ways of blowing up the internal walls or picking up mice so the search becomes too wide and uses too much memory even though it's at least smart enough to never process the same state multiple times. The pressure limit has to be lowered to 100 or so for somewhat bearable runtimes and memory usage.

Explanation

I use the bit pattern of a character to represent the state of a field:

contains victim: 0000 0010
has hero:        0100 0000
carry dynamite   0000 0001
carry mouse      0000 0100
home             0000 1000
walkable         0001 0000 (not really needed but results in shorter regexes)
make printable   0010 0000
wall             0010 xxxx (bit patterns not very important,
permawall        0010 xxxx  just avoid letters and digits)

For example the hero (01000000) carrying dynamite (00000001) must be on a place he can walk (00010000) and we want all values to be printable ASCII (00100000). Taking the bitwise or of all these bitmasks gives 01110001 which is the ASCII code for q. In total this becomes::

p: hero                     r hero on victim
q: hero carrying dynamite   s hero carrying dynamite on victim
t: hero carrying mouse      v hero carrying mouse on victim

x : hero at home
y : hero at home carrying dynamite
| : hero at home carrying mouse

0: empty  without hero
8: home   without hero
2: victim without hero

%: permanent wall
#: normal wall

The program will only consider the hero moving to the right (the rotation explained later will take care of the other directions). The bitmasks were carefully chosen such that the hero is always represented by a letter and a place he can move to by a digit (except the hero at home carrying a victim, but again this is intentional so that the hero's only move will be to drop the victim). So a hero that can move forward is matched by /\pL\d/. The matched substring has to be modified so that the hero and what he is carrying is removed from the first character and added to the second one, which can be done with a bitwise xor with the same value for both characters. The xor value consists of the hero bit (01000000), the dynamite bit (00000001) and the carry mouse bit (00000100). Together they or to 01000101 which is ASCII E. So moving the hero becomes:

s/\pL\d/$&^(E&$&)x2/e

The hero can blow up a wall if he is standing right in front of it and is carrying dynamite (q, s or y). The hero will lose his dynamite (xor with 00000001) and the wall # will change to a passage 0 (xor with 00010011), so

s/(q|s|y)#/$&^"\x01\x13"/e

To handle the other directions the whole board is rotated (rotated board ends up in $o):

my$o;$o.="\n"while s/.$/$o.=$&,""/meg

Apart from moving the hero also has a number of other choices he can make:

When at home, pick up dynamite:                   x -> y
When on victim not carrying anything pick him up: r -> t
When at home carrying a victim, drop him off:     | -> x

This is done by

y/xr|/ytx/

The board is finished if the hero is at home carrying nothing (x) and there are no more victims to rescue (no 2). This can be conveniently tested using

/x/>/2/

Once the board is solved I want to remember this state and at the end print it. For that I carry the "is solved" flag in $\ and print that at the end of the program without printing $_, so

$\|=/x/>/2/  ...   }{

The states to be processed at pressure 0 are kept in @0, at pressure 1 on @1 etc. The current pressure is kept in $%. Using $n or something like it would be shorter but the code doesn't work if the variable isn't initialized to something because autovivification will otherwise change $n to an ARRAY reference.Looping over the states at a certain pressure is done using a for and not a map because with a for you can extend the array while it is still being looped over and will pick up the new elements. This is needed because the rotations and single field choices of the hero happen in 0 time and end up in the same pressure array. So the loop for a given pressure is done by

for(@{$%}){...}

This is repeated until the pressure reaches 1000 or a solution is found:

$%++>999|$\||redo

All that is left is adding newly discovered states to their respective pressure arrays. That will be done by subroutine f. We only want to add a state if it has not been seen yet. States that have been seen before are kept in %a so:

sub f{@a{@_}||=push@$n, @_}

$n represents the new pressure for a state. I will derive that from the state that the regex variables still have as a result of the hero's action leading to this call:

if $1 is set it was from s/(q|s|y)#/$&^"\x01\x13"/e which blows a wall -> 50
else if $& is set it was from s/\pL\d/$&^(E&$&)x2/e, so the hero moves.
    if $& contains 8 the hero went home -> 0
    else if the hero has carry bits (5) -> 2
    else                                   1
else ($& was not set) it was from y/xr|/ytx/r -> 0

This leads to the following formula for $n:

$%+($&?$1?50:$&=~8?0:$&&"5"?2:1:0)

All the substitutions get an r modifier so they return the changed state and leave the current state in $_ alone. f is then called on this changed state, so you get code like

f y/xr|/ytx/r;

Because the calculation of $n needs the regex variables they must default to unset in case the substitutions changes nothing (because the condition to trigger them is not fulfilled). I must also not pick up any regex variables from a previous loop. Therefore the substitutions are wrapped in {} blocks to save and restore the regex state. That's how you get statements like

{f s/\pL\d/$&^(E&$&)x2/er}

In particular the rotation is so wrapped so it calls f without regex variables and gets a pressure contribution of 0.

The only thing still to do is to prime @0 with the initial state at the start

f$_

This is in the main loop so it also tries to add $_ to later pressure arrays, but since the initial state will already be in %a nothing will happen.

Together all this basically finds the shortest solution using Dijkstra's algorithm. There is a potential problem though. The current code won't add a state if it is rediscovered with a lower pressure than the first discovery. I've not been able to construct a board that would trigger this, but have also been unable to prove it is impossible.

JavaScript, 863 834 785 781 bytes

Saved 29 bytes thanks to ETHproductions
Saved 53 bytes thanks to Jordan

L=[]
f=(S,r="",R="",p=0,s=S.replace(RegExp(r),R),l=`((.|\n){${s.split`
`[0].length}})`,q=p+1,o=p+2,n=p+50)=>s in L|p>999?1e3:!/M/.test(s,L[s]=0)&/E/.test(s)?p:Math.min(...[[/ E/,"me",q],[/ E/,"de",o],[/ME/,"ce",q],[/E /,"em",q],[/E /,"ed",o],[/EM/,"ec",q],[`E${l} `,"e$1m",q],[`E${l} `,"e$1d",o],[`E${l}M`,"e$1c",q],[` ${l}E`,"m$1e",q],[` ${l}E`,"d$1e",o],[`M${l}E`,"c$1e",q],[/ m/,"m ",q],[/m /," m",q],[`m${l} `," $1m",q],[` ${l}m`,"m$1 ",q],[/ (d|c)/,"$1 ",o],[/(d|c) /," $1",o],[`(d|c)${l} `," $2$1",o],[` ${l}(d|c)`,"$3$1 ",o],[/d#/,"m ",n],[/#d/," m",n],[`#${l}d`," $1m",n],[`d${l}#`,"m$1 ",n],[/mM/," c",q],[/Mm/,"c ",q],[`M${l}m`,"c$1 ",q],[`m${l}M`," $1c",q],[/[mc]e/," E",p],[/e[mc]/,"E ",p],[`e${l}[mc]`,"E$1 ",p],[`[mc]${l}e`," $1E",p]].map(a=>f(s,...a)))
F=s=>f(s)<1e3

Takes input as a multiline string.

This defines an anonymous function that uses a recursive function f to determine if you trip off the alarm before retrieving all the mice. f returns 1000 if the pressure is above 1000 (to avoid endless recursion), returns the pressure if there are no more mice to rescue and the mouse in the exit, and returns the minimum pressure of all possible moves from the current state otherwise. It uses an array L to keep track of already visited positions where L[pos]==0 if it is visited, and undefined if it isn't. This may not be necessary, but it prevents the mouse from doing useless moves and throwing recursion errors at the very least. (This does mean you should redefine L if you are testing this multiple times)

This uses the format in the question other than that it requires you to use a different character for the external walls. (Anything other than # MEmecd)

A Mouse with Dynamite

Perl, 216 215 bytes

Explanation

JavaScript, 863 834 785 781 bytes

Tags:

Maze

Path Finding

Code Golf

Related

Recent Posts