19
2
Introduction
Almost everyone is familiar with the Travelling Salesman Problem (TSP). The task is to, given a list of N
cities, find the minimum Hamiltonian cycle which is to say the shortest path that visits each city and comes full-circle back to the start. That is not what this challenge is about. This challenge is to implement Chuck Norris' solution to the TSP:
Chuck Norris solved the Travelling Salesman problem in
O(1)
time: break salesman into N pieces; kick each piece to a different city.
Challenge
In order to solve the TSP in this way, we need a sufficiently durable Salesman that won't shy away from frivolities like dismemberment; a number of cities to visit; a set of products to sell; a concrete method for dismemberment; and a calculation for scoring.
Specification
- Cities
N
is the number of cites our Salesman will visit
- Salesman
- The main program or function
- Written in language
X
- With length mod
N
equal to0
- Products
- Dismemberment
- Slicing the Salesman into
N
continuous pieces of equal length - Each piece is should be a valid function or program in language
X
- Slicing the Salesman into
- Output
- When executed the Salesman should output
Chuck Norris
and the sliced pieces should each output a distinct product - Only extra trailing white space is acceptable
- When executed the Salesman should output
- Scoring
- The length,
L
, of the Salesman in bytes divided by the number of cities,N
, squared. Score = L/(N*N)
- Smallest score wins
- Please include 3 significant figures when posting your decimal score
- The length,
Examples
- This Salesman visits 3 cities so
N=3
and and it has a length of 9 soL=9
. Thus the score for this answer would beS = 9 / (3 * 3) = 9/9 = 1
.- Note that the Salesman and each sliced piece (of which there are 3), should all be valid programs or functions in the same language.
Program -> Output
------- ------
aaaBBBccc -> Chuck Norris
aaa -> Helium
BBB -> Iridium
ccc -> Tennessine
N=4
andL=20
soS=20/16=1.25
Program -> Output
------- ------
aaaaaBBBBBcccccDDDDD -> Chuck Norris
aaaaa -> Hydrogen
BBBBB -> Cadmium
ccccc -> Mercury
DDDDD -> Iron
3Are built-ins like Mathematica's
ElementData
allowed? (I doubt it'll save much, but I don't know.) – Martin Ender – 2016-09-05T06:29:54.857Is capitalisation of the outputs important? – Martin Ender – 2016-09-05T06:34:06.407
1@MartinEnder ^^ yes ^ yes – NonlinearFruit – 2016-09-05T10:05:13.683
6Could any of the close voters explain which part they actually find unclear? (I know it can't be just my two questions, which I don't even think need to be explicitly addressed in the challenge, because there were already close votes when I posted them.) – Martin Ender – 2016-09-05T13:17:04.887
2Totally agree with @MartinEnder. If you don't like a challenge, just try another one. – edc65 – 2016-09-05T15:11:44.713
Isn't "break salesman into N pieces; kick each piece to a different city."
O(N)
? One break and kick per city? Obviously, it's stillO(1)
for Chuck Norris and Jon Skeet (everything isO(1)
for Jon Skeet), but in my experience anyone else dismembering and distributing salesmen will find themselves working longer for more cities. – Lord Farquaad – 2017-07-13T16:31:28.517