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

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!

• Do we have to use those exact chars? – Blue Feb 17 '16 at 13:12
• @muddyfish In the original challenges inputs were given in a specific form and so often a key part of the challenge was parsing the inputs; while I don't want this to become a "chameleon problem" I think the spirit of the original is that the input should be a string of brackets. I realise this does privilege some languages over others but I would call upon voters to take this into account when awarding upvotes to solutions. – A Simmons Feb 17 '16 at 13:16
• Very closely related to Parenthifiable binary numbers ... I don't feel quite strongly enough that it's a dupe, so I'll just leave a comment instead. – AdmBorkBork Feb 17 '16 at 13:31
• @TimmyD I see what you mean but I feel like this question is different enough that competitive answers won't be able to draw too much from that question! – A Simmons Feb 17 '16 at 13:38
• I'm trying to solve this in SMBF (basically BF), and this language SUCKS to debug... ugh. – mbomb007 Feb 17 '16 at 20:26

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


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

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

• Welcome to the site! This is a very nice first post. :) – Alex A. Feb 17 '16 at 16:53
• you can replace [0:g] by [:g] – Erwan Feb 17 '16 at 17:11
• and this replacement save 1 bytes i think -2*ord(z)+81 by 2*(z<')')-1 – Erwan Feb 17 '16 at 17:22

# 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


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

## 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.
'_* 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.


## 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
:               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
"               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


# 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


# 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. • – mbomb007 Feb 17 '16 at 18:30 ## Grep+AWK, 51 Bytes grep -o .|awk '/\(/{s++}/)/{s--}s<0{print NR;exit}'  The grep command places each character on a new line. ## 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

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

• You could put that comment into your answer instead. – mbomb007 Feb 17 '16 at 18:32

# 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


# 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


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

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


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

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

# Ruby, 47 bytes

Anonymous function.

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


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

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);
}
printf("%d", c);
}


Nicely-formatted version:

• Can you move the f=c=0 into the initialization of the loop as for(f=c=0;f!=... to save a byte? – AdmBorkBork Feb 17 '16 at 16:52
• @TimmyD better to make them global so they're auto initialized. – Cole Cameron Feb 17 '16 at 18:53

## PowerShell, 7565 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 # Mathematica, 62 55 bytes Position[Accumulate[(-1)^ToCharacterCode@#],-1][[1,1]]&  All of the long function names! Works similarly to Simmons' CJam answer. # Befunge 25 bytes Outputs in unary. This starts you on floor one, and will go until 0. 1<\1_v#:+-*2%2~ :#._@>$1>


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


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

## Lua, 9289 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)


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


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


# 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


## Python (3.5), 7871 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