10
\$\begingroup\$

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.

\$\endgroup\$
  • 3
    \$\begingroup\$ This might be better as a program that takes inputs (ex. [0, 5, 7, 13, 16, 17] and 62) so that you can make sure it's not specifically hard-coded to this case. \$\endgroup\$ – Doorknob Feb 19 '15 at 1:42
  • \$\begingroup\$ @Doorknob, good point. I have adjusted the assignment accordingly. \$\endgroup\$ – Michael Stern Feb 19 '15 at 1:56
  • 1
    \$\begingroup\$ Does the path start at any friend? \$\endgroup\$ – xnor Feb 19 '15 at 2:23
  • 1
    \$\begingroup\$ Can I define the format of the input and output strings? Is an input like "[0, 5, 7, 13, 16, 17], 62" and an output "(7, 16, 0, 17, 5, 13)" ok? \$\endgroup\$ – Logic Knight Feb 19 '15 at 6:15
  • 1
    \$\begingroup\$ @Geobits just sloppiness on my part. Corrected. \$\endgroup\$ – Michael Stern Feb 19 '15 at 16:07
1
\$\begingroup\$

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'
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I can't vet the code, but per your summary of it, this seems to be the shortest entry that does everything the problem requires. \$\endgroup\$ – Michael Stern Feb 23 '15 at 17:34
6
\$\begingroup\$

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]&
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Could you adjust so that it responds with the letters rather than just the locations? \$\endgroup\$ – Michael Stern Feb 19 '15 at 14:39
  • \$\begingroup\$ @MichaelStern It's not really clear from the question how much should be hardcoded and how much should be part of the parameters? Should the input be something like a mapping from letters to positions? \$\endgroup\$ – Martin Ender Feb 19 '15 at 15:02
  • \$\begingroup\$ Assume the letters are always in the order given in the number line above (E, F, G, H, J, K). The distances between them should be passed to the function as you do in your solution. \$\endgroup\$ – Michael Stern Feb 19 '15 at 16:04
  • \$\begingroup\$ @MichaelStern I added a version that returns an array of strings. It supports any number of positions in the list, but after Z will continue with the next ASCII characters (not that you want to run my code for n > 20 anyway :D). \$\endgroup\$ – Martin Ender Feb 19 '15 at 19:49
5
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ You could save a few bytes with from itertools import*. Also, Python 3 might be shorter with input() and *a,c=map(...) if it can work with the rest of your program. \$\endgroup\$ – grc Feb 19 '15 at 6:08
  • \$\begingroup\$ Thanks for the import tip. I am resisting a py3 install and conversion of my code base. I am waiting until every 3rd party module I use is available and stable under py3 (I use many old and obscure ones). \$\endgroup\$ – Logic Knight Feb 19 '15 at 6:21
  • \$\begingroup\$ Could you adjust so that it responds with the letters rather than just the locations? \$\endgroup\$ – Michael Stern Feb 19 '15 at 14:38
  • \$\begingroup\$ chr(a.index(n)+69)? \$\endgroup\$ – Martin Ender Feb 20 '15 at 19:52
  • \$\begingroup\$ Nice optimisation. But I think @MichaelStern really wants to see the 'EFGHJK', and it was easy enough so I wrote the code that way. \$\endgroup\$ – Logic Knight Feb 21 '15 at 11:40
4
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Can you adjust it to report the answer in terms of letters? \$\endgroup\$ – Michael Stern Feb 19 '15 at 18:17
  • \$\begingroup\$ @MichaelStern I could, but that would add quite a bit to the character count (J is terrible with strings). I'll try it now, to see what the damage might be. \$\endgroup\$ – ɐɔıʇǝɥʇuʎs Feb 19 '15 at 18:18
3
\$\begingroup\$

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)

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I don't know what the deal is, but perms() in Octave 3.6.2 on ideone.com is having issues with the vector of strings. \$\endgroup\$ – Alex A. Feb 20 '15 at 17:20
  • \$\begingroup\$ Interesting. I have 3.8.1 locally. \$\endgroup\$ – dcsohl Feb 20 '15 at 21:26
2
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.