Riffle de matriz generalizada

22

¡Un simple golf para comenzar la semana! Te dan tres matrices: la matriz base B , la matriz de valor V y la matriz de índice I . Debe producir otra matriz donde los valores de Vse inserten en Blos índices especificados por I. Aquí hay un ejemplo:

Base:    [5, 1, 4, 1, 3]
Values:  [0, 0, 7]
Indices: [5, 0, 3]

Los índices apuntan a las siguientes posiciones en la matriz base:

[ 5, 1, 4, 1, 3 ]
 ^        ^    ^
 0        3    5

Entonces, al insertar los elementos correspondientes de la matriz de valores, el resultado debería ser:

[0, 5, 1, 4, 7, 1, 3, 0]

Reglas

Puede escribir un programa o función, tomando la entrada a través de STDIN (o la alternativa más cercana), argumentos de línea de comando o argumentos de función y generando el resultado a través de STDOUT (o la alternativa más cercana), el valor de retorno de la función, o modificando la matriz dada como Bparámetro .

Si su envío es una función, Iy Vpuede modificarse de cualquier manera, así como Bsi no se usa para la salida.

Puede hacer los siguientes supuestos sobre la entrada:

  • Todos los elementos de la base y la matriz de valores serán enteros no negativos.
  • La matriz de valores tendrá como máximo un elemento más que la matriz base.
  • La matriz de valores y la matriz de índice tendrán el mismo número de elementos.
  • La matriz de índice no contendrá índices repetidos, y todos los índices estarán dentro del rango.
  • Las matrices de base y valor pueden contener elementos repetidos.
  • Cualquiera o todas las matrices pueden estar vacías.
  • No debe suponer que los índices se dan en un orden particular.
  • Puede recibir entradas y producir salidas en cualquier formato de cadena o lista conveniente y sin ambigüedades. También puede elegir recibir las tres matrices en un orden diferente.
  • Puede elegir entre indexación basada en 0 y basada en 1.

Este es el código de golf, por lo que gana la respuesta más corta (en bytes).

Casos de prueba

Dado en el formato B V I => Resultpara indexación basada en 0. Si está utilizando la indexación basada en 1, incremente los elementos de la tercera matriz en 1.

[] [] [] => []
[] [1] [0] => [1]
[1,2] [] [] => [1,2]
[1,2] [3] [0] => [3,1,2]
[1,2] [3] [1] => [1,3,2]
[1,2] [3] [2] => [1,2,3]
[0,0,0] [1,1,1,1] [0,1,2,3] => [1,0,1,0,1,0,1]
[5,1,4,1,3] [0,0,7] [5,0,3] => [0,5,1,4,7,1,3,0]
[1,2,3,4] [4,3,2,1] [4,0,3,1] => [3,1,1,2,3,2,4,4]

Avíseme si se encuentra con otros casos interesantes y los agregaré.

Tabla de clasificación

Aquí hay un fragmento de pila para generar una tabla de clasificación regular y una descripción general de los ganadores por idioma.

Para asegurarse de que su respuesta se muestre, comience con un título, utilizando la siguiente plantilla de Markdown:

# Language Name, N bytes

¿Dónde Nestá el tamaño de su envío? Si mejora su puntaje, puede mantener los puntajes antiguos en el título, tachándolos. Por ejemplo:

# Ruby, <s>104</s> <s>101</s> 96 bytes

Mostrar fragmento de código

code-golf array-manipulation Martin Ender
fuente
44
¿Cómo te sientes acerca NULLde una matriz vacía para idiomas donde está una matriz vacía NULL?
Alex A.
@AlexA. Si se trata de un común / la representación de la matriz vacía en dicho idioma (s), estoy bien con eso.
Martin Ender
3
¿Un simple golf ? Eso es lo más difícil que hice en CJam toda la semana. : P
Dennis

Respuestas:

13

Pyth, 14 bytes

s.icFPQmedSCtQ

Demostración.

Este programa toma las entradas como 3-tuplas de listas en el orden Base, Índices, Valores.

Explicación sobre el ejemplo [5, 1, 4, 1, 3], [5, 0, 3], [0, 0, 7]:

  1. Tome la entrada: implícita, Q es la entrada.

  2. Hacer el índice, pares de valores: CtQ=[(5, 0), (0, 0), (3, 7)]

  3. Ordenar los pares en orden de índice creciente: SCtQ=[(0, 0), (3, 7), (5, 0)]

  4. Saque el valor de cada par: medSCtQ=[0, 7, 0]

  5. Dividir la lista base en la ubicación de las indicaciones: cFPQ=[[], [5, 1, 4], [1, 3], []]

  6. Intercalar 3 y 4: .icFPQmedSCtQ=[[], 0, [5, 1, 4], 7, [1, 3], 0, []]

  7. Combinar en una lista: s.icFPQmedSCtQ=[0, 5, 1, 4, 7, 1, 3, 0]

isaacg
fuente
Maldita sea. ¿Desde cuándo tenemos un método de intercalación? Solo quería publicar ssC,cFPQamedSCtQ].
Jakube
55
@Jakube isaac lo cometió furtivamente hace 6 días.
orlp
@Jakube Since github.com/isaacg1/pyth/commit/…
isaacg
3
@Jakube ya que Pyth puede crecer para resolver cualquier problema. Ese es el problema con los idiomas de golf. Las lenguas esotéricas existen por el bien de las lenguas esotéricas; tal como están diseñados * después.
sentiao
@sentiao Para ser justos, el lenguaje anfitrión (Python) se ha intercalado con un nombre diferente por un tiempo.
Mego
16

Pitón 2, 54

lambda B,*X:map(B.insert,*zip(*sorted(zip(*X))[::-1]))

Toma entrada como B,I,V. Modifica la entrada Bcuando se llama (gracias a Martin Büttner por recordarme que esto es posible).

Utiliza mappara llamar B.inserta cada par índice / elemento. Para evitar el problema de que los índices de la lista cambien a medida que se insertan los elementos, ordena los pares en orden decreciente de índice mediante un archivo zip / sort / unzip feo. Si no fuera por el problema cambiante, podríamos hacerlo map(B.insert,*X).

Método antiguo (65):

B,V,I=input()
for i,v in sorted(zip(I,V))[::-1]:B[i:i]=v,
print B
xnor
fuente
5

Haskell, 62 bytes

import Data.List
f b v i=map snd$sort$zip[0.5,1.5..]b++zip i v

Ejemplo de uso: f [5,1,4,1,3] [0,0,7] [5,0,3]-> [0,5,1,4,7,1,3,0].

Cómo funciona: aumente la lista base con índices de "y media" que comiencen en 0.5(p [(0.5,5),(1.5,1),(2.5,4),(3.5,1),(4.5,3)]. Ej. ) Y concatene con los pares índice-valor. Ordenar y descartar el índice.

Observación : no sé si estoy haciendo trampa aquí. Desde un punto de vista matemático está bien, pero un programador podría argumentar que la lista de índices [5,0,3]no es una lista de Integerslo solicitado, sino una lista de Fractionals(para ser exactos, el tipo es polimórfico, pero debe pertenecer a la Fractionalclase, por ejemplo Floato Double)

nimi
fuente
5

Ruby, 60 59 53 bytes

->a,b,c{c.zip(b).sort.reverse.map{|i,v|a.insert i,v}}

Y la versión sin golf

def riffle(array, values, indices)
    indices.zip(values).sort.reverse.each do |index, value|
        array.insert(index, value)
    end
end
Dylan Frese
fuente
2
Puede acortar este por lo que es una función sin nombre en su lugar: ->a,b,c{...}. También es probable insertque no necesite paréntesis.
Martin Ender
@ MartinBüttner Sabía sobre la función sin nombre con la lambda, pero no sentí que fuera el espíritu del desafío (que generalmente pide una función con nombre). Gracias por ver a los padres, sin embargo.
Dylan Frese
A menos que el desafío solicite específicamente una función con nombre , las funciones sin nombre siempre son aceptables . Y no pedí una función con nombre (nunca lo hago).
Martin Ender
5

CJam, 34 23 18 bytes

{.\2/\ee+{0=}$1f=}

Mi primera presentación de CJam. Los consejos son bienvenidos, estoy seguro de que hay mucho para jugar al golf.

16 bytes guardados con la ayuda de @ MartinBüttner y @Dennis.

Función que espera entrada en la pila en orden B V I(I es la más alta).

Ejemplo de uso:

[5 1 4 1 3] [0 0 7] [5 0 3] {.\2/\ee+{0=}$1f=}~

Método:

  • emparejar el ielemento th de la matriz coni+0.5
  • emparejar valores de inserción con posiciones de inserción
  • fusionar las dos matrices resultantes
  • ordenar matriz basada en elementos de posición
  • mantener elementos de valor
randomra
fuente
Ese enfoque de coma flotante es muy inteligente y (lamentablemente) mejor que el mío. Puede obtener hasta 19 bytes con q~.5fm.\2/\ee+$1f=py hasta 18 bytes utilizando una función anónima:{.5fm.\2/\ee+$1f=}
Dennis
La misma idea sin el truco de punto flotante: {.\2/\ee+{0=}$1f=}(todavía 18 bytes)
Dennis
@ Dennis Gracias, no pude encontrar el get array elementoperador para 1f=. Sin embargo, lo dejaré como un programa completo.
randomra
Tu llamada. ¿Te molesta que te pregunte por qué te opones a publicar una función?
Dennis
@Dennis Acabo de comenzar CJam y no estaba seguro de cómo usar las funciones. Ahora lo descubrí, así que cambié la respuesta a eso.
randomra
5

K, 22 21 bytes

{,//+(y@<z;(z@<z)_ x)}

Definimos una función de 3 argumentos {…}con las variables implícitas x, yy que zrepresentan la lista inicial, la lista de valores y la lista de índice, respectivamente. El operador "cortar" ( _) se utiliza para dividir la lista de inicio en la lista ordenada de los índices dados ( (z@<z)). Intercalamos valores (después de ordenarlos de manera correspondiente) con los fragmentos divididos de la matriz original formando una lista ( (a;b)), tomando su transposición ( +) y allanando el resultado ( ,//).

Ejemplo de uso:

  f:{,//+(y@<z;(z@<z)_ x)}
{,//+(y@<z;(z@<z)_ x)}

  f[1 2 3 4;4 3 2 1;4 0 3 1]
3 1 1 2 3 2 4 4

  f[5 1 4 1 3;0 0 7;5 0 3]
0 5 1 4 7 1 3 0

Los espacios alrededor del guión bajo son necesarios porque K permite los guiones bajos en los identificadores. K5 elimina esta ambigüedad potencial. Si pudiéramos contar con los índices en orden ascendente y los guiones bajos no fueran identificadores válidos, podríamos usar el programa de 13 bytes, mucho más agradable:

{,//+(y;z_x)}

(suspiro.)

editar:

{,//+(y@<z;(z@<z)_ x)} / before
{,//+(y@<z;z[<z]_ x)}  / after

Rompe la simetría, pero podemos guardar un byte mediante el uso de la indexación de paréntesis ( […]) en lugar del @operador de indexación infijo . Por lo general, esto hace que los programas sean más largos, pero en este caso necesitamos parens de todos modos para ordenar zantes de realizar el corte.

JohnE
fuente
4

Pyth, 17 bytes

ssC,cFPQamedSCtQ]

@isaacg ya superó mi solución. Pero como terminé mi documentación, de todas formas la publicaré.

Esto toma la entrada en el formato B, I, V. Puedes probarlo aquí: Demostración o Test Suite

Explicación:

Estoy usando el ejemplo B = [5,1,4,1,3], I = [5,0,3], V = [0,0,7]del OP.

                    implicit: Q = input()
      PQ            all elements but last of Q   => [[5,1,4,1,3], [5,0,3]]
    cF              split B it the indices in I  => [[], [5,1,4], [1,3], []]

              tQ    all elements but first of Q  => [[5,0,3], [0,0,7]]
             C      zip                          => [(5,0), (0,0), (3,7)]
            S       sort                         => [(0,0), (3,7), (5,0)]
         med        extract the end of each pair => [0,7,0]
        a       ]   append an empty list         => [0,7,0,[]]

   ,                create a pair => ([[], [5,1,4], [1,3], []], [0,7,0,[]])
  C                 zip           => [([],0), ([5,1,4],7), ([1,3],0), ([],[])]
 s                  sum           => ([],0,[5,1,4],7,[1,3],0,[],[])
s                   sum           => [0,5,1,4,7,1,3,0]
Jakube
fuente
4

JavaScript (ES6), 75

Una función con 3 parámetros de matriz, que devuelve una matriz. Extrañamente, esta función modifica su iparámetro (según lo permitido por OP)

Pruebe a ejecutar el fragmento, Firefox solo como de costumbre. 

f=(b,v,i,j=0)=>b.concat(v).map(p=>(p=i.indexOf(j))<0?b[j++]:(i[p]=-1,v[p]))

// TEST
out=x=>O.innerHTML+=x+'\n'

test=[
{ b:[], v:[], i:[], k:[] },
{ b:[], v:[1], i:[0], k:[1] },
{ b:[1,2], v:[], i:[], k:[1,2] },
{ b:[1,2], v:[3], i:[0], k:[3,1,2] },
{ b:[1,2], v:[3], i:[1], k:[1,3,2] },
{ b:[1,2], v:[3], i:[2], k:[1,2,3] },
{ b:[0,0,0], v:[1,1,1,1], i:[0,1,2,3], k:[1,0,1,0,1,0,1] },
{ b:[5,1,4,1,3], v:[0,0,7], i:[5,0,3], k:[0,5,1,4,7,1,3,0] },
{ b:[1,2,3,4], v:[4,3,2,1], i:[4,0,3,1], k:[3,1,1,2,3,2,4,4] }
];

test.forEach(x=>{
  r = f(x.b,x.v,x.i.slice(0)) // pass a copy of i, as the function will alter it
  ok = ''+r==''+x.k
  s='Test ' + (ok?'OK':'FAIL')
  +'\n B ['+x.b
  +']\n V ['+x.v
  +']\n I ['+x.i
  +']\n Result ['+r
  +']\n Check  ['+x.k
  +']\n'
  out(s)
  
})
<pre id=O></pre>
Expandir fragmento

edc65
fuente
Por curiosidad, ¿qué pasa con el código que lo hace específico para Firefox? ¿Es porque es ES6?
Alex A.
@ AlexA.Es porque es ES6, sí. Particularmente, fat arrow functionno se implementa incluso en la versión de desarrollador de Chrome (AFAIK)
edc65
De hecho, ni siquiera la versión canaria de Chrome lo admite.
DocMax
4

Mathematica, 52 51 bytes

Last/@(Tr@#2->#&~MapIndexed~#⋃Thread[#3+.5->#2])&

Ejemplo:

In[1]:= f = Last/@(Tr@#2->#&~MapIndexed~#⋃Thread[#3+.5->#2])&;

In[2]:= f[{5, 1, 4, 1, 3}, {0, 0, 7}, {5, 0, 3}]

Out[2]= {0, 5, 1, 4, 7, 1, 3, 0}

Explicación:

Usando el ejemplo anterior.

  • Tr@#2->#&~MapIndexed~# => {1 -> 5, 2 -> 1, 3 -> 4, 4 -> 1, 5 -> 3}
  • Thread[#3+.5->#2] => {5.5 -> 0, 0.5 -> 0, 3.5 -> 7}
  • Luego tome la unión (ordenada) de estas dos listas. (=> {0.5 -> 0, 1 -> 5, 2 -> 1, 3 -> 4, 3.5 -> 7, 4 -> 1, 5 -> 3, 5.5 -> 0})
  • Y luego toma el último elemento de cada par. (=> {0, 5, 1, 4, 7, 1, 3, 0})
alephalpha
fuente
3

CJam, 30 29 bytes

q~.\2/$z~0@+2ew@f{\~@<>}.\e_p

Esto es demasiado largo Siento que esto no es una presentación de lenguaje de golf: |

Pruébalo en línea aquí

Optimizador
fuente
3

R, 75 bytes

function(b,v,i){n=b;j=0;for(g in v)n=append(n,g,i[j<-j+1]+sum(i<i[j])-1);n}

Esto crea una función sin nombre. Para llamarlo, dale un nombre, por ejemplo f=function.... Tenga en cuenta que las matrices deben estar indexadas en 1 porque así es como R rueda.

Ungolfed + explicación:

f <- function(b, v, i) {
    # Initialize the output vector to b
    n <- b

    # Initialize an index over the indices
    j <- 0

    # Loop over the values to insert
    for(g in v) {
        # Get the index of the next given insertion index
        j <- j + 1

        # Insert g into n.
        # The position at which to insert the value is determined by
        # adding the number of indices less than the current one and
        # subtracting 1. The subtraction is because we're using the
        # `after` argument in the `append` function.

        n <- append(n, g, i[j] + sum(i < i[j]) - 1)
    }

    # Return n
    n
}

Ejemplos:

> f(c(), c(), c())
[1] NULL

> f(c(0, 0, 0), c(1, 1, 1, 1), c(1, 2, 3, 4))
[1] 1 0 1 0 1 0 1

> f(c(5, 1, 4, 1, 3), c(0, 0, 7), c(6, 1, 4))
[1] 0 5 1 4 7 1 3 0

¡Las sugerencias son bienvenidas como siempre!

Alex A.
fuente
2

CJam, 19 bytes

l~_,)N*q~.{t}~.\N-p

Este es un programa completo que lee las matrices B , I y V (una por línea, en ese orden) de STDIN.

Pruébelo en línea en el intérprete de CJam .

Cómo funciona

l~    e# Evaluate the first line of input.
_,)   e# Compute the array length and add 1.
N*    e# Push a string of that many linefeeds.
q~    e# Evaluate the remaining input.
.{t}~ e# Vectorized array set: for each index in the array from line 2, replace the
      e# LF at that index by the corresponding element of the array from line 3.
.\    e# Interleave the two arrays on the stack.
N-    e# Remove the linefeeds.
p     e# Print.

CJam, 20 bytes

{Qa+@@.{a2$2$=+t}e_}

Esta es una función anónima que muestra B , V e I (de arriba a abajo) de la pila y, a cambio, deja una sola matriz en la pila.

Pruébelo en línea en el intérprete de CJam .

Cómo funciona

Qa+      e# Append [[]] to B.
@@       e# Rotate V and I on top of B.
.{       e# For each v in V and the corresponding i in I:
   a     e#     Push [v].
   2$2$= e#     Retrieve b := B[i].
   +     e#     Append to push [v b].
         e#     The stack now consists of: B i [v b]
   t     e#     Set B[i] := [v b].
}        e#
e_       e# Flatten B.
Dennis
fuente
1

Ruby, 48 bytes

Creo que esto cumple con las reglas, pero por favor verifique.

->b,v,i{l=-1;i.map{|j|b[j]=[v[l+=1],b[j]]};b*?:}

Función sin nombre que toma las tres matrices como entrada. Emite una cadena que se puede analizar sin ambigüedades en una matriz de números con la expresión ruby x.split(/:+/).map(&:to_i).

Casos de prueba en ideona .

Podría ahorrar 3 bytes más, pero el formato de salida [1,2,[nil,5]]está extendiendo las reglas un poco demasiado mych imo, aunque no es ambiguo.

blutorange
fuente
Creo que el formato actual está bien. Las matrices anidadas con nilvalores de entrelazado son un poco exageradas. Pero en cualquier caso, esto no está ganando el concurso, por lo que no estoy realmente preocupado por eso de ninguna manera.
Martin Ender
1

R, 60

Como una función sin nombre que toma b, v e i

function(b,v,i){e=c(NA,rbind(b,NA));e[i*2+1]=v;e[!is.na(e)]}

Expande b con NA Llena los huecos donde se requiere con v Devuelve el vector sin NA

> f=function(b,v,i){e=c(NA,rbind(b,NA));e[i*2+1]=v;e[!is.na(e)]}
> f(c(), c(), c())
logical(0)
> f(c(0, 0, 0), c(1, 1, 1, 1), c(0, 1, 2, 3))
[1] 1 0 1 0 1 0 1
> f(c(5, 1, 4, 1, 3), c(0, 0, 7), c(5, 0, 3))
[1] 0 5 1 4 7 1 3 0
MickyT
fuente
1

Java, 253, 226, 219, 209

No es exactamente un ganador, pero bueno.

Suponiendo que B, V y yo no somos nulos. v (v minúscula) es la longitud de las matrices de valores / indicaciones. R es la matriz devuelta. r es la longitud de la matriz devuelta. x, y, y yo somos todos ints temporales.

int[]f(int[]B,int[]V,int[]I){int v=V.length,r=B.length+v,x,y,i;int[]R=java.utils.Arrays.copyOf(B,r);for(x=0;x<v;x++){i=I[x];for(y=0;y<x;y++)if(I[x]>I[y])i++;for(y=r-2;y>=i;y--)R[y+1]=R[y];R[i]=V[x];}return R;}

expandido:

int[]f( int[] B, int[] V, int[] I ) {
    int v = V.length, //length of Values
        r = B.length + v, //length of the result
        x, y, i; //temps
        int[] R = java.utils.Arrays.copyOf( B, r );       
        for( x = 0; x < v; x++ ) {
        i = I[x];
        for( y = 0; y < x; y++ )
            if( I[x] > I[y] )
                i++;
        for( y = r - 2; y >= i; y-- )
            R[y+1] = R[y];
        R[i] = V[x];
    }
    return R;
}
Jack munición
fuente
1

APL, 22 bytes

{(∊⌽2↑⍵)[⍋(2⊃⍵),⍳≢⊃⍵]}

En ⎕IO ← 0 para que coincida con los casos de prueba.

Es un algoritmo estándar: el vector índice del primer argumento se agrega a los índices dados (tercer argumento). ⍋calcula la permutación que ordenaría los índices en orden ascendente. Dado que el algoritmo de clasificación de APL es estable por definición, la permutación calculada coloca el elemento de la cateación del segundo y primer argumento en el lugar correcto.

Por ejemplo :

    {(∊⌽2↑⍵)[⍋(2⊃⍵),⍳≢⊃⍵]}(5 1 4 1 3)(0 0 7)(5 0 3)
0 5 1 4 7 1 3 0
lstefano
fuente