Podwójnie połączona lista to struktura danych, w której każdy węzeł ma valuezarówno „łącza” do obu, jak previousi następnego nodesna liście. Rozważmy na przykład następujące węzły o wartościach 12, 99 i 37:

Tutaj węzły o wartościach 12 i 99 wskazują ich odpowiednie nextwęzły o wartościach 99 i 37 . Węzeł o wartości 37 nie ma nextwskaźnika, ponieważ jest ostatnim węzłem na liście. Podobnie, węzły o wartościach 99 i 37 wskazują ich odpowiednie previouswęzły, 12 i 99 , ale 12 nie ma previouswskaźnika, ponieważ jest to pierwszy węzeł na liście.

Ustawić

W praktyce „łącza” węzła są implementowane jako wskaźniki do lokalizacji poprzedniego i następnego węzła w pamięci. Dla naszych celów „pamięć” będzie tablicą węzłów, a lokalizacja węzła będzie jej indeksem w tablicy. Węzeł może być traktowany jako 3-krotna forma ( prev value next ). Powyższy przykład może wyglądać następująco:

Zamiast tego może to wyglądać tak:

Zaczynając od dowolnego węzła, możesz podążać za previouslinkami (pokazanymi jako pochodzenie czerwonych strzałek), aby dostać się do poprzedzających go węzłów i nextlinkami (zielonymi strzałkami), aby znaleźć kolejne węzły, aby uzyskać wszystkie wartości węzłów w kolejności: [12, 99, 37].

Pierwszy diagram powyżej może być reprezentowany w tablicy jako [[null, 12, 1], [0, 99, 2], [1, 37, null]]. Drugi więc byłby [[2, 99, 1], [0, 37, null], [null, 12, 0]].

Wyzwanie

Napisz program, który pobiera jako dane wejściowe tablicę węzłów i indeks węzła i zwraca, w kolejności listowej, wartości węzłów na tej samej podwójnie połączonej liście.

Komplikacja

„Pamięć” nie zawsze zawiera węzły tylko jednej listy. Może zawierać kilka list:

Powyższa tablica zawiera trzy podwójnie połączone listy, oznaczone kolorami dla Twojej wygody:

1. Węzły w indeksach 7, 10, 1, 4, 3, 12(widocznych jedynie nextodnośniki do zmniejszenia bałaganu; kliknij, aby powiększyć):

   

   Biorąc pod uwagę tę tablicę i dowolny z tych indeksów, Twój program powinien zwracać wartości w odpowiedniej kolejności [0, 1, 1, 2, 3, 5, 8].

2. Węzeł o indeksie 9:

   

   Biorąc pod uwagę indeks 9, twój program powinien powrócić [99].

3. Węzły w indeksach 11, 8, 0, 6, 2:

   

   Biorąc pod uwagę jeden z tych indeksów, powinien on zwrócić [2, 3, 5, 7, 11].

Zasady

Wejście

Twój program otrzyma jako dane wejściowe:

1. Lista odes węzłów (3 krotki jak opisano powyżej), gdzie 1 ≤ 𝒏 ≤ 1000, w dowolnym dogodnym formacie, np. Tablica tablic, „płaska” tablica liczb całkowitych o długości 3𝒏 itd.

   Elementy 3-krotki może znajdować się w dowolnej kolejności: ( prev value next ), ( next prev value ), itd. Dla każdego węzła, previ nextbędzie null(lub inną dogodną wartością, na przykład -1), wskazując na pierwszy lub ostatni węzeł podwójnie połączonej listy lub ważny indeks lista, oparta na 0 lub 1, co jest wygodne. valuebędzie 32-bitową liczbą całkowitą ze znakiem lub największą liczbą całkowitą obsługiwaną przez Twój język, w zależności od tego, która wartość jest mniejsza.

2. Indeks 𝒑 węzła na liście (1). Wskazany węzeł może być pierwszym węzłem na podwójnie połączonej liście, ostatnim, środkowym lub nawet jedynym.

Lista wejściowa (1) może zawierać dane patologiczne (np. Cykle, węzły wskazywane przez wiele innych węzłów itp.), Ale indeks wejściowy (2) zawsze będzie wskazywał węzeł, z którego można uzyskać pojedyncze, dobrze uformowane wyjście wydedukować.

Wynik

Twój program powinien wyświetlać wartości węzłów podwójnie połączonej listy, której członkiem jest węzeł o indeksie 𝒑, w kolejności list. Dane wyjściowe mogą być w dowolnym dogodnym formacie, ale dane muszą zawierać tylko węzły value.

Zwycięski

To jest golf golfowy . Najkrótsza odpowiedź w bajtach wygrywa. Obowiązują standardowe luki.

Przypadki testowe

Poniżej każdy przypadek testowy ma postać:

X)
prev value next, prev value next, ...
index
value value value ...

... gdzie Xjest litera identyfikująca przypadek testowy, drugi wiersz to lista wejściowa, trzeci wiersz to indeks wejściowy oparty na 0, a czwarty wiersz to wynik.

A) null 12 1, 0 99 2, 1 37 null
   1
   12 99 37

B) 2 99 1, 0 37 null, null 12 0
   1
   12 99 37

C) 8 5 6, 10 1 4, 6 11 null, 4 3 12, 1 2 3, 12 8 null, 0 7 2, null 0 10, 11 3 0, null 99 null, 7 1 1, null 2 8, 3 5 5
   4
   0 1 1 2 3 5 8

D) 8 5 6, 10 1 4, 6 11 null, 4 3 12, 1 2 3, 12 8 null, 0 7 2, null 0 10, 11 3 0, null 99 null, 7 1 1, null 2 8, 3 5 5
   0
   2 3 5 7 11

E) 8 5 6, 10 1 4, 6 11 null, 4 3 12, 1 2 3, 12 8 null, 0 7 2, null 0 10, 11 3 0, null 99 null, 7 1 1, null 2 8, 3 5 5
   9
   99

F) 13 80 18, 18 71 null, 5 10 19, 12 1 8, 19 21 null, 31 6 2, 17 5 26, 26 0 30, 3 -1 25, null 1 23, 27 6 17, 14 1 24, 28 -1 3, null 80 0, 20 4 11, 33 6 29, 24 9 33, 10 7 6, 0 67 1, 2 15 4, 32 1 14, null 1 31, 29 3 null, 9 -1 28, 11 5 16, 8 1 null, 6 3 7, null 8 10, 23 1 12, 15 5 22, 7 9 null, 21 3 5, null 3 20, 16 2 15
   18
   80 80 67 71

G) 13 80 18, 18 71 null, 5 10 19, 12 1 8, 19 21 null, 31 6 2, 17 5 26, 26 0 30, 3 -1 25, null 1 23, 27 6 17, 14 1 24, 28 -1 3, null 80 0, 20 4 11, 33 6 29, 24 9 33, 10 7 6, 0 67 1, 2 15 4, 32 1 14, null 1 31, 29 3 null, 9 -1 28, 11 5 16, 8 1 null, 6 3 7, null 8 10, 23 1 12, 15 5 22, 7 9 null, 21 3 5, null 3 20, 16 2 15
   8
   1 -1 1 -1 1 -1 1

H) 13 80 18, 18 71 null, 5 10 19, 12 1 8, 19 21 null, 31 6 2, 17 5 26, 26 0 30, 3 -1 25, null 1 23, 27 6 17, 14 1 24, 28 -1 3, null 80 0, 20 4 11, 33 6 29, 24 9 33, 10 7 6, 0 67 1, 2 15 4, 32 1 14, null 1 31, 29 3 null, 9 -1 28, 11 5 16, 8 1 null, 6 3 7, null 8 10, 23 1 12, 15 5 22, 7 9 null, 21 3 5, null 3 20, 16 2 15
   4
   1 3 6 10 15 21

I) 13 80 18, 18 71 null, 5 10 19, 12 1 8, 19 21 null, 31 6 2, 17 5 26, 26 0 30, 3 -1 25, null 1 23, 27 6 17, 14 1 24, 28 -1 3, null 80 0, 20 4 11, 33 6 29, 24 9 33, 10 7 6, 0 67 1, 2 15 4, 32 1 14, null 1 31, 29 3 null, 9 -1 28, 11 5 16, 8 1 null, 6 3 7, null 8 10, 23 1 12, 15 5 22, 7 9 null, 21 3 5, null 3 20, 16 2 15
   14
   3 1 4 1 5 9 2 6 5 3

J) 13 80 18, 18 71 null, 5 10 19, 12 1 8, 19 21 null, 31 6 2, 17 5 26, 26 0 30, 3 -1 25, null 1 23, 27 6 17, 14 1 24, 28 -1 3, null 80 0, 20 4 11, 33 6 29, 24 9 33, 10 7 6, 0 67 1, 2 15 4, 32 1 14, null 1 31, 29 3 null, 9 -1 28, 11 5 16, 8 1 null, 6 3 7, null 8 10, 23 1 12, 15 5 22, 7 9 null, 21 3 5, null 3 20, 16 2 15
   17
   8 6 7 5 3 0 9

K) 4 11 0, null 22 3, null 33 3, 1 44 4, 3 55 null, 7 66 7, 6 77 6
   3
   22 44 55

L) null -123 null
   0
   -123

05AB1E , 25 bajtów

è[¬D0‹#Isè]\[`sˆD0‹#Isè]¯

Wypróbuj online!

Wyjaśnienie

è[¬D0‹#Isè]\[`sˆD0‹#Isè]¯   # Arguments n, a
è                           # Get element at index n in a
 [¬D0‹#Isè]                 # Find the first element in the list
 [                          # While true, do
  ¬                         #   Head (get index of previous element)
   D0‹#                     #   Break if lower than 0
       Isè                  #   Get the element at that index
          ]                 # End loop
           \                # Delete top element of stack
            [`sˆD0‹#Isè]    # Iterate through list
            [               # While true, do
             `sˆ            #   Add value to global array and keep next index on stack
                D0‹#Isè     #   Same as above
                       ]    # End loop
                        ¯   # Push global array

Haskell , 79 65 59 55 bajtów

-6 bajtów dzięki Brute Force .

x#i|let-1!d=[];i!d=i:x!!i!!d!d=[x!!i!!1|i<-last(i!0)!2]

Definiuje funkcję, #która akceptuje listę list liczb całkowitych, gdzie nulljest reprezentowana jako -1, i zwraca listę wartości węzłów.

Wypróbuj online!

Wyjaśnienie

let-1!d=[];i!d=i:x!!i!!d!d

Zdefiniuj funkcję, !która iteruje przez węzły zaczynające się od węzła ii zwraca indeksy odwiedzonych list. Akceptuje drugi argument, dktóry określa, który indeks „krotki” ma być używany jako indeks następnego węzła ( d==2do iteracji do przodu, d==0do iteracji do tyłu).

(i!0)

Iteruj wstecz, zaczynając od podanego indeksu i zwracaj odwiedzone indeksy.

last(i!0)

Weź ostatnio odwiedzony indeks, który jest początkiem listy.

last(i!0)!2

Iteruj od początku listy.

[x!!i!!1|i<-last(i!0)!2]

Zamień każdy odwiedzony indeks na wartość węzła.

Python 2 , 60 bajtów

l,n=input()
while~n:m=n;n=l[n][0]
while~m:p,v,m=l[m];print v

Wypróbuj online!

To właściwie odpowiedź Chasa Browna, pomijając te golfa:

• Używam ponownie n, zapisując zadanie
• Przechowuję ostatni ważny nwm, pozwalając mi na to
• umieść wydruk po zadaniu w wierszu 3, oszczędzając mi ostateczny wydruk
• Używam tylko ~ n zamiast - ~ n, ponieważ wartości ujemne są tak samo prawdziwe jak wartości dodatnie, oszczędzając mi 2 znaki.

Czysty , 94 90 88 bajtów

import StdEnv
$l[_,u,v]|v<0=[u]=[u: $l(l!!v)]
?l= $l o until((>)0o hd)((!!)l o hd)o(!!)l

Wypróbuj online!

MATL , 39 bajtów

XHx`HwI3$)t]x6Mt`Hwl3$)tbhwt]x4L)Hw2I$)

Wypróbuj online!

Prawie bezpośredni port mojej odpowiedzi Octave, ale ta wersja najpierw znajduje koniec, a następnie działa w przeszłość, a nie na odwrót, co pozwoliło zaoszczędzić jeden bajt.

XHx           % Store array in H.
`HwI3$)t]     % Work to the end of the array
x6Mt          % Delete the end of array delimiter, and push the array end index twice
`Hwl3$)    t] % Work to the beginning of the array
       tbhw   % Append all indices found.
Hw2I$)        % Index into original array.

PHP, 132 bajty

<?list(,$x,$y)=$argv;parse_str($x);while(($q=$x[$y*3+1])>=0)$y=$q;do{$n[]=$x[$y*3+2];$y=$x[$y*3];}while($x[$y*3]);echo join(' ',$n);

Wypróbuj online!

Wejście jest traktowana jako kwerendy x[]=-1&x[]=1&x[]=1...(wszystkie węzły w płaskiej matrycy), w kolejności next, prev, po czym valuedla każdego węzła, z -1 używany do zakończenia węzłów.

Python 2 , 81 77 bajtów

a,n=input()
u=a[n][0]
while-~u:u,v,w=a[u]
while-~w:print v;u,v,w=a[w]
print v

Wypróbuj online!

EDYCJA: Dziękuję Panu Xcoder za 4 bajty ...

Pobiera listę krotek [u, v, w], gdzie u i w oznaczają -1, aby reprezentować początek / koniec połączonego segmentu listy.

Oktawa , 81 78 76 bajtów

function o=f(a,n)while q=a(n,1)o=a(n=q,2);end
while n=a(n,3)o=[o a(n,2)];end

Wypróbuj online!

Raczej prosta wersja. Wyjaśnienie pozostawia się czytelnikowi jako ćwiczenie. O wiele bardziej zabawna wersja jest przedstawiona poniżej:

Oktawa , 142 99 92 bajty

@(a,n)[(p=@(b,c,z){q=a(z,2),@()[b(b,c,a(z,c)),q]}{2-~a(z,c)}())(p,1,n),p(p,3,n)(end-1:-1:1)]

Wypróbuj online!

Słyszałem, że lubisz anonimowe funkcje ...

Pobiera nx3tablicę, w której pierwsza kolumna jest poprzednikiem, druga kolumna wartością, a trzecią wartością węzły następcze. Wszystkie indeksy węzłów są oparte na 1, co jest wartością domyślną w Octave.

% Create an anonymous function, taking an array a and first node n
@(a,n)
% Returns an array containing the predecessor and sucessor nodes
      [                                                                     ,                     ]
% Defines an recursive anonymous function (by supplying itself to the local namespace)
% which looks at the first column (c=1) or last column (c=3) of the input array to get the next nodes
       (p=@(p,c,z)                                                   )(p,1,n)
% Create a cell array, either containing the end node,
                    {q=a(z,2),                       
% ...or an array with all next  next nodes and the current node
% (note the use of an anonymous function taking no parameters to defer array access, in case of the last node)                
                              @()[p(p,c,a(z,c)),q]}
% depending whether the next node number is nonzero (followed by () to execute the deferred array access)
                                                    {2-~a(z,c)}()
% Do the same with c=3, reverse (function p builds the array right-to-left) and drop the current node to prevent a duplicate.                                                                             
                                                                             p(p,3,n)(end-1:-1:1)

Kotlin , 85 bajtów

{g,S->generateSequence(generateSequence(S){g[it][0]}.last()){g[it][2]}.map{g[it][1]}}

Upiększony

{g,S->
    generateSequence(generateSequence(S){g[it][0]}.last()){ g[it][2]}.map { g[it][1] }
}

Test

typealias Node=Triple<Int?,Int?,Int?>
data class Test(val input: List<Node>, val start:Int, val result: List<Int>)
val TEST = listOf<Test>(
Test(
listOf(Node(null, 12, 1), Node(0, 99, 2), Node(1, 37, null)),
1,
listOf(12, 99, 37)
),
Test(listOf(
Node(2, 99, 1), Node(0, 37, null), Node(null, 12, 0)),
1,
listOf(12, 99, 37)
),
Test(
listOf(Node(8, 5, 6), Node(10, 1, 4), Node(6, 11, null), Node(4, 3, 12), Node(1, 2, 3), Node(12, 8, null), Node(0, 7, 2), Node(null, 0, 10), Node(11, 3, 0), Node(null, 99, null), Node(7, 1, 1), Node(null, 2, 8), Node(3, 5, 5)),
4,
listOf(0, 1, 1, 2, 3, 5, 8)
),
Test(
listOf(Node(8, 5, 6), Node(10, 1, 4), Node(6, 11, null), Node(4, 3, 12), Node(1, 2, 3), Node(12, 8, null), Node(0, 7, 2), Node(null, 0, 10), Node(11, 3, 0), Node(null, 99, null), Node(7, 1, 1), Node(null, 2, 8), Node(3, 5, 5)),
0,
listOf(2, 3, 5, 7, 11)
),
Test(
listOf(Node(8, 5, 6), Node(10, 1, 4), Node(6, 11, null), Node(4, 3, 12), Node(1, 2, 3), Node(12, 8, null), Node(0, 7, 2), Node(null, 0, 10), Node(11, 3, 0), Node(null, 99, null), Node(7, 1, 1), Node(null, 2, 8), Node(3, 5, 5)),
9,
listOf(99)
),
Test(
listOf(Node(13, 80, 18), Node(18, 71, null), Node(5, 10, 19), Node(12, 1, 8), Node(19, 21, null), Node(31, 6, 2), Node(17, 5, 26), Node(26, 0, 30), Node(3, -1, 25), Node(null, 1, 23), Node(27, 6, 17), Node(14, 1, 24), Node(28, -1, 3), Node(null, 80, 0), Node(20, 4, 11), Node(33, 6, 29), Node(24, 9, 33), Node(10, 7, 6), Node(0, 67, 1), Node(2, 15, 4), Node(32, 1, 14), Node(null, 1, 31), Node(29, 3, null), Node(9, -1, 28), Node(11, 5, 16), Node(8, 1, null), Node(6, 3, 7), Node(null, 8, 10), Node(23, 1, 12), Node(15, 5, 22), Node(7, 9, null), Node(21, 3, 5), Node(null, 3, 20), Node(16, 2, 15)),
18,
listOf(80, 80, 67, 71)
),
Test(
listOf(Node(13, 80, 18), Node(18, 71, null), Node(5, 10, 19), Node(12, 1, 8), Node(19, 21, null), Node(31, 6, 2), Node(17, 5, 26), Node(26, 0, 30), Node(3, -1, 25), Node(null, 1, 23), Node(27, 6, 17), Node(14, 1, 24), Node(28, -1, 3), Node(null, 80, 0), Node(20, 4, 11), Node(33, 6, 29), Node(24, 9, 33), Node(10, 7, 6), Node(0, 67, 1), Node(2, 15, 4), Node(32, 1, 14), Node(null, 1, 31), Node(29, 3, null), Node(9, -1, 28), Node(11, 5, 16), Node(8, 1, null), Node(6, 3, 7), Node(null, 8, 10), Node(23, 1, 12), Node(15, 5, 22), Node(7, 9, null), Node(21, 3, 5), Node(null, 3, 20), Node(16, 2, 15)),
8,
listOf(1, -1, 1, -1, 1, -1, 1)
),
Test(
listOf(Node(13, 80, 18), Node(18, 71, null), Node(5, 10, 19), Node(12, 1, 8), Node(19, 21, null), Node(31, 6, 2), Node(17, 5, 26), Node(26, 0, 30), Node(3, -1, 25), Node(null, 1, 23), Node(27, 6, 17), Node(14, 1, 24), Node(28, -1, 3), Node(null, 80, 0), Node(20, 4, 11), Node(33, 6, 29), Node(24, 9, 33), Node(10, 7, 6), Node(0, 67, 1), Node(2, 15, 4), Node(32, 1, 14), Node(null, 1, 31), Node(29, 3, null), Node(9, -1, 28), Node(11, 5, 16), Node(8, 1, null), Node(6, 3, 7), Node(null, 8, 10), Node(23, 1, 12), Node(15, 5, 22), Node(7, 9, null), Node(21, 3, 5), Node(null, 3, 20), Node(16, 2, 15)),
4,
listOf(1, 3, 6, 10, 15, 21)
),
Test(
listOf(Node(13, 80, 18), Node(18, 71, null), Node(5, 10, 19), Node(12, 1, 8), Node(19, 21, null), Node(31, 6, 2), Node(17, 5, 26), Node(26, 0, 30), Node(3, -1, 25), Node(null, 1, 23), Node(27, 6, 17), Node(14, 1, 24), Node(28, -1, 3), Node(null, 80, 0), Node(20, 4, 11), Node(33, 6, 29), Node(24, 9, 33), Node(10, 7, 6), Node(0, 67, 1), Node(2, 15, 4), Node(32, 1, 14), Node(null, 1, 31), Node(29, 3, null), Node(9, -1, 28), Node(11, 5, 16), Node(8, 1, null), Node(6, 3, 7), Node(null, 8, 10), Node(23, 1, 12), Node(15, 5, 22), Node(7, 9, null), Node(21, 3, 5), Node(null, 3, 20), Node(16, 2, 15)),
14,
listOf(3, 1, 4, 1, 5, 9, 2, 6, 5, 3)
),
Test(
listOf(Node(13, 80, 18), Node(18, 71, null), Node(5, 10, 19), Node(12, 1, 8), Node(19, 21, null), Node(31, 6, 2), Node(17, 5, 26), Node(26, 0, 30), Node(3, -1, 25), Node(null, 1, 23), Node(27, 6, 17), Node(14, 1, 24), Node(28, -1, 3), Node(null, 80, 0), Node(20, 4, 11), Node(33, 6, 29), Node(24, 9, 33), Node(10, 7, 6), Node(0, 67, 1), Node(2, 15, 4), Node(32, 1, 14), Node(null, 1, 31), Node(29, 3, null), Node(9, -1, 28), Node(11, 5, 16), Node(8, 1, null), Node(6, 3, 7), Node(null, 8, 10), Node(23, 1, 12), Node(15, 5, 22), Node(7, 9, null), Node(21, 3, 5), Node(null, 3, 20), Node(16, 2, 15)),
17,
listOf(8, 6, 7, 5, 3, 0, 9)
),
Test(
listOf(Node(4, 11, 0), Node(null, 22, 3), Node(null, 33, 3), Node(1, 44, 4), Node(3, 55, null), Node(7, 66, 7), Node(6, 77, 6)),
3,
listOf(22, 44, 55)
),
Test(
listOf(Node(null, -123, null)),
0,
listOf(-123)
)
)

var f:(List<List<Int?>>,Int)-> Sequence<Int?> =
{g,S->generateSequence(generateSequence(S){g[it][0]}.last()){g[it][2]}.map{g[it][1]}}

fun main(args: Array<String>) {
    for ((input, start, result) in TEST) {
        val out = f(input.map { it.toList() }, start).toList()
        if (out != result) {
            throw AssertionError("$input $start $result $out")
        }
    }
}

TIO

TryItOnline

JavaScript ES6, 70 63 bajtów

(x,i,a)=>(h=_=>i&&h(a(x[i].v),i=x[i].n))(x.map(_=>i=x[i].p||i))

Przypadek testowy:

F([undefined,{p:0,v:12,n:2},{p:1,v:99,n:3},{p:2,v:37,n:0}],1,alert)