58

Seu desafio recebe uma entrada de um layout da prisão para determinar se algum dos presos pode escapar.

Entrada

A entrada pode estar em qualquer formato razoável, como uma sequência, matriz, matriz de matrizes etc. A entrada será composta por três caracteres, neste caso #, Pe espaço. A entrada não conterá necessariamente os três caracteres.

#: Uma parede
P: Um prisioneiro
espaço: um espaço vazio

Um exemplo de entrada será semelhante a:

#####
#   #
# P #
#   #
#####

Resultado

Um valor verdadeiro / falso de se a prisão é segura ou não. A prisão só é segura se puder conter todos os presos. Se qualquer prisioneiro puder escapar, não é seguro.

Um prisioneiro pode escapar se não estiver totalmente cercado por um muro. Uma junção diagonal é totalmente fechada.

Casos de teste

############# Truthy
# P #  P#   #
#   #   # P #
#############

############# Truthy
# P    P    #
#   #   # P #
#############

############# Falsey
# P #  P#   #
#   #   # P #
########## ##

####          Truthy
#   #
 #   #
  # P ####
  ####

P             Falsey

###           Falsey
# #
# #
### P

code-golf ascii-art decision-problem grid path-finding TheLethalCoder
fonte

8

Sinto que isso é uma duplicata ou pelo menos um desafio semelhante. Bom desafio de qualquer maneira.

John Dvorak

2

@JanDvorak Pode ser, mas com meu Google Fu limitado, não consegui encontrar uma duplicata.

TheLethalCoder

2

relacionado (Preencha uma grade em 2D)

Esolanging Fruit

3

Seria bom ter exemplos de Falsey, nos quais os movimentos horizontal e vertical são necessários para escapar.

xnor

2

@tfbninja Não é realmente uma duplicata. Aquele pede para tentar extrapolar o programa dos dados fornecidos para determinar se a palavra está na caixa. Este é um floodfill BFS para verificar se há espaços não fechados mantendo valores marcados.

HyperNeutrino

54

Caracóis , 13 bytes

!(t\P(o\ ),o~

Experimente online!

Imprime 0para prisões inseguras e o tamanho da caixa delimitadora da entrada para prisões seguras.

A idéia é garantir que não possamos encontrar um caminho de uma Pcélula para fora dos limites ( ~) movendo-se apenas ortogonalmente ( o) pelos espaços. O té um teletransporte para que, independentemente de onde tentemos a partida, tente todas as posições iniciais possíveis para encontrar a P.

Martin Ender
fonte

23

A ferramenta certa.

Jonathan Allan

16

C # (.NET Core) , 485 480 474 470 421 408 bytes

A ferramenta e abordagem absolutamente erradas, mas mesmo assim ...

7 bytes (e mais) salvos com as dicas úteis do TheLethalCoder.
4 bytes salvos retornando um número inteiro.
Mais 4 bytes salvos graças (mais uma vez) ao TheLethalCoder, substituindo ' 'por 32nas comparações.
MUITOS bytes salvos refatorando o código.
Mais 13 bytes graças a (adivinhem quem?) TheLethalCoder. :) Eu continuo esquecendo suas dicas e ele continua me lembrando delas.

m=>{var p='P';int a=m.Length,b=m[0].Length,i=0,j,x,y;var c=new System.Collections.Stack();for(;i<a;i++)for(j=0;j<b;j++)if(m[i][j]==p)c.Push(new[]{i,j});while(c.Count>0){var t=(int[])c.Pop();x=t[0];y=t[1];if(x<1|x>a-2|y<1|y>b-2)return 0;foreach(var v in new[]{-1,1}){var z=x>0&x<a-1&y>0&y<b-1;if(z&m[x+v][y]==32){m[x][y]=p;c.Push(new[]{x+v,y});}if(z&m[x][y+v]==32){m[x][y]=p;c.Push(new[]{x,y+v});}}}return 1;}

Experimente online!

Basicamente, expanda as posições dos Ps sempre que houver um espaço em branco até atingir (ou não) a borda do layout.

Algumas licenças:

Eu uso a char[][]como entrada para o layout.
Retorna 0como inseguro e 1seguro.

Charlie
fonte

Você não pode fornecer informações adicionais para a função e assumir as dimensões ... A menos que você encontre uma meta post para me convencer do contrário.

TheLethalCoder

1>0e 1<0são mais curtos que truee false.

TheLethalCoder

11

Pode ==0se tornar <1? Você tem pelo menos 1 byte de espaço em branco irrelevante. Você pode remover os new[]? (Nem sempre funciona, mas às vezes gosta de int[] n = {1,2,3};).

TheLethalCoder

11

{m[x][y]= p; c.Push(new[]->{m[x][y]=p;c.Push(new[]

TheLethalCoder

11

Você pode comparar chars de ints então eu acredito que você pode substituir as ==' 'de ==32bytes para salvar. Você também deve fazer isso em comparações semelhantes.

TheLethalCoder

15

Perl 5 , 69 bytes

-10 bytes graças a @Grimy .

-2 bytes graças a @Neil .

77 bytes de código + -p0sinalizadores.

/
/;$_=s/(P| )(.{@{-}})?(?!\1)(?1)/P$2P/s?redo:!/\A.*P|P.*\Z|^P|P$/m

Experimente online!

Algumas breves explicações:
A idéia é colocar um Plugar onde os prisioneiros possam ir. Se houver algum Pna primeira / última linha, ou na primeira / última coluna, os presos podem ir até lá e fugir, o que significa que a prisão não é segura.
s/(P| )(.{@{-}})?(?!\1)(?1)/P$2P/ssubstitui um espaço à direita de ou abaixo de a Ppor a P, ou um espaço à esquerda ou em cima de a P.
Por fim, /\A.*P|P.*\Z|^P|P$/mverifica se uma linha começa ou termina com a Pou se existe uma Pna primeira ou na última linha.

dada
fonte

abordagem legal usando regexps! (mas provavelmente muito caro quando o espaço cresce)

Olivier Dulac

Na verdade, não é que ineficiente. Em particular, não requer muito retorno, não existe *ou +, a correspondência mais longa que pode ser feita é o tamanho de uma linha ... Agora, é claro, se você comparar com uma abordagem mais manual, baseada em matrizes, por exemplo , sim, é bastante ineficiente!

Dada

11

Bytes -6 por fusão das duas substituições: s/P(.{@{-}})? | (.{@{-}})?P/P$1$2P/s.

Grimmy

11

-2 bytes de golfe a substituição resultante da fusão: s/(P| )(.{@{-}})?(?!\1)(?1)/P$2P/s.

Grimmy

2

@ Grimy muito bom golfe do regex! Obrigado :)

Dada

7

JavaScript (ES6), 134 133 bytes

Recebe a entrada como uma matriz de matrizes de caracteres. Devoluções 0(inseguras) ou 1(seguras).

f=a=>a.map((r,y)=>r.map((c,x)=>c>'O'&&[-1,1,0,0].map((X,i)=>(R=a[y+1-'1102'[i]])&&R[X+=x]?R[X]<'!'?R[o=2,X]=c:0:o=0)),o=1)|o&2?f(a):o

Casos de teste

Mostrar snippet de código

f=a=>a.map((r,y)=>r.map((c,x)=>c>'O'&&[-1,1,0,0].map((X,i)=>(R=a[y+1-'1102'[i]])&&R[X+=x]?R[X]<'!'?R[o=2,X]=c:0:o=0)),o=1)|o&2?f(a):o

console.log(f([
  [...'#############'],
  [...'# P #  P#   #'],
  [...'#   #   # P #'],
  [...'#############']
]))

console.log(f([
  [...'#############'],
  [...'# P    P    #'],
  [...'#   #   # P #'],
  [...'#############']
]))

console.log(f([
  [...'#############'],
  [...'# P #  P#   #'],
  [...'#   #   # P #'],
  [...'########## ##']
]))

console.log(f([
  [...'####'],
  [...'#   #'],
  [...' #   #'],
  [...'  # P ####'],
  [...'  ####']
]))

console.log(f([
  [...'P']
]))

console.log(f([
  [...'###'],
  [...'# #'],
  [...'# #'],
  [...'### P']
]))

Expandir snippet

Arnauld
fonte

Os &&s podem ser apenas &?

TheLethalCoder

@TheLethalCoder Não é o primeiro, mas o segundo pode ser substituído por |. Obrigado!

precisa

Não sabia que o operador de propagação trabalhava em strings. Legal!

aebabis

6

JavaScript (ES6), 121 bytes

f=s=>s==(s=s.replace(eval('/( |P)([^]{'+s.search`
`+'})?(?!\\1)[ P]/'),'P$2P'))?!/^.*P|P.*$/.test(s)&!/^P|P$/m.test(s):f(s)

Recebe a entrada como uma string retangular delimitada por nova linha. Retorna 0 para inseguro e 1 para seguro. Com base na minha resposta para Detectar castelos fracassados , embora fosse mais eficiente testar um prisioneiro escapado a cada passo, em vez de eles terminarem de explorar a prisão.

Neil
fonte

2

Oitava, 64 55 bytes

@(a,z=padarray(a,[1 1]))~nnz(bwfill(z==35,1,1,4)&z>35);

Experimente online!

ou

Verifique todos os casos de teste!

Explicação:

z=padarray(a,[1 1])       %add a boundary(of 0s) around the scene
F = bwfill(z==35,1,1,4)   %flood fill the prison starting from the boundary
~nnz(F&z>35);             %if position of at least a prisoner  is filled then the prison is not secure

rahnema1
fonte

2

APL (Dyalog Classic) , 40 bytes

{⊃2≠(××{1⊃⌈/⍵,⍉⍵}⌺3 3)⍣≡(⌽1,⍉)⍣4⊢'# '⍳⍵}

Experimente online!

'# '⍳⍵codificar '#', ' ', 'P'como 0 1 2

(⌽1,⍉)⍣4 surround com 1s

(××{1⊃⌈/⍵,⍉⍵}⌺3 3)⍣≡ número máximo de vizinhos de preenchimento de células diferentes de zero

⊃2≠ não temos um 2 no canto superior esquerdo?

ngn
fonte

1

Stax , 35 bytes ^CP437

ä¬my■╡╤▲l@┤êr*⌠\¶ƒläå─▄¶√¿ [Uy⌠Só4↔

Experimente online!

Certamente, uma linguagem de golfe sem um interno para lidar com a localização de caminhos também pode fazer isso!

Explicação

Usa o formato descompactado para explicar.

zLz]Y+Mys+y+{{{" P|P ""PP"Rm}Y!My!Mgphh' =
zLz]Y+Mys+y+                                  Surround the original matrix with four borders of whitespaces
            {                      gp         Iterate until a fixed point is found, return the single fixed point
             {              }Y!               Store the block in register Y and execute it
              {" P|P ""PP"Rm                  For each row, flood every space adjacent to a P with P.
                               My!            Transpose the matrix and do the flooding again
                                     hh' =    The final matrix has a space on the upper left corner that has not been flooded by P

Weijun Zhou
fonte

1

SmileBASIC, 154 146 bytes

Eu esperava que uma resposta usando preenchimento fosse mais curta que isso.

DEF S P
FOR J=0TO 1X=1Y=1FOR I=0TO LEN(P)-1GPSET X,Y,-(P[I]=="#")GPAINT X,Y,-1,-J*(P[I]>@A)X=X*(P[I]>"31")+1INC Y,X<2NEXT
NEXT?!GSPOIT(0,0)GCLS
END

Substitua 31pelo caractere ASCII correspondente.

12Me21
fonte

Minha prisão está segura?

Respostas:

Caracóis , 13 bytes

C # (.NET Core) , 485 480 474 470 421 408 bytes

Perl 5 , 69 bytes

JavaScript (ES6), 134 133 bytes

Casos de teste

JavaScript (ES6), 121 bytes

Oitava, 64 55 bytes

APL (Dyalog Classic) , 40 bytes

Stax , 35 bytes ^CP437

Explicação

SmileBASIC, 154 146 bytes

Minha prisão está segura?

Respostas:

Caracóis , 13 bytes

C # (.NET Core) , 485 480 474 470 421 408 bytes

Perl 5 , 69 bytes

JavaScript (ES6), 134 133 bytes

Casos de teste

JavaScript (ES6), 121 bytes

Oitava, 64 55 bytes

APL (Dyalog Classic) , 40 bytes

Stax , 35 bytes CP437

Explicação

SmileBASIC, 154 146 bytes

Stax , 35 bytes ^CP437