Code Golf: Решите лабиринт

Question

Вот интересная проблема для решения в минимальном количестве кода. Я ожидаю, что рекурсивные решения будут самыми популярными.

У нас есть лабиринт, который определен как отображение символов, где = является стеной, пространство представляет собой путь, + является отправной точкой, и # ваша конечная точка. Невероятно простой пример, как так:

==== 
+ = 
= == 
= # 
==== 

Вы можете написать программу, чтобы найти самый короткий путь для решения лабиринта в этом стиле, как мало коды, насколько это возможно?

Бонусные баллы, если они работают для всех входов лабиринта, например, с дорожкой, пересекающей себя или с огромным количеством ветвей. Программа должна иметь возможность работать на больших лабиринтах (например, 1024x1024 - 1 МБ), а также то, как вы проходите лабиринт программы, не имеет значения.

«Игрок» может перемещаться по диагонали. Входной лабиринт никогда не будет иметь диагонального прохода, поэтому ваш базовый набор движений будет вверх, вниз, влево, вправо. Движение по диагонали будет просто немного заглядывать вперед, чтобы определить, можно ли объединить вверх/вниз и влево/вправо.

Вывод должен быть самым лабиринтом с самым коротким путем, выделенным с использованием символа звездочки (*).

Answer 1

Python

387 символов

принимает входные данные из стандартного ввода.

import sys 
m,n,p=sys.stdin.readlines(),[],'+' 
R=lambda m:[r.replace(p,'*')for r in m] 
while'#'in`m`:n+=[R(m)[:r]+[R(m)[r][:c]+p+R(m)[r][c+1:]]+R(m)[r+1:]for r,c in[(r,c)for r,c in[map(sum,zip((m.index(filter(lambda i:p in i,m)[0]),[w.find(p)for w in m if p in w][0]),P))for P in zip((-1,0,1,0),(0,1,0,-1))]if 0<=r<len(m)and 0<=c<len(m[0])and m[r][c]in'# ']];m=n.pop(0) 
print''.join(R(m)) 

Answer 2

Работает на любом (фиксированном) лабиринте с минимальным количеством циклов процессора (при достаточно большом BFG2000). Размер источника не имеет значения, поскольку компилятор невероятно эффективен.

while curr.x != target.x and curr.y != target.y: 
    case: 
     target.x > curr.x : dx = 1 
     target.x < curr.x : dx = -1 
     else    : dx = 0 
    case: 
     target.y > curr.y : dy = 1 
     target.y < curr.y : dy = -1 
     else    : dy = 0 
    if cell[curr.x+dx,curr.y+dy] == wall: 
     destroy cell[curr.x+dx,curr.y+dy] with patented BFG2000 gun. 
    curr.x += dx 
    curr.y += dy 
survey shattered landscape 

Answer 3

F #, не очень короткий (72 непустых строки), но читаемый. Я немного изменил/отточил спецификацию; Я предполагаю, что оригинальный лабиринт - это прямоугольник, полностью окруженный стенами, я использую разные персонажи (которые не повреждают мои глаза), я допускаю ортогональные движения (не диагональные). Я попробовал только один образец лабиринта. За исключением ошибки об указателях x и y, это работало в первый раз, поэтому я ожидаю, что это правильно (я ничего не сделал, чтобы проверить его, кроме глазного яблока, решение на одном образце, который я ему дал).

open System 

[<Literal>] 
let WALL = '#' 
[<Literal>] 
let OPEN = ' ' 
[<Literal>] 
let START = '^' 
[<Literal>] 
let END = '$' 
[<Literal>] 
let WALK = '.' 

let sampleMaze = @"############### 
# # #  # 
# ^# # # ### # 
# # # # # # # 
#  # # # 
############ # 
# $  # 
###############" 

let lines = sampleMaze.Split([|'\r';'\n'|], StringSplitOptions.RemoveEmptyEntries) 
let width = lines |> Array.map (fun l -> l.Length) |> Array.max 
let height = lines.Length 
type BestInfo = (int * int) list * int // path to here, num steps 
let bestPathToHere : BestInfo option [,] = Array2D.create width height None 

let mutable startX = 0 
let mutable startY = 0 
for x in 0..width-1 do 
    for y in 0..height-1 do 
     if lines.[y].[x] = START then 
      startX <- x 
      startY <- y 
bestPathToHere.[startX,startY] <- Some([],0) 

let q = new System.Collections.Generic.Queue<_>() 
q.Enqueue((startX,startY)) 
let StepTo newX newY (path,count) = 
    match lines.[newY].[newX] with 
    | WALL ->() 
    | OPEN | START | END -> 
     match bestPathToHere.[newX,newY] with 
     | None -> 
      bestPathToHere.[newX,newY] <- Some((newX,newY)::path,count+1) 
      q.Enqueue((newX,newY)) 
     | Some(_,oldCount) when oldCount > count+1 -> 
      bestPathToHere.[newX,newY] <- Some((newX,newY)::path,count+1) 
      q.Enqueue((newX,newY)) 
     | _ ->() 
    | c -> failwith "unexpected maze char: '%c'" c 
while not(q.Count = 0) do 
    let x,y = q.Dequeue() 
    let (Some(path,count)) = bestPathToHere.[x,y] 
    StepTo (x+1) (y) (path,count) 
    StepTo (x) (y+1) (path,count) 
    StepTo (x-1) (y) (path,count) 
    StepTo (x) (y-1) (path,count) 

let mutable endX = 0 
let mutable endY = 0 
for x in 0..width-1 do 
    for y in 0..height-1 do 
     if lines.[y].[x] = END then 
      endX <- x 
      endY <- y 

printfn "Original maze:" 
printfn "%s" sampleMaze 
let bestPath, bestCount = bestPathToHere.[endX,endY].Value 
printfn "The best path takes %d steps." bestCount 
let resultMaze = Array2D.init width height (fun x y -> lines.[y].[x]) 
bestPath |> List.tl |> List.iter (fun (x,y) -> resultMaze.[x,y] <- WALK) 
for y in 0..height-1 do 
    for x in 0..width-1 do 
     printf "%c" resultMaze.[x,y] 
    printfn "" 

//Output: 
//Original maze: 
//############### 
//# # #  # 
//# ^# # # ### # 
//# # # # # # # 
//#  # # # 
//############ # 
//# $  # 
//############### 
//The best path takes 27 steps. 
//############### 
//# # #....... # 
//# ^# #.# ###. # 
//# .# #.# # #. # 
//# .....# #. # 
//############. # 
//# $....... # 
//############### 

Answer 4

я сделал такого рода вещи для собеседования один раз (это было предварительно интервью программирования вызов)

удалось заставить его работать в какой-то степени успеха, и это забавная проблема.