Zostałeś zatrudniony jako asystent naukowy i poproszony o stworzenie małego programu, który zbuduje labirynty szczurów. Pudełko szczura ma zawsze wymiary 62 x 22 i ma wejście (a) i wyjście (A) dla szczura, takie jak to (wejście 1):

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

Twój program musi wypełnić pole blokami (#) pozostawiając ścieżkę dla szczura, tak jak to (wynik 1):

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

To łatwe, myślisz! Zaczynasz pisać mały, pełen zaufania program. Jednak główny naukowiec wpadł na nowy pomysł - chce, aby dwa szczury poruszały się jednocześnie po labiryncie. Dr Rattanshnorter wyjaśnia, że ​​mają różne drzwi i różne wyjścia (wkład 2):

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

Szczury zostały wytrenowane, aby poruszać się prosto przez skrzyżowania, ale przecięcia w T pozostawiają je beznadziejnie zdezorientowane i unieważnią eksperyment. Zaczynasz od nowego, bardziej złożonego zadania, gdy dobry Doktor wyjaśnia jeden końcowy wymóg: szczury są wobec siebie dzikie, więc jeśli zobaczą się w dowolnym momencie, wybuchnie walka na szczurach i oboje staniecie przed komisją etyki. Teraz zdajesz sobie sprawę, że twój program powinien wypisać labirynt coś takiego (wynik 2):

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

Zanim szczur B dotrze do skrzyżowania, szczur A będzie podróżował korytarzem do wyjścia A i uniknie się walki ze szczurami.

Zasady:

• Twój program powinien wczytywać (STDIN lub plik) dane wejściowe takie jak te powyżej i wyprowadzać (STDOUT lub plik) te same dane, z tym wyjątkiem, że wiele spacji będzie teraz skrótami (#). Możesz zastąpić dowolny pojedynczy znak (np. ;) Zamiast \nw ciągu wejściowym, ale ciąg wyjściowy nadal wymaga \nznaków. AKTUALIZACJA

• Ścieżka szczura musi mieć szerokość jednego znaku, z wyjątkiem skrzyżowań (każde miejsce musi mieć zero lub dwa prostopadle sąsiadujące #znaki). Każdy szczur musi mieć wyraźną pojedynczą ścieżkę, z wyjątkiem skrzyżowań. Niedozwolone są przecięcia w kształcie litery T.

• Szczury są wypuszczane jednocześnie i poruszają się ze stałą prędkością. W żadnym momencie dwa lub więcej szczurów nie powinno się widzieć (znajdować się w tej samej kolumnie lub rzędzie bez jednego lub więcej #znaków pomiędzy nimi).

• Jeśli żadne rozwiązanie nie jest możliwe (takie jak sąsiednie punkty wejścia), wydrukuj Impossible\ni wyjdź.

• Wejścia i wyjścia mogą być po każdej stronie, jednak nigdy nie będą na rogach.

• Jeśli dopasowane wejście i wyjście sąsiadują ze sobą (np . ##aA##:), szczur nie może przejść bezpośrednio od ado A. W obszarze labiryntu musi znajdować się mały 2-kosmiczny korytarz.

• W turze, w której szczur osiąga punkt wyjścia (lub w dowolnym późniejszym czasie), nie jest już widoczny dla innych szczurów.

• Twój program może być zaprojektowany do obliczania labiryntów dla 1, 2, do 26 szczurów.

• Standardowe luki są niedozwolone.

Wynik:

Za pomocą swojego rozwiązania określ, ile szczurów na labirynt (N) może rozwiązać Twój program. Twój wynik to długość kodu w bajtach podzielona przez tę liczbę N.

W odpowiedzi podaj przykładowy wynik, abyśmy mogli zobaczyć, co produkuje Twój program.

Haskell, 26 szczurów ?, ~ 5000 bajtów

Teoretycznie ten kod powinien działać dla dowolnej liczby szczurów, ale nie oferuję żadnej gwarancji, że zakończy się przed śmiercią wszechświata. Opiera się na algorytmie cofania, który próbuje najpierw przejść prostą ścieżkę, a następnie zmienić ścieżkę, jeśli ścieżka nie działa. Liczba alternatyw jest wykładnicza w stosunku do długości ścieżki i liczby szczurów.

Jeszcze nie zadałem sobie trudu gry w golfa, ponieważ jest on tak duży i ponieważ chcę go najpierw przyspieszyć.

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

Próbka wyjściowa, 6 szczurów:

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

Haskell, 1 szczur, 681 znaków

Problem można rozwiązać w trywialny sposób dla wszystkich labiryntów z jednym szczurem. Ten kod „działa” także na dowolną liczbę szczurów, ale nie przestrzega żadnych ograniczeń interakcji między wieloma szczurami i ścieżkami.

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)

Przykładowe dane wyjściowe:

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

Planuję wspierać wiele szczurów, więc napisałem ogólny kod, ale nie znalazłem jeszcze dobrego algorytmu do tego.

• parse wyodrębnia listę wszystkich wejść i wyjść wraz z ich współrzędnymi
• rats bierze tę listę i konwertuje ją na pary współrzędnych dla każdego szczura.
• bnds bierze współrzędną na krawędzi i przesuwa ją do najbliższej współrzędnej w labiryncie.
• naive przyjmuje pozycje początkową i końcową i zwraca prostą ścieżkę między nimi.
• main następnie zastępuje całą białą spację nie na ścieżce znakiem „#”