Écrivez un programme qui accepte une chaîne de longueur impaire contenant uniquement les caractères .et :. À l'aide d'une pile initialement vide , générez un nombre à partir de cette chaîne comme suit:

Pour chaque caractère c de la chaîne (de gauche à droite) ...

• Si c est .et que la pile contient moins de 2 éléments, appuyez sur 1 sur la pile.
• Si c est .et que la pile a 2 éléments ou plus, sortez les deux premières valeurs de la pile et poussez leur somme sur la pile.
• Si c est :et que la pile contient moins de 2 éléments, appuyez sur 2 sur la pile.
• Si c est :et que la pile contient 2 éléments ou plus, sortez les deux valeurs supérieures de la pile et poussez leur produit sur la pile.

Le nombre résultant est la valeur en haut de la pile. Votre programme doit imprimer ce numéro sur stdout (avec un retour à la ligne facultatif).

(Une petite analyse montre qu'il ne reste qu'un seul nombre, sauf si la chaîne a une longueur égale, c'est pourquoi nous les ignorons. En fait, la pile n'a jamais plus de 2 éléments.)

Par exemple, le nombre de ::...:.:.est 9:

  2   1   2   2    /______ stack just after the character below is handled
2 2 4 4 5 5 7 7 9  \
: : . . . : . : .  <-- string, one character at a time

Pour vérifier la santé mentale, voici les numéros de toutes les chaînes de longueur 1, 3 et 5:

. 1
: 2
... 2
..: 1
.:. 3
.:: 2
:.. 3
:.: 2
::. 4
::: 4
..... 3
....: 2
...:. 4
...:: 4
..:.. 2
..:.: 1
..::. 3
..::: 2
.:... 4
.:..: 3
.:.:. 5
.:.:: 6
.::.. 3
.::.: 2
.:::. 4
.:::: 4
:.... 4
:...: 3
:..:. 5
:..:: 6
:.:.. 3
:.:.: 2
:.::. 4
:.::: 4
::... 5
::..: 4
::.:. 6
::.:: 8
:::.. 5
:::.: 4
::::. 6
::::: 8

Le programme le plus court en octets gagne. Tiebreaker est un post antérieur.

• Vous pouvez supposer que l'entrée est toujours valide, c'est-à-dire une chaîne contenant uniquement .et :dont la longueur est impaire.
• Au lieu d'écrire un programme, vous pouvez écrire une fonction qui prend une chaîne valide et imprime ou renvoie le nombre généré.

CJam, 27 24 23 22 octets

q{i]_,+~3<-"1+2* "=~}/

Assez simple. J'utilise la pile de CJam comme pile mentionnée dans la question;)

Algorithme

Voyons d'abord le code ASCII pour .et :.

'.i ':ied

[46 58]

Comme dans CJam, l'index s'enroule, permet de voir si nous pouvons utiliser ces valeurs directement pour obtenir l'opération souhaitée.

'.i4% ':i4%ed

[2 2]

Je ne peux donc pas simplement utiliser les codes ASCII dans une chaîne d'opération de 4 longueurs. Permet d'essayer d'autres valeurs

'.i 10% ':i 10%ed

[6 8]

qui sur une chaîne de 4 longueurs se résume à

[2 0]

Je peux utiliser cette opération mod 10 mais cela coûtera 2 octets. Essayons autre chose

'.i5% ':i5%ed

[1 3]

Nice !, maintenant nous soustrayons juste 1 pour la condition de taille de pile pour obtenir les index 0, 1, 2 and 3et utiliser un 5tableau de longueur ( "1+2* ") comme cas de commutateur. Le dernier espace est juste un remplissage pour le rendre de longueur 5. C'est juste 1 octet supplémentaire par rapport à l'opération de modding.

q{                  }/    e# parse each input character in this loop
  i]                      e# convert '. or ': into ASCII code and wrap everything
                          e# in stack in an array
    _,+                   e# Copy the stack array, take its length and add the length to
                          e# the stack array 
       ~3<                e# unwrap the stack array and check if stack size is less than 3
                          e# 3 because either . or : is also on stack
          -               e# subtract 0 or 1 based on above condition from ASCII code
           "1+2* "        e# string containing the operation to perform
                  =~      e# chose the correct operation and evaluate it

Essayez-le en ligne ici

1 octet économisé grâce à cosechy

> <> (Poisson) , 33 octets

ib%1-i:1+?\~n;
5a*)?*+40.\b%1-0@i

Assez simple avec de petites astuces / optimisations.

Explication:

• Info: i= point de code du prochain caractère d'entrée, -1si la fin de l'entrée est atteinte; a= 10; b= 11; )=>
• ipoint de code du premier caractère d'entrée,
• b%1- top_of_stack mod 11 - 1masques 48 ('.') , 56 (':')à1 , 2
• i:1+?\~n; si la fin de l'entrée est atteinte, imprimer le dernier résultat et terminer
• autrement:
• b%1- masque d'entrée 1 , 2
• 0@pousser 0sous les deux chiffres
• i5a*)lire la prochaine entrée et la masquer pour la 0 , 1comparer à50
• if 1( ':') multiplie les deux premiers éléments créant une pile [0 produit]
• ajoutez toujours les deux premiers éléments créant une pile soit [0 sum]ou[0+product=product]
• 40.sauter (boucle) en position (4,0), notre point 4,i:1+?\~n;

Haskell, 73 65 octets

Une solution simple, utilisant le fait que la pile n'a jamais plus de 2 éléments.

[x,y]#'.'=[x+y]
[x,y]#_=[x*y]
s#'.'=1:s
s#_=2:s
f=head.foldl(#)[]

C, 104 octets

k[2],n;f(char*c){for(n=0;*c;)k[n]=*c++-58?n>1?n=0,*k+k[1]:1:n>1?n=0,*k*k[1]:2,k[1]=n++?k[1]:0;return*k;}

Eh bien, c'est trop long.

Pyth, 25 24 octets

eu?]?.xGHsGtG+GhHmqd\:zY

Vous avez une idée en étudiant la solution de @ isaacg. Mais j'utilise une pile.

Démonstration en ligne ou suite de tests

Explication

La première chose que je fais est de convertir la chaîne d'entrée en 0 et 1. Un "."se convertit en un 0, un ":"en un 1.

mqd\:z   map each char d of input to (d == ":")

Ensuite, je réduis cette liste de nombres:

eu?]?.xGHsGtG+GhHmqd\:zY
 u                     Y   start with the empty stack G = []
                           for each H in (list of 0s and 1s), update G:
                              G = 
    ?.xGHsG                      product of G if H != 0 else sum of G
   ]                             wrapped in a list 
  ?        tG                 if G has more than 1 element else
             +GhH                G + (H + 1)
e                         take the top element of the stack

JavaScript (ES6), 65

Nous utilisons seulement 2 cellules de notre pile.

Commencez à mettre une valeur dans s [0].
Ensuite, à chaque position impaire (à partir de 0) dans la chaîne d'entrée, mettez une valeur dans s [1].
À chaque position paire, exécutez un calcul (additionnez ou multipliez) et stockez le résultat dans s [0].

Alors oubliez la pile et utilisez seulement 2 variables, a et b.

f=s=>[...s].map((c,i)=>(c=c>'.',i&1?b=1+c:i?c?a*=b:a+=b:a=1+c))|a

Un test rapide

for(i=0;i<128;i++)
{
  b=i.toString(2).replace(/./g,v=>'.:'[v]).slice(1)
  if(b.length&1) console.log(b,f(b))
} 

Sortie

"." 1
":" 2
"..." 2
"..:" 1
".:." 3
".::" 2
":.." 3
":.:" 2
"::." 4
":::" 4
"....." 3
"....:" 2
"...:." 4
"...::" 4
"..:.." 2
"..:.:" 1
"..::." 3
"..:::" 2
".:..." 4
".:..:" 3
".:.:." 5
".:.::" 6
".::.." 3
".::.:" 2
".:::." 4
".::::" 4
":...." 4
":...:" 3
":..:." 5
":..::" 6
":.:.." 3
":.:.:" 2
":.::." 4
":.:::" 4
"::..." 5
"::..:" 4
"::.:." 6
"::.::" 8
":::.." 5
":::.:" 4
"::::." 6
":::::" 8

Pyth, 27 octets

Jmhqd\:zu?*GhHteH+GhHctJ2hJ

Une pile? Qui a besoin d'une pile.

                       Implicit: z is the input string.
Jmhqd\:z               Transform the string into a list, 1 for . and 2 for :
                       Store it in J.
u            ctJ2hJ     Reduce over pairs of numbers in J, with the
                       first entry as initial value.
 ?    teH               Condition on whether the second number is 1 or 2.
  *GhH                  If 1, update running total to prior total times 1st num.
         +GhH           If 2, update running total to prior total plus 1nd num.

Manifestation.

Rétine , 105 75 73 octets

Mon premier programme Retina! (Merci à Martin Büttner pour avoir économisé 2 octets, sans parler d'avoir inventé la langue en premier lieu.)

Chaque ligne doit aller dans un fichier séparé; ou, vous pouvez les mettre tous dans un seul fichier et utiliser l' -sindicateur. La <empty>notation représente un fichier / ligne vide.

^(a+;)?\.
$1a;
^(a+;)?:
$1aa;
;(a+;)\.
$1
(a+);aa;:
$1$1;
)`;a;:
;
;
<empty>
a
1

Inspiré par la réponse de mbomb007 , mais j'adopte une approche quelque peu différente. Une différence majeure est que je construis la pile devant la chaîne pointillée (avec le haut de la pile orienté vers la droite). Cela facilite la conversion des symboles en nombres correspondants sur place. J'utilise également aau lieu de 1, en ne le remplaçant qu'à la fin, pour éviter d'analyser l'ambiguïté dans des séquences comme $1a. Si une réponse comme aaaaaaest acceptable comme nombre unaire, les deux dernières lignes / fichiers pourraient être éliminés pour économiser 4 octets.

Explication:

^(a+;)?\.
$1a;

Correspond s'il y a 0 ou 1 élément sur la pile ( (a+;)?) suivi d'un point ( \.); si c'est le cas, il remplace la période par a;(c.-à-d. pousse un 1).

^(a+;)?:(.*)
$1aa;$2

Correspond s'il y a 0 ou 1 élément sur la pile suivi de deux points. Si c'est le cas, il remplace les deux points par aa;(c'est-à-dire pousse un 2).

;(a+;)\.
$1

Correspond s'il y a deux éléments sur la pile suivis d'un point. Supprime le point et le point-virgule entre les éléments, les ajoutant ainsi.

(a+);aa;:
$1$1;

Correspond s'il y a deux éléments sur la pile, dont le haut est un 2, suivi de deux points. Supprime le deux-points et le 2 et répète deux fois l'autre nombre, le multipliant ainsi par 2.

)`;a;:
;

La regex correspond s'il y a deux éléments sur la pile, dont le haut est un 1, suivi de deux points. Supprime les deux points et le 1, laissant l'autre nombre inchangé (c'est-à-dire multiplié par 1).

)`indique la fin d'une boucle. Si des modifications ont été apportées à la chaîne, le contrôle revient en haut du programme et réexécute les substitutions. Si la chaîne a cessé de changer, nous avons remplacé tous les points et les deux-points, et tout ce qui reste est le nettoyage ...

;
<empty>

Supprime le point-virgule restant.

a
1

Transforme tous les a en 1. Encore une fois, si les nombres unaires sont autorisés à utiliser n'importe quel symbole, cette étape n'est pas nécessaire.

Rouille, 170 caractères

fn f(s:String)->i32{let(mut a,mut b)=(-1,-1);for c in s.chars(){if b!=-1{a=match c{'.'=>a+b,':'=>a*b,_=>0};b=-1}else{b=match c{'.'=>1,':'=>2,_=>0};if a==-1{a=b;b=-1}};}a}

Encore une preuve que Rust est absolument terrible au golf. Code complet non golfé:

#[test]
fn it_works() {
    assert_eq!(dotty_ungolfed("::...:.:.".to_string()), 9);
    assert_eq!(f("::...:.:.".to_string()), 9);
}

fn dotty_ungolfed(program: String) -> i32 {
    let (mut a, mut b) = (-1, -1);
    for ch in program.chars() {
        if b != -1 {
            a = match ch { '.' => a + b, ':' => a * b, _ => panic!() };
            b = -1;
        } else {
            b = match ch { '.' => 1, ':' => 2, _ => panic!() };
            if a == -1 { a = b; b = -1; }
        }
    }
    a
}

fn f(s:String)->i32{let(mut a,mut b)=(-1,-1);for c in s.chars(){if b!=-1{a=match c{'.'=>a+b,':'=>a*b,_=>0};b=-1}else{b=match c{'.'=>1,':'=>2,_=>0};if a==-1{a=b;b=-1}};}a}

Voici une astuce intéressante que j'ai utilisée dans celui-ci. Vous pouvez raser un caractère dans une instruction if / else en lui faisant retourner une valeur qui est immédiatement supprimée, ce qui signifie que vous n'avez besoin que d'un point-virgule au lieu de deux.

Par exemple,

if foo {
    a = 42;
} else {
    doSomething(b);
}

peut être changé en

if foo {
    a = 42
} else {
    doSomething(b)
};

qui sauve un personnage en rasant un point-virgule.

Haskell, 88 81 79 octets

(h:t)![p,q]|h=='.'=t![p+q]|1<2=t![p*q]
(h:t)!s|h=='.'=t!(1:s)|1<2=t!(2:s)
_!s=s

Il semble que quelqu'un m'a battu jusqu'à la marque sur une solution Haskell, non seulement cela, leur solution est plus courte que la mienne. C'est dommage, mais je ne vois aucune raison de ne pas publier ce que j'ai trouvé.

APL (50)

Je suis très désavantagé ici, car APL n'est pas un langage basé sur la pile. J'ai finalement pu abuser de la réduction pour raccourcir le programme.

{⊃{F←'.:'⍳⍺⋄2>⍴⍵:F,⍵⋄((⍎F⌷'+×')/2↑⍵),2↓⍵}/(⌽⍵),⊂⍬}

La fonction interne prend une «commande» à gauche et une pile à droite, et l'applique, renvoyant la pile. La fonction externe le réduit sur la chaîne, en commençant par une pile vide.

Explication:

• (⌽⍵),⊂⍬: la liste initiale à réduire. ⊂⍬est une liste vide encadrée, qui représente la pile, (⌽⍵)est l'inverse de l'entrée. (La réduction est appliquée de droite à gauche sur la liste, de sorte que la chaîne sera traitée de droite à gauche. Si vous inversez l'entrée au préalable, vous appliquez les caractères dans le bon ordre.)

• {... }: la fonction intérieure. Il prend la pile à droite, un caractère à gauche et retourne la pile modifiée.

  • F←'.:'⍳⍺: l'index du caractère dans la chaîne .:, ce sera 1 ou 2 selon la valeur.
  • 2>⍴⍵:F,⍵: Si 2 est plus grand que la taille de pile actuelle, ajoutez simplement la valeur actuelle à la pile.
  • ⋄: autrement,
    • 2↓⍵: retirer les deux premiers éléments de la pile
    • (... )/2↑⍵: réduisez une fonction donnée sur eux, et ajoutez-la à la pile.
    • ⍎F⌷'+×': la fonction est soit +(addition) soit ×(multiplication), sélectionnée par F.

• ⊃: enfin, renvoyez l'élément le plus haut de la pile

Rubis - 96 caractères

La pièce intéressante ici est eval.

Mis à part cela, je fais l'hypothèse qu'après le premier caractère, la pile ira toujours 2, math, 2, math, .... Cela me permet d'utiliser moins de code en saisissant deux caractères à la fois - je n'ai jamais à comprendre savoir si un caractère est mathématique ou numérique. C'est positionnel.

x,m=$<.getc>?.?2:1
(b,f=m.split //
b=b>?.?2:1
x=f ?eval("x#{f>?.??*:?+}b"):b)while m=gets(2)
p x

Non golfé:

bottom_of_stack = $<.getc > '.' ? 2 : 1 # if the first char is ., 1, else 2
two_dots = nil
while two_dots = gets(2) do # get the next 2 chars
  number_char, math_char = two_dots.split //
  number = number_char > '.' ? 2 : 1
  if math_char
    math = math_char > '.' ? '*' : '+'
    # so bottom_of_stack = bottom_of_stack + number ...
    # or bottom_of_stack = bottom_of_stack * number
    bottom_of_stack = eval("bottom_of_stack #{math} number")
  else
    # if there's no math_char, it means that we're done and 
    # number is the top of the stack
    # we're going to print bottom_of_stack, so let's just assign it here
    bottom_of_stack = number
  end
end
p bottom_of_stack  # always a number, so no need for `puts`

TI-BASIC, 78 73 70 69 66 octets

Input Str1
int(e^(1=inString(Str1,":
For(A,2,length(Str1),2
Ans+sum({Ans-2,1,1,0},inString("::..:",sub(Str1,A,2
End
Ans

TI-BASIC est bon pour les lignes simples, car les parenthèses fermantes sont facultatives; à l'inverse, c'est un langage médiocre où le stockage de plusieurs valeurs est nécessaire car le stockage dans une variable prend de deux à quatre octets d'espace. Par conséquent, l'objectif est d'écrire autant de choses que possible sur chaque ligne. TI-BASIC est également horrible (pour un langage à jetons) pour la manipulation de chaînes de toutes sortes; même la lecture d'une sous-chaîne est longue.

Les astuces comprennent:

• int(e^([boolean]au lieu de 1+(boolean; enregistre un octet
• Somme partielle d'une liste au lieu d'un découpage de liste (ce qui nécessiterait le stockage dans une liste): enregistre 3 octets

Aller, 129 115 112 octets

func m(s string){a,b:=0,0;for c,r:=range s{c=int(r/58);if b>0{a=a*b*c+(a+b)*(c^1);b=0}else{b,a=a,c+1}};print(a)}

(un peu) non golfé:

func m(s string){
    // Our "stack"
    a, b := 0, 0
    // abusing the index asignment for declaring c
    for c, r := range s {
        // Ascii : -> 58, we can now use bit fiddeling
        c = int(r / 58)
        if b > 0 {
            // if r is :, c will be 1 allowing a*b to pass through, c xor 1 will be 0
            // if r is ., c xor 1 will be 1 allowing a+b to pass through
            a = a*b*c + (a+b)*(c^1)
            b = 0
        } else {
            b, a = a, c+1 // Since we already know c is 0 or 1
        }
    }
    print(a)
}

Essayez-le en ligne ici: http://play.golang.org/p/B3GZonaG-y

Python 3, 74

x,*s=[1+(c>'.')for c in input()]
while s:a,b,*s=s;x=[x*a,x+a][-b]
print(x)

Transforme d'abord la liste d'entrée en une séquence de 1 et de 2, en prenant la première valeur comme valeur initiale x. Ensuite, décolle deux éléments à la fois de l'avant de s, en prenant le premier nombre et en ajoutant ou en multipliant par le nombre actuel selon que le second est 1 ou 2.

bien c'est une opération si facile, sophistiquée par l'op (intentionnellement)

c'est juste ...

expression entre parenthèses traduite en opération postfixée * / +

Code: C (80 octets)

int f(char*V){return*(V-1)?f(V-2)*(*V==58?*(V-1)/29:1)+(*V&4)/4**(V-1)/29:*V/29;}

• cette fonction doit être appelée à partir de la queue de chaîne comme ceci: f (V + 10) où V = ".: ..:.: .. ::"

contribution

longueur = 2n + 1 vecteur V de type char '.' ou ':'

Sortie

un entier k

Une fonction

• k = (V [1] op (V [3]) V [2]) op (V [5]) V [4] ....

• op (x): (x = '.') -> +, (x = ':') -> *

Simulation:

essayez-le ici

Rétine, 181 135 129 octets

Chaque ligne doit être dans un fichier séparé. <empty>représente un fichier vide. La sortie est en Unary.

^\..*
$&1;
^:.*
$&11;
^.
<empty>
(`^\..*
$&1
^:.*
$&11
^.(.*?1+;1+)
$1
^(\..*);(1+)
$1$2;
;1$
;
^(:.*?)(1+).*
$1$2$2;
)`^.(.*?1+;)
$1
;
<empty>

Quand ${0}1est utilisé, les accolades se séparent $0du 1, sinon ce serait $01le 1er groupe correspondant. J'ai essayé d'utiliser $001, mais cela ne semble pas fonctionner dans la saveur .NET de l'expression régulière.

Edit: Trouvé c'est $&la même chose que $0.

En pseudo-code, ce serait essentiellement une boucle do-while, comme indiqué ci-dessous. J'appuie sur le premier nombre, puis boucle: appuie sur le deuxième nombre, supprime l'opération (instruction), fais des maths, supprime l'op. Continuez à boucler. Notez que lorsqu'une opération est sautée, cela supprimera également l'espace une fois toutes les instructions terminées.

Commenté:

^\..*           # Push if .
$&1;
^:.*            # Push if :
$&11;
^.              # Pop op
<empty>


(`^\..*         # Loop, Push #
$&1
^:.*
$&11
^.(.*?1+;1+)    # Pop op
$1


^(\..*);(1+)    # Add if . (move ;)
$1$2;
;1$          # If mul by 1, remove
;
^(:.*?)(1+).*   # Mul if : (double)
$1$2$2;
)`^.(.*?1+;)    # Pop op, End Loop (clean up)
$1
;               # Remove semicolon
<empty>

Python 3, 122 octets

x=input()
l=[0,0]
for _ in x:
 t=len(l)-2<2
 l=[[[0,0,l[-2]*l[-1]],l+[2]][t],[[0,0,sum(l)],l+[1]][t]][_=='.']
print(l[-1])

Non golfé:

x = input()
l = []
for i in x:
    if i == '.':
        if len(l) < 2: 
            l+=[1]        #True, True = 1,1
        else:
            l=[sum(l)]    #True, True = 1,0
    else:
        if len(l)<2:
            l+=[2]        #False, True = 0,1
        else:
            l=[l[0]*l[1]] #False, False = 0,0
print (l[0])

En python, vous référencez l'index d'une liste comme ceci:

list[index]

Vous pouvez y mettre une valeur booléenne, Trueest 1et Falseest 0.

# t is True if the length is less than 2, else false.

l=[ 

  # |------- Runs if char is : -------|
  # |------- l<2 -------| |- l>=2 -|

    [ [ 0,0, l[-2]*l[-1] ], l+[2] ] [t],

                                      # |---- Runs if char is . ----| 
                                      # |--- l<2 ---|  |- l>=2 -|

                                        [ [0,0, sum(l)], l+[1] ] [t] ]
                                                                      [_=='.']

Essayez-le en ligne ici

Perl, 77 octets

@o=(0,'+','*');sub d{$_=shift;y/.:/12/;eval'('x s!\B(.)(.)!"$o[$2]$1)"!ge.$_}

étendu:

@o=(0, '+', '*');
sub d{
    $_=shift;
    y/.:/12/;
    eval '(' x s!\B(.)(.)!"$o[$2]$1)"!ge.$_
}

Le @otableau mappe les chiffres aux opérateurs. Ensuite, nous substituons des paires de chiffres avec l'opérateur approprié, réorganisé en infixe. L'expression régulière commence par \Bdonc nous ne correspondons pas au tout premier caractère. Le résultat de s///gnous indique le nombre de parens ouverts dont nous avons besoin au début. Ensuite, lorsque nous avons assemblé l'expression infixe complète, nous pouvons l'évaluer. (Supprimez evalsi vous souhaitez voir l'expression à la place).

Voici le faisceau de test que j'ai utilisé pour vérifier les résultats:

while(<>) {
    my ($a, $b) = m/(.*) (.*)/;
    print d($a), " $b\n";
}

L'entrée est la liste des expressions dotty et leurs valeurs (fournies dans la question) et la sortie est des paires de {réel, attendu}.