Introduction: logique combinatoire
La logique combinatoire (CL) est basée sur des choses appelées combinateurs , qui sont essentiellement des fonctions. Il existe deux combinateurs de base "intégrés" Set K, qui seront expliqués plus loin.
Associativité gauche
CL est associatif à gauche , ce qui signifie que les parenthèses (contenant des éléments) qui sont à l'extrême gauche de la paire d'anthères de parenthèses le contenant peuvent être supprimées, avec ses éléments libérés. Par exemple, quelque chose comme ceci:
((a b) c)
Peut être réduit à
(a b c)
Où se (a b)trouve à l'extrême gauche du support le plus grand ((a b) c), il peut donc être retiré.
Un exemple beaucoup plus grand d'association à gauche (les crochets sont des explications):
((a b) c ((d e) f (((g h) i) j)))
= (a b c ((d e) f (((g h) i) j))) [((a b) c...) = (a b c...)]
= (a b c (d e f (((g h) i) j))) [((d e) f...) = (d e f...)]
= (a b c (d e f ((g h i) j))) [((g h) i) = (g h i)]
= (a b c (d e f (g h i j))) [((g h i) j) = (g h i j)]
Les supports peuvent également être réduits lorsque plusieurs paires s'enroulent autour des mêmes objets. Exemples:
((((a)))) -> a
a ((((b)))) -> a b
a (((b c))) -> a (b c) [(b c) is still a group, and therefore need brackets.
Note that this doesn't reduce to `a b c`, because
`(b c)` is not on the left.]
Builtins
CL a deux combinateurs "intégrés", Set K, qui peuvent commuter des objets (combinateurs simples, ou un groupe de combinateurs / groupes enroulés autour de crochets) comme ceci:
K x y = x
S x y z = x z (y z)
Où x, yet zpeut remplacer n'importe quoi.
Un exemple de Set Ksont comme suit:
(S K K) x [x is a stand-in for anything]
= S K K x [left-associativity]
= K x (K x) [S combinator]
= x [K combinator]
Un autre exemple:
S a b c d
= a c (b c) d [combinators only work on the n objects to the right of it,
where n is the number of "arguments" n is defined to have -
S takes 3 arguments, so it only works on 3 terms]
Les exemples ci-dessus sont des instructions CL normales, dans lesquelles l'instruction ne peut pas être évaluée plus avant et atteint un résultat final en un temps limité. Il existe des instructions non normales (qui sont des instructions CL qui ne se terminent pas et continueront d'être évaluées pour toujours), mais elles ne relèvent pas de la portée du défi et n'auront pas besoin d'être couvertes.
Si vous voulez en savoir plus sur CL, lisez cette page Wikipedia .
Tâche:
Votre tâche consiste à créer des combinateurs supplémentaires, compte tenu du nombre d'arguments et de ce à quoi il correspond en entrée, ce qui est donné comme suit:
{amount_of_args} = {evaluated}
Où {amount_of_args}est un entier positif égal au nombre d'arguments, et se {evaluated}compose de:
- arguments jusqu'à la quantité d'arguments, avec
1le premier argument,2le deuxième, etc.- Vous êtes assuré que les nombres d'arguments supérieurs au nombre d'arguments (donc un
4quand{amount_of_args}est seulement3) n'apparaîtront pas{evaluated}.
- Vous êtes assuré que les nombres d'arguments supérieurs au nombre d'arguments (donc un
- supports
()
Voici donc des exemples d'entrées:
3 = 2 3 1
4 = 1 (2 (3 4))
La première entrée demande un combinateur (disons R) avec trois arguments ( R 1 2 3), qui évalue ensuite:
R 1 2 3 -> 2 3 1
La deuxième entrée le demande (avec un nom de combinateur A):
A 1 2 3 4 -> 1 (2 (3 4))
Compte tenu de l'entrée dans ce format, vous devez renvoyer une chaîne de S, Ket ()qui, lorsqu'elle est substituée par un nom de combinateur et exécutée avec des arguments, renvoie la même instruction évaluée que le {evaluated}bloc lorsque le bloc de commande est substitué en arrière pour ce nom de combinateur.
L'instruction de combinateur de sortie peut voir ses espaces supprimés et les crochets externes supprimés, de sorte que quelque chose comme (S K K (S S))peut être transformé en SKK(SS).
Si vous voulez tester les sorties de votre programme, @aditsu a fait un analyseur logique combinatoire (qui inclut S, K, Iet même d' autres comme Bet C) ici .
But:
Puisqu'il s'agit d'un métagolf , l'objectif de ce défi est d'atteindre le plus petit nombre d'octets possible en sortie, compte tenu de ces 50 cas de test . Veuillez mettre vos résultats pour les 50 cas de test dans la réponse, ou créer une boîte à pâte (ou quelque chose de similaire) et publier un lien vers cette boîte à pâte.
En cas d'égalité, la première solution l'emporte.
Règles:
- Votre réponse doit renvoyer une sortie CORRECT - donc étant donné une entrée, elle doit retourner la sortie correcte selon la définition de la tâche.
- Votre réponse doit sortir dans une heure sur un ordinateur portable moderne pour chaque cas de test.
- Tout codage en dur des solutions est interdit. Cependant, vous êtes autorisé à coder en dur jusqu'à 10 combinateurs.
- Votre programme doit renvoyer la même solution à chaque fois pour la même entrée.
- Votre programme doit renvoyer un résultat valide pour toute entrée donnée, pas seulement des cas de test.
la source
1, vous pouvez soustraire1de tout, puis envelopper la solution pour cette réponseK(). Exemple: Solution pour2 -> 1isK, donc solution pour3 -> 2isKK, solution pour4 -> 3isK(KK)etc.Réponses:
Haskell , score 5017
Ceci combine l'algorithme le plus stupide possible pour l'élimination de l'abstraction ((λ x . X ) = I; (λ x . Y ) = K y ; (λ x . M N ) = S (λ x . M ) (λ x . N ) ) avec un optimiseur de judas utilisé après chaque application. La règle d'optimisation la plus importante est S (K x ) (K y ) ↦ K ( xy ), ce qui empêche l'algorithme de toujours exploser de façon exponentielle.
L'ensemble de règles est configuré comme une liste de paires de chaînes, il est donc facile de jouer avec de nouvelles règles. En plus de la réutilisation de l'analyseur d'entrée à cet effet, S, K et I sont également acceptés dans les combinateurs d'entrée.
Les règles ne sont pas appliquées sans condition; au lieu de cela, les anciennes et les nouvelles versions sont conservées et les versions sous-optimales ne sont élaguées que lorsque leur longueur dépasse celle de la meilleure version de plus d'une constante (actuellement 3 octets).
Le score est légèrement amélioré en traitant I comme un combinateur fondamental jusqu'à ce que l'étage de sortie le réécrit dans SKK. De cette façon, KI = K (SKK) peut être raccourci de 4 octets à SK en sortie sans confondre le reste des optimisations.
Essayez-le en ligne!
Production
la source
S (K x) (K y) = K (x y))?ruleStrings. Sinon, la sortie serait exponentiellement plus longue: pour ce petit exemple, nous aurions obtenu S (S (KS) (S (S (KS) (S (KK) (KS)))) (S (S (KS) (S (KK) (KK))) (S (KK) (SKK))))) (S (S (KS) (S (S (KS) (S (KK) (KS)))) ( S (S (KS) (S (KK) (KK))) (SK)))) (S (KK) (SK))) au lieu de S (KS) K.Somme des longueurs de solution:
12945 85085872Code Haskell qui prend les lignes d'entrée de stdin et ne se soucie pas si le séparateur est
=ou->:Il implémente l'abstraction améliorée des crochets de la section 3.2 de John Tromp: Calcul binaire Lambda et logique combinatoire qui est liée à l'article de Wikipedia sur la logique combinatoire. Les cas spéciaux les plus utiles utilisent uniquement le
Scombinateur pour assouplir les sous-termes afin d'éviter l'imbrication profonde des variables. Le cas qui vérifie l'égalité de certains sous-termes n'est nécessaire pour aucun des cas de test. Bien qu'il n'y ait pas de cas particulier pour gérer leWcombinateur (voir la réponse de Peter), les règles fonctionnent ensemble pour trouver l'SS(SK)expression la plus courte . (J'ai d'abord fait une erreur en essayant d'optimiser les appels internes versabstract, puis cetteWoptimisation n'a pas eu lieu et le résultat global était de 16 octets de plus.)Et voici les résultats des cas de test:
la source
8486 utilisant S, K, I, W
Explication
L'algorithme standard (comme décrit par exemple dans le chapitre 18 de Pour Mock a Mockingbird ) utilise quatre cas, ce qui correspond aux combinateurs
S,K,I = SKK, et simple gauche-association. Je pense que c'est ce que la réponse de Christian met en œuvre. C'est suffisant, mais pas nécessairement optimal, et comme nous sommes autorisés à coder en dur jusqu'à 10 combinateurs, il reste 7 options.D'autres combinateurs combinatoires bien connus sont
qui, avec
K, constituent une base complète . En SK, ce sontet les
SKIrègles dérivent ces mêmes expressions pourBetC, mais pourWelles dériventS S (K (S K K)). J'ai donc choisi de mettreWen œuvre comme un cas particulier.Programme (CJam)
Suite de tests en ligne
Sorties générées:
la source