Golf moje tablice Ada

10

tło

Ada to język programowania, który nie jest dokładnie znany ze swojej zwięzłości.

Jednak jego dosłowna składnia tablicowa może teoretycznie pozwolić na dość zwięzłe specyfikacje tablic. Oto prosty opis EBNF dosłownej składni tablicowej ( możliwy do przejścia do bottlecaps.de :

array ::= positional_array | named_array
positional_array ::= expression ',' expression (',' expression)*
                   | expression (',' expression)* ',' 'others' '=>' expression
named_array ::= component_association (',' component_association)*
component_association ::= discrete_choice_list '=>' expression
discrete_choice_list ::= discrete_choice ('|' discrete_choice)*
discrete_choice ::= expression ('..' expression)? | 'others'

Dla uproszczenia ograniczymy się do jednowymiarowych tablic liczb całkowitych. Oznacza to, że do wartości wyrażeń użyjemy tylko liczb całkowitych. Być może w przyszłym wyzwaniu moglibyśmy wypróbować coś bardziej zaawansowanego (np. Deklarowanie zmiennych i tablic wielowymiarowych). Zdajesz nie muszą golfa literały całkowite .

Oto kilka przykładów literałów tablicowych Ada i równoważnej reprezentacji w Pythonie dla przejrzystości:

(1, 2, 3) = [1, 2, 3]
(1, others => 2) = [1, 2, 2, ..., 2]
(others => 1) = [1, 1, ..., 1]
(1 => 1, 2 => 3) = [1, 3]
(1|2 => 1, 3 => 2) = [1, 1, 2]
(1 => 1, 3 => 2, others => 3) = [1, 3, 2, 3, 3, ..., 3]

Wyzwanie

Celem tego wyzwania jest wygenerowanie najkrótszego literału tablicy Ada dla danej tablicy wejściowej. Zauważ, że tablice Ada mogą zaczynać się od dowolnego pożądanego indeksu, więc możesz wybrać, o ile ma być początkowy indeks, o ile każda wartość jest sekwencyjna. W tym przykładzie postanowiłem zacząć od 1, co jest idiomatyczne dla Ady, jednak możesz zacząć od dowolnej innej liczby całkowitej.

Wejście

Twój wkład będzie składał się z listy liczb całkowitych, w dowolnej dogodnej formie.

Wynik

Twój wynik będzie ciągiem tekstowym reprezentującym najkrótszy prawidłowy literał tablicy Ada, który reprezentuje listę liczb całkowitych wejściowych. Możesz użyć dowolnego początkowego indeksu na tej tablicy, ale twój wybór (cokolwiek to jest) musi zostać określony w odpowiedzi (indeks początkowy może być również dynamiczny).

Liczby całkowite należy przedstawić jako liczby dziesiętne ze znakiem, jak w przykładach. To wyzwanie nie obejmuje gry w golfa o wartościach całkowitych.

Przykłady

Oto kilka przykładów:

Simple: [1, 2, 3] -> (1,2,3)
Range: [1, 1, 1, 1, 1, 1, 1,] -> (1..7=>1)
Others: [1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1] -> (6=>2,others=>1)
Multiple Ranges: [1,1,1,1,1,2,2,2,2,2,1,1,1,1,1,2,2,2,2,2,1,1,1,1,1] -> (6..10|16..20=>2,others=>1)
Tiny Ranges: [1,1,2,2,1,1,1,1,1] -> (3|4=>2,others=>1)
Far Range: [[1]*5, [2]*100, [3]*5] -> (1..5=>1,6..105=>2,others=>3)
Alternation: [1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2] -> (1|3|5|7|9|11|13|15|17=>1,others=>2)
Big Number: [1234567890,1,1234567890] -> (2=>1,1|3=>1234567890)
Big-ish Number: [1234567,1,1234567] -> (1234567,1,1234567)
Solo: [-1] -> (1=>-1)
Huge Input: [[0],[1]*1000000000] -> (0,others=>1)
Positional Others: [1, 2, 3, 3, 3, 3, 3, 3] -> (1,2,others=>3)
Range and Choice, no Others: [1,1,1,12,12,3,3,3,3,3,3,3,3,3,3,4] -> (1..3=>1,4|5=>12,6..15=>3,16=>4)

Minimalne wymagania

  • Obsługuje co najmniej 100 liczb i dane wejściowe o długości co najmniej 256 cyfr.

  • Podaj poprawny wynik dla wszystkich takich danych wejściowych

    • Obejmuje umieszczenie „innych” na końcu
    • Obejmuje umieszczenie indeksu dla tablic pojedynczych elementów
  • Zakończ (najlepiej na TIO) dla każdego z powyższych wejść w niecałą minutę.

Najkrótsze rozwiązanie w bajtach wygrywa!

Wdrożenie referencyjne

Wypróbuj online!

Ta implementacja wykorzystuje dane wejściowe jako tablicę, przy czym każdy znak jest liczbą. Wielkie litery są specjalnymi stałymi dla dużych wartości. Argumentem programu jest „indeks początkowy”, którego należy użyć.

Sekcja „kod” w łączu TIO jest poprawnym rozwiązaniem problemu, a „nagłówek” i „stopka” implementują strukturę testową.

LambdaBeta
źródło
3
Czy „Far Range” przypadek exist po prostu oznacza, że możemy podjąć wejście w tym formacie, jeśli mamy wybierać lub, aby zaznaczyć, że muszą być w stanie obsługiwać tego formatu wejściowego, a także zwykłych tablic? Ponadto, czy ostatni przypadek testowy nie powinien po prostu generować (-1)?
Kudłaty
3
Przypadek „Dalekiego zasięgu” jest po prostu zapisany w ten sposób, aby zaoszczędzić miejsce. Rzeczywistym wejściem byłaby płaska tablica składająca się ze 110 liczb całkowitych, ale dane wyjściowe są prawidłowe. Jego celem jest pokazanie przypadków, w których słowo kluczowe „inni” powinno mieć krótszy zakres, który ma dłuższą reprezentację. ( 106..110=>3,others=>2byłoby dłuższe) Ostatni przypadek musi mieć indeks, ponieważ gramatyka nie zezwala na tablice pozycyjne z pojedynczym elementem ( positional_array ::= expression ',' expression (',' expression)*)
LambdaBeta
1
Teoretycznie, czy (i powinna) być w stanie zakodować listę 100 000 000 , skoro jest krótsza niż ? 1(1=>1,others=>1)(1..100000000=>1)
Arnauld
2
Czy możesz potwierdzić, że (1|3=>1234567,2=>1)jest to kolejne prawidłowe wyjście dla [1234567,1,1234567]?
Arnauld
1
Czy wolno nam używać Ady jako naszego wybranego języka?
Benjamin Urquhart

Odpowiedzi:

5

JavaScript (ES6),  307  304 bajtów

Zaoszczędzono 2 bajty dzięki @KevinCruijssen

To krępująco długie ...

a=>[b=([...a,m=''].map(o=(v,i)=>(i?p==v?!++n:m=o[(o[p]=[o[p]&&o[p]+'|']+(n?i-n+(n>1?'..':'|')+i:i))[m.length]?(x=i-n,j=p):j]:1)&&(p=v,M=n=0)),Object.keys(o).map(k=>j-k|!m[6]?o[k]+'=>'+k:O,O='others=>'+j).sort()),1/a[1]?[...a]:b,j-a.pop()?b:a.slice(0,x-1)+[,O]].map(a=>M=M[(s=`(${a})`).length]||!M?s:M)&&M

Wypróbuj online!

Arnauld
źródło
305 bajtów (-2) , tworząc zmienną dla duplikatu 'others=>'.
Kevin Cruijssen
@KevinCruijssen Thanks! (Uwaga: w twojej wersji tjest używany, zanim zostanie zdefiniowany; powodem, dla którego nie ulega awarii, jest to, że pierwsze 2 przypadki testowe w ogóle go nie używają; można to jednak łatwo naprawić bez żadnych kosztów.)
Arnauld
Ach ok. Tak naprawdę nie odrzuciłem twojej odpowiedzi, żeby zobaczyć, co zostało użyte. Zauważyłem po prostu, że miałeś 'others'dwa razy i próbowałem utworzyć dla niego zmienną bez zmiany wyniku. ;) Dzięki za wyjaśnienie i fajny golf przecinka za pomocą [,O]. :)
Kevin Cruijssen
2

05AB1E , 136 134 132 bajtów

"',ý'(ì')«ˆ"©.V"θ…ˆ†=>쪮.V"Uγ¨D€gPi˜IX.V}\ÙεQƶ0KDāαγ€g£}D2Fε¾iεнyg≠iyθyg<i'|ë„..}ý}}ë˜}'|ý„=>«Iyнн<è«}Ю.VgFDN._ć'>¡X.V}\¼}¯éIgi¦}н

EDYCJA: Naprawiono teraz dla wszystkich przypadków testowych.

Wypróbuj online lub sprawdź wszystkie przypadki testowe (z wyjątkiem jednego „Ogromnego wejścia”, ponieważ jest zbyt duży).

Wyjaśnienie:

"',ý'(ì')«ˆ"       # Push this string (function 1), which does:
 ',ý              '#  Join a list by ","
    '(ì           '#  Prepend a "("
       ')«        '#  Append a ")"
          ˆ        #  Pop and add it to the global array
            ©      # Store this string in the register (without popping)
             .V    # And execute it as 05AB1E code on the (implicit) input-list
"θ…ˆ†=>쪮.V"      # Push this string (function 2), which does:
 θ                 #  Pop and push the last element of the list
  …ˆ†=>ì           #  Prepend dictionary string "others=>"
        ª          #  Append that to the list which is at the top of the stack
         ®.V       #  And execute function 1 from the register     
             U     # Pop and store this string in variable `X`
γ                  # Get the chunks of equal elements in the (implicit) input-list
 ¨                 # Remove the last chunk
  D                # Duplicate the list of remaining chunks
   g              # Get the length of each
     Pi     }      # If all chunk-lengths are 1:
       ˜           #  Flatten the list of remaining chunks
        I          #  Push the input-list
         X.V       #  Execute function 2 from variable `X`
             \     # Discard the top of the stack (in case we didn't enter the if-statement)
Ù                  # Uniquify the (implicit) input-list
 ε                 # Map each unique value `y` to:
  Q                #  Check for each value in the (implicit) input-list if it's equal to `y`
                   #  (1 if truthy; 0 if falsey)
   ƶ               #  Multiply each by its 1-based index
    0K             #  Remove all 0s
      D            #  Duplicate it
       ā           #  Push a list [1, length] without popping the list itself
        α          #  Get the absolute difference at the same indices
         γ         #  Split it into chunks of the same values
          g       #  Get the length of each
            £      #  And split the duplicated indices-list into those parts
                   # (this map basically groups 1-based indices per value.
                   #  i.e. input [1,1,2,1,1,2,2,1,1] becomes [[[1,2],[4,5],[8,9]],[[3],[6,7]]])
 }D                # After the map: duplicate the mapped 3D list
   2F              # Loop 2 times:
     ε             #  Map the 3D list of indices to:
      ¾i           #   If the counter_variable is 1:
        ε          #    Map each list `y` in the 2D inner list to:
         н         #     Leave the first value
         ygi      #     And if there is more than one index:
             yθ    #      Push the last value as well
             yg<i  #      If there are exactly two indices:
              '|  '#       Push string "|"
             ë     #      Else (there are more than two indices)
              „..  #       Push string ".."
                 #      And join the first and last value by this string
        }}         #    Close the if-statement and map
      ë            #   Else:
       ˜           #    Flatten the 2D list
      }'|ý        '#   After the if-else: join by "|"
          „=>«     #   Append "=>"
       yнн         #   Get the very first index of this 2D list
          <        #   Decrease it by 1 to make it 0-based
      I    è       #   And index it into the input-list to get its value again
            «      #   Which is also appended after the "=>"
                 #  After the map: triplicate the result
       ®.V         #  Execute function 1 from the register
       g           #  Get the amount of items in the triplicated list
        F          #  Loop that many times:
         D         #   Duplicate the list
          N._      #   Rotate it the index amount of times
          ć        #   Extract the head; pop and push remainder and head
           '>¡    '#   Split this head by ">"
              X.V  #   And then function 2 is executed again from variable `X`
        }\         #  After the loop: discard the list that is still on the stack
          ¼        #  And increase the counter_variable by 1
                 # After looping twice: push the global array
     é             # Sort it by length
      Igi }        # If the input only contained a single item:
         ¦         #  Remove the very first item
           н       # And then only leave the first item
                   # (which is output implicitly as result)

Zobacz moją wskazówkę 05AB1E (sekcja Jak kompresować ciągi znaków, które nie są częścią słownika? ), Aby zrozumieć, dlaczego tak …ˆ†=>jest "others=>".

Kevin Cruijssen
źródło