Eu tenho uma pergunta difícil para você!
Minha namorada recentemente se deparou com um novo programa na MTV (EUA). É um show terrível, e todos são inúteis, mas o "jogo" é bem interessante. Da Wikipedia:
Você é o único? segue 20 pessoas que vivem juntas no Havaí para encontrar a combinação perfeita. Se os 10 homens e 10 mulheres puderem escolher corretamente todas as dez combinações perfeitas em dez semanas, eles ganharão US $ 1 milhão para dividir entre eles.
Agora, para a parte do jogo (também da Wikipedia):
Cada episódio que o elenco irá emparelhar com quem eles acreditam que seu par perfeito é competir em um desafio. Os vencedores do desafio sairão em um encontro e terão a chance de testar sua partida no estande da verdade. Os membros do elenco escolherão um dos casais vencedores para ir ao estande da verdade para determinar se eles são uma combinação perfeita ou não. Esta é a única maneira de confirmar correspondências. Cada episódio termina com uma cerimônia de correspondência, onde os casais serão informados de quantas combinações perfeitas elas têm, mas não quais delas estão corretas.
TL; DR: Este é um derivado do Mastermind (M (10,10) para ser específico). As regras do jogo são as seguintes:
Você começa com 2 conjuntos de 10, vamos chamá-los de Conjunto A: {A, B, C, D, E, F, G, H, I, J} e Conjunto 2: {1,2,3,4,5, 6,7,8,9,10}
O computador cria uma solução (não visível para você) na forma de {A1, B2, C3, D4, E5, F6, G7, H8, I9, J10}, em que os membros do conjunto A são mapeados 1 para 1 para definir 2. Outro exemplo de solução pode ser {A2, B5, C10, D8, E1, F7, G6, H4, I9, J3}.
Antes do seu primeiro turno, você pergunta se um único par específico de sua escolha está correto. Sua pergunta seria na forma de {A1} (por exemplo, {C8}) e você receberá 1 (significando correto) ou 0 (significando que seu palpite está incorreto).
Sua primeira vez real. Você faz seu primeiro palpite na forma de {A1, B2, C3, D4, E5, F6, G7, H8, I9, J10} ou qualquer permutação de sua escolha. Sua suposição não pode conter múltiplos de nenhum item, ou seja, uma suposição de {A1, A2, A3, A4, A5, B6, B7, B8, B9, B10} NÃO é válida. Após cada turno, o computador informa o número de correspondências corretas, mas NÃO as correspondências corretas.
Repita as etapas 3 e 4 até acertar todas as correspondências (por exemplo, uma resposta de 10) ou até que seus 10 movimentos subam (o que ocorrer primeiro). Se você resolver isso antes ou no seu 10º turno, você ganha $ 1 milhão. Caso contrário, você perde e algumas pessoas (ou letras e números) vão para casa sozinhas para passar a eternidade com seus 10 gatos.
Este NÃO é um concurso de código mais curto. A pessoa que conseguir resolver uma correspondência aleatória no menor número médio de palpites será o vencedor. Provavelmente, a jogabilidade inteligente e a velocidade de cálculo também serão consideradas. Estou assumindo que o número médio de turnos será quase certamente maior que 10, então as chances de você ganhar o prêmio de US $ 1 milhão (presumivelmente pago pela MTV, não eu) são pequenas. Assim como impossível é para o elenco de ganhar o grande prêmio?
Nota: Colocá-lo no formato {A1, B2, ...} não é necessariamente necessário. Simplesmente usei esse formulário na pergunta para deixar absolutamente claro o que é o quebra-cabeça. Se você não o colocar neste formulário, explique como chamá-lo.
Boa sorte!
fonte
Respostas:
Python 2 (execute mais rápido se for executado usando Pypy)
Acredita-se que quase sempre adivinhe o emparelhamento correto em 10 rodadas ou menos
Meu algoritmo é retirado da minha resposta para o cérebro como meu hobby (veja em Ideone ). A idéia é encontrar um palpite que minimize o número de possibilidades restantes no pior caso. Meu algoritmo abaixo apenas a força bruta, mas para economizar tempo, basta escolher palpites aleatórios se o número de possibilidades restantes for maior que
RANDOM_THRESHOLD
. Você pode brincar com esse parâmetro para acelerar as coisas ou obter um melhor desempenho.O algoritmo é bastante lento, em média 10s para uma execução, se executado com Pypy (se o interpretador CPython normal estiver em torno de 30s), então não posso testá-lo em todas as permutações. Mas o desempenho é muito bom, depois de cerca de 30 testes, não vi nenhum caso em que ele não encontre o emparelhamento correto em 10 rodadas ou menos.
De qualquer forma, se isso for usado no programa da vida real, ele terá bastante tempo antes da próxima rodada (uma semana?) Para que esse algoritmo possa ser usado na vida real = D
Portanto, acho que é seguro supor que, em média, este ache os pares corretos em 10 palpites ou menos.
Tente você mesmo. Talvez eu melhore a velocidade nos próximos dias (EDIT: parece difícil melhorar ainda mais, então deixarei o código como está. Tentei apenas fazer uma escolha aleatória, mas mesmo assim
size=7
, ele falha em 3 dos 5040 casos , então eu decidi manter o método mais inteligente). Você pode executá-lo como:Ou, se você quiser apenas ver como funciona, insira um número menor (para que seja mais rápido)
Para executar um teste completo (aviso: levará muito tempo para
size
> 7), coloque um número negativo.Teste completo para
size=7
(concluído em 2m 32s):Se
RANDOM_THRESHOLD
eCLEVER_THRESHOLD
estiverem ambos definidos com um valor muito alto (como 50000), forçará o algoritmo a encontrar a estimativa ideal que minimiza o número de possibilidades no pior caso. Isso é muito lento, mas muito poderoso. Por exemplo, executá-losize=6
afirma que ele pode encontrar os pares corretos em no máximo 5 rodadas.Embora a média seja mais alta em comparação ao uso da aproximação (que é média de 4,11 rodadas), mas sempre é bem-sucedida, ainda mais com uma rodada sobrando. Isso reforça ainda mais nossa hipótese de que
size=10
, quando , quase sempre deve encontrar os pares corretos em 10 rodadas ou menos.O resultado (concluído em 3m 9s):
O código.
fonte
len(remove_perms ...)
parte). E sim, eu quis dizer em <= 10 rodadas =). Entre no código acima, o palpite realmente ótimo nunca é feito, como eu disseCLEVER_THRESHOLD=0
, o que significa que ele apenas tentará adivinhar a partir da lista de possibilidades, embora o palpite ideal possa estar fora deste conjunto. Mas eu decidi desativar isso para economizar tempo. Eu adicionei teste completo parasize=7
, mostrando que sempre é bem-sucedido.size=8
e descobri que a versão mais recente tem apenas 40308 sucessos (em vez de 40320) se essa configuração for usada. Mas ainda é uma taxa de sucesso de 99,97%! Acho que podemos fazer com que o organizador do programa de TV vá à falência.CJam -19 turnos - A estratégia de um idiota
Esta não é uma resposta séria, mas uma demonstração. Esta é a solução de um idiota em que ele não leva em consideração o número de informações corretas de emparelhamento fornecidas a partir da segunda parte do turno. Com pares completamente aleatórios, isso leva em média 27 semanas. Essa resposta é insuficiente, como eu disse, mas indica que as chances de um grupo de intelectuais (muito mais intelectuais que esse programa) provavelmente não são tão pequenas quanto você poderia esperar. Os algoritmos mais intelectuais que eu escrevi, no entanto, levam muito mais tempo para serem executados, para que eu possa realmente obter respostas deles.
Atualização: o código abaixo foi atualizado para usar o estado de que ele deve remover os que não funcionarem se os únicos corretos forem aqueles que já sabíamos que estavam corretos. Também foi editado para mostrar meu gerador aleatório de "resposta correta". O resultado médio agora é de apenas 19. Ainda é uma solução idiota, mas é melhor que a anterior marginalmente.
fonte
Versão rápida C ++ multithread
Eu sei que já faz um tempo desde que esse segmento estava ativo, mas tenho uma adição interessante para compartilhar: Aqui está uma implementação em C ++ do algoritmo minimax para Are You The One? , que usa multiencadeamento para acelerar a avaliação de cada palpite possível.
Esta versão é muito mais rápida que a versão do Python (mais de 100x mais rápido quando a versão original do Python está definida como máxima
RANDOM_THRESHOLD
eCLEVER_THRESHOLD
). Ele não usa nenhuma suposição aleatória, mas avalia todas as permutações e submete como suposição a permutação que elimina o maior número de soluções possíveis (dada a resposta do pior caso).Para jogos menores, chamar "ayto -n" executará o jogo em todos os n! possíveis correspondências ocultas e fornecerá um breve resumo dos resultados no final.
Como ainda é difícil avaliar todos os 10! possíveis correspondências ocultas, se você chamar "ayto 10", por exemplo, o simulador faz suas três primeiras suposições fixas, executa o minimax para escolher sua suposição e assume que recebeu a pior avaliação possível. Isso nos leva a um "caminho do pior caso" para um vetor oculto, presumivelmente na classe de vetores que leva o algoritmo a um número máximo de suposições para identificar. Essa conjectura não foi testada.
Até n = 9 , não houve uma simulação que levou mais de n turnos para resolver.
Para testar você mesmo, um exemplo de compilação seria o seguinte:
Aqui está um pequeno exemplo com saída:
Código
fonte