Sie wurden als wissenschaftlicher Mitarbeiter eingestellt und gebeten, ein kleines Programm für den Bau von Rattenlabyrinthen zu erstellen. Die Rattenbox ist immer 62x22 und hat einen Eingang (a) und einen Ausgang (A) für die Ratte, wie folgt (Eingang 1):

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

Ihr Programm muss die Box mit Blöcken (#) füllen und einen Pfad für die Ratte hinterlassen, wie folgt (Ausgabe 1):

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

Das ist einfach, denkst du! Sie schreiben ein kleines Programm voller Selbstvertrauen. Der Principle Scientist hat jedoch eine neue Idee: Er möchte, dass zwei Ratten gleichzeitig durch das Labyrinth navigieren. Dr. Rattanshnorter erklärt, dass sie unterschiedliche Türen und unterschiedliche Ausgänge haben (Eingang 2):

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

Die Ratten wurden darauf trainiert, sich gerade durch Kreuzungen zu bewegen, aber T-Kreuzungen lassen sie hoffnungslos verwirrt und machen das Experiment ungültig. Sie beginnen mit Ihrer neuen, komplexeren Aufgabe, wenn der gute Doktor eine letzte Anforderung erklärt: Die Ratten sind wild zueinander. Wenn sie sich also zu irgendeinem Zeitpunkt sehen, bricht ein Rattenkampf aus und Sie befinden sich beide vor der Ethikkommission. Sie erkennen jetzt, dass Ihr Programm ein Labyrinth wie das folgende ausgeben sollte (Ausgabe 2):

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

Wenn Ratte B die Kreuzung erreicht, fährt Ratte A den Korridor entlang bis zum Ausgang A und der Rattenkampf wird vermieden.

Regeln:

• Ihr Programm sollte eine Eingabe wie oben einlesen (STDIN oder Datei) und dieselben Daten ausgeben (STDOUT oder Datei), außer dass viele Leerzeichen jetzt als Hashes (#) dargestellt werden. Sie können jedes einzelne Zeichen (z. B. ;) anstelle \nder Eingabezeichenfolge einsetzen, die Ausgabezeichenfolge erfordert jedoch weiterhin \nZeichen. AKTUALISIERT

• Ein Rattenpfad muss mit Ausnahme von Kreuzungspunkten eine Zeichenbreite haben (jedes Leerzeichen muss null oder zwei orthogonal nebeneinander haben) # Zeichen enthalten). Jede Ratte muss einen freien Weg haben, mit Ausnahme von Kreuzungspunkten. Es sind keine T-Kreuzungen erlaubt.

• Die Ratten werden gleichzeitig freigesetzt und bewegen sich mit konstanter Geschwindigkeit. Zu keinem Zeitpunkt sollten sich zwei oder mehr Ratten sehen (in derselben Spalte oder Zeile ohne ein oder mehrere #dazwischenliegende Zeichen).

• Wenn keine Lösung möglich ist (z. B. benachbarte Eingangspunkte), drucken Sie Impossible\nund beenden Sie.

• Ein- und Ausgänge können an beliebigen Seiten sein, sie werden jedoch niemals an den Ecken sein.

• Wenn ein passender Ein- und Ausgang nebeneinander liegt (zB ##aA##:), kann die Ratte nicht direkt von anach gehen A. Innerhalb des Labyrinthbereichs muss sich ein kleiner Korridorabschnitt mit 2 Feldern befinden.

• In der Kurve, in der eine Ratte ihren Austrittspunkt erreicht (oder zu einem späteren Zeitpunkt), ist sie für andere Ratten nicht mehr sichtbar.

• Ihr Programm kann so konzipiert sein, dass Labyrinthe für 1, 2 bis 26 Ratten berechnet werden.

• Standardlücken sind nicht zulässig.

Ergebnis:

Nenne mit deiner Lösung, wie viele Ratten pro Labyrinth (N) dein Programm lösen kann. Ihre Punktzahl ist Ihre Codelänge in Bytes geteilt durch diese Zahl N.

Bitte fügen Sie Ihrer Antwort eine Beispielausgabe bei, damit wir sehen können, was Ihr Programm produziert.

Haskell, 26 Ratten, ~ 5000 Bytes

Theoretisch sollte dieser Code für eine beliebige Anzahl von Ratten funktionieren, aber ich gebe keine Garantie dafür, dass er vor dem Hitzetod des Universums endet. Es basiert auf einem Backtracking-Algorithmus, der versucht, zuerst den geraden Pfad zu verfolgen und dann den Pfad zu wechseln, wenn der Pfad nicht funktioniert. Die Anzahl der Alternativen ist in Bezug auf die Länge des Pfades und die Anzahl der Ratten exponentiell.

Ich habe mich noch nicht darum gekümmert, Golf zu spielen, da es so groß ist und ich es zuerst schneller machen möchte.

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

Probenausgabe, 6 Ratten:

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

Haskell, 1 Ratte, 681 Zeichen

Das Problem kann für alle Labyrinthe mit nur einer Ratte trivial gelöst werden. Dieser Code "funktioniert" auch für eine beliebige Anzahl von Ratten, befolgt jedoch keine der Einschränkungen bei der Interaktion zwischen mehreren Ratten und Pfaden.

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)

Beispielausgabe:

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

Ich plane, viele Ratten zu unterstützen, also habe ich allgemeinen Code geschrieben, aber ich habe noch keinen guten Algorithmus dafür gefunden.

• parse Extrahiert eine Liste aller Ein- und Ausgänge mit ihren Koordinaten
• rats Nimmt diese Liste und konvertiert sie in Koordinatenpaare für jede Ratte.
• bnds Nimmt eine Koordinate an einer Kante und verschiebt sie zur nächsten Koordinate im Labyrinth.
• naive nimmt eine Start- und eine Endposition ein und gibt einen einfachen Pfad zwischen ihnen zurück.
• main Ersetzt dann den gesamten Leerraum, der sich nicht in einem Pfad befindet, mit '#'