Evaluating Dotty Strings

Question

Write a program that takes in an odd length string containing only the characters . and :. With the aid of an initially empty stack, generate a number from this string as follows:

For every character c in the string (going from left to right)...

• If c is . and the stack has less than 2 elements, push 1 on the stack.
• If c is . and the stack has 2 or more elements, pop the two top values off the stack and push their sum onto the stack.
• If c is : and the stack has less than 2 elements, push 2 on the stack.
• If c is : and the stack has 2 or more elements, pop the two top values off the stack and push their product onto the stack.

The resulting number is the value at the top of the stack. Your program should print this number to stdout (with an optional trailing newline).

(A little analysis shows that there is only ever one number left unless the string has even length, which is why we are ignoring those. In fact, the stack never has more than 2 elements.)

For example, the number for ::...:.:. is 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

As a sanity check, here are the numbers for all strings of length 1, 3, and 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

The shortest program in bytes wins. Tiebreaker is earlier post.

• You may assume the input is always valid, i.e. a string containing only . and : whose length is odd.
• Instead of writing a program, you may write a function that takes in a valid string and prints or returns the generated number.

Answer 1

CJam, 27 24 23 22 bytes

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

Pretty straight forward. I use CJam's stack as the stack mentioned in the question ;)

Algorithm

First lets look at the ASCII code for . and :.

'.i ':ied

[46 58]

Since in CJam, index wraps around, lets see if we can use these values directly to get the desired operation ..

'.i4% ':i4%ed

[2 2]

So I cannot simply use the ASCII codes in a 4 length operation string. Lets try some other values

'.i 10% ':i 10%ed

[6 8]

which on a 4 length string boils down to

[2 0]

I can use this mod 10 operation but that will cost be 2 bytes. Lets try something else

'.i5% ':i5%ed

[1 3]

Nice!, now we just subtract 1 for the stack size condition to get the indexes 0, 1, 2 and 3 and use a 5 length array ("1+2* ") as a switch case. The last space is just a filler to make it of length 5. This is just 1 extra byte as compared to modding operation.

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

Try it online here

1 byte saved thanks to cosechy

Answer 2

><> (Fish), 33 bytes

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

Fairly straightforward with little tricks/optimizations.

Explanation:

• Info: i = codepoint of next input char, -1 if end of input reached ; a = 10; b = 11; ) = >
• icodepoint of first input char,
• b%1- top_of_stack mod 11 - 1 masks 48 ('.') , 56 (':') to 1 , 2
• i:1+?\~n; if end of input reached print the last result and terminate
• otherwise:
• b%1- mask input to 1 , 2
• 0@ push 0 under the two number
• i5a*) read next input and mask it to 0 , 1 comparing to 50
• if 1 (':') multiply top two elements creating stack [0 product]
• always add top two elements creating stack either [0 sum] or [0+product=product]
• 40. jump (loop) back to position (4,0), our point 4, i:1+?\~n;

Answer 3

Haskell, 73 65 bytes

A straightforward solution, using the fact that the stack never has more than 2 elements.

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

Answer 4

C, 104 bytes

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;}

Well, this is too long.

Answer 5

Pyth, 25 24 bytes

eu?]?.xGHsGtG+GhHmqd\:zY

Got an idea by studying @isaacg's solution. But I'm using a stack.

Online Demonstration or Test Suite

Explanation

The first thing I do is to convert the input string into 0s and 1s. A "." gets converted into a 0, a ":" into a 1.

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

Then I reduce this list of numbers:

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

Answer 6

JavaScript (ES6), 65

We only use 2 cells of our stack.

Start putting a value in s[0].
Then, at each odd position (counting from 0) in the input string, put a value in s[1].
At each even position, exec a calc (add or multiply) and store result in s[0].

So forget about the stack and use just 2 variables, a and b.

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

A quick test

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))
} 

Output

"." 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

Answer 7

Pyth, 27 bytes

Jmhqd\:zu?*GhHteH+GhHctJ2hJ

A stack? Who needs a stack.

                       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.

Demonstration.

Answer 8

Retina, 105 75 73 bytes

My first Retina program! (Thanks to Martin Büttner for saving 2 bytes, not to mention inventing the language in the first place.)

Each line should go in a separate file; or, you can put them all in one file and use the -s flag. The <empty> notation represents an empty file/line.

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

Inspired by mbomb007's answer, but I take a somewhat different approach. One major difference is that I build the stack in front of the dotty string (with the top of the stack facing right). This makes it easy to convert symbols to the corresponding numbers in-place. I also use a instead of 1, swapping it out only at the end, to avoid parsing ambiguity in sequences like $1a. If an answer like aaaaaa is acceptable as a unary number, the last two lines/files could be eliminated to save 4 bytes.

Explanation:

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

Matches if there are 0 or 1 items on the stack ((a+;)?) followed by a period (\.); if so, it replaces the period with a; (i.e. pushes a 1).

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

Matches if there are 0 or 1 items on the stack followed by a colon. If so, it replaces the colon with aa; (i.e. pushes a 2).

;(a+;)\.
$1

Matches if there are two items on the stack followed by a period. Deletes the period and the semicolon between the items, thereby adding them.

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

Matches if there are two items on the stack, the top of which is a 2, followed by a colon. Deletes the colon and the 2 and repeats the other number twice, thereby multiplying it by 2.

)`;a;:
;

The regex matches if there are two items on the stack, the top of which is a 1, followed by a colon. Deletes the colon and the 1, leaving the other number unchanged (i.e. multiplied by 1).

)` indicates the end of a loop. If any changes were made to the string, control returns to the top of the program and runs the substitutions again. If the string has stopped changing, we've replaced all the periods and colons, and all that's left is cleanup...

;
<empty>

Deletes the leftover semicolon.

a
1

Transforms all the a's into 1's. Again, if unary numbers are allowed to use any symbol, this step is unnecessary.

Answer 9

Rust, 170 characters

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}

More proof that Rust is absolutely terrible at golfing. Full ungolfed code:

#[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}

Here's an interesting trick I used in this one. You can shave off a character in an if/else statement by having them return a value that is immediately discarded, which means you only need one semicolon instead of two.

For example,

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

can be changed into

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

which saves a character by shaving off a semicolon.

Answer 10

Haskell, 88 81 79 Bytes

(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

It seems that someone beat me to the mark on a Haskell solution, not only that, their solution is shorter than mine. That's to bad but, I see no reason not to post what I came up with.

Answer 11

APL (50)

I'm at a great disadvantage here, because APL is not a stack-based language. I finally got to abuse reduction to shorten the program, though.

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

The inner function takes a 'command' on the left and a stack on the right, and applies it, returning the stack. The outer function reduces it over the string, starting with an empty stack.

Explanation:

• (⌽⍵),⊂⍬: the initial list to reduce over. ⊂⍬ is a boxed empty list, which represents the stack, (⌽⍵) is the reverse of the input. (Reduction is applied right-to-left over the list, so the string will be processed right-to-left. Reversing the input beforehand makes it apply the characters in the right order.)

• {...}: the inner function. It takes the stack on the right, a character on the left, and returns the modified stack.

  • F←'.:'⍳⍺: the index of the character in the string .:, this will be 1 or 2 depending on the value.
  • 2>⍴⍵:F,⍵: If 2 is larger than the current stack size, just append the current value to the stack.
  • ⋄: otherwise,
    • 2↓⍵: remove the top two items from the stack
    • (...)/2↑⍵: reduce a given function over them, and add it to the stack.
    • ⍎F⌷'+×': the function is either + (addition) or × (multiplication), selected by F.

• ⊃: finally, return the topmost item on the stack

Answer 12

Ruby - 96 chars

The sorta interesting piece here is eval.

Aside from that, I am making the assumption that after the first character, the stack will always go 2, math, 2, math, .... This lets me use less code by grabbing two chars at once - I never have to figure out whether a character is math or number. It's positional.

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

Ungolfed:

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`

Answer 13

TI-BASIC, 78 73 70 69 66 bytes

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 is good at one-liners, because closing parentheses are optional; conversely, it is a poor language where storing multiple values is required because storing to a variable takes two to four bytes of space. Therefore, the goal is to write as much on each line as possible. TI-BASIC is also awful (for a tokenized language) at string manipulation of any kind; even reading a substring is lengthy.

Tricks include:

• int(e^([boolean] instead of 1+(boolean; saves one byte
• Partial sum of a list instead of list slicing (which would require storing into a list): saves 3 bytes

Answer 14

Go, 129 115 112 bytes

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)}

(somewhat) ungolfed:

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)
}

Try it online here: http://play.golang.org/p/B3GZonaG-y

Answer 15

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)

First transforms the input list into a sequence of 1's and 2's, taking the first value as the initial value x. Then, takes off two elements at a time from the front of s, taking the first number and either adding or multiplying with the current number based on whether the second is 1 or 2.

Answer 16

well this is so easy operation , sophisticated by the op (intentionally)

it is just ...

parenthesed expression translated into postfixed */+ operation

Code: C ( 80 bytes)

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

• this function should be called from the string tail like this : f(V+10) where V=".:..:.:..::"

input

length=2n+1 vector V of type char '.' or ':'

Output

an integer k

Function

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

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

---

Simulation:

try it here

Answer 17

Retina, 181 135 129 bytes

Each line should be in a separate file. <empty> represents an empty file. The output is in Unary.

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

When ${0}1 is used, the braces separate $0 from the 1, otherwise it would be $01, the 1st matching group. I tried using $001, but this appears not to work in the .NET flavor of regex.

Edit: Found that $& is the same as $0.

In pseudo-code, this would essentially be a do-while loop, as seen below. I push the first number, then loop: push the second number, remove the operation (instruction), do math, remove the op. Continue looping. Note that when an operation is popped, this will also remove the space after all the instructions are done.

Commented:

^\..*           # 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>

Answer 18

Python 3, 122 bytes

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])

Ungolfed:

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])

In python, you reference the index of a list like this:

list[index]

You can put a boolean value into that, True is 1 and False is 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] ]
                                                                      [_=='.']

Try it online here

Answer 19

Perl, 77 bytes

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

expanded:

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

The @o array maps digits to operators. Then we substitute pairs of digits with the appropriate operator, reordered to infix. The regexp begins with \B so we don't match the very first character. The result of s///g tells us how many open parens we need at the beginning. Then, when we've assembled the full infix expression, we can evaluate it. (Remove eval if you would like to see the expression instead).

Here's the test harness I used to verify the results:

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

Input is the list of dotty expressions and their values (provided in the question) and output is pairs of {actual, expected}.