Rechercher des séries de tableaux

14

Trouver les pistes à l'intérieur d'un tableau

Une exécution est définie comme trois nombres ou plus qui incrémentent le précédent avec un pas constant. Par exemple, [1,2,3] serait une exécution avec l'étape 1, [1,3,5,7] serait une exécution avec l'étape 2 et [1,2,4,5] n'est pas une exécution.

Nous pouvons exprimer ces exécutions par la notation "i à j par s" où i est le premier numéro de l'analyse, j est le dernier numéro de l'analyse et s est l'étape. Cependant, les exécutions de l'étape 1 seront exprimées "i à j".

Donc, en utilisant les tableaux avant, nous obtenons:

  • [1,2,3] -> "1to3"

  • [1,3,5,7] -> "1to7by2"

  • [1,2,4,5] -> "1 2 4 5"

Dans ce défi, c'est votre tâche de le faire pour les tableaux qui peuvent avoir plusieurs exécutions.

Exemple de code Python avec récursivité:

def arr_comp_rec(a, start_index):
    # Early exit and recursion end point
    if start_index == len(a)-1:
        return str(a[-1])
    elif start_index == len(a):
        return ''

    # Keep track of first delta to compare while searching
    first_delta = a[start_index+1] - a[start_index]
    last = True
    for i in range(start_index, len(a)-1):
        delta = a[i+1] - a[i]
        if delta != first_delta:
            last = False
            break
    # If it ran through the for loop, we need to make sure it gets the last value
    if last: i += 1

    if i - start_index > 1:
        # There is more than 2 numbers between the indexes
        if first_delta == 1:
            # We don't need by if step = 1
            return "{}to{} ".format(a[start_index], a[i]) + arr_comp_rec(a, i+1)
        else:
            return "{}to{}by{} ".format(a[start_index], a[i], first_delta) + arr_comp_rec(a, i+1)
    else:
        # There is only one number we can return
        return "{} ".format(a[start_index]) + arr_comp_rec(a, i)

IO est flexible

Contribution

Tableau d'entrées positives triées (pas de doublons)

Production

Chaîne des exécutions séparées par un espace ou un tableau de chaînes des exécutions

N'a pas besoin d'être gourmand dans une direction particulière

Peut avoir un espace de fin

Cas de test

In: [1000, 1002, 1004, 1006, 1008, 1010]
Out: "1000to1010by2"

In: [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233]
Out: "1to3 5 8 13 21 34 55 89 144 233"

In: [10, 20, 30, 40, 60]
Out: "10to40by10 60"

In: [5, 6, 8, 11, 15, 16, 17]
Out: "5 6 8 11 15to17"

In: [1, 2, 3, 4, 5, 6, 7, 9, 11, 13, 15, 30, 45, 50, 60, 70, 80, 90, 91, 93]
Out: "1to7 9to15by2 30 45 50to90by10 91 93"

C'est le donc le moins d'octets gagne.

WretchedLout
la source
1
connexes
Luis felipe De jesus Munoz
2
Doit-il être gourmand de gauche à droite? (c'est-à-dire [4, 5, 6, 7, 9, 11, 13, 15]ne peut pas l'être 4to6 7to15by2?)
Jonathan Allan
1
@JonathanAllan Non, il ne faut pas nécessairement le laisser gourmand.
WretchedLout
Je suppose qu'il n'y aura pas d'entrées en double?
Shieru Asakoto
1
Seuls les entiers positifs. @ Espaces de fuite Traurous acceptables.
WretchedLout

Réponses:

5

Gelée ,  42  40 octets

-2 merci à Kevin Cruijssen (filtrer les deux ḟ2, plutôt que de remplacer les deux par des zéros 2,0y)

ŒṖIE×LƲ€ḟ2SƊÞṪµ.ịU,Iḟ1ƊQ€Fż“to“by”ṁṖƊ$)K

Un programme complet imprimant le résultat.
(En tant que lien monadique, une liste contenant un mélange d'entiers et de caractères serait produite)

Essayez-le en ligne!
(Trop inefficace pour que le plus grand cas de test se termine dans les 60s, j'ai donc supprimé[1,2,3,4].)

Comment?

ŒṖIE×LƲ€ḟ2SƊÞṪµ.ịU,Iḟ1ƊQ€Fż“to“by”ṁṖƊ$)K - Main Link: list of numbers
ŒṖ                                       - all partitions
           ƊÞ                            - sort by last three links as a monad:
      Ʋ€                                 -   last four links as a monad for €ach:
  I                                      -     incremental differences (of the part)
   E                                     -     all equal?
     L                                   -     length (of the part)
    ×                                    -     multiply
        ḟ2                               -   filter discard twos
          S                              -   sum
             Ṫ                           - tail (gets us the desired partition of the input)
              µ                       )  - perform this monadic chain for €ach:
               .                         -   literal 0.5
                ị                        -   index into (the part) - getting [tail,head]
                 U                       -   upend - getting [head,tail]
                      Ɗ                  -   last three links as a monad:
                   I                     -     incremental differences (of the part)
                     1                   -     literal one
                    ḟ                    -     filter discard (remove the ones)
                  ,                      -   pair -> [[head,tail],[deltasWithoutOnes]]
                       Q€                -   de-duplicate €ach -> [[head,tail],[delta]] or [[head,tail],[]] or [[loneValue],[]]
                         F               -   flatten -> [head,tail,delta] or [head,tail] or [loneValue]
                                     $   -   last two links as a monad:
                                    Ɗ    -     last three links as a monad:
                           “to“by”       -       literal list [['t', 'o'], ['b', 'y']]
                                   Ṗ     -       pop (get flattened result without rightmost entry)
                                  ṁ      -       mould ["to","by"] like that (i.e. ["to","by"] or ["to"] or [])
                         ż               -     zip together      
                                       K - join with spaces
                                         - implicit print
Jonathan Allan
la source
'by' ne doit pas être utilisé si step = 1
WretchedLout
oh Gawwwd: p Merci pour l'avertissement!
Jonathan Allan
2,0ySƲÞpeut être joué au golf ḟ2SƊÞpour -2 octets.
Kevin Cruijssen
@KevinCruijssen très vrai, beau golf, merci
Jonathan Allan
1
@KevinCruijssen FYI Je me souviens pourquoi c'était là maintenant - à l'origine, j'essayais de faire mon tri avec un produit P, plutôt qu'avec une somme Set j'aurais eu besoin des zéros.
Jonathan Allan
6

Swift, 246 octets

func f(_ a:[Int]){
var c=a.count,m=a+a,z=0,r:String=""
for i in 1..<c{m[i]-=a[i-1];if m[i]==m[i-1]{m[i-1]=0}};m[0]=1
for i in 0..<c{if m[i]==0 {z=1}else if z==0{r+=" \(a[i])"}else{r+="to\(a[i])"+(m[i]>1 ? "by\(m[i])":"");z=0;m[i+1]=1}}
print(r)
}

Essayez-le en ligne!

dessiné
la source
4
Bienvenue sur Programmation Puzzles & Code Golf! Très belle première réponse. J'espère que vous resterez dans les parages car la communauté Swift ici est ... vraiment petite!
M. Xcoder
3

JavaScript (ES6), 129 octets

Renvoie un tableau de chaînes.

a=>(a.map((n,i)=>n+[n-a[i+1]||''])+'').replace(/(\d+)(-\d+)(?:,\d+\2)+,(\d+)/g,(_,a,b,c)=>a+'to'+(~b?c+'by'+-b:c)).split(/-\d+,/)

Essayez-le en ligne!

Comment?

Étape 1

Nous ajoutons d'abord à chaque numéro un suffixe composé d'un début '-'suivi de la différence avec le numéro suivant, à l'exception de la dernière entrée qui reste inchangée. Ce nouveau tableau est contraint à une chaîne.

(a.map((n, i) => n + [n - a[i + 1] || '']) + '')

Exemple:

Input : [ 1, 2, 3, 5, 9, 11, 13, 20 ]
Output: "1-1,2-1,3-2,5-4,9-2,11-2,13-7,20"

Étape 2

Nous identifions toutes les exécutions dans la chaîne résultante et les remplaçons par la notation appropriée.

.replace(
  /(\d+)(-\d+)(?:,\d+\2)+,(\d+)/g,
  (_, a, b, c) => a + 'to' + (~b ? c + 'by' + -b : c)
)

Exemple:

Input : "1-1,2-1,3-2,5-4,9-2,11-2,13-7,20"
Output: "1to3-2,5-4,9to13by2-7,20"

Étape 3

Enfin, nous avons divisé la chaîne sur les suffixes restants, y compris les virgules de fin.

.split(/-\d+,/)

Exemple:

Input : "1to3-2,5-4,9to13by2-7,20"
Output: [ '1to3', '5', '9to13by2', '20' ]
Arnauld
la source
2

Ruby , 125 118 bytes

->a{i=y=0;a.chunk{|x|-y+y=x}.map{|z,w|2-i<(s=w.size)?"#{w[i*s]}to#{w[~i=0]}"+"by#{z}"*(z<=>1)+' ':' '*i+w*' '*i=1}*''}

Essayez-le en ligne!

Explication

L'énumérable de Ruby a une chunkméthode utile qui fait précisément ce dont nous avons besoin ici - il regroupe les éléments par exécutions consécutives de la même valeur de retour du bloc, dans notre cas - la différence entre la valeur courante ( x) et précédente ( y).

La mise en garde est qu'une telle stratégie ne capturera pas le premier élément de la course, par exemple ici seuls les deux derniers éléments sont regroupés:

Input: [5, 6, 8, 11, 15, 16, 17]
Grouped: [[5, [5]], [1, [6]], [2, [8]], [3, [11]], [4, [15]], [1, [16, 17]]]

Par conséquent, lors du mappage sur les chaînes correctement formatées, lorsque nous rencontrons une nouvelle exécution potentielle (bloc avec> 1 élément), nous devons suivre si l'élément précédent était unique ( i=1) ou déjà utilisé dans une autre exécution ( i=0). S'il y a un élément unique inutilisé, il devient le point de départ de l'analyse et abaisse le seuil de taille de bloc de 3 à 2.

Kirill L.
la source
2

R , 180 175 octets

r=rle(c(0,diff(a<-scan())));for(j in 1:sum(1|r$l)){l=r$l[j];v=r$v[j];i=T+l-1;cat("if"(l>2-F,paste0(a[T][!F],"to",a[i],"by"[v>1],v[v>1]," "),c("",a[T:i])[-3^F]));T=i+1;F=l<3-F}

Essayez-le en ligne!

Conceptuellement, ceci est un portage de ma réponse Ruby , bien qu'évidemment assez différent techniquement.

5 octets enregistrés par JayCe.

Kirill L.
la source
Je voulais faire quelque chose avec rlemais j'étais trop paresseux ... vous pouvez enregistrer 1 octet sum(1|x)en length(x)
remplaçant
En fait, vous pouvez avoir seulement 1 cat pour 175 octets: TIO
JayCe
Ah, super, merci!
Kirill L.
2

R , 238 217 octets

Merci @digEmAll pour -19 octets.

function(v,R=rle(diff(v)),L=R$l,S=sum(L|1),Y=0)if(!S)cat(v)else for(i in 1:S){D=R$v[i]
N=L[i]-F
if(N>1){N=N+1
cat(v[Y+1],'to',v[Y+N],'by'[D>1],D[D>1],' ',sep='')
F=1}else{N=N+(i==S)
if(N>0)cat(v[Y+1:N],'')
F=0}
Y=Y+N}

Essayez-le en ligne!

J.Doe
la source
utiliser Fau lieu de ncomme il est déjà initialisé 0, ce qui devrait économiser quelques octets, je pense.
Giuseppe
Celui-ci est frustrant. Vous y êtes presque en utilisant simplement split, diffet rle. Malheureusement, la recherche gourmande de pistes signifie beaucoup de tripotage.
J.Doe
214 octets Presque là, le seul problème est parfois l'espacement
incorrect
C'est 'by'[D>1]une bonne astuce.
J.Doe
Cela semble fonctionner
correctement
1

JavaScript (Node.js) , 177 173 octets

a=>{for(h=t=p=d=0,o=[];(c=a[t])||h<t;p=c,t++)d||!c?c-p!=d?(o.push(...[[a[h]+"to"+p+(d>1?"by"+d:"")],[p],[p-d,p]][t-h<3?t-h:0]),d=0,h=t--):0:!d&&t-h?d=c-p:0;return o.join` `}

Essayez-le en ligne!

Shieru Asakoto
la source
1

Nettoyer , 208 ... 185 octets

import StdEnv,Data.List,Text
l=length
$[]=""
$k=last[u<+(if(v>[])("to"<+last v<+if(u<v!!0-1)("by"<+(v!!0-u))"")"")+" "+ $t\\i=:[u:v]<-inits k&t<-tails k|l(nub(zipWith(-)i v))<2&&l i<>2]

Essayez-le en ligne!

Οurous
la source
1

Gelée , 41 octets

ŒṖIE€Ạ$>Ẉ2eƊƲƇṪµ.ịṚj⁾to;IḢ⁾by;ẋ⁻1$ƲƊµḊ¡€K

Essayez-le en ligne!

Programme complet.

Erik le Outgolfer
la source
1

Python 2 , 170 166 octets

def f(a):
 j=len(a)
 while j>2:
	l,r=a[:j:j-1];s=(r-l)/~-j
	if a[:j]==range(l,r+1,s):return[`l`+'to%d'%r+'by%d'%s*(s>1)]+f(a[j:])
	j-=1
 return a and[`a[0]`]+f(a[1:])

Essayez-le en ligne!

TFeld
la source
Je ne sais pas si ce format de sortie est valide; les pistes devraient toutes être des cordes, non?
Erik the Outgolfer
@EriktheOutgolfer Fixed
TFeld
1

Python 2 , 138 136 octets

-2 octets grâce à Erik l'Outgolfer .

r=[];d=0
for n in input()+[0]:
 a=n-([n]+r)[-1]
 if(a-d)*d:
	if r[2:]:r=["%dto"%r[0]+`r[-1]`+"by%s"%d*(1%d)]
	print r.pop(0),
 r+=n,;d=a

Essayez-le en ligne!

ovs
la source
1

gvm (commit 2612106 ) bytecode, 108 octets

Attend la taille du tableau sur une ligne, puis les membres chacun sur une ligne.

Hexdump:

> hexdump -C findruns.bin
00000000  e1 0a 00 10 00 e1 0b 00  ff c8 92 00 f4 f7 10 00  |................|
00000010  01 b0 20 03 00 ff 0a 01  a2 01 c8 92 00 f4 01 c0  |.. .............|
00000020  03 00 ff 0a 02 d0 72 01  0a 03 c8 92 00 f4 05 b0  |......r.........|
00000030  20 a2 02 c0 02 02 6a 03  8b 00 ff f6 06 b0 20 a2  | .....j....... .|
00000040  02 f4 ce 0a 02 c8 92 00  f6 07 6a 03 8b 00 ff f6  |..........j.....|
00000050  f2 b9 66 01 a2 02 00 01  8a 03 f6 05 b9 69 01 a2  |..f..........i..|
00000060  03 92 00 f4 ac c0 74 6f  00 62 79 00              |......to.by.|
0000006c

Essais:

> echo -e "7\n5\n6\n8\n11\n15\n16\n17\n" | ./gvm findruns.bin
5 6 8 11 15to17
> echo -e "20\n1\n2\n3\n4\n5\n6\n7\n9\n11\n13\n15\n30\n45\n50\n60\n70\n80\n90\n91\n93\n" | ./gvm findruns.bin
1to7 9to15by2 30 45 50to90by10 91 93

Assemblé manuellement à partir de ceci:

0100  e1        rud                     ; read length of array
0101  0a 00     sta     $00             ; -> to $00
0103  10 00     ldx     #$00            ; loop counter
                  readloop:
0105  e1        rud                     ; read unsigned number
0106  0b 00 ff  sta     $ff00,x         ; store in array at ff00
0109  c8        inx                     ; next index
010a  92 00     cpx     $00             ; length reached?
010c  f4 f7     bne     readloop        ; no -> read next number
010e  10 00     ldx     #$00            ; loop counter
0110  01                                ; 'lda $20b0', to skip next instruction
                  runloop:
0111  b0 20     wch     #' '            ; write space character
0113  03 00 ff  lda     $ff00,x         ; load next number from array
0116  0a 01     sta     $01             ; -> to $01
0118  a2 01     wud     $01             ; and output
011a  c8        inx                     ; next index
011b  92 00     cpx     $00             ; length reached?
011d  f4 01     bne     compare         ; if not calculate difference
011f  c0        hlt                     ; done
                  compare:
0120  03 00 ff  lda     $ff00,x         ; load next number from array
0123  0a 02     sta     $02             ; -> to $01
0125  d0        sec                     ; calculate ...
0126  72 01     sbc     $01             ; ... difference ...
0128  0a 03     sta     $03             ; ... to $03
012a  c8        inx                     ; next index
012b  92 00     cpx     $00             ; length reached?
012d  f4 05     bne     checkrun        ; if not check whether we have a run
012f  b0 20     wch     #' '            ; output space
0131  a2 02     wud     $02             ; output number
0133  c0        hlt                     ; done
                  checkrun:
0134  02 02     lda     $02             ; calculate next ...
0136  6a 03     adc     $03             ; ... expected number in run
0138  8b 00 ff  cmp     $ff00,x         ; compare with real next number
013b  f6 06     beq     haverun         ; ok -> found a run
013d  b0 20     wch     #' '            ; otherwise output space ...
013f  a2 02     wud     $02             ; ... and number
0141  f4 ce     bne     runloop         ; and repeat searching for runs
                  haverun:
0143  0a 02     sta     $02             ; store number to $02
0145  c8        inx                     ; next index
0146  92 00     cpx     $00             ; length reached?
0148  f6 07     beq     outputrun       ; yes -> output this run
014a  6a 03     adc     $03             ; calculate next expected number
014c  8b 00 ff  cmp     $ff00,x         ; compare with real next number
014f  f6 f2     beq     haverun         ; ok -> continue parsing run
                  outputrun:
0151  b9 66 01  wtx     str_to          ; write "to"
0154  a2 02     wud     $02             ; write end number of run
0156  00 01     lda     #$01            ; compare #1 with ...
0158  8a 03     cmp     $03             ; ... step size
015a  f6 05     beq     skip_by         ; equal, then skip output of "by"
015c  b9 69 01  wtx     str_by          ; output "by"
015f  a2 03     wud     $03             ; output step size
                  skip_by:
0161  92 00     cpx     $00             ; length of array reached?
0163  f4 ac     bne     runloop         ; no -> repeat searching for runs
0165  c0        hlt                     ; done
                  str_to:
0166  74 6f 00                          ; "to"
                  str_by:
0169  62 79 00                          ; "by"
016c
Felix Palmen
la source
1

05AB1E (hérité) , 49 50 octets

.œʒε¥Ë}P}Σ€g2KO>}¤εD©g≠i¬s¤„toý¬®¥0èDU≠i„byX««]˜ðý

Beaucoup trop longtemps, mais je suis déjà content que ça marche. Ce défi est beaucoup plus difficile qu'il n'y paraît. Peut sans aucun doute être joué plus loin.
Σ€g2KO>}¤est un portage de la réponse Jelly 2,0ySƲÞṪ de @JonathanAllan (merci!).

Essayez-le en ligne. (REMARQUE: Délai d'expiration pour les grands cas de test.)

+1 octet comme correction de bogue car 0 est toujours placé à la fin du tri lors du tri.

Explication:

                       # Get all partions of the (implicit) input-list
                         #  i.e. [1,2,3,11,18,20,22,24,32,33,34]
                         #   → [[[1],[2],[3],[11],[18],[20],[22],[24],[32],[33],[34]],
                         #      [[1],[2],[3],[11],[18],[20],[22],[24],[32],[33,34]],
                         #      [[1],[2],[3],[11],[18],[20],[22],[24],[32,33],[34]],
                         #      ...]
  ʒ     }                # Filter this list by:
   ε  }                  #  Map the current sub-list by:
    ¥Ë                   #   Take the deltas, and check if all are equal
                         #    i.e. [1,2,3] → [1,1] → 1
                         #    i.e. [1,2,3,11] → [1,1,8] → 0
       P                 #  Check if all sub-list have equal deltas
  Σ      }               # Now that we've filtered the list, sort it by:
   g                    #  Take the length of each sub-list
                         #   i.e. [[1,2,3],[11,18],[20,22,24],[32,33],[34]]
                         #    → [3,2,3,2,1]
                         #   i.e. [[1,2,3],[11],[18,20,22,24],[32,33,34]]
                         #    → [3,1,4,3]
     2K                  #  Remove all 2s
                         #   i.e. [3,2,3,2,1] → ['3','3','1']
       O                 #  And take the sum
                         #   i.e. ['3','3','1'] → 7
                         #   i.e. [3,1,4,3] → 11
        >                #  And increase the sum by 1 (0 is always trailing when sorting)
          ¤              # And then take the last item of this sorted list
                         #  i.e. for input [1,2,3,11,18,20,22,24,32,33,34]
                         #   → [[1,2,3],[11],[18,20,22,24],[32,33,34]]
  ε                      # Now map each of the sub-lists to:
   D©                    #  Save the current sub-list in the register
     gi                 #  If its length is not 1:
                         #    i.e. [11] → 1 → 0 (falsey)
                         #    i.e. [18,20,22,24] → 4 → 1 (truthy)
        ¬s¤              #   Take the head and tail of the sub-list
                         #    i.e. [18,20,22,24] → 18 and 24
           toý          #   And join them with "to"
                         #    i.e. 18 and 24 → ['18to24', '18to20to22to24']
               ¬         #   (head to remove some access waste we no longer need)
                         #    i.e. ['18to24', '18to20to22to24'] → '18to24'
        ®                #   Get the sub-list from the register again
         ¥               #   Take its deltas
                         #    i.e. [18,20,22,24] → [2,2,2]
          0è             #   Get the first item (should all be the same delta)
                         #    i.e. [2,2,2] → 2
            DU           #   Save it in variable `X`
              i         #   If the delta is not 1:
                         #     i.e. 2 → 1 (truthy)
                byX«    #    Merge "by" with `X`
                         #     i.e. 2 → 'by2'
                     «   #    And merge it with the earlier "#to#"
                         #     i.e. '18to24' and 'by2' → '18to24by2'
                      ]  # Close the mapping and both if-statements
˜                        # Flatten the list
                         #  i.e. ['1to3',[11],'18to24by2','32to34']
                         #   → ['1to3',11,'18to24by2','32to34']
 ðý                      # And join by spaces (which we implicitly output as result)
                         #  i.e. ['1to3',11,'18to24by2','32to34']
                         #   → '1to3 11 18to24by2 32to34'
Kevin Cruijssen
la source
0

Perl 5 , 154 octets

{my(@r,$r);@r&&(@$r<2||$$r[1]-$$r[0]==$_-$$r[-1])?push@$r,$_:push@r,$r=[$_]for@_;join" ",map@$_<3?@$_:("$$_[0]to$$_[-1]by".($$_[1]-$$_[0]))=~s/by1$//r,@r}

Idem avec les espaces, les nouvelles lignes, les #comments et sub by:

sub by {
  my(@r,$r);
  @r &&                               # if at least one run candidate exists and...
   ( @$r<2                            # ...just one elem so far
     || $$r[1]-$$r[0] == $_-$$r[-1] ) # ...or diff is same
    ? push @$r, $_                    # then add elem to curr. run candidate
    : push @r, $r=[$_]                # else start new run cand. with curr elem
        for @_;
  join " ",
    map @$_<3                                         # is it a run?
    ? @$_                                             # no, just output the numbers
    : ("$$_[0]to$$_[-1]by".($$_[1]-$$_[0]))=~s/by1$//r, # yes, make run, delete by1
    @r                                                # loop run candidates
}

Essayez-le en ligne!

... pour réussir les tests de l'OP.

Kjetil S.
la source
0

Retina 0.8.2 , 77 octets

\d+
$*
(1+)(?= \1(1+))
$1:$2
1:(1+) (1+:\1 )+(1+)
1to$3by$1
:1+|by1\b

1+
$.&

Essayez-le en ligne! Le lien inclut des cas de test. Explication:

\d+
$*

Convertissez en unaire.

(1+)(?= \1(1+))
$1:$2

Calculez les différences consécutives.

1:(1+) (1+:\1 )+(1+)
1to$3by$1

Convertissez les exécutions en to...bysyntaxe.

:1+|by1\b

Supprimez les différences non converties et by1.

1+
$.&

Convertissez en décimal.

Neil
la source