Längster Hypercube-Pfad

18

Herausforderung

Sie erhalten zwei unterschiedliche Bitfolgen gleicher Länge. (Zum Beispiel 000und 111.) Ihr Ziel ist es, einen Pfad von einem zum anderen zu finden, so dass:

  • Bei jedem Schritt ändern Sie nur ein Bit (Sie gehen 000zu einem 001, 010, 100).
  • Sie können dieselbe Bitfolge nicht zweimal besuchen.
  • Der Pfad ist unter diesen Bedingungen so lang wie möglich.

Wenn wir zum Beispiel von 000nach gehen 111, können wir den Weg nehmen

000, 001, 011, 010, 110, 100, 101, 111

der alle 8-Bit-Strings der Länge 3 aufruft, muss also so lang wie möglich sein.

Regeln

  • Es gelten Standardlücken.
  • Sie können die Eingabe als zwei Folgen von Nullen und Einsen oder als zwei Arrays von Nullen und Einsen oder als zwei Arrays von Booleschen Werten verwenden.
  • Sie können nicht die Eingabe als zwei ganzen Zahlen mit der rechten Binärdarstellung nehmen ( das Schreiben 000und 111wie 0und 7sind nicht gültig).
  • Wenn Sie möchten, können Sie die Länge der Bitfolgen als Eingabe verwenden.
  • Ihr Programm kann den Pfad ausgeben, indem es die jeweils besuchten Bitfolgen druckt oder ein Array der besuchten Bitfolgen zurückgibt (jeweils im gleichen Format wie die Eingabe).
  • Ihre Ausgabe sollte den Anfang und das Ende des Pfads enthalten (dies sind Ihre Eingaben).
  • Dies ist Code-Golf , der kürzeste Code in Bytes gewinnt.

Beispiele

0 1 -> 0, 1
10 01 -> 10, 00, 01 or 10, 11, 01
000 111 -> any of the following:

   000, 100, 110, 010, 011, 001, 101, 111

   000, 100, 101, 001, 011, 010, 110, 111

   000, 010, 110, 100, 101, 001, 011, 111

   000, 010, 011, 001, 101, 100, 110, 111

   000, 001, 101, 100, 110, 010, 011, 111

   000, 001, 011, 010, 110, 100, 101, 111

1001 1100 -> 1001, 0001, 0000, 0010, 0011, 0111, 0101, 0100, 0110, 1110, 1010, 1011, 1111, 1101, 1100 (other paths exist)
code-golf binary graph-theory Mischa Lawrow
quelle
1
Können wir auch Boolesche Werte anstelle von Einsen und Nullen verwenden?
Fehler
Sicher, das ist in Ordnung.
Mischa Lawrow
Dürfen wir davon ausgehen, dass wir nicht zwei gleiche Bit-Strings erhalten (oder dass wir in diesem Fall etwas unternehmen können)?
Jonathan Allan
1
@ JonathanAllan Ja, nehmen wir an, dass die Bit-Strings nicht gleich sind.
Mischa Lawrow
Related
Undichte Nonne

Antworten:

6

Schale , 27 26 24 Bytes

→foΛεẊδṁ≠ÖLm↓≠⁰←ġ→PΠmṠe¬

Brute Force, also sehr langsam. Probieren Sie es online!

Erläuterung

Schale liest natürlich von rechts nach links.

←ġ→PΠmṠe¬  Hypercube sequences ending in second input, say y=[1,1,0]
     mṠe¬  Pair each element with its negation: [[0,1],[0,1],[1,0]]
    Π      Cartesian product: [[0,0,1],[1,0,1],..,[1,1,0]]
   P       Permutations.
 ġ→        Group by last element
←          and take first group.
           The permutations are ordered so that those with last element y come first,
           so they are grouped together and returned here.

ÖLm↓≠⁰  Find first input.
  m     For each permutation,
   ↓≠⁰  drop all elements before the first input.
ÖL      Sort by length.

foΛεẊδṁ≠  Check path condition.
fo        Keep those lists that satisfy:
    Ẋ      For each adjacent pair (e.g. [0,1,0] and [1,1,0]),
      ṁ    take sum of
       ≠   absolute differences
     δ     of corresponding elements: 1+0+0 gives 1.
  Λε       Each value is at most 1.

→  Finally, return last element (which has greatest length).
Zgarb
quelle
4

Mathematica, 108 Bytes

a=#~FromDigits~2+1&;Last@PadLeft[IntegerDigits[#-1,2]&/@FindPath[HypercubeGraph@Length@#,a@#,a@#2,∞,All]]&

Eingang:

[{0, 0, 0, 0}, {1, 1, 1, 1}]

Ausgabe:

{{0, 0, 0, 0}, {0, 0, 0, 1}, {0, 0, 1, 1}, {0, 0, 1, 0}, {0, 1, 1, 0},
 {0, 1, 0, 0}, {0, 1, 0, 1}, {1, 1, 0, 1}, {1, 0, 0, 1}, {1, 0, 0, 0},
 {1, 1, 0, 0}, {1, 1, 1, 0}, {1, 0, 1, 0}, {1, 0, 1, 1}, {1, 1, 1, 1}}
Ben
quelle
3

Mathematica, 175 Bytes

Schöne erste Frage! 

(m=#;n=#2;Last@SortBy[(S=Select)[S[Rest@Flatten[Permutations/@Subsets[Tuples[{0,1},(L=Length)@m]],1],First@#==m&&Last@#==n&],Union[EditDistance@@@Partition[#,2,1]]=={1}&],L])&


Eingang

[{0, 0, 0}, {1, 1, 1}]

J42161217
quelle
3

Haskell , 212 207 Bytes

Das ist wahrscheinlich viel zu lang, aber es funktioniert jetzt endlich. (Danke an @Lynn für den kartesischen Produkttrick !) Thansk @nimi für -5 Bytes!

import Data.List
b%l=[l++[x|b/=last l,x`notElem`l,1==sum[1|(u,v)<-x`zip`last l,u/=v]]|x<-mapM id$[0>1..]<$b]
b!a|f<-nub.concat.((b%)<$>)=snd$maximum$map(length>>=(,))$filter((==b).last)$until(f>>=(==))f[[a]]

Probieren Sie es online!

Erläuterung:

b%l -- helper function:
    -- given a path l (that should end in b) this generates all possible extensions
    -- of l (if not possible also l itself) 
            x<-mapM id$[0>1..]<$b -- generate all possible vertices of the hypercube
             -- and check the criteria
           b/=last l,x`notElem`l,1==sum[1|(u,v)<-x`zip`last l,u/=v] 
             -- extend if possible
    [l++[x|  ...                                                   ]| ... ]
b!a| -- actual function: 
     -- first define a helper function:
    f<-nub.concat.((b%)<$>)
     -- begin with the vertex a and apply the function from above repeatedly
     -- until you cannot make the path any longer without violating the
     -- criteria 
                                                                             until(f>>=(==))f[[a]]
     -- only take the paths that actually end in b          
                                                          filter((==b).last)$
     -- and find the one with the maximum length    
                           =snd$maximum$map(length>>=(,))$
fehlerhaft
quelle
x<-mapM id$[1>0,1<0]<$b
Nimi
... brauchst du [True,False]? Wenn [False,True]auch klappt, kannst du verwenden [0>1..].
nimi
Na toll, danke, ich wusste nicht , dass Boolist Enum, und ich habe vergessen , dass <$verfügbar ist (zunächst versucht , *>die nicht in Prelude ist)!
Fehler
3

Mathematica 116 114 Bytes

Mit mehreren Bytes dank Mischa Lawrow gespeichert.

Last@FindPath[Graph[Rule@@@Cases[Tuples[Tuples[{0,1},{l=Length@#}],{2}],x_/;Count[Plus@@x,1]==1]],##,{1,2^l},Alll]&

Eingabe (8 Dimensionen)

[{1,0,0,1,0,0,0,1},{1,1,0,0,0,0,1,1}]//AbsoluteTiming

Ausgabe (Länge = 254, nach 1,82 Sekunden)

{1.82393, {{1, 0, 0, 1, 0, 0, 0, 1}, {0, 0, 0, 1, 0, 0, 0, 1}, {0, 0, 0, 0, 0, 0, 0, 1}, {0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 1, 0}, {0, 0,0, 0, 0, 0, 1, 1}, {0, 0, 0, 0, 0, 1, 1, 1}, {0, 0, 0, 0, 0, 1, 0, 1}, {0, 0, 0, 0, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 1, 1, 0}, {0, 0, 0, 0,1, 1, 1,0}, {0, 0, 0, 0, 1, 0, 1, 0}, {0, 0, 0, 0, 1, 0, 0, 0}, {0, 0, 0, 0, 1, 0, 0, 1}, {0, 0, 0, 0, 1, 0, 1, 1}, {0, 0, 0, 0,1, 1, 1, 1}, {0, 0, 0, 0, 1, 1, 0, 1}, {0, 0, 0, 0, 1, 1, 0, 0}, {0, 0, 0, 1, 1, 1, 0, 0}, {0, 0, 0, 1, 0, 1, 0, 0}, {0, 0, 0, 1,0, 0, 0, 0}, {0, 0, 0, 1, 0, 0, 1, 0}, {0, 0, 0, 1, 0, 0, 1, 1}, {0, 0, 0, 1, 0, 1, 1, 1}, {0, 0, 0, 1, 0, 1, 0, 1}, {0, 0, 0, 1, 1, 1, 0, 1}, {0, 0, 0, 1, 1, 0, 0, 1}, {0, 0, 0, 1, 1, 0, 0, 0}, {0, 0, 0, 1, 1, 0, 1, 0}, {0, 0, 0, 1, 1, 0, 1, 1}, {0, 0, 0, 1,1, 1, 1, 1}, {0, 0, 0, 1, 1, 1, 1, 0}, {0, 0, 0, 1, 0, 1, 1, 0}, {0, 0, 1, 1, 0, 1, 1, 0}, {0, 0, 1, 0, 0, 1, 1, 0}, {0, 0, 1, 0,0, 0, 1, 0}, {0, 0, 1, 0, 0, 0, 0, 0}, {0, 0, 1, 0, 0, 0, 0, 1}, {0, 0, 1, 0, 0, 0, 1, 1}, {0, 0, 1, 0, 0, 1, 1, 1}, {0, 0, 1, 0,0, 1, 0, 1}, {0, 0, 1, 0, 0, 1, 0, 0}, {0, 0, 1, 0, 1, 1, 0, 0}, {0, 0, 1, 0, 1, 0, 0, 0}, {0, 0, 1, 0, 1, 0, 0, 1}, {0, 0, 1, 0,1, 0, 1, 1}, {0, 0, 1, 0, 1, 0, 1, 0}, {0, 0, 1, 0, 1, 1, 1, 0}, {0, 0, 1, 0, 1, 1, 1, 1}, {0, 0, 1, 0, 1, 1, 0, 1}, {0, 0, 1, 1,1, 1, 0, 1}, {0, 0, 1, 1, 0, 1, 0, 1}, {0, 0, 1, 1, 0, 0, 0, 1}, {0, 0, 1, 1, 0, 0, 0, 0}, {0, 0, 1, 1, 0, 0, 1, 0}, {0, 0, 1, 1,0, 0, 1, 1}, {0, 0, 1, 1, 0, 1, 1,1}, {0, 0, 1, 1, 1, 1, 1, 1}, {0, 0, 1, 1, 1, 0, 1, 1}, {0, 0, 1, 1, 1, 0, 0, 1}, {0, 0, 1, 1,1, 0, 0, 0}, {0, 0, 1, 1, 1, 0, 1, 0}, {0, 0, 1, 1, 1, 1, 1, 0}, {0, 0, 1, 1, 1, 1, 0, 0}, {0, 0, 1, 1, 0, 1, 0, 0}, {0, 1, 1, 1,0, 1, 0, 0}, {0, 1, 0, 1, 0, 1, 0, 0}, {0, 1, 0, 0, 0, 1, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 1}, {0, 1, 0, 0,0, 0, 1, 1}, {0, 1, 0, 0, 0, 0, 1, 0}, {0, 1, 0, 0, 0, 1, 1, 0}, {0, 1, 0, 0, 0, 1, 1, 1}, {0, 1, 0, 0, 0, 1, 0, 1}, {0, 1, 0, 0,1, 1, 0, 1}, {0, 1, 0, 0, 1, 0, 0, 1}, {0, 1, 0, 0, 1, 0, 0, 0}, {0, 1, 0, 0, 1, 0, 1, 0}, {0, 1, 0, 0, 1, 0, 1, 1}, {0, 1, 0, 0,1, 1, 1, 1}, {0, 1, 0, 0, 1, 1, 1, 0}, {0, 1, 0, 0, 1, 1, 0,0}, {0, 1, 0, 1, 1, 1, 0, 0}, {0, 1, 0, 1, 1, 0, 0, 0}, {0, 1, 0, 1,0, 0, 0, 0}, {0, 1, 0, 1, 0, 0, 0, 1}, {0, 1, 0, 1, 0, 0, 1, 1}, {0, 1, 0, 1, 0, 0, 1, 0}, {0, 1, 0, 1, 0, 1, 1, 0}, {0, 1, 0, 1,0, 1, 1, 1}, {0, 1, 0, 1, 0, 1, 0, 1}, {0, 1, 0, 1, 1, 1, 0, 1}, {0, 1, 0, 1, 1, 0, 0, 1}, {0, 1, 0, 1, 1, 0, 1, 1}, {0, 1, 0, 1,1, 0, 1, 0}, {0, 1, 0, 1, 1, 1, 1, 0}, {0, 1, 0, 1, 1, 1, 1, 1}, {0, 1, 1, 1, 1, 1, 1, 1}, {0, 1, 1, 0, 1, 1, 1, 1}, {0, 1, 1, 0,0, 1, 1, 1}, {0, 1, 1, 0, 0, 0, 1, 1}, {0, 1, 1, 0, 0, 0, 0, 1}, {0, 1, 1, 0, 0, 0, 0, 0}, {0, 1, 1, 0, 0, 0, 1, 0}, {0, 1, 1, 0,0, 1, 1, 0}, {0, 1, 1, 0, 0, 1, 0, 0}, {0, 1, 1, 0, 0, 1, 0, 1}, {0, 1, 1, 0, 1, 1, 0, 1}, {0, 1, 1, 0, 1, 0, 0, 1}, {0, 1, 1, 0,1, 0, 0, 0}, {0, 1, 1, 0, 1, 0, 1, 0}, {0, 1, 1, 0, 1, 0, 1, 1}, {0, 1, 1, 1, 1, 0, 1, 1}, {0, 1, 1, 1, 0, 0, 1, 1}, {0, 1, 1, 1,0, 0, 0, 1}, {0, 1, 1, 1, 0, 0, 0, 0}, {0, 1, 1, 1, 0, 0, 1, 0}, {0, 1, 1, 1, 0, 1, 1, 0}, {0, 1, 1, 1, 0, 1, 1, 1}, {0, 1, 1, 1,0, 1, 0, 1}, {0, 1, 1, 1, 1, 1, 0, 1}, {0, 1, 1, 1, 1, 0, 0, 1}, {0, 1, 1, 1, 1, 0, 0, 0}, {0, 1, 1, 1, 1, 0, 1, 0}, {0, 1, 1, 1,1, 1, 1, 0}, {0, 1, 1, 0, 1, 1, 1, 0}, {0, 1, 1, 0, 1, 1, 0, 0}, {0, 1, 1, 1, 1, 1, 0, 0}, {1, 1, 1, 1, 1, 1, 0, 0}, {1, 0, 1, 1,1, 1, 0, 0}, {1, 0, 0, 1, 1, 1, 0, 0}, {1, 0, 0, 0, 1, 1, 0, 0}, {1, 0, 0, 0, 0, 1, 0, 0}, {1, 0, 0, 0, 0, 0, 0, 0}, {1, 0, 0, 0,0, 0, 0, 1}, {1, 0, 0, 0, 0, 0, 1, 1}, {1, 0, 0, 0, 0, 0, 1, 0}, {1, 0, 0, 0, 0, 1, 1, 0}, {1, 0, 0, 0, 0, 1, 1, 1}, {1, 0, 0, 0,0, 1, 0, 1}, {1, 0, 0, 0, 1, 1, 0, 1}, {1, 0, 0, 0, 1, 0, 0, 1}, {1, 0, 0, 0, 1, 0, 0, 0}, {1, 0, 0, 0, 1, 0, 1, 0}, {1, 0, 0, 0,1, 0, 1, 1}, {1, 0, 0, 0, 1, 1, 1, 1}, {1, 0, 0, 0, 1, 1, 1, 0}, {1, 0, 0, 1, 1, 1, 1, 0}, {1, 0, 0, 1, 0, 1, 1, 0}, {1, 0, 0, 1,0, 0, 1, 0}, {1, 0, 0, 1, 0, 0, 0, 0}, {1, 0, 0, 1, 0, 1, 0, 0}, {1, 0, 0, 1, 0, 1, 0, 1}, {1, 0, 0, 1, 0, 1, 1, 1}, {1, 0, 0, 1,0, 0, 1, 1}, {1, 0, 0, 1, 1, 0, 1, 1}, {1, 0, 0, 1, 1, 0, 0, 1}, {1, 0, 0, 1, 1, 0, 0, 0}, {1, 0, 0, 1, 1, 0, 1, 0}, {1, 0, 1, 1,1, 0, 1, 0}, {1, 0, 1, 0, 1, 0, 1, 0}, {1, 0, 1, 0, 0, 0, 1, 0}, {1, 0, 1, 0, 0, 0, 0, 0}, {1, 0, 1, 0, 0, 0, 0, 1}, {1, 0, 1, 0,0, 0, 1, 1}, {1, 0, 1, 0, 0, 1, 1, 1}, {1, 0, 1, 0, 0, 1, 0, 1}, {1, 0, 1, 0, 0, 1, 0, 0}, {1, 0, 1, 0, 0, 1, 1, 0}, {1, 0, 1, 0,1, 1, 1, 0}, {1, 0, 1, 0, 1, 1, 0, 0}, {1, 0, 1, 0, 1, 0, 0, 0}, {1, 0, 1, 0, 1, 0, 0, 1}, {1, 0, 1, 0, 1, 0, 1, 1}, {1, 0, 1, 0,1, 1, 1, 1}, {1, 0, 1, 0, 1, 1, 0, 1}, {1, 0, 1, 1, 1, 1, 0, 1}, {1, 0, 0, 1, 1, 1, 0, 1}, {1, 0, 0, 1, 1, 1, 1, 1}, {1, 0, 1, 1,1, 1, 1, 1}, {1, 0, 1, 1, 0, 1, 1, 1}, {1, 0, 1, 1, 0, 0, 1, 1}, {1, 0, 1, 1, 0, 0, 0, 1}, {1, 0, 1, 1, 0, 0, 0, 0}, {1, 0, 1, 1,0, 0, 1, 0}, {1, 0, 1, 1, 0, 1, 1, 0}, {1, 0, 1, 1, 0, 1, 0, 0}, {1, 0, 1, 1, 0, 1, 0, 1}, {1, 1, 1, 1, 0, 1, 0, 1}, {1, 1, 0, 1,0, 1, 0, 1}, {1, 1, 0, 0, 0, 1, 0,1}, {1, 1, 0, 0, 0, 0, 0, 1}, {1, 1, 0, 0, 0, 0, 0, 0}, {1, 1, 0, 0, 0, 0, 1, 0}, {1, 1, 0, 0,0, 1, 1, 0}, {1, 1, 0, 0, 0, 1, 0, 0}, {1, 1, 0, 0, 1, 1, 0, 0}, {1, 1, 0, 0, 1, 0, 0, 0}, {1, 1, 0, 0, 1, 0, 0, 1}, {1, 1, 0, 0,1, 0, 1, 1}, {1, 1, 0, 0, 1, 0, 1, 0}, {1, 1, 0, 0, 1, 1, 1, 0}, {1, 1, 0, 0, 1, 1, 1, 1}, {1, 1, 0, 0, 0, 1, 1, 1}, {1, 1, 0, 1,0, 1, 1, 1}, {1, 1, 0, 1, 0, 0, 1, 1}, {1, 1, 0, 1, 0, 0, 0, 1}, {1, 1, 0, 1, 0, 0, 0, 0}, {1, 1, 0, 1, 0, 0, 1, 0}, {1, 1, 0, 1,0, 1, 1, 0}, {1, 1, 0, 1, 0, 1, 0, 0}, {1, 1, 0, 1, 1, 1, 0, 0}, {1, 1, 0, 1, 1, 0, 0, 0}, {1, 1, 0, 1, 1, 0, 0, 1}, {1, 1, 0, 1,1, 0, 1, 1}, {1, 1, 0, 1, 1, 0, 1, 0}, {1, 1, 0, 1, 1, 1, 1, 0}, {1, 1, 0, 1, 1, 1, 1, 1}, {1, 1, 0, 1, 1, 1, 0, 1}, {1, 1, 0, 0,1, 1, 0, 1}, {1, 1, 1, 0, 1, 1, 0, 1}, {1, 1, 1, 0, 0, 1, 0, 1}, {1, 1, 1, 0, 0, 0, 0, 1}, {1, 1, 1, 0, 0, 0, 0, 0}, {1, 1, 1, 0,0, 0, 1, 0}, {1, 1, 1, 0, 0, 1, 1, 0}, {1, 1, 1, 0, 0, 1, 0, 0}, {1, 1, 1, 0, 1, 1, 0, 0}, {1, 1, 1, 0, 1, 0, 0, 0}, {1, 1, 1, 0,1, 0, 0, 1}, {1, 1, 1, 0, 1, 0, 1, 1}, {1, 1, 1, 0, 1, 0, 1, 0}, {1, 1, 1, 0, 1, 1, 1, 0}, {1, 1, 1, 0, 1, 1, 1, 1}, {1, 1, 1, 0,0, 1, 1, 1}, {1, 1, 1, 1, 0, 1, 1, 1}, {1, 1, 1, 1, 0, 1, 1, 0}, {1, 1, 1, 1, 0, 0, 1, 0}, {1, 1, 1, 1, 0, 0, 0, 0}, {1, 1, 1, 1,0, 0, 0, 1}, {1, 1, 1, 1, 1, 0, 0, 1}, {1, 1, 1, 1, 1, 1, 0, 1}, {1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 0}, {1, 1, 1, 1,1, 0, 1, 0}, {1, 1, 1, 1, 1, 0, 0, 0}, {1, 0, 1, 1, 1, 0, 0, 0}, {1, 0, 1, 1, 1, 0, 0, 1}, {1, 0, 1, 1, 1, 0, 1, 1}, {1, 1, 1, 1,1, 0, 1, 1}, {1, 1, 1, 1, 0, 0, 1, 1}, {1, 1, 1, 0, 0, 0, 1, 1}, {1, 1, 0, 0, 0, 0, 1, 1}}}

Tuples[{0,1},{l=Length@#}],{2}]& generiert die Zahlen 0 ... 8 als Binärlisten.

Das äußere Tuples...{2}erzeugt alle geordneten Paare dieser Binärzahlen.

Plus@@x summiert jedes der Paare und erzeugt Tripletts von 0, 1.

Cases....Count[Plus@@x, 1]==1 Gibt alle Summen zurück, die eine einzelne 1 enthalten. Diese entstehen, wenn die beiden ursprünglichen Binärzahlen durch eine Flanke verbunden sind.

Rules verbindet die Eckpunkte des Graphen, wobei jeder Eckpunkt eine Binärzahl ist.

Graph Erstellt einen Graphen, der den Scheitelpunkten und Kanten entspricht.

FindPath findet bis zu 2 ^ n Pfade, die Scheitelpunkt a mit Scheitelpunkt b verbinden, die angegebenen Zahlen.

Last nimmt den längsten dieser Wege.

Für drei Dimensionen kann das Diagramm wie hier gezeigt in einer Ebene dargestellt werden:

Grafik flach

Für die Eingabe wird {0,0,0}, {1,1,1}Folgendes ausgegeben:

{{{0, 0, 0}, {0, 0, 1}, {0, 1, 1}, {0, 1, 0}, {1, 1, 0}, {1, 0, 0}, {1, 0, 1}, {1, 1, 1}}}

Diesen Pfad finden Sie in der obigen Grafik.

Es kann auch als folgender Pfad im 3-Raum gedacht werden, wobei jeder Scheitelpunkt einem Punkt entspricht {x,y,z} . {0,0,0} repräsentiert den Ursprung und {1,1,1} repräsentiert den "entgegengesetzten" Punkt in einem Einheitswürfel.

Der Lösungsweg entspricht also einem Durchlaufen von Kanten entlang des Einheitswürfels. In diesem Fall ist der Pfad ein Hamilton-Pfad: Er besucht jeden Scheitelpunkt einmal (dh ohne Kreuzungen und ohne ausgelassene Scheitelpunkte).

g4

DavidC
quelle
Gibt es einen einfachen Grund, warum 2 ^ n Pfade von a nach b genug Pfade sind, damit der längste von ihnen insgesamt der längste ist?
Mischa Lawrow
@ Mischa, eine sehr gute Frage.
DavidC
Hier ist eine Möglichkeit, darüber nachzudenken. Der längste Pfad, ein Hamilton-Pfad, ist um eins kleiner als die Anzahl der Ecken. (Wir zählen die Anzahl der Kanten auf dem Pfad.) Die Anzahl der Ecken beträgt 2 ^ n. Die maximale Pfadlänge wäre also 2 ^ n-1.
DavidC
Ich bin damit einverstanden, dass die maximale Pfadlänge immer entweder 2 ^ n Eckpunkte (wenn es sich um einen Hamilton-Pfad handelt) oder 2 ^ n-1 Eckpunkte (wenn ein Hamilton-Pfad aufgrund der Parität nicht möglich ist) aufruft. Das ist etwas anderes als meine Frage: Warum erzeugt man 2 ^ (n + 2) (ich glaube, 2 ^ n war die falsche Zahl)? Verschiedene Pfade (von denen einige sehr kurz sein können) garantieren, dass der längste von ihnen der sein wird längster aller verschiedenen Pfade.
Mischa Lawrow
Mit anderen Worten, warum 2^(l+2)in Ihrem Code?
Mischa Lawrow
3

Haskell , 141 123 Bytes

c(a:b)=(1-a:b):map(a:)(c b)
c _=[]
q#z=[z]:[z:s|w<-c z,notElem w q,s<-(w:q)#w]
x!y=snd$maximum[(p*>x,p)|p<-[x]#x,last p==y]

Verwendet Listen mit ganzen Zahlen. Probieren Sie es online!

Erläuterung

Die Hauptfunktion ist !und die Hilfsfunktionen sind #und c. Gibt bei einer gegebenen Liste von Bits calle möglichen Möglichkeiten zum Umdrehen einer von ihnen an, z [0,1,1] -> [[1,1,1],[0,0,1],[0,1,0]].

c(a:b)=        -- c on nonempty list with head a and tail b is
 (1-a:b):      -- the list with negated a tacked to b, then
 map(a:)(c b)  -- c applied recursively to b, with a tacked to each of the results.
c _=[]         -- c on empty list gives an empty list.

Die Funktion #nimmt eine Liste von Listen (der "Speicher") und eine Liste (die "anfängliche Bitfolge"). Es werden alle Hypercube-Pfade erstellt, die mit dem Anfangselement beginnen, nur unterschiedliche Bitstrings enthalten und die Strings im Speicher nicht betreten.

q#z=            -- # on memory q and initial string z is
 [z]:           -- the singleton path [z], and
 [z:s|          -- z tacked to each path s, where
  w<-c z,       -- w is obtained by flipping a bit of z,
  notElem w q,  -- w is not in the memory, and
  s<-(w:q)#w]   -- s is a path starting from w that avoids w and all elements of q.

Die Hauptfunktion !verbindet alles miteinander. Ein Trick , den ich hier verwenden ist p*>x( xwiederholte length pmal) statt length p. Da längere Wiederholungen xspäter in die natürliche Reihenfolge der Listen kommen, maximumwählt man in beiden Fällen den längsten Pfad, da die ersten Koordinaten der Paare vor den zweiten verglichen werden.

x!y=          -- ! on inputs x and y is
 snd$maximum  -- the second element of the maximal pair in
 [(p*>x,p)|   -- the list of pairs (p*>x,p), where
  p<-[x]#x,   -- p is a path starting from x that avoids stepping on x, and
  last p==y]  -- p ends in y.
Zgarb
quelle
2

Jelly ,  25  27 Bytes

+2 Bytes, um einen Fehler beim Golfen zu beheben :( Hoffentlich finde ich aber einen kürzeren Weg.

ṫi¥³ḣi
L2ṗŒ!瀵ạ2\S€ỊẠ×LµÞṪ

Ein vollständiges Programm, das die Bit-Strings mit 1und 2* als Listen verwendet. Die Argumente sind fromund to. Das Programm druckt eine Liste von Listen derselben.

* 0und 1können stattdessen auf Kosten eines Bytes verwendet werden ( ’zwischen L2ṗund Œ!ç€...zu dekrementieren).

Probieren Sie es online!

Wie?

Aktualisierung...

ṫi¥³ḣi - Link 1, getSlice: list of lists, bitstrings; list, toBitstring
   ³   - get 3rd command line argument (fromBitstring)
  ¥    - last two links as a dyad:
 i     -   index (of fromBitstring in bitstrings)
ṫ      -   tail (bitstrings) from (that) index
     i - index (of toBitstring in that result)
    ḣ  - head to (that) index

L2ṗŒ!瀵ạ2\S€ỊẠ×LµÞṪ - Main link: list, fromBitstring; list, toBitstring
L                    - length (of fromBitstring)
 2                   - literal two
  ṗ                  - Cartesian power (of implicit range(2)=[1,2] with L(fromBitstring))
                     - ...i.e. all unique bitstrings of the required length (using [1,2])
   Œ!                - all permutations (of that list)
     ç€              - call the last link (1) as a dyad (i.e. f(that, toBitstring))
       µ         µÞ  - sort by the monadic function:
         2\          -   2-wise reduce with:
        ạ            -     absolute difference
           S€        -   sum €ach
             Ị       -   insignificant (vectorises) (abs(z)<=1 - for our purposes it's really just used for z==1 since only positive integers are possible)
              Ạ      -   all truthy? (1 if so 0 otherwise)
                L    -   length
               ×     -   multiply
                   Ṫ - tail (the last one is one of the maximal results)
                     - implicit print
Jonathan Allan
quelle
Wie Jelly funktioniert, ist für mich ein Rätsel, aber eine Eingabe von [1,1]und [2,2]eine Ausgabe von, [[1, 1], [2, 1], [1, 2], [2, 2]]wenn ich es online versuche, was kein gültiger Pfad ist.
Mischa Lawrow
Hmm, ich muss etwas falsch gemacht haben - auf der Suche nach ...
Jonathan Allan
OK behoben durch Zurücksetzen eines meiner Golfs für 2 Bytes.
Jonathan Allan