Fourth grade math homework for the week: A most inefficient traveling salesman

Question

My daughter had the following assignment for her math homework. Imagine six friends living on a line, named E, F, G, H, J and K. Their positions on the line are as indicated (not to scale) below:

Thus, F lives five units from E, and two units from G, and so forth.

Your assignment: craft a program that identifies a path that visits each friend exactly once with a total length of n units, taking the locations of the friends and n as inputs. It should report the path if it finds it (for example, for length 17 it might report "E,F,G,H,J,K", and it should exit gracefully if no solution exists. For what it's worth, I completed an ungolfed solution in Mathematica in 271 bytes. I suspect it's possible much more concisely than that.

Answer 1

Mathematica, 55 or 90 bytes

Mathematica you said? ;)

FirstCase[Permutations@#,p_/;Tr@Abs@Differences@p==#2]&

This is an anonymous function that first takes the positions of the friends (in any order), and then the target length. It returns Missing[NotFound], if no such path exists.

FirstCase[Permutations@#,p_/;Tr@Abs@Differences@p==#2]&[{0, 5, 7, 13, 16, 17}, 62]
(* {7, 16, 0, 17, 5, 13} *)

I can save four bytes if returning all valid paths is allowed (FirstCase -> Cases).

Returning an array of strings is a bit more cumbersome:

FromCharacterCode[68+#]&/@Ordering@FirstCase[Permutations@#,p_/;Tr@Abs@Differences@p==#2]&

Answer 2

Python 2, 154 148 bytes

(or 118 bytes for the general solution)

This program accepts a line with a list and an integer like '[0, 5, 7, 13, 16, 17], n' on stdin and prints a path on the output of length n or nothing if impossible.

# echo "[0, 5, 7, 13, 16, 17], 62" | python soln.py 
['G', 'J', 'E', 'K', 'F', 'H']

It is challenging to write small programs in Python that require permutations. That import and use is very costly.

from itertools import*
a,c=input()
for b in permutations(a):
 if sum(abs(p-q)for p,q in zip(b[1:],b))==c:print['EFGHJK'[a.index(n)]for n in b];break

The source for the OP requirement before the minifier:

from itertools import*

puzzle, goal = input()
for option in permutations(puzzle):
    if sum(abs(p-q) for p,q in zip(option[1:], option)) == goal :
        print ['EFGHJK'[puzzle.index(n)] for n in option];
        break

The general solution (not minified):

from itertools import*

puzzle, goal = input()
for option in permutations(puzzle):
    if sum(abs(p-q) for p,q in zip(option[1:], option)) == goal :
        print option;
        break

Due to the simple algorithm and vast number of combinations, execution for more than 20 initial positions will be very slow.

Answer 3

J (48 or 65)

I hypothesize that this can be golfed a hell of a lot more. Feel free to use this as a jumping off point to golf it further

]A.~[:I.(=([:([:+/}:([:|-)}.)"1(A.~([:i.[:!#))))

Or with letters:

([:I.(=([:([:+/}:([:|-)}.)"1(A.~([:i.[:!#)))))A.[:(a.{~65+[:i.#)]

What it does:

   62 (]A.~[:I.(=([:([:+/}:([:|-)}.)"1(A.~([:i.[:!#))))) 0 5 7 13 16 17
 7 16  0 17  5 13
 7 16  5 17  0 13
 7 17  0 16  5 13
 7 17  5 16  0 13
13  0 16  5 17  7
13  0 17  5 16  7
13  5 16  0 17  7
13  5 17  0 16  7

(I hope this I/O format is okay...)

How it does it:

(A.~([:i.[:!#))

Generates all permutations of the input

([:+/}:([:|-)}.)"1

Calculates the distance

(]A.~[: I. (= ([:distance perms)))

Sees which results are the same as the input, and re-generates those permutations (I suspect some characters can be shaved off here)

With letters:

((a.{~65+[:i.#))

Create a list of the first n letters, where n is the length of the input list

indices A. [: letters ]

does the same as above

Answer 4

Octave, 73

function r=t(l,d,s)r=perms(l)(find(sum(abs(diff(perms(d)')))==s,1),:);end

There's really no un-golfing this, so let me try to explain... from inside to out, we permute all the distances, then for each permutation, we take the differences between houses, take the absolute value as a distance, add them up, find the index of the first permutation with the desired distance, and permute the letters and find that particular permutation of letters.

octave:15> t(["E" "F" "G" "H" "J" "K"],[0 5 7 13 16 17],62)
ans = HEJFKG

which is 13-0-16-5-17-7 => 13+16+11+12+10=62.

octave:16> t(["E" "F" "G" "H" "J" "K"],[0 5 7 13 16 17],2)
ans = 

(blank for impossible inputs)

Answer 5

Matlab (86)

x=input('');X=perms(1:6);disp(char(X(find(sum(abs(diff(x(X).')))==input(''),1),:)+64))

Example in which a solution exists:

>> x=input('');X=perms(1:6);disp(char(X(find(sum(abs(diff(x(X).')))==input(''),1),:)+64))
[0, 5, 7, 13, 16, 17]
62
DBFAEC
>>

Example in which a solution doesn't exist:

>> x=input('');X=perms(1:6);disp(char(X(find(sum(abs(diff(x(X).')))==input(''),1),:)+64))
[0, 5, 7, 13, 16, 17]
100
>> 

---

Matlab (62)

If the output format can be relaxed by producing positions instead of letters, and producing an empty matrix if no solution exists:

X=perms(input(''));X(find(sum(abs(diff(X.')))==input(''),1),:)

Example in which a solution exists:

>> X=perms(input(''));X(find(sum(abs(diff(X.')))==input(''),1),:)
[0, 5, 7, 13, 16, 17]
62
ans =
    13     5    17     0    16     7

Example in which a solution doesn't exist:

>> X=perms(input(''));X(find(sum(abs(diff(X.')))==input(''),1),:)
[0, 5, 7, 13, 16, 17]
62
ans =
   Empty matrix: 0-by-6

---

Matlab (54)

If it's acceptable for the program to provide all valid paths:

X=perms(input(''));X(sum(abs(diff(X.')))==input(''),:)

Example in which a solution exists:

>> X=perms(input(''));X(sum(abs(diff(X.')))==input(''),:)
[0, 5, 7, 13, 16, 17]
62
ans =
    13     5    17     0    16     7
    13     5    16     0    17     7
    13     0    17     5    16     7
    13     0    16     5    17     7
     7    16     5    17     0    13
     7    16     0    17     5    13
     7    17     5    16     0    13
     7    17     0    16     5    13

Answer 6

J, 54 bytes

Outputs one correct route. If no route exists it outputs nothing.

   f=.4 :'{.(x=+/|:2|@-/\"#.s A.y)#(s=.i.!6)A.''EFGHJK'''

   62 f 0 5 7 13 16 17
GJEKFH

52-byte code that outputs all routes (one per line):

f=.4 :'(x=+/|:2|@-/\"#.s A.y)#(s=.i.!6)A.''EFGHJK'''

38-byte code that outputs positions instead letters:

f=.4 :'p#~x=+/|:2|@-/\"#.p=.(i.!6)A.y'

Answer 7

Haskell, 109 bytes

import Data.List
a%b=abs$snd a-snd b
n#l=[map(fst)p|p<-permutations(zip['E'..]l),n==sum(zipWith(%)p(tail p))]

Usage example: 17 # [0, 5, 7, 13, 16, 17] which outputs all valid paths, i.e. ["EFGHIJ","JIHGFE"]. If there's no valid path, the empty list [] is returned.

The list of letters includes I (hope that's fine).

How it works: make a list of (name, position) pairs, permute and take those where the path length equals n and remove the position part.

Answer 8

Python + golfing-shortcuts, 123 bytes

A port of Logic Night's answer.

from s import*
def F(A,C):
 for B in Im(A):
  if s(abs(P-Q)for P,Q in z(B[1:],B))==C:p(['EFGHJK'[li(A,N)]for N in B]);break