Reto de reescritura abstracta (ladrones)

9

Este es un desafío de como el . 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).

Vea el hilo de la policía para más detalles y definiciones.

Nathaniel
fuente
Do'h! Puse una recompensa por la pregunta equivocada, estaba destinado a estar en el desafío de la policía. Entonces alguien recibirá una recompensa al azar.
Nathaniel
No se preocupe, he devuelto la recompensa.
James
@DJMcMayhem: Huh ... así que es por eso que la API de SE enumera esta pregunta como presentada, pero sin cantidad de recompensa o fecha de cierre. : o Bueno, es hora de agregar alguna validación de entrada a mi script de usuario.
Ilmari Karonen

Respuestas:

16

jimmy23013

Trabajemos al revés para este. Primero convertimos los dígitos en sus representaciones binarias. Vamos de VW626206555675126212043640270477001760465526277571600601a VW++__+_++__+____++_+_++_++_+++_++++_+__+_+_++__+___+_+____+___++++_+______+_+++___+__++++++________++++++____+__++_+_++_+_+_++__+_+++++++_++++__+++_______++______+. A continuación, seguimos aplicando el inverso de DCW:W+y DW:W_hasta que borramos todos los símbolos. Nuestro resultado es ahora VDCDCDDDCDDCDCDDDCDDDDDCDCDDCDDCDCDDCDCDDCDCDCDDCDCDCDCDDCDDDCDDCDDCDCDDDCDDDDCDDCDDDDDCDDDDCDCDCDCDDCDDDDDDDCDDCDCDCDDDDCDDDCDCDCDCDCDCDDDDDDDDDCDCDCDCDCDCDDDDDCDDDCDCDDCDDCDCDDCDDCDDCDCDDDCDDCDCDCDCDCDCDCDDCDCDCDCDDDCDCDCDDDDDDDDCDCDDDDDDDCW. Ahora queremos hacer que esta cadena coincida VD+C+W; es decir, queremos mover todos los Ds a la izquierda de todos los Cs. Esto se puede hacer invirtiendo DCC:CD. Hacemos esto repitiendo el siguiente algoritmo:

  1. Encuentra el primero Dque está a la derecha de un bloque de Cs.
  2. Mueve el Da la izquierda de ese bloque.
  3. Duplica el número de Cs.

A través de algunas matemáticas, podemos determinar que terminaremos con 123 Dsy 4638704741628490670592103344196019722536654143873 Cs (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 los Ds ahora, así que obtenemos VCCC.......CCCW. Convertimos la Vespalda en YZ. Ahora tenemos YZCCC.......CCCW.

Queremos poder deshacernos de todos los Cs y tenerlo en forma YAAA...AAABBB...BBBZW. Afortunadamente, esto se puede hacer mediante el siguiente método. En primer lugar, aplicamos YB:Yinversamente 587912508217580921743211 veces para obtener YBBB.......BBBZCCC.......CCCW. Luego, repetimos la siguiente secuencia de pasos (donde [?*]significa cualquier número de ?, no necesariamente mayor que cero):

  1. Aplicar de CZ:ZCforma inversa 587912508217580921743211 veces para obtenerY[A*]BBB.......BBBCCC.......CCCZCCC.......CCCW
  2. Aplicar inversamente CB:BCmuchas veces para obtenerY[A*]BCBCBC.......BCBCBCZCCC.......CCCW
  3. Aplicación inversa AZ:Zy AB:BCAmuchas veces para obtenerY[A*]ABBB.......BBBZCCC.......CCCW

A través de la inducción, vemos que podemos mover la BZcombinación hasta el final (excepto antes del W) y luego el número de As es 1/587912508217580921743211 del número de Cs, dejándonos con 7890127658096618386747843 As. Ahora tenemos YAAA.......AAABBB.......BBBZW. Convierta la parte ZWposterior a a U, luego aplique inversamente U:BUmuchas veces para mantener solo 2 Bsy luego convierta la BBUa a T, y ahora tiene YAAA.......AAAT. Luego, puede aplicar inversamente T:AAAAATmuchas veces para obtener YAAATporque el número de As fue 3 mayor que un múltiplo de 5.

Gracias por el reto!

Hiperneutrino
fuente
¿Se indica en alguna parte o es por defecto que se permite la aplicación inversa?
Weijun Zhou
2
@WeijunZhou Es decir, si la aplicación A:Ba ABCda BBC, es obvio que la aplicación de la inversa de la A:Bque BBCpuede dar ABC. 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.
HyperNeutrino
Quiero decir, por ejemplo, si solo hay una regla A:By no se establece que se permite la aplicación inversa, entonces no creo que pueda pasar de BBCa ABC. Este caso específico puede ser diferente y hay alguna manera de ir en la otra dirección. Lo revisaré más tarde.
Weijun Zhou
2
@HyperNeutrino ^^
Weijun Zhou
1
¿Qué programa usaste para factorizar esto y cuánto tiempo tomó?
user202729
9

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.

bb94
fuente
9

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:

←ológicamente → ↓↓ ← ↑ ← peculiaridades habitualmente ↓↓ → ↑ ← ↑↑↑ ← ↓ → ↑ → ↓↓ →viousviousviousvious ferrocarril ↓ → ↑↑ ↓↓ ← ↓ ← ↑ → ↑ ←uerdo ← ↑ ←cedentes ↓ →viousviousvious ferrocarril ↓ →font> ↑↑ → ↑↑ ← ↓ ←otóx ↓↓ → ↑ ← ↑ →vious ↑ →vious ↓ ← ↓ ← preservar ↓↓ → ↑ ← corporativos con frecuencia ↑ ↑ ← usualmente ↓ →vious ↓ → ↓↓ ← ↑ ← ↑ → ↑↑ ←+ ↓ → ↑ → ↓↓ ← ↓ → ↑ →viousviousvious ferrocarrilorence ↓↓ ← ↑ → ↑ ← ← →viousvious ↑↑ ← ↓ → ↓ ← ↑↑ →vious ↑ →vious ↓ ← ↓ ← → ↑↑ ← ↓ ← ↓ ↑ →vious ↓ ← ↑ ←nge ↓↓↓ → suces ↑↑ ↓↓ ← us ↑↑ → ↓ ↑↑ → ↑ →font> ↓ ← ↓ ← ↓ ←,5 ↑↑ →font> ↑ → ↓ ← ↓↓ ← ómnidos de destino ↑ ← us ↓ →viousviousviousvious ← ← Resumen de las características ↑↑ ←( ↓↓ ← ↑ →viousviousviousvious

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.

s="___##___####_____##_#_#_##_#_!####______##_#####__####_#_######__###__"
input=

while
    printf '\n%80s\n' "$s"|fold -w14
    read -n 1
    [ "$REPLY" = $'\e' ]
do
    read -n 2
    case "$REPLY" in
    [A)
        s="$(sed '
s:!:wLW_:
        :a
s:L:<<<<<<<<<<<<<:
s:#w<:w#:
s:_w<:w_:
s:_<:<_:
s:#<:<#:
s:#wW:wLX!:
s:_W:W_:
s:#W:W#:
s:_wW:!:
s:_X:X_:
s:#X:X#:
s:_wX:#:
        ta' <<<"$s")";;
    [B)
        s="$(sed '
s:!:_VRv:
        :a
s:R:>>>>>>>>>>>>>:
s:>v#:#v:
s:>v_:_v:
s:>_:_>:
s:>#:#>:
s:Vv#:!URv:
s:U_:_U:
s:U#:#U:
s:Uv_:#:
s:V_:_V:
s:V#:#V:
s:Vv_:!:
        ta' <<<"$s")";;
    [C)
        s="$(sed '
s:!#_:_!#:
        te
s:!_:_!:
        :e' <<<"$s")";;
    [D)
        s="$(sed '
s:_#!:#!_:
        te
s:_!:!_:
        :e' <<<"$s")";;
    esac
    input="$input${REPLY:1}"
done

echo "$input"

Pruébalo en línea!

¡Pruébelo en línea (con el código de escape eliminado)!

Para arriba y abajo, !:wLW_o !:_VRvse 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.

jimmy23013
fuente
6

xnor

Regla 1 x:xn Regla 2 no:oon Regla 3 nr:r Regla 4ooooooooooo:

Usamos [X,Y]para indicar una corrida de Y Xs

A partir de xn[o,A]r,

  1. Aplicando la Regla 2 una vez que la tengamos x[o,2]n[o,A-1]r.
  2. Aplicando la Regla 2 una vez más tenemos x[o,4]n[o,A-2]r
  3. Aplicando hasta que la os entre ny se rconvierte en 0, tenemos x[o,2*A]nr.
  4. Aplicando la Regla 3 una vez que la tengamos x[o,2*A]r.
  5. Aplicando la Regla 1 una vez que la tengamos xn[o,2*A]r.

Entonces, tenemos un algoritmo para generar de xn[o,A]ra xn[o,2*A]r.

Comenzando desde xnor = xn[o,1]r, repitiendo 10 veces el algoritmo, excepto en el décimo bucle, nos detenemos en el Paso 4, teniendo x[o,1024]r.

Aplicando la Regla 4, esto borra 1023 = 11 * 93 os, dejando xor.

Shieru Asakoto
fuente
2

VortexYT

No hay forma de eliminar Fs sin crear / usar otros caracteres; por lo tanto, debemos usarlo I:Fcomo el último paso para llegar al objetivo. Ninguna regla da un solo Isin 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 Fhasta Ique no tengas más opciones.

Hiperneutrino
fuente
Ooch, eso duele. Sin embargo, hay otra solución ...
VortexYT
@VortexYT oh, ¿en serio? hm, no lo sabia. pero sí, el objetivo no puede asignar más de un paso, lo que probablemente hizo que esto fuera mucho más fácil de lo que pretendía: P
HyperNeutrino
2
veces