Вы были наняты в качестве научного сотрудника и попросили создать небольшую программу, которая будет создавать лабиринты для крыс. Крысиный ящик всегда 62х22 и имеет вход (а) и выход (А) для крысы, вот так (вход 1):

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

Ваша программа должна заполнить поле блоками (#), оставляя путь для крысы, вот так (вывод 1):

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

Это легко, вы думаете! Вы начинаете писать небольшую программу, полную уверенности. Однако у Принципиального ученого появилась новая идея - он хочет, чтобы две крысы одновременно перемещались по лабиринту. Доктор Раттаншнортер объясняет, что у них разные двери и разные выходы (вход 2):

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

Крыс обучали двигаться прямо через перекрестки, но Т-образные перекрестки оставляют их безнадежно запутанными и лишают законной силы эксперимент. Вы начинаете свою новую более сложную задачу, когда хороший Доктор объясняет одно последнее требование: крысы дикие друг с другом, поэтому, если они увидят друг друга в какой-то момент, начнется драка крыс, и вы оба окажетесь перед доской этики. Теперь вы понимаете, что ваша программа должна выводить лабиринт примерно так (вывод 2):

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

К тому времени, когда крыса B достигнет перекрестка, крыса A будет двигаться по коридору, чтобы выйти из A, и бой с крысой будет предотвращен.

Правила:

• Ваша программа должна прочитать (STDIN или файл) входные данные, подобные приведенным выше, и вывести (STDOUT или файл) те же данные, за исключением того, что многие пробелы теперь будут хешами (#). Вы можете заменить любой отдельный символ (например, ;) вместо \nвходной строки, но для выходной строки все еще требуются \nсимволы. ОБНОВЛЕНО

• Путь крысы должен быть шириной в один символ, за исключением перекрестных пересечений (каждый пробел должен иметь ноль или два соседних с ортогональными #символами символа). У каждой крысы должен быть четкий отдельный путь, за исключением перекрестных пересечений. Т-образные перекрестки не допускаются.

• Крысы выпускаются одновременно и движутся с постоянной скоростью. Никогда две и более крысы не должны видеть друг друга (находиться в одном столбце или строке без одного или нескольких #символов между ними).

• Если решение невозможно (например, смежные точки входа), распечатайте Impossible\nи выйдите.

• Входы и выходы могут быть с любой стороны, однако они никогда не будут на углах.

• Если совпадающие вход и выход находятся рядом (например:) ##aA##, крыса не может перейти непосредственно от aк A. Внутри лабиринта должен быть небольшой 2-х пространственный коридор.

• На ходу, когда крыса достигает своей точки выхода (или в любое время после этого), она больше не видна другим крысам.

• Ваша программа может быть рассчитана на вычисление лабиринтов для 1, 2, до 26 крыс.

• Стандартные лазейки запрещены.

Гол:

Используя ваше решение, укажите, сколько крыс на лабиринт (N) может решить ваша программа. Ваша оценка - это длина вашего кода в байтах, деленная на это число N.

Пожалуйста, включите пример вывода в ваш ответ, чтобы мы могли увидеть, что производит ваша программа.

Haskell, 26 крыс ?, ~ 5000 байт

Теоретически, этот код должен работать для любого количества крыс, но я не даю никаких гарантий, что он прекратит работу до тепловой смерти вселенной. Он основан на алгоритме обратного отслеживания, который сначала пытается пройти по прямому пути, а затем переключать путь, если путь не работает. Количество альтернатив экспоненциально по отношению к длине пути и количеству крыс.

Я еще не удосужился поиграть в гольф, потому что он такой большой, и с тех пор я хочу сделать его быстрее.

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

Пример вывода, 6 крыс:

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

Хаскелл, 1 крыса, 681 персонаж

Проблема может быть решена тривиально для всех лабиринтов с помощью одной крысы. Этот код также «работает» для любого количества крыс, но не соблюдает никаких ограничений на взаимодействие между несколькими крысами и путями.

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)

Пример вывода:

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

Я планирую поддерживать много крыс, поэтому я написал общий код, но пока не нашел хорошего алгоритма для этого.

• parse извлекает список всех входов и выходов, с их координатами
• rats берет этот список и преобразует его в пары координат для каждой крысы.
• bnds берет координату на ребре и перемещает ее к ближайшей координате внутри лабиринта.
• naive занимает начальную и конечную позиции и возвращает простой путь между ними.
• main затем заменяет все пробелы, не находящиеся на пути, на «#»