Stapelbare Sequenzen

29

Sie geben Karten mit den Bezeichnungen 0 bis 9 nacheinander aus einem Stapel und bilden Stapel, die bei 0 beginnen und um 1 aufwärts zählen.

  • Wenn Sie eine 0 austeilen, legen Sie diese auf den Tisch, um einen neuen Stapel zu beginnen.
  • Wenn Sie eine andere Karte austeilen, stapeln Sie sie auf eine Karte, die genau einen niedrigeren Wert hat und diese verdeckt. Wenn es keine solche Karte gibt, kann das Deck nicht gestapelt werden.

Bestimmen Sie bei einem gegebenen Stapel, ob er gestapelt werden kann, wenn die angegebene Reihenfolge eingehalten wird. Entscheiden Sie gleichermaßen anhand einer Liste von Ziffern, ob sie in disjunkte Untersequenzen für jedes Formular unterteilt werden können0,1,..,k

Beispiel

Nimm das Deck 0012312425. Die ersten beiden Karten sind 0, also gehen sie auf den Tisch:

Stacks: 00

  Deck: 12312425

Als nächstes beschäftigen wir uns mit einem 1, was weitergeht 0, egal welches:

        1
Stacks: 00

  Deck: 2312425

Wir geben dann ein Oben-Auf 2-Platziertes 1und das 3Oben-Auf -Platzierte aus.

        3
        2
        1
Stacks: 00

  Deck: 12425

Als nächstes wird die 1, 2und oben auf dem ersten Stapel und platziert 4oben auf dem zweiten. 

        4
        3
        22
        11
Stacks: 00

  Deck: 25

Jetzt müssen wir einen platzieren 2, aber es gibt keinen 1Stapel auf beiden. Dieses Deck war also nicht stapelbar.

Eingabe: Eine nicht leere Liste von Ziffern 0-9 oder eine Folge davon. Sie können nicht davon ausgehen, dass 0 immer in der Eingabe sein wird.

Ausgabe : Einer von zwei unterschiedlichen konsistenten Werten, einer für stapelbare Sequenzen und einer für nicht stapelbare

Testfälle:

Stapelbar:

0
01
01234
00011122234567890
012031
0120304511627328390

Nicht stapelbar:

1
021
0001111
0012312425
012301210
000112223

Der Einfachheit halber als Listen:

[0]
[0, 1]
[0, 1, 2, 3, 4]
[0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 4, 5, 6, 7, 8, 9, 0]
[0, 1, 2, 0, 3, 1]
[0, 1, 2, 0, 3, 0, 4, 5, 1, 1, 6, 2, 7, 3, 2, 8, 3, 9, 0]

[1]
[0, 2, 1]
[0, 0, 0, 1, 1, 1, 1]
[0, 0, 1, 2, 3, 1, 2, 4, 2, 5]
[0, 1, 2, 3, 0, 1, 2, 1, 0]
[0, 0, 0, 1, 1, 2, 2, 2, 3]

Gruppiert:

[[0], [0, 1], [0, 1, 2, 3, 4], [0, 0, 0, 1, 1, 1, 2, 2, 2, 3], [0, 1, 2, 0, 3, 1], [0, 1, 2, 0, 3, 0, 4, 5, 1, 1, 6, 2, 7, 3, 2, 8, 3, 9, 0]]
[[1], [0, 2, 1], [0, 0, 0, 1, 1, 1, 1], [0, 0, 1, 2, 3, 1, 2, 4, 2, 5]]

Bestenliste:

Code-Snippet anzeigen

code-golf sequence decision-problem subsequence xnor
quelle
Können wir eine Begrenzung der Listenlänge annehmen?
Orlp
@orlp Keine explizite Beschränkung.
Xnor
@xnor bittet er wahrscheinlich um Rechtfertigung, int a[99]in C
Leaky Nun
@ LuisMendo Du darfst, ich sage "nicht leer".
xnor
@xnor Ah, sorry, das habe ich nicht gesehen. Kann das Array 1-basiert sein? Das heißt, Zahlen von 1bis10
Luis Mendo

Antworten:

6

Haskell , 55 Bytes

Eine anonyme Funktion, die eine Liste von Ganzzahlen aufnimmt und a zurückgibt Bool.

Verbrauch: (all(<1).foldr(?)[]) [0,1,2,3,4].

all(<1).foldr(?)[]
m?l|(p,r)<-span(/=m+1)l=m:p++drop 1r

Probieren Sie es online!

Wie es funktioniert

  • foldr(?)[]Faltet das Listenargument mit von rechts nach links ?, beginnend mit einer leeren Liste. Das Ergebnis ist die Liste der Nummern in der Liste, die nicht über eine vorherige Nummer passen.
  • all(<1) testet, ob die einzigen Zahlen, die nicht über eine vorherige Zahl passen, Nullen sind.
  • m?lStellt eine Nummer meiner Liste lnicht passender Nummern voran . Wenn m+1es bereits in der Liste ist, kann es jetzt entfernt werden, wenn es oben drauf passt m.
    • (p,r)<-span(/=m+1)lTeilt die Liste lin zwei Teile pund rin der ersten Instanz der Nummer m+1. Wenn es keine gibt, ist der rechte Teil rleer.
    • m:p++drop 1rgeht mden geteilten Teilen voran . Wenn res nicht leer ist, muss es mit beginnen m+1, was durch entfernt wird drop 1.
Ørjan Johansen
quelle
Tolle Idee, das Stapeln in umgekehrter Reihenfolge durchzuführen! Ich habe versucht, Ihre ?rekursiv auszudehnen, habe aber die gleiche Länge .
Xnor
54 Bytes mitData.List.delete
H.PWiz
5

Schale , 9 Bytes

Λ¬ḞS:o-→ø

Probieren Sie es online!

Rückgabe 1für stapelbare Decks und 0für nicht stapelbare Decks.

Es sieht so aus, als hätte Ørjan Johansen in seiner Haskell-Antwort bereits den gleichen Algorithmus gefunden, aber in Husk ist dies offensichtlich viel prägnanter.

Erläuterung

Wir lösen das Problem von einer anderen Seite: Drehen Sie das Deck um und machen Sie absteigende Stapel. Wenn nach dem Durchlaufen des gesamten Decks alle Stapel eine 0 oben haben, ist das Deck stapelbar.

Λ¬ḞS:(-→)ø
         ø    Starting with the empty list (each element of this list will be the top card
              of a stack)
  ḞS          Traverse the input from right to left. For each card:
      -→        Remove the successor of this card from our list (if present)
    :           Add this card to our list
Λ¬            At the end, check if all the cards in our list are zeroes (falsy)
Löwe
quelle
4

Jelly , 15 11 Bytes

‘Ṭ€+\I>0FS¬

Probieren Sie es online!

Undichte Nonne
quelle
Oh! Sehr schön. Würde das ‘Ṭ€+\I>0FṀimmer funktionieren?
Jonathan Allan
@ JonathanAllan Nun, angesichts der Regel von 2 konsistenten Werten sollte es.
Erik der Outgolfer
4

C (gcc) 74 73 Bytes

f(int*l){int s[10]={},r=1;for(;~*l;s[*l++]++)r*=!*l||s[*l-1]--;return r;}

Erfordert, dass das Eingabearray das Ende mit -1 markiert. Anwendungsbeispiel:

int main(int argc, char** argv) {
    int a[] = {0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 4, 5, 6, 7, 8, 9, 0, -1};
    printf("%d\n",  f(a));
    return 0;
}
orlp
quelle
Was ist los mit plain return r?
Undichte Nonne
4

Netzhaut , 42 Bytes

O$#`(.)(?<=(\1.*?)*)
$#2
.
$*1,
^(,|1\1)+$

Probieren Sie es online!

Erläuterung

O$#`(.)(?<=(\1.*?)*)
$#2

Dies sortiert die Ziffern stabil danach, wie oft dieselbe Ziffer zuvor vorgekommen ist. Tatsächlich werden dadurch die verschiedenen Teilsequenzen der Kandidaten zusammengestellt. Die resultierende Zeichenfolge hat zuerst das erste Vorkommen jeder Ziffer und dann das zweite Vorkommen jeder Ziffer und so weiter. In einer stapelbaren Eingabe sieht das Ergebnis so aus 0123...0123...0123..., als würde jeder dieser Teilstrings an einer beliebigen Stelle enden.

Es ist am einfachsten festzustellen, ob die Eingabe ein solches Muster hat.

.
$*1,

Wir ersetzen jede Ziffer n durch ns 1 , gefolgt von einem Komma, um einzelne Ziffern zu trennen.

^(,|1\1)+$

Schließlich verwenden wir eine Vorwärtsreferenz, um fortlaufend ansteigende Ziffernfolgen abzugleichen. Wir versuchen, die gesamte Zeichenfolge abzugleichen, indem wir entweder ein einzelnes Komma (das eine 0 darstellt , die einen neuen Lauf startet) oder die vorherige 1Ziffer, der eine zusätzliche vorangestellt ist, abgleichen. Dies funktioniert nur, wenn die aktuelle Ziffer die Nachfolge der vorherigen Ziffer ist.

Martin Ender
quelle
3

TI-Basic (Serie 83), 25 Byte (49 Zeichen)

:min(seq(min(cumSum(Ans=I)≤cumSum(Ans=I-1)),I,1,9

Wie es funktioniert

Nimmt Eingaben als Liste auf Ans. Ansonsten Ausgänge 1für stapelbare Eingänge 0.

Für jeden I, cumSum(Ans=I)berechnet eine Liste der Anzahl der Male , Iin jedem Anfangssegment aufgetreten ist, so min(cumSum(Ans=I)≤cumSum(Ans=I-1))ist nur ein , wenn an jeder Position haben wir gesehen , I-1zumindest so oft wie I. Der Gesamtausdruck ist, 1wann immer dies für jedes zutrifft I.

Mischa Lawrow
quelle
3

JavaScript (ES6), 61 45 40 Bytes

Übernimmt die Eingabe als Liste.

a=>a.every(k=>a[~k]=!k|a[-k]--&&-~a[~k])

Testfälle

Code-Snippet anzeigen

Wie?

Für jeden Wert 0 ... 9 verfolgen wir die Anzahl der verfügbaren Stapel, wobei die vorhergehende Karte oben liegt. Diese Zähler werden in a [-9] bis a [0] gespeichert , wobei a [] das ursprüngliche Eingabearray ist. Der einzige Zähler, der mit den Eingabedaten kollidiert, ist eine [0] , aber das interessiert uns nicht wirklich, da 1) Karten mit der Bezeichnung 0 immer zulässig sind und ohnehin separat verarbeitet werden müssen und 2) der Eingabewert eine [0] ist ] wird verarbeitet, bevor eine Aktualisierung möglich ist.

a => a.every(k =>  // given the input array a, for each card k in a:
  a[~k] =          // the card is valid if:
    !k |           //   - it's a 0 or
    a[-k]-- &&     //   - there's at least one stack with the card k-1 atop
    -~a[~k]        // in which case we allow a new card k+1 and go on with the next card
)                  // otherwise, every() fails immediately
Arnauld
quelle
Du bist schneller als ich: o
Leaky Nun
@LeakyNun Du musst 20 Minuten weg gewesen sein ...;)
Arnauld
2

MATL , 16 Bytes

0*GQ"@yQy=f1)(]a

Die Eingabe ist ein Array von Zahlen.

Der Code wird 1in STDOUT ausgegeben, wenn die Eingabe stapelbar ist, oder wird mit einem Fehler und einer leeren Ausgabe in STDOUT beendet, wenn die Eingabe nicht stapelbar ist.

Probieren Sie es online!

Luis Mendo
quelle
2

Netzhaut , 110 Bytes

+`0((.*?)1((.*?)2((.*?)3((.*?)4((.*?)5((.*?)6((.*?)7((.*?)8((.*?)9)?)?)?)?)?)?)?)?)?
$2$4$6$8$10$12$14$16$+
^$

Probieren Sie es online! Link enthält Testfälle. Ich bekomme nicht oft zu verwenden $16...

Neil
quelle
2

Mathematica, 80 Bytes

Catch[Fold[#~Join~{-1}/.{{p___,#2-1,q___}:>{p,#2,q},-1:>Throw[1<0]}&,{},#];1>0]&
JungHwan min
quelle
2

R 88 Bytes

function(d){s={}
for(e in d)if(!e)s=c(s,0)else{k=match(e,s+1)
if(is.na(k))T=F
s[k]=e}
T}

Probieren Sie es online!

Funktion, die einen R-Vektor annimmt; kehrt TRUEfür stapelbar und FALSEfür nicht stapelbar zurück.

Erläuterung:

function(d){
 s <- {}              # initialize the stacks as empty
 for(e in d){         # iterate over the deck
  if(!e)              # if e is zero
   s <- c(s,0)        # start a new stack
  else {              # otherwise
   k <- match(e,s+1)  # find where e should go in s, NA if not there
   if(is.na(k))       # if no match (unstackable)
    T <- F            # set T to F (False)
   s[k] <- e          # set s[k] to e
  }
 T                    # return the value of T, which is TRUE by default and only gets changed in the loop to F.
}
Giuseppe
quelle
2

Nim, 133 Bytes

proc s(d:seq[int]):int=
 var
  t= @[0]
  r=1
 for c in d:(t.add(0);var f=0;for i,s in t.pairs:(if s==c:(t[i]=c+1;f=1;break));r*=f)
 r

1ob es funktioniert; 0wenn nicht.

Musste ein paar unkonventionelle Dinge erledigen, um mit der Veränderlichkeit von Variablen in for-Schleifen umzugehen, na ja.

Quelklef
quelle
1

Haskell , 77 75 Bytes

import Data.List
g[]=1<3
g(x:r)|s<-r\\[x-1]=g r&&(x<1||s/=r&&g s)
g.reverse

Probieren Sie es online! Verbrauch: g.reverse $ [0,1,2]. Gibt Truefür stapelbare Eingaben und Falsesonstiges zurück.

Dies ist eine rekursive Lösung, die eine gegebene Liste von hinten nach vorne durchläuft. Es setzt die Beobachtung um, dass

  • Die leere Liste ist stapelbar.
  • eine nicht-leere Liste mit Prefix rund letzte Element xist stapelbar , wenn rist stapelbar und entweder xNull oder beide x-1erscheint in rund rmit x-1entfernt wird auch stapelbar.
Laikoni
quelle
1

Java 8, 168 150 142 Bytes

a->{int x[]=new int[a.length],s=0,i;a:for(int n:a){if(n<1){s++;continue;}for(i=0;i<s;i++)if(x[i]==n-1){x[i]=n;continue a;}return 0;}return 1;}

Gibt zurück 0/ 1ob es korrekt stapelbar ist oder nicht.

Erläuterung:

Probieren Sie es hier aus.

a->{                         // Method with integer-array parameter and integer return-type
  int x[]=new int[a.length], //  Array for the stacks, (max) size equal to input-size
      s=0,                   //  Amount of stacks, starting at 0
      i;                     //  Index integer
  a:for(int n:a){            //  Loop (1) over the input
    if(n<1){                 //   If the current item is a zero:
      s++;                   //    Increase amount of stacks `s` by 1
      continue;}             //    And go to the next iteration
    for(i=0;i<s;i++)         //   Inner loop (2) over the stacks
      if(x[i]==n-1){         //    If a top item of a stack equals the current item - 1:
        x[i]=n;              //     Set this item in the stacks-array
        continue a;}         //     And go to the next iteration of loop (1)
    return 0;                //   If we haven't encountered a `continue`, return 0
  }                          //  End of loop (1)
  return 1;                  //  Return 1 if we were able to correctly stack everything
}                            // End of method
Kevin Cruijssen
quelle
1

C 248 Bytes

Hinweis: Um den Rückgabestatus zu drucken, geben Sie "echo $ status" in das Terminal ein

Rückgabestatus 0: Nicht stapelbar

Rückgabestatus 1: Stapelbar

Erläuterung: Inkrementiert das Array-Element mit dem Index, der der aktuell höchsten Stelle im Stapel entspricht. Anschließend prüft das Programm, ob dieses gerade inkrementierte Array-Element größer als das vorhergehende Element ist. Wenn ja, wird 0 zurückgegeben. Andernfalls gibt das Programm, wenn es ans Ende des Arrays gelangt, 1 zurück.

 main(int argc, char ** argv)
{
    static int stack[10];

    while ( *++argv != 0x0 )
    {
        stack[**argv - 0x30]++;

        if ( **argv - 0x30 > 0 )
        {
            if ( stack[**argv - 0x30] > stack[**argv - 0x30 - 1] )
            {
                return 0;
            }

        }

    }   

    return 1;
}
T. Salim
quelle
3
Willkommen bei Code Golf! Ihr Code und Ihr bytecount sollten übereinstimmen. Stellen Sie daher sicher, dass Sie eine vollständige Version Ihres Codes zur Verfügung haben. Die ungolfed Version ist die wahlweise freigestellte.
Stephen
0

Gelee , 15 Bytes

œp@ŒQẎµ0rṀ⁼Qµ¿Ẹ

Eine monadische Verknüpfung, die eine Liste nicht negativer Ganzzahlen erstellt und zurückgibt, 0wenn sie stapelbar oder 1nicht stapelbar ist.

Probieren Sie es online!

Wie?

œp@ŒQẎµ0rṀ⁼Qµ¿Ẹ - Link: list
             ¿  - while loop:
      µ     µ   - ...condition chain:
       0        -      literal zero
         Ṁ      -      maximum of current list
        r       -      inclusive range = [0,1,2,...,max(list)]
           Q    -      de-duplicate list (unique values in order of appearance)
          ⁼     -      equal?
                - ...do:
   ŒQ           -      distinct sieve (1s at first occurrences 0s elsewhere)
  @             -      use swapped arguments:
œp              -        partition (the list) at truthy values (of the distinct sieve)
     Ẏ          -      tighten (makes the list flat again ready for the next loop)
              Ẹ - any truthy? 1 if the resulting list has any non-zero integers remaining
                -           - effectively isNotEmpty for our purposes since a list of only
                -             zeros gets reduced to an empty list via the loop.
Jonathan Allan
quelle
Dein Zug: P: P
Leaky Nun
Na ja, ich bezweifle, dass ich 11 (oder 10 ?!) geschlagen habe und einschlafen muss: D
Jonathan Allan
0

Japt , 16 Bytes

£=k_¥T©°T}T=0ÃUd

Online testen! Ausgänge falsefür stapelbar, truefür nicht stapelbar.

Erläuterung

 £   = k_  ¥ T© ° T}T=0Ã Ud
UmX{U=UkZ{Z==T&&++T}T=0} Ud    Ungolfed
                               Implicit: U = input array
UmX{                   }       For each item X in the array:
                    T=0          Set T to 0.
      UkZ{         }             Remove the items Z where
          Z==T&&++T              Z == T (and if so, increment T).
                                 This has the effect of removing the largest stack.
    U=                           Reset U to the result.
                               This process is repeated U.length times, which is
                               evidently enough to handle any U.
                         Ud    Return whether there are any truthy items in U.
                               Any items not part of a stack are non-zero/truthy,
                               so this works for every possible case.
ETHproductions
quelle
0

05AB1E , 25 Bytes

ηε[DõQ#ZƒDNåiNõ.;Dëˆ#]¯OĀ

Die Herausforderung sieht nicht allzu schwierig aus, ist aber in 05AB1E ziemlich schwierig (zumindest für mich ..)

Ausgaben, 0wenn stapelbar und 1wenn nicht stapelbar.

Probieren Sie es online aus oder überprüfen Sie alle Testfälle .

Erläuterung:

η             # Prefixes of the (implicit) input
              #  i.e. '012031' → ['0','01','012','0120','01203','012031']
              #  i.e. `021` → ['0','02','021']
 ε            # Map each to:
  [           # Start an infinite inner loop
   D          # Duplicate the current value
    õQ#       # If it's an empty String, stop the infinite loop
   Z          # Get the maximum (without popping)
              #  i.e. '01203' → 3
              #  i.e. '02' → 2
    ƒ         # Inner loop `N` in the range [0,max]
     D        # Duplicate the current value
      Nåi     # If it contains the current digit `N`
              #  i.e. '01203' and 1 → 1 (truthy)
              #  i.e. '02' and 1 → 0 (falsey)
         Nõ.; # Remove the first one (by replacing the first `N` with an empty string)
              #  i.e. '1203' and 1 → '203'
         D    # And duplicate it again for the next iteration of the inner loop
      ë       # Else (does not contain the digit `N`):
       ˆ      # Push `N` to the global stack
        #     # And break the infinite loop
 ]            # Close the if-else, inner loop, infinite loop, and mapping (short for `}}}}`)
  ¯           # Push the global stack
   O          # Take the sum
              #  i.e. [] → 0
              #  i.e. ['2'] → 2
    Ā         # And get the trutified value of that (which we implicitly output as result)
              #  i.e. 0 → 0
              #  i.e. 2 → 1
Kevin Cruijssen
quelle
0

Java 8, 87 Bytes

Anstatt die Stapel aufzubauen, berechne ich einfach, ob ein Element auf den vorherigen Elementen nicht stapelbar ist, und gebe 0 zurück, wenn ein nicht stapelbares Element angetroffen wird. Wenn ich das Ende erreiche, ist der gesamte String stapelbar und 1 wird zurückgegeben:

s->{int l[]=new int[10];for(int n:s)if(n!=0&&l[n]>=l[n-1]||l[n]++<0)return 0;return 1;}

Probieren Sie es online!

Erläuterung:

s->{
  int l[]=new int[10];                # initialise the counts of each digit encountered prefix of element, all initialised to 0
  for(int n:s)                        # Iterate over all entries in input
    if(n!=0&&l[n]>=l[n-1]||++l[n]<0)  # Check if the element is stackable on the previous elements. Last check is always evaluated and false, but the sideeffect is to add the element to the handled, prefixed element og the next element.  
      return 0;                       # Unstackable
  return 1;                           # No unstackable elements, so the result is stackable
}
tfantonsen
quelle