Maneiras de especificar a geração aleatória em desafios

Nota : De acordo com o consenso sobre o Meta , as perguntas de redação de desafios estão no tópico aqui.

À luz dessa "coisa a evitar ao escrever desafios" , comecei a pensar em desafios que envolvem a geração aleatória de certos tipos de objetos.

Às vezes, eu quero postar um desafio de código-golfe que envolve gerar aleatoriamente um foo, em que

1. é muito fácil verificar se uma determinada coisa é um foo, e
2. é um pouco mais difícil gerar rapidamente um foo aleatório de "boa qualidade".

Como exemplo, um foo pode ser uma matriz binária na qual não existem segmentos de 4 bits iguais em nenhuma direção. É fácil verificar se uma dada matriz binária é um foo, mas gerar um foo aleatório com uma distribuição bem distribuída parece exigir um algoritmo de retorno ou algo semelhante.

De qualquer forma, agora vou precisar especificar objetivamente o que qualifica como um foo aleatório, e gostaria que fosse "imprevisível" no sentido intuitivo de que, quando executo o programa várias vezes, os resultados sempre parecem diferentes. A abordagem mais restritiva é exigir que a saída seja uniformemente aleatória: todos os foos válidos têm a mesma probabilidade de serem gerados. Isso geralmente é muito restritivo, porque não tenho idéia de como fazer isso, para gerar todos os foos válidos, remover duplicatas e escolher uma que seja chata e lenta.

Minha próxima idéia é exigir que todos os foos válidos tenham uma probabilidade positiva de serem gerados. No entanto, isso significa que a seguinte abordagem é válida: gere uma coisa aleatória semelhante a um foo (no nosso exemplo, uma matriz binária aleatória), se for um foo, em seguida, retorne-o, caso contrário, retorne um foo codificado (por exemplo, a matriz de identidade ) Isso também é um pouco chato, já que é basicamente apenas um reconhecedor de foos presos a um gerador de matriz aleatória.

Poderia haver uma boa definição geral para um foo imprevisivelmente aleatório?

TL; DR

Existe uma boa maneira de especificar um objeto gerado aleatoriamente "imprevisível" que não corrige a distribuição, mas desencoraja a codificação?

Retorne mil foos diferentes

Isso torna impossível retornar valores codificados e ter um golfe meio decente. No entanto, um gerador de foo legítimo tem uma pequena chance de gerar foos duplicados, a menos que esteja realmente verificando-os. Para remover o ônus da verificação, uma taxa de falha empiricamente testada, digamos 10%, pode ser especificada como aceitável.

Esteja ciente do paradoxo do aniversário , pois a probabilidade de duplicatas pode ser maior do que você pensa. Se houver apenas um milhão de foos possíveis, mil foos aleatórios terão uma probabilidade de cerca de 0,6 de que haja uma duplicata em algum lugar, e isso pressupõe que a geração de foos seja completamente uniforme. Se isso for um problema, exija, digamos, 900 foos exclusivos para cada 1000 gerados, o que é muito mais generoso para um gerador de foo genuíno, mas ainda impraticável para codificação.

Isso também permite que você gere repetidamente coisas semelhantes a foo e verifique fooness até obter foos. Eu acho que essa é uma solução válida, mas se você não gosta:

Faça isso rapidamente

As chances de uma coisa completamente aleatória como foo ser foo são provavelmente muito baixas, então especificar um limite de tempo provavelmente forçará uma tentativa genuína de geração de foo.

Para acomodar as diferenças de velocidade entre diferentes idiomas, convém ter limites de tempo diferentes, dependendo do idioma como Hackerrank: https://www.hackerrank.com/environment . No entanto, se você especificar foos grandes o suficiente, a probabilidade de coisas aleatórias semelhantes a foo serem foo pode ser realmente muito baixa, portanto, uma regra "antes da morte por calor do Universo" pode ser suficiente.

Não pretendo ter a solução definitiva para o problema (ou que esta lista seja exaustiva), mas quero descrever algumas abordagens possíveis que me vêm à mente e por que elas funcionariam ou não. Também não abordarei questões tangenciais, como se o uso do carimbo de data / hora atual como fonte de aleatoriedade é suficientemente "imprevisível" e como impor certas propriedades da distribuição de probabilidade - vou me concentrar apenas em evitar soluções que usam codificação codificada.

Não é uma solução: não permitir a codificação embutida explicitamente

Esta é uma má ideia. É um requisito não observável (o que significa que você não pode determinar se está satisfeito apenas com a execução do programa), que é fortemente desencorajado no PPCG e pode ser totalmente impossível se estiver executando o programa em qualquer outra plataforma, na qual os envios são verificados em um maneira automatizada. O problema com um requisito como esse é que você teria que começar encontrando uma definição objetiva para "codificação". Em geral, se você tentar isso, só piorará as coisas.

Tornar a codificação impraticável

Se você não pode proibi-lo completamente, mas não deseja que as pessoas o usem, tente criar o desafio de forma que a codificação não seja simplesmente uma abordagem competitiva. Isso é possível se os objetos que devem ser gerados forem suficientemente grandes e incompressíveis para que colocar um exemplo no código exija muito mais bytes do que escrever um algoritmo que gera soluções válidas aleatoriamente. No seu exemplo específico, esse não é o caso, é claro, porque as matrizes de identidade são válidas e geralmente são fáceis de gerar, mas para outros problemas, esse pode não ser o caso. Se os objetos de destino forem suficientemente irregulares, apenas exija um tamanho grande, o que provavelmente não afetará a contagem de bytes de um algoritmo real, mas explodirá a parte codificada.

Parametrizar a saída

Geralmente, esses problemas vêm com um ou mais parâmetros naturais, como o tamanho da matriz no seu exemplo. Nesse caso, tornar esse parâmetro uma entrada pode ser suficiente para tornar a codificação impossível ou pelo menos impraticável. Em alguns casos, pode ser fácil codificar uma solução específica para um determinado valor de parâmetro que foi encontrado manualmente ou por meio de uma pesquisa extensiva, mas talvez não exista um formulário fechado simples para uma instância dessa solução em geral, por isso não é possível gerar um valor padrão para entradas arbitrárias facilmente. Novamente, este não é o caso do exemplo que você mencionou, porque a matriz de identidade funciona em qualquer tamanho, mas uma solução ideal para esse problema relacionadogeralmente é altamente irregular, portanto, não é possível ter valor padrão sem procurar ativamente valores válidos. Você pode combinar isso com um limite de tempo para evitar uma pesquisa de força bruta por um valor padrão.

Coloque alguma restrição na distribuição de probabilidade

Se você deseja desistir de uma distribuição de probabilidade completamente irrestrita, pode colocar algumas restrições nela, que ainda dão muita liberdade aos respondentes na escolha de sua distribuição, mas que tornam difícil ou impossível a codificação embutida:

• A restrição mais simples que vem à mente é exigir que a diferença entre a probabilidade mínima e máxima para que qualquer saída possível esteja abaixo de um determinado limite. Uma abordagem codificada provavelmente terá probabilidades quase nulas para quase todas as saídas e uma probabilidade próxima de 1 para o valor padrão. Se você exigir que a diferença máxima esteja abaixo de 0,1, digamos, seriam necessários 10 valores padrão (escolhidos aleatoriamente) para tornar a abordagem uma opção. Da mesma forma, você também pode exigir apenas uma probabilidade mínima para cada saída possível, por exemplo, 1 / (2 * N *), onde N é o número de saídas possíveis.
• Como alternativa, você pode exigir que não haja lacunas (probabilidade) na distribuição, para que não haja intervalo de tamanho δ (escolhido por você), de modo que exista probabilidade maior e menor. Isso significa que não pode haver discrepantes em termos de probabilidade, que provavelmente são gerados por uma abordagem codificada.

O principal problema dessas abordagens é que elas são muito mais difíceis de raciocinar, provar que a exatidão das respostas é difícil e verificar experimentalmente a exatidão pode ser impossível para grandes espaços de saída. Ainda assim, eles fornecem um requisito principalmente observável para o programa, o que pode tornar impossível a codificação.

Essas abordagens também podem precisar de um limite de tempo, porque uma maneira de aumentar a probabilidade dos valores não padrão seria tentar encontrar um aleatório foo várias vezes antes de retornar ao valor padrão.