Chuck Norris gegen Travelling Salesman

19

Einführung

Fast jeder kennt das Travelling Salesman Problem (TSP). Die Aufgabe besteht darin, anhand einer Liste von NStädten den minimalen Hamilton-Zyklus zu finden, dh den kürzesten Weg, der jede Stadt besucht und den Kreis schließt, um zum Start zurückzukehren. Darum geht es bei dieser Herausforderung nicht. Diese Herausforderung besteht darin, Chuck Norris ' Lösung für den TSP zu implementieren :

Chuck Norris löste das Problem des Handlungsreisenden O(1)rechtzeitig: Zerlege den Handlungsreisenden in N Teile; Kick jedes Stück in eine andere Stadt.

Herausforderung

Um den TSP auf diese Weise zu lösen, brauchen wir einen ausreichend langlebigen Verkäufer, der Frivolitäten wie Zergliederung nicht scheut. eine Reihe von Städten zu besuchen; eine Reihe von Produkten zu verkaufen; eine konkrete Methode zur Zerlegung; und eine Berechnung für die Wertung.

Spezifikation

  • Städte
    • N ist die Anzahl der von unserem Verkäufer besuchten Stellen
  • Verkäufer
    • Das Hauptprogramm oder die Hauptfunktion
    • In Sprache geschrieben X
    • Mit Länge mod Ngleich0
  • Produkte
    • Die vollständigen Namen der Elemente im Periodensystem
    • Dies schließt die neu akzeptierten Namen der Elemente ein
  • Zerstückelung
    • Den Verkäufer in Ngleichlange durchgehende Stücke schneiden
    • Jedes Stück sollte eine gültige Funktion oder ein gültiges Programm in der Sprache sein X
  • Ausgabe
    • Bei der Ausführung sollte der Verkäufer Chuck Norrisein bestimmtes Produkt ausgeben und die geschnittenen Stücke sollten jeweils ein bestimmtes Produkt ausgeben
    • Nur zusätzliche Leerzeichen am Ende sind zulässig
  • Wertung
    • Die Länge Ldes Verkäufers in Bytes geteilt durch die Anzahl der Städte Nim Quadrat.
    • Score = L/(N*N)
    • Kleinste Punktzahl gewinnt
    • Bitte geben Sie 3 signifikante Ziffern an, wenn Sie Ihre Dezimalpunktzahl veröffentlichen

Beispiele

  1. Dieser Verkäufer besucht so 3 Städte N=3und hat so eine Länge von 9 L=9. Somit wäre die Punktzahl für diese Antwort S = 9 / (3 * 3) = 9/9 = 1.
    • Beachten Sie, dass der Verkäufer und jedes in Scheiben geschnittene Stück (von denen es 3 gibt) gültige Programme oder Funktionen in derselben Sprache sein sollten.
Program      -> Output
-------         ------
aaaBBBccc    -> Chuck Norris

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

aaaaa                   -> Hydrogen
BBBBB                   -> Cadmium
ccccc                   -> Mercury
DDDDD                   -> Iron
code-challenge source-layout NichtlinearFruit
quelle
3
Sind Einbauten wie bei Mathematica ElementDataerlaubt? (Ich bezweifle, dass es viel spart, aber ich weiß es nicht.)
Martin Ender
Ist die Kapitalisierung der Outputs wichtig?
Martin Ender
1
@MartinEnder ^^ yes ^ yes
NonlinearFruit
6
Könnte einer der engen Wähler erklären, welchen Teil sie tatsächlich unklar finden? (Ich weiß, dass es nicht nur meine beiden Fragen sein können, die meiner Meinung nach nicht explizit in der Herausforderung angesprochen werden müssen, da es bereits enge Abstimmungen gab, als ich sie veröffentlichte.)
Martin Ender
2
Stimme voll und ganz @MartinEnder zu. Wenn Sie eine Herausforderung nicht mögen, versuchen Sie es einfach mit einer anderen.
Edc65

Antworten:

11

C Jam, L = 1482, N = 114, Score 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"?

Probieren Sie es online!

Jedes Programm ist 13 Byte lang. Hier sind sie in einzelne Zeilen aufgeteilt:

'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"?

Die fehlenden Elemente sind Darmstadtium, Praseodymium, Protactinium und Rutherfordium, die 12 oder 13 Zeichen lang sind, was bedeutet, dass ich sie nicht in jeweils 13 Zeichen drucken kann.

Die Idee ist, dass die ersten wenigen Programme, die die Elemente mit kurzen Namen drucken, ihre fremden Zeichen verwenden, um die Zeichenfolge Chuck Norriin der Variablen zu erstellen L, was sich nicht auf die Ausgabe auswirkt, wenn sie alleine verwendet werden. Das endgültige Programm prüft dann, ob sich bereits etwas auf dem Stapel befindet, und verwendet es, um zwischen L(plus s) und zu wählen Xenon.

Einige zusätzliche Bytes werden mit dem Zeichen gespeichert, das wir gerade Lals Teil des Elementnamens hinzugefügt haben , insbesondere für CArbon, NIckel, Coppe rund Silve r.

Martin Ender
quelle
2

Python, L = 2596, N = 118, Score = 0,186

Die Länge jedes Schnitts beträgt 22 , was das Ganze ziemlich lang macht.

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  "

Hier ist der Verkäufer nach dem Schneiden und Würfeln:

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  "

Bildbeschreibung hier eingeben

Aktualisieren

  • [16-09-08] Sublime hat beim Verbinden mit einer Zeile, die mit einem Kommentarzeichen endet, ein zusätzliches Leerzeichen hinzugefügt
  • [16-09-08] Jedes Slice wurde 22 Zeichen lang gemacht und gif hinzugefügt
NichtlinearFruit
quelle
Bei Python bin ich mir ziemlich sicher, wie funktioniert die lambda:"Actinium";print""Ausgabe von Actinium? Gilt das möglicherweise speziell für Python 3?
Linus
@Linus Das Lambda- Schlüsselwort erstellt eine anonyme Funktion, die keine Parameter annimmt und zurückgibt Actinium. Das print ""macht nichts Sinn, nachdem der Verkäufer auseinandergenommen wurde.
NonlinearFruit