Repara los rangos

30

Dada la entrada de una lista de enteros positivos con algunos reemplazados por 0, envíe la lista con los números faltantes que se cambiaron por 0reemplazados.

Características de la lista de entrada:

  • La lista siempre tendrá una longitud de al menos 2.

  • Definamos la lista de entrada como ay la "lista original" (es decir, la lista antes de que los números fueran reemplazados por 0s) como b. Para cualquiera n, a[n]es b[n]o 0.

  • Para cualquiera n, b[n]es b[n-1] + 1o b[n-1] - 1. Es decir, los números en bsiempre cambiarán 1en cada índice de su anterior. El primer elemento está, por supuesto, exento de esta regla.

  • Para cada ejecución de ceros en a(es decir, elementos consecutivos reemplazados 0), con xlo que representa el índice del inicio de la carrera y y que representa el final, a[x-1]que a[y+1]siempre será bien únicamente aumentando o disminuyendo exclusivamente. Por lo tanto, solo habrá una forma posible de completar los ceros.

    • Esto también significa que ni el primer ni el último elemento de la matriz pueden ser ceros.

En términos más simples, para completar una serie de ceros, simplemente reemplácelo con un rango desde el número anterior al siguiente. Por ejemplo, una entrada de

1 2 0 0 0 6 7

debe salir

1 2 3 4 5 6 7

Como se trata de , ganará el código más corto en bytes.

Casos de prueba:

In                      Out
-----------------------------------------------------
1 0 0 0 5 6 0 4 0 0 1 | 1 2 3 4 5 6 5 4 3 2 1
7 6 0 0 3 0 0 0 7 0 5 | 7 6 5 4 3 4 5 6 7 6 5
1 0 3 0 5 0 3 0 5 0 7 | 1 2 3 4 5 4 3 4 5 6 7
14 0 0 0 0 0 0 0 0 23 | 14 15 16 17 18 19 20 21 22 23
Pomo de la puerta
fuente
En lugar de ¿ 0puede nuestro programa tomar otro valor como null?
Downgoat
@Downgoat No, los números faltantes se deben dar como 0.
Pomo de la puerta

Respuestas:

15

JavaScript (ES6), 72 66 64 54 53 bytes

¡Guardado 12 bytes gracias a @Neil!

Guardado 1 byte gracias a @IsmaelMiguel

a=>a.map((l,i)=>l?b=l:b+=a.find((q,r)=>r>i&&q)>b||-1)

Bastante bueno para JavaScript.


Pruébelo en línea (todos los navegadores funcionan)

Explicación

a=>  // Function with arg `a`
  a.map((l,i)=>  // Loop through input
    l?             // If nonzero
      b=l          // Set `b` to current number
    :a.find((q,r)=>r>i&q) // Otherwise look for the next nonzero number
     >b?           // If it's increased since nonzero last number   
       ++b:--b)    // Increasing? increase `b` (the previous nonzero number)
                   // otherwise decrease `b`
Downgoat
fuente
1
Creo que a.find((q,r)=>r>i&&q)>b?++b:--bes lo mismo queb+=a.find((q,r)=>r>i&&q)>b||-1
Ismael Miguel
@IsmaelMiguel que es inteligente, gracias!
Downgoat
De nada. Me alegra que te haya funcionado.
Ismael Miguel
Creo que puede reemplazar && con solo & (acabo de notar que tiene uno & en la explicación y dos en la respuesta)
Charlie Wynn
7

MATL , 11 12 bytes

fGXzGn:3$Yn

Funciona con la versión actual (13.0.0) del lenguaje / compilador.

Pruébalo en línea!

f        % implicitly input array. Indices of nonzero elements (*)
GXz      % push input and get its nonzero elements (**)
Gn:      % vector [1,2,...,n], where n is input length (***)
3$Yn     % interpolate at positions (***) from data (**) defined at positions (*)
Luis Mendo
fuente
7

Haskell, 68 61 58 bytes

g(a:b:r)=[a..b-1]++[a,a-1..b+1]++g(b:r)
g x=x
g.filter(>0)

Ejemplo de uso: g.filter(>0) $ [7,6,0,0,3,0,0,0,7,0,5]-> [7,6,5,4,3,4,5,6,7,6,5].

Cómo funciona: elimine los ceros de la entrada, luego llame g. Deje aser el primer y bluego el segundo elemento de la lista restante. Concatene las listas de aarriba hacia abajo b-1y ahacia abajo b+1(una de ellas estará vacía) y una llamada recursiva con acaída.

Editar: @Zgarb guardó 3 bytes. ¡Gracias!

nimi
fuente
6

Mathematica, 59 bytes

#//.{a___,x_,0..,y_,b___}:>{a,##&@@Range[x,y,Sign[y-x]],b}&

Caso de prueba

%[{1,0,3,0,5,0,3,0,5,0,7}]
(* {1,2,3,4,5,4,3,4,5,6,7} *)
njpipeorgan
fuente
4

Perl, 47 45 44 39 37 bytes

Incluye +1 para -p

s%\S+%$p+=/\G(0 )+/?$'<=>$p:$&-$p%eg

Espera la lista en stdin. Ejemplo: echo 1 0 3 0 1 | perl -p archivo.pl

Ton Hospel
fuente
Veo alguna copia pegando aquí ... ;-) Bien hecho por cierto.
Kenney
3

Jalea, 12 11 bytes

ḢWW;ḟ0Ṫr¥\F

Pruébalo en línea!

Versión alternativa, 8 bytes (no competitiva)

Desafortunadamente, Jelly's popno se lanzó a iterable, en la última versión anterior a este desafío. Esto se ha solucionado y lo siguiente funciona en la versión actual.

ḟ0Ṫr¥\FḊ

Pruébalo en línea!

Cómo funciona

ḢWW;ḟ0Ṫr¥\F  Main link. Input: A (list)

Ḣ            Pop the first element of A. Let's call it a.
 WW          Yield [[a]].
   ;         Concatenate with the popped A.
             This wraps the first element of A in an array.
    ḟ0       Filter; remove all zeroes.
        ¥    Create a dyadic chain:
      Ṫ        Pop the last element of the left argument.
       r       Call range on the popped element and the right argument.
         \   Reduce the modified A by this chain.
          F  Flatten the resulting list of ranges.

En la versión alternativa, se ḢWW;vuelve innecesario. Sin embargo, dado que el primer elemento se convierte en iterable antes de aparecer, en realidad no se modifica. El final elimina el duplicado del primer elemento.

Dennis
fuente
3

Retina, 39 34 31 bytes

3 bytes guardados gracias a @Martin.

+`1(1*) (?= +((1)\1)?)
$0$1$3$3

Toma entrada y da salida en unario.

El código llena iterativamente cada lugar vacío (0) previous_number - 1 + 2 * if_next_nonzero_number_bigger. previous_number - 1es $1y if_next_nonzero_number_biggeres $3.

Con E / S decimal, el código tiene 51 bytes de longitud, como puede ver en el intérprete en línea con todos los casos de prueba .

randomra
fuente
Puede guardar otro byte omitiendo el primero 1en la búsqueda anticipada.
Martin Ender
@ MartinBüttner Derecha, editado.
randomra
2

GNU Sed (con execextensión usando bash), 61

La puntuación incluye +1 para la -ropción de sed.

:
s/( 0)+ /../
s/\w+..\w+/{&}/
s/.*/bash -c 'echo &'/e
/ 0/b
  • Encuentra carreras de 0s y reemplázalas..
  • Coloque llaves alrededor de los números de punto final para crear una expansión de llave bash como {1..4}para los puntos finales locales. La belleza de las expansiones de llaves bash aquí es que la secuencia generada siempre se ejecutará en la dirección correcta, independientemente de si el inicio o el final son más grandes.
  • Use la eopción del scomando para llamar a bash para evaluar esta expansión de llaves
  • Si encuentra más 0s, vuelva al inicio.

Ideona

Trauma digital
fuente
2

Python 2, 195 111 bytes (¡gracias Alex !)

t=input()
z=0
for i,e in enumerate(t):
 if e:
  while z:t[i-z]=e+z if l>e else e-z;z-=1
  l=e
 else:z+=1
print t

Entrada: debe ser [list]de entradas
Salida: [list]de entradas

vageli
fuente
¡Lo siento por eso! Fijo. Gracias por el aviso.
vageli
Sin preocupaciones. Buena solución :) Puedes bajarlo a 112 bytes usando esto , que es tu mismo enfoque, solo jugué un poco más. También tenemos una colección de consejos para jugar golf en Python aquí .
Alex A.
1

Perl, 85 82 bytes

incluye +1 para -p

s/(\d+)(( 0)+) (\d+)/$s=$1;$e=$4;$_=$2;$c=$s;s!0!$c+=$e<=>$s!eg;"$s$_ $e"/e&&redo

Espera la lista en stdin. Ejemplo: echo 1 0 3 0 1 | perl -p file.pl.

Esto usa una expresión regular anidada. Algo legible:

s/(\d+)(( 0)+) (\d+)                  # match number, sequence of 0, number
 /
    $s=$1;                            # start number
    $e=$4;                            # end number
    $_=$2;                            # sequence of ' 0'
    $c=$s;                            # initialize counter with start number
    s!0! $c += $s <=> $e !eg          # replace all 0 with (in|de)cremented counter
    "$s$_ $e"                         # return replacement
 /e
&& redo                               # repeat until no more changes.
Kenney
fuente
1

Python 2, 92 88 bytes

(Variable intermedia eliminada)

t=filter(bool,input())
print sum([range(o,p,cmp(p,o))for o,p in zip(t,t[1:])],[])+t[-1:]
Orez
fuente
1

Pyth, 17 bytes

u+G+treGHHfTtQ[hQ

La forma en que funciona:

u                 reduce
              [hQ     seed: the first element of input, in a list
                      iterable:
          tQ              all except the first element of input
        fT                remove if 0
                      lambda: G is the list to be returned, H is the current item
 +G                       append to return list
    reGH                  a range from the last element of the return list and the current item
   +                      concatenated with
        H                 the last item (this step forms a bidirectional inclusive list)

En otras palabras: todos los ceros se eliminan de la entrada, luego se inserta un rango exclusivo entre cada elemento. Este rango es de longitud cero en elementos solo uno aparte.

Cameron McCluskie
fuente
1

Vim: 231 comandos clave

Tenga en cuenta que cualquier ^ que precede a un carácter significa que debe mantener el control mientras escribe ese carácter

mbomayiwo^V^R"^V^V^V^X ^V^["sy0dd`a@f ^["bc0yiwo^V^V^V^X^V^R"^V^[0l@sa^V^V^V^A-^V^[0f-"ayhdd`a@i ^["dc0mbyiwo^V^R"Exe@b^V^[0fel"ty2ldd`b@t ^["ec0wmbyiwo@f @d^V^[@z ^["fc0"xyiwwmbyiwocw^V^V^V^Rx^V^V^V^[@a@i @e^V^[@z ^["ic0IB0 B^V^R" ^V^OWB0 ^V^OA B0^V^[0*w"tyiWdd`b@t ^["zd0dd`bAe^[0@e 

¡Pasos para que puedas ejecutar esto también!

  1. Copia la línea en Vim
  2. Escriba :s/\^V/<Ctrl-V><Ctrl-V>/gy presione Intro (los dos s deberían darle un ^ V azul)
  3. Escriba :s/\^R/<Ctrl-V><Ctrl-R>/gy presione Intro (debería ver azul ^ Rs ahora)
  4. Escriba :s/\^X/<Ctrl-V><Ctrl-X>/gy presione Intro (debería ver las ^ Xs azules ahora)
  5. Escribe :s/\^O/<Ctrl-V><Ctrl-O>/gy presiona enter
  6. Escribe :s/\^A/<Ctrl-V><Ctrl-A>/gy presiona enter
  7. Escriba :s/\^\[/<Ctrl-V><Ctrl-[>/gy presione Intro (este comando es ligeramente diferente porque necesitaba escapar del [)
  8. Tipo 0"yy$. El comando ahora está almacenado en el registro y
  9. Configure la entrada en una línea y corra con @y

Si alguien conoce una mejor manera de compartir el comando, hágamelo saber. Sé que esto es largo, pero es lo mejor que se me ocurrió.

De entrada y salida

La cadena de entrada debe estar sola en cualquier línea del archivo. 1 0 0 4 3 0 0 0 7

La salida simplemente sobrescribirá la cadena de entrada 1 2 3 4 3 4 5 6 7

Explicación

Algoritmo

  1. Comience en un número distinto de cero, asegúrese de que no sea el último número
  2. Encuentra el siguiente número distinto de cero
  3. Toma su diferencia. Si la respuesta es negativa, debe disminuir para reparar el rango; de lo contrario, incremente para reparar el rango.
  4. Regrese al primer carácter y reemplace cada cero incrementando / decrementando el número anterior.
  5. Repita hasta llegar al último personaje.

Macros utilizadas

@e: compruebe el final. El último número tendrá una e adjunta. Si el número debajo del cursor tiene una e al final, elimine la e y detenga la ejecución. De lo contrario, comience un ciclo de interpolación con @b.

mbyiwo^R"Exe@b^[0fel"ty2ldd`b@t

@b - Comienza el ciclo de interpolación. Guarde el número debajo del cursor para una operación de resta (@s) y luego encuentre el siguiente término distinto de cero (@f)

mayiwo^R"^V^X ^["sy0dd`a@f

@s: almacena el comando de resta para usar en @d. Es simplemente (val)^Xdónde (val)está el número al comienzo del paso de interpolación. Esto se establece mediante el comando @b.

@f - Encuentra el siguiente término distinto de cero. Escriba el valor actual en el registro sin nombre, luego escriba @f @den la línea siguiente y luego ejecute @z. Esto repetirá este comando si el número es cero y ejecutará @d si no lo es.

wmbyiwo@f @d^[@z

@z: ejecución condicional si el registro sin nombre es 0. Este comando espera dos comandos en una nueva línea en el formato command1 command2. Si el registro sin nombre es 0, command1se ejecuta, de lo contrario command2se ejecuta. Tenga en cuenta que ninguno de los comandos puede tener espacios.

 IB0 B^R" ^OWB0 ^OA B0^[0*w"tyiWdd`b@t`

@t: registro de comando temporal. Almacena varios comandos por un corto tiempo antes de ejecutarlos. Se usa principalmente en declaraciones if.

@d: determina la dirección de interpolación. Resta el primer número de la secuencia del número debajo del cursor (usando @s). Si el resultado es negativo, la interpolación debe disminuir para que ^ X se guarde en @a. De lo contrario, deberíamos incrementar para que ^ A se guarde en @a. Una vez guardado esto, retroceda al comienzo de este ciclo de interpolación y ejecute @i para interpolar realmente

yiwo^V^X^R"^[0l@sa^V^A-^[0f-"ayhdd`a@i

@a: almacena ^Ao ^Xpara incrementar o disminuir durante el paso de interpolación. Esto se establece mediante el comando @d.

@i - Interpolar. Copie el número en la ubicación actual a @x y pase al siguiente número. Si ese número es cero, reemplácelo con @x y ejecute @a para modificarlo correctamente hacia arriba o hacia abajo, luego repita este comando. Si el número no es cero, hemos llegado al final de este ciclo de interpolación. Se debe comenzar uno nuevo con este número como principio, así que ejecute @e para verificar el final y vuelva a ejecutar.

"xyiwwmbyiwocw^V^Rx^V^[@a@i @e^[@z

@x: registro de almacenamiento temporal. Utilizado en el comando interpolar (@i)

Desglosando las pulsaciones del teclado

mbo :Set b mark to current position and open a new line below to write macros
mayiwo^V^R"^V^V^V^X ^V^["sy0dd`a@f ^["bc0 :Write to @b and reset line

yiwo^V^V^V^X^V^R"^V^[0l@sa^V^V^V^A-^V^[0f-"ayhdd`a@i ^["dc0 :Write to @d and reset line

mbyiwo^V^R"Exe@b^V^[0fel"ty2ldd`b@t ^["ec0 :Write to @e and reset line

wmbyiwo@f @d^V^[@z ^["fc0 :Write to @f and reset line

"xyiwwmbyiwocw^V^V^V^Rx^V^V^V^[@a@i @e^V^[@z ^["ic0 :Write to @i and reset line

IB0 B^V^R" ^V^OWB0 ^V^OA B0^V^[0*w"tyiWdd`b@t ^["zd0 :Write to @z and reset line

dd`b :Delete this line and move cursor back to original line

Ae^[ :Append an e to the last number

0@e  :Move to the beginning of the line and run
Dominic A.
fuente
0

Python 3.5, 159 bytes

una solución recursiva

def f(s):
 h=s[0]
 g=lambda s,h,v:h*(h[-1]==s[0])if len(s)==1else(g(s[1:],h+[h[-1]-v],-v)+g(s[1:],h+[h[-1]+v],+v))*(s[0]==0 or h[-1]==s[0])
 return g(s,[h],1)

Sin golf

def f(s):
    h=s[0]
    def g(s,h,v):
        if len(s)==1:
            if h[-1]!=s[0]:
                r=[]
            else:
                r=h
        else:
            if s[0]==0:
                r=g(s[1:],h+[h[-1]+v],v)
            elif h[-1]!=s[0]:
                r=[]
            else:
                r=g(s[1:],h+[h[-1]-v],-v)+g(s[1:],h+[h[-1]+v],+v)
        return r
return g(s,[h],1)

En la solución de golf, reemplazo las condiciones usando el hecho de que h*True=hyh*False=[]

Resultado

>>> f([7, 6, 0, 0, 3, 0, 0, 0, 7, 0, 5])
[7, 6, 5, 4, 3, 4, 5, 6, 7, 6, 5]
Erwan
fuente
0

Perl 6 , 54 bytes

{$_=$^a;1 while s/:s(\d+) 0 + (\d+)/{+~$0...+~$1}/;$_}
smls
fuente
0

MATLAB, 39 38 37 bytes

@(a)interp1(find(a),a(a>0),find(a/0))

Función anónima que interpola linealmente entre los puntos en a. find(a)es una matriz de índices de elementos distintos de cero en ay a(a>0)son los valores positivos. Guardado 1 byte gracias a la sugerencia de un amigo en >lugar de ~=.

MattWH
fuente