Este es un desafío de policías y ladrones como el golf . Este es el hilo de los ladrones; El hilo de la policía está aquí .
Ladrones
Los policías publicarán sistemas de reescritura abstracta. Su tarea es descifrar sus envíos demostrando que la cadena de destino puede o no ser alcanzada desde la cadena de origen mediante la aplicación de sus reglas de reescritura. (Puede hacer esto ya sea publicando una secuencia de reglas de reescritura que comience con la cadena fuente y termine con el destino, o demostrando matemáticamente que esto existe o no).
Respuestas:
jimmy23013
Trabajemos al revés para este. Primero convertimos los dígitos en sus representaciones binarias. Vamos de
VW626206555675126212043640270477001760465526277571600601
aVW++__+_++__+____++_+_++_++_+++_++++_+__+_+_++__+___+_+____+___++++_+______+_+++___+__++++++________++++++____+__++_+_++_+_+_++__+_+++++++_++++__+++_______++______+
. A continuación, seguimos aplicando el inverso deDCW:W+
yDW:W_
hasta que borramos todos los símbolos. Nuestro resultado es ahoraVDCDCDDDCDDCDCDDDCDDDDDCDCDDCDDCDCDDCDCDDCDCDCDDCDCDCDCDDCDDDCDDCDDCDCDDDCDDDDCDDCDDDDDCDDDDCDCDCDCDDCDDDDDDDCDDCDCDCDDDDCDDDCDCDCDCDCDCDDDDDDDDDCDCDCDCDCDCDDDDDCDDDCDCDDCDDCDCDDCDDCDDCDCDDDCDDCDCDCDCDCDCDCDDCDCDCDCDDDCDCDCDDDDDDDDCDCDDDDDDDCW
. Ahora queremos hacer que esta cadena coincidaVD+C+W
; es decir, queremos mover todos losD
s a la izquierda de todos losC
s. Esto se puede hacer invirtiendoDCC:CD
. Hacemos esto repitiendo el siguiente algoritmo:D
que está a la derecha de un bloque deC
s.D
a la izquierda de ese bloque.C
s.A través de algunas matemáticas, podemos determinar que terminaremos con 123
D
sy 4638704741628490670592103344196019722536654143873C
s (tenía razón acerca de que esto no encaja en una respuesta SE ... Dudo que esto encajaría si se almacenara como estados de todos los átomos en la Tierra combinado: P).Si seguimos aplicando el reverso de
V:VD
, podemos deshacernos de todos losD
s ahora, así que obtenemosVCCC.......CCCW
. Convertimos laV
espalda enYZ
. Ahora tenemosYZCCC.......CCCW
.Queremos poder deshacernos de todos los
C
s y tenerlo en formaYAAA...AAABBB...BBBZW
. Afortunadamente, esto se puede hacer mediante el siguiente método. En primer lugar, aplicamosYB:Y
inversamente 587912508217580921743211 veces para obtenerYBBB.......BBBZCCC.......CCCW
. Luego, repetimos la siguiente secuencia de pasos (donde[?*]
significa cualquier número de?
, no necesariamente mayor que cero):CZ:ZC
forma inversa 587912508217580921743211 veces para obtenerY[A*]BBB.......BBBCCC.......CCCZCCC.......CCCW
CB:BC
muchas veces para obtenerY[A*]BCBCBC.......BCBCBCZCCC.......CCCW
AZ:Z
yAB:BCA
muchas veces para obtenerY[A*]ABBB.......BBBZCCC.......CCCW
A través de la inducción, vemos que podemos mover la
BZ
combinación hasta el final (excepto antes delW
) y luego el número deA
s es 1/587912508217580921743211 del número deC
s, dejándonos con 7890127658096618386747843A
s. Ahora tenemosYAAA.......AAABBB.......BBBZW
. Convierta la parteZW
posterior a aU
, luego aplique inversamenteU:BU
muchas veces para mantener solo 2B
sy luego convierta laBBU
a aT
, y ahora tieneYAAA.......AAAT
. Luego, puede aplicar inversamenteT:AAAAAT
muchas veces para obtenerYAAAT
porque el número deA
s fue 3 mayor que un múltiplo de 5.Gracias por el reto!
fuente
A:B
aABC
daBBC
, es obvio que la aplicación de la inversa de laA:B
queBBC
puede darABC
. No se dice específicamente que esté permitido, pero puedo revertir mis pasos fácilmente y tener una solución "convencional", es solo que es más fácil retroceder en la OMI.A:B
y no se establece que se permite la aplicación inversa, entonces no creo que pueda pasar deBBC
aABC
. Este caso específico puede ser diferente y hay alguna manera de ir en la otra dirección. Lo revisaré más tarde.boboquack
Para una cadena dada, tome todas las letras (a = 0, b = 1, c = 2), sume y tome el módulo 3. Entonces ninguna de las reglas de reescritura cambia ese valor. La cadena de origen tiene un valor de 1 y el destino tiene un valor de 2. Por lo tanto, ninguna combinación de reglas transformará la cadena de origen en la cadena de destino.
fuente
Feersum
Este es un rompecabezas sokoban. La posición inicial es:
La posición final es:
Se puede resolver utilizando la siguiente secuencia de teclas:
Aquí hay un programa bash que convierte la secuencia de teclas en comandos sed y los aplica. Los comandos sed contienen solo comandos de reemplazo usando las reglas de reescritura definidas en la respuesta del policía y los comandos de etiquetado y ramificación que no modifican la cadena. Confirma que puede obtener la cadena de destino utilizando solo las reglas de reescritura.
Pruébalo en línea!
¡Pruébelo en línea (con el código de escape eliminado)!
Para arriba y abajo,
!:wLW_
o!:_VRv
se aplica por una vez correspondientemente, y las reglas relevantes se aplican repetidamente hasta que!
aparezca nuevamente. Por derecho, se aplica uno de!#_:_!#
y!_:_!
. Para la izquierda, se aplica uno de_#!:#!_
y_!:!_
.Vea la salida en los enlaces para la posición después de cada movimiento.
fuente
xnor
Usamos
[X,Y]
para indicar una corrida de YX
sComenzando desde
xnor = xn[o,1]r
, repitiendo 10 veces el algoritmo, excepto en el décimo bucle, nos detenemos en el Paso 4, teniendox[o,1024]r
.Aplicando la Regla 4, esto borra 1023 = 11 * 93
o
s, dejandoxor
.fuente
VortexYT
No hay forma de eliminar
F
s sin crear / usar otros caracteres; por lo tanto, debemos usarloI:F
como el último paso para llegar al objetivo. Ninguna regla da un soloI
sin otros caracteres no deseados, por lo que no puede llegar a la cadena de destino.De manera equivalente, si intentas hacer un mapa hacia atrás desde la fuente, solo puedes ir desde antes
F
hastaI
que no tengas más opciones.fuente