Chuck Norris vs Travelling Salesman

19

Introdução

Quase todo mundo está familiarizado com o Problema do Vendedor Viajante (TSP). A tarefa é, dada uma lista de Ncidades, encontrar o ciclo hamiltoniano mínimo , ou seja, o caminho mais curto que visita cada cidade e volta ao início. Não é disso que se trata esse desafio. Esse desafio é implementar a solução de Chuck Norris para o TSP:

Chuck Norris resolveu o problema do Vendedor O(1)ambulante a tempo: dividir o vendedor em N pedaços; chute cada peça para uma cidade diferente.

Desafio

Para resolver o TSP dessa maneira, precisamos de um vendedor suficientemente durável que não evite frivolidades como desmembramento; um número de cidades para visitar; um conjunto de produtos para vender; um método concreto de desmembramento; e um cálculo para pontuação.

Especificação

  • Cidades
    • N é o número de citações que nosso vendedor visitará
  • Vendedor
    • O programa ou função principal
    • Escrito no idioma X
    • Com comprimento mod Nigual a0
  • Produtos
    • Os nomes completos dos elementos na Tabela Periódica
    • Isso inclui os nomes de elementos recém- aceitos
  • Desmembramento
    • Fatiar o vendedor em Npedaços contínuos de igual comprimento
    • Cada peça deve ser uma função ou programa válido na linguagem X
  • Resultado
    • Quando executado, o Vendedor deve produzir Chuck Norrise as peças fatiadas devem produzir um produto distinto
    • Apenas espaço em branco à direita é aceitável
  • Pontuação
    • O comprimento L,, do Vendedor em bytes dividido pelo número de cidades N, ao quadrado.
    • Score = L/(N*N)
    • Menor pontuação ganha
    • Inclua 3 números significativos ao publicar sua pontuação decimal

Exemplos

  1. Este vendedor visita três cidades N=3e tem 9 L=9. Assim, a pontuação para esta resposta seria S = 9 / (3 * 3) = 9/9 = 1.
    • Observe que o Vendedor e cada peça fatiada (dos quais existem 3) devem ser programas ou funções válidos no mesmo idioma.
Program      -> Output
-------         ------
aaaBBBccc    -> Chuck Norris

aaa          -> Helium
BBB          -> Iridium
ccc          -> Tennessine
  1. N=4e L=20assimS=20/16=1.25
Program                 -> Output
-------                    ------
aaaaaBBBBBcccccDDDDD    -> Chuck Norris

aaaaa                   -> Hydrogen
BBBBB                   -> Cadmium
ccccc                   -> Mercury
DDDDD                   -> Iron
code-challenge source-layout NonlinearFruit
fonte
3
São ElementDatapermitidos embutidos como o Mathematica ? (Eu duvido que vai economizar muito, mas eu não sei.)
Martin Ender
A capitalização dos produtos é importante?
Martin Ender
11
@MartinEnder ^^ yes ^ yes
NonlinearFruit
6
Algum dos eleitores próximos poderia explicar qual parte eles realmente acham incerto? (Eu sei que não pode ser apenas a duas perguntas, que eu nem sequer pensar necessidade de ser explicitamente abordada no desafio, porque já estavam perto de votos quando eu postei-los.)
Martin Ender
2
Concordo totalmente com @MartinEnder. Se você não gosta de um desafio, tente outro.
Edc65 5/09/16

Respostas:

11

CJam, L = 1482, N = 114, pontuação 0,114

'C:L"arbon"  L'h+:L;"Gold"L'u+:L;"Iron"L'c+:L;"Lead"L'k+:L;"Neon"LS+:L;"Argon"L'N+:L"ickel"L'o+:L;"Zinc""Coppe"L'r+:L"Silve"L'r+:LL'i+:L;"Tin" "Boron"      "Radon"      "Barium"     "Cerium"     "Cesium"     "Cobalt"     "Curium"     "Erbium"     "Helium"     "Indium"     "Iodine"     "Osmium"     "Oxygen"     "Radium"     "Sodium"     "Sulfur"     "Arsenic"    "Bismuth"    "Bohrium"    "Bromine"    "Cadmium"    "Calcium"    "Dubnium"    "Fermium"    "Gallium"    "Hafnium"    "Hassium"    "Holmium"    "Iridium"    "Krypton"    "Lithium"    "Mercury"    "Niobium"    "Rhenium"    "Rhodium"    "Silicon"    "Terbium"    "Thorium"    "Thulium"    "Uranium"    "Yttrium"    "Actinium"   "Aluminum"   "Antimony"   "Astatine"   "Chlorine"   "Chromium"   "Europium"   "Fluorine"   "Francium"   "Hydrogen"   "Lutetium"   "Nihonium"   "Nitrogen"   "Nobelium"   "Platinum"   "Polonium"   "Rubidium"   "Samarium"   "Scandium"   "Selenium"   "Tantalum"   "Thallium"   "Titanium"   "Tungsten"   "Vanadium"   "Americium"  "Berkelium"  "Beryllium"  "Flerovium"  "Germanium"  "Lanthanum"  "Magnesium"  "Manganese"  "Moscovium"  "Neodymium"  "Neptunium"  "Oganesson"  "Palladium"  "Plutonium"  "Potassium"  "Ruthenium"  "Strontium"  "Tellurium"  "Ytterbium"  "Zirconium"  "Dysprosium" "Gadolinium" "Lawrencium" "Meitnerium" "Molybdenum" "Phosphorus" "Promethium" "Seaborgium" "Technetium" "Tennessine" "Californium""Copernicium""Einsteinium""Livermorium""Mendelevium""Roentgenium"]L's+"Xenon"?

Experimente online!

Cada programa tem 13 bytes. Aqui eles são divididos em linhas individuais:

'C:L"arbon"  
L'h+:L;"Gold"
L'u+:L;"Iron"
L'c+:L;"Lead"
L'k+:L;"Neon"
LS+:L;"Argon"
L'N+:L"ickel"
L'o+:L;"Zinc"
"Coppe"L'r+:L
"Silve"L'r+:L
L'i+:L;"Tin" 
"Boron"      
"Radon"      
"Barium"     
"Cerium"     
"Cesium"     
"Cobalt"     
"Curium"     
"Erbium"     
"Helium"     
"Indium"     
"Iodine"     
"Osmium"     
"Oxygen"     
"Radium"     
"Sodium"     
"Sulfur"     
"Arsenic"    
"Bismuth"    
"Bohrium"    
"Bromine"    
"Cadmium"    
"Calcium"    
"Dubnium"    
"Fermium"    
"Gallium"    
"Hafnium"    
"Hassium"    
"Holmium"    
"Iridium"    
"Krypton"    
"Lithium"    
"Mercury"    
"Niobium"    
"Rhenium"    
"Rhodium"    
"Silicon"    
"Terbium"    
"Thorium"    
"Thulium"    
"Uranium"    
"Yttrium"    
"Actinium"   
"Aluminum"   
"Antimony"   
"Astatine"   
"Chlorine"   
"Chromium"   
"Europium"   
"Fluorine"   
"Francium"   
"Hydrogen"   
"Lutetium"   
"Nihonium"   
"Nitrogen"   
"Nobelium"   
"Platinum"   
"Polonium"   
"Rubidium"   
"Samarium"   
"Scandium"   
"Selenium"   
"Tantalum"   
"Thallium"   
"Titanium"   
"Tungsten"   
"Vanadium"   
"Americium"  
"Berkelium"  
"Beryllium"  
"Flerovium"  
"Germanium"  
"Lanthanum"  
"Magnesium"  
"Manganese"  
"Moscovium"  
"Neodymium"  
"Neptunium"  
"Oganesson"  
"Palladium"  
"Plutonium"  
"Potassium"  
"Ruthenium"  
"Strontium"  
"Tellurium"  
"Ytterbium"  
"Zirconium"  
"Dysprosium" 
"Gadolinium" 
"Lawrencium" 
"Meitnerium" 
"Molybdenum" 
"Phosphorus" 
"Promethium" 
"Seaborgium" 
"Technetium" 
"Tennessine" 
"Californium"
"Copernicium"
"Einsteinium"
"Livermorium"
"Mendelevium"
"Roentgenium"
]L's+"Xenon"?

Os elementos ausentes são Darmstadtium, Praseodymium, Protactinium e Rutherfordium, com 12 ou 13 caracteres, o que significa que não posso imprimi-los em 13 caracteres cada.

A idéia é que os primeiros programas, que imprimem os elementos com nomes abreviados, usem seus caracteres estranhos para criar a sequência Chuck Norrina variável L, o que não afeta a saída quando usados ​​por si próprios. O programa final verifica se algo já está na pilha e o utiliza para escolher entre L(mais s) e Xenon.

Alguns bytes adicionais são salvos usando o caractere ao qual acabamos de adicionar Lcomo parte do nome do elemento, especificamente para Carbon, Nickel, Coppe re Silve r.

Martin Ender
fonte
2

Python, L = 2596, N = 118, Pontuação = 0,186

O comprimento de cada fatia é 22 , o que torna isso bastante longo.

lambda:"Gold"; print"""";print "Carbon     "print   "Thorium     "print   "Curium      "print "Calcium       "print "Nickel        "print      "Zinc     "print    "Neon       "print "Boron         "print   "Iron        "print  "Cerium       "print "Barium        "print "Caesium       """[9::22];lambda:"Tin"[0];lambda:"Lead    "#print"Argon          "print"Radon          "print"Xenon          "print"Erbium         "print"Cobalt         "print"Copper         "print"Helium         "print"Indium         "print"Iodine         "print"Osmium         "print"Oxygen         "print"Radium         "print"Silver         "print"Sodium         "print"Sulfur         "print"Arsenic        "print"Bismuth        "print"Bohrium        "print"Bromine        "print"Cadmium        "print"Dubnium        "print"Fermium        "print"Gallium        "print"Hafnium        "print"Hassium        "print"Holmium        "print"Iridium        "print"Krypton        "print"Lithium        "print"Mercury        "print"Niobium        "print"Rhenium        "print"Rhodium        "print"Silicon        "print"Terbium        "print"Thulium        "print"Uranium        "print"Yttrium        "print"Actinium       "print"Antimony       "print"Astatine       "print"Chlorine       "print"Chromium       "print"Europium       "print"Fluorine       "print"Francium       "print"Hydrogen       "print"Lutetium       "print"Nitrogen       "print"Nobelium       "print"Platinum       "print"Polonium       "print"Rubidium       "print"Samarium       "print"Scandium       "print"Selenium       "print"Tantalum       "print"Thallium       "print"Titanium       "print"Tungsten       "print"Vanadium       "print"Nihonium       "print"Aluminium      "print"Americium      "print"Berkelium      "print"Beryllium      "print"Flerovium      "print"Germanium      "print"Lanthanum      "print"Magnesium      "print"Manganese      "print"Neodymium      "print"Neptunium      "print"Palladium      "print"Plutonium      "print"Potassium      "print"Ruthenium      "print"Strontium      "print"Tellurium      "print"Ytterbium      "print"Zirconium      "print"Moscovium      "print"Oganesson      "print"Dysprosium     "print"Gadolinium     "print"Lawrencium     "print"Meitnerium     "print"Molybdenum     "print"Phosphorus     "print"Promethium     "print"Seaborgium     "print"Technetium     "print"Tennessine     "print"Californium    "print"Copernicium    "print"Einsteinium    "print"Livermorium    "print"Mendelevium    "print"Roentgenium    "print"Darmstadtium   "print"Praseodymium   "print"Protactinium   "print"Rutherfordium  "

Aqui está o vendedor depois de fatiar e picar:

lambda:"Gold"; print""  # <-- This is a function
"";print "Carbon     "
print   "Thorium     "
print   "Curium      "
print "Calcium       "
print "Nickel        "
print      "Zinc     "
print    "Neon       "
print "Boron         "
print   "Iron        "
print  "Cerium       "
print "Barium        "
print "Caesium       "
""[9::22];lambda:"Tin"  # <-- This is a function and the choke point
[0];lambda:"Lead    "#  # <-- This is a function
print"Argon          "
print"Radon          "
print"Xenon          "
print"Erbium         "
print"Cobalt         "
print"Copper         "
print"Helium         "
print"Indium         "
print"Iodine         "
print"Osmium         "
print"Oxygen         "
print"Radium         "
print"Silver         "
print"Sodium         "
print"Sulfur         "
print"Arsenic        "
print"Bismuth        "
print"Bohrium        "
print"Bromine        "
print"Cadmium        "
print"Dubnium        "
print"Fermium        "
print"Gallium        "
print"Hafnium        "
print"Hassium        "
print"Holmium        "
print"Iridium        "
print"Krypton        "
print"Lithium        "
print"Mercury        "
print"Niobium        "
print"Rhenium        "
print"Rhodium        "
print"Silicon        "
print"Terbium        "
print"Thulium        "
print"Uranium        "
print"Yttrium        "
print"Actinium       "
print"Antimony       "
print"Astatine       "
print"Chlorine       "
print"Chromium       "
print"Europium       "
print"Fluorine       "
print"Francium       "
print"Hydrogen       "
print"Lutetium       "
print"Nitrogen       "
print"Nobelium       "
print"Platinum       "
print"Polonium       "
print"Rubidium       "
print"Samarium       "
print"Scandium       "
print"Selenium       "
print"Tantalum       "
print"Thallium       "
print"Titanium       "
print"Tungsten       "
print"Vanadium       "
print"Nihonium       "
print"Aluminium      "
print"Americium      "
print"Berkelium      "
print"Beryllium      "
print"Flerovium      "
print"Germanium      "
print"Lanthanum      "
print"Magnesium      "
print"Manganese      "
print"Neodymium      "
print"Neptunium      "
print"Palladium      "
print"Plutonium      "
print"Potassium      "
print"Ruthenium      "
print"Strontium      "
print"Tellurium      "
print"Ytterbium      "
print"Zirconium      "
print"Moscovium      "
print"Oganesson      "
print"Dysprosium     "
print"Gadolinium     "
print"Lawrencium     "
print"Meitnerium     "
print"Molybdenum     "
print"Phosphorus     "
print"Promethium     "
print"Seaborgium     "
print"Technetium     "
print"Tennessine     "
print"Californium    "
print"Copernicium    "
print"Einsteinium    "
print"Livermorium    "
print"Mendelevium    "
print"Roentgenium    "
print"Darmstadtium   "
print"Praseodymium   "
print"Protactinium   "
print"Rutherfordium  "

insira a descrição da imagem aqui

Atualizar

  • [16-09-08] Sublime adicionou um espaço extra ao ingressar em uma linha que termina em um caractere de comentário
  • [16-09-08] Aumentou em 22 caracteres cada pedaço e adicionou gif
NonlinearFruit
fonte
Eu sou bastante conhecido em Python, como é que produz lambda:"Actinium";print""o Actinium? Talvez isso seja particular do Python 3?
Linus
@Linus A palavra-chave lambda cria uma função anônima que não aceita parâmetros e retorna Actinium. A print ""não faz nada de útil após o vendedor foi desmembrado.
NonlinearFruit