Mathe-Hausaufgaben der vierten Klasse für die Woche: Ein ineffizienter reisender Verkäufer

10

Meine Tochter hatte die folgende Aufgabe für ihre Mathe-Hausaufgaben. Stellen Sie sich sechs Freunde vor, die in einer Linie mit den Namen E, F, G, H, J und K leben. Ihre Positionen in der Linie sind wie folgt angegeben (nicht maßstabsgetreu):

Somit lebt F fünf Einheiten von E und zwei Einheiten von G und so weiter.

Ihre Aufgabe: Erstellen Sie ein Programm, das einen Pfad identifiziert, der jeden Freund genau einmal mit einer Gesamtlänge von n Einheiten besucht, wobei die Standorte der Freunde und n als Eingaben verwendet werden. Es sollte den Pfad melden, wenn es ihn findet (zum Beispiel könnte es für Länge 17 "E, F, G, H, J, K" melden, und es sollte ordnungsgemäß beendet werden, wenn keine Lösung vorhanden ist. Für das, was es wert ist, habe ich abgeschlossen Eine ungolfed Lösung in Mathematica in 271 Bytes. Ich vermute, es ist viel präziser möglich.

code-golf graph-theory path-finding Michael Stern
quelle
3
Dies ist möglicherweise besser als ein Programm, das Eingaben (z. B. [0, 5, 7, 13, 16, 17]und 62) entgegennimmt, damit Sie sicherstellen können, dass es für diesen Fall nicht speziell fest codiert ist.
Türknauf
@ Doorknob, guter Punkt. Ich habe die Zuordnung entsprechend angepasst.
Michael Stern
1
Beginnt der Weg bei einem Freund?
xnor
1
Kann ich das Format der Eingabe- und Ausgabezeichenfolgen definieren? Ist eine Eingabe wie "[0, 5, 7, 13, 16, 17], 62"und eine Ausgabe in "(7, 16, 0, 17, 5, 13)"Ordnung?
Logic Knight
1
@Geobits nur Schlamperei meinerseits. Korrigiert.
Michael Stern

Antworten:

1

J, 54 Bytes

Gibt eine korrekte Route aus. Wenn keine Route vorhanden ist, wird nichts ausgegeben.

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

   62 f 0 5 7 13 16 17
GJEKFH

52-Byte-Code, der alle Routen ausgibt (eine pro Zeile):

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

38-Byte-Code, der Positionen anstelle von Buchstaben ausgibt:

f=.4 :'p#~x=+/|:2|@-/\"#.p=.(i.!6)A.y'
randomra
quelle
Ich kann den Code nicht überprüfen, aber laut Ihrer Zusammenfassung scheint dies der kürzeste Eintrag zu sein, der alles tut, was das Problem erfordert.
Michael Stern
6

Mathematica, 55 oder 90 Bytes

Mathematica hast du gesagt? ;)

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

Dies ist eine anonyme Funktion, die zuerst die Positionen der Freunde (in beliebiger Reihenfolge) und dann die Ziellänge einnimmt. Es wird zurückgegeben Missing[NotFound], wenn kein solcher Pfad vorhanden ist.

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

Ich kann vier Bytes speichern, wenn die Rückgabe aller gültigen Pfade zulässig ist ( FirstCase-> Cases).

Das Zurückgeben eines Arrays von Zeichenfolgen ist etwas umständlicher:

FromCharacterCode[68+#]&/@Ordering@FirstCase[Permutations@#,p_/;Tr@Abs@Differences@p==#2]&
Martin Ender
quelle
Könnten Sie anpassen, dass es mit den Buchstaben und nicht nur mit den Positionen reagiert?
Michael Stern
@MichaelStern Aus der Frage geht nicht wirklich hervor, wie viel fest codiert werden soll und wie viel Teil der Parameter sein soll. Sollte die Eingabe so etwas wie eine Zuordnung von Buchstaben zu Positionen sein?
Martin Ender
Angenommen, die Buchstaben befinden sich immer in der in der obigen Zahlenzeile angegebenen Reihenfolge (E, F, G, H, J, K). Die Abstände zwischen ihnen sollten wie in Ihrer Lösung an die Funktion übergeben werden.
Michael Stern
@MichaelStern Ich habe eine Version hinzugefügt, die ein Array von Zeichenfolgen zurückgibt. Es unterstützt eine beliebige Anzahl von Positionen in der Liste, aber danach Zwerden die nächsten ASCII-Zeichen fortgesetzt (nicht, dass Sie meinen Code für n> 20 ausführen möchten: D).
Martin Ender
5

Python 2, 154 148 Bytes

(oder 118 Bytes für die allgemeine Lösung)

Dieses Programm akzeptiert eine Zeile mit einer Liste und einer Ganzzahl wie '[0, 5, 7, 13, 16, 17], n' auf stdin und druckt einen Pfad auf die Ausgabe der Länge n oder nichts, wenn dies unmöglich ist.

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

Es ist schwierig, kleine Programme in Python zu schreiben, die Permutationen erfordern. Dieser Import und diese Verwendung sind sehr kostspielig.

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

Die Quelle für die OP-Anforderung vor dem 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

Die allgemeine Lösung (nicht minimiert):

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

Aufgrund des einfachen Algorithmus und der großen Anzahl von Kombinationen ist die Ausführung für mehr als 20 Anfangspositionen sehr langsam.

Logikritter
quelle
Sie könnten ein paar Bytes mit sparen from itertools import*. Außerdem ist Python 3 möglicherweise kürzer input()und *a,c=map(...)funktioniert mit dem Rest Ihres Programms.
Grc
Danke für den Importtipp. Ich widersetze mich einer py3-Installation und Konvertierung meiner Codebasis. Ich warte, bis jedes von mir verwendete Modul eines Drittanbieters unter py3 verfügbar und stabil ist (ich verwende viele alte und dunkle).
Logic Knight
Könnten Sie anpassen, dass es mit den Buchstaben und nicht nur mit den Positionen reagiert?
Michael Stern
chr(a.index(n)+69)?
Martin Ender
Schöne Optimierung. Aber ich denke, @MichaelStern möchte wirklich das 'EFGHJK' sehen, und es war einfach genug, also habe ich den Code so geschrieben.
Logic Knight
4

J (48 oder 65)

Ich nehme an, dass dies verdammt viel mehr Golf gespielt werden kann. Fühlen Sie sich frei, dies als Ausgangspunkt zu nutzen, um weiter Golf zu spielen

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

Oder mit Buchstaben: 

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

Was es macht:

   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

(Ich hoffe, dieses E / A-Format ist in Ordnung ...)

Wie es geht:

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

Erzeugt alle Permutationen der Eingabe

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

Berechnet die Entfernung

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

Sieht, welche Ergebnisse mit der Eingabe identisch sind, und generiert diese Permutationen neu (ich vermute, dass einige Zeichen hier abgeschabt werden können).

Mit Buchstaben:

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

Erstellen Sie eine Liste der ersten n Buchstaben, wobei n die Länge der Eingabeliste ist

indices A. [: letters ]

macht das gleiche wie oben

ɐɔıʇǝɥʇuʎs
quelle
Können Sie es anpassen, um die Antwort in Buchstaben zu melden?
Michael Stern
@MichaelStern Ich könnte, aber das würde die Anzahl der Zeichen erheblich erhöhen (J ist schrecklich mit Strings). Ich werde es jetzt versuchen, um zu sehen, was der Schaden sein könnte.
19ıʇǝɥʇuʎs
3

Oktave, 73

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

Es gibt wirklich kein Entgolf, also lassen Sie mich versuchen zu erklären ... von innen nach außen permutieren wir alle Entfernungen, dann nehmen wir für jede Permutation die Unterschiede zwischen Häusern, nehmen den absoluten Wert als Entfernung, addieren sie Suchen Sie nach oben den Index der ersten Permutation mit dem gewünschten Abstand, permutieren Sie die Buchstaben und suchen Sie die bestimmte Permutation der Buchstaben.

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

Das ist 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 =

(leer für unmögliche Eingaben)

dcsohl
quelle
Ich weiß nicht, was der Deal ist, aber perms()in Octave 3.6.2 auf ideone.com gibt es Probleme mit dem String-Vektor.
Alex A.
Interessant. Ich habe 3.8.1 vor Ort.
dcsohl
2

Matlab (86)

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

Beispiel, in dem eine Lösung existiert:

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

Beispiel, in dem es keine Lösung gibt:

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

Wenn das Ausgabeformat gelockert werden kann, indem Positionen anstelle von Buchstaben erzeugt werden und eine leere Matrix erzeugt wird, wenn keine Lösung vorhanden ist:

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

Beispiel, in dem eine Lösung existiert:

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

Beispiel, in dem es keine Lösung gibt:

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

Wenn es für das Programm akzeptabel ist, alle gültigen Pfade anzugeben :

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

Beispiel, in dem eine Lösung existiert:

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

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

Anwendungsbeispiel: 17 # [0, 5, 7, 13, 16, 17]Gibt alle gültigen Pfade aus, d ["EFGHIJ","JIHGFE"]. H. Wenn kein gültiger Pfad vorhanden ist, wird die leere Liste []zurückgegeben.

Die Liste der Briefe enthält I(hoffe, das ist in Ordnung).

So funktioniert es: Erstellen Sie eine Liste von (name, position)Paaren, permutieren Sie und nehmen Sie diejenigen, bei denen die Pfadlänge gleich ist, nund entfernen Sie den Positionsteil.

Nimi
quelle