Classificação básica, com bug irritante

28

Sua entrada é uma lista / sequência / vetor / matriz de 5-255 números inteiros positivos, não necessariamente exclusivos. Você pode assumir qualquer formato de entrada mais adequado e que cada número inteiro (assim como a quantidade de números inteiros) seja escolhido uniformemente aleatoriamente no intervalo 5-255.

O objetivo é gerar a mesma lista, no mesmo formato (ou equivalente), mas classificada em ordem crescente (não decrescente). Um exercício inicial comum no aprendizado de um idioma. Envios para incluir:

  1. Uma resposta que funciona corretamente e atinge a meta; e

  2. Uma segunda resposta que contém um bug irritante. Entre 1% e 10% do tempo, a saída precisa ser uma lista no formato correto e contendo os elementos corretos, mas na ordem errada (qualquer ordem, exceto a classificação correta). O restante do tempo, o programa deve funcionar corretamente e atingir a meta.

As duas respostas devem ter a distância de Levenshtein uma; isto é, podemos obter um do outro excluindo um byte ou adicionando um byte ou alterando um byte.

Pontuação como de costume no código-golfe (com base na menor das suas duas respostas), com brechas usuais proibidas.

Bônus de 10% (redução na pontuação) se o bug irritante for independente da entrada, ou seja, usar a mesma entrada novamente não reproduz o bug (exceto entre 1% e 10% do tempo).

code-golf array-manipulation random integer Vadim Ponomarenko
fonte
9
Bem-vindo ao PPCG! Sugiro remover o bônus, não é realmente uma boa prática.
Sr. Xcoder 4/11
2
Não está claro qual é a probabilidade de cada comprimento de entrada possível.
precisa saber é o seguinte
12
As especificações entre 1% e 10% do tempo devem ser cumpridas para cada entrada ou apenas no geral para o conjunto de possíveis entradas? Para algumas entradas como [5,5,5]é impossível produzir a ordem errada
Luis Mendo
4
Há uma sutileza em relação aos nossos formatos de E / S padrão . Se nosso código define uma função, tudo bem se houver alguma chance de definir a função de forma consistente com bugs, em vez de definir uma função com alguma chance de ser com bugs?
Xnor
1
@VadimPonomarenko Neste site, as pessoas podem fornecer funções, bem como programas completos. O xnor está perguntando se é permitido ter uma função que, 1% a 10% do tempo quando criada, é uma função de buggy que sempre terá um bug. Mantendo a letra da sua pergunta, a resposta provavelmente não é , mas seria mais divertido se fosse sim .
precisa saber é o seguinte

Respostas:

9

Python 3 , 36 bytes

Versão sem erros, 37 bytes

lambda l:sorted(l,reverse=l[-9:]==[])

Experimente online!

Versão irritante, 36 bytes

lambda l:sorted(l,reverse=l[9:]==[])

Experimente online!

Isso depende da entrada e, portanto, não se qualifica para o bônus.
Tem uma probabilidade de cerca de 2% falhar. Falha quando o comprimento da entrada é inferior a 10.

Combinado com a resposta do LyricLy, obtém 34 bytes:

lambda l:sorted(l)[::l[9:]>[]or 1]
lambda l:sorted(l)[::l[9:]>[]or-1]
ovs
fonte
Eu não acho que você precise do espaço na versão sem erros.
precisa saber é o seguinte
@ wizzwizz4 sem o espaço or1será interpretado como um nome de variável e gera um erro de sintaxe.
ovs 04/11/19
9

05AB1E , 5 * 0,9 = 4,5 bytes

Solução de trabalho

{TLΩi

Experimente online!

Explicação

{      # sort input
 TL    # push the range [1 ... 10]
   Ω   # pick a random number in the range
    i  # if true (equal to 1), do nothing

Solução contendo o bug

Fornece a solução errada 10% do tempo (independente da entrada).

{TLΩiR

Experimente online!

Explicação

O mesmo que a solução de trabalho, exceto que inverte a lista se o número escolhido for verdadeiro.

Emigna
fonte
Sério, o que oi. A saída nem é da cardinalidade correta.
Joshua
@ Josué Como assim?
Erik the Outgolfer 5/17
Experimente online mostra a saída de uma lista de listas.
Joshua
4
@ Josué O link TiO inclui um cabeçalho 100Fe um rodapé },que nos ajudam a visualizar o resultado da função chamada na entrada várias vezes. Isso nos mostra que a solução de trabalho sempre retorna resultados corretos, enquanto a solução com defeito apresenta falhas.
Xcoder
Por favor, alguém, explique o algoritmo. Em breve, aceitarei a submissão com melhor classificação (ou uma das submissões com melhor classificação). Não posso aceitar nenhuma solução que não possa entender.
Vadim Ponomarenko
7

Gelatina , 7 * (100% - 10%) = 6,3 bytes

Ṣ¹⁵X:¤¡

Experimente online!

Versão com buggy:

ṢẊ⁵X:¤¡

Experimente online!

Nos dois links, há um equipamento de teste que executará o código 100 vezes, sempre com a lista que você fornecer como argumento e, em seguida, retornará os resultados.

A probabilidade de cada comprimento de entrada é:

0.1 - 0.1/(length!)

Portanto, para o comprimento 1, há uma probabilidade de 0%, para o comprimento 2 5%, para o comprimento 3 8,83̅%, para o comprimento 4 9,583̅% etc. até o comprimento ∞ que tem 10% de probabilidade.

Erik, o Outgolfer
fonte
Deveria ser 0.1 - 0.1/(length!).
precisa saber é o seguinte
@ user202729 com certeza
Erik the Outgolfer 4/17
Ṣ⁵X’¤¡e também Ṣ⁵X¤¡deve funcionar: a versão com bugs retorna a lista sem classificação <10% do tempo e, como a entrada é escolhida uniformemente aleatoriamente, ela deve funcionar, economize 2 bytes.
precisa saber é o seguinte
Se você não gosta dessa solução, obviamente pode simplesmente excluir o ¹para salvar 1 byte (o número da contagem de regras de byte = o menor); Também há uma linha superior combinando estranhos após a segunda 6em 6.6̅%.
precisa saber é o seguinte
@ user202729 Infelizmente, não será mais independente de entrada, e não, não posso "apenas remover o ¹", porque não seria capaz de classificar 10% do tempo.
Erik the Outgolfer
6

Python 3, pontuação 58 57 - 10% = 51,3

Guardou um byte graças a ovs.

Versão sem erros, 57 bytes

lambda m:sorted(m)[::random()>.1or 1]
from random import*

Experimente online!

Versão com bug, 57 bytes

lambda m:sorted(m)[::random()>.1or-1]
from random import*

Experimente online!

Eu decidi tentar uma solução que use o bônus. Não supera a outra resposta do Python, mas eu me diverti pensando nisso.

LyricLy
fonte
5

C, 71 * 0,9 = 63,9 bytes

Sem erros:

c(int*a,int*b){return*a-*b;}f(a,n)int*a;{if(rand()%1<9)qsort(a,n,4,c);}

Experimente online!

Buggy:

c(int*a,int*b){return*a-*b;}f(a,n)int*a;{if(rand()%10<9)qsort(a,n,4,c);}

Experimente online!

Steadybox
fonte
+1 para% 1 (oh vêm em 6 de mais para ir Você tem que estar brincando comigo)
Joshua
4

Groovy , 31 bytes

Solução com bug:

{a->a.sort()[a[9]?0..-1:-1..0]}

Solução de trabalho:

{a->a.sort()[a[0]?0..-1:-1..0]}

O operador de subscrito Groovy (o getAtmétodo) retorna nulo para listas se o índice for maior que o tamanho. Portanto, se houver um nono elemento, ele permanecerá o mesmo da lista classificada, mas se não (1,99203187% de chance), será revertido. No entanto, sempre haverá um primeiro elemento, porque o tamanho da lista é sempre maior ou igual a 5. Portanto, o 0 in a[0]pode ser trocado por 1, 2, 3 ou 4.

Hlaaftana
fonte
1
Bem-vindo ao site e bom primeiro post!
caird coinheringaahing
3

Wolfram Language (Mathematica) , 29 bytes

São 26,1 bytes com o bônus, mas não tenho muita certeza de ganhar o bônus; na entrada já classificada, ambas as versões sempre produzem saída classificada.

Versão sem erros (29 bytes)

If[RandomReal[]<0.,#,Sort@#]&

Experimente online!

Versão irritante (30 bytes)

If[RandomReal[]<0.1,#,Sort@#]&

Experimente online!

Misha Lavrov
fonte
3

PHP, 70 bytes

Versão sem erros, 70 bytes

<?unset($argv[0]);((rand(1,9)?"":r).sort)($argv);echo join(" ",$argv);

Experimente online!

Versão com bug, 70 bytes

<?unset($argv[0]);((rand(0,9)?"":r).sort)($argv);echo join(" ",$argv);

Experimente online!

A versão com bug classifica na ordem inversa 10% do tempo (com base em um gerador de números aleatórios).

Jo.
fonte
não há necessidade da tag com -r(-2 bytes). junte por sublinhado; isso deve ser equivalente (-2 bytes). use em asortvez de sort(-1 byte).
Titus
... ou use a palavra inteira em vez do prefixo (ou não): unset($argv[0]);(rand(1,9)?sort:rsort)($argv);echo join(_,$argv);(também 65 bytes)
Titus
3

Python 2 , 26 bytes

Buggy:

lambda l:l[9:]and l.sort()

Experimente online!

Saídas modificando a lista de entrada . Classifica a lista apenas se seu comprimento for pelo menos 10. A versão sem bugs substitui a 9por a 0para sempre classificar.

Trabalhando:

lambda l:l[0:]and l.sort()

Experimente online!

Podemos modificar a função para retornar a lista ao custo de 4 bytes, para um total de 30 bytes:

lambda l:l[9:]and l.sort()or l

Experimente online!

25 bytes com alguns trechos das regras:

[list,sorted][id(0)%17>0]

Experimente online!

Gera uma literal de função que classifica ou é a identidade, usando id(0)como uma fonte aleatória. Altere >para >=corrigir ou 0para ~0.

xnor
fonte
3

Casca , 6 bytes

Versão com buggy:

?OIV¦9

Experimente online!

Versão correta:

?OIVK9

Experimente online!

Explicação

Esses programas são completamente determinísticos. De fato, Husk atualmente não tem suporte para números aleatórios.

?  V    If any element
    ¦9  is divisible by 9 (in buggy version),
    K9  is truthy when replaced by 9 (in correct version),
 O      sort the list,
  I     otherwise return it unchanged.

Afirmo que a saída do programa de buggy não é classificada com uma probabilidade entre 1% e 2%. Denote por N = 251 o número de valores possíveis dos elementos. A probabilidade de uma lista aleatória de comprimento L não conter múltiplos de 9 é ((NK) / N) ^ L , onde K é o número de valores divisíveis por 9 (no nosso caso, K = 28 ). A probabilidade total é a média disso para 5 ≤ L ≤ 255 , que é de cerca de 1,98%. Algumas dessas listas são falsos positivos, pois já estão classificadas. A probabilidade de uma lista aleatória de comprimento L a ser classificada é no máximo ((N + N * (N-1) / 2) / N ^ 2) ^ ⌊L / 2⌋ : se dividirmos a lista em pedaços de comprimento 2, cada um dosPedaços ⌊L / 2⌋ devem ser classificados. A probabilidade total de uma lista ser classificada é limitada pela média acima para 5 ≤ L ≤ 255 , que é de cerca de 0,30%. Portanto, a probabilidade da função retornar uma lista não classificada está entre 1,67% e 1,98%.

Zgarb
fonte
divisível por 9 dá aproximadamente 11% de chance de falha. e não classificar não garante que a lista não esteja classificada.
Titus
1
@Titus Abordo isso na análise. A falha na classificação ocorre apenas se a lista não contiver elementos divisíveis por 9. A probabilidade disso é de cerca de 1,98%. E é verdade que, se a lista já estiver classificada, não fazer nada também fornecerá uma lista classificada. No entanto, a probabilidade de a lista já estar classificada é de no máximo 0,30%, o que é baixa o suficiente para que a probabilidade total de gerar uma lista não classificada seja superior a 1%.
Zgarb
true ... e a entrada que está sendo classificada não altera o bug.
Titus
Você poderia usar em ↓9vez de V¦9reduzi-lo 9para a versão correta? Isso sempre falha em entradas curtas e sempre funciona corretamente em entradas mais longas, mas como o comprimento da entrada segue uma distribuição aleatória, ainda deve ser uma resposta válida
Leo
3

Bash , 26 bytes

Versão correta

s=n
sort -${s:RANDOM%20<0}

Experimente online! ou verifique as probabilidades .

Versão com bug

s=n
sort -${s:RANDOM%20<1}

Experimente online! ou verifique as probabilidades .

Recebe a entrada como números separados por nova linha. Usa a variável embutidaRANDOM , que sempre retorna um número aleatório (pseudo) no intervalo de 0 a 32767 . Usando %20resultados em cerca de 5% de taxa de falha (obrigado @Titus por esclarecer problemas com %10).

Essa aleatoriedade significa que a taxa de falha é independente da entrada, mas isso exige que a matriz de entrada inclua pelo menos um número com mais de um dígito, porque a saída da falha é classificada lexicograficamente.

Versão alternativa, 27 bytes

((RANDOM+20))||cat&&sort -n

Versão com bug substitui o +por um %. Experimente online ou tente com erros .

Justin Mariner
fonte
centavo picking: %10tem uma maior chance de retornar 0ao 7que 8ou 9, então a chance de fracasso é acima de 10%;)
Titus
@ Titus Obrigado, eu esqueci esse fato. Atualizado para usar %20como sua resposta.
perfil completo de Justin Mariner
3

Pitão , pontuação 8 * 0,9 = 7,2

Primeiro trecho (correto):

h.uSNT.S

Experimente aqui!

Segundo trecho (com bug):

O.uSNT.S

Experimente aqui!

Economizou dois bytes (e 1,8 pontos) graças ao isaacg !

Mr. Xcoder
fonte
Eu acho que 9 em vez de 10 novas cópias seriam boas. A possibilidade de .Sretornar a entrada inalterada significa que, nesses casos (raros), nossas chances de obter a resposta errada caem de 10% para 0% - portanto, em média, ainda está na faixa certa. Claro, 10 cópias também estão bem.
Misha Lavrov #
@MishaLavrov Cometi um erro na minha explicação, agora abordada. Eu disse .Sque também pode retornar a entrada em si (o que não seria um problema), mas quis dizer .Stambém pode retornar a lista classificada .
Xcoder #
Certo, foi o que eu quis dizer também.
Misha Lavrov #
Mesma idéia, mas mais curta:O.uSNT.S
isaacg 4/11
2

JavaScript (ES6), 24 bytes

Versão sem erros (pelo menos para números inteiros no intervalo 0-2147483647, portanto, qualquer coisa no intervalo fornecido):

a=>a.sort((a,b)=>a-b>>0)

Versão com buggy:

a=>a.sort((a,b)=>a-b>>1)

Depende de a) no algoritmo de classificação do mecanismo eb) na lista de entrada que contém dois valores na ordem errada que diferem em 1. (Se a probabilidade disso for muito baixa, ela 1poderá ser aumentada, mas quando você conseguir para 8ele simplesmente não vai resolver nada no intervalo 5-255.)

Neil
fonte
2

PHP, 62 bytes

inspirado na solução do Jo (e acabei de perceber: é um porto de Justin Mariner ):

trabalhando (classifica em ascensão):

unset($argv[0]);(r[rand()+20].sort)($argv);echo join(_,$argv);

carrinho (aproximadamente 5% de chance de classificação descendente):

unset($argv[0]);(r[rand()%20].sort)($argv);echo join(_,$argv);

Correr com -nr

Titus
fonte
2

Pushy , 9 bytes - 10% = 8,1

Solução com bug:

g0TUn?};_

Experimente online!

Solução de trabalho:

g1TUn?};_

Experimente online!

O código com bug faz o seguinte:

g0TUn?};_

g          \ Sort the stack correctly
 0TU       \ Generate random(0, 10)
    n? ;   \ If this is zero:
      }    \    Cyclically shift the stack right once
        _  \ Print the result

O código fixo simplesmente muda 0para 1. Como random(1, 10)nunca será 0, a instrução if nunca será executada.

FlipTack
fonte
2

MATL , 7 * 0,9 = 6,3 6 * 0,9 = 5,4 bytes

Versão com buggy:

Gr.9<?S

Experimente online!

Explicação:

G        % Grab input
 r       % Push a random number between 0 and 1
  .9     % Push 0.9
    <    % Check if the random number is smaller than 0.9
     ?   % If true
      S  % Sort input
         % Implicit output

Versão sem erros:

Gr9<?S

Experimente online!

Explicação:

G       % Grab input
 r      % Push a random number between 0 and 1
  9     % Push 9
   <    % Check if the random number is smaller than 9 (always true)
    ?   % If true
     S  % Sort the input
        % Implicit output
Stewie Griffin
fonte
1

Jq 1.5 , 42 bytes

Buggy

sort|if length%13<=0then reverse else. end

Trabalhando (exclua o =)

sort|if length%13<0then reverse else. end

Supondo que os comprimentos das linhas sejam uniformes no intervalo [5.255], cerca de 7% acionarão o bug

Experimente online!

jq170727
fonte
1

J, 22,5 bytes (25 bytes - 10%)

com bug:

[:]`(1&A.)@.(0.1>?@0:)/:~

sem bug:

[:]`(0&A.)@.(0.1>?@0:)/:~

Experimente online!

Jonah
fonte
1

R , 30 * .9 = 27 bytes

(carrinho)

function(l)sort(l,runif(1)<.1)

Experimente online!

(não de buggy)

function(l)sort(l,runif(1)<.0)

A versão com bugs é classificada em decreasing=T10% do tempo, amostrando a partir de uma distribuição uniforme (0,1). A versão un-buggy é sempredecreasing=F

Giuseppe
fonte
1

Röda , 42 bytes - 10% = 37,8

Sem erros:

{sort key={|i|currentTime|[_%20//19*0+i]}}

Buggy:

{sort key={|i|currentTime|[_%20//19*i+i]}}

Experimente online!

Isso usa a currentTimefunção para criar números aleatórios. Parece que sua distribuição varia um pouco entre as máquinas. A proporção 20//19pode ser ajustada para obter resultados diferentes, sem penalidade de bytes (a menos que seja menor que 99//98).

fergusq
fonte
1

Oitava , 36 * 0,9 = 32,4 bytes

Versão com buggy:

@(x)sort(x)(shift(1:end,+(rand<.1)))

Experimente online!

Versão sem erros:

@(x)sort(x)(shift(1:end,+(rand<.0)))

Experimente online!

Isso classifica o vetor e muda todos os números um para a direita se um número aleatório for menor que 0,1.

Stewie Griffin
fonte
Sim, você está, naturalmente, direito :) Thanks :)
Stewie Griffin
1

Java 8, 45 34,2 ( 50 38 - 10%) bytes

Versão normal:

a->{if(Math.random()>0.)a.sort(null);}

Explicação:

Experimente aqui.

a->{                    // Method with ArrayList<Integer> parameter and no return-type
  if(Math.random()>0.)  //  If the random 0-1 double is larger than 0:
    a.sort(null);       //   Sort the input-List
}                       // End of method

Versão com bug ( 51 39 bytes):

a->{if(Math.random()>0.1)a.sort(null);}

LD de 1: 1adicionado.

Explicação:

Experimente aqui.

a->{                     // Method with ArrayList<Integer> parameter and no return-type
  if(Math.random()>0.1)  //  If the random 0-1 double is larger than 0.1:
    a.sort(null);        //   Sort the input-List
}                        // End of method
Kevin Cruijssen
fonte
0

JavaScript, 25 * 0,9 = 22,5

new Date%25?x:x.sort()

entrada x

l4m2
fonte