Évaluer une expression d'opérateurs ternaires

29

Considérons une grammaire sur l'alphabet { 0, 1, ?, :} défini par la règle de production

s → 010 ?s :s ┃ 1 ?s :s

Étant donné une chaîne générée à partir de s , analysez-la comme une expression où ?:est associative à droite (par exemple, a?B?X:Y:c?d:e?f:gsignifie a?(B?X:Y):(c?d:(e?f:g))) et évaluez-la avec la sémantique suivante:

eval(0) = 0
eval(1) = 1
eval(0?a:b) = eval(b)
eval(1?a:b) = eval(a)

Si le résultat est 0 , sortez une valeur fixe; si la sortie est 1 , émettez une valeur fixe différente. Spécifiez les valeurs de sortie que vous avez choisies (par exemple 0/ 1, ou False/ True) dans votre réponse.

Cas de test

0 -> 0
1 -> 1
0?0:1 -> 1
0?1:0 -> 0
1?0:1 -> 0
1?1:0 -> 1
0?1?0:1:1 -> 1
1?0?1:1:1 -> 1
1?0:1?0:1?1:1 -> 0
1?1?1:0?1?0:0:0:0 -> 1
1?0:1?0?1:1?1:0:1?1?1:1:1?0:1 -> 0
1?1?1:0?0?1:1:0?1:0:1?1?0?0:0:1?1:0:0?1?0:1:1?0:1 -> 1
0?0?1?0?0:1:0?0:0:0?0?1:1:1?0:1:0?0?0?1:0:0?1:1:1?1?0:1:1 -> 0

Règles

  • Vous ne pouvez pas utiliser de langage intégré qui interprète les chaînes comme du code dans certains langages de programmation et les exécute (comme JavaScript / Perl / Ruby / Python eval).
  • Cela dit, votre code ne fait avoir à analyser et évaluer la chaîne d'entrée. Vous pouvez adopter n'importe quelle approche pour obtenir des résultats équivalents et ne pas enfreindre la règle précédente.
  • Votre programme sera vérifié perl -le 'print eval<>'.
  • Le code le plus court (en octets) gagne.
Lynn
la source
Que diriez-vous d'utiliser des langages intégrés comme eval qui interprètent les chaînes comme du code $ my_language après avoir changé radicalement la chaîne?
Adám
Qu'en est-il des builtins qui interprètent les chaînes comme du code $ some_other_language ?
Mego
@ Adám Ce serait interdit, désolé.
Lynn
@Mego Hmm, il y a là une opportunité de tricherie triviale, j'ai donc étendu la règle pour couvrir tous ces éléments intégrés.
Lynn
1
A la lumière des cas de test de Martin, il serait peut-être plus simple de définir la grammaire S → T | T ? S : S, T → 0 | 1, en supprimant la nécessité de parler associativité?
Peter Taylor

Réponses:

17

Rétine , 23 octets

r-1=+`0\?.:|1\?(.):.
$1

Essayez-le en ligne! (La première ligne active une suite de tests séparés par un saut de ligne.)

Explication

C'est assez simple en fait. L'entrée est réduite au résultat en +évaluant à plusieurs reprises ( ) les ternaires qui ne contiennent que des littéraux. Pour nous assurer que cela se fait de manière associative à droite, nous recherchons les correspondances de droite à gauche ( r) et ne remplaçons que la dernière correspondance trouvée ( -1=).

Le regex lui-même correspond 0\?.:et le supprime (ne laissant que les éléments après :) ou le 1\?.:.remplace par la valeur après le ?.

Martin Ender
la source
Si l'expression régulière commence à droite, ne devriez-vous pas traiter la 1correspondance de st au lieu de la -1st?
Leaky Nun
@LeakyNun Malheureusement, je pense que j'inverse les correspondances avant d'appliquer la limite.
Martin Ender du
10

Haskell, 106101100 90 83 octets

Cela s'appuie fortement sur les capacités de correspondance de motifs de Haskell. Tout d'abord, nous inversons la chaîne de sorte que nous puissions simplement rechercher la première occurrence de b:a?x(qui se lirait normalement comme x?a:b) et la remplacer par sa valeur. Cela fournit automatiquement la bonne associativité . Ici, nous utilisons le x:xsmodèle. C'est ce que fait la fonction f. Ensuite, nous appliquons essentiellement fà sa sortie maintes et maintes fois, jusqu'à ce qu'il ne nous reste qu'un seul numéro (0 ou 1).

Merci @Lynn pour 12 octets!

f(b:':':a:'?':x:l)|x>'0'=a:l|1>0=b:l
f(x:l)=x:f l
f x=x
until((<2).length)f.reverse
flawr
la source
8

Brainfuck, 82 64 63 octets

+
[
  ,>>,>
  +++++++[<---<<-[------>>]<-]
  <<
  [
    ->[<++>[+]]
  ]
  +>[>>]
  <<<-
]
<.

La sortie est \xffpour 0et \x00pour 1. L'implémentation brainfuck doit permettre d'aller à gauche de la cellule de départ.

Cela utilise essentiellement la même approche que la réponse Python de xsot , mais la ramification est probablement plus difficile à suivre par rapport à ma soumission initiale de 82 octets:

-
[
  +
  [
    ->,,>+++++++[<--------->-]
    <[<++>[+]]
    <
  ]
  ,->,>+++++++[<[-------<]>>-->-]
  <[<]
  <
]
>>.

(Pour cette solution, la sortie est \xfepour 0et \xffpour 1, et une compatibilité plus large est obtenue lorsque l'entrée se termine par une nouvelle ligne.)

Si vous ne pouvez pas vous soucier d'analyser la solution de xsot, l'idée est la suivante: procédez de gauche à droite. Si vous voyez, 1?jetez-le avec avidité. Si vous voyez 0?alors jetez tout entre cela et le correspondant :. Lorsque ?n'apparaît pas comme deuxième caractère, arrêtez la boucle et imprimez le premier caractère de la chaîne restante.

Ainsi, la solution de 82 octets reflète en fait ce schéma de très près. La boucle intérieure gère 0?, tout comme la boucle intérieure de xsot. Un certain soin est pris pour entrer dans la boucle principale sans vérifier les caractères saisis; c'est-à-dire, nous voulons vérifier si le deuxième caractère est ?juste une fois à la fin de la boucle principale, et pas aussi au début avant d'entrer dans la boucle principale.

La solution de 63 octets combine essentiellement les boucles internes et externes en une seule, ce qui, je le soupçonnais, était possible compte tenu de la similitude entre ces boucles. La disposition de la mémoire dans la boucle principale peut être décrite comme suit:

[s] d c

[x]signifie cellule actuelle - le sdébut sous la forme d'une valeur fictive non nulle qui indique simplement que nous bouclons toujours et est immédiatement remplacé par un caractère d'entrée (soit 0ou 1). La dcellule détient la profondeur (négative) au cas où nous serions au milieu de a 0?, sinon 0. Le cva être ou ?ou :ou nouvelle ligne ou EOF.

Après la mise à jour set c, nous traitons le 0?cas en mettant à jour en dconséquence et en ajustant le pointeur, sinon nous utilisons la valeur actuelle de ccomme valeur de ddans la prochaine itération, ou nous arrêtons si nous avons terminé.

Mitch Schwartz
la source
7

Python 2, 76 74 73 72 octets

a=`id`
for c in input()[::-1]:a=(c+a,a[ord(c)*7%9]+a[4:])[a>'?']
print a

Avec entrée comme chaîne littérale à éviter raw_.

La sortie est 0ou 1suivie de <built-in function id>.

Mitch Schwartz
la source
1
Haha, je viens de lire ta réponse pour b lang et j'étais sur le point de poster une réponse presque identique! Voici une optimisation supplémentaire:3>>int(c)
xsot
Vous voulez expliquer comment cela fonctionne?
Ça a l'air
@WorldSEnder Je pense que c'est le type de solution qui peut être difficile à trouver, mais facile à comprendre une fois que vous le voyez. Il parcourt la chaîne en arrière et traite à plusieurs reprises le conditionnel le plus à droite, comme d'autres solveurs l'ont fait également.
Mitch Schwartz
Cette `id`astuce…! Bravo :)
Lynn
5

Python 2, 89 octets

s=input()
while'?'<=s[1:]:
 n=s<'1'
 while n:s=s[2:];n+=-(s[1]<'?')|1
 s=s[2:]
print s[0]

L'entrée est prise comme un littéral de chaîne.

xsot
la source
5

Grime , 34 31 octets

E=d|d\?E.E
e`\1|\1\?_.E|\0\?E._

Imprime 1pour les entrées véridiques et 0pour les fausses. Essayez-le en ligne! Le dernier cas de test manque malheureusement de mémoire sur TIO.

Explication

L'associativité droite signifie essentiellement que dans a?b:c, aest toujours soit 0ou 1, jamais une expression plus longue. Je vais simplement définir de manière récursive un modèle qui correspond à une expression véridique comme celle-ci, et vérifier l'entrée en fonction de celle-ci. Il n'est pas non plus nécessaire de vérifier que tout :est vraiment un :, si tous les ?s sont vérifiés: il y a un nombre égal de ?s et de :s dans l'entrée, et si certains ?sont incorrectement classés comme a :, le correspondant :ne correspondra pas et la correspondance de Grime le moteur fera marche arrière.

E=d|d\?E.E
E=                      Define nonterminal E (for "expression") as
  d|                     a digit, OR
    d                    a digit,
     \?                  a literal ?,
       E                 a match of E,
        .                any character (will match a :), and
         E               another match of E.
e`\1|\1\?_.E|\0\?E._
e`                      Match entire input against this pattern (truthy expression):
  \1|                    a literal 1, OR
     \1\?                a literal 1?,
         _               a recursive match of truthy expression,
          .              any character (will match a :), and
           E|            any expression, OR
             \0\?E._     the same, but with 0 in front, and _ and E swapped.
Zgarb
la source
5

Haskell, 79 71 70 62 60 56 octets

Edit: Merci à @Zgarb pour 3 octets et à @nimi pour 4 octets!

e(x:'?':r)|a:_:s<-e r=last$e s:[a:tail(e s)|x>'0']
e x=x

Il s'agit d'une approche récursive qui abuse quelque peu de la règle de sortie "une certaine valeur fixe" . Edit: Se débarrasser des tuples n'économise pas seulement 8 octets, il donne également une sortie plus agréable: "0"ou "1".

Version non golfée:

eval (x:'?':r1) = if x=='1' then (a, r3) else (b, r3)
    where (a,':':r2) = eval r1
          (b, r3)    = eval r2
eval (x:r) = (x,r)

Comment ça marche?
La evalfonction parcourt l'arbre implicite des expressions

eval 1?0?0:1:0?1:0 -> eval 1?          :
                             eval 0?0:1 eval 0?1:0

et renvoie un tuple du formulaire (result, rest).
Le premier motif (x:'?':r1)correspond xà '1'et r1à "0?0:1:0?1:0". L'application récursive evalà r1évalue la sous-expression 0?0:1et renvoie (0,":0?1:0"). Faire correspondre cela au modèle (a,':':r2)donne a=0et r2=0?1:0. Cette sous-formule est également évaluée récursivement de sorte que b='0'et r3="". Vérifiez si xest '1'ou '0'et le retour soit (a, r3)ou (b, r3).

Laikoni
la source
1
Belle approche! Fonctionnerait x>'0'à la place de x=='1'?
Zgarb
Merci, je n'y ai pas pensé en traitant des caractères.
Laikoni
1
Je pense que vous pouvez également remplacer ':'par _.
Zgarb
Oui, le code fonctionne même pour les délimiteurs arbitraires au lieu de simplement :. Merci encore!
Laikoni
1
Agréable! Vous pouvez remplacer le if .. then .. elsepar last$e s:[a:tail(e s)|x>'0'].
nimi
3

JavaScript (ES6), 53 octets

f=s=>s[1]?f(s.replace(/0\?.:|1\?(.):.(?!\?)/,"$1")):s

Renvoie 0ou 1pour une entrée valide; se bloque pour une entrée non valide. Explication: comme inverser une chaîne est gênant en JavaScript, ma première tentative de 71 octets a fonctionné en utilisant une impasse négative pour un ?qui autrement perturberait l'associativité:

f=s=>s[1]?f(s.replace(/(.)\?(.):(.)(?!\?)/,(_,a,b,c)=>+a?b:c)):s

Comme cela était un peu long, je me demandais si je pouvais améliorer les choses en incorporant la prise de décision dans l'expression rationnelle. Il s'est avéré que ce n'était pas un succès immédiat, car cela a également pris 71 octets:

f=s=>s[1]?f(s.replace(/0\?.:(.)(?!\?)|1\?(.):.(?!\?)/,"$1$2")):s

Ensuite, il m'est venu à l'esprit que 0?0:et 0?1:sont toujours sans opération, sans souci d'associativité. Cela m'a fait économiser près de 25%.

Neil
la source
Votre bloc de code en haut est manquant f=. Je n'ai pas vérifié si votre nombre d'octets en tient compte ou non.
Patrick Roberts
@PatrickRoberts Je le fais toujours, car je copie à partir du journal, qui ne montre que le résultat de l'affectation (ce qui est bien sûr suffisant pour les fonctions non récursives).
Neil
@Neil, vous pouvez copier à partir de l'entrée du journal au lieu de la sortie
ASCII uniquement
@MarsUltor L'entrée de journal comprend l'invite, que je dois ensuite me rappeler d'exclure. Il s'agit d'une étape supplémentaire maladroite pour les fonctions non récursives, c'est pourquoi je copie par défaut à partir de la sortie.
Neil
3

Perl, 32 + 1 ( -pindicateur) = 33 octets

Plein crédit à @Mitch Swartch , car sa solution était de 14 octets plus courte que la mienne!
Merci également à @Neil qui a proposé une solution 1 octet de plus que Mitch.

s/.*\K(0\?..|1\?(.)..)/\2/&&redo

Besoin d'un -pdrapeau, ainsi que -M5.010ou -Epour courir. Par exemple :

perl -pE 's/.*\K(0\?..|1\?(.)..)/\2/&&redo' <<< "0
0?0:1
0?1?0:1:1
1?0:1?0?1:1?1:0:1?1?1:1:1?0:1
0?0?1?0?0:1:0?0:0:0?0?1:1:1?0:1:0?0?0?1:0:0?1:1:1?1?0:1:1"

Explications : Il réduit essentiellement les blocs de a?b:c(à partir de la fin pour être sûr qu'aucun suivi ne ?suit) dans bou en cfonction de la justesse de a, encore et encore jusqu'à ce que la chaîne ne contienne que 1ou 0.

Dada
la source
Le -ne compte- t-il pas dans votre score? Hrm. Intéressant ... Bonne réponse!
MayorMonty
@MayorMonty Pour un 1-liner, vous pouvez l'invoquer sur la ligne de commande en perl -e '<code>'ajoutant ainsi un pseul coût de 1 octet perl -pe '<code>'.
Neil
@Neil Ahh, c'est logique
MayorMonty
En fait, vous n'avez pas à inverser la chaîne, vous pouvez simplement chercher à l'avance pour un ?, j'ai pu réduire cela à 34 octets de cette façon.
Neil
Voici un 32 + 1:s/.*\K(1\?(.)..|0\?..)/\2/&&redo
Mitch Schwartz
2

Python 3, 93 69 octets

def f(s):z=s.pop;r=z(0);return s and':'<z(0)and(f(s),f(s))[r<'1']or r

L'entrée est la chaîne sous forme de liste de caractères, la sortie est soit "0"ou"1"

>>>f(list("0?0:1"))
<<<"1"

Version non golfée:

def parse(s):
    predicate = s.pop(0)
    if s and s.pop(0) == '?':
        left, right = parse(s), parse(s)
        if predicate == '0':
            return right
        return left
    return predicate

Un autre essai, mais avec beaucoup plus d'octets:

i=input()[::-1]
a=[i[0]]
for o,z in zip(i[1::2],i[2::2]):a+=[z]if o<'?' else[[a.pop(),a.pop()][z>'0']]
print(a[0])
WorldSEnder
la source
Votre réponse peut être une fonction - vous pouvez supprimer la deuxième ligne.
Lynn
Ceci n'est clairement pas testé, car il ne passe pas les cas de test, et la version non golfée donne une erreur d'exécution. Votre idée de base est cependant bonne. Avec quelques ajustements, j'obtiens 68 en Python 2 et 69 en Python 3.
Mitch Schwartz
1
Eh bien, je pense qu'il est plus logique pour moi de vous donner la réponse que de la modifier dans la mienne (puisque je ne pensais pas à ce genre d'approche avant d'avoir vu votre réponse) ou de rester assis à attendre pendant que votre réponse est boguée. Voici le 68 que j'ai mentionné def f(s):x=s.pop(0);return[]<s<s.pop(0)>'>'and(f(s),f(s))[x<'1']or x, et pour Python 3 avec une petite distance d'édition par rapport au vôtre, il y en a def f(s):z=s.pop;r=z(0);return s and':'<z(0)and(f(s),f(s))[r<'1']or r.
Mitch Schwartz
Merci @MitchSchwartz, à peu près analyser de droite, au lieu de gauche, gotcha
WorldSEnder
1
Sinon, gauche au lieu de droite, ~~~
WorldSEnder
1

SED, 75 74 68 (40 + 1 pour -r) 41

:
s,(.*)1\?(.):.,\1\2,
s,(.*)0\?.:,\1,
t
Riley
la source
Vous pouvez probablement réduire cela en utilisant l'astuce de @ MitchSchwartz dans son commentaire , même si vous devrez peut-être utiliser (.*)et ajouter un terme de remplacement supplémentaire.
Neil
@Neil, vous avez peut-être raison, mais je ne sais pas comment le faire fonctionner.
Riley
Je l'ai écrit dans le chat, car le formatage dans un commentaire peut prêter à confusion: chat.stackexchange.com/transcript/message/31709640#31709640
Mitch Schwartz
@MitchSchwartz Heh, les étiquettes vierges fonctionnent? Mais je pense que vous vouliez dire \3au lieu de \2. Vous pouvez également joindre les lignes avec ;pour obtenir :;s/(.*)(1\?(.):.|0\?.:)/\1\3/;t.
Neil
@Neil que j'avais \3donc cela signifie que j'ai accidentellement copié une version précédente. Je connais les points-virgules. Mais beurk, pourquoi voudriez-vous utiliser des points-virgules.
Mitch Schwartz
0

Utilitaires Bash + GNU, 42

rev|sed -r ':
s/(.):.\?0|.:(.)\?1/\1\2/
t'

Idée similaire à la plupart des autres réponses d'appariement de motifs.

Ideone .

Traumatisme numérique
la source
Vous n'avez pas besoin de capturer le premier caractère du 0boîtier, ce qui vous fait économiser 5 octets.
Neil