<< Zurück

Dank der PPCG-Community hat der Weihnachtsmann jetzt seine Lagerwagen ausgeglichen. Jetzt muss er sie in die Transportdocks bringen, damit sie zu den Laderampen geschickt werden können. Leider sind die Spuren, um die Karren zu bewegen, ein Chaos, und er muss herausfinden, wie man sie überall hin bringt, ohne dass sie zusammenstoßen!

Herausforderung

Sie erhalten die Spuren für jeden der Wagen als Listen von "Etiketten" (oder Stationen). Die Wagen müssen so bewegt werden, dass sich zu keinem Zeitpunkt zwei Wagen auf demselben Etikett / derselben Station befinden. Im Wesentlichen bewegen sich die Wagen zwischen Positionen, die jeweils ein eindeutiges Etikett haben.

Aufgabe

Bestimmen Sie anhand der Spuren für jeden Wagen als Liste von Etikettenlisten (die alle positive ganze Zahlen sind), wann jeder Wagen freigegeben werden soll, um alle Wagen in kürzester Zeit sicher an ihren Bestimmungsort zu senden.

Hier finden Sie eine Erklärung, wie das gesamte Schienensystem funktioniert. Angenommen, der Warenkorb iwird zur Zeit t_iauf einer Spur mit Etiketten veröffentlicht T_i_1, T_i_2, ..., T_i_n. Während t_1des t_i-1Vorgangs ibefindet sich der Einkaufswagen nicht im Raster und kann ignoriert werden.

Zum Zeitrahmen t_ibefindet sich der Wagen auf dem Etikett T_i_1, und für jeden Zeitrahmen t_kvon t_ibis t_i+n(halb inklusive) befindet sich der Wagen auf dem Etikett T_i_k+1.

Für alle Zeiträume nach und einschließlich t_i+nbefindet sich der Wagen am Ziel und befindet sich nicht mehr im Raster.

Die Gesamtzeit t_Tist der letzte Zeitrahmen, in dem sich ein Wagen noch auf einer Spur im System befindet.

Spezifikationen

Geben Sie bei einem gegebenen Streckensystem eine Liste von Zeitrahmen zurück, in [t_1, t_2, ..., t_n]denen der idritte Wagen zum Zeitpunkt startet t_i, sodass keine andere Anordnung es den Wagen ermöglichen würde, mit einer geringeren Gesamtzeit sicher an ihr Ziel zu gelangen.

In Bezug auf die „sicher“, wenn jederzeit Rahmen von t_1bis t_Tmehr als ein Wagen auf jedem Etikett, dann kollidieren sie und die Anordnung war nicht „sicher“. Beachten Sie, dass sich zwei Wagen von a, bnach bewegen können b, aund trotzdem "sicher" sind, da die Gleise in beide Richtungen verlaufen.

Formatierungsspezifikationen

Die Eingabe wird als Matrix positiver Ganzzahlen in einem beliebigen vernünftigen Format angegeben. Die Ausgabe sollte als Liste positiver Ganzzahlen in einem angemessenen Format angegeben werden. Sie können die Ausgabe in Zeiträumen mit einem Index von Null angeben, sodass die Ausgabe eine Liste nicht negativer Ganzzahlen in einem angemessenen Format ist.

Regeln

• Standardschlupflöcher gelten
• Dies ist ein Code-Golf, so dass die kürzeste Antwort in Bytes gewinnt
• Es wird keine Antwort akzeptiert

Testfälle

Input -> Output
[[1, 2, 3], [4, 5, 6], [7, 8, 9]] -> [1, 1, 1]
[[1, 2, 3], [1, 2, 3]] -> [1, 2]
[[1, 2, 3], [3, 2, 1]] -> [1, 2]
[[1, 2, 3, 4], [4, 3, 2, 1]] -> [1, 1]
[[1, 1, 1], [1, 1, 1]] -> [1, 4]
[[1, 2, 3, 4], [2, 4, 3, 1]] -> [2, 1]
[[1, 2, 3, 4, 5, 6, 7], [2, 3, 3, 4], [5, 4, 3]] -> [1, 3, 4]
[[1, 2, 3, 4, 4], [1, 2, 3, 5, 4], [1, 2, 3, 4, 5]] -> [2, 3, 1]

^{Hinweis: Ich habe mich für diese Herausforderungsserie von Advent Of Code inspirieren lassen . Ich habe keine Verbindung zu dieser Site}

Eine Liste aller Herausforderungen in der Serie finden Sie im Abschnitt "Verknüpft" der ersten Herausforderung hier .

Viel Spaß beim Golfen!

JavaScript (ES7), 172 Byte

Gibt ein Array von 0-indizierten Zeitrahmen zurück.

a=>(g=k=>a.map((a,i)=>[l=a.length+1,i,a,L=L<l?l:L]).sort(([a],[b])=>a-b).every(([,n,b],i)=>b.every((c,t)=>o[t+=A[n]=k/L**i%L|0]&1<<c?0:o[t]|=1<<c),o=[],A=[])?A:g(k+1))(L=0)

NB : Dies kann nur mit Beschriftungen in [0-31] funktionieren. Dies ist eine JS-Grenze, keine Grenze des Algorithmus.

Testfälle

let f =

a=>(g=k=>a.map((a,i)=>[l=a.length+1,i,a,L=L<l?l:L]).sort(([a],[b])=>a-b).every(([,n,b],i)=>b.every((c,t)=>o[t+=A[n]=k/L**i%L|0]&1<<c?0:o[t]|=1<<c),o=[],A=[])?A:g(k+1))(L=0)

console.log(JSON.stringify(f([[1, 2, 3], [4, 5, 6], [7, 8, 9]])))                   // -> [0, 0, 0]
console.log(JSON.stringify(f([[1, 2, 3], [1, 2, 3]])))                              // -> [0, 1] or [1, 0]
console.log(JSON.stringify(f([[1, 2, 3], [3, 2, 1]])))                              // -> [0, 1] or [1, 0]
console.log(JSON.stringify(f([[1, 2, 3, 4], [4, 3, 2, 1]])))                        // -> [0, 0]
console.log(JSON.stringify(f([[1, 1, 1], [1, 1, 1]])))                              // -> [0, 3] or [3, 0]
console.log(JSON.stringify(f([[1, 2, 3, 4], [2, 4, 3, 1]])))                        // -> [1, 0]
console.log(JSON.stringify(f([[1, 2, 3, 4, 5, 6, 7], [2, 3, 3, 4], [5, 4, 3]])))    // -> [0, 2, 3]
console.log(JSON.stringify(f([[1, 2, 3, 4, 4], [1, 2, 3, 5, 4], [1, 2, 3, 4, 5]]))) // -> [1, 2, 0]

Kommentiert

a => (                         // given a = array of tracks
  g = k =>                     // g = recursive function taking k = counter
    a.map((t, i) => [          // map each track t in a to a new entry made of:
      l = t.length + 1,        //   - its length + 1 (l)
      i,                       //   - its original index in the input array
      t,                       //   - the original track data
      L = L < l ? l : L        //   and update the maximum track length L
    ])                         // end of map()
    .sort(([a], [b]) =>        // let's sort the tracks from shortest to longest
      a - b                    // so that solutions that attempt to delay short
    )                          // tracks are tried first
    .every(([, n, b],          // for each track b with an original position n,
                      i) =>    // now appearing at position i:
      b.every((c, t) =>        //   for each label c at position t in b:
        o[t += A[n] =          //     add to t the time frame A[n] corresponding
          k / L**i % L | 0     //     to this position (i) and this combination (k)
        ] & 1 << c ?           //     if the station c is already occupied at time t:
          0                    //       make every() fail
        :                      //     else:
          o[t] |= 1 << c       //       mark the station c as occupied at time t
      ),                       //   end of inner every()
      o = [],                  //   start with: o = empty array (station bitmasks)
      A = []                   //               A = empty array (time frames)
    ) ?                        // end of outer every(); if successful:
      A                        //   return A
    :                          // else:
      g(k + 1)                 //   try the next combination
)(L = 0)                       // initial call to g() + initialization of L