24
\$\begingroup\$

You're a mouse. Your mouse friends have all been captured, and are unconscious and trapped in a maze that has only one entrance/exit. You happen to have a perfect map of the maze, so you can plot a solution to rush in and carry them all to safety. However, the maze is guarded with a security system that will trigger an alert if a threshold of 1000 is reached, causing you to be captured and fail your rescue mission.

From your previous investigations of the maze, each square you step (i.e., each horizontal or vertical movement -- mice can't move diagonally) adds 1 to the security system's counter. However, if you're carrying a weight (either a block of dynamite or an unconscious mouse friend), it instead adds 2 since it detects the additional pressure. The entrance/exit square doesn't have this security system, and so doesn't add to the counter.

You have an unlimited supply of dynamite that you've brought to the entrance, so you can simply blow up all the walls to free your friends. But you need to be cautious with doing so, since each explosion adds 50 to the counter from the concussive pressure. Additionally, you can only carry one thing at a time, either one mouse or one block of dynamite. Since each block of dynamite can only detonate one wall space, this means that if there are multiple walls in a row, you need to make an empty-handed trip back to the entrance to grab more.

Worked-through example

Suppose our maze looks like the following:

######
#M# E#
######

I'll use c for the counter. We start at the Entrance, move one square left while carrying dynamite, c=2. We detonate the dynamite to explode the wall, c=52. We move two squares left, empty-handed, to get c=54, and we're now standing on the mouse's square. We pick our friend up, and move 3 squares back to the Exit, but the last square doesn't count since it doesn't have any sensors, so that's only 2 squares with something on our back. That means that when we reach the exit with the final mouse, c=58, which is less than 1000, and therefore the mission succeeds.

Challenge

Given an input maze, output whether you, the mouse hero, can successfully rescue all trapped mice within the constraints outlined above, or whether the mission is a failure.

Input

  • A 2D maze in any acceptable format (multiline string, array of strings, etc.).
  • For this challenge, I will be using # for both the interior and exterior walls, M for the mouse friends, and E for the entrance.
  • The entrance will never be immediately adjacent to an interior wall (there will always be at least one space in which to move freely).
  • You can substitute any printable ASCII characters you wish so long as it's consistent. This does allow you to use two different symbols for interior walls vs. exterior walls, so long as you maintain consistency (e.g., if you choose to use @ for interior walls instead, and leave # for exterior, every interior wall must be @ and every exterior wall #).
  • The maze will always be completely bounded by walls, but is not necessarily rectangular. If desired, you can assume that the maze is padded with spaces to make rectangular input (optional).
  • The maze may have sections that are unreachable without dynamite.
  • You cannot dynamite the exterior walls of the maze.

Output

A truthy/falsey value. Truthy for "Yes, the mouse can rescue every other mouse" or Falsey for "No, the alarm system will be tripped."

The Rules

  • Either a full program or a function are acceptable.
  • Standard loopholes are forbidden.
  • This is so all usual golfing rules apply, and the shortest code (in bytes) wins.

Examples

Truthy examples, separated by blank lines.

#####
#M E#
#####
######
#M# E#
######
########
#E # M#
# # #
# # #
# #
########
#############################
# ## # # #
# M ## M # # #
# ## # M # E #
#M ## # # #
#############################
###############
#MMMMMMMMMMMMM#
#MMMMMMMMMMMMM#
#MMMMMMMMMMMMM#
#MMMMMMMMMM MM#
#MMMMMMMMMMMME#
###############

Falsey examples, separated by blank lines

#############################
#M ## ## ## #
# M ## M ## ## #
# ## ## M ## E #
#M ## ## ## #
#############################
#############################
 ########
 ########
 # # #
 # M # M#
 ########
 #####
 # M #
 #####
 #####
 #####
 #####
###################
# # # ## ## # # #
#M#M#M## E ##M#M#M#
# # # ## ## # # #
###################
#######
######
#####
####
# M#
####
###############
#MMMMMMMMMMMMM#
#MMMMMMMMMMMMM#
#MMMMMMMMMMMMM#
#MMMMMMMMMMMMM#
#MMMMMMMMMMMME#
###############
asked Sep 22, 2016 at 14:46
\$\endgroup\$
15
  • 3
    \$\begingroup\$ The mice were furious (mild spoiler) \$\endgroup\$ Commented Sep 22, 2016 at 14:51
  • 3
    \$\begingroup\$ @AlexA. Sorry that you had to learn it from a stranger on the Internet. ;-) \$\endgroup\$ Commented Sep 22, 2016 at 19:51
  • 3
    \$\begingroup\$ I suspect most people would have a hard time solving this with regular code, let alone golfing it. It's a great challenge that I unfortunately don't currently have time to work on. \$\endgroup\$ Commented Sep 23, 2016 at 0:13
  • 2
    \$\begingroup\$ Is it acceptable to have a different char for the external walls (as they're not destrcutible) ? \$\endgroup\$ Commented Sep 23, 2016 at 9:54
  • 2
    \$\begingroup\$ @Moshe Katz, sure you don't have time. You just don't wanna save the Mäuse. \$\endgroup\$ Commented Sep 28, 2016 at 18:53

2 Answers 2

21
\$\begingroup\$

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.

answered Oct 4, 2016 at 20:50
\$\endgroup\$
4
  • 3
    \$\begingroup\$ Ooo, intriguing. This is significantly shorter than I was expecting any answer to be. Can you add a little bit of explanation? I don't really grok Perl. \$\endgroup\$ Commented Oct 4, 2016 at 20:54
  • 3
    \$\begingroup\$ @TimmyD Ok, explanation added with enough details so that even a non perl programmer should get at least an impression of how it works \$\endgroup\$ Commented Oct 5, 2016 at 9:36
  • 1
    \$\begingroup\$ Very impressive! \$\endgroup\$ Commented Oct 5, 2016 at 13:02
  • \$\begingroup\$ Awesome golfing, that's really impressive... When I think I'm not that bad at golfing with Perl, I take a look at your golfings, and that feeling goes away pretty fast! \$\endgroup\$ Commented Oct 5, 2016 at 20:54
13
\$\begingroup\$

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} `,"e1ドルm",q],[`E${l} `,"e1ドルd",o],[`E${l}M`,"e1ドルc",q],[` ${l}E`,"m1ドルe",q],[` ${l}E`,"d1ドルe",o],[`M${l}E`,"c1ドルe",q],[/ m/,"m ",q],[/m /," m",q],[`m${l} `," 1ドルm",q],[` ${l}m`,"m1ドル ",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`," 1ドルm",n],[`d${l}#`,"m1ドル ",n],[/mM/," c",q],[/Mm/,"c ",q],[`M${l}m`,"c1ドル ",q],[`m${l}M`," 1ドルc",q],[/[mc]e/," E",p],[/e[mc]/,"E ",p],[`e${l}[mc]`,"E1ドル ",p],[`[mc]${l}e`," 1ドルE",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)

More readable version:

stateList = []
f=(s,regex="",replacement="",pressure=0,state=s.replace(regexp(regex),replacement),line=`((.|\n){${state.split("\n")[0].length}})`)=>{
 if (state in stateList || pressure > 999) return 1e3
 if (!/M/.test(state) && /E/.test(state)) return pressure
 stateList[state] = 0
 return [
 [/ E/,"me",pressure+1],
 [/ E/,"de",pressure+2],
 [/ME/,"ce",pressure+1],
 [/E /,"em",pressure+1],
 [/E /,"ed",pressure+2],
 [/EM/,"ec",pressure+1],
 [`E${line} `,"e1ドルm",pressure+1],
 [`E${line} `,"e1ドルd",pressure+2],
 [`E${line}M`,"e1ドルc",pressure+1],
 [` ${line}E`,"m1ドルe",pressure+1],
 [` ${line}E`,"d1ドルe",pressure+2],
 [`M${line}E`,"c1ドルe",pressure+1],
 [/ m/,"m ",pressure+1],
 [/m /," m",pressure+1],
 [`m${line} `," 1ドルm",pressure+1],
 [` ${line}m`,"m1ドル ",pressure+1],
 [/ ([dc])/,"1ドル ",pressure+2],
 [/([dc]) /," 1ドル",pressure+2],
 [`([dc])${line} `," 2ドル1ドル",pressure+2],
 [` ${line}([dc])`,"3ドル1ドル ",pressure+2],
 [/d#/,"m ",pressure+50],
 [/#d/," m",pressure+50],
 [`#${line}d`," 1ドルm",pressure+50],
 [`d${line}#`,"m1ドル ",pressure+50],
 [/mM/," c",pressure+1],
 [/Mm/,"c ",pressure+1],
 [`M${line}m`,"c1ドル ",pressure+1],
 [`m${line}M`," 1ドルc",pressure+1],
 [/[mc]e/," E",pressure],
 [/e[mc]/,"E ",pressure],
 [`e${line}[mc]`,"E1ドル ",pressure],
 [`[mc]${line}e`," 1ドルE",pressure]
 ].map(a=>f(state,...a)).reduce((a,b)=>a-b<0?a:b) //reduce used for support in more browsers.
}
s=>f(s)>1e3
answered Sep 24, 2016 at 22:11
\$\endgroup\$
12
  • \$\begingroup\$ Useless whitespaces at s in L|p > 999. \$\endgroup\$ Commented Sep 24, 2016 at 22:44
  • \$\begingroup\$ @TuukkaX Thanks for reminding me about that, the bytecount was for the version without the spaces already. \$\endgroup\$ Commented Sep 24, 2016 at 22:49
  • \$\begingroup\$ See if you can save bytes by wrapping the code in eval and replacing @ with 1ドル (not sure if this will work, but you write 1ドル a lot) \$\endgroup\$ Commented Sep 24, 2016 at 23:29
  • \$\begingroup\$ I think you could save a bunch by making f a one-liner: f=(...)=>s in L|p>999?1e3:!/M/.test(s,L[s]=0)&/E/.test(s)?p:Math.min(... \$\endgroup\$ Commented Sep 25, 2016 at 0:53
  • \$\begingroup\$ @Cyoce I use 1ドル 18 times, and .replace("@","1ドル") is 18 bytes. I don't see a way to pull it off. \$\endgroup\$ Commented Sep 25, 2016 at 0:56

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.