Este é um pouco à prova de golf -como COPS-e-ladrões desafio. Este é o fio dos ladrões; a discussão dos policiais está aqui .
Ladrões
Os policiais publicarão sistemas de reescrita abstratos. Sua tarefa é decifrar os envios, provando que a cadeia de destino pode ou não ser alcançada a partir da cadeia de origem, aplicando suas regras de reescrita. (Você pode fazer isso publicando uma sequência de regras de reescrita que começa com a cadeia de origem e termina com o destino ou provando matematicamente que isso existe ou não.)
cops-and-robbers
repeated-transformation
grammars
Nathaniel
fonte
fonte
Respostas:
jimmy23013
Vamos trabalhar para trás neste. Primeiro, transformamos os dígitos em suas representações binárias. Nós vamos de
VW626206555675126212043640270477001760465526277571600601
paraVW++__+_++__+____++_+_++_++_+++_++++_+__+_+_++__+___+_+____+___++++_+______+_+++___+__++++++________++++++____+__++_+_++_+_+_++__+_+++++++_++++__+++_______++______+
. Em seguida, continuamos aplicando o inverso deDCW:W+
eDW:W_
até limparmos todos os símbolos. Nosso resultado é agoraVDCDCDDDCDDCDCDDDCDDDDDCDCDDCDDCDCDDCDCDDCDCDCDDCDCDCDCDDCDDDCDDCDDCDCDDDCDDDDCDDCDDDDDCDDDDCDCDCDCDDCDDDDDDDCDDCDCDCDDDDCDDDCDCDCDCDCDCDDDDDDDDDCDCDCDCDCDCDDDDDCDDDCDCDDCDDCDCDDCDDCDDCDCDDDCDDCDCDCDCDCDCDCDDCDCDCDCDDDCDCDCDDDDDDDDCDCDDDDDDDCW
. Agora, queremos fazer com que essa string correspondaVD+C+W
; isto é, queremos mover todos osD
s para a esquerda de todos elesC
. Isso pode ser feito revertendoDCC:CD
. Fazemos isso repetindo o seguinte algoritmo:D
que está à direita de um bloco deC
s.D
para a esquerda desse bloco.C
s.Através de algumas contas, podemos determinar que teremos 123 se
D
4638704741628490670592103344196019722536654143873C
s (você estava certo sobre isso não se encaixar em uma resposta SE ... duvido que isso se encaixaria se armazenado como estados de todos os átomos da Terra combinado: P).Se continuarmos aplicando o inverso de
V:VD
, podemos nos livrar de todos osD
s agora, e assim conseguiremosVCCC.......CCCW
. Nós convertemos asV
costas emYZ
. Agora nós temosYZCCC.......CCCW
.Queremos ser capazes de nos livrar de todos os se
C
tê-lo na formaYAAA...AAABBB...BBBZW
. Felizmente, isso pode ser feito pelo seguinte método. Em primeiro lugar, aplicamosYB:Y
inversamente 587912508217580921743211 vezes para obterYBBB.......BBBZCCC.......CCCW
. Em seguida, repetimos a seguinte sequência de etapas (onde[?*]
significa qualquer número de?
, não necessariamente maior que zero):CZ:ZC
Aplicação inversa 587912508217580921743211 vezes para obterY[A*]BBB.......BBBCCC.......CCCZCCC.......CCCW
CB:BC
várias vezes para obterY[A*]BCBCBC.......BCBCBCZCCC.......CCCW
AZ:Z
eAB:BCA
muitas vezes para obterY[A*]ABBB.......BBBZCCC.......CCCW
Por indução, vemos que podemos mover a
BZ
combinação até o fim (exceto antes doW
) e, em seguida, o número deA
s é 1/587912508217580921743211 do número deC
s, deixando-nos 7890127658096618386747843A
s. Agora temosYAAA.......AAABBB.......BBBZW
. Converta asZW
costas em a eU
, em seguida, aplique inversamenteU:BU
várias vezes para manter apenas 2 se,B
depois converta-asBBU
em aT
, e agora você temYAAA.......AAAT
. Em seguida, você pode aplicar inversamenteT:AAAAAT
várias vezes para obter,YAAAT
porque o número deA
s era 3 maior que um múltiplo de 5.Obrigado pelo desafio!
fonte
A:B
aABC
dáBBC
, é óbvio que a aplicação do inverso doA:B
queBBC
pode darABC
. Não é especificamente declarado que é permitido, mas eu posso facilmente reverter meus passos e ter uma solução "convencional", mas é mais fácil voltar ao IMO.A:B
e não for declarado que a aplicação inversa é permitida, acho que você não pode ir deBBC
paraABC
. Esse caso específico pode ser diferente e há algum caminho a seguir na outra direção. Vou verificar mais tarde.boboquack
Para uma determinada sequência, pegue todas as letras (a = 0, b = 1, c = 2), some-as e faça o módulo 3. Em seguida, nenhuma regra de reescrita altera esse valor. A cadeia de origem tem um valor de 1 e o destino tem um valor de 2. Portanto, nenhuma combinação de regras transformará a cadeia de origem na cadeia de destino.
fonte
feersum
Este é um quebra-cabeça sokoban. A posição inicial é:
A posição final é:
Pode ser resolvido usando a seguinte sequência de teclas:
Aqui está um programa bash que converte a sequência de teclas em comandos sed e os aplica. Os comandos sed contêm apenas comandos de substituição usando as regras de reescrita definidas na resposta do policial e comandos de rotulagem e ramificação que não modificam a sequência. Ele confirma que você pode obter a sequência de destino usando apenas as regras de reescrita.
Experimente online!
Experimente online (com o código de escape removido)!
Para cima e para baixo,
!:wLW_
ou!:_VRv
é aplicado uma vez de forma correspondente, e as regras relevantes são aplicadas repetidamente até que!
apareça novamente. Para a direita, um de!#_:_!#
e!_:_!
é aplicado. Para a esquerda, um de_#!:#!_
e_!:!_
é aplicado.Veja a saída nos links para a posição após cada movimento.
fonte
xnor
Usamos
[X,Y]
para indicar uma sequência de YX
sComeçando com
xnor = xn[o,1]r
, repetindo 10 vezes o algoritmo - exceto no 10º loop, paramos na Etapa 4, tendox[o,1024]r
.Aplicando a Regra 4, isso limpa 1023 = 11 * 93
o
s, saindoxor
.fonte
VortexYT
Não há como eliminar
F
s sem criar / usar outros caracteres; portanto, devemos usarI:F
como o último passo para chegar ao alvo. Nenhuma regra fornece um únicoI
sem outros caracteres indesejados, portanto, você não pode chegar à string de destino.Da mesma forma, se você tentar mapear de trás para frente a partir da fonte, poderá ir de
F
atéI
antes de não ter mais opções.fonte