58

Votre défi reçoit une entrée d'une configuration de prison pour déterminer si l'un des prisonniers peut s'échapper.

Contribution

L'entrée peut être dans n'importe quel format raisonnable tel qu'une chaîne, un tableau, un tableau de tableaux, etc. L'entrée comprendra trois caractères, dans ce cas #, Pet un espace. L'entrée ne contiendra pas nécessairement les trois caractères.

#: Un mur
P: Un prisonnier
space: Un espace vide

Un exemple d'entrée ressemblera à ceci:

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

Sortie

Une valeur vérité / vérité pour déterminer si la prison est sécurisée ou non. La prison n'est sécurisée que si elle peut contenir tous les prisonniers. Si un prisonnier peut s'échapper, il n'est pas en sécurité.

Un prisonnier peut s'échapper s'il n'est pas complètement enfermé par un mur. Une jonction diagonale est entièrement fermée.

Cas de test

############# 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
la source

8

J'ai l'impression que c'est un doublon ou du moins un défi similaire. Bon défi quand même.

John Dvorak

2

@ JanDvorak C'est peut-être le cas, mais avec mon Google Fu limité, je n'ai pas pu trouver de doublon.

TheLethalCoder

2

liés (Remplir une grille 2D)

Esolanging Fruit

3

Il serait bon d’avoir des exemples de Falsey où des mouvements horizontaux et verticaux sont nécessaires pour s’échapper.

xnor

2

@tfbninja Pas vraiment un doublon. Celui-ci demande à ce que le programme extrapole à partir de données données pour déterminer si le mot est dans la boîte. Celui-ci est rempli par BFS pour voir s'il existe des espaces non fermés contenant des valeurs marquées.

HyperNeutrino

54

Escargots , 13 octets

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

Essayez-le en ligne!

Imprime 0pour les prisons non sécurisées et la taille de la boîte de sélection des entrées pour les prisons sécurisées.

L'idée est de s'assurer que nous ne pouvons pas trouver un chemin allant d'un a Pà une cellule hors-limite ( ~) se déplaçant uniquement orthogonalement ( o) dans des espaces. Le test un téléport de sorte que peu importe où nous essayons le match, il essaie toutes les positions de départ possibles pour trouver un P.

Martin Ender
la source

23

Le bon outil

Jonathan Allan

16

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

L'outil et l'approche absolument faux, mais néanmoins ...

7 octets (et plus) enregistrés avec les conseils utiles de TheLethalCoder.
4 octets enregistrés en renvoyant un entier.
Encore 4 octets sauvés grâce (encore une fois) à TheLethalCoder en remplaçant ' 'par 32dans les comparaisons.
Beaucoup d'octets enregistrés en refacturant le code.
13 octets supplémentaires grâce à (devinez qui?) TheLethalCoder. :) Je n'arrête pas d'oublier ses astuces et il ne cesse de me les rappeler.

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;}

Essayez-le en ligne!

En gros, j'agrandis les positions des P chaque fois qu'il y a un espace blanc jusqu'à ce qu'il atteigne (ou non) la bordure de la mise en page.

Quelques licences:

J'utilise un char[][]comme entrée pour la mise en page.
Retourne 0comme non sécurisé et 1sécurisé.

Charlie
la source

Vous ne pouvez pas prendre d’entrée supplémentaire dans la fonction pour pouvoir assumer les dimensions ... À moins que vous ne trouviez une méta-poste pour me persuader du contraire.

TheLethalCoder

1>0et 1<0sont plus courts que trueet false.

TheLethalCoder

1

Peut ==0devenir <1? Vous avez au moins 1 octet d'espaces non pertinents. Pouvez-vous enlever le new[]s? (Cela ne fonctionne pas toujours mais parfois comme dans int[] n = {1,2,3};).

TheLethalCoder

1

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

TheLethalCoder

1

Vous pouvez comparer chars à ints, alors je pense que vous pouvez remplacer ==' 'to ==32pour économiser des octets. Vous devriez pouvoir le faire sur des comparaisons similaires.

TheLethalCoder

15

Perl 5 , 69 octets

-10 octets grâce à @Grimy .

-2 octets grâce à @Neil .

77 octets de code + -p0drapeaux.

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

Essayez-le en ligne!

Quelques brèves explications:
L’idée est de mettre un Pendroit où les prisonniers peuvent aller. S'il y en a une Psur la première / dernière ligne, ou la première / dernière colonne, les prisonniers peuvent y aller et s'échapper, ce qui signifie que la prison n'est pas sécurisée.
s/(P| )(.{@{-}})?(?!\1)(?1)/P$2P/sremplace un espace à droite ou au-dessous de a Ppar un P, ou un espace à gauche ou au-dessus de a P.
Enfin, /\A.*P|P.*\Z|^P|P$/mvérifie si une ligne commence ou se termine par un Pou s'il y en a un Psur la première ou la dernière ligne.

Dada
la source

approche cool en utilisant les expressions rationnelles! (mais probablement très cher quand l'espace s'agrandit)

Olivier Dulac

En fait, ce n'est pas si inefficace. En particulier, cela ne nécessite pas beaucoup de retours en arrière, il n'y en a pas *ou +la correspondance la plus longue qu'il peut faire est la taille d'une ligne ... Maintenant, bien sûr, si vous comparez avec une approche plus manuelle, basée sur des tableaux par exemple alors oui c'est assez inefficace!

Dada

1

-6 octets en fusionnant les deux substitutions: s/P(.{@{-}})? | (.{@{-}})?P/P$1$2P/s.

Grimmy

1

-2 octets par la substitution du golf fusionné: s/(P| )(.{@{-}})?(?!\1)(?1)/P$2P/s.

Grimmy

2

@ Grimy très beau golf de la regex! Merci :)

Dada

7

JavaScript (ES6), 134 133 octets

Prend les entrées comme un tableau de tableaux de caractères. Retourne 0(non sécurisé) ou 1(sécurisé).

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

Cas de test

Afficher l'extrait de code

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']
]))

Développer l'extrait

Arnauld
la source

Le &&s peut juste être &?

TheLethalCoder

@TheLethalCoder Pas le premier, mais le second peut être remplacé par |. Merci!

Arnauld

Je ne savais pas que l'opérateur de diffusion travaillait sur des chaînes. Cool!

aebabis

6

JavaScript (ES6), 121 octets

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)

Prend l'entrée en tant que chaîne rectangulaire délimitée par des lignes. Renvoie 0 pour non sécurisé et 1 pour sécurisé. D'après ma réponse à Détecter les châteaux fugitifs , bien qu'il soit plus efficace de rechercher un prisonnier évadé à chaque étape, plutôt qu'une fois qu'ils ont fini d'explorer la prison.

Neil
la source

2

Octave, 64 55 octets

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

Essayez-le en ligne!

ou

Vérifiez tous les cas de test!

Explication:

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
la source

2

APL (Dyalog Classic) , 40 octets

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

Essayez-le en ligne!

'# '⍳⍵coder '#', ' ', 'P'comme 0 1 2

(⌽1,⍉)⍣4 entourer de 1

(××{1⊃⌈/⍵,⍉⍵}⌺3 3)⍣≡ Remplissage maximum de voisins de cellules non nulles

⊃2≠ N'avons-nous pas un 2 en haut à gauche?

ngn
la source

1

Stax , 35 octets ^CP437

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

Essayez-le en ligne!

Sûrement, une langue de golf sans interne pour gérer la recherche de parcours peut le faire aussi!

Explication

Utilise le format décompressé pour expliquer.

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
la source

1

SmileBASIC, 154 146 octets

J'espérais qu'une réponse utilisant le remplissage par inondation serait plus courte que cela.

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

Remplacez-le 31par le caractère ASCII correspondant.

12Me21
la source

Est-ce que ma prison est en sécurité?

Réponses:

Escargots , 13 octets

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

Perl 5 , 69 octets

JavaScript (ES6), 134 133 octets

Cas de test

JavaScript (ES6), 121 octets

Octave, 64 55 octets

APL (Dyalog Classic) , 40 octets

Stax , 35 octets ^CP437

Explication

SmileBASIC, 154 146 octets

Est-ce que ma prison est en sécurité?

Réponses:

Escargots , 13 octets

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

Perl 5 , 69 octets

JavaScript (ES6), 134 133 octets

Cas de test

JavaScript (ES6), 121 octets

Octave, 64 55 octets

APL (Dyalog Classic) , 40 octets

Stax , 35 octets CP437

Explication

SmileBASIC, 154 146 octets

Stax , 35 octets ^CP437