En combien de morceaux pouvez-vous couper cette chaîne?

45

Considérons un morceau de ficelle (comme dans "corde", pas comme dans "un tas de caractères"), qui est plié dans les deux sens sur la ligne réelle. Nous pouvons décrire la forme de la chaîne avec une liste de points qu'elle traverse (dans l'ordre). Pour simplifier, supposons que tous ces points sont des entiers.

Prenons un exemple [-1, 3, 1, -2, 5, 2, 3, 4](notez que chaque entrée n’implique pas un pli):

entrez la description de l'image ici

La chaîne qui s'étend verticalement sert uniquement à la visualisation. Imaginez la chaîne tout aplatie sur la ligne réelle.

Maintenant, voici la question: quel est le plus grand nombre de pièces que cette ficelle peut être découpée en une seule coupe (qui devrait être verticale dans l'image ci-dessus). Dans ce cas, la réponse est 6 avec une coupure comprise entre 2et 3:

entrez la description de l'image ici

Pour éviter les ambiguïtés, la coupe doit être effectuée à une position non entière.

Le défi

Étant donné la liste des positions entières par lesquelles une chaîne est pliée, vous devez déterminer le plus grand nombre de pièces dans lesquelles la chaîne peut être coupée en une seule coupe à une position non entière.

Vous pouvez écrire un programme complet ou une fonction. Vous pouvez effectuer une entrée via STDIN, un argument de ligne de commande, une invite ou un paramètre de fonction. Vous pouvez écrire la sortie dans STDOUT, l'afficher dans une boîte de dialogue ou la renvoyer depuis la fonction.

Vous pouvez supposer que la liste est dans un format de liste ou de chaîne approprié.

La liste contiendra au moins 2 et pas plus de 100 entrées. Les entrées seront des entiers, compris entre -2 31 ≤ p i <2 31 . Vous pouvez supposer que deux entrées consécutives ne sont pas identiques.

Votre code doit traiter une telle entrée (y compris les cas de test ci-dessous) en moins de 10 secondes sur un ordinateur de bureau raisonnable.

Cas de test

Tous les cas de test sont simplement entrés, suivis par les résultats.

[0, 1]
2

[2147483647, -2147483648]
2

[0, 1, -1]
3

[1, 0, -1]
2

[-1, 3, 1, -2, 5, 2, 3, 4]
6

[-1122432493, -1297520062, 1893305528, 1165360246, -1888929223, 385040723, -80352673, 1372936505, 2115121074, -1856246962, 1501350808, -183583125, 2134014610, 720827868,  -1915801069, -829434432, 444418495, -207928085, -764106377, -180766255, 429579526,  -1887092002, -1139248992, -1967220622, -541417291, -1617463896, 517511661, -1781260846,  -804604982, 834431625, 1800360467, 603678316, 557395424, -763031007, -1336769888,  -1871888929, 1594598244, 1789292665, 962604079, -1185224024, 199953143, -1078097556, 1286821852, -1441858782, -1050367058, 956106641, -1792710927, -417329507, 1298074488,  -2081642949, -1142130252, 2069006433, -889029611, 2083629927, 1621142867, -1340561463,  676558478, 78265900, -1317128172, 1763225513, 1783160195, 483383997, -1548533202,  2122113423, -1197641704, 319428736, -116274800, -888049925, -798148170, 1768740405,  473572890, -1931167061, -298056529, 1602950715, -412370479, -2044658831, -1165885212,  -865307089, -969908936, 203868919, 278855174, -729662598, -1950547957, 679003141,  1423171080, 1870799802, 1978532600, 107162612, -1482878754, -1512232885, 1595639326,  1848766908, -321446009, -1491438272, 1619109855, 351277170, 1034981600, 421097157,  1072577364, -538901064]
53

[-2142140080, -2066313811, -2015945568, -2013211927, -1988504811, -1884073403, -1860777718,  -1852780618, -1829202121, -1754543670, -1589422902, -1557970039, -1507704627, -1410033893,  -1313864752, -1191655050, -1183729403, -1155076106, -1150685547, -1148162179, -1143013543,  -1012615847, -914543424, -898063429, -831941836, -808337369, -807593292, -775755312, -682786953, -679343381, -657346098, -616936747, -545017823, -522339238, -501194053,  -473081322, -376141541, -350526016, -344380659, -341195356, -303406389, -285611307, -282860017, -156809093, -127312384, -24161190, -420036, 50190256, 74000721, 84358785,  102958758, 124538981, 131053395, 280688418, 281444103, 303002802, 309255004, 360083648,  400920491, 429956579, 478710051, 500159683, 518335017, 559645553, 560041153, 638459051,  640161676, 643850364, 671996492, 733068514, 743285502, 1027514169, 1142193844, 1145750868,  1187862077, 1219366484, 1347996225, 1357239296, 1384342636, 1387532909, 1408330157,  1490584236, 1496234950, 1515355210, 1567464831, 1790076258, 1829519996, 1889752281,  1903484827, 1904323014, 1912488777, 1939200260, 2061174784, 2074677533, 2080731335, 2111876929, 2115658011, 2118089950, 2127342676, 2145430585]
2
Martin Ender
la source
Pouvons-nous supposer que vous voulez que la coupe se trouve à un endroit garantissant le maximum de pièces?
DavidC
2
Je dirais probablement "Déterminez le plus grand nombre de pièces" au lieu de "Déterminez le nombre de pièces".
DavidC
1
N'est-ce pas a reasonable desktop PCplutôt ambigu?
Globby
3
@globby C'est une phrase assez courante que nous utilisons lorsque le moteur d'exécution ne fait pas partie des critères gagnants (mais uniquement utilisé pour garantir que les solutions ne font pas appel à la force brutale). Cela signifie principalement que la limite n'est pas stricte à 100%. Si cela prend 15 secondes sur votre machine (et que vous n'utilisez pas de superordinateur), il y a des chances pour que quelqu'un ici ait un PC de bureau où il se termine en 10 secondes. Mais si cela prend moins de temps sur votre machine, il vous faudra alors envisager une approche différente. En outre, la limite est choisie de sorte qu'un algorithme efficace se termine facilement en moins de 10 secondes.
Martin Ender
2
@ZainR Nope .
Martin Ender

Réponses:

16

APL, 16 à 14 octets

1+⌈/+/2≠/∘.≤⍨⎕

Merci à @ ngn pour la sauvegarde de 2 octets.

Le est en fait un caractère de boîte, pas une erreur de police manquante. Vous pouvez essayer le programme sur tryapl.org , mais comme il n’est pas totalement pris en charge, vous devez le remplacer par la valeur en entrée:

    1+⌈/+/2≠/∘.≤⍨ ¯1 3 1 ¯2 5 2 3 4
6

Explication

Le programme s’explique mieux avec l’exemple d’entrée s = ¯1 3 1 ¯2 5 2 3 4, tiré de STDIN par . Premièrement, nous calculons le produit -outer de savec lui-même en utilisant ∘.≤⍨. Cela donne une matrice booléenne dont ila rangée indique quels éléments ssont inférieurs ou égaux à s[i]:

1 1 1 0 1 1 1 1
0 1 0 0 1 0 1 1
0 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1
0 0 0 0 1 0 0 0
0 1 0 0 1 1 1 1
0 1 0 0 1 0 1 1
0 0 0 0 1 0 0 1

Les occurrences de 0 1et 1 0sur la ligne imarquent des endroits où la chaîne passe sur le point s[i] + 0.5. Nous comparons sur ces lignes chaque ligne en utilisant 2≠/"réduire les 2 sous-listes par ":

0 0 1 1 0 0 0
1 1 0 1 1 1 0
1 0 1 1 0 0 0
0 0 0 0 0 0 0
0 0 0 1 1 0 0
1 1 0 1 0 0 0
1 1 0 1 1 1 0
0 0 0 1 1 0 1

Reste à prendre les sommes des lignes avec +/

2 5 3 0 2 3 5 3

et un plus le maximum de ceux-ci avec 1+⌈/:

6

Le résultat est automatiquement imprimé sur STDOUT dans la plupart des implémentations APL.

Zgarb
la source
@ n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Mon mauvais - résultat attendu est le nombre de pièces, pas l'emplacement pour le produire.
J ... le
Techniquement, c'est 16 caractères, 28 octets. Unicode vous le fera = P
KChaloux
1
@KChaloux que si vous comptez en utf8 octets, ce que vous ne feriez pas pour APL. Il y a une page de code à un octet qui contient tout le jeu de caractères utilisé par APL. Il est donc juste de l'utiliser pour le comptage.
Martin Ender
@ MartinBüttner Un lien source fiable serait formidable. Sinon, quelqu'un pourrait créer sa propre page Web arbitraire avec uniquement le jeu de caractères utilisé dans n'importe quelle langue pour réduire le nombre d'octets.
agweber
1
@GuillaumeLethuillier APL est en fait très facile à apprendre, au moins au point où vous pouvez écrire des réponses simples au golf comme celle-ci. Il existe quelques dizaines de fonctions avec des noms faciles à retenir, comme ×pour la multiplication, et des règles de syntaxe très simples. Google "mastering Dyalog APL" pour un bon guide.
Zgarb
16

Python, 88 75 73 octets

lambda x:max(sum((a+.5-m)*(a+.5-n)<0for m,n in zip(x,x[1:]))for a in x)+1

Juste un simple lambda


Juste pour montrer une autre approche:

Pyth, 28 à 27 octets

heSmsmq@S+k(d)1dC,QtQm+b.5Q

Celui-ci est à peu près équivalent à

lambda x:max(sum(a+.5==sorted(n+(a+.5,))[1]for n in zip(x,x[1:]))for a in x)+1

appliqué à la liste d'entrée de STDIN. Essayez-le sur l' interprète en ligne .

Sp3000
la source
Vous pouvez même enregistrer la fonction dans le même nombre de caractères:def f(x):max(sum((a+.5-m)*(a+.5-n)<0for m,n in zip(x,x[1:]))for a in x)+1
Christian Sonne
4
@ChristianSonne Votre fonction ne renvoie rien.
Jakube
Shoot, vous avez raison @Jakube
Christian Sonne
Je ne suis pas tout à fait sûr de savoir comment cela fonctionne, mais je pense que vous pouvez supprimer le +.5s pour sauvegarder certains caractères. J'ai réalisé qu'ils étaient inutiles dans le mien.
KSFT le
@KSFT Il divise la chaîne en intervalles, effectue une itération sur chaque a = point + .5et compte le nombre d'intervalles strictement contenus a. Sans le, .5vous aurez des problèmes avec des cas comme l' [1, 0, -1]exemple.
Sp3000
16

Pyth : 31 30 29 28 24 23 caractère (Python 68 caractères)

heSmsm&<hSkdgeSkdC,tQQQ

Essayez-le ici: Compilateur / Exécuteur Pyth

Il attend une liste d'entiers en entrée [-1, 3, 1, -2, 5, 2, 3, 4]

C'est une traduction directe de mon programme Python:

lambda s:1+max(sum(min(a)<i<=max(a)for a in zip(s,s[1:]))for i in s)

Ancienne solution: Pyth 28 car

Juste pour des raisons d'archivage.

heSmsm<*-dhk-dek0C,tQQm+b.5Q

Un code Python correspondant serait:

f=lambda x:1+max(sum((i-a)*(i-b)<0for a,b in zip(x,x[1:]))for i in [j+.5 for j in x])
Jakube
la source
Assez sûr que vous pourriez utiliser à la ,QtQplace de[QtQ)
FryAmTheEggman le
in'est pas la ligne d'intersection, i - 0.5est. Et donc 1 (en fait 1 - 0.5 = 0.5) est à l'intérieur (-1, 1). min(a)<i<=max(a)est équivalent à min(a) < i - 0.5 < max(a), ce qui est résolu en Pyth avec min(a) < i < max(a)+1(notez le hdans heSk).
Jakube
Je pense que vous êtes ici. Ou du moins, je ne trouve aucun cas où cette logique échoue ...
Optimiseur
Vous pouvez enregistrer un personnage en utilisant gce qui est >=, si vous remplacez <dheSkpar geSkd.
isaacg
2
Merci @isaacg. Mais pourquoi venez-vous toujours et détruisez-vous ma solution, alors que je suis vraiment heureux et confiant à ce sujet? ;-)
Jakube
10

CJam, 36 34 33 30 octets

q~[__(+]zW<f{f{1$+$#1=}1b}$W=)

Je crois qu'il existe un meilleur algorithme dans la nature. Néanmoins, cela fonctionne sous la limite requise pour tous les cas de test (même sur le compilateur en ligne).

L'entrée est comme

[-2142140080 -2066313811 -2015945568 -2013211927 -1988504811 -1884073403 -1860777718  -1852780618 -1829202121 -1754543670 -1589422902 -1557970039 -1507704627 -1410033893  -1313864752 -1191655050 -1183729403 -1155076106 -1150685547 -1148162179 -1143013543  -1012615847 -914543424 -898063429 -831941836 -808337369 -807593292 -775755312 -682786953 -679343381 -657346098 -616936747 -545017823 -522339238 -501194053  -473081322 -376141541 -350526016 -344380659 -341195356 -303406389 -285611307 -282860017 -156809093 -127312384 -24161190 -420036 50190256 74000721 84358785  102958758 124538981 131053395 280688418 281444103 303002802 309255004 360083648  400920491 429956579 478710051 500159683 518335017 559645553 560041153 638459051  640161676 643850364 671996492 733068514 743285502 1027514169 1142193844 1145750868  1187862077 1219366484 1347996225 1357239296 1384342636 1387532909 1408330157  1490584236 1496234950 1515355210 1567464831 1790076258 1829519996 1889752281  1903484827 1904323014 1912488777 1939200260 2061174784 2074677533 2080731335 2111876929 2115658011 2118089950 2127342676 2145430585]

La sortie (pour le cas ci-dessus) est

2

Comment ça marche

q~[__(+]zW<f{f{1$+$#1=}1b}$W=)
q~                                "Evaluate input string as array";
  [__                             "Put two copies of it in an array";
     (+]                          "Shift first element of second copy to its end";
        z                         "Zip together the two arrays. This creates";
                                  "pair of adjacent elements of the input.";
         W<                       "Remove the last pair";
           f{            }        "For each element of input array, take the zipped";
                                  "array and run the code block";
             f{       }           "For each element of the zipped array along with";
                                  "the current element from input array, run this block";
               1$+                "Copy the current number and add it to the pair";
                  $#              "Sort the pair and find index of current number";;
                    1=            "check if index == 1 for a < I <= b check";
                       1b         "Get how many pairs have this number inside of them";
                          $W=)    "Get the maximum parts the rope can be cut into";

Supposons maintenant que le tableau en entrée soit [-1 3 1 -2 5 2 3 4], les étapes de compression se présentent comme suit:

[-1 3 1 -2 5 2 3 4] [[-1 3 1 -2 5 2 3 4] [-1 3 1 -2 5 2 3 4]
[-1 3 1 -2 5 2 3 4] [[-1 3 1 -2 5 2 3 4] [3 1 -2 5 2 3 4 -1]
[-1 3 1 -2 5 2 3 4] [[-1 3] [3 1] [1 -2] [-2 5] [5 2] [2 3] [3 4]]]

Le deuxième tableau de la dernière ligne est constitué des plis de la chaîne.

Maintenant, nous parcourons [-1 3 1 -2 5 2 3 4]et calculons le nombre d'ensembles dans lesquels chacun se situe. Tirez le maximum de ce nombre, augmentez-le et nous avons notre réponse.

Essayez-le en ligne ici

Optimiseur
la source
10

Matlab (123) (97) (85)

Oui, enfin une utilisation de XNOR =), je suis sûr qu’il peut être joué beaucoup plus au golf.

Mais honnêtement, je suis un peu gêné que MatLab devienne la langue que je connais le mieux = /

Le temps d'exécution approximatif est O(n^2).

EDIT2:

a=input();v=2:nnz(a);disp(max(arrayfun(@(e)sum(~xor(a(v-1)<e,e<a(v))),sort(a)-.5))+1)

EDIT: Nouvelle version plus golfée (y compris des astuces de @DennisJaheruddin, merci!)

a=input();c=sort(a)-.5;n=0;v=2:nnz(c);for e=c;n=[n,sum(~xor(a(v-1)<e,e<a(v)))];end;disp(max(n)+1)

Ancienne version:

a=input();
c=conv(sort(a),[.5,.5],'valid');' %find all cutting positions by taking the mean of two successive points
k=numel(c);
for e=1:k %iterate over all 'cuts'
    n(e)=sum(~xor(a(1:k)<c(e),c(e)<a(2:k+1)));%find the number of threads the cut cuts
end
disp(max(n)+1) %output the max

@ MartinBüttner: J'aime beaucoup vos gentils petits défis juste avant d'aller au lit!

flawr
la source
10
Ma femme ne supporte pas XNORing
gnibbler
9
Il est temps pour @xnor de prendre des notes =)
mardi
Je pense que vous pouvez en économiser quelques uns pour trouver les points de découpage car les plis sont toujours entiers: c=sort(a)-.5Bien sûr, le premier point est alors hors de portée, mais il est sûrement plus facile de gérer cela. Dans le pire des cas, vous pouvez le faire c(1)=[];. - Vous pouvez aussi effacer la commande disp, en calculant que quelque chose l'écrira sur stdout .-- Enfin, dans ce cas, numelpeut être remplacé parnnz
Dennis Jaheruddin
Mais j'étais si fier de mon convapproche ... = D. J'oublie toujours le nnz, merci beaucoup!
flawr
Je pourrais trouver pas mal de façons de le rendre encore plus court! J'utilise dispdepuis une personne une fois que la critiquée méthode que vous proposez, vous obtenez également d' autres caractères (nom du var ou ans) par écrit stdout ...
flawr
9

Mathematica 134 133 104

Amusant à résoudre, malgré la taille du code. En outre le golf peut encore être atteint en remplaçant l'idée d' IntervalMemberQ[Interval[a,b],n]avec a<n<b.

n_~f~i_:=Count[IntervalMemberQ[#,n]&/@i,1>0];
g@l_:=Max[f[#,Interval/@Partition[l,2,1]]&/@(Union@l+.5)]+1

g[{-1, 3, 1, -2, 5, 2, 3, 4}]

6


Explication

list1Est la liste donnée de points list2est une liste abrégée qui supprime les nombres qui n'étaient pas au plis; ils ne sont pas pertinents. Ce n'est pas nécessaire, mais cela conduit à une solution plus claire et plus efficace.

list1 = {-1, 3, 1, -2, 5, 2, 3, 4};
list2 = {-1, 3, 1, -2, 5,2, 3, 4} //. {beg___, a_, b_, c_, end___} /; (a <= b <= c) 
 \[Or] (a >= b >= c) :> {beg, a, c, end}

Les intervalles en list1et list2sont indiqués dans les graphiques ci-dessous:

NumberLinePlot[Interval /@ Partition[list1, 2, 1]]
NumberLinePlot[intervalsArrangedVertically = Interval /@ Partition[list2, 2, 1]]

intervalles


Nous n'avons besoin de tester qu'une seule ligne dans chaque intervalle déterminé par les points de pli. Les lignes de test sont les lignes verticales en pointillés du tracé.

delimitersLeftToRight = Union[list2]
testLines = delimitersLeftToRight + .5
NumberLinePlot[
 intervalsArrangedVertically = Interval /@ Partition[list2, 2, 1], 
 GridLines -> {testLines, {}}, 
 GridLinesStyle -> Directive[Gray, Dashed]]

lignes de test


ftrouve le nombre de coupes ou de croisements de chaque ligne de test. La ligne en x = 2,5 fait 5 croisements. Cela laisse 5 + 1 morceaux de ficelle.

f[num_, ints_] := Count[IntervalMemberQ[#, num] & /@ ints, True]
f[#, intervalsArrangedVertically] & /@ testLines
Max[%] + 1

{2, 3, 5, 3, 2, 0}
6

DavidC
la source
8

Pyth, 21 octets

heSmsmq1xS+dSkdC,tQQQ

Essayez ici.

Donne une entrée sous forme de liste de style Python, par exemple [-1, 3, 1, -2, 5, 2, 3, 4]

Étroitement basé sur le programme de @ jakube, mais avec un algorithme central amélioré. Au lieu de faire une >vérification et une >=vérification, je fais un .index()sur les trois nombres combinés et je m'assure que l'indice est 1, ce qui signifie qu'il est supérieur au minimum et inférieur ou égal au maximum.

isaacg
la source
7

R, 86 83

Travaillait à travers cela et ensuite réalisé que j'avais essentiellement trouvé la même solution que Optimizer et d'autres que je soupçonne.

Quoi qu’il en soit ici c’est comme une fonction qui prend un vecteur

f=function(l)max(colSums(mapply(function(n)c(l[-1],NA,l)<=n&c(l,l[-1],NA)>=n,l),T))
MickyT
la source
OK, alors je suis partial et j'aime juste R. FWIW vous pourriez économiser 3 caractères en utilisant T"TRUE"
Carl Witthoft
@CarlWitthoft Merci pour le tuyau
MickyT
4

GolfScript (43 octets)

~[.(;]zip);{$}%:x{0=:y;x{{y>}%2,=},,}%$-1=)

En termes d'efficacité, il s'agit de O (n ^ 2) en supposant que les comparaisons prennent du temps O (1). Il sépare l'entrée en segments de ligne et compte pour chaque point de départ les segments de ligne semi-ouverts qui le traversent.

Démo en ligne

Peter Taylor
la source
4

Python - 161

Cela peut probablement être joué plus au golf. Gnibbler a beaucoup aidé au golf.

l=input()
d={}
for i in zip(l,l[1:]):d[sum(i)/2.]=0
for i,k in zip(l,l[1:]):
 for j in[m for m in d.keys()if min(i,k)<m<max(i,k)]:d[j]+=1
print max(d.values())+1
KSFT
la source
1
@ MartinBüttner / Jakube je l'ai corrigé. Cela fonctionne maintenant pour tous les cas de test en moins de dix secondes.
KSFT
Pourquoi y a-t-il deux votes négatifs à ce sujet?
KSFT
3

Ruby, 63 ans

Similaire aux solutions Python dans le concept.

->a{a.map{|x|a.each_cons(2).count{|v|v.min<x&&x<=v.max}}.max+1}

Ajoutez 2 caractères avant le code, par exemple f=si vous voulez une fonction nommée. Merci à MarkReed .

Vectorisé
la source
Le procédé nu semble être une réponse acceptable sans l'assigner à une variable. Enregistre deux caractères.
Mark Reed
3

C #, 73 65 octets

N=>1+N.Max(i=>N.Zip(N.Skip(1),(f,s)=>f<i+.5==i+.5<s).Count(b=>b))

En lisant les règles, j'ai pensé qu'un C # lambda devrait très bien se débrouiller.

Edit: just found Counta une surcharge utile pour le filtrage!

Vous pouvez tester cela en définissant le delegatetype approprié :

delegate int solver(int[] l);

Et alors

var l = new int[] { -1, 3, 1, -2, 5, 2, 3, 4 };
solver s = N=>1+N.Max(i=>N.Zip(N.Skip(1),(f,s)=>f<i+.5==i+.5<s).Count(b=>b));

Console.WriteLine(s(l));
Carl Walsh
la source
3

Matlab ( 63 43)

L'entrée est donnée sous la forme d'un vecteur ligne transmis à la fonction f. Donc, par exemple, f([-1, 3, 1, -2, 5, 2, 3, 4])retourne 6.

f=@(x)max(sum(diff(bsxfun(@le,2*x',x(1:end-1)+x(2:end)))~=0))+1

Version plus courte:

f=@(x)max(sum(diff(bsxfun(@lt,x',x))~=0))+1

Octave (31)

En Octave bsxfunpeut être supprimé grâce à la diffusion automatique:

f=@(x)max(sum(diff(x'<x)~=0))+1
Luis Mendo
la source
2

JavaScript (ES6) 80 82

Voir les commentaires - le nombre d'octets n'inclut pas l'affectation à F (cela reste à tester)

F=l=>Math.max(...l.map(v=>l.map(t=>(n+=t>u?v<t&v>=u:v>=t&v<u,u=t),n=1,u=l[0])&&n))

Test dans la console FireFox / FireBug

;[
 F([0, 1])
,F([2147483647, -2147483648])
,F([0, 1, -1])
,F([1, 0, -1])
,F([-1, 3, 1, -2, 5, 2, 3, 4])  
,F([-1122432493, -1297520062, 1893305528, 1165360246, -1888929223, 385040723, -80352673, 1372936505, 2115121074, -1856246962, 1501350808, -183583125, 2134014610, 720827868, -1915801069, -829434432, 444418495, -207928085, -764106377, -180766255, 429579526, -1887092002, -1139248992, -1967220622, -541417291, -1617463896, 517511661, -1781260846, -804604982, 834431625, 1800360467, 603678316, 557395424, -763031007, -1336769888, -1871888929, 1594598244, 1789292665, 962604079, -1185224024, 199953143, -1078097556, 1286821852, -1441858782, -1050367058, 956106641, -1792710927, -417329507, 1298074488, -2081642949, -1142130252, 2069006433, -889029611, 2083629927, 1621142867, -1340561463, 676558478, 78265900, -1317128172, 1763225513, 1783160195, 483383997, -1548533202, 2122113423, -1197641704, 319428736, -116274800, -888049925, -798148170, 1768740405,  473572890, -1931167061, -298056529, 1602950715, -412370479, -2044658831, -1165885212, -865307089, -969908936, 203868919, 278855174, -729662598, -1950547957, 679003141,  1423171080, 1870799802, 1978532600, 107162612, -1482878754, -1512232885, 1595639326, 1848766908, -321446009, -1491438272, 1619109855, 351277170, 1034981600, 421097157, 1072577364, -538901064])
,F([-2142140080, -2066313811, -2015945568, -2013211927, -1988504811, -1884073403, -1860777718, -1852780618, -1829202121, -1754543670, -1589422902, -1557970039, -1507704627, -1410033893,  -1313864752, -1191655050, -1183729403, -1155076106, -1150685547, -1148162179, -1143013543,  -1012615847, -914543424, -898063429, -831941836, -808337369, -807593292, -775755312, -682786953, -679343381, -657346098, -616936747, -545017823, -522339238, -501194053,  -473081322, -376141541, -350526016, -344380659, -341195356, -303406389, -285611307, -282860017, -156809093, -127312384, -24161190, -420036, 50190256, 74000721, 84358785,  102958758, 124538981, 131053395, 280688418, 281444103, 303002802, 309255004, 360083648,  400920491, 429956579, 478710051, 500159683, 518335017, 559645553, 560041153, 638459051,  640161676, 643850364, 671996492, 733068514, 743285502, 1027514169, 1142193844, 1145750868,  1187862077, 1219366484, 1347996225, 1357239296, 1384342636, 1387532909, 1408330157,  1490584236, 1496234950, 1515355210, 1567464831, 1790076258, 1829519996, 1889752281,  1903484827, 1904323014, 1912488777, 1939200260, 2061174784, 2074677533, 2080731335, 2111876929, 2115658011, 2118089950, 2127342676, 2145430585])
]

Sortie

[2, 2, 3, 2, 6, 53, 2]

edc65
la source
2
Selon les lambdasolutions Python , il n'est pas nécessaire d'attribuer la valeur de la fonction à une variable réelle, vous pouvez donc supprimer deux caractères.
Mark Reed
1
Oui. Sauf indication contraire dans le défi, les fonctions non nommées conviennent parfaitement.
Martin Ender
1

Gelée , 10 octets

>þ`^ƝS$€Ṁ‘

Essayez-le en ligne!

Comment ça marche

>þ`^ƝS$€Ṁ‘ - Main link. 1 argument        e.g.   [1, 0, -1]
>þ`        - Greater than outer product          [[0, 0, 0], [1, 0, 0], [1, 1, 0]]
      $€   - Over each sublist:           e.g.   [1, 1, 0]
    Ɲ      -   Over each overlapping pair e.g.   [1, 0]
   ^       -     Perform XOR                     1
     S     -   Take the sums                     [0, 1, 1]
        Ṁ  - Take the maximum                    1
         ‘ - Increment                           2
caird coinheringaahing
la source
1

05AB1E , 6 octets

ε@Ôg}à

Essayez-le en ligne!

Explication:

ε   }    # for each element of the input
 @       # is each element >= this one? (returns list of booleans)
  Ô      # connected uniquified
   g     # length
     à   # maximum
Grimmy
la source
0

Ajouter ++ , 27 octets

D,w,@@,VbUG€<ÑBxs
L~,A€wM1+

Essayez-le en ligne!

Merci à Zgarb pour sa réponse APL

L'élément clé de ce défi consiste à mettre en œuvre une commande de produit externe. Malheureusement, Add ++ n’a pas de fonction intégrée pour le faire, pas plus qu’il n’a aucun moyen de définir des fonctions qui prennent d’autres fonctions en tant qu’arguments. Cependant, nous pouvons toujours faire une fonction généralisée de produit extérieur. Comme la seule manière d'accéder à une fonction dans une autre fonction est de référencer une fonction existante, définie par l'utilisateur ou intégrée, nous devons créer un «intégré» qui référence une telle fonction.

Une fonction "table" généralisée ressemblerait à ceci:

D,func,@@,+

D,iter,@@*, VbUG €{func}
D,table,@@, $ bRbU @ €{iter} B]

Essayez-le en ligne!

funcest une fonction dyadique qui contient notre opérande. Vous pouvez voir de légères similitudes de cette structure dans la soumission originale, au début de la fonction w , mais ici, nous voulons avant tout une fonction de produit externe monadique - une fonction de produit externe qui prend le même argument des deux côtés.

La fonction de table générale tire parti de la façon dont le très rapide approche les fonctions dyadiques. Si la pile ressemble à

 [a b c d e]

Quand €{func}est rencontré, le pop e, lie cela comme l'argument de gauche à la dyade, et mappe cette fonction partielle sur a, b, c, d. Cependant, les cartes rapides sur toute la pile, plutôt que sur les listes. Nous devons donc aplatir d’abord les tableaux passés en arguments.

La fonction table fonctionne globalement comme ceci

D,func,@@,+

D,iter,		; Define our helper function iter
		;   This takes an array as its left argument
		;   And a single integer as its right argument
	@@	; Dyadic arguments - take two arguments and push to the stack
	*,	; After execution, return the entire stack, rather then just the top element
		;
		; Example arguments:	[5 6 7 8] 1
		; 
	VbUG	; Unpack the array;	[5 6 7 8 1]
		;
	€{func}	; Map func over the stack
		; As func is dyadic, this pops the right argument
		;   and binds that to a monadic func
		; This then maps the remaining elements, [5 6 7 8]
		;   over the monadic call of func, yielding [6 7 8 9]
		; Now, as the * flag was defined, we return the entire array
		;   rather than just the last element.
		; We'd achieve the same behaviour by removing the flag and appending B]

D,table,	; Define the main table function
		;   This takes two arrays as arguments
		;   Returns a single 2D array representing their outer product with func
	@@,	; Take the two arrays and push to the stack
		; 
		; Example arguments:	[[1 2 3 4] [5 6 7 8]]
		;
	$	; Swap;		STACK = [[5 6 7 8] [1 2 3 4]]
	bR	; Reverse last;	STACK = [[5 6 7 8] [4 3 2 1]]
	bU	; Unpack;	STACK = [[5 6 7 8] 4 3 2 1]
	@	; Reverse;	STACK = [1 2 3 4 [5 6 7 8]]
		; 
		; This allows us to place the stack so that each element of
		;   the first array is iterated over with the second array
		;
	€{iter}	; Map iter;	STACK = [[6 7 8 9] [7 8 9 10] [8 9 10 11] [9 10 11 12]]
		;
	B]	; Return the whole stack;

$table>?>?
O

Cependant, nous pouvons raccourcir beaucoup cela car nous avons besoin que notre table externe soit monadique et que nous n’ayons qu’à s’appliquer à l’argument passé. La Acommande pousse chaque argument individuellement dans la pile, évitant ainsi toute manipulation inutile de la pile. En bref, si notre argument est le tableau [a b c d], nous devons transformer la pile en

[a b c d [a b c d]]

La valeur supérieure est, bien sûr, le argument.You peut - être remarqué l'exemple général qui bUest le déballer commande -à- dire qu'il Splats le tableau supérieur à la pile. Donc, pour faire la configuration ci-dessus, nous pouvons utiliser le code

L,bUA

Essayez-le en ligne!

Cependant, cela peut être raccourci par un octet. Comme alias pour L,bU, nous pouvons utiliser le ~drapeau pour splatter au préalable les arguments dans la pile, transformant ainsi notre exemple de configuration en

L~,A

Essayez-le en ligne!

qui est le début de la deuxième ligne du programme. Maintenant que nous avons mis en place un produit externe monadique, il ne nous reste plus qu'à implémenter le reste de l'algorithme. Une fois que la récupération du résultat de la table avec <(inférieur), et compter le nombre de [0 1]et [1 0]paires dans chaque rangée. Enfin, nous prenons le maximum de ces comptes et l’augmentons.

La marche à suivre complète est la suivante:

D,w,		; Define a function w
		;   This takes an array and an integer as arguments
		;   First, it produces the outer product with less than
		;   Then reduce overlapping pairs by XOR
		;   Finally, sum the rows
	@@,	; Take two arguments
		;
		; Example arguments:		[[0 1 2 3] 0]
		;
	VbUG€<	; Map < over the array;	STACK = [0 1 1 1]
	ÑBx	; Equals [1 0];		STACK = [1 0 0]
	s	; Sum;			STACK = [1]

L		; Define a lambda function
		;   This takes one argument, an array
	~,	;   Splat the array to the stack before doing anything
		;
		; Example argument:		[0 1 2 3]
		;
	A€w	; Map with w;		STACK = [1 1 1 0]
	M	; Maximum;		STACK = [1]
	1+	; Increment;		STACK = [2]
Communauté
la source