Uma rotação de uma string é feita dividindo uma string em duas partes e revertendo sua ordem, por exemplo, "world! Hello,"é uma rotação de "Hello, world!". É possível criar programas que podem ser rotacionados para formar um programa diferente, mas ainda válido. Considere este exemplo em python:
print ")import sys; sys.stdout.write("
Pode ser girado para formar
import sys; sys.stdout.write("print ")
O qual é um programa python válido.
Seu desafio é escrever um programa que produza uma rotação própria que, quando executado, gera o programa original. O bônus aponta para qualquer entrada com uma duração de ciclo superior a dois!
Este é o código de golfe, a pontuação exata será: (comprimento do código) / (duração do ciclo - 1).
EDIT: Temos um vencedor (a menos que alguém seja capaz de vencer uma pontuação de 4)! Eu ainda estaria muito interessado em ver outras soluções, sejam elas concorrentes ou não.
fonte
Respostas:
APL (158 caracteres, pontuação = 4)
Estou usando o Dyalog APL aqui. O número de ciclos pode ser aumentado em um adicionando
0(0 seguido de um espaço) ao final da expressão e ao final da string (antes'''). A duração do ciclo é(# 0's) + 1e a duração da expressão é150 + 4*(cycle length)). Supondo que continuemos adicionando zeros para sempre, a pontuação éLimit[(150 + 4*n)/(n - 1), n -> Infinity] = 4ondenestá a duração do ciclo.Aqui está um exemplo com duração do ciclo = 6:
192 caracteres, pontuação = 2
Dependendo da implementação, um ponto de falha pode ser quando o número inteiro prefixado na sequência for muito grande. Teoricamente, no entanto, podemos adicionar um ciclo adicionando dois caracteres - um
1no final da string (antes''') e um1no final de toda a linha.200 caracteres, pontuação = 1
Minha implementação de APL não possui números inteiros de precisão ilimitados por padrão; portanto, o número inteiro é convertido em um número flutuante quando se torna muito grande, causando uma saída incorreta. Portanto, este é o mais exigente, mas teoricamente (à mão ou com um intérprete de APL diferente), ele deve ter uma pontuação de 1. Basta adicionar
1a ao final da expressão e você obterá outro ciclo.Visão geral (com uma solução mais curta)
Vou dar uma visão geral da primeira versão, porque acho que é provavelmente a mais fácil de entender. Antes de abordar essa versão, no entanto, consideraremos uma solução simples no APL :
Descobri que uma das melhores maneiras de entender algumas expressões de APL é observar a saída em toda a cascata de operadores / funções. Todos os operadores e funções no APL são associativos à direita e têm a mesma precedência, então aqui está, da direita para a esquerda:
'''1⌽22⍴11⍴''': Esta é apenas uma string literal (uma lista de caracteres).''é a maneira da APL de escapar de aspas simples. Saída:'1⌽22⍴11⍴'.11⍴'''1⌽22⍴11⍴''': Aqui, remodelamos (⍴) a string para ser de comprimento11. Como o comprimento da string é inferior a 11, ele é repetido (ou seja,5⍴'abc'renderia'abcab'). Saída:'1⌽22⍴11⍴''. Portanto, agora temos duas aspas no final - estamos chegando a algum lugar!22⍴11⍴'''1⌽22⍴11⍴''': Da mesma forma, agora remodelamos nossa saída anterior para ser longa22. Saída:'1⌽22⍴11⍴'''1⌽22⍴11⍴''. Estamos quase chegando - precisamos apenas mover a primeira citação única para o final.1⌽22⍴11⍴'''1⌽22⍴11⍴''': Aqui, rotacionamos (⌽) a lista de caracteres por1. Isso move o primeiro caractere da string para o final. Como outro exemplo,2⌽'abcdef'retorna'cdefab'. Saída:1⌽22⍴11⍴'''1⌽22⍴11⍴'''.Quine rotativo
Esse quine curto é a base principal do nosso quine rotativo. Agora, com isso em mente, vamos dar uma olhada em nosso quine:
{ ... }define uma função sem nome, que é onde faremos o trabalho. Observe que as funções no APL usam um argumento à direita, denotado por⍵, e um argumento opcional à esquerda, denotado por⍺(think infix). Queremos alimentar essa função tanto com a nossa cadeia quine quanto com algo que nos ajude a criar um número arbitrário de ciclos. Para facilitar as coisas para nós mesmos (e para quem deseja adicionar ciclos), tornamos a sequência quine o argumento da esquerda. O argumento certo, então, é onde colocamos nossa lista de ciclos. 2 ou mais itens separados por um espaço criam uma lista; portanto, neste exemplo, temos uma lista de 2 elementos composta por a1e a0.Podemos ver que a função se parece com a quine de antes. Temos a mesma
...⌽...⍴...⍴...forma de antes. Então isso é bom - pelo menos entendemos isso! Vamos aprofundar as elipses, começando com tudo após o último⍴:⊃,/(~^/¨⍺=0)/⍺.⍺=0retorna uma lista, nesse caso, com a mesma forma que⍺, em que cada elemento⍺é substituído por a1se for igual a0e por0outro. Isso é realizado recursivamente; portanto, se tivermos uma lista de uma lista de caracteres, os caracteres individuais serão testados em relação a 0 e você receberá uma lista de uma lista de valores binários.⍺consiste apenas em nossa string, retornamos uma lista de zeros. Caso contrário, nosso argumento esquerdo possui alguns 0's prefixados (por exemplo,0 0 0 'quinestring'), portanto, é uma lista que consiste em 0's e outra lista, nossa string. Então nossa saída se parece1 1 1 <sub-list of zeros>.^/¨⍺=0: Aplicamos a função derivada^/, que reduz (/) usando a função lógica AND (^), a cada¨elemento ( ) de⍺=0. Isso é para achatar a sub-lista de zeros, para que possamos considerar a string quine como um valor binário. Considerando o exemplo anterior, a saída seria1 1 1 0.~: Nós binários NÃO cada um dos valores de antes (por exemplo, retornando0 0 0 1).(~^/¨⍺=0)/⍺: Para cada elemento em⍺, replicamos (/) o número de vezes fornecido pelo elemento correspondente no argumento esquerdo. Isso elimina todos os 0s, deixando-nos apenas com nossa string de quine.⊃,/é uma documentação necessária para garantir que recebamos de volta uma lista achatada de caracteres, reduzindo o resultado com a função de concatenação (,). Se a entrada já é uma lista achatada (ou seja, o argumento esquerdo da nossa função principal é apenas a string), obtemos uma lista de 1 elemento contendo essa lista. No outro caso, quando temos uma lista que consiste em uma sub-lista para a string, obtemos a mesma coisa de volta (uma lista com uma sub-lista). Em seguida, descompactamos this (⊃), fornecendo apenas o primeiro elemento da lista (ou seja, a sub-lista de caracteres). Isso pode parecer desnecessário, mas, caso contrário, estaríamos tentando remodelar uma lista de 1 elemento!A seguir, examinamos o comprimento fornecido para a primeira remodelação, entre parênteses:
⍺,⍵: Concatenamos o argumento correto para o primeiro argumento⊃,/⍺,⍵: O mesmo de antes - achatar a lista.+/0=⊃,/⍺,⍵: Adicione o número de zeros na lista reduzindo (/) usando a+função de adição ( ).2×+/0=⊃,/⍺,⍵: Multiplique esse número por dois.z←2×+/0=⊃,/⍺,⍵: Atribua (←) o resultado a uma variávelz,. Para recapitular,zagora é o dobro do número de zeros encontrado nos argumentos esquerdo e direito.77+z←2×+/0=⊃,/⍺,⍵: Em seguida77, adicionamos , para os caracteres na sequência quine, ignorando tudo após o espaço a seguir1. Como no exemplo inicial de quine, adicionamos 1 ao comprimento da string para obter outra aspas simples.'{(((3+z)×^/⍵)-5+2×+/+/¨⍺=0)⌽(2×77+z)⍴(77+z←2×+/0=⊃,/⍺,⍵)⍴⊃,/(~^/¨⍺=0)/⍺}1 0 ''O argumento para a remodelagem a seguir é simples e reflete o quine curto (2 vezes o comprimento da primeira remodelagem). Nossa saída agora é:
Agora, para a etapa final, onde calculamos quanto girar a sequência de saída:
0(e outro espaço) também se mova para o início, queremos girar mais três caracteres para trás.+/+/¨⍺=0: Adicione o número de zeros no argumento esquerdo . O primeiro (da direita)+/¨soma a contagem de cada elemento (ou seja, uma sub-lista ou apenas um número inteiro), e o segundo+/nos fornece a soma dessa lista resultante.5+2×+/+/¨⍺=0: Multiplique por dois (para girar os espaços também) e adicione 5 (o resultado que vimos antes).-para lidar com o caso quando chegamos ao final do nosso ciclo:(3+z)×^/⍵: E todos os elementos no argumento certo juntos para ver se chegamos ao fim (1) e multiplicamos por3+z.E nós terminamos!
fonte
⍴operador (?). Acho que vou ter que ler a coisa toda mais algumas vezes antes de digeri-la completamente!GolfScript, 10046/9999 ≈ 1,0047 (pontuação assintótica 1)
OK, vou tentar vencer a entrada de APL da DC com isso:
O código acima não é o quine real - senti que postar uma linha de 10kB não seria uma boa idéia. Em vez disso, executar o código acima uma vez produz o programa GolfScript de 10046 caracteres, que, quando iterado conforme especificado na pergunta, gera 9999 rotações de si mesmo e, finalmente, novamente.
A duração do ciclo (e o programa) pode ser ajustada alterando a constante
9999. Por questões de brevidade e conveniência, mostrarei como será a saída iterada se a constante for reduzida para9:À medida que a constante
9999aumenta, a proporção da duração do programa e da duração do ciclo (menos um) tende a um. Tenho certeza de que esta solução não pode ser derrotada, pelo menos não assintoticamente. ;-)Como funciona?
O GolfScript é uma linguagem bastante fácil de escrever quines, uma vez que basicamente qualquer número literal atua como um quine: por exemplo, o programa GolfScript
12345produz - você adivinhou -12345. Além disso, a concatenação de vários quines normalmente produz um quine. Assim, eu poderia usar um número simples como11111...111parte repetitiva da minha rotina cíclica.No entanto, para que o quine efetue o ciclo, precisamos transportar e executar uma "carga útil" não trivial. A solução mais simples que eu poderia pensar sobre o GolfScript que pode fazer é o seguinte:
Portanto, meu plano era prefixar um quine como esse com uma constante numérica repetitiva e usar uma carga útil que retirasse um dígito do número e o movesse para o final do programa. Se os detecta programa que é não constante numérica em frente da mesma (no caso em que o valor abaixo dela na pilha vai ser uma cadeia vazia, assumindo que não há entrada), que será em vez preceder uma constante numérica de comprimento fixo na frente de em si.
Porém, há uma ruga adicional - ao "contornar", a carga útil também deve suprimir a saída do número depois de si mesma. Normalmente, quando um programa GolfScript termina, todos os valores na pilha são impressos automaticamente, o que seria um problema aqui.
No entanto, existe uma maneira não documentada (AFAIK) de evitar isso: o intérprete realmente chama a função predefinida
putspara fazer a impressão, portanto, redefinir essa função como não-op suprime a saída automática. Obviamente, isso também significa que devemos primeiroputsnos chamar para imprimir a parte da pilha que queremos imprimir.O código final parece bastante confuso (mesmo para o GolfScript), mas pelo menos funciona. Suspeito que possa haver algumas maneiras inteligentes de eu ainda não ter pensado em cortar alguns caracteres da carga, mas para esta versão, eu estava focando principalmente na pontuação assintótica.
fonte
puts{}:puts, embora eu pudesse ver um argumento com{print}:putsbase no fato de que uma nova linha na saída significaria que não é estritamente de bicicleta.]puts{}:putsnecessário para a transição de{STUFF}.~111111111para111111111{STUFF}.~, caso contrário, o número de1s no final do programa continua crescendo e crescendo. (The{}parece ser desnecessário, embora, aparentemente, o intérprete GolfScript permite a atribuição de uma pilha vazia.)HTML, menos infinito (quase)
-2
AA-10
AAAAAAAAAAE assim por diante ... Se alguém disser que é trapaça, podemos discutir sobre isso, mas eu encontrei um buraco em questão :)
Então, eu acho que todo mundo entende que o código tem, ele não tem loops, então o loop mais longo é
0e, considerando o tamanho do programan, score én / (0 - 1)ou-n, eu posso escrever um programa que tenha onnúmero inteiro positivo grande, mas é inútil, porque todo mundo entende.fonte