Vous avez été embauché comme assistant de recherche et vous avez demandé de créer un petit programme qui construira des labyrinthes de rats. La boîte de rat est toujours 62x22 et a une entrée (a) et une sortie (A) pour le rat, comme ceci (entrée 1):

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

Votre programme doit remplir la case avec des blocs (#) laissant un chemin pour le rat, comme ceci (sortie 1):

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

C'est facile vous pensez! Vous commencez à écrire un petit programme, plein de confiance. Cependant, le scientifique principal a eu une nouvelle idée - il veut que deux rats parcourent le labyrinthe en même temps. Le Dr Rattanshnorter explique qu'ils ont différentes portes et différentes sorties (entrée 2):

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

Les rats ont été entraînés à se déplacer directement à travers les intersections croisées mais les intersections en T les laissent désespérément confus et invalideront l'expérience. Vous commencez votre nouvelle tâche plus complexe lorsque le bon docteur explique une dernière exigence: les rats sont sauvages les uns envers les autres, donc s'ils se voient à tout moment, un combat de rats éclatera et vous serez tous les deux devant le comité d'éthique. Vous réalisez maintenant que votre programme devrait sortir un labyrinthe quelque chose comme ça (sortie 2):

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

Au moment où le rat B atteint l'intersection, le rat A voyagera dans le couloir pour sortir A et le combat de rats sera évité.

Règles:

• Votre programme doit lire (STDIN ou fichier) une entrée comme celles ci-dessus, et produire (STDOUT ou fichier) les mêmes données sauf que de nombreux espaces seront désormais des hachages (#). Vous pouvez remplacer n'importe quel caractère unique (tel que ;) au lieu de \ndans la chaîne d'entrée, mais la chaîne de sortie nécessite toujours des \ncaractères. MIS À JOUR

• Une voie de rat doit avoir une largeur de caractère, sauf pour les intersections croisées (chaque espace doit avoir zéro ou deux caractères orthogonalement adjacents #). Chaque rat doit avoir un chemin unique clair, sauf pour les intersections croisées. Aucune intersection en T n'est autorisée.

• Les rats sont libérés simultanément et se déplacent à un rythme constant. A aucun moment, deux rats ou plus ne devraient se voir (être dans la même colonne ou ligne sans# caractères entre les deux).

• Si aucune solution n'est possible (comme des points d'entrée adjacents), imprimez Impossible\net quittez.

• Les entrées et les sorties peuvent être de n'importe quel côté, mais elles ne seront jamais aux coins.

• Si une entrée et une sortie appariées sont adjacentes (par exemple:) ##aA##, le rat ne peut pas aller directement de aà A. Il doit y avoir une petite section de couloir de 2 espaces à l'intérieur de la zone du labyrinthe.

• Au tour où un rat atteint son point de sortie (ou à tout moment par la suite), il n'est plus visible pour les autres rats.

• Votre programme peut être conçu pour calculer des labyrinthes pour 1, 2, jusqu'à 26 rats.

• Les failles standard ne sont pas autorisées.

But:

Avec votre solution, indiquez combien de rats par labyrinthe (N) votre programme peut résoudre. Votre score est la longueur de votre code en octets divisée par ce nombre N.

Veuillez inclure un exemple de sortie dans votre réponse afin que nous puissions voir ce que votre programme produit.

Haskell, 26 rats?, ~ 5000 octets

Théoriquement, ce code devrait fonctionner pour n'importe quel nombre de rats, mais je n'offre aucune garantie qu'il se terminera avant la mort par la chaleur de l'univers. Il est basé sur un algorithme de retour en arrière qui essaie d'abord de suivre le chemin droit, puis de changer de chemin si le chemin ne fonctionne pas. Le nombre d'alternatives est exponentiel par rapport à la longueur du trajet et au nombre de rats.

Je n'ai pas encore pris la peine de jouer au golf, car il est si grand et que je veux d'abord le rendre plus rapide.

{-# 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)

Exemple de sortie, 6 rats:

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

Haskell, 1 rat, 681 caractères

Le problème peut être trivialement résolu pour tous les labyrinthes avec un seul rat. Ce code "fonctionne" également pour n'importe quel nombre de rats, mais ne suit aucune des contraintes sur les interactions entre plusieurs rats et chemins.

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)

Exemple de sortie:

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

Je prévois de prendre en charge de nombreux rats, j'ai donc écrit du code générique, mais je n'ai pas encore trouvé de bon algorithme pour cela.

• parse extrait une liste de toutes les entrées et sorties, avec leurs coordonnées
• rats prend cette liste et la convertit en paires de coordonnées pour chaque rat.
• bnds prend une coordonnée sur un bord et la déplace vers la coordonnée la plus proche à l'intérieur du labyrinthe.
• naive prend une position de début et de fin et renvoie un chemin simple entre elles.
• main remplace ensuite tous les espaces blancs qui ne se trouvent pas dans un chemin par '#'