HolyJS 2019: débriefing de SEMrush (Partie 1)

Lors de la conférence régulière pour les développeurs de HolyJS JavaScript qui a eu lieu du 24 au 25 mai à Saint-Pétersbourg, notre stand d'entreprise a offert à chacun de nouvelles tâches. Cette fois, il y en avait 3! Les tâches ont été données à tour de rôle et pour la solution de chacune des suivantes, un insigne (JS Brave> JS Adept> JS Master) a été récompensé, ce qui a été une bonne motivation pour ne pas s'arrêter. Au total, nous avons recueilli environ 900 réponses et sommes pressés de partager une analyse des solutions les plus populaires et uniques.

Les tests proposés attendent du courageux et de la compréhension des «fonctionnalités» de base du langage, et de la connaissance des nouvelles fonctionnalités d'ECMAScript 2019 (en fait, cette dernière n'est pas nécessaire). Il est important que ces tâches ne soient pas destinées à des entretiens, ne soient pas pratiques et soient conçues uniquement dans le but de s'amuser.

Tâche 1 ~ Expression du compte à rebours

Qu'est-ce qui rendra l'expression? Réorganisez tout caractère unique en

1. expression renvoyée 2
2. expression renvoyée 1

+(_ => [,,~1])().length 

De plus : est-il possible d'obtenir 0 par permutations?

Qu'est-ce qui rendra l'expression?

Il ne faut pas longtemps pour réfléchir ici: l'expression reviendra 3 . Nous avons une fonction anonyme qui renvoie simplement un tableau de trois éléments, dont les deux premiers sont vides. L'appel de fonction nous donne ce tableau, nous en prenons la longueur, et l'opérateur unaire plus ne résout rien.

L'expression renvoie 2

Une solution rapide semble réduire le nombre d'éléments dans le tableau renvoyé. Pour ce faire, jetez simplement une virgule:

 [,~1].length // 2 

Il est impossible de jeter un symbole comme ça: il doit être réorganisé à un autre endroit dans l'expression originale. Mais nous savons que la propriété length du tableau prend en compte les éléments vides répertoriés dans le littéral du tableau, sauf dans un cas :

Si un élément est élidé à la fin d'un tableau, cet élément ne contribue pas à la longueur du tableau.

Autrement dit, si un élément vide se trouve à la fin du tableau, il est ignoré:

 [,10,] // [empty, 10] 

Ainsi, l'expression corrigée ressemble à ceci:

 +(_ => [,~1,])().length // 2 

Existe-t-il une autre option pour se débarrasser de cette virgule? Ou a continué.

L'expression renvoie 1

Il n'est plus possible d'en obtenir un en réduisant la taille du tableau, car vous devrez effectuer au moins deux permutations. Je dois chercher une autre option.

La fonction elle-même fait allusion à la décision. Rappelons qu'une fonction en JavaScript est un objet qui a ses propres propriétés et méthodes. Et l'une des propriétés est également la longueur , qui détermine le nombre d'arguments attendus par la fonction. Dans notre cas, la fonction a un seul argument ( souligné ) - ce dont vous avez besoin!

Pour que la longueur soit extraite d'une fonction, et non d'un tableau, vous devez arrêter de l'appeler entre parenthèses. Il devient évident que l'un de ces supports est un candidat à une permutation. Et quelques options me viennent à l'esprit:

 +((_ => [,,~1])).length // 1 +(_ => ([,,~1])).length // 1 

Peut-être qu'il y a autre chose? Ou le niveau suivant.

L'expression renvoie 0

Dans la tâche supplémentaire, le nombre de permutations n'est pas limité. Mais nous pouvons essayer de le réaliser en faisant des gestes minimaux.

En développant une expérience précédente avec la longueur d'un objet fonction, vous pouvez rapidement trouver une solution:

 +(() => [,_,~1]).length // 0 

Il existe plusieurs dérivées ici, mais le fait est que nous avons réduit le nombre d'arguments de fonction à zéro. Pour ce faire, nous avions besoin de trois permutations : deux crochets et le caractère de soulignement , qui est devenu un élément du tableau.

D'accord, mais il est peut-être temps d'arrêter d'ignorer les opérateurs d'addition (+) et de bit NON (~) dans notre raisonnement? Il semble que l'arithmétique de ce problème puisse jouer entre nos mains. Afin de ne pas retourner au début, voici l'expression originale:

 +(_ => [,,~1])().length 

Pour commencer, nous calculons ~ 1 . Le NOT binaire de x renverra - (x + 1) . Autrement dit, ~ 1 = -2 . Et nous avons également un opérateur d'addition dans l'expression, qui, pour ainsi dire, indique que quelque part ailleurs, vous devez en trouver 2 de plus et tout fonctionnera.

Plus récemment, nous nous sommes souvenus du «non-effet» du dernier élément vide dans un tableau littéral sur sa taille, ce qui signifie que notre diable est quelque part ici:

 [,,].length // 2 

Et tout s'additionne très bien: nous obtenons l'élément ~ 1 du tableau, réduisant sa longueur à 2, et l'ajoutons comme premier opérande pour notre ajout au début de l'expression:

 ~1+(_ => [,,])().length // 0 

Ainsi, nous avons déjà atteint l'objectif en deux permutations !

Mais que faire si ce n'est pas la seule option? Un petit roulement de tambour ...

 +(_ => [,,~1.])(),length // 0 

Il nécessite également deux permutations: le point après l'unité (cela est possible, car le type numérique n'est que le nombre ) et la virgule avant la longueur . Cela semble absurde, mais "parfois" fonctionne. Pourquoi parfois?

Dans ce cas, l'expression via l' opérateur virgule est divisée en deux expressions et le résultat sera la valeur calculée de la seconde. Mais la deuxième expression n'est que longueur ! Le fait est que nous accédons ici à la valeur d'une variable dans un contexte global. Si le runtime est un navigateur, alors window.length . Et l'objet fenêtre a une propriété length qui renvoie le nombre de cadres sur la page. Si notre document est vide, alors la longueur retournera 0. Oui, une option avec une hypothèse ... nous allons donc nous attarder sur la précédente.

Et voici quelques options plus intéressantes découvertes (déjà pour un nombre différent de permutations):

 (_ => [,,].length+~1)() // 0 +(~([,,].len_gth) >= 1) // 0 ~(_ => 1)()+[,,].length // 0 ~(_ => 1)().length,+[,] // 0 ~[,,]+(_ => 1()).length // 0 

Il n'y a aucun commentaire. Quelqu'un trouve-t-il quelque chose d'encore plus amusant?

La motivation

Bonne tâche à l'ancienne sur "réorganiser un ou deux matchs pour faire un carré". Le puzzle bien connu pour le développement de la logique et de la pensée créative se transforme en obscurantisme dans de telles variations JavaScript. Est-ce utile? Plus probablement non que oui. Nous avons abordé de nombreuses fonctionnalités du langage, certaines même assez conceptuelles, pour aller au fond des solutions. Cependant, les vrais projets ne concernent pas la longueur de la fonction et de l'expression aux stéroïdes. Cette tâche a été proposée lors de la conférence comme une sorte d'entraînement addictif pour se rappeler à quoi ressemble JavaScript.

Combinatoire Eval

Toutes les réponses possibles n'ont pas été envisagées, mais pour ne rien manquer, nous nous tournons vers le vrai JavaScript ! S'il est intéressant d'essayer de les trouver vous-même, alors il y avait suffisamment de conseils ci-dessus, et alors il vaut mieux ne pas lire plus loin.



Donc, nous avons une expression de 23 caractères, dans l'enregistrement de chaîne dont nous ferons des permutations. Au total, nous devons effectuer n * (n - 1) = 506 permutations dans l'enregistrement d'origine de l'expression afin d'obtenir toutes les variantes avec un symbole permuté (comme requis par les conditions du problème 1 et 2).

Nous définissons une fonction de combinaison qui prend une expression d'entrée sous forme de chaîne et un prédicat pour tester l'adéquation de la valeur obtenue en exécutant cette expression. La fonction va forcer toutes les options possibles et évaluer l'expression via eval , en enregistrant le résultat dans un objet: clé - la valeur reçue, valeur - une liste de mutations de notre expression pour cette valeur. Quelque chose comme ça s'est produit:

 const combine = (expr, cond) => { let res = {}; let indices = [...Array(expr.length).keys()]; indices.forEach(i => indices.forEach(j => { if (i !== j) { let perm = replace(expr, i, j); try { let val = eval(perm); if (cond(val)) { (res[val] = res[val] || []).push(perm); } } catch (e) { /* do nothing */ } } })); return res; } 

Lorsque la fonction de remplacement de la chaîne passée de l'expression renvoie une nouvelle chaîne avec le caractère réorganisé de la position i à la position j . Et maintenant, sans trop de crainte, nous allons faire:

 console.dir(combine('+(_ => [,,~1])().length', val => typeof val === 'number' && !isNaN(val))); 

En conséquence, nous avons obtenu des ensembles de solutions:

 { "1": [ "+(_ => [,,~1]()).length", "+((_ => [,,~1])).length", "+(_ =>( [,,~1])).length", "+(_ => ([,,~1])).length" ], "2": [ "+(_ => [,~1,])().length" ] "3": [/* ... */] "-4": [/* ... */] } 

Les solutions pour 3 et -4 ne nous intéressent pas, pour les deux nous avons trouvé la seule solution, et pour l'unité il y a un nouveau cas intéressant avec [,, ~ 1] () . Pourquoi pas TypeError: bla-bla n'est pas une fonction ? Et tout est simple: cette expression n'a pas d'erreur pour l'analyseur syntaxique, et en runtime elle ne s'exécute tout simplement pas, puisque la fonction n'est pas appelée.

Comme vous pouvez le voir, dans une permutation, il est impossible de résoudre le problème à zéro. Pouvons-nous essayer en deux? Résoudre le problème par une recherche aussi exhaustive, dans ce cas, nous aurons la complexité O (n ^ 4) de la longueur de la chaîne et «évaluer» tant de fois poursuivi et puni, mais la curiosité prévaut. Il n'est pas difficile d'affiner indépendamment la fonction de combinaison donnée ou d'écrire une meilleure énumération qui prend en compte les caractéristiques d'une expression particulière.

 console.dir(combine2('+(_ => [,,~1])().length', val => val === 0)); 

Au final, l'ensemble des solutions pour zéro serait:

 { "0": [ "+(_ => [,~.1])(),length", "+(_ => [,~1.])(),length", "~1+(_ => [,,])().length" ] } 

Il est curieux que dans le raisonnement, nous ayons réorganisé le point après l'unité, mais nous avons oublié que le point devant l'unité est également possible: enregistrement 0,1 avec zéro omis.

Si vous effectuez toutes les permutations possibles de deux caractères chacune, vous pouvez constater qu'il existe un grand nombre de réponses pour des valeurs comprises entre 3 et -4:

 { "3": 198, "2": 35, "1": 150, "0": 3, "-1": 129, "-2": 118, "-3": 15, "-4": 64 } 

Ainsi, le chemin de solution de l' expression du compte à rebours à deux permutations peut être plus long que le chemin proposé de 3 à 0 sur un.

C'était la première partie de l'analyse de nos tâches à HolyJS 2019, et bientôt la deuxième devrait apparaître, où nous examinerons les solutions des deuxième et troisième tests. Nous serons en contact!