When does Santa enter the basement? (AOC Day 1)

Question

I'm reproducing the second part of the first day of Advent of Code, with permission from the creator.

Santa is trying to deliver presents in a large apartment building, but he can't find the right floor - the directions he got are a little confusing. He starts on the ground floor (floor 0) and then follows the instructions one character at a time.

An opening parenthesis, (, means he should go up one floor, and a closing parenthesis, ), means he should go down one floor.

The apartment building is very tall, and the basement is very deep; he will never find the top or bottom floors.

Given a set of instructions, find the position of the first character that causes him to enter the basement (floor -1).

As examples:

input ) causes him to enter the basement at character position 1.

input ()()) causes him to enter the basement at character position 5.

A long input is given here that should yield the solution 1797.

This is code golf, so the shortest solution wins!

Answer 1

Jelly, 8 7 bytes

O-*+\i-

Thanks to @Sp3000 for golfing off 1 byte!

Try it online!

How it works

O-*+\i-    Main link. Input: s (string)

O          Ordinal; replace each character with its code point.
           This maps "()" to [48, 49].
 -*        Apply x -> (-1) ** x.
           This maps [48, 49] to [1, -1].
   +\      Compute the cumulative sum, i.e., the list of partial sums.
     i-    Find the first index of -1.

Answer 2

Python 2, 44 bytes

try:input()
except Exception,e:print e[1][2]

This clever solution was found by hallvabo, xsot, mitchs, and whatisgolf on this problem on Anarchy golf. If any of you want to post it instead, I'll remove this.

The trick is to let Python's parser do the work. The function input() tries to evaluate an input string, and throws an error on the first unmatched paren. This error, when caught, has form

SyntaxError('unexpected EOF while parsing', ('<string>', 1, 1, ')'))

which includes the character number where the error took place.

Answer 3

Python, 79 77 Bytes

lambda m:[sum([2*(z<')')-1for z in m][:g])for g in range(len(m)+1)].index(-1)

There is probably a better way to do this, but I'm out of ideas. Also this is my first post on codegolf.

Thanks to @Erwan. for golfing off 2 bytes.

Answer 4

Python 3, 59

Saved 3 bytes thanks to grc.

I really dislike doing manual string indexing in Python. It feels so wrong.

def f(x):
 c=q=0
 while-~c:c+=1-(x[q]>'(')*2;q+=1
 return q

Answer 5

CJam, 10 bytes

0l'_*:~1#)

or

0l'_*~]1#)

or (credits to Dennis)

Wl+'_*:~1#

Test it here.

Explanation

As A Simmons already noted, () is a lucky choice for CJam since those are the decrement/increment operators, respectively. That means if we're starting from zero we're looking for the step at which Santa reaches floor 1.

0   e# Push 0, the initial floor.
l   e# Read input.
'_* e# Riffle the input string with underscores, which duplicate the top of the stack.
:~  e# Evaluate each character, using a map which wraps the result in an array.
1#  e# Find the position of the first 1.
)   e# Increment because we're looking for a one-based index.

Answer 6

C, 55 bytes

g;main(f){for(;f;g++)f+=81-getchar()*2;printf("%d",g);}

Try it here.

Edit: Not sure why I left an unused variable in there...

Answer 7

Labyrinth, 18 bytes

+(+"#(!@
:  :
%2_,

Try it online! This answer was the result of collaborating with @MartinBüttner.

Explanation

The usual Labyrinth primer (I say "usual", but I actually rewrite this every time):

• Labyrinth is a stack-based 2D language, with execution starting from the first valid char (here the top left). At each junction, where there are two or more possible paths for the instruction pointer to take, the top of the stack is checked to determine where to go next. Negative is turn left, zero is go forward and positive is turn right.
• The stack is bottomless and filled with zeroes, so popping from an empty stack is not an error.
• Digits in the source code don't push the corresponding number – instead, they pop the top of the stack and push n*10 + <digit>. This allows the easy building up of large numbers. To start a new number, use _, which pushes zero.

This code is a bit weird since, for golfing purposes, the main loop combines two tasks into one. For the first half of the first pass, here's what happens:

+(+             Add two zeroes, decrement, add with zero
                This leaves -1 on the stack
"               NOP at a junction. -1 is negative so we try to turn left, fail, and
                turn right instead.
:               Duplicate -1

Now that the stack has been initialised with a -1 on top, the actual processing can start. Here's what the main loop does.

,               Read a byte of input
_2%             Take modulo 2.
:+              Duplicate and add, i.e. double
(               Decrement
                This maps "(" -> -1, ")" -> 1
+               Add to running total
"               NOP at a junction. Go forward if zero, otherwise turn right.
:               Duplicate the top of the stack

The last duplicate adds an element to the stack for every iteration we perform. This is important because, when we hit zero and go forward at the NOP, we do:

#               Push stack depth
(               Decrement
!               Output as num
@               Terminate

Answer 8

MATL, 12 11 bytes

1 byte saved using Dennis' idea of computing -1 raised to the input string

1_j^Ys0<f1)

Try it online!

1_         % number -1
j          % take string input
^          % element-wise power. This transforms '('  to 1 and ')' to -1
Ys         % cumulative sum
0<         % true for negative values
f          % find all such values 
1)         % pick first. Implicit display

Answer 9

Pyth, 13 bytes

f!hsm^_1Cd<zT

Explanation

              - autoassign z = input()
f             - First where V returns Truthy.
          <zT -     z[:T]
    m         -    [V for d in ^]
        Cd    -     ord(d)
     ^_1      -      -1**^
   s          -   sum(^)
 !h           -  not (^+1)

Try it here

Old algorithm, 15 bytes

f!h-/J<zT\(/J\)

Explanation:

                - autoassign z = input()
f               - First where V returns Truthy.
      <zT       -      z[:T]
     J          -     autoassign J = ^
    /    \(     -    ^.count("(")
           /J\) -    J.count(")")
   -            -   ^-^
 !h             -  not (^+1)

Try it here

Or if allowed to use chars other than ( and ), 9 bytes (moving pre-processing to input)

f!.v+<zT1

Explanation

          - autoassign z = input()
f         - First where V returns Truthy.
     <zT  -     z[:T]
    +   1 -    ^+"1"
  .v      -   eval(^)
 !        -  not ^

Try it here

Answer 10

JavaScript (ES6), 58 bytes

f=(s,t=s)=>s<')'?f(s.replace('()',''),t):t.length-s.length+1

Works by recursively removing a pair of matching ()s until the first character is a ). Warning: Don't try this on strings that don't have enough )s. Example:

((()())()))
((())()))
(()()))
(()))
())
)

At this point it sees that 12 characters were deleted in total so that the answer is 13.

Answer 11

Oracle SQL 11.2, 160 159 bytes

SELECT MIN(l)FROM(SELECT l,SUM(m)OVER(ORDER BY l)p FROM(SELECT LEVEL l,DECODE(SUBSTR(:1,LEVEL,1),'(',1,-1)m FROM DUAL CONNECT BY LEVEL<=LENGTH(:1)))WHERE p=-1;

Un-golfed

SELECT MIN(l) -- Keep the min level
FROM(
  SELECT l,SUM(m)OVER(ORDER BY l)p -- Sum the () up to the current row
  FROM(
    SELECT LEVEL l,DECODE(SUBSTR(:1,LEVEL,1),'(',1,-1)m -- ( equal 1 and ) equal -1 
    FROM DUAL 
    CONNECT BY LEVEL<= LENGTH(:1)
  )
)
WHERE p=-1 -- Keep the rows where the () sum is equal to -1

Answer 12

Retina, 22 21

!M`^((\()|(?<-2>.))+

Try it online or try the big test case. (The URL is large for the big test case, let me know if it breaks for you, seems OK in chrome.)

1 byte saved thanks to Martin!

We match the first set of balanced parentheses and extract it, then we count the number of times the empty string will match that result. I'm not sure if this is the nicest way to do this in Retina, particularly if PCRE mode makes it shorter, but using the $#_ replacement seemed to be longer because of off by one errors and the problem of having more than one match.

This algorithm causes odd behaviour for invalid input, it essentially assumes that if Santa doesn't make it to the basement, he mysteriously teleports there after the other movements.

Answer 13

Grep+AWK, 51 Bytes

grep -o .|awk '/\(/{s++}/)/{s--}s<0{print NR;exit}'

The grep command places each character on a new line.

Answer 14

CJam, 12 10 Bytes

0q{~_}%1#)

Try it here.

Two bytes saved thanks to Martin.

Explanation:

0              Load 0 onto the stack
 q             Load input onto the stack without evaluating
  {  }       Code block
   ~_          Evaluate the next command and duplicate the top stack element. The format of the question is good for CJam and Golfscript since ) and ( are increment and decrement operators (though the wrong way round).
        %      Map this code block over the string. This yields an array of Santa's floor positions
         1#   Find the first instance of a 1, since decrement and increment are swapped
           )  Fix the off-by-1 error caused by zero-indexing

Answer 15

Perl, 34 + 1 = 35 bytes

$.+=s+.+++s+\)++while")"gt$_;$_=$.

Thanks to Dennis for some tips.

Run with the -p flag. It works in Perl 5.10, but later versions need a space here: ++ while

Older, ungolfed version:

$_ = <>;                # get a line of input
while ($_ lt ')') {     # while it begins with a (
    s/.//;              # remove the first (
    s/\)//;             # remove the first )
    $i += 2;            # increase index by 2
}
print $i + 1;           # print the position

Answer 16

Javascript, 117 bytes

o=f=0;i=prompt().split('');for(c in i){switch (i[c]){case '(':f++;break;case ')':f--;if(f<0){alert(o+1);i=[];}}o++;}

Ignores other characters. Uses prompt and alert.

Answer 17

Python, 44 bytes

f=lambda s,i=1:i and-~f(s[1:],i-1+2*(s<')'))

The floor i starts at 1 so that we terminate on i being the falsey value 0. If not terminated, recursively add one to result with the first character removed and the floor number updated based on that character.

Answer 18

Javascript, 57 bytes

p=>{c=0;for(i in p){c+=p[i]==')'?-1:1;if(c<0)return+i+1}}

Pretty simple, just iterates over input, incs if '(' decs if ')'. Returns on first negative.

Answer 19

Ruby, 47 bytes

Anonymous function.

->s{i,l=-1,0;l+=s[i+=1]>?(?-1:1 while l>-1;i+1}

Answer 20

Lua, 92 89 87 Bytes

It takes in a command-line argument.

Edit: Saved 3 Bytes

Edit: Saved 2 bytes, and corrected a bug that could happen on edge cases, it now outputs via its exit code

r=0i=0(...):gsub(".",function(c)i=i+1r=r+(c==")"and-1or 1)if r<0then os.exit(i)end end)

Ungolfed

r,i=0,0                     -- set r (the actual floor), and i(the character count)
(...):gsub(".",function(c) -- apply an anonymous functions on each character of the input
  i,r=i+1,                  -- increment i
      r+(c==")"and -1 or 1) -- decrement r if c==")", increment it otherwise
  if r<0 then os.exit(i)end -- if r==-1, exit and output the current index
end)

Answer 21

PowerShell, 75 65 62 bytes

[char[]]$args[0]|%{$c+=(1,-1)[$_%40];$d++;if($c-lt0){$d;exit}}

Uses a similar technique as on Parenthifiable binary numbers to loop through all the input characters, keeping a running $counter of +1 for each ( and -1 for each ), then testing whether we've hit negative (i.e., we're in the basement).

_{Edit - saved 10 bytes by iterating over the actual characters rather than their indices
Edit 2 - saved 3 additional bytes by swapping equality check for modulo so casting is implicit}

Answer 22

C, 73 bytes

main(f,c){f=c=0;for(;f!=-1;c++){f+=1-((getchar()&1)<<1);}printf("%d",c);}

Expects input on STDIN; no characters other than ( and ) may appear in the input (at least until we've reached the answer). Input must be ASCII.

Emits the answer on STDOUT.

Uses the 1-bit difference between the ASCII for ( and ).

/* old-style arguments, implicitly int */
main(x, f)
{
    /* c is our character counter, f is the floor*/
    c = f = 0;
    /* increase c while f is not -1 */
    for (;f != -1; c++) {
        /* use difference in LSB to add one for (, subtract one for ) */
        f += 1-((getchar()&1)<<1);
    }
    /* answer */
    printf("%d", c);
}

Nicely-formatted version:

Answer 23

Mathematica, 62 55 bytes

Position[Accumulate[(-1)^ToCharacterCode@#],-1][[1,1]]&

All of the long function names! Works similarly to Simmons' CJam answer.

Answer 24

Befunge 25 bytes

Outputs in unary. This starts you on floor one, and will go until 0.

1<\1_v#:+-*2%2~
:#._@>$1>

Answer 25

Racket (102)

(λ(s)(let l((c 0)(b 0)(s(string->list s)))(if(> 0 b)c(l(+ 1 c)((if(eqv?(car s)#\()+ -)b 1)(cdr s)))))

Ungolfed

(λ (input)
  (let loop ((count 0) (balance 0) (chars (string->list input)))
    (if (> 0 balance)
        count
        (loop (+ 1 count)
              ((if (eqv? (car chars) #\() + -) balance 1)
              (cdr chars)))))

Answer 26

APL, 18 chars

{1⍳⍨¯1=+\¯1*')'=⍵}

In English:

• ¯1*')'=⍵: -1 where input =")", 1 otherwise;
• +\: running sum;
• 1⍳⍨¯1=: find the index of the first -1.

Answer 27

k/kona, 23 21 bytes

2 bytes saved by removing unnecessary parentheses.

{1+(+\1 -1"()"?x)?-1}

Usage:

k){1+(+\1 -1"()"?x)?-1} "())"
3

Answer 28

Perl, 40 + 1 = 41 bytes

$y++,($i+=/\(/*2-1)<0&&last for/./g;$_=$y

Requires the -p flag:

$ perl -pe'$y++,($i+=/\(/*2-1)<0&&last for/./g;$_=$y' <<< '()())'
5
$ perl -pe'$y++,($i+=/\(/*2-1)<0&&last for/./g;$_=$y' 1797.txt
1797

Assumes valid input.

How it works:

                                           # -p read line by line into $_ and auto prints at the end
        $y++,                              # Counter for steps taken
             ($i+=/\(/*2-1) < 0            # The match /\(/ will give 1 or 0 in a numeric context 1 for `(` and 0 for anything else
                                           # times it by 2 and subtracting -1 will yield 1 or -1
                               && last     # End the iteration if $i < 0
for/./g;                                   # Iterate over each items in the input
                                      $_=$y# Print the output

Answer 29

Python (3.5), 78 71 62 bytes

a recursive solution

f=lambda s,p=0,v=0:p if v<0else f(s[1:],p+1,v+2*(s[0]<')')-1) 

it's similar to this solution for mini golf

we can assume santa always reach the basement

Answer 30

Javascript (ES6), 68 67 bytes

(s,r,f=0)=>s.split``.map((l,i)=>(f+=l=='('?1:-1,f<0?r=r||++i:0))&&r

Takes input as first argument

Explanation

(s, r, f=0)                                  //Gets string, declares r and f to equal undefined and 0
         =>
            s.split``                        //Splits string into character array
            .map(                            //Loops over array
                 (l, i)=>(
                         f +=                //Increment f
                         l=='(' ? 1 : -1,    //By either 1 or -1 depending on character
                         f<0 ?               //If the floor is less than 0
                         r=r||++i            //And is first time below, r equals index (+1 to make it '1 indexed not 0')
                         : 0)
                         &&r                   //Return index