Унарные числа обычно представляют только неотрицательные целые числа, но мы можем расширить их, чтобы представить все целые числа следующим образом:

• Положительное целое число N представляется как N 1:5 -> 11111
• Отрицательное целое число -N представляется как 0 N, за которыми следуют 1:-5 -> 011111
• Ноль представлен как 0

Затем мы можем однозначно представить список этих чисел, если будем использовать 0в качестве разделителя:

3,-2,0,1
111,011,0,1
111 0 011 0 0 0 1
11100110001

Ваша задача: взять строку, представляющую такой список унарных чисел со знаком, и перевести ее в список десятичных чисел.

Детали

Вы можете предположить, что ввод представляет собой полный список унарных чисел со знаком. В частности, вашей программе не нужно обрабатывать 1) пустой ввод или 2) ввод, заканчивающийся разделителем.

Вы можете предположить, что величина каждого числа не будет превышать 127. Для языков с максимальными размерами строк или списков вы можете предполагать, что ввод и вывод будут соответствовать структуре данных вашего языка, но ваш алгоритм теоретически должен работать для списка любого размера.

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

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

Контрольные примеры

1 -> 1
0 -> 0 (or -0, and similarly for the other test cases)
011 -> -2
1101 -> 2,1
1100 -> 2,0
11001 -> 2,-1
110001 -> 2,0,1
11100110001 -> 3,-2,0,1
00000001 -> 0,0,0,-1
01111011111111001111111111111110111111111111111100111111111111111111111110111111111111111111111111111111111111111111 -> -4,8,-15,16,-23,42
01111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 -> -127

Python 2 , 73 70 байт

Функция, которая принимает строку в качестве входных данных и возвращает строковое представление списка Python. Ноль может быть представлен как 0и -0(когда это происходит последним):

lambda s:`map(len,s.split('0'))`.replace('0, ','-').replace('--','0,')

объяснение

1. split входная строка s на нули.
2. Возьмите длину каждой строки в результирующем списке (используяmap ).

Это займет у нас долгий путь. Нули были разделителями в конце концов. И числа были одинарными, поэтому lenудобно конвертировать их в десятичные. Но теперь мы испортили все виды использования без разделителей 0. К счастью, все виды использования без разделителей были ведущими нулями, поэтому они шли после нулевого разделителя и дали нам строки нулевой длины ( '00'.split('0') == ['', '', '']). Эти строки нулевой длины также стали 0из-за len.

3. Превратите список в строку ( используя «обратные кавычки» ), чтобы мы могли легче исправить беспорядок.
4. replaceвместо этого каждый ноль, который предшествует другому числу с отрицательным знаком на этом числе. Это исправляет использование 0в качестве знака, но ломает буквальные нули. Буквальным нулям также предшествовал разделитель, поэтому они стали парами дополнительных тире на следующем числе.
5. replaceкаждый --обратно в 0элемент в «списке».

Сетчатка , 23 21 байт

(.)0
$1 
01
-1
1+
$.&

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

Первый этап (.)0<newline>$1<space>соответствует любому персонажу, за которым следует0 . Матч заменяется первым символом, за которым следует пробел. Это разбивает строку по отдельным номерам.

Второй этап 01<newline>-1заменяет 0's перед блоком 1' s на -знак.

Последний этап 1+<newline>$.&сопоставляет все блоки 1's' и заменяет их длиной группы.

Вот пример с выводом отдельных этапов.

Vim, 56 байт

:s/\v(0?1*)0?/\1\r/g|%s/0/-/|%s/1*$/\=len(submatch(0))
D

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

Я давно не публиковал сообщения в vim. В основном я использую vim, потому что иногда V - это боль. Посколькуcount команда, которая идеально подходит для получения числа «1» в строке, будет перезаписывать любые «0» в строке, поэтому мы не можем впоследствии отменить ее.

Объяснение:

Это на один байт короче, чем простой способ:

:s/\v(0?1*)0?/\1\r/g
:%s/0/-
:%s/1*$/\=len(submatch(0))
D

из-за цепочки команд. Так как это разделяет команды, я буду использовать его для объяснения.

:s/                     " Substitute
                        " Search for...
   \v                   "   Enable 'magic'. This determines whether certain atoms require a backslash or not.
                        "   Without it we would have: '\(0\?1*\)0\?', which is 2 bytes longer
      0?                "   An optional 0
        1*              "   Followed by any number of '1's
     (    )             "   (call that group 1)
           0?           "   Followed by another optional 0
             /          " Replace it with...
              \1        "   Subgroup 1
                \r      "   A newline
                  /g    " Do this for every match on the current line.

Теперь каждый подписанный унарный номер находится на отдельной строке. Используя «11100110001» в качестве примера, на данный момент мы будем иметь:

111
011
0
1

:%s/0   " Replace every 0
     /- " With a dash  

:%s/1*$/                    " Replace every run of 1's at the end of a line
        \=len(submatch(0))  " With the length of said run

Так как мы добавляли новые строки в конце каждого матча, перед запуском у нас была пустая строка. После выполнения этого у нас будет '0' (потому что он соответствует серии 0 '1). Поэтому мы просто вызываем, Dчтобы удалить эту строку, оставив ее пустой

Haskell , 68 66 байт

f(x:r)|(a,b)<-span(>0)r=([(0-),(1+)]!!x$sum a):[z|_:t<-[b],z<-f t]

Попробуйте онлайн! Вводит в виде списка нулей и единиц. Пример использования: f [0,0,0,1,1]доходность [0,-2].

Объяснение:

Сопоставление с шаблоном в f(x:r)|(a,b)<-span(>0)rпривязывает xк первому элементу ввода, aк (потенциально пустому) списку следующих 1s и bк остальной части ввода. Учитывая вход [0,1,1,1,0,0,1], мы получаем x=0, a=[1,1,1]иb=[0,0,1] .

Тогда текущее число является либо суммой aотрицания if x=0, либо суммой aплюс один if x=1. Это достигается путем индексации с xв список , содержащий отрицание и приращение функции, и применяя полученную функцию к сумме a: [(0-),(1+)]!!x$sum a.

Остальной список bлибо пуст, либо содержит разделительный ноль и следующий номер. Понимание списка [z|_:t<-[b],z<-f t]пытается соответствовать bшаблону _:t, то есть забыть элемент head и привязать остальную часть списка к t. Если bпусто, это совпадение не выполняется, и понимание списка оценивается как [], что является базовым случаем для рекурсии. В противном случае функция fрекурсивно применяется к, tи понимание списка оценивается для всех элементов zиз результата f t.

Wolfram Language (Mathematica) , 80 байт

StringCases[#<>"0",x_~~Shortest@y___~~"0":>(If[x=="0",-#,#+1]&)@StringLength@y]&

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

Злоупотребляет механикой StringCases , поскольку не проверяет перекрывающиеся шаблоны. Так как мы ищем слева направо, без перекрытий, мы всегда получаем только те числа, которые нам нужны.

объяснение

#<>"0"

Добавить ноль в конце

StringCases

Найти все из следующего шаблона ...

x_~~Shortest@y___~~"0"

Один символ (назовите это x), сопровождаемый самой короткой возможной строкой нулевой длины или более длинной (назовите это y), сопровождаемый нулем.

(If[x=="0",-#,#+1]&)@StringLength@y

Применить к соответствующему шаблону: взять длину y. Еслиx ноль, тогда отрицайте значение. Иначе, увеличивай единицу.

Это 00также распространяется, поскольку yбудет пустой строкой, и мы вычислим -0( == 0).

Brain-Flak , 94 (70?) Байтов

([]){{}({(<()>)()}{}(<>)<>{<([{}]<>{})><>})
{{}<>([{}])(<>)}{}{}([])}{}<>([]){{}({}<>)<>([])}<>

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

Это на самом деле на удивление лаконично для мозговых штурмов.

Вот комментируемая / читаемая версия:

([])

{

    #Pop the Stack height
    {}

    (
        #If there isn't a leading 0, evaluate to 1...
        {
            (<()>)

            ()
        }

        #Pop the 0
        {}

        #Push a 0 onto the alternate stack
        (<>)
        <>

        #Run of '1's
        {
            #Decrement the alternate stack
            <([{}]<>{})>
            <>
        }

        #And push it here
    )

    #Was there a not leading 0?

    {
        {}

        #Invert the value on the alternate stack
        <>([{}])(<>)
    }

    #Pop 2 zeros
    {}{}


    ([])

}{}<>

#Push stack height
([])

#Reverse the stack
{

    {}

    ({}<>)

    <>([])

}<>

Если результат может быть обратным, мы можем сделать это для 70 вместо этого:

([]){{}({(<()>)()}{}(<>)<>{<([{}]<>{})><>}){{}<>([{}])(<>)}{}{}([])}<>

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

([]){{}({(<()>)()}{}(<>)<>{<([{}]<>{})><>})
{{}<>([{}])(<>)}{}{}(<>())<>([])}{}<>{{}({}<>)<>}<>

что также составляет 94 байта.

Perl 5 , 40 + 1 ( -n) = 41 байт

print'-'x/00/.y/1//.$"for"0$_"=~/00?1*/g

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

Шелуха , 20 18 17 15 14 байт

Γ~:?Σṁ_Πȯ₀tΣġ/

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

объяснение

Γ~:?Σṁ_Πȯ₀tΣġ/  Input is a list, say x = [0,1,1,0,0,0,1,1]
            ġ   Group by
             /  division.
                This splits x right before each 0: [[0,1,1],[0],[0],[0,1,1]]
Γ               Deconstruct into head y = [0,1,1] and tail z = [[0],[0],[0,1,1]]
   ?Σṁ_Π        Apply to y:
       Π         Product: 0
   ?Σ            If that is nonzero, take sum of y,
     ṁ_          else take sum of negated elements of y: u = -2
        ȯ₀tΣ    Apply to z:
           Σ     Concatenate: [0,0,0,1,1]
          t      Drop first element: [0,0,1,1]
         ₀       Recurse: [0,2]
 ~:             Tack u to the front: [-2,0,2]

Расщепление работает следующим образом. ġ/разделяет свой аргумент между каждой парой элементов, a,bдля которых /a bэто ложь. /a bэто деление с перевернутыми аргументами, поэтому bделится на a. Соответствующие значения в этой программе:

• /1 1дает 1(правда).
• /1 0дает 0(ложь).
• /0 1дает Inf(положительная бесконечность, правдивость).
• /0 0дает Any(специальное NaN-подобное значение, ложь).

Точность !! , 252 237 байт

N
Count i while _/48 {
Count n while 48/_ {
Write 45
50+N
}
_+49/_*50
Count u while _%50/49 {
_+100-_%50+N
}
_/50-1
Count h while _/200 {
Write _/200+48
_%200+1
}
Count t while _/20+_%2 {
Write _/20+48
_%20-_%2
}
Write _/2+48
Write 9
N
}

Использует -0. Вывод чисел, разделенных символами табуляции, с завершающей табуляцией. Попробуйте онлайн!

^{Время написания фактического алгоритма: 20 минут. Время отладки моего десятичного выходного кода: 45 минут. : ^ P}

С комментариями

Я не знаю, объясняют ли эти комментарии код очень хорошо - они основаны на моих заметках для меня, пока я писал его, поэтому они предполагают некоторое понимание того, как Acc !! работает. Если что-то требует большего объяснения, дайте мне знать, и я постараюсь прояснить ситуацию.

# We partition the accumulator _ as [number][flag][nextchar]
# [flag] is a 2-value slot and [nextchar] a 50-value slot
# So [nextchar] is _%50, [flag] is _/50%2, [number] is _/100
# [flag] is 1 if we're in the middle of reading a number, 0 if we're between numbers
# It is also used for outputting as decimal (see below)
# Possible input characters are 0, 1, and newline, so [nextchar] is 48, 49, or 10

# Read the first character
N
# Loop while the character we just read is 0 or 1 and not newline
Count i while _/48 {
  # What we do in the loop depends on the combination of [flag] and [nextchar]:
  # 0,48 (start of number, read 0) => write minus sign, [flag] = 1, read another char
  # _,49 (read 1) => increment [number], [flag] = 1, read another char
  # 1,48 (middle of number, read 0) => write/clear [number], status = 0, read another
  #      char
  # 1,10 (middle of number, read <cr>) => ditto; the next read will be 0 for eof, which
  #      means the acc will be less than 48 and exit the loop

  # Process leading 0, if any
  Count n while 48/_ {
    # acc is 48: i.e. [number] is 0, [flag] is 0, [nextchar] is 48 (representing a 0)
    # Output minus sign
    Write 45
    # Set [flag] to 1 (thereby exiting loop) and read [nextchar]
    50+N
  }
  # If number starts with 1, then we didn't do the previous loop and [flag] is not set
  # In this case, acc is 49, so we add (50 if acc <= 49) to set [flag]
  _+49/_*50

  # Process a run of 1's
  Count u while _%50/49 {
    # [nextchar] is 49 (representing a 1)
    # Increment [number] and read another
    _+100-_%50+N
  }

  # At this stage, we know that we're at the end of a number, so write it as decimal
  # This is "easier" (ha) because the number has at most three digits
  # We shift our partitioning to [number][flag] and set [flag] to 0
  _/50-1

  # Output hundreds digit if nonzero
  # Since [number] is _/2, the hundreds digit is _/200
  Count h while _/200 {
    Write _/200+48
    # Mod 200 leaves only tens and units; also, set [flag] to 1
    _%200+1
  }
  # Output tens digit (_/20) if nonzero OR if there was a hundreds digit
  # In the latter case, [flag] is 1
  Count t while _/20+_%2 {
    Write _/20+48
    # Mod 20 leaves only units; clear [flag] if it was set
    _%20-_%2
  }
  # Write units unconditionally
  Write _/2+48

  # Write a tab for the separator
  Write 9
  # Read another character
  N
}

Python 2 , 96 92 байта

lambda s:[[len(t),-len(t)+1]['1'>t]for t in s.replace('10','1 ').replace('00','0 ').split()]

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

Thx в ovs и DLosc по 2 байта каждый.

R 119 байт

function(x){n=nchar
y=regmatches(x,regexec("(0?)(1*)0?([01]*)",x))[[1]]
cat((-1)^n(y[2])*n(y[3]),"")
if(y[4]>0)f(y[4])}

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

Код использует это решение из stackoverflow для связанной проблемы (спасибо jeales за идею). Выводом является строка, разделенная пробелом, которая выводится на стандартный вывод.

Желе ,  19  18 байт

^{Должен быть лучший способ ...}

®ḢN$Ḣ©?ṄEȧ
ṣ0L€ÇL¿

Полная программа печати каждого номера с последующим переводом строки.

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

Как?

®ḢN$Ḣ©?ṄEȧ - Link 1, print first number and yield next input: list of numbers, X
           -                              e.g. [8,0,15,16,...] or [0,4,8,0,15,16,...]
      ?    - if...
    Ḣ      - condition: yield head and modify  8([0,15,16,...])   0([4,8,0,15,16,...])  
     ©     -            (copy to register)     8                  0
®          - then: recall from the register    8
   $       - else: last two links as a monad:
 Ḣ         -         yield head and modify                        4([8,0,15,16,...])
  N                  negate                                      -4
       Ṅ   - print that and yield it           8                 -4
        E  - all equal (to get 0 to be truthy) 1                  1
         ȧ - AND the (modified) input          [0,15,16,...]      [8,0,15,16,...]
           -   (ready to be the input for the next call to this link)

ṣ0L€ÇL¿ - Main link: list e.g. [0,1,0,0,0,0,1,1]
ṣ0      - split at zeros       [[],[1],[],[],[],[1,1]
  L€    - length of €ach       [0,1,0,0,0,2]
      ¿ - while...
     L  - condition: length                           1  1  1  0  ([0,1,0,0,0,2], [0,0,0,2], [0,2], [])
    Ç   - action: call the last link (1) as a monad  -1  0 -2     ( - 1            - 0        - 2)

QBasic, 88 86 байт

1u$=INPUT$(1)
z=u$<"1
IF n*z THEN?(1-2*s)*(n-s):s=0:n=0ELSE s=s-z:n=n+1
IF"!"<u$GOTO 1

Это было весело Многочисленные ревизии, начиная с 107-байтовой версии, привели к одному из самых запутанных кусочков QBasic, который я когда-либо писал. (Редактировать: как ни странно, я смог сыграть в гольф 2 байта, сделав код более понятным.)

Примечание: эта программа читает пользовательский ввод по одному символу за раз, не отображая его на экране (результат использования INPUT$(1)вместо обычного INPUTвыражения). Поэтому, когда вы печатаете, вы не увидите 1 и 0, но десятичные числа будут отображаться по мере их вычисления. Убедитесь, что нажали Enterв конце ввода, чтобы увидеть последний номер и завершить программу.

Неуправляемая версия

sign = 0
num = 0
DO
  digit$ = INPUT$(1)
  isZero = (digit$ < "1")
  IF num > 0 AND isZero THEN
    PRINT (1 - 2 * sign) * (num - sign)
    sign = 0
    num = 0
  ELSE
    IF isZero THEN sign = 1
    num = num + 1
  END IF
LOOP WHILE "!" < digit$

объяснение

(АКА "Что? Это все еще не имеет смысла!")

Основная стратегия состоит в том, чтобы запустить цикл, который захватывает один символ INPUT$(1)каждый раз, делает что-то с ним и продолжает цикл, пока у символа есть значение ASCII больше, чем у! (то есть, не было новой строки).

Мы отслеживаем текущие числа, используя две переменные. numколичество символов в текущем знаковом унарном числе (включая любой начальный ноль). signявляется 1ли число было ведущим к нулю, 0если нет. Оба они должны быть инициализированы в 0, что отлично подходит для гольфовой версии, потому что числовые переменные в QBasic автоматически инициализируются в 0.

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

Теперь, если мы находимся в середине чтения числа ( num > 0) и достигли нуля или конца ввода ( isZero), нам нужно вычислить, какое число мы закончили читать.

• signмагазины 0для позитива, 1для негатива. Чтобы получить 1положительное и -1отрицательное, нам нужно 1-2*sign.
• numхранит правильную величину для позитивов, но на единицу больше, чем величина для негативов (поскольку она включает маркер знака). Таким образом, мы можем использовать num-signдля величины.

Умножьте их вместе и напечатайте; затем сбросить signи numчтобы 0в ходе подготовки для считывания следующего номера.

В противном случае (если мы не достигли нуля или если мы достигли нуля в начале числа), мы обновляем signи выполняем numследующие действия:

• signстановится, 1если мы смотрим на ведущий ноль; в противном случае, если мы смотрим на одно, оно остается на том, что уже было. Гольф-код - s=s-zэто то же самое:
  • Если это ведущий ноль, zесть -1. Так sкак гарантированно будет 0(потому что это начало нового числа), s-zбудет 1.
  • Если это один, zесть 0. Затем s-zостается в любом значении sранее.
• num увеличивается

Это оно!

JavaScript (ES6), 60 байт

Возвращает разделенный пробелами список целых чисел.

s=>(0+s).replace(/00?1*/g,s=>(l=s.length,+s[1]?l-1:2-l)+' ')

Контрольные примеры

let f =

s=>(0+s).replace(/00?1*/g,s=>(l=s.length,+s[1]?l-1:2-l)+' ')

console.log(f("1")) // 1
console.log(f("0")) // 0
console.log(f("011")) // -2
console.log(f("1101")) // 2,1
console.log(f("1100")) // 2,0
console.log(f("11001")) // 2,-1
console.log(f("110001")) // 2,0,1
console.log(f("11100110001")) // 3,-2,0,1
console.log(f("00000001")) // 0,0,0,-1
console.log(f("01111011111111001111111111111110111111111111111100111111111111111111111110111111111111111111111111111111111111111111")) // -4,8,-15,16,-23,42
console.log(f("01111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111")) // -127

Луа , 58 байт

(...):gsub("(0?)(1*)0?",function(s,n)print(#n-2*#s*#n)end)

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

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