Я воспроизводлю вторую часть первого дня «Появления кода» с разрешения создателя.

Санта пытается доставить подарки в большой жилой дом, но он не может найти правильный этаж - направления, которые он получил, немного запутаны. Он начинает с первого этажа (этаж 0) и затем следует инструкциям по одному символу за раз.

Открывающая скобка (означает, что он должен подняться на один этаж, а закрывающая скобка )означает, что он должен спуститься на один этаж.

Жилой дом очень высокий, а подвал очень глубокий; он никогда не найдет верхний или нижний этажи.

Учитывая набор инструкций, найдите положение первого персонажа, который заставляет его войти в подвал (этаж -1).

В качестве примеров:

ввод )заставляет его войти в подвал в позиции персонажа 1.

ввод ()())заставляет его войти в подвал в позиции персонажа 5.

Длинный вклад дается здесь , что должно дать решение 1797.

Это код гольф, поэтому выигрывает самое короткое решение!

Желе, 8 7 байт

O-*+\i-

Спасибо @ Sp3000 за вывод 1 байта!

Попробуйте онлайн!

Как это устроено

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 байта

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

Это умное решение было найдено с помощью Hallvabo, xsot, mitchs и whatisgolf по этой проблеме на анархическом гольфе . Если кто-то из вас захочет опубликовать это, я удалю это.

Хитрость заключается в том, чтобы парсер Python сделал всю работу. Функция input()пытается вычислить входную строку и выдает ошибку в первом непревзойденном парене. Эта ошибка при обнаружении имеет форму

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

который включает в себя номер символа, где произошла ошибка.

Python, 79 77 байт

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

Возможно, есть лучший способ сделать это, но у меня нет идей. Также это мой первый пост на Codegolf.

Спасибо @Erwan. для игры в гольф от 2 байтов.

Python 3, 59

Сохранено 3 байта благодаря grc.

Мне очень не нравится выполнять ручную индексацию строк в Python. Это так неправильно.

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

C, 55 байтов

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

Попробуй здесь .

Изменить: Не уверен, почему я оставил неиспользованную переменную там ...

CJam, 10 байтов

0l'_*:~1#)

или

0l'_*~]1#)

или (кредиты Денису)

Wl+'_*:~1#

Проверьте это здесь.

объяснение

Как уже отмечал Симмонс, ()это удачный выбор для CJam, так как это операторы декремента / приращения соответственно. Это означает, что если мы начинаем с нуля, мы ищем шаг, на котором Санта достигает 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.

Лабиринт , 18 байт

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

Попробуйте онлайн! Этот ответ стал результатом сотрудничества с @ MartinBüttner.

объяснение

Обычный лабиринтный праймер (я говорю «обычный», но я на самом деле переписываю это каждый раз):

• Лабиринт - это основанный на стеке двумерный язык, выполнение которого начинается с первого действительного символа (здесь вверху слева). В каждом соединении, где есть два или более возможных путей для указателя инструкций, вершина стека проверяется, чтобы определить, куда идти дальше. Отрицательным является поворот влево, нулевым - движение вперед, а положительным - поворот направо.
• Стек бездонный и заполнен нулями, поэтому выталкивание из пустого стека не является ошибкой.
• Цифры в исходном коде не выдвигают соответствующее число - вместо этого они выталкивают вершину стека и нажимают n*10 + <digit>. Это позволяет легко накапливать большие числа. Чтобы начать новый номер, используйте_ , который толкает ноль.

Этот код немного странный, поскольку для целей игры в гольф основной цикл объединяет две задачи в одну. Для первой половины первого прохода вот что происходит:

+(+             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

Теперь, когда стек был инициализирован с -1 сверху, фактическая обработка может начаться. Вот что делает основной цикл.

,               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

Последний дубликат добавляет элемент в стек для каждой итерации, которую мы выполняем. Это важно, потому что, когда мы достигаем нуля и идем вперед в NOP, мы делаем:

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

Oracle SQL 11.2, 160 159 байт

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

Сетчатка ,22 21

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

Попробуйте онлайн или попробуйте большой контрольный пример. (URL большой для большого тестового случая, дайте мне знать, если он сломался для вас, кажется, в Chrome нормально.)

1 байт сохранен благодаря Мартину!

Мы сопоставляем первый набор сбалансированных скобок и извлекаем его, а затем подсчитываем, сколько раз пустая строка будет соответствовать этому результату. Я не уверен, является ли это наилучшим способом сделать это в Retina, особенно если режим PCRE делает его короче, но использование $#_замены показалось более продолжительным из-за одной ошибки и проблемы с более чем одним совпадением.

Этот алгоритм вызывает странное поведение для неверного ввода, он по существу предполагает, что, если Санта не доберется до подвала, он таинственным образом телепортируется туда после других движений.

Grep + AWK, 51 байт

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

Команда grepпомещает каждый символ на новую строку.

Pyth, 13 байт

f!hsm^_1Cd<zT

объяснение

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

Попробуй здесь

Старый алгоритм, 15 байтов

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

Объяснение:

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

Попробуй здесь

Или, если разрешено использовать символы, отличные от (и ), 9 байтов (перевод предварительной обработки на вход)

f!.v+<zT1

объяснение

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

Попробуй здесь

JavaScript (ES6), 58 байт

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

Работает путем рекурсивного удаления пары совпадающих ()s до тех пор, пока первый символ не станет a ). Предупреждение: не пытайтесь делать это со строками, которых недостаточно) s. Пример:

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

На данный момент он видит, что всего 12 символов было удалено, так что ответ 13.

MATL , 12 11 байт

1 байт сохранен с использованием идеи Денниса вычисления -1, возведенного во входную строку

1_j^Ys0<f1)

Попробуйте онлайн!

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 байт

0q{~_}%1#)

Попробуй это здесь.

Два байта спасены благодаря Мартину.

Объяснение:

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 байт

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

Игнорирует других персонажей. Использует promptи alert.

Perl, 34 + 1 = 35 байт

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

Спасибо Деннису за несколько советов.

Беги с -pфлагом. Это работает в Perl 5.10, но более поздние версии требуют пробела здесь:++ while

Более старая, негольфированная версия:

$_ = <>;                # 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 байта

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

Пол iначинается 1так , что мы заканчиваем на iвремя значение falsey 0. Если не завершено, рекурсивно добавьте единицу к результату с удалением первого символа и обновлением номера этажа на основе этого символа.

Javascript, 57 байт

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

Довольно просто, просто перебирает ввод, incs if '(' decs if ')'. Возвращает на первый негатив.

Рубин, 47 байтов

Анонимная функция.

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

C 73 байта

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

Ожидается ввод на STDIN; никакие символы кроме (и не )могут появиться на входе (по крайней мере, пока мы не дойдем до ответа). Ввод должен быть ASCII.

Издает ответ на STDOUT.

Использует 1-битную разницу между ASCII для (и ).

/* 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);
}

Красиво отформатированная версия:

PowerShell, 75 65 62 байта

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

Использует технику, аналогичную двоичным числам Parenthifiable, чтобы перебрать все входные символы, сохраняя текущую $cунцию +1для каждого (и -1для каждого ), а затем проверяя, не попали ли мы в минус (т. Е. Мы в подвале).

_{Редактировать - сохранить 10 байтов путем итерации по фактическим символам, а не по их индексам
Редактировать 2 - сохранить 3 дополнительных байта путем замены проверки равенства по модулю, поэтому приведение неявно}

Mathematica, 62 55 байт

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

Все длинные имена функций! Работает аналогично ответу Симмонса на CJam.

Befunge 25 байтов

Выходы в одинарных. Это запускает вас на первом этаже и будет идти до 0.

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

Ракетка (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 символов

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

По-английски:

• ¯1*')'=⍵: -1 где input = ")", 1 в противном случае;
• +\: текущая сумма;
• 1⍳⍨¯1=: найти индекс первого -1.

Луа, 92 89 87 байт

Он принимает аргумент командной строки.

Изменить: сохранено 3 байта

Редактировать: Сохранено 2 байта и исправлена ​​ошибка, которая могла произойти в крайних случаях, теперь она выводится через код выхода

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)

к / кона , 23 21 байт

2 байта сохраняются путем удаления ненужных скобок.

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

Использование:

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

Perl, 40 + 1 = 41 байт

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

Требуется -pфлаг:

$ 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

Предполагается действительный ввод.

Как это устроено:

                                           # -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 байт

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

Принимает ввод в качестве первого аргумента

объяснение

(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), 78 71 62 байта

рекурсивное решение

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

это похоже на это решение для мини-гольфа

мы можем предположить, что Санта всегда достигает подвала