You have been hired as a research assistant, and asked to create a small program that will build rat mazes. The rat box is always 62x22 and has an entrance (a) and exit (A) for the rat, like this (input 1):

#######a######################################################
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#################################################A############

Your program must fill the box with blocks (#) leaving a path for the rat, like this (output 1):

#######a######################################################
####### ######################################################
####### ######################################################
####### ######################################################
####### ######################################################
#######                                           ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
#################################################A############

This is easy you think! You start writing a small program, full of confidence. However, the Principle Scientist has had a new idea -- he wants two rats to navigate the maze at the same time. Dr Rattanshnorter explains that they have different doors and different exits (input 2):

#b#####a######################################################
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            #
#                                                            B
#                                                            #
#################################################A############

The rats have been trained to move straight through cross intersections but T-intersections leave them hopelessly confused and will invalidate the experiment. You start on your new more complex task when the good Doctor explains one final requirement: the rats are savage to each other so if they see each other at any point, a rat fight will break out and you will both be before the ethics board. You now realise your program should output a maze something like this (output 2):

#b#####a######################################################
# ##### ######################################################
# ##### ######################################################
# ##### #######################################           ####
# ##### ####################################### ######### ####
# #####                                           ####### ####
# ############################################# # ####### ####
# ############################################# # ####### ####
# ############################################# # ####### ####
# ############################################# # ####### ####
#                                               # ####### ####
################################################# ####### ####
################################################# ####### ####
################################################# ####### ####
################################################# ####### ####
################################################# ####### ####
################################################# ####### ####
################################################# ####### ####
################################################# ####### ####
################################################# #######    B
################################################# ############
#################################################A############

By the time rat B reaches the intersection, rat A will be travelling down the corridor to exit A and the rat fight will be avoided.

Rules:

Your program should read in (STDIN or file) an input like those above, and output (STDOUT or file) the same data except many spaces will now be hashes (#). You may substitute any single character (such as ;) instead of \n in the input string but the output string still requires \n characters. UPDATED
A rat pathway must be one character width wide, except for cross intersections (every space must have zero or two orthogonally adjacent # characters). Each rat must have a clear single path, except for cross intersections. No T-intersections are allowed.
Rats are released simultaneously and move at a constant rate. At no time should two or more rats see each other (be in the same column or row without one of more # characters in between).
If no solution is possible (such as adjacent entrance points), print Impossible\n and exit.
Entrances and exits can be on any sides, however they will never be on the corners.
If a matched entrance and exit are adjacent (eg: ##aA##), the rat cannot go directly from a to A. There must be a small 2 space corridor section inside the maze area.
On the turn where a rat reaches its exit point (or any time after that), it is no longer visible to other rats.
Your program may be designed to compute mazes for 1, 2, up to 26 rats.
Standard loopholes are disallowed.

Score:

With your solution, nominate how many rats per maze (N) your program can solve. Your score is your code length in bytes divided by this number N.

Please include a sample output in your answer so we can see what your program produces.

Logic Knight

Posted 2015-04-03T06:52:52.290

Reputation: 6 622

Is the only difference in the possible inputs the locations of a,A,b,B? – xnor – 2015-04-03T07:09:27.783

For the 2 rat version, yes. If your program is designed for up to 3 rats, you would need to cope with all possible locations of a,b,c,A,B,C. – Logic Knight – 2015-04-03T07:21:59.300

Are T intersections allowed if the rat will only walk alongside the horizontal part of the T? – orlp – 2015-04-03T07:38:44.317

No, these rats are easily confused. Only straight paths, elbow bends, and cross roads are allowed. – Logic Knight – 2015-04-03T07:49:03.507

@CarpetPython Can an entrance/exit be anywhere along the edge of the maze? Can they be adjacent? – orlp – 2015-04-03T07:50:07.943

As mentioned in the rules above, they may be adjacent and therefore that input is not solvable. Entrance/exits will never be on the corners though. – Logic Knight – 2015-04-03T08:11:21.187

I meant adjacent entrance and exit, like this: https://gist.github.com/orlp/f986056d28eb0a4a3a9e

– orlp – 2015-04-03T08:16:47.393

Oh, I get it. It is a valid input to have 'aA' adjacent like that, and is trivial to solve. An input with 'ab' together is valid but impossible to solve (so output Impossible). – Logic Knight – 2015-04-03T08:24:39.247

@CarpetPython Can open space be seen a series of cross intersections? Example: https://gist.github.com/orlp/f986056d28eb0a4a3a9e

– orlp – 2015-04-03T08:43:15.787

Please note the updated rule 2 above. Rat paths must be single character width. – Logic Knight – 2015-04-03T08:46:07.183

@CarpetPython It doesn't say that. It says there must be zero or 2 orthogonal characters - a cross intersection for example is an invalidation of 'single character width'. – orlp – 2015-04-03T08:47:46.747

Mmmm. I will try to make that rule more clear. – Logic Knight – 2015-04-03T08:51:02.873

@CarpetPython Can rats move along other rats' exits and ignore them? Example. Or are those unsolvable? What about cases where there are 3 adjacent exits?

– orlp – 2015-04-03T13:03:38.370

Yes, rats will only use their own exit, and ignore others. Your example solution looks ok. Three adjacent exits should be ok in principle, but I can't see how it could still follow the 2 or 0 # per space rule. – Logic Knight – 2015-04-03T13:45:54.057

Can I output a maze with sparse walls? http://pastebin.com/hRxud3cX for example, no rat ever encounters a three-way junction; its just that most of the spaces they pass through are four-way junctions.

– AJMansfield – 2015-04-03T15:01:47.060

@AJMansfield, please rule 2 above: "A rat pathway must be one character width wide, except for cross intersections (every space must have zero or two orthogonally adjacent # characters). Each rat must have a clear single path, except for cross intersections.". This would mean that sparse layouts are not valid solutions. – Logic Knight – 2015-04-03T16:25:02.910

@CarpetPython I would interpret that wording to mean that they are valid, because every rat's path is one character wide, except at cross intersections, because most of the rat's path is through cross intersections. If that is your intent, you need to reword it to express that idea. Something like "any space that is not used by a rat as a path must have a wall in it", although that is a but cumbersome. – AJMansfield – 2015-04-03T16:33:25.350

@CarpetPython But I strongly disagree that such solutions should be invalid anyway. I think that sparse solutions should be allowed. Deriving a non-sparse solution from a sparse one would be a trivial operation, but would mean that programs that arrive at their solutions by placing things in a sparse arrangement would need to include additional code to thicken the solution. – AJMansfield – 2015-04-03T16:40:30.697

I can see your point AJ, but I decided on the corridor requirement early when I designed this challenge. There are several good reasons to limit paths to corridors, not the least of which is visual validation. May I suggest a statement at the end like for xy in grid: cell[xy]='#' if xy not in paths to fill in non-path cells? I hope this limitation will not put you off this challenge. I look forward to seeing your solution. – Logic Knight – 2015-04-03T17:15:35.227

@CarpetPython If the algorithm I'm playing with pans out the way I think it will, although it might not work at all... – AJMansfield – 2015-04-04T11:57:29.490

@CarpetPython If the entrance is adjacent to the exit, do you need any path at all, or can the rat go straight from the entrance to the exit? ##aA## – Hjulle – 2015-04-05T10:49:44.710

@Hjulle, good question. The rat will need some corridor. They cannot go from a to A directly. – Logic Knight – 2015-04-05T12:03:41.297

@CarpetPython Would ##aA##\n## ##\n###### be a valid solution then, or is it unsolveable? – Hjulle – 2015-04-05T12:05:38.100

The only valid solution would be ##aA##\n##..##\n###### (note the 2 space corridor shown as .. here) as the "zero or 2 # per space" rule would block any other option. – Logic Knight – 2015-04-05T12:14:49.647

@CarpetPython Can rats see other rats that have already exited from the maze? – Hjulle – 2015-04-06T15:14:38.693

No. Once a rat has reached its exit place, no other rats can see it (maybe it drops down a chute into its own cage). – Logic Knight – 2015-04-06T17:12:43.330

For javascript in a browser, stdin equivalent is usually 'prompt()', but it does not work for multiline strings. May I write a function with a string (multiline) parameter? – edc65 – 2015-04-07T08:53:05.697

If I add "you may substitute any single character (such as ;) instead of \n in the input string.", would this solve the problem? – Logic Knight – 2015-04-07T09:03:56.417

Are you sure that this can be solved in polynomial time in general? My strategy is probably not the best, but just going 2 steps with 6 rats leads to 46656 possibilities. – Hjulle – 2015-04-08T00:58:28.990

I have made no promises or predictions on the algorithmic complexity of this puzzle. I tend to make my challenges complex enough (see questions in my profile) that brute force search is not practical. You usually need clever optimisations to make a good answer. – Logic Knight – 2015-04-08T05:09:09.157

Answers

Haskell, 26 rats?, ~5000 bytes

Theoretically, this code should work for any number of rats, but I offer no warranty that it will terminate before the heat death of the universe. It is based on a backtracking algorithm which tries to go the straight path first, and then switch path if the path doesn't work. The number of alternatives is exponential with respect to the length of the path and the number of rats.

I haven't bothered to golf it yet, since it's so large, and since I want to make it faster first.

{-# LANGUAGE FlexibleContexts #-}
module Main (main) where

import Control.Lens
import Control.Monad
import Data.Char
import Data.Function
import Data.List
import Data.Maybe

type Pos = (Int,Int)
type Path = [Pos]
type Maze = String
type Input = [(Pos,Char)]
type MazeState = [(Path,Path)]

type ChoiceMonad a = [a]


instance (Num a, Num b) => Num (a,b) where
  (x,y)+(x',y')=(x+x',y+y')
  (x,y)-(x',y')=(x-x',y-y')
  fromInteger n = (fromInteger n,fromInteger n)


parseMaze :: Maze -> Input
parseMaze maze = maze ^@.. inner . filtered (`notElem` "# ")

inner :: IndexedTraversal' Pos Maze Char
inner = lined <.> traversed

main :: IO ()
main = do
    maze <- readFile "Sample2.in"
    putStrLn $ solveAndShow maze

fillMaze :: Maze -> Maze
fillMaze = inner.filtered(==' ').~'#'

updateMaze :: Path -> Maze -> Maze
updateMaze path = inner.indices (`elem` path).filtered(=='#') .~ ' '

isDone :: MazeState -> Bool
isDone = all (null . snd)

showMaze :: Maze -> MazeState -> Maze
showMaze maze path = updateMaze (fst =<< path) $ fillMaze maze

showSolution :: Maze -> ChoiceMonad MazeState -> String
showSolution _    []    = "Impossible"
showSolution maze (x:_) = showMaze maze x


stopCondition :: ChoiceMonad MazeState ->  Bool
stopCondition x = not $ null x || isDone (head x)

solveAndShow :: Maze -> String
solveAndShow maze = showSolution maze . solve $ mazeToState maze

solve :: ChoiceMonad MazeState -> ChoiceMonad MazeState
solve = fromJust . find (not.stopCondition) . iterate fullStep

mazeToState :: Maze -> ChoiceMonad MazeState
mazeToState maze = do
    let startsEnds = paths $ parseMaze maze
        return $ startsEnds & traverse.both %~ (:[])


fullStep :: ChoiceMonad MazeState -> ChoiceMonad MazeState
fullStep = (>>= stepAll)

stepAll :: MazeState -> ChoiceMonad MazeState
stepAll input = do
    pths <- mapM goStep input
    guard $ iall (checkVisible pths) $ map fst pths
    return $ pths
  where
    goStep :: (Path,Path) -> ChoiceMonad (Path,Path)
    goStep (curr:rest,[]) = return (curr:curr:rest,[])
    goStep (curr:these,end:ends)
       | distance curr end == 1 = return (end:curr:these,ends)

       | curr == end = goStep (curr:these,ends)
    goStep (path,end) = do
      next <- twoSteps (head end) path
      prev <- twoSteps next end
      return $ (next:path,prev:end)
    inMaze = inMazeWith input

    twoSteps :: Pos -> Path -> ChoiceMonad Pos
    twoSteps goal path = do
      next <- oneStep goal path inMaze
      guard $ not.null $ oneStep goal (next:path) (\x -> x==next || inMaze x)
      return next

checkVisible :: MazeState -> Int -> Path -> Bool
checkVisible _    _ [] = True
checkVisible pths i xs@(x:_) = checkBack && checkNow
  where
    nBack = 1 + visibleBackwards xs
    --checkBack = none (any (==x).take nBack .fst) pths
    checkBack = hasn't (folded.indices (/=i)._1.taking nBack folded.filtered (==x)) pths
    checkNow  = inone (\i' (x':_,_) -> (i/=i') && (==x') `any` take nBack xs ) pths

-- How long have you stayed on a line
visibleBackwards :: Path -> Int
visibleBackwards as = length . takeWhile ((==headDiff as) .headDiff). filter ((>=2).length) $ tails as
      where headDiff (a:a1:_) = a-a1
            headDiff x        = error $ "Bug: Too short list " ++ show x


inMazeWith :: [(Path, Path)] -> Pos -> Bool
inMazeWith = flip elem . concatMap (\x->snd x ++ fst x)

oneStep :: MonadPlus m => Pos -> Path -> (Pos -> Bool)  -> m Pos
oneStep end (curr:prev:_) inMaze =
  if distance curr end <= 1
     then return end
     else do
    let distance' :: Pos -> Double
        distance' x = fromIntegral (distance x end) + if curr - prev == x - curr then 0 else 0.4
    next <- msum . map return $ sortBy (compare`on`distance') $ neighbors curr

    -- Don't go back
    guard $ next /= prev

    -- Stay in bounds
    guard $ isInBounds next

    let dir = (next - curr)
    let lr = neighbors next \\ [curr,next+dir,end]

    -- If next is blocked, check that the one after that is free
    if inMaze next
      then do
        guard $ not . (\x->(x/=end)&&inMaze x) $ next + dir
        -- Both sides should be blocked as well
        guard $ (==2). length . filter inMaze $ lr
      else do
        -- No neighbors if empty
        guard $ null . filter inMaze $ lr

    -- All neighbors of 'curr', including 'next'
    let neigh' = filter (\i -> inMaze i || i == next) $ neighbors curr
        -- should be an even number
        guard $ even $ length neigh'

    return next
oneStep _ [start] _ = return $ inBounds start
oneStep _ _ _ = error "Too short path given"


toBounds :: (Num a, Eq a) => (a,a) -> a -> a
toBounds (low, high) x
    | x == low  = x + 1
    | x == high = x - 1
    | otherwise = x

distance :: Pos -> Pos -> Int
distance (x1,y1) (x2,y2) = abs(x1-x2)+abs(y1-y2)

-- Moves a pos to the closest one inside the bounds
inBounds :: Pos -> Pos
inBounds = bimap (toBounds (0,21)) (toBounds (0,61))

isInBounds :: Pos -> Bool
isInBounds x = x == inBounds x

neighbors :: Pos -> [Pos]
neighbors pos = [ pos & l %~ p| l <- [_1,_2], p <- [succ,pred]]

paths :: Input -> [(Pos,Pos)]
paths pos = flip unfoldr 'a' $ \x ->
  do (y,_) <- find ((==x).snd) pos
     (z,_) <- find ((==toUpper x).snd) pos
     return ((y,z),succ x)

Sample output, 6 rats:

##c###B#####b#######C#######F######################f##########
##   #       #       #######                        ##########
####  ######## ###############################################
#####          ###############################################
##############################################################
##############################################################
##############################################################
##############################################################
##############################################################
##############################################################
##############################################################
##############################################################
##############################################################
##############################################################
#############       ##########################################
############# #####  #########################################
D             #    #     #####################################
##############  ## ##### #####################################
#########      #                 #############################
######### ###### # ##### ####### #############################
####      #      #     # #######                        ######
####E######a##########e#d##############################A######

Hjulle

Posted 2015-04-03T06:52:52.290

Reputation: 479

2When b gets to the intersection of e and b, is he not seen by e? b seems to get there at t = 11, which would put e still in that corridor. Am I missing something? – BrainSteel – 2015-04-07T05:43:50.037

@BrainSteel Yes, that is correct. My answer is invalid. I noted to myself previously that I needed to check for collisions "backwards in time" as well (after crossing other rats paths), but for some reason I decided that it wasn't needed. :P – Hjulle – 2015-04-07T10:02:27.917

@BrainSteel I believe I have fixed that bug now. – Hjulle – 2015-04-07T16:15:00.720

Haskell, 1 rat, 681 Characters

The problem can be trivially solved for all mazes with just one rat. This code also "works" for any number of rats, but doesn't follow any of the constraints on the interactions between multiple rats and paths.

module Main where
import Control.Lens
import Data.List(unfoldr,find)
import Data.Char(toUpper)
parse=(^@..lined<.>folded.filtered(`notElem`"# "))
main=interact$do i<-(naive=<<).rats.parse;(lined<.>traversed).filtered(==' ').indices (`notElem`i).~'#'
    naive(start,(ex,ey))=start':unfoldr go start' where
     start'=bnds start
     (ex',ey')=bnds(ex,ey)
     go(x,y)
      |(x,y)==(ex',ey')=Nothing
      |x== ex'=ok(x,y`t`ey')
      |otherwise=ok(x`t`ex',y)
     ok z=Just(z,z)
     t x y=if x>y then x-1 else x+1
    bnd(l,h)x |x==l=x+1 |x==h=x-1 |True=x
    bnds=bimap(bnd(0,21))(bnd(0,61))
    rats pos=(`unfoldr`'a')$ \x->
  do (y,_)<-find((==x).snd)pos
     (z,_)<-find((==toUpper x).snd)pos
     return((y,z),succ x)

Sample output:

#######a######################################################
####### ######################################################
####### ######################################################
####### ######################################################
####### ######################################################
####### ######################################################
####### ######################################################
####### ######################################################
####### ######################################################
####### ######################################################
####### ######################################################
####### ######################################################
####### ######################################################
####### ######################################################
####### ######################################################
####### ######################################################
####### ######################################################
####### ######################################################
####### ######################################################
####### ######################################################
#######                                           ############
#################################################A############

I'm planning to support many rats, so I wrote generic code, but I haven't found a good algorithm for that yet.

parse extracts a list of all entrances and exits, with their coordinates
rats takes that list and converts it to pairs of coordinates for each rat.
bnds takes a coordinate on an edge and moves it to the nearest coordinate inside the maze.
naive takes a start and end positions and returns a simple path between them.
main then replaces all the white space not in a path with '#'

Hjulle

Posted 2015-04-03T06:52:52.290

Reputation: 479

@edc65 "... constraints between multiple rats". This is an answer for just 1 rat, which is allowed according to the question. – Hjulle – 2015-04-07T12:18:33.493

OK my fault. Just thinking that for 1 rat it's a different challenge. I'm going to delete my previous comments – edc65 – 2015-04-07T13:26:38.203

Programs to build a rat maze

Rules:

Score:

Answers

Haskell, 26 rats?, ~5000 bytes

Haskell, 1 rat, 681 Characters