Visualize o algoritmo euclidiano

17

O algoritmo euclidiano é um algoritmo amplamente conhecido para calcular o maior divisor comum (MDC) de dois números inteiros positivos.

O algoritmo

Para os propósitos deste desafio, o algoritmo é descrito abaixo:

  1. Exiba as duas entradas como linhas adjacentes de um determinado caracter,
    por exemplo, uma entrada de 3,4pode ser representada pelas linhas adjacentes 000e0000

  2. Transforme os primeiros length(short_line)caracteres na linha mais longa em outro, diga -
    agora que parece 000e---0

  3. Elimine os primeiros length(short_line)caracteres na linha mais longa.
    agora 000,0

  4. Repetir os passos 2 e 3 até que os dois têm a mesma duração, utilizando as linhas mais curtas e mais longas depois de cada iteração, por exemplo
    000, 0
    -00, 0
    00, 0
    -0, 0
    0,0

  5. Você pode optar por parar aqui ou continuar a iteração e transformar uma das linhas em uma linha vazia.

Cada uma dessas etapas deve ser separada por um intervalo entre 0,3s e 1,5s.

O desafio

Escreva um programa que, dados dois números naturais como entrada, crie uma saída exatamente igual à saída do algoritmo acima. Você pode usar outros caracteres ASCII imprimíveis que não sejam espaços em branco além de 0e -, mas seja consistente e use apenas dois caracteres. Você também pode usar algoritmos alternativos, desde que a saída, incluindo o tempo, seja exatamente a mesma que seria produzida pelo algoritmo acima.

Exemplos

Este é um exemplo com entrada 24,35, que são coprimes, portanto seu GCD é 1.

insira a descrição da imagem aqui

Este é um exemplo com entrada 16,42, que possui o GCD 2.

insira a descrição da imagem aqui

Regras


Esclarecimentos

  • As linhas que representam os números precisam permanecer em sua ordem original, ou seja, a primeira e a segunda linhas do primeiro "quadro" exibido precisam ser a primeira e a segunda linhas, respectivamente, em todos os quadros subsequentes.
  • Depois que o algoritmo termina, nenhuma entidade visível adicional deve aparecer. No entanto, isso também significa que não há problema em deixar as linhas em branco, se você garantir que o último "quadro" seja exibido pelo menos na mesma quantidade de tempo que todos os outros quadros antes de apagar.
busukxuan
fonte
@WheatWizard ótima sugestão, sobre ele
busukxuan
As linhas precisam permanecer na mesma ordem relativa? Ou eles podem ser reordenados entre iterações? (Verificando porque o último provavelmente é muito mais conciso na maioria dos idiomas, e, portanto, preciso saber se devo usar essa otimização ou ignorá-la devido à violação do sepc.)
@ ais523 Sim, eles fazem:-)
busukxuan
@ ais523 Sim é aprovado em branco, mas certifique-se o último quadro é dado o mesmo tempo de exibição como os outros quadros
busukxuan
11
@busukxuan Pessoalmente, eu acho que eu iria permitir espaços à direita, mas talvez não o espaço como um dos personagens "significativas"
Luis Mendo

Respostas:

3

Gelatina , 29 bytes

VY“ñc‘ỌœS.⁸
1ẋǵ+M¦ṚÇt€2ǵ⁻/¿

Experimente online!

Isso define uma função 2Ŀ(não um programa completo; o link TIO contém um rodapé que converte uma função em um programa) que pega uma lista de dois elementos como entrada e exibe a saída na tela (um dos nossos métodos legais de E / S , e que é meio que necessário para esse desafio, porque fala sobre a aparência na tela). Isso pressupõe que o programa seja executado em um terminal que esteja em conformidade com o padrão ANSI (eu usei, gnome-terminalmas a maioria funcionará) e que o terminal esteja inicialmente vazio (o que parece ser o padrão mais sensato); note que Experimente online! não está de acordo com essas suposições e, portanto, a saída é distorcida (executei o programa localmente para verificar se ele anima como esperado). Eu uso 1onde a pergunta usa 0e2no lugar de -.

Explicação

Função auxiliar 1Ŀ (dada uma lista de duas listas de dígitos, as gera na primeira e na segunda linhas da tela e aguarda 0,5 segundos; retorna sua entrada)

VY“ñc‘ỌœS.⁸
V                   Convert each list of digits to an integer
 Y                  Separate these integers by newlines
  “ñc‘              {Output that; then restart with} the list [27, 99]
      Ọ             Convert codepoints to characters (i.e. "\x1bc"
       œS.          Wait (œS) 0.5 (.) seconds
          ⁸         {Output that; then return} the initial argument

A cadeia "\ x1bc", quando enviada para um terminal compatível com ANSI, é interpretada como um código de controle para redefinir o terminal; isso limpa a tela e move o cursor para o canto superior esquerdo (redefinindo assim o terminal pronto para a próxima saída).

A função auxiliar é chamada 1Ŀ (o Jelly gera automaticamente nomes desse formulário para funções e, de fato, não há outra maneira de nomeá-los), mas pode ser referido simplesmente a Çpartir do programa principal (porque o idioma possui abreviação de funções com números próximos) )

Função principal 2Ŀ (implementa a tarefa solicitada na questão)

1ẋǵ+M¦ṚÇt€2ǵ⁻/¿
1ẋ                  Convert input to unary
  Ç                 Call helper function (producing one animation frame)
   µ         µ  ¿   While
              ⁻/      the elements differ:
     M¦               Change the largest element
    +  Ṛ                by adding corresponding elements of the other element
        Ç             Call helper function (producing one animation frame)
         t€2          Delete all 2s from each side of each element
            Ç         Call helper function (producing one animation frame)

fonte
6

JavaScript (ES6), 128 124 bytes

t=0
f=
(a,b,o,c,d)=>setInterval(e=>{e=[b,d,a,c];o.data=`-0
-0`.replace(/./g,c=>c.repeat(e.pop()));c|d?c=d=0:a>b?a-=c=b:b-=d=a},1e3)
<form><input id=a><input id=b><button onclick=clearTimeout(t),t=f(+a.value,+b.value,o.firstChild)>Go!</button><pre id=o>

Neil
fonte
3

Python 2 , 152 146 bytes

import time
s,o='-0'
a,b=input()
while a*b:
 d,e=o*a,o*b
 if a>b:a=a-b;d=s*b+o*a
 elif b>a:b=b-a;e=s*a+o*b
 else:a=0
 print d+'\n'+e;time.sleep(1)

Experimente online!


Toma dois números inteiros separados por vírgula como entrada

ovs
fonte
Essa é uma boa resposta.
ElPedro
2

Javascript (ES6), 215 194 ... 135 129 127 bytes

a=>b=>F=(c=0)=>alert('-'[d='repeat'](e=c&a>b&&b)+'0'[d](a-=e)+`
`+'-'[d](f=c&a<b&&a)+'0'[d](b-=f))|a-b|c&&setTimeout(F,1e3,1-c)

Uso

Isso leva em consideração uma variação no curry. Para usá-lo, primeiro atribua a função a uma variável (por exemplo G) e chame-a assim:

G(5)(6)()

Explicação

Função um pouco recursiva que se chama após 1 segundo, desde que o algoritmo não tenha terminado. Ele controla uma terceira variável cque determina se ae bdeve ser alterada (se cfor 1, é hora de mudar).

Primeiro, a função grava algo no console. Se cfor 0, ele grava duas seqüências de zeros com uma nova linha entre elas. Como cé inicializado 0, podemos tirar proveito disso e configurar variáveis ​​globais fe gque contêm algumas strings que precisamos com frequência (como0 e repeat).

Caso contrário, ele cria uma string com zeros e menos. Todas essas strings consistem em duas partes: primeiro alguns (chamam esse valor A) menos, depois alguns (chamam esse valor B) zeros, depois uma nova linha, depois alguns (chamam esse valor D) menos e, finalmente, alguns (chamam esse valor)E ) zeros.

Se a primeira entrada for menor que a segunda entrada, precisamos remover os zeros da segunda entrada, assim Aé zero, Bigual à primeira entrada, Digual à primeira entrada e Eigual à segunda entrada menos a primeira entrada. Se a primeira entrada não for menor que a segunda entrada, o inverso será aplicado ( Aé a segunda entrada, Bé a primeira entrada menos a segunda entrada etc.).

Com esses novos valores para a entrada e uma variável comutada c, a função está programada para ser chamada novamente em 1e3milissegundos, o que equivale a um segundo.

Notas

  • Usa alertpara saída
  • Usa 0e -, assim como nos exemplos
  • O atraso entre as etapas é de 1000 ms (1 segundo)
  • Após o primeiro passo, a função retornará (devido à natureza do JavaScript) algum número que deve ser ignorado
  • A versão no TIO gera tudo de uma vez, colar o código no console do navegador levará em consideração os atrasos

Experimente online

Experimente aqui!

Lucas
fonte
2

Python 2 , 208 204 194 bytes

-4 com agradecimentos a @math_junkie pelo truque sorrateiro com time.sleep

-10 com agradecimentos a @busukxuan por esclarecer a regra "tela limpa".

def z(a,b,y='-',w=1):
 import time;c,d,n,s='0'*a,'0'*b,'\n',time.sleep
 if w:print c+n+d;s(1)
 if b>a:d=y*a+d[a:]
 else:c=y*b+c[b:]
 print c+n+d;s(1)
 if c!=d:z(len(c),len(d),('','-')[y!='-'],0)

Experimente online!

Certamente isso poderia ser mais jogado. Dói-me duplicar o printe o forloop para criar a pausa, mas não consigo encontrar uma maneira de contorná-lo no momento.

Notas

  • A pausa agora usa uma dica de @math_junkie
  • Não funciona totalmente no TIO, pois armazena a saída e a despeja quando o programa termina. Funciona bem no console.
ElPedro
fonte
11
Você deve ser capaz de salvar alguns bytes utilizando import time, s=time.sleepe s(1)em vez de um loop para o atraso
viciado em matemática
Obrigado @math_junkie - Eu tentei a maioria das combinações usando, time.sleepmas perdi essa. Vai tentar.
ElPedro
@math_junkie - chega a 215 para mim. Talvez esteja faltando algo estúpido. Você pode postar um exemplo no Try it Online ?
ElPedro
11
Tente aqui
math junkie
1

perl, 161 149 bytes

... sem recuos e novas linhas:

($a,$b)=map 0 x$_,@ARGV;
sub p{say"\n$a\n$b";sleep 1}p;
while($a ne$b){
  ($A,$B)=$b lt$a?(\$a,\$b):(\$b,\$a);
  map$$A=~s/0/-/,1..length$$B;
  p;
  $$A=~s/-//g;
  p
}

Coloque-o em um arquivo gcd.pl e execute assim:

perl -M5.010 gcd.pl 16 42
Kjetil S.
fonte
11
O -M5.010sinalizador para perl é gratuito, portanto você pode salvar alguns bytes usando sayover print…\n. Além disso, tenho certeza de que é mais tenso atribuir um nome à sua sub-rotina anônima, em vez de armazená-la em uma variável.
Thx para ais523 para obter dicas para cortar 12 bytes
Kjetil S.
1

GNU Sed (com e extensão xec), 88

A pontuação inclui +3 para as -zrfopções de sed.

p
:
x
esleep 1
g
ta
:a
s/o+//p
t
s/^((O+)(O+)\n\2\b|(O+)\n\4\B)/\L\2\U\3\4\n\2\L\4\U/p
t

A entrada é fornecida como dois números inteiros unários separados por nova linha, usando maiúsculas O como dígitos.

Por exemplo, o exemplo 16, 42 pode ser executado como:

printf "%0*d\n%0*d\n" 16 0 42 0 | tr 0 O | sed -znrf euclidvis.sed

De acordo com os comentários mais recentes, não estou limpando a tela entre as iterações.

Trauma Digital
fonte
0

V , 47 44 bytes

Àé0á
Àé0Hqwmmjlhmmkl@wqòHî@w
gs`mlhv0r-gsÓ-ò

Experimente online!

O cabeçalho e rodapé no TIO são modificados gspara copiar as duas linhas atuais na parte inferior da tela e, em seguida, excluir as duas primeiras no final. Isso visualiza a operação do TIO, mas se você a executasse em V (sem o cabeçalho e o rodapé), esperaria apenas um segundo entre cada operação.

Àé0                     " Print (Arg1) zeroes
   á                    " Newline
Àé0                     " Print (Arg2) zeroes
   H                    " Go home
    qwmmjlhmmkl@wq      " Store a recursive macro in w that finds the shorter line
                  ò     " recursively
                   Hî@w " find the longest line
gs                      " wait a second
  `mlhv0r-              " replace the zeroes of the long line with -
          gs            " wait a second
            Ó-          " delete all -
              ò         " end recursion
nmjcman101
fonte
Você realmente precisa do final ò?
Kritixi Lithos 28/02
Ele trava sem ele, sem saber o porquê. Vai esperar até eu ter um computador com V nele para depurar qualquer
nmjcman101