# 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, 2016 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. Feb 17, 2016 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. Feb 17, 2016 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! Feb 17, 2016 at 13:38
• I'm trying to solve this in SMBF (basically BF), and this language SUCKS to debug... ugh. Feb 17, 2016 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


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. :) Feb 17, 2016 at 16:53
• you can replace [0:g] by [:g] Feb 17, 2016 at 17:11
• and this replacement save 1 bytes i think -2*ord(z)+81 by 2*(z<')')-1 Feb 17, 2016 at 17:22

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


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

# 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


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


# 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


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

# 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. • Feb 17, 2016 at 18:30 # Mathematica, 62 55 bytes Position[Accumulate[(-1)^ToCharacterCode@#],-1][[1,1]]&  All of the long function names! Works similarly to Simmons' CJam answer. ## 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. # Ruby, 47 bytes Anonymous function. ->s{i,l=-1,0;l+=s[i+=1]>?(?-1:1 while l>-1;i+1}  ## 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. # Husk, 11 10 bytes neat backwards solution with 1/2 literal from @Dominic van Essen €.∫mȯ-.%2c   -- implicit last parameter (⁰ variable) c -- get char code %2c -- get the remainder of int div 2 ( => 0, ) => 1 -.%2c -- subtract 1/2 from either that 1 or 0 ȯ-.%2c -- compose the 3 functions [-. %2 c] together (map only takes one function) ∫mȯ-.%2c -- map over all the chars and get cumulative sum €.∫mȯ-.%2c -- find the first index where the element is equal to 1/2  old solution: https://pastebin.com/Ut8Wne6w Try it online! • A different 10 byte approach... Dec 20, 2021 at 20:56 • where did you find that . is 1/2? pretty strange ngl Dec 23, 2021 at 15:43 • See 'literals' section of github.com/barbuz/Husk/wiki/Syntax Dec 23, 2021 at 15:54 # 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  # Befunge 25 bytes Outputs in unary. This starts you on floor one, and will go until 0. 1<\1_v#:+-*2%2~ :#._@>$1>


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

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


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


# BQN, 14 bytes

1+0⊐˜1+¯1⋆-⟜@


Anonymous tacit function that takes a string and returns an integer wrapped in a unit array. Prepend ⊑ to get a plain integer instead.

Run it online!

### Explanation

1+0⊐˜1+¯1⋆-⟜@
-⟜@  Subtract null character from each character (yields list of charcodes)
¯1⋆      Take -1 to the power of each
1+         Scan with addition (cumulative sum), starting at 1
0⊐˜            Find the index of the first 0
1+               Add 1 because BQN uses 0-based indexing


# 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? Feb 17, 2016 at 16:52
• @TimmyD better to make them global so they're auto initialized. Feb 17, 2016 at 18:53

## PowerShell, 7565 62 bytes

[char[]]$args|%{$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

# 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