Devoirs de mathématiques de quatrième année pour la semaine: un vendeur itinérant des plus inefficaces

10

Ma fille avait la tâche suivante pour ses devoirs de mathématiques. Imaginez six amis vivant sur une ligne, nommés E, F, G, H, J et K. Leurs positions sur la ligne sont comme indiqué (pas à l'échelle) ci-dessous:

Ainsi, F vit à cinq unités de E, et deux unités de G, et ainsi de suite.

Votre mission: créer un programme qui identifie un chemin qui visite chaque ami exactement une fois avec une longueur totale de n unités, en prenant les emplacements des amis et n comme entrées. Il doit signaler le chemin s'il le trouve (par exemple, pour la longueur 17, il peut signaler «E, F, G, H, J, K», et il doit se terminer correctement si aucune solution n'existe. Pour ce que ça vaut, j'ai terminé une solution non gérée dans Mathematica en 271. Je pense que c'est possible de façon beaucoup plus concise que cela.

code-golf graph-theory path-finding Michael Stern
la source
3
Cela pourrait être mieux en tant que programme qui prend des entrées (ex. [0, 5, 7, 13, 16, 17]Et 62) afin que vous puissiez vous assurer qu'il n'est pas spécifiquement codé en dur dans ce cas.
Poignée de porte
@ Doorknob, bon point. J'ai ajusté l'affectation en conséquence.
Michael Stern
1
Le chemin commence-t-il chez un ami?
xnor
1
Puis-je définir le format des chaînes d'entrée et de sortie? Une entrée comme "[0, 5, 7, 13, 16, 17], 62"et une sortie sont-elles "(7, 16, 0, 17, 5, 13)"correctes?
Logic Knight
1
@Geobits est simplement négligent de ma part. Corrigée.
Michael Stern

Réponses:

1

J, 54 octets

Génère un itinéraire correct. Si aucune route n'existe, elle ne produit rien.

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

   62 f 0 5 7 13 16 17
GJEKFH

Code de 52 octets qui génère tous les itinéraires (un par ligne):

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

Code de 38 octets qui génère des positions à la place des lettres:

f=.4 :'p#~x=+/|:2|@-/\"#.p=.(i.!6)A.y'
randomra
la source
Je ne peux pas contrôler le code, mais d'après votre résumé, cela semble être l'entrée la plus courte qui fait tout ce que le problème nécessite.
Michael Stern
6

Mathematica, 55 ou 90 octets

Mathematica vous avez dit? ;)

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

Il s'agit d'une fonction anonyme qui prend d'abord la position des amis (dans n'importe quel ordre), puis la longueur cible. Il retourne Missing[NotFound], si aucun chemin n'existe.

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

Je peux enregistrer quatre octets si le retour de tous les chemins valides est autorisé ( FirstCase-> Cases).

Le retour d'un tableau de chaînes est un peu plus lourd:

FromCharacterCode[68+#]&/@Ordering@FirstCase[Permutations@#,p_/;Tr@Abs@Differences@p==#2]&
Martin Ender
la source
Pourriez-vous ajuster pour qu'il réponde avec les lettres plutôt que seulement les emplacements?
Michael Stern
@MichaelStern Il n'est pas vraiment clair à partir de la question combien devrait être codé en dur et combien devrait faire partie des paramètres? L'entrée devrait-elle être quelque chose comme un mappage des lettres aux positions?
Martin Ender
Supposons que les lettres sont toujours dans l'ordre indiqué dans la ligne numérique ci-dessus (E, F, G, H, J, K). Les distances entre eux doivent être transmises à la fonction comme vous le faites dans votre solution.
Michael Stern
@MichaelStern J'ai ajouté une version qui renvoie un tableau de chaînes. Il prend en charge n'importe quel nombre de positions dans la liste, mais après Z, continuera avec les prochains caractères ASCII (pas que vous souhaitiez quand même exécuter mon code pour n> 20: D).
Martin Ender
5

Python 2, 154 148 octets

(ou 118 octets pour la solution générale)

Ce programme accepte une ligne avec une liste et un entier comme '[0, 5, 7, 13, 16, 17], n' sur stdin et imprime un chemin sur la sortie de longueur n ou rien si impossible.

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

Il est difficile d'écrire de petits programmes en Python qui nécessitent des permutations. Cette importation et cette utilisation sont très coûteuses.

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

La source de l'exigence OP avant la minifiante:

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

La solution générale (non minifiée):

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

En raison de l'algorithme simple et du grand nombre de combinaisons, l'exécution pour plus de 20 positions initiales sera très lente.

Logic Knight
la source
Vous pouvez enregistrer quelques octets avec from itertools import*. En outre, Python 3 peut être plus court avec input()et *a,c=map(...)s'il peut fonctionner avec le reste de votre programme.
grc
Merci pour le conseil d'importation. Je résiste à une installation et à une conversion py3 de ma base de code. J'attends que chaque module tiers que j'utilise soit disponible et stable sous py3 (j'utilise de nombreux modules anciens et obscurs).
Logic Knight
Pourriez-vous ajuster pour qu'il réponde avec les lettres plutôt que seulement les emplacements?
Michael Stern
chr(a.index(n)+69)?
Martin Ender
Belle optimisation. Mais je pense que @MichaelStern veut vraiment voir le 'EFGHJK', et c'était assez facile alors j'ai écrit le code de cette façon.
Logic Knight
4

J (48 ou 65)

Je suppose que cela peut être joué beaucoup plus. N'hésitez pas à l'utiliser comme un point de départ pour jouer au golf plus loin

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

Ou avec des lettres: 

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

Ce qu'il fait:

   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

(J'espère que ce format d'E / S est correct ...)

Comment ça marche:

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

Génère toutes les permutations de l'entrée

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

Calcule la distance

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

Voir les résultats qui sont les mêmes que l'entrée et recréer ces permutations (je soupçonne que certains caractères peuvent être rasés ici)

Avec des lettres:

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

Créer une liste des n premières lettres, où n est la longueur de la liste d'entrée

indices A. [: letters ]

fait la même chose que ci-dessus

ɐɔıʇǝɥʇuʎs
la source
Pouvez-vous l'ajuster pour rapporter la réponse en termes de lettres?
Michael Stern
@MichaelStern Je pourrais, mais cela ajouterait pas mal au nombre de caractères (J est terrible avec des cordes). Je vais l'essayer maintenant, pour voir quels pourraient être les dégâts.
ɐɔıʇǝɥʇuʎs
3

Octave, 73

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

Il n'y a vraiment pas de non-golf à cela, alors laissez-moi essayer d'expliquer ... de l'intérieur vers l'extérieur, nous permutons toutes les distances, puis pour chaque permutation, nous prenons les différences entre les maisons, prenons la valeur absolue comme distance, ajoutez-les vers le haut, trouver l'indice de la première permutation avec la distance souhaitée, et permuter les lettres et trouver cette permutation particulière des lettres.

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

qui est 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 =

(vide pour les entrées impossibles)

dcsohl
la source
Je ne sais pas quel est l'accord, mais perms()dans Octave 3.6.2 sur ideone.com a des problèmes avec le vecteur de chaînes.
Alex A.
Intéressant. J'ai 3.8.1 localement.
dcsohl
2

Matlab (86)

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

Exemple dans lequel une solution existe:

>> 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
>>

Exemple dans lequel une solution n'existe pas:

>> 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)

Si le format de sortie peut être assoupli en produisant des positions au lieu de lettres et en produisant une matrice vide si aucune solution n'existe:

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

Exemple dans lequel une solution existe:

>> 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

Exemple dans lequel une solution n'existe pas:

>> 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)

S'il est acceptable que le programme fournisse tous les chemins valides :

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

Exemple dans lequel une solution existe:

>> 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
Luis Mendo
la source
1

Haskell, 109 octets

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))]

Exemple d'utilisation: 17 # [0, 5, 7, 13, 16, 17]qui génère tous les chemins valides, c'est-à-dire ["EFGHIJ","JIHGFE"]. S'il n'y a pas de chemin valide, la liste vide []est renvoyée.

La liste des lettres comprend I(j'espère que ça va).

Comment ça marche: faites une liste de (name, position)paires, permutez et prenez celles où la longueur du chemin est égale net supprimez la partie de position.

nimi
la source