Analisar uma lista de números unários assinados

16

Números unários geralmente representam apenas números inteiros não negativos, mas podemos estendê-los para representar todos os números inteiros da seguinte maneira:

  • Um número inteiro positivo N é representado como N 1's:5 -> 11111
  • Um número inteiro negativo -N é representado como um 0seguido por N 1's:-5 -> 011111
  • Zero é representado como 0

Podemos então representar uma lista desses números sem ambiguidade, se usarmos 0como separador:

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

Sua tarefa: pegue uma sequência representando uma lista de números unários assinados e traduza-a em uma lista de números decimais.

Detalhes

Você pode assumir que a entrada é uma lista completa de números unários assinados. Em particular, seu programa não precisará lidar com 1) entrada vazia ou 2) entrada que termina com um separador.

Você pode supor que a magnitude de cada número não exceda 127. Para idiomas com tamanhos máximos de strings ou listas, você pode supor que a entrada e a saída se encaixem nas estruturas de dados do seu idioma, mas seu algoritmo deve teoricamente funcionar para uma lista de qualquer tamanho.

Seu programa ou função pode executar E / S de qualquer uma das maneiras padrão . A entrada pode ser uma sequência ou uma lista de caracteres, seqüências de caracteres únicos, números inteiros ou booleanos. Você pode usar dois caracteres para representar 1e 0; se você não usar 1e 0, especifique quais caracteres você está usando.

A saída deve ser números decimais em qualquer formato razoável de lista (em particular, deve haver algum tipo de separador entre números). Os números negativos devem ser indicados com um sinal de menos, embora, se o seu idioma tiver um formato diferente para números inteiros negativos, eu também o aceite. Zero pode ser representado na saída como 0ou -0.

Casos de teste

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
DLosc
fonte
2
Nitpick: Como isso contém '0's, não é tecnicamente unário. Bom desafio!
DJMcMayhem
4
@DJMcMayhem Nitpick ao nitpick: Eu nunca disse tecnicamente que era unário. É uma extensão do unário que estou chamando de "assinado unário". ;)
DLosc
@DJMcMayhem IMO, o desafio é especificamente que o separador ( 0) e o prefixo do sinal negativo ( 0) sejam os mesmos, embora ainda sejam inequívocos, pois você não pode ter sinais negativos no meio de um número (é 182--693-1um número? Não, e nem é 1111011000101111exatamente pelo mesmo motivo).
Erik the Outgolfer
Tudo bem se a lista emitida estiver na ordem inversa da entrada?
DJMcMayhem
tecnicamente, o decimal também não é decimal, pois usa o símbolo '-'
Unlambder

Respostas:

10

Python 2 , 73 70 bytes

Uma função que recebe uma string como entrada e retorna uma representação de string de uma lista Python. Zero pode ser representado por 0e -0(na última vez):

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

Explicação

  1. splita sequência de entrada snos zeros.
  2. Pegue o comprimento de cada sequência na lista resultante (usando map).

Isso nos leva um longo caminho. Os zeros eram separadores, afinal. E os números eram unários, de maneira lenconveniente os converte em decimal. Mas agora nós estragamos todos os usos não separadores de 0. Felizmente, todos os usos que não eram do separador estavam levando zeros, então eles vieram depois de um separador-zero e nos deram cadeias de comprimento zero ( '00'.split('0') == ['', '', '']). Essas cadeias de comprimento zero também se tornaram 0por causa do len.

  1. Transforme a lista em uma string ( usando "aspas reversas" ), para que possamos arrumar a bagunça mais facilmente.
  2. replacecada zero que precede outro número por um sinal negativo nesse número. Isso corrige o uso de 0como um sinal, mas quebra os zeros literais. Os zeros literais também foram precedidos por um separador; portanto, eles agora se tornaram pares de traços extras no próximo número.
  3. replacecada um de --volta em um 0elemento na "lista".
mercator
fonte
1
Bem-vindo ao PPCG!
Steadybox
Esta é uma abordagem realmente criativa! Você pode adicionar uma breve explicação para que aqueles que não falam Python também apreciem sua resposta.
21917 DLosc #
@DLosc, obrigado, eu não sabia sobre o backtick. Explicação Wordy também acrescentou.
mercator
8

Retina , 23 21 bytes

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

Experimente online!

O primeiro estágio (.)0<newline>$1<space>corresponde a qualquer caractere seguido de a 0. A partida é substituída pelo primeiro caractere seguido por um espaço. Isso divide a string nos números individuais.

O segundo estágio 01<newline>-1substitui 0's antes de um bloco de 1' s para a -placa.

O último estágio 1+<newline>$.&corresponde a todos os blocos de 1's e os substitui pelo comprimento do grupo.

Aqui está um exemplo com a saída dos estágios individuais.

ovs
fonte
Muito bom - todas as minhas idéias parecem ter clock de 24 bytes ...
Neil
1
Você poderia adicionar uma explicação? Eu não falo retina.
Daniel
@Dopapp adicionou uma explicação
ovs
7

Vim, 56 bytes

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

Experimente online!

Eu não publico no vim há algum tempo. Eu estou usando principalmente o vim porque V às vezes é uma dor. Como o countcomando, perfeito para colocar o número de '1's na linha, substituirá qualquer' 0 'na linha, portanto, não podemos negá-lo posteriormente.

Explicação:

Este é um byte mais curto que o simples:

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

devido ao encadeamento de comandos. Como esse separa os comandos, eu o usarei para a explicação.

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

Agora, cada número unário assinado está em uma linha individual. Usando '11100110001' como exemplo, neste momento teremos:

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

Como adicionamos novas linhas ao final de cada partida, tínhamos uma linha vazia antes de executá-la. Depois de executar isso, teremos um '0' (porque corresponde a uma execução de 0 '1). Então chamamos Dpara excluir esta linha, deixando em branco

DJMcMayhem
fonte
Ugh. :%s/1+$/você obteria um byte menor se não fosse a necessidade de barra invertida a +:(
NieDzejkob
@NieDzejkob Não entendo por que isso seria mais curto. E também, isso daria em -vez de 0ou-0
DJMcMayhem
Eu queria eliminar a última linha dessa maneira: P, não importa.
NieDzejkob
7

Haskell , 68 66 bytes

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

Experimente online! Aceita entrada como uma lista de zeros e uns. Exemplo de uso: f [0,0,0,1,1]rendimentos [0,-2].

Explicação:

O padrão correspondente em f(x:r)|(a,b)<-span(>0)rliga x- se ao primeiro elemento da entrada, aa uma lista (potencialmente vazia) dos seguintes 1s e bao restante da entrada. Dada uma entrada [0,1,1,1,0,0,1], obtemos x=0, a=[1,1,1]e b=[0,0,1].

O número atual é então a soma de anegado se x=0ou a soma de amais um se x=1. Isto é conseguido através da indexação com xa uma lista que contém uma função negação e incremento, e aplicando a função resultante com a soma de a: [(0-),(1+)]!!x$sum a.

A lista restante bestá vazia ou contém um zero separador e o próximo número. A compreensão da lista [z|_:t<-[b],z<-f t]tenta corresponder bao padrão _:t, ou seja, esquecer o elemento head e vincular o restante da lista t. Se bestiver vazio, essa correspondência falhará e a compreensão da lista será avaliada [], que é o caso base da recursão. Caso contrário, a função fé aplicada recursivamente te a compreensão da lista é avaliada para todos os elementos zdo resultado de f t.

Laikoni
fonte
3

Wolfram Language (Mathematica) , 80 bytes

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

Experimente online!

Abusa do mecânico StringCases, pois ele não verifica padrões sobrepostos. Como pesquisamos da esquerda para a direita, sem sobreposições, sempre obtemos apenas os números inteiros necessários.

Explicação

#<>"0"

Anexar um zero no final

StringCases

Encontre todos os seguintes padrões ...

x_~~Shortest@y___~~"0"

Um único caractere (chame-o x), seguido pela menor seqüência possível de comprimento zero ou maior (chame-o y), seguido por um zero.

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

Aplicar ao padrão correspondente: mede o comprimento de y. Se xfor zero, negue o valor. Senão, incremente um.

Isso também abrange 00, já yque seria uma string vazia e calcularíamos -0( == 0).

JungHwan Min
fonte
3

Flacidez cerebral , 94 (70?) Bytes

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

Experimente online!

Na verdade, isso é surpreendentemente conciso para o cérebro.

Aqui está uma versão comentada / legível:

([])

{

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

    {}

    ({}<>)

    <>([])

}<>

Se a saída puder ser inversa, podemos fazer isso por 70:

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

Essa dica é quase perfeita para essa situação. Mas isso não funciona muito bem, já que precisamos pressionar um 0 antes de fazer a operação (contando os '1s), e a operação acontece em um loop. O mais curto que pude utilizar esta dica é:

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

que também tem 94 bytes.

DJMcMayhem
fonte
3

Casca , 20 18 17 15 14 bytes

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

Experimente online!

Explicação

Γ~:?Σṁ_Πȯ₀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 divisão funciona assim. ġ/divide seu argumento entre cada par de elementos a,bpara o qual /a bé falso. /a bé a divisão com argumentos invertidos, então bdivididos por a. Os valores relevantes neste programa são estes:

  • /1 11(verdade).
  • /1 00(falso).
  • /0 1Inf(infinito positivo, verdade).
  • /0 0Any(um valor especial de NaN, falso).
Zgarb
fonte
3

Acc !! , 252 237 bytes

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
}

Usos -0. Produz números separados por caracteres de tabulação, com uma tabulação à direita.Experimente online!

Quantidade de tempo escrevendo o algoritmo real: 20 minutos. Período de depuração do meu código de saída decimal: 45 minutos. : ^ P

Com comentários

Não sei se esses comentários explicam muito bem o código - eles são baseados nas minhas anotações enquanto eu escrevia, então eles assumem alguma compreensão de como Acc !! trabalho. Se algo precisar de mais explicações, entre em contato e tentarei esclarecer as coisas.

# 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
}
DLosc
fonte
2

Python 2 , 96 92 bytes

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

Experimente online!

Thx para ovs e DLosc para 2 bytes cada.

Chas Brown
fonte
2

R , 119 bytes

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

Experimente online!

O código usa esta solução do stackoverflow para um problema relacionado (obrigado aos ciumentos pela ideia). A saída é uma sequência separada por espaço impressa em stdout.

NofP
fonte
2

Geléia ,  19  18 bytes

Deve haver uma maneira melhor ...

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

Um programa completo imprimindo cada número seguido de um avanço de linha.

Experimente online!

Quão?

®Ḣ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)
Jonathan Allan
fonte
1

QBasic, 88 86 bytes

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

Isso foi divertido. Várias revisões a partir de uma versão de 107 bytes resultaram em um dos bits mais ofuscados do QBasic que acho que já escrevi. (Edit: Estranhamente, eu consegui jogar 2 bytes, tornando o código mais claro.)

Nota: este programa lê a entrada do usuário, um caractere de cada vez, sem ecoá-lo na tela (resultado do uso em INPUT$(1)vez da INPUTdeclaração usual ). Portanto, enquanto você digita, não verá os zeros e zeros, mas os números decimais aparecerão conforme são calculados. Certifique-se de baterEnter no final da entrada para ver o último número e finalizar o programa.

Versão ungolfed

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$

Explicação

(AKA "O quê? Isso ainda não faz sentido!")

A estratégia básica é executar um loop que agarra um caractere de INPUT$(1)cada vez, faz coisas com ele e continua em loop enquanto o personagem tiver um valor ASCII maior que o de! (ou seja, não era uma nova linha).

Nós acompanhamos os números em andamento usando duas variáveis. numé o número de caracteres no número unário assinado atual (incluindo qualquer zero inicial). signé 1se o número tiver um zero à esquerda, 0caso contrário. Ambos precisam ser inicializados 0, o que é ótimo para a versão golfada porque as variáveis ​​numéricas no QBasic são inicializadas automaticamente para0 .

Sempre que lemos um personagem, a primeira coisa é determinar se é 1ou não 0. Usaremos esse resultado duas vezes, para armazená-lo isZero. Tecnicamente, esse nome é enganador, pois o valor também será verdadeiro se o caractere for uma nova linha. Observe que a verdade no QBasic é -1e falsey é0 .

Agora, se estamos no meio da leitura de um número ( num > 0) e atingimos o zero ou o final da entrada ( isZero), precisamos calcular qual número terminamos de ler.

  • signarmazena 0para positivo, 1para negativo. Para obter o 1positivo e o -1negativo, precisamos 1-2*sign.
  • numarmazena a magnitude correta para positivos, mas uma a mais que a magnitude para negativos (uma vez que inclui o marcador de sinal). Para que possamos usar num-signpela magnitude.

Multiplique-os e imprima; redefina signe numpara 0em preparação para ler o próximo número.

Caso contrário (se não ter atingido um zero, ou se nós batemos um zero no início de um número), atualizamos signe numcomo segue:

  • signtorna- 1se se estamos olhando para um zero à esquerda; caso contrário, se estivermos olhando para um, ele permanece no que já era. O código de golfe és=s-z , o que equivale à mesma coisa:
    • Se este é um zero inicial, zé -1. Como sé garantido que será 0(porque este é o início de um novo número), s-zserá1 .
    • Se este é um, zé 0. Em seguida, s-zpermanece com o valor que stinha anteriormente.
  • num é incrementado.

É isso aí!

DLosc
fonte
0

JavaScript (ES6), 60 bytes

Retorna uma lista separada por espaços de números inteiros.

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

Casos de teste

Arnauld
fonte
0

Lua , 58 bytes

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

Experimente online!

Programa completo, recebe entrada da linha de comando e imprime os números em stdout separados por novas linhas.

Jonathan S.
fonte