Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Your task – should you choose to accept it – is to build a program that parses and evaluates a string (from left to right and of arbitrary length) of tokens that give directions – either left or right. Here are the four possible tokens and their meanings:

>  go right one single step
<  go left one single step
-> go right the total amount of single steps that you've gone right, plus one,
   before you previously encountered this token and reset this counter to zero
<- go left the total amount of single steps that you've gone left, plus one,
   before you previously encountered this token and reset this counter to zero

There's a catch though – the tokens of directions your program should be able to parse will be presented in this form:

<<->-><<->->>->>->

... in other words, they are concatenated, and it is your program's task to figure out the correct precedence of directions and amount of steps to take (by looking ahead). The order of precedence is as follows (from highest to lowest precedence):

  1. ->
  2. <-
  3. >
  4. <

If you encounter <- when no steps to the left had previously been made since either the start or since the last reset, take one single step to the left. Same rule applies to ->, but then for going to the right.

Your program should start at 0 and its result should be a signed integer representing the final end position.

You may expect the input to always be valid (so, nothing like <--->>--<, for instance).

Example input:

><->><-<-><-<>>->

Steps in this example:

 step | token | amount | end position
------+-------+--------+--------------
   1. |   >   |     +1 |           1  
   2. |   <   |     -1 |           0  
   3. |  ->   |     +2 |           2  
   4. |   >   |     +1 |           3  
   5. |   <-  |     -2 |           1  
   6. |   <   |     -1 |           0  
   7. |  ->   |     +2 |           2  
   8. |   <-  |     -2 |           0  
   9. |   <   |     -1 |          -1  
  10. |   >   |     +1 |           0  
  11. |   >   |     +1 |           1  
  12. |  ->   |     +3 |           4  

For clarification: the output of the program should only be the final end position as a signed integer. The table above is just there to illustrate the steps my example took. No need to output such a table, table row, or even just the steps' end positions. Only the final end position, as a signed integer, is required.

Shortest code, after one week, wins.

share|improve this question
4  
If I understand the precedence rules correctly, the only time you could invoke <- is if it is immediately followed by a < or a ->. There's no way in this language to represent the sequence <- then > - which would be go left the total amount of single steps that you've gone left, plus one, then go right one single step. Is this correct and by design? –  Adam Davis Feb 20 at 21:20
    
@AdamDavis You are right. That was a bit inattentive of me, unfortunately. –  fireeyedboy Feb 21 at 1:18
add comment

12 Answers

up vote 5 down vote accepted

GolfScript, 46 chars

'->'/')'*.'<-'-.')'/);+,\'>)'-.'<-'/);\'-'-+,-

This is one of the most linear GolfScript programs I've ever written — there's not a single loop, conditional or variable assignment in it. Everything is done using string manipulation:

  • First, I replace every occurrence of -> by ). Since the input is guaranteed to be valid, this ensures that any remaining occurrence of - must be a part of <-.

  • Next, I make two copies of the string. From the first copy, I remove the characters < and -, leaving only > and ). I then duplicate the result, remove all the )s and every > following the last ) from the second copy, concatenate them and count the characters. Thus, in effect, I'm counting:

    • +1 for each ),
    • +1 for each > after the last ), and
    • +2 for each > before the last ).
  • Next, I do the same for the other copy, except this time counting < and <- instead of > and ), and removing the -s before the final character count. Thus, I count:

    • +1 for each <-,
    • +1 for each < after the last <-, and
    • +2 for each < before the last <-.
  • Finally, I subtract the second count from the first one, and output the result.

share|improve this answer
add comment

Python 2.7 - 154 147 134 128 bytes

l=r=p=0
exec"exec raw_input('%s->','p+=r+1;r=0%s<-','p-=l+1;l=0%s>','r+=1;p+=1%s<','l+=1;p-=1;')"%((";').replace('",)*4)
print p

Serious changes have been made to the way this program works. I've removed the old explanation, which can still be found in this answer's edit history.

This one's gross.

It works pretty much the same way as other answers for this question, replacing the characters in the input with valid statements in that language and executing them. There's one major difference, though: replace is a long word. Fuck that.

@ProgrammerDan in chat came up with the idea of using a tuple with the string ;').replace(' in it 4 times, to use the pre-str.format() method of formatting text. Four instances of %s are in the string on the second line, each one taking its value from the associated element of the tuple at the end. Since they're all the same, each %s is replaced with ;').replace('. When you perform the operations, you get this string:

exec raw_input(';').replace('->','p+=r+1;r=0;').replace('<-','p-=l+1;l=0;').replace('>','r+=1;p+=1;').replace('<','l+=1;p-=1;')

This is now valid python code that can be executed with exec. That's right, baby: Nested execs let me use string operations on code that needs to perform string operations on code. Someone please kill me.

The rest of it is pretty straightforward: Each command is replaced with code that keeps track of three variables: The current position, the number of rights since the last ->, and the same for lefts and <-. The whole thing is run and the position is printed.

You'll notice that I do raw_input(';'), using ';' as a prompt, rather than raw_input() which has no prompt. This saves characters in an unintuitive way: If I did raw_input(), I'd have to have the tuple filled with ).replace(', and every instance of %s would have ';\'' before it except the first one. Having a prompt creates more redundancy so I can save more characters overall.

share|improve this answer
2  
"list.index() returns -1 when it fails to find the character".. erm no. It raises an IndexError. You may have confused it with str.find. In fact you could replace [list('><rl').index(c)] with ['><rl'.find(c)]. –  Bakuriu Feb 20 at 20:52
    
...Huh, I looked it up in the docs and could have sworn it said it returned -1. It was specifically the page for lists, so I have no idea what I read. Anyway, thanks for the help, I'll edit that into the answer. –  undergroundmonorail Feb 21 at 0:12
add comment

Perl, 134 131 ... 99 95 bytes

sub f{$p+=$d;$&=~/-/?($p+=$s,$s=0):($s+=$d)}$_=<>;$d=1;s/-?>/f/eg;$s=0;$d=-1;s/<-?/f/eg;print$p

Takes input as a single line on stdin, eg:

ski@anito:~$ perl -le 'sub f{$p+=$d;$&=~/-/?($p+=$s,$s=0):($s+=$d)}$_=<>;$d=1;s/-?>/f/eg;$s=0;$d=-1;s/<-?/f/eg;print$p'
><->><-<-><-<>>->
4

or:

ski@anito:~$ echo "><->><-<-><-<>>->" | perl -le 'sub f{$p+=$d;$&=~/-/?($p+=$s,$s=0):($s+=$d)}$_=<>;$d=1;s/-?>/f/eg;$s=0;$d=-1;s/<-?/f/eg;print$p'
4

I split the instructions into the "right" operators (">" and "->") and "left" operators ("<" and "<-"). The advantages of this are that it's easier to exploit the parallelism between left and right operators, and we don't have to do anything fancy to tokenize the string. Each "direction" is dealt with as a substitution operation where we adjust the running total by the number of steps taken in that direction, ignoring the reverse direction which is taken care of by the other substitution operation. Here's a less-golfed ancestor of this code as a sort of documentation:

sub f {
  $dir=shift;
  if($1 =~ /-/) {
    $pos+=$side+$dir;
    $side=0;
  } else {
    $pos+=$dir;
    $side+=$dir;
  }
}

$_=<>;

s/(-?>)/f(1)/eg;
$side=0;
s/(<-?)/f(-1)/eg;

print $pos

In a prior iteration of this code, the substitutions were all done in one pass. This had the advantage of keeping a direct mapping between $p/$pos and the position that would be returned at any given point in time, but took more bytes of code.

If you want to use() 5.10.0, you can s/print/say/ to shave another 2 characters off the count, but that's not really my style.

share|improve this answer
add comment

Ruby, 141 bytes

l=1;r=1;o=0
gets.gsub('->',?R).gsub('<-',?L).chars{|c|case c
when'<';o-=1;l+=1
when'>';o+=1;r+=1
when'L';o-=l;l=1
when'R';o+=r;r=1
end}
$><<o

Ungolfed:

parsed = gets.gsub('->', 'R')
             .gsub('<-', 'L')
countL = 1
countR = 1
result = 0
parsed.each_char do |c|
    case c
    when '<'
        result -= 1
        countL += 1
    when '>'
        result += 1
        countR += 1
    when 'L'
        result -= countL
        countL = 1
    when 'R'
        result += countR
        countR = 1
    end
end
puts result
share|improve this answer
    
A couple of quick wins: l=1;r=1 can be l=r=1 and $><<o can be p o. I think you could shave a lot by replacing that case statement with something less bulky, maybe something along the lines of eval %w(o-=1;l+=1 o+=1;r+=1 o-=l;l=1 o+=r;r=1)['<>LR'.index c] –  Chron Feb 25 at 3:33
    
In fact with the eval approach you can pull out some prefixes/suffixes to save even more. This is 98 chars: l=r=1;o=0;gets.gsub('->',??).scan(/<-|./){eval"o+=#{%w[-1;l+ -l;l 1;r+ r;r][$&[-1].ord%4]}=1"};p o, you could go down to 94 using ruby -p –  Chron Feb 25 at 4:01
add comment

Perl, 88 77 bytes

$_=<>;print s/->/F/g+2*s/>(?=.*F)//g+s/>//g-(s/<-/B/g+2*s/<(?=.*B)//g+s/<//g)

Input is expected via STDIN, for example:

echo '><->><-<-><-<>>->'|perl -e '$_=<>;print s/->/F/g+2*s/>(?=.*F)//g+s/>//g-(s/<-/B/g+2*s/<(?=.*B)//g+s/<//g)'
4

Update

There is no need to convert the string to a summation, because s// is already counting. :-)

First version

$_=<>;s/->/+1/g;s/>(?=.*1)/+2/g;s/>/+1/g;s/<-/-1/g;s/<(?=.*-)/-2/g;s/</-1/g;print eval

Input is expected via STDIN, example:

echo '><->><-<-><-<>>->'|perl -e '$_=<>;s/->/+1/g;s/>(?=.*1)/+2/g;s/>/+1/g;s/<-/-1/g;s/<(?=.*-)/-2/g;s/</-1/g;print eval'
4

Explanation:

The idea is to convert the direction string into a summation so that the result is output by a simple print eval.

> before any -> takes two steps, one at once and the other at the next ->. It does not matter, which of the -> while it follows at least one of them. The internal counter is reset after the next ->, thus > does not cause further steps, the maximum is two steps. Then -> adds one step for itself and so do any remaining > after the last ->.

The same holds for the backwards direction with negative instead of positive step counts.

E.g.: ><->><-<-><-<>>->

s/->/+1/: Start with forward direction, because -> has highest precedence.
E.g.: ><+1><-<+1<-<>>+1

s/>(?=.*1)/+2/g: The look-ahead pattern assures that only the > before any -> are converted.
E.g.: +2<+1+2<-<+1<-<+2+2+1

s/>/+1/g: Now the remaining > are covered.
E.g.: +2<+1+2<-<+1<-<+2+2+1

s/<-/-1/g: Analog the backwards direction.
E.g.: +2<+1+2-1<+1-1<+2+2+1

s/<(?=.*-)/-2/g: In the look-ahead pattern the full -1 of the former <- is not needed, because there are no - of the direction symbols left.
E.g.: +2-2+1+2-1-2+1-1<+2+2+1

s/</-1/g: The remaining < after the last <- are converted.
E.g.: +2-2+1+2-1-2+1-1-1+2+2+1

print eval: Calculate and output the result.
E.g.: 4

share|improve this answer
    
Good one. I was kicking around this concept last night but didn't have a chance to try implementing it until today. Good thing I checked the post and saw you already had =) –  skibrianski Feb 21 at 17:50
    
@skibrianski: Thanks for fixing the copy&paste error. –  Heiko Oberdiek Feb 21 at 18:17
add comment

D - 243

Golfed:

import std.regex,std.stdio;void main(string[]a){int s,c,v;auto t=a[1].matchAll("->|<-(?!>)|>|<".regex);foreach(m;t){auto r=m.hit;if(r=="->"){s+=c+1;c=0;}else if(r=="<-"){s-=v+1;v=0;}else if(r==">"){++s;++c;}else if(r=="<"){--s;++v;}}s.write;}}

Un-golfed:

import std.regex, std.stdio;

void main( string[] a )
{
    int s, c, v;
    auto t = a[1].matchAll( "->|<-(?!>)|>|<".regex );

    foreach( m; t )
    {
        auto r = m.hit;

        if( r == "->" )
        {
            s += c + 1;
            c = 0;
        }
        else if( r == "<-" )
        {
            s -= v + 1;
            v = 0;
        }
        else if( r == ">" )
        {
            ++s;
            ++c;
        }
        else if( r == "<" )
        {
            --s;
            ++v;
        }
    }

    s.write;
}
share|improve this answer
    
The required output was originally in the question. I've highlighted it now, and added further clarification. –  fireeyedboy Feb 20 at 17:44
    
Right, I've edited my answer to output the result now. –  Tony H. Feb 20 at 17:53
add comment

C, 148 141 140

140:

r,l,o;main(char *x,char **v){for(x=v[1];*x;x++)(*x^45)?(*x^60)?(r++,o++):(*(x+1)==45)?(x++,o-=l+2,l=0):(o--,l++):(o+=r+1,r=0,x++);return o;}

141:

r,l,o;main(char *x,char **v){for(x=v[1];*x;x++)(*x^45)?(*x^60)?(r++,o++):(*(x+1)==45)?(x++,o=o-l-2,l=0):(o--,l++):(o+=r+1,r=0,x++);return o;}

148:

r,l,o;main(char *x,char **v){for(x=v[1];*x;x++){if(*x^45){if(*x^60)r++,o++;else{o--,l++;if(*(x+1)==45)x++,o-=l,l=0;}}else o+=r+1,r=0,x++;}return o;}

With whitespace:

r,l,o;
main(char *x,char **v) 
{
    for(x=v[1];*x;x++)
    (*x^45) ?
        (*x^60) ?
            (r++,o++)
            :
            (*(x+1)==45) ?
                (x++,o-=l+2,l=0)
            :(o--,l++)
        :(o+=r+1,r=0,x++);
    return o;
}

Probably a lot more room to golf this. I mostly gave up on trying to manipulate 4 variables in ternaries that captured lvalues (it kept coming out longer and getting later), but not a bad first pass. Pretty straight-forward array pass. Takes input as a command-line argument, outputs via the return value.

You'll need the -std=c99 flag to compile it with gcc.

EDIT: Yep, it's late - missed some obvious stuff.

share|improve this answer
    
You can remove two spaces in the argument list of main: main(char*x,char**v). Then you have 138 instead of 140. –  Heiko Oberdiek Feb 21 at 13:08
    
There is a bug: >><- gives 0 instead of 1 or ><-> gives 0 instead of 2. –  Heiko Oberdiek Feb 21 at 13:36
    
You can save 4 bytes if your remove spaces between char and *, and replace (*(x+1)==45)?(x++,o-=l+2,l=0):(o--,l++) with (*++x==45)?(o-=l+2,l=0):(x--,o--,l++). –  Mathieu Rodic Apr 4 at 15:28
add comment

JavaScript, 136

z=0;l=r=1;c=["--z;++l;",/</g,"++z;++r;",/>/g,"z-=l;l=1;",/<-/g,"z+=r;r=1;",/->/g];for(a=8;a--;s=s.replace(c[a--],c[a]));eval(s);alert(z)

Unminified:

s="><->><-<-><-<>>->";
z=0;
l=r=1;
c=[
    "--z;++l;", /</g,
    "++z;++r;", />/g,
    "z-=l;l=1;", /<-/g,
    "z+=r;r=1;", /->/g
];
for(a=8;a--;s=s.replace(c[a--],c[a]));
eval(s);
alert(z) // Output (4)

How it works

Given a string input as s like so:

s="><->><-<-><-<>>->";

It uses a Regex to replace each command with a set of instructions which modify z (the end position), l (stored left movements) and r stored right movements. Each Regex is performed in order of precedence.

For the input above this converts s to:

"++z;++r;--z;++l;z+=r;r=1;++z;++r;z-=l;l=1;--z;++l;z+=r;r=1;z-=l;l=1;--z;++l;++z;++r;++z;++r;z+=r;r=1;"

Pretty, ain't it.

Finally we eval(s) to perform the instructions and alert z which contains the end position.

share|improve this answer
add comment

Javascript (116, 122, 130)

116:

for(l=r=p=i=0;c='<>-0'.indexOf(a.replace(/->/g,0)[i++])+1;p--)c-4?c-3?c-2?l++:(r++,p+=2):(p-=l-2,l=0):(p+=r+2,r=0);p

122:

for(l=r=p=i=0,a=a.replace(/->/g,0);c='<>-0'.indexOf(a[i])+1;i++,p--)c-4?c-3?c-2?l++:(r++,p+=2):(p-=l-2,l=0):(p+=r+2,r=0);p

130:

for(l=r=p=i=0;c='<>-'.indexOf(a[i])+1;i++,p--)c-3?c-1?(r++,p+=2):a[i+1]=='-'?a[i+2]=='>'?l++:(p-=l,l=0,i++):l++:(p+=r+2,r=0,i++);p
share|improve this answer
add comment

JavaScript [217 bytes]

prompt(x=l=r=0,z='replace',f='$1 $2 ')[z](/(>.*?)(->)/g,f)[z](/(<.*?)(<-)/g,f)[z](/(<|>)(<|>)/g,f)[z](/<-?|-?>/g,function(c){c=='>'&&(x++,r++),c=='<'&&(x--,l++),c=='->'&&(x+=++r,r*=0),c=='<-'&&(x-=++l,l*=0)}),alert(x)

Probably it may be shortened a bit more...

share|improve this answer
add comment

PHP, 284 282

No regex.

$i=fgets(STDIN);$c=$a=0;$s=str_split($i);while($c<count($s)){switch($s[$c]){case"<":if($s[$c+1]=="-"){if($s[$c+2]==">"){$c+=3;$a+=$rr;$rr=0;$ll++;}else{$c+=2;$a+=-($ll+1);$ll=0;}}else{$c++;$a--;$ll++;}break;case">":$c++;$a++;$rr++;break;case"-":$c+=2;$a+=$rr+1;$rr=0;break;}}echo$a;

Ungolfed:

$i=fgets(STDIN);
$c=$a=0;
$s=str_split($i);
while($c<count($s)){
    switch($s[$c]){
    case "<":
        if($s[$c+1]=="-"){
            if($s[$c+2]==">"){
                $c+=3;$a+=$rr;$rr=0;$ll++;
            }
            else{
                $c+=2;$a+=-($ll+1);$ll=0;
            }
        }
        else{
            $c++;$a--;$ll++;
        }
    break;
    case ">":
        $c++;$a++;$rr++;
        break;
    case "-":
        $c+=2;$a+=$rr+1;$rr=0;
        break;
    }
}
echo $a;
share|improve this answer
    
You can win 2 chars with str_split($i) (1 is the default for the second argument.) And $i should probably be $c, correct? –  fireeyedboy Feb 20 at 18:00
    
First line was wrong (it was $i) :P Fixed it! –  Vereos Feb 20 at 18:02
add comment

Another perl solution, 113 chars

There are already two answers that beat this, it's just for giggles. It uses an approach based on Ilmari's observation about the value of tokens:

$_=<>;chomp;s/->/#/g;s/<-/%/g;s/>(?=.*#)/?/g;s/<(?=.*%)/;/g;s/#/>/g;s/%/</g;$t+=ord for split//;print$t-61*length

Exploded a bit:

$_=<>;
chomp;
s/->/#/g;
s/<-/%/g;
s/>(?=.*#)/?/g;
s/<(?=.*%)/;/g;
s/#/>/g;
s/%/</g;
$t+=ord for split//;
print$t-61*length
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.