Encuentre dos enteros de una lista desordenada para sumar a la entrada

13

Esta es una pregunta de la entrevista de Google, vea aquí un enlace de YouTube.

La tarea:

Encuentre 2 enteros de una lista desordenada que sumen a un entero dado.

  1. Dada una lista desordenada de enteros, encuentre 2 enteros que sumen un valor dado, imprima estos 2 enteros e indique el éxito (salida 0). No necesitan ser números particulares (es decir, los primeros 2 enteros que suman el número correcto), cualquier par que sume al valor funcionará.
  2. un entero es positivo y mayor que cero.
  3. una lista de enteros puede estar en cualquier estructura de datos, incluido un archivo de enteros, un entero por línea.
  4. Si no se pueden encontrar enteros, indique una falla (salida 1).
  5. deben devolverse dos enteros en diferentes posiciones en la lista. (es decir, no puede devolver el mismo número desde la misma posición dos veces)

(Nota: en el video, estos no son exactamente los requisitos. El 'entrevistador' cambió sus múltiples veces).

p.ej.

sum2 8 <<EOF
1
7
4
6
5
3
8
2
EOF

Imprime 3y el 5estado de salida es 0. Tenga en cuenta que en esto 1,7y 2,6también se permitirían resultados.

sum2 8 <<EOF
1
2
3
4

Devuelve el estado de salida 1 ya que no hay combo posible. 4,4no está permitido, según la regla 5.

philcolbourn
fuente
15
Esta podría haber sido una gran pregunta si hubiera tenido la oportunidad de sacudir algunos de los cabos sueltos en el Sandbox primero. Por ejemplo, para algo como esto, esperaría escribir una función que devolviera un valor falso o un par de números.
Neil
2
En el ejemplo, ¿por qué el par devuelto es (3,5) y no (1,7)?
Rod
44
¿Cómo puede haber un "primer" par en una lista desordenada? Eso es inherentemente contradictorio.
Peter Taylor
23
Realmente no creo que la cosa de salida 0 / salida 1 sea una buena idea. Muchos idiomas no pueden existir fácilmente así, y generalmente se permite salir con un error (es decir, ignorar STDERR) Muchos idiomas de golf ni siquiera tienen una forma fácil de salir por código de salida, creo
R
2
Pensándolo bien, algunas respuestas se han esforzado para producir el código de salida 1, por lo que puede ser mejor no cambiar los requisitos ahora
Luis Mendo

Respuestas:

5

Bash, 84 bytes

Mi implementación de (aproximadamente) la solución del ingeniero de Google pero usando bash y un flujo de entrada, no es mi solución, por lo que esto no cuenta.

while read V;do((V<$1))&&{ ((T=R[V]))&&echo $T $V&&exit;((R[$1-V]=V));};done;exit 1

Método

mientras que podemos leer el entero V del flujo de entrada si es inferior al objetivo $ 1, si ya se ha visto $ 1-V, imprimir $ 1-V y V y salir 0 (de lo contrario) guardar el candidato para la entrada $ 1-V salida 1

philcolbourn
fuente
4

Brachylog , 9 bytes

h⊇Ċ.+~t?∧

Pruébalo en línea!

Asumiendo que entendí el desafío correctamente ...

Explicación

h⊇Ċ          Ċ ('couple') has two elements, and is a subset of the head of the input
  Ċ.         Output = Ċ
   .+~t?     The sum of the elements of the Output is the tail of the Input
        ∧    (disable implicit unification)
Fatalizar
fuente
4

Perl 6 , 59 bytes

$_=get;put lines().combinations(2).first(*.sum==$_)//exit 1

Pruébalo
Pruébalo sin resultado posible

Expandido:

$_ = get;            # get one line (the value to sum to)

put                  # print with trailing newline
    lines()          # get the rest of the lines of input
    .combinations(2) # get the possible combinations
    .first(          # find the first one
      *.sum == $_    # that sums to the input
    )
  //                 # if there is no value (「Nil」)
    exit 1           # exit with a non-zero value (「put」 is not executed)
Brad Gilbert b2gills
fuente
4

JavaScript ES6, 58 70 68 64 bytes

a=>b=>{for(i in a)if(a.includes(b-a[i],i+1))return[a[i],b-a[i]]}

Devuelve un par de números en forma de matriz si se encuentra; de lo contrario undefined, devuelve un valor falso.

f=a=>b=>{for(i in a)if(a.includes(b-a[i],i+1))return[a[i],b-a[i]]}

console.log(f([1,7,4,6,5,3,8,2])(8));
console.log(f([1,2,3,4,5,6,7,8])(8));
console.log(f([1,2,3,4])(8));
console.log(f([2,2])(4));

Tom
fuente
El ejemplo fue 3, 5pero esto genera 1, 7...
Neil
@Neil, lo siento, he modificado las reglas porque me equivoqué. 1,7 está bien.
philcolbourn
1
¿No funcionará f([2,2] 4)?
Cliffroot
1
@cliffroot debería funcionar para ese caso ahora
Tom
1
Buen includestruco
Neil
4

JavaScript (ES6), 61 57 56 bytes

Toma la matriz de enteros ay la suma esperada sen la sintaxis de curry (a)(s). Devuelve un par de enteros coincidentes como una matriz, o undefinedsi no existe dicho par.

a=>s=>(r=a.find((b,i)=>a.some(c=>i--&&b+c==s)))&&[r,s-r]

Formateado y comentado

a =>                      // given an array of integers (a)
  s => (                  // and an expected sum (s)
    r = a.find((b, i) =>  // look for b at position i in a such that:
      a.some(c =>         //   there exists another c in a:
        i-- &&            //     - at a different position
        b + c == s        //     - satisfying b + c == s
      )                   //   end of some()
    )                     // end of find(): assign the result to r
  ) &&                    // if it's not falsy:
  [r, s - r]              // return the pair of integers

Prueba

Arnauld
fuente
3

Jalea , 14 bytes

ŒcS=⁹$$ÐfḢṄo⁶H

Pruébalo en línea!

Esta es una función (no un programa completo) que sale a la salida estándar. (El enlace TIO tiene un contenedor que ejecuta una función y no tiene en cuenta su valor de retorno).

Este programa podría ser 4 bytes más corto si no fuera por el requisito del código de salida; devolver un código de salida de 1 en Jelly es bastante difícil. (Es posible que haya una forma más tersa de hacer esto que he echado de menos).

Explicación

ŒcS=⁹$$ÐfḢṄo⁶H
Œc                All pairs of values from {the first argument}
       Ðf         Take only those which
  S=⁹               sum to {the second argument}
     $$           Parse the preceding three builtins as a group
         Ḣ        Take the first result (0 if there are no results)

          Ṅ       Output this result (plus a newline) on standard output
           o⁶     If this value is falsey, replace it with a space character
             H    Halve every element of the value

Podemos reducir a la mitad todos los enteros de un par, así o⁶Hque no hará nada si encontramos un resultado, aparte de devolver un valor de retorno inútil que de todos modos no es relevante ( sirve como un método conveniente de un solo byte para determinar el retorno de la función valor temprano, bajo las reglas PPCG). Sin embargo, si no encontramos un resultado, terminamos tratando de reducir a la mitad un carácter espacial, una operación tan insignificante que hace que el intérprete de Jelly se bloquee. Afortunadamente, este bloqueo produce un código de salida de 1.


fuente
3

Perl 5 , 51 bytes

46 bytes de código + para 5 bytes para -plibanderas.

$\="$_ $v"if$h{$v=$^I-$_};$h{$_}=1}{$\||exit 1

Pruébalo en línea!

La idea es iterar en la lista de entrada: en un número x( $_), si previamente vimos n-x( $^I-$_), entonces encontramos lo que estábamos buscando y establecemos $\estos dos valores ( "$_ $v"). Al final, si $\no está configurado, entonces nosotros exit 1, de lo contrario, se imprimirá implícitamente.

Dada
fuente
¿Funciona una pestaña literal en lugar de los dos caracteres ^I?
@ ais523 Parece que no puedo. Sin embargo, tal vez fue posible en versiones anteriores de Perl.
Dada
3

Röda , 60 56 bytes

f s,a{seq 1,s|{|x|[[x,s-x]]if[x in a,s-x in a-x]}_|pull}

Pruébalo en línea!

Este código arroja un error si no hay respuesta. Genera todos los pares posibles que pueden formar la suma s, es decir. 1, s-1, 2, s-2, 3, s-3, ... A continuación, se comprueba si ambos números están en la matriz ay si es así, les empuja a la corriente. pulllee un valor de la secuencia y lo devuelve. Si no hay valores en la secuencia, arroja un error. a-xdevuelve la matriz acon xeliminado.

fergusq
fuente
3

Python 2, 60 bytes

Este breve, hasta que se aclaren las reglas para salir con el código 1. Ahora sale con error si no se encuentra nada.

-5 bytes gracias a @Peilonrayz

-4 bytes gracias a @Rod

Pruébalo en línea

a,s=input()
while a:
 x=a.pop()
 if s-x in a:r=s-x,x
print r
Zarigüeya muerta
fuente
@Peilonrayz No se dio cuenta de eso, ¡gracias!
Dead Possum
@Peilonrayz Esto violaría la quinta regla: deben devolverse dos enteros en diferentes posiciones de la lista. (es decir, no puede devolver el mismo número desde la misma posición dos veces)
Dead Possum
3
Puede usar espacios + pestañas para sangría mixta para reducir 2 bytes o cambiarinput() para reducir 4 bytes
Rod
@ Rod ¡Gracias! La entrada parece más agradable
Dead Possum
2
@Eric Duminil Sí. Es equivalente a eval(raw_input())(creo).
Yytsi
2

C ++ 133 bytes (compilado con clang 4 y gcc 5.3 -std = c ++ 14)

#include <set>
auto f=[](auto s,int v,int&a,int&b){std::set<int>p;for(auto i:s)if(p.find(i)==end(p))p.insert(v-i);else{a=v-i;b=i;}};

C 108 bytes

void f(int*s,int*e,int v,int*a,int*b){do{int*n=s+1;do if(v-*s==*n){*a=*s;*b=*n;}while(++n<e);}while(++s<e);}
em2er
fuente
1
Bienvenido al sitio! Desafortunadamente, creo que necesita agregar 15 bytes para #include <set>y algunos más para std::set. Aunque también puede guardar algunos bytes si elimina las llavesp.insert(v-i);
James
@DJMcMayhem oh, gracias. Entonces, ¿debería incluir main ()?
em2er
@ em2er No, no es necesario incluirlo main. Consideramos (a menos que se indique lo contrario en el desafío) que una función es una presentación válida. (¡bienvenido en el sitio por cierto!)
Dada
No, la presentación de una función está bien. (Y mucho más corto porque puede tomar la entrada como argumentos) Solo necesita contar cualquier inclusión que requiera su envío.
James
1
@DJMcMayhem @Dada muchas gracias! No estoy seguro con end, pero se compila en gcc sin std::(y configurado si no)
em2er
2

Haskell , 34 bytes

(n:v)#s|elem(s-n)v=(n,s-n)|1<2=v#s

Pruébalo en línea!

Para cada elemento de la lista, esta función verifica si (elemento-suma) está en la siguiente parte de la lista. Devuelve el primer par que encuentra. Si la función llega al final de la lista, arroja un error de "patrones no exhaustivos" y sale con el código 1.

León
fuente
Me temo que este enfoque no funciona para entradas como [2,2]#4.
Laikoni
@Laikoni Gracias, no había leído el desafío lo suficientemente bien. Esta nueva versión debería ser correcta (y más corta ^^)
Leo
2

PowerShell, 109 97 bytes

param($i,$a)($c=0..($a.count-1))|%{$c-ne($f=$_)|%{if($a[$f]+$a[$_]-eq$i){$a[$f,$_];exit}}};exit 1

Tomó un acuerdo de 12 bytes que AdmBorkBork ofreció

Explicación

# Get the parameter passed where $i is the addition target from the array of numbers in $a
param($i,$a)

($c=0..($a.count-1))|%{
    # We are going to have two loops to process the array elements.
    # The first loop element will be held by $f
    $f=$_
    # Create a second loop that will be the same as the first except for the position of $f to
    # prevent counting the same number twice. 
    $c|?{$_-ne$f}|%{
        # Check if the number at the current array indexes add to the target value. If so print and exit.
        if($a[$f]+$a[$_]-eq$i){$a[$f],$a[$_];exit}        
    }

}
# If nothing was found in the loop then we just exit with error.
exit 1

Las reglas actuales buscan el código de salida que hace esto. Esos podrían eliminarse y simplemente verificar los números devueltos y una falsificación.

Uso de muestra

Si el código anterior se guardó como función s

s 8 @(1,2,3,4)
s 8 @(1,7,4,6,5,3,8,2) 
Mate
fuente
Puede guardar unos pocos bytes más eliminando $cy haciendo un bucle hacia abajo -($a.count-1)..1|%{$f=$_;--$_..0|%{if...
AdmBorkBork
2

R, 49 bytes

function(x,y){r=combn(x,2);r[,colSums(r)==y][,1]}

Esto encuentra todas las combinaciones de 2 xy devuelve una matriz. Luego, suma por columna y encuentra todas las sumas que son iguales a y(por lo tanto, sin la [,1]parte al final, imprimirá todas las combinaciones a las que equivalen sus sumas y)

David Arenburg
fuente
2

Japt , 9 bytes

Ahorró muchos bytes gracias a @ETHproductions

à2 æ_x ¥V

Pruébalo en línea!

Explicación

à2 æ_x ¥V
à2         // Creates all combinations of the input, length 2
   æ       // Returns the first item where:
    _x     //     The sum of the two items in each set
       ¥V  //     == Second input   

Ejemplo

Input:        [1,2,3], 4
à2         // [[1,2],[1,3],[2,3]]
   æ_x     // [3,    4,    5    ]
       ¥V  //  3!=4, 4==4 ✓
Output:    //  1,3
Oliver
fuente
2

Javascript, 114 96 86 84 bytes

a=>b=>{c=b.length;for(x=0;x<c;x++)for( y=x;++y<c;)if(b[x]+b[y]==a)return[b[x],b[y]]}

Se guardó 1 byte gracias a @Cyoce y otros 8 bytes gracias a @ETHProductions

Esto devuelve una tupla con la primera combinación de elementos de lista que suman la entrada dada, o nada para ninguna coincidencia. He eliminado la vars en la función; REPL.it se bloquea sin ellos, pero Chrome Dev Console maneja esto muy bien ...

Pruébalo en línea!

Steenbergh
fuente
No sale del código 1, ya que el desafío solicita específicamente una entrada no válida. Es una respuesta no válida por ahora, pero le he preguntado a OP sobre este requisito para los idiomas que no pueden hacerlo tan fácilmente.
Rɪᴋᴇʀ
@ Matt Sí, se observa esa regla: y=x+1se encarga de eso.
steenbergh
1
Puede usar a=>b=>...para guardar un byte
Cyoce
1
Puede guardar otros tres bytes con for(y=x;++y<b.length;){. Además, puede eliminar todos los conjuntos de llaves, excepto el más externo, y puede eliminar el espacio después dereturn
ETHproductions
1

Clojure, 77 bytes

#(first(mapcat(fn[i a](for[b(drop(inc i)%):when(=(+ a b)%2)][a b]))(range)%))

Devuelve el primer par o nil.

NikoNyrh
fuente
1

Haskell, 62 bytes

r=return;s#[]=r 1;s#(a:b)|elem(s-a)b=print(a,s-a)>>r 0|1<2=s#b

Todavía no sé qué permite el desafío y qué no. Voy por una función que imprime un par de números y devuelve 0 si hay una solución y no imprime nada y devuelve 1 si no hay solución. Como la impresión es E / S, tengo que elevar los valores de retorno a la IO-Monad (vía return) y el tipo real de la función esNum a => IO a .

Ejemplo de uso (con el valor de retorno impreso por la réplica):

*Main> 4 # [2,2]
(2,2)
0

Pruébalo en línea!.

Si se permiten las excepciones, failse guardarán algunos bytes (51 en total):

s#[]=fail"";s#(a:b)|elem(s-a)b=print(a,s-a)|1<2=s#b
nimi
fuente
1

Jalea , 9 bytes

ŒcS=¥ÐfḢZ

Jelly no tiene forma de establecer el código de salida en valores arbitrarios, por lo que esto produce un TypeError para la entrada sin una solución válida que hará que el intérprete principal salga con el código de salida 1 .

Pruébalo en línea!

Cómo funciona

ŒcS=¥ÐfḢZ  Main link. Argument: A (array of integers), n (integer)

Œc         Yield all 2-combinations of different elements of A.
     Ðf    Filter by the link to the left.
    ¥        Combine the two links to the left into a dyadic chain.
  S            Take the sum of the pair.
   =           Compare the result with n.
       Ḣ   Head; extract the first pair of the resulting array.
           This yields 0 if the array is empty.
        Z  Zip/transpose the result.
           This doesn't (visibly) alter pairs, but it raise a TypeError for 0.
Dennis
fuente
1

Nova , 101 bytes

q(Int[] a,Int x)=>a{if(Int y=a.firstWhere({a.contains(x-a.remove(0))}))return [y,x-y];System.exit(1)}

Una cosa buena del código golf es que me ayuda a encontrar errores en mi idioma. por ejemplo, el espacio requerido entre returny [y,x-y].

Una vez que agregue funciones push / pop a Array.nova y corrija el retorno, serían 96 bytes:

q(Int[] a,Int x)=>a{if(Int y=a.firstWhere({a.contains(x-a.pop())}))return[y,x-y];System.exit(1)}

Uso:

class Test {
    static q(Int[] a,Int x)=>a{if(Int y=a.firstWhere({a.contains(x-a.remove(0))}))return [y,x-y];System.exit(1)}

    public static main(String[] args) {
        Console.log(q([1, 2, 3, 4, 5], 8)) // [5, 3]
        Console.log(q([1, 2, 3, 4, 5], 5)) // [1, 4]
        Console.log(q([1, 2, 3, 4], 8)) // exit code 1
    }
}

Editar: Además, hay esta manera en 73 bytes (69 usando pop), también:

q(Int[] a,Int x)=>[Int y=a.firstOrThrow({a.contains(x-a.remove(0))}),x-y]

firstOrThrow lanzará una Excepción, que será descubierta y, por lo tanto, finalmente saldrá del programa con el código de salida 1.;)

Esta forma parece más legible también.

Braden Steffaniak
fuente
0

Pyth, 12 bytes

hfqsThQ.ceQ2

Explicación

       .ceQ2   Get all pairs from the second input
 fqsThQ        Find the ones whose sum is the first input
h              Take the first (exits with error code 1 if there aren't any)

fuente
0

PHP, 88 bytes

for($i=1;$a=$argv[$k=++$i];)for(;$b=$argv[++$k];)if($a+$b==$argv[1])die("$a $b");die(1);

toma información de los argumentos de la línea de comando, suma primero. Corre con-nr .

Afortunadamente, die/ exitsale con0 cuando le das una cadena como parámetro.

Traté de fusionar los bucles a uno; pero requiere una inicialización más larga y prueba esta vez.

Titus
fuente
¿Mal día? for($i=1;$a=$argv[$k=++$i];)for(;$b=$argv[++$k];)$a+$b!=$argv[1]?:die(!0);y deberías echar un vistazo a este codegolf.stackexchange.com/questions/120803/…
Jörg Hülsermann
0

Mathematica, 76 bytes

f::e="1";If[(l=Cases[#~Subsets~{2},x_/;Tr@x==#2])=={},Message@f::e,First@l]&

Bastante sencillo: #~Subsets~{2}obtiene todos los subconjuntos de 2 elementos de la lista, luego Cases[...,x_/;Tr@x==#2]selecciona solo aquellos cuya suma es el número que queremos. Si no hay ninguno de estos, If[l=={}, Message@f::e,First@l]imprime el mensaje de errorf::e : 1 que definimos anteriormente (ya que no tengo idea de qué más podría significar "estado de salida 1" para Mathematica); de lo contrario, devuelve la primera entrada en la lista de pares que suman lo correcto.

Si se nos permite devolver un valor falsey en lugar de hacer ese extraño estado de salida, el siguiente código tiene 58 bytes:

If[(l=Cases[#~Subsets~{2},x_/;Tr@x==#2])=={},1<0,First@l]&
No un arbol
fuente
0

Scala, 55 41 bytes

(l,n)=>l combinations 2 find(_.sum==n)get

Devuelve una lista de los dos números si existen y, de lo contrario, arroja un error. Descubierto, este error dará como resultado un estado de salida de 1.

Brian McCutchon
fuente
0

Ruby, 53 48 bytes

->a,s{p(a.combination(2).find{|x,y|x+y==s})?0:1}

Entrada: a es la lista, s es la suma esperada.

Si se encuentran los 2 números, imprímalos y devuelva 0, de lo contrario devuelva 1, como en la especificación.

GB
fuente
0

TI-Basic, 59 bytes

Prompt L1
Prompt X
While 1
L1(1→B
seq(L1(C),C,2,dim(L1→L1
If sum(not(X-L1-B
Then
Disp B,X-B
Return
End
End

Explicación:

Prompt L1               # 4 bytes, input array like "{1, 2, 3}"
Prompt X                # 3 bytes, Input target sum
While 1                 # 3 bytes, until the list is empty
L1(1→B                  # 7 bytes, try the first element (now B)
seq(L1(C),C,2,dim(L1→L1  # 18 bytes, remove first element from list
If sum(not(X-L1-B       # 10 bytes, if any element in the list plus B is the target
Then                    # 2 bytes, then...
Disp B,X-B              # 7 bytes, print it and it's "complement"
Return                  # 2 bytes, and exit gracefully
End                     # 2 bytes
End                     # 1 byte

Si el programa no salió correctamente, causará un error cuando no haya suficientes elementos en la lista para que continúe.

pizzapants184
fuente
0

CJam, 23 bytes

l~_,1>{e!2f<::+#)}{;;}?

Entrada es sum numbers. Por ejemplo:6 [3 2 3] . Deja un número positivo para la verdad y una cadena vacía o 0 para falsey.

Explicación:

l~    e# Read input and evaluate:  | 7 [3 2 3]
_     e# Duplicate:                | 7 [3 2 3] [3 2 3]
,     e# Take the length:          | 7 [3 2 3] 3
1>{   e# If more than 1:           | 7 [3 2 3]
  e!  e#   Unique permutations:    | 7 [[2 3 3] [3 2 3] [3 3 2]]
  2f< e#   Slice each to length 2: | 7 [[2 3] [3 2] [3 3]]
  ::+ e#   Some each:              | 7 [5 5 6]
  #   e#   Index:                  | -1
  )   e#   Increment:              | 0
}{    e# Else:                     | 7 [3 2 3]
  ;   e#   Pop                     | 7
  ;   e#   pop                     |
}?    e# Endif
e# Implicit output: 0
Fruta Esolanging
fuente