Este es un desafío de policías y ladrones como el golf . Este es el hilo conductor de la policía; El hilo de los ladrones está aquí.
Policías
Su tarea es definir un sistema de reescritura abstracta en el que la accesibilidad de una palabra a otra sea difícil de determinar. Preparará las siguientes cosas:
Un conjunto de símbolos, llamado alfabeto. (Puede utilizar caracteres Unicode para estos, pero no utilice espacios en blanco o símbolos que sean difíciles de distinguir entre sí).
Una cadena fuente compuesta de símbolos de su alfabeto.
Una cadena objetivo compuesta de símbolos de su alfabeto.
Un conjunto de reglas de reescritura utilizando caracteres de su alfabeto. (Consulte a continuación la definición de una regla de reescritura).
Una prueba que muestra si su cadena de origen se puede convertir en su cadena de destino mediante la aplicación sucesiva de sus reglas de reescritura. Esta prueba puede consistir en una secuencia real de pasos de reescritura, o una prueba matemática de que dicha secuencia debe existir, o una prueba matemática de que dicha secuencia no existe.
Publicará los primeros cuatro de estos, manteniendo la prueba en secreto; los ladrones intentarán descifrar su respuesta proporcionando su propia prueba de que su cadena de destino puede o no ser alcanzada desde su cadena de origen. Si su envío no se resuelve en dos semanas , puede marcarlo como seguro y editarlo en su prueba.
Las presentaciones se puntuarán de acuerdo con el número de caracteres en sus reglas de reescritura y sus cadenas de origen y destino, como se detalla a continuación. El ganador será la presentación sin descifrar con la puntuación más baja.
¿Qué es una regla de reescritura?
Una regla de reescritura es simplemente un par de cadenas en su alfabeto. (Cualquiera de estas cadenas puede estar vacía.) Una aplicación de una regla de reescritura consiste en encontrar una subcadena que sea igual a la primera cadena del par y reemplazarla por la segunda.
Un ejemplo debería aclarar esto:
Supongamos que el alfabeto es A, By C; la cadena de origen es " A"; la cadena de destino es " C" y las reglas de reescritura son
A:B
B:BB
B:A
AA:C
entonces la cadena de destino es accesible de la siguiente manera:
A
B (using rule 1)
BB (using rule 2)
AB (using rule 3)
AA (using rule 3)
C (using rule 4)
Tanteo
Tu puntaje será
- la longitud de su cadena de origen,
- más la longitud de tu cadena objetivo,
- más la longitud de todas las cadenas incluidas en sus reglas de reescritura,
- más un punto extra por cada regla de reescritura.
Si escribe sus reglas de reescritura con un separador de dos puntos como se indica arriba, esta es solo la longitud total de todas las reglas de reescritura (incluido el separador), más las longitudes de las cadenas de origen y destino. Una puntuación más baja es mejor. El número de caracteres distintos en su alfabeto se usará para romper los lazos, y menos serán mejores.
Generosidad
Me gustaría ver respuestas que realmente vayan para puntuaciones bajas. Otorgaré 200 repeticiones a la primera respuesta que obtenga menos de 100 puntos en este desafío y no se quiebre.
Mx -> Mxxregla, por lo que terminaría mucho más complicado que el de Hofstadter original.Respuestas:
326 puntos - Agrietado por jimmy23013
El nivel es Picokosmos # 13 de Aymeric du Peloux (con una modificación trivial). Traté de encontrar un nivel de buen gusto que pudiera implementarse con "cajas" y "paredes" siendo el mismo personaje. Para este nivel, fue posible haciendo que el estrangulador central tuviera dos columnas de ancho en lugar de una.
Las cadenas de reglas / inicial / objetivo podrían jugarse un poco más, pero esto es solo por diversión.
Cadena inicial:
Cadena de destino:
Reglas:
fuente
171 puntos, agrietados por HyperNeutrino
Fuente:
YAAATObjetivo:
VW626206555675126212043640270477001760465526277571600601Reglas:
Solo algo obvio que hacer. La secuencia real de pasos de reescritura probablemente no encajará en una respuesta SE.
fuente
VWxdondexse forma a partir de cualquier cadena binaria de_(0) y+(1) que evalúe a10*n+6(incluido el líder_;n= entero no negativo), pero elxdado (626...601) se forma a partir de un binario que evalúa a10*n+3(para un grann).33 puntos, resquebrajados por el usuario 71546
Una simple para comenzar.
Fuente:
xnorDestino:
xorReescribir reglas:
La última regla lleva 11 o a la cadena vacía.
fuente
139 puntos (seguro-ish)
Tenía la intención de que esta respuesta fuera descifrada, y user202729 básicamente la resolvió en los comentarios, pero nadie publicó una respuesta en el hilo de los ladrones, así que la marco como "segura" e incluyo mi prueba a continuación.
(Evidentemente, estas cosas son mucho más fáciles de hacer que de descifrar. Sin embargo, nadie ha intentado obtener un puntaje realmente bajo, y podría haber más diversión al final de las cosas, si este desafío alguna vez despega. )
Aquí hay una respuesta propia. Es potencialmente muy difícil, pero debería ser fácil si averigua de dónde viene.
alfabeto:
ABCDEⒶⒷⒸⒹⒺⒻ⬛⚪️️🎂←→fuente:
←A→objetivo:
←🎂→Reglas: (el espacio en blanco no es significativo)
Aquí hay una versión ASCII , en caso de que unicode no se muestre bien para todos.
Prueba
Esto es equivalente al mejor contendiente actual para un castor ocupado de seis estados . Un castor ocupado es una máquina de Turing que se detiene después de mucho tiempo. Debido a esto, la cadena de origen
←A→se puede transformar en la cadena de destino←🎂→, pero solo después de más de7*10^36534pasos, lo que llevaría mucho más tiempo que la edad del universo para cualquier implementación física.La cinta de la máquina Turing está representada por los símbolos
⬛(0) y⚪(1). Las normassignifica que los extremos de la cinta siempre se pueden extender con más ceros. Si el cabezal de la máquina de Turing alguna vez se acerca a un extremo de la cinta, podemos aplicar una de estas reglas, lo que nos permite pretender que la cinta es infinita, y comienza con todos los ceros. (Los símbolos
→y←nunca se crean o destruyen, por lo que siempre están en los extremos de la cinta).La cabeza de la máquina de Turing se representa con los símbolos
ABCDEⒶⒷⒸⒹⒺⒻy🎂.Asignifica que la cabeza está en estadoAy el símbolo debajo de la cabeza es un⬛(0), mientras que Ⓐ significa que está en estadoAy el símbolo debajo de ella es un⚪(1). Esto continúa para los otros estados, con la letra dentro de un círculo que representa un 1 debajo de la cabeza y la versión no circulada que representa un 0. (No hay símboloFporque sucede que la cabeza nunca termina en estadoFcon un 1 debajo).El estado
🎂es el estado de detención. Tiene las reglas especialesSi alguna vez se alcanza el estado de detención, podemos aplicar repetidamente estas reglas para "absorber" toda la cinta (incluidos los ceros adicionales que surgieron al extender la cinta más de lo necesario), dejándonos en el estado
←🎂→. Por lo tanto, el problema de accesibilidad se reduce a si🎂alguna vez se alcanzará el estado .Las reglas restantes son las reglas de transición para la máquina Turing. Por ejemplo, las reglas
puede leerse como "si la máquina está en estado A y hay un cero debajo de la cabeza, luego escriba un 1, cambie al estado B y muévase a la derecha". Mover a la derecha requiere dos reglas, porque la celda de la cinta a la derecha podría contener un
⬛, en cuyo caso la máquina debería entrar en estadoB, o la celda podría contener un⚪, en cuyo caso debería entrar en estadoⒷ, ya que hay una⚪debajo.Similar,
significa "si la máquina está en estado D y hay un 1 debajo de la cabeza, luego escriba un 0, cambie al estado C y muévase a la izquierda".
La máquina Turing utilizada fue descubierta por Pavel Kropitz en 2010. Aunque a menudo se menciona en el contexto de castores ocupados, su tabla de transición real es un poco difícil de rastrear, pero se puede encontrar, por ejemplo, aquí . Se puede escribir como
que puede leerse como "si la máquina está en el estado A y hay un cero debajo de la cabeza, luego escriba un 1, cambie al estado B y muévase a la derecha", y así sucesivamente. Debe ser sencillo, si es laborioso, verificar que cada entrada de esta tabla corresponda a un par de reglas como se describió anteriormente.
La única excepción es la regla
1RHque ocurre cuando la máquina está en el estado F sobre un 0, porque parecía bastante inútil hacer que la máquina escribiera un 1 y se moviera hacia la derecha cuando podría detenerse inmediatamente tan pronto como entrara en el estado F sobre un 0. Así que cambié la regla que habría sidodentro
Por eso no hay símbolo
Fen el alfabeto. (Hay otros 'golfs' que podría haber hecho, pero no quería ocultarlo demasiado).Eso es básicamente todo. Se puede acceder a la cadena de destino desde la cadena de origen, pero solo después de un número ridículo de pasos.
Un dato más divertido: si hubiera usado
←A⚪⚪→como punto de partida, entonces no se necesitarían
7*10^36534pasos para detenerlos, sino10^10^10^10^18705352pasos, que es un número muy grande.fuente
48 puntos, agrietados por bb94
Alfabeto:
abcFuente:
cbaabaabcDestino:
cbacbcabcReescribir reglas:
fuente
287 puntos, seguro
Fuente:
YAATObjetivo:
Reglas:
Descubrí que openssl es mucho más fácil de usar que gpg para este propósito.
Vea el crack de HyperNeutrino a la versión más débil. En este caso, el número de
Cs es:Y los factores primos son:
El primer número mod 5 = 2, por lo que es posible obtener la cadena final.
fuente
402 puntos
Alfabeto:
abcdefghijklmnopqrstuFuente:
abcdoiDestino:
ioabcdnnnnnnnnnnnnnnnnnnReescribir reglas:
La última regla le permite crear tantos
ncorreos electrónicos como necesite.Por feo que parezca, en realidad es bastante agradable, de una forma u otra ...
fuente
aoi:eogseeogsupone que eseag?1337 puntos
Definitivamente no es competitivo, y tardó demasiado en crear (espero no haberme equivocado)
Insinuación:
Alfabeto:
ABEILRSTabcdefijlrFuente:
SIbbbbbbbdbffacebbfadbdbeecddfaeebddcefaddbdbeeecddaaaaadfaeeebdddcefbbfadbdbdbeeecdddfaeeebdddcefaddbdbeeecddaaaadfaeeebdddcefbfadbdbdbeeecdddfaeeebdddcbdbffacebfadbdbeecddfaeebddceeefadddbdbeeeecddddfaeeeebddddceefaddbdbeeecdddfaeeebdddceefadadbefadfacdbeecddfaeebddcefaeeefaddbdbeeecdddfaeeebdddcceecdfaeeaddceecefaeadcbefadfacecdfaebdceeeeefadddddbdbeeeeeecddddddfaeeeeeebddddddceeefaddaeecdddbdbffacebfadbdbeecddfaeebddceeefadddbdbeeeecddddfaeeeebddddceefaddbdbeeecdddfaeeebdddceefadadbefadfacdbeecddfaeebddcefaeeefaddbdbeeecdddfaeeebdddcceecdfaeeaddceecefaeadcbefadfacecdfaebdcefaefaeeebdddcdcefaceeaaaceefacdffacebdceeeeefadddddbdbeeeeeecddddddfaeeeeeebddddddceeefaddaeecdddbdbffacebfadbdbeecddfaeebddceeefadddbdbeeeecddddfaeeeebddddceefaddbdbeeecdddfaeeebdddceefadadbefadfacdbeecddfaeebddcefaeeefaddbdbeeecdddfaeeebdddcceecdfaeeaddceecefaeadcbefadfacecdfaebdcefaefaeeebdddcdcefaceeaaaaceefacdffacebdcecefacEObjetivo:
SEReescribir reglas:
fuente
154 puntos
Alfabeto:
P.!xABC[{mD<Fuente:
[x!P.P...P..P.P....P..P.P.....P.P....P......P.P..P...P.P...Pm(61 caracteres)Objetivo:
{CCCCC<(hay 5Cs, entonces 7 caracteres)Reglas:
Hay 19 reglas, número total de caracteres = 67.
fuente
106 puntos - agrietados por HyperNeutrino
Alfabeto:
ABCDEFGHIJFuente:
FIABCJAGJDEHHIDObjetivo:
FReescribir reglas:
Bien, HyperNeutrino ha demostrado que esto no tiene solución. Sin embargo, hay otra solución para esto.
Tomar:
El valor de la fuente es par. El valor del objetivo es impar. Si tomamos cada lado, sumamos el valor y llevamos el valor a mod 2, los valores se mantienen igual. Por lo tanto, esto no se puede lograr.
fuente