Este é um pouco à prova de golf -como COPS-e-ladrões desafio. Este é o tópico dos policiais; o fio dos ladrões está aqui.

Policiais

Sua tarefa é definir um sistema de reescrita abstrato no qual é difícil determinar a acessibilidade de uma palavra da outra. Você irá preparar o seguinte:

1. Um conjunto de símbolos, chamado alfabeto. (Você pode usar caracteres Unicode para isso, mas não use espaços em branco ou símbolos que sejam difíceis de distinguir entre si.)

2. Uma sequência de origem composta por símbolos do seu alfabeto.

3. Uma sequência de destino composta por símbolos do seu alfabeto.

4. Um conjunto de regras de reescrita usando caracteres do seu alfabeto. (Veja abaixo a definição de uma regra de reescrita.)

5. Uma prova que mostra se a string de origem pode ser convertida na string de destino pela aplicação sucessiva de suas regras de reescrita. Essa prova pode consistir em uma sequência real de etapas de reescrita, ou uma prova matemática de que essa sequência deve existir ou uma prova matemática de que essa sequência não existe.

Você postará os quatro primeiros, mantendo a prova em segredo; os ladrões tentarão decifrar sua resposta, fornecendo sua própria prova de que sua sequência de destino pode ou não ser alcançada a partir da sequência de origem. Se o seu envio não for quebrado dentro de duas semanas , você poderá marcá-lo como seguro e editar em sua prova.

Os envios serão pontuados de acordo com o número de caracteres em suas regras de reescrita e suas sequências de origem e destino, conforme detalhado abaixo. O vencedor será o envio sem rachaduras com a pontuação mais baixa.

O que é uma regra de reescrita?

Uma regra de reescrita é simplesmente um par de strings no seu alfabeto. (Qualquer uma dessas cadeias de caracteres pode estar vazia.) Um aplicativo de regra de reescrita consiste em localizar uma substring igual à primeira cadeia de caracteres do par e substituí-la pela segunda.

Um exemplo deve deixar isso claro:

Alfabeto Suponha que é A, Be C; a cadeia de origem é " A"; a cadeia de destino é " C" e as regras de reescrita são

A:B
B:BB
B:A
AA:C

a sequência de destino é alcançável da seguinte maneira:

A
B   (using rule 1)
BB  (using rule 2)
AB  (using rule 3)
AA  (using rule 3)
C   (using rule 4)

Pontuação

Sua pontuação será

• o comprimento da sua string de origem,
• mais o comprimento da sua sequência de destino,
• além do comprimento de todas as strings incluídas nas suas regras de reescrita,
• mais um ponto extra para cada regra de reescrita.

Se você escrever suas regras de reescrita com um separador de dois pontos, acima, esse será apenas o comprimento total de todas as regras de reescrita (incluindo o separador), além dos comprimentos das strings de origem e de destino. Uma pontuação mais baixa é melhor. O número de caracteres distintos em seu alfabeto será usado para romper laços, com menos sendo melhores.

Recompensa

Eu gostaria de ver respostas que realmente valem para pontuações baixas. Atribuirei 200 repetições à primeira resposta que marcar menos de 100 pontos neste desafio e não ficar rachada.

326 pontos - Rachado por jimmy23013

O nível é Picokosmos # 13 por Aymeric du Peloux (com uma modificação trivial). Tentei encontrar um nível de bom gosto que pudesse ser implementado com "caixas" e "paredes" sendo o mesmo personagem. Para esse nível, foi possível fazer com que o ponto de estrangulamento central tivesse duas colunas de largura em vez de uma.

As regras / seqüências iniciais / alvo podem ser um pouco mais complicadas, mas isso é apenas por diversão.

Sequência inicial:

___##___####_____##_#_#_##_#_!####______##_#####__####_#_######__###__

Cadeia de destino:

___##___####_____##_#_#_##_#_#####____!__#_#####__####_#_######__###__

Regras:

_wW:!
_<:<_
Vv_:!
V_:_V
R:>>>>>>>>>>>>>
V#:#V
#w<:w#
>v_:_v
_wX:#
_!:!_
!:wLW_
L:<<<<<<<<<<<<<
#W:W#
!#_:_!#
_w<:w_
#<:<#
!:_VRv
>v#:#v
Uv_:#
_W:W_
_X:X_
>#:#>
#X:X#
U_:_U
Vv#:!URv
#wW:wLX!
>_:_>
!_:_!
_#!:#!_
U#:#U

171 pontos, quebrado por HyperNeutrino

Fonte: YAAAT

Alvo: VW626206555675126212043640270477001760465526277571600601

Regras:

T:AAAAAT
T:BBU
U:BU
U:ZW
AB:BCA
CB:BC
AZ:Z
CZ:ZC
YB:Y
YZ:V
V:VD
DCC:CD
DCW:W+
DW:W_
___:0
__+:1
_+_:2
_++:3
+__:4
+_+:5
++_:6
+++:7

Apenas algo óbvio para fazer. A sequência real de etapas de reescrita provavelmente não caberá em uma resposta SE.

33 pontos, quebrado pelo usuário71546

Simples para começar.

Origem: xnor
Alvo: xor
Regras de reescrita:

x:xn
no:oon
nr:r
ooooooooooo:

A última regra leva 11 o para a string vazia.

139 pontos (seguro)

Eu pretendia que essa resposta fosse quebrada, e o user202729 basicamente a resolveu nos comentários, mas ninguém postou uma resposta no tópico dos ladrões, por isso estou marcando-a como "segura" e incluindo minha prova abaixo.

(Essas coisas são evidentemente muito mais fáceis de fazer do que de quebrar. Porém, ninguém tentou obter uma pontuação muito baixa ainda, e pode haver mais diversão nesse fim, se esse desafio decolar. )

Aqui está uma resposta automática. É potencialmente muito difícil, mas deve ser fácil se você descobrir de onde veio.

alfabeto: ABCDEⒶⒷⒸⒹⒺⒻ⬛⚪️️🎂←→

fonte: ←A→

alvo: ←🎂→

Regras: (espaço em branco não é significativo)

← : ←⬛
→ : ⬛→
A⬛ : ⚪B
A⚪ : ⚪Ⓑ
⬛Ⓐ : E⚪
⚪Ⓐ : Ⓔ⚪
B⬛ : ⚪C
B⚪ : ⚪Ⓒ
Ⓑ⬛ : 🎂
Ⓑ⚪ : ⚪Ⓕ
⬛C : D⚪
⚪C : Ⓓ⚪
Ⓒ⬛ : ⬛B
Ⓒ⚪ : ⬛Ⓑ
D⬛ : ⚪E
D⚪ : ⚪Ⓔ
⬛Ⓓ : C⬛
⚪Ⓓ : Ⓒ⬛
⬛E : A⚪
⚪E : Ⓐ⚪
Ⓔ⬛ : ⬛D
Ⓔ⚪ : ⬛Ⓓ
Ⓕ⬛ : ⚪C
Ⓕ⚪ : ⚪Ⓒ
⬛🎂 : 🎂
⚪🎂 : 🎂
🎂⬛ : 🎂
🎂⚪ : 🎂

Aqui está uma versão ASCII , caso esse unicode não seja exibido bem para todos.

Prova

Isso é equivalente ao melhor candidato atual para um castor de seis estados ocupados . Um castor ocupado é uma máquina de Turing que pára depois de muito tempo. Por causa disso, a cadeia de origem ←A→pode realmente ser transformada na cadeia de destino ←🎂→, mas somente após mais de 7*10^36534etapas, o que levaria muito mais tempo que a idade do universo para qualquer implementação física.

A fita da máquina de Turing é representada pelos símbolos ⬛(0) e ⚪(1). As regras

← : ←⬛
→ : ⬛→

significa que as extremidades da fita sempre podem ser estendidas com mais zeros. Se o cabeçote da máquina de Turing chegar perto de uma extremidade da fita, podemos aplicar uma dessas regras, o que nos permite fingir que a fita é infinita e começa preenchida com todos os zeros. (Os símbolos →e ←nunca são criados ou destruídos, por isso estão sempre no final da fita.)

A cabeça da máquina de Turing é representada pelos símbolos ABCDEⒶⒷⒸⒹⒺⒻe 🎂. Asignifica que a cabeça está no estado Ae o símbolo embaixo da cabeça é um ⬛(0), enquanto Ⓐ significa que está no estado Ae o símbolo embaixo é um ⚪(1). Isso é continuado para os outros estados, com a letra circulada representando um 1 embaixo da cabeça e a versão sem círculo representando um 0. (Não existe símbolo Fporque acontece que a cabeça nunca termina no estado Fcom um 1 embaixo dela.)

O estado 🎂é o estado de parada. Tem regras especiais

⬛🎂 : 🎂
⚪🎂 : 🎂
🎂⬛ : 🎂
🎂⚪ : 🎂

Se o estado de parada for atingido, podemos aplicar repetidamente essas regras para "sugar" toda a fita (incluindo zeros extras que surgiram ao estender a fita mais do que o necessário), deixando-nos no estado ←🎂→. Portanto, o problema da acessibilidade se resume a saber se o estado 🎂será alcançado.

As regras restantes são as regras de transição para a máquina de Turing. Por exemplo, as regras

A⬛ : ⚪B
A⚪ : ⚪Ⓑ

pode ser lido como "se a máquina estiver no estado A e houver um zero embaixo da cabeça, escreva 1, mude para o estado B e mova para a direita". Mover para a direita requer duas regras, porque a célula de fita para a direita pode conter a ⬛, nesse caso a máquina deve entrar em estado B, ou a célula pode conter a ⚪, nesse caso, deve entrar em estado Ⓑ, pois existe uma ⚪por baixo.

Similarmente,

⬛Ⓓ : C⬛
⚪Ⓓ : Ⓒ⬛

significa "se a máquina estiver no estado D e houver 1 sob a cabeça, escreva 0, mude para o estado C e mova para a esquerda".

A máquina de Turing usada foi descoberta por Pavel Kropitz em 2010. Embora seja frequentemente mencionada no contexto de castores ocupados, sua tabela de transição real é um pouco difícil de rastrear, mas pode ser encontrada aqui, por exemplo . Pode ser escrito como

    0   1

A   1RB 1LE
B   1RC 1RF
C   1LD 0RB
D   1RE 0LC
E   1LA 0RD
F   1RH 1RC

que pode ser lido como "se a máquina estiver no estado A e houver um zero embaixo da cabeça, escreva 1, mude para o estado B e mova para a direita" e assim por diante. Deve ser simples, se trabalhoso, verificar se cada entrada desta tabela corresponde a um par de regras, conforme descrito acima.

A única exceção é a regra 1RHque ocorre quando a máquina está no estado F acima de 0, porque parecia bastante inútil fazer a máquina escrever 1 e mover-se para a direita quando podia parar imediatamente assim que entra no estado F acima de 0. Então mudei a regra que teria sido

Ⓑ⬛ : ⚪F

para dentro

Ⓑ⬛ : 🎂

É por isso que não há símbolo Fno alfabeto. (Existem alguns outros "campos de golfe" que eu poderia ter feito, mas não queria obscurecer muito.)

É basicamente isso. A sequência de destino é alcançável a partir da sequência de origem, mas somente após um número ridículo de etapas.

Mais um fato divertido: se eu tivesse usado

←A⚪⚪→

como ponto de partida, não seriam necessárias 7*10^36534etapas para interromper, mas 10^10^10^10^18705352etapas, que é realmente um número muito grande.

48 pontos, quebrado por bb94

Alfabeto: abc
Origem: cbaabaabc
Alvo: cbacbcabc
Regras de reescrita:

ab: ba
bc: cb
ca: ac
ab: cc
bc: aa
ca: bb

287 pontos, seguro

Fonte: YAAT

Alvo:

VW644507203420630255035757474755142053542246325217734264734527745236024300376212053464720055350477167345032015327021403167165534313137253235506613164473217702550435776242713

Regras:

T:AAAAAT
T:BBU
U:BU
U:ZW
AB:BCA
CB:BC
AZ:Z
CZ:ZC
YB:Y
YZ:V
V:VD
DCC:CD
DCW:W+
DW:W_
___:0
__+:1
_+_:2
_++:3
+__:4
+_+:5
++_:6
+++:7

Eu descobri que o openssl é muito mais fácil de usar do que o gpg para esse fim.

Veja o crack do HyperNeutrino para a versão mais fraca. Nesse caso, o número de Cs é:

22030661124527021657244569669713986649562044939414344827127551659400215941242670121250289039666163853124410625741840610262419007778597078437731811349579211

E os principais fatores são:

220040395270643587721928041668579651570457474080109642875632513424514300377757
100120985046540745657156603717368093083538096517411033964934953688222272684423

O primeiro número mod 5 = 2, portanto, é possível obter a sequência final.

402 pontos

Alfabeto: abcdefghijklmnopqrstu
Origem: abcdoi
Alvo: ioabcdnnnnnnnnnnnnnnnnnn
Regras de reescrita:

ab: ba
ba: ab
ac: ca
ca: ac
anúncio: da
da: ad
bc: cb
cb: bc
bd: db
db: bd
cd: dc
dc: cd
na: um
nb: bn
nc: cn
nd: dn
nm: mn
nj: jn
aoi: eag
boi: ebg
coi: ecg
doi: edg
ae: ha
be: hb
ce: hc
de: hd
ioa: kam
iob: kbm
ioc: kcm
iod: kdm
ma: aj
mb: bj
mc: cj
md: dj
dg: rdnnnnnnnnnn
cg: qcnnnnn
bg: pbnn
ag: fan
cr: fc
br: fb
ar: fa
bq: fb
aq: fa
ap: fa
er: io
eq: io
ep: io
ef: io
hf: io
kd: dunnnnnnnnnn
kc: ctnnnnn
kb: bsnn
ka: aln
uc: cl
ub: bl
ua: al
tb: bl
ta: al
sa: al
um: oi
tm: oi
sm: oi
lm: oi
lj: oi
: n

A última regra permite que você crie quantos ns precisar.

Por mais feio que pareça, na verdade é bem legal, de um jeito ou de outro ...

1337 Pontos

Definitivamente não é competitivo e demorou muito para ser criado (espero não ter me enganado).

Dica:

tente entender a string de origem antes de examinar as regras

Alfabeto: ABEILRSTabcdefijlr

Fonte: SIbbbbbbbdbffacebbfadbdbeecddfaeebddcefaddbdbeeecddaaaaadfaeeebdddcefbbfadbdbdbeeecdddfaeeebdddcefaddbdbeeecddaaaadfaeeebdddcefbfadbdbdbeeecdddfaeeebdddcbdbffacebfadbdbeecddfaeebddceeefadddbdbeeeecddddfaeeeebddddceefaddbdbeeecdddfaeeebdddceefadadbefadfacdbeecddfaeebddcefaeeefaddbdbeeecdddfaeeebdddcceecdfaeeaddceecefaeadcbefadfacecdfaebdceeeeefadddddbdbeeeeeecddddddfaeeeeeebddddddceeefaddaeecdddbdbffacebfadbdbeecddfaeebddceeefadddbdbeeeecddddfaeeeebddddceefaddbdbeeecdddfaeeebdddceefadadbefadfacdbeecddfaeebddcefaeeefaddbdbeeecdddfaeeebdddcceecdfaeeaddceecefaeadcbefadfacecdfaebdcefaefaeeebdddcdcefaceeaaaceefacdffacebdceeeeefadddddbdbeeeeeecddddddfaeeeeeebddddddceeefaddaeecdddbdbffacebfadbdbeecddfaeebddceeefadddbdbeeeecddddfaeeeebddddceefaddbdbeeecdddfaeeebdddceefadadbefadfacdbeecddfaeebddcefaeeefaddbdbeeecdddfaeeebdddcceecdfaeeaddceecefaeadcbefadfacecdfaebdcefaefaeeebdddcdcefaceeaaaaceefacdffacebdcecefacE

Alvo: SE

Regras de reescrita:

Ab: bA
bA: Ab
Aa: aA
aA: Aa
Anúncio: dA
dA: anúncio
Ae: eA
eA: Ae
Af: fA
fA: Af
Ac: cA
cA: Ac
IA: AI
AI: IA
Bb: bB
bB: Bb
Ba: aB
aB: Ba
Bd: dB
eB: Be
Be: eB
dB: Bd
Bf: fB
fB: Bf
Bc: cB
cB: Bc
E: BE
S: SB
Ib: AbI
AIa: aI
IdB: dBI
BIe: eIB
AIf: AfI
BIfB: BfiLB
Lb: bL
La: aL
Le: eL
Ld: dL
Se: fL
Lc: cL
ib: bi
ia: ai
ie: ei
id: di
if: fil
lb: bl
la: al
le: el
ld: dl
Se: fl
lc: cl
icl: ci
icL: cI
Ic: jRc
bj: jb
aj: ja
dj: jd
ej: je
br: rb
ar: ra
dr: rd
er: re
fr: rf
cr: rc
bR: Rb
aR: Ra
dR: Rd
eR: Re
fR: Rf
cR: Rc
cj: jrc
fjr: jf
fjR: se
ISTO
TB: T
BT: T
bT: T
aT: T
dT: T
eT: T
fT: T
cT: T
T:

Note que cometi alguns erros inicialmente, então a pontuação foi alterada. No entanto, a ideia é a mesma. Espero que não haja mais erros agora.

154 Pontos

Alfabeto: P.!xABC[{mD<
Fonte: [x!P.P...P..P.P....P..P.P.....P.P....P......P.P..P...P.P...Pm(61 caracteres)
Alvo: {CCCCC<(existem 5 Cs, portanto 7 caracteres)

Regras:

P.  →  .PP
!.  →  !
x   →  AxB
x   →  
AB  →  BAC
CB  →  BC
CA  →  AC
[B  →  [
[A  →  {
{A  →  {
!   →  !m
mP  →  PmD
Dm  →  mD
DP  →  PD
!P  →  ?
?P  →  ?
!m  →  <
<m  →  <
C<D →  <

Existem 19 regras, número total de caracteres = 67.

106 pontos - rachado por HyperNeutrino

Alfabeto: ABCDEFGHIJ

Fonte: FIABCJAGJDEHHID

Alvo: F

Regras de reescrita:

B:DCIE
A:IFBA
D:EEFJ
C:GFIC
E:HBJG
F:FEBG
G:HFCJ
H:DIGB
I:FCAH
J:BHEA

EJGI:FF
FFF:J
FF:E
EE:D
DDEA:FI
I:F

Ok, o HyperNeutrino provou que isso é insolúvel. No entanto, existe outra solução para isso.

Toma:

I E C D H G J A F B
1 2 3 4 5 6 7 8 9 10

O valor da fonte é par. O valor do alvo é ímpar. Se considerarmos cada lado, totalizar o valor e levar o valor para o mod 2, os valores permanecerão os mesmos. Portanto, isso não pode ser alcançado.