Это вопрос об интервью Google, здесь вы найдете ссылку на YouTube.

Задание:

Найти 2 целых числа из неупорядоченного списка, которые суммируются с заданным целым числом.

1. Получив неупорядоченный список целых чисел, найдите 2 целых числа, которые суммируются с заданным значением, выведите эти 2 целых числа и укажите успех (выход 0). Они не должны быть какими-то конкретными числами (то есть первые 2 целых числа, суммирующими правильное число), любая пара, которая суммирует значение, будет работать.
2. целое число положительное и больше нуля.
3. Список целых чисел может быть в любой структуре данных, включая файл целых чисел - одно целое число в строке.
4. если целые числа не найдены, укажите сбой (выход 1).
5. два целых числа в разных позициях в списке должны быть возвращены. (то есть вы не можете вернуть один и тот же номер из одной и той же позиции дважды)

(Примечание: в видео это не совсем требования. «Интервьюер» менял его несколько раз.)

например.

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

Печатает 3и 5и выходит из состояния 0. Обратите внимание, что в этом 1,7и 2,6будут также разрешены результаты.

sum2 8 <<EOF
1
2
3
4

Возвращает статус выхода 1, так как невозможна комбо. 4,4не разрешено, согласно правилу 5.

Баш, 84 байта

Моя реализация (примерно) решения инженера Google, но с использованием bash и потока ввода - не мое решение, так что это не считается.

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

метод

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

Брахилог , 9 байт

h⊇Ċ.+~t?∧

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

Предполагая, что я правильно понял задачу ...

объяснение

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)

Perl 6 , 59 байт

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

Попробуй
Попробуй без возможного результата

Expanded:

$_ = 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)

JavaScript ES6, 58 70 68 64 байта

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

Возвращает пару чисел в виде массива, если найдено, в противном случае возвращает undefinedложное значение.

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));

JavaScript (ES6), 61 57 56 байт

Принимает массив целых чисел aи ожидаемую сумму sв синтаксисе карри (a)(s). Возвращает пару совпадающих целых чисел в виде массива или, undefinedесли такой пары не существует.

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

Отформатировано и прокомментировано

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

Тестовое задание

let f =

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

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

Желе , 14 байт

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

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

Это функция (не полная программа), которая выводит на стандартный вывод. (Ссылка TIO имеет оболочку, которая запускает функцию и игнорирует ее возвращаемое значение.)

Эта программа может быть на 4 байта короче, если не требуется код выхода; вернуть код выхода 1 в Jelly довольно сложно. (Возможно, есть более краткий способ сделать это, что я пропустил.)

объяснение

Œ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

Мы можем просто вдвое сократить каждое целое число в паре, поэтому o⁶Hмы ничего не сделаем, если найдем результат, кроме возврата бесполезного возвращаемого значения, которое в любом случае не имеет значения ( Ṅслужит удобным однобайтовым методом для определения возврата функции). стоимость рано, в соответствии с правилами PPCG). Однако, если мы не нашли результат, мы заканчиваем тем, что пытаемся вдвое сократить символ пробела, операция настолько бессмысленная, что вызывает сбой интерпретатора Jelly. К счастью, этот сбой дает код выхода 1.

Perl 5 , 51 байт

46 байт кода + 5 байт для -pliфлагов.

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

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

Идея состоит в том, чтобы перебрать список ввода: для числа x( $_), если мы ранее видели n-x( $^I-$_), то мы нашли то, что искали, и установили $\эти два значения ( "$_ $v"). В конце, если $\не установлено, то мы exit 1, иначе это будет неявно напечатано.

Рёда , 60 56 байт

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

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

Этот код выдает ошибку, если ответа нет. Он генерирует все возможные пары, которые могут составить сумму s, т.е. 1, s-1, 2, s-2, 3, s-3, ... Тогда он проверяет , если оба числа в массиве , aи если да, подталкивает их к потоку. pullчитает одно значение из потока и возвращает его. Если в потоке нет значений, выдается ошибка. a-xвозвращает массив aс xудаленным

Python 2, 60 байт

Этот короткий, пока правила с выходом с кодом 1 не будут разъяснены. Теперь выходит с ошибкой, если ничего не найдено.

-5 байт благодаря @Peilonrayz

-4 байта благодаря @Rod

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

a,s=input()
while a:
 x=a.pop()
 if s-x in a:r=s-x,x
print r

C ++ 133 байта (скомпилировано с помощью clang 4 и 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 байтов

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

Haskell , 34 байта

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

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

Для каждого элемента списка эта функция проверяет, находится ли (sum-element) в следующей части списка. Возвращает первую найденную пару. Если функция достигает конца списка, она выдает ошибку «неисчерпывающие шаблоны» и завершается с кодом 1.

PowerShell, 109 97 байт

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

Заключил 12-байтную сделку, предложенную AdmBorkBork

объяснение

# 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

Текущие правила ищут код выхода, который это делает. Они могут быть удалены и просто проверить возвращаемые номера и ложные.

Образец использования

Если код выше был сохранен как функция s

s 8 @(1,2,3,4)
s 8 @(1,7,4,6,5,3,8,2) 

R, 49 байт

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

Это находит все 2-комбинации x и возвращает матрицу. Затем суммирует столбец и находит все суммы, которые равны y(поэтому без [,1]части в конце он напечатает все комбинации, которым равны их суммы y)

Japt , 9 байт

Сохранено много байтов благодаря @ETHproductions

à2 æ_x ¥V

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

объяснение

à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   

пример

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

Javascript, 114 96 86 84 байта

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

Сохранено 1 байт благодаря @Cyoce и еще 8 байт благодаря @ETHProductions

Это возвращает кортеж с первой комбинацией элементов списка, которые суммируют до заданного входного значения, или ничего без совпадения. Я удалилvar s в функции; REPL.it вылетает без них, но Chrome Dev Console прекрасно справляется с этим ...

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

Clojure, 77 байт

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

Возвращает первую такую ​​пару или nil.

Haskell, 62 байта

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

Я до сих пор не знаю, что разрешено вызовом, а что нет. Я собираюсь для функции, которая печатает пару чисел и возвращает 0, если есть решение и ничего не печатает и возвращает 1, если нет решения. Поскольку печать - это ввод-вывод, я должен поднять возвращаемые значения в IO-Monad (черезreturn ), и фактический тип функцииNum a => IO a .

Пример использования (с возвращаемым значением, напечатанным repl):

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

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

Если поднятие исключений разрешено, failбудет сохранено несколько байтов (всего 51):

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

Желе , 9 байт

ŒcS=¥ÐfḢZ

У Jelly нет способа установить для кода выхода произвольные значения, поэтому это вызывает ошибку TypeError для ввода без допустимого решения, которое приведет к завершению родительского интерпретатора с кодом выхода 1. .

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

Как это устроено

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

Нова , 101 байт

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

Хорошая вещь в Code Golf состоит в том, что она помогает мне находить ошибки на моем языке. например, пространство, необходимое между returnи [y,x-y].

Как только я добавлю функции push / pop в Array.nova и исправлю возвращаемый результат, будет 96 байтов:

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

Использование:

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

Изменить: Кроме того, есть этот путь на 73 байта (69 с использованием pop), также:

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

firstOrThrow сгенерирует исключение, которое будет необработанным и, следовательно, в конечном итоге выйдет из программы с кодом выхода 1.;)

Этот способ кажется более читабельным.

Pyth, 12 байт

hfqsThQ.ceQ2

объяснение

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

PHP, 88 байт

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

принимает входные данные из аргументов командной строки, сумма в первую очередь. Беги с -nr.

К счастью, die/ exitвыходит, 0когда вы задаете ему строку в качестве параметра.

_{Я пытался объединить петли в одну; но это требует более длительной инициализации и тестирования на этот раз.}

Mathematica, 76 байт

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

Довольно просто: #~Subsets~{2}получает все 2-элементные подмножества списка, затем Cases[...,x_/;Tr@x==#2]выбирает только те, чья сумма равна желаемому числу. Если нет ни одного из них,If[l=={}, Message@f::e,First@l] печатается сообщение об ошибкеf::e : 1 которое мы определили ранее (поскольку я понятия не имею, что еще может означать «выход из состояния 1» для Mathematica); в противном случае он возвращает первую запись в списке пар, которые суммируются с правильным значением.

Если нам разрешено возвращать значение Falsey вместо этого странного состояния выхода, следующий код имеет 58 байтов:

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

Scala, 55 41 байт

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

Возвращает список двух чисел, если они существуют, в противном случае выдает ошибку. Uncaught, эта ошибка приведет к состоянию выхода 1.

Рубин, 53 48 байт

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

Входные данные: a - список, s - ожидаемая сумма.

Если 2 числа найдены, выведите их и верните 0, в противном случае верните 1, как в спецификации.

TI-Basic, 59 байт

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

Объяснение:

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

Если программа не завершилась корректно, она вызовет ошибку, если в списке недостаточно элементов для продолжения.

CJam, 23 байта

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

Вход есть sum numbers. Например: 6 [3 2 3]. Оставляет положительное число для truey и пустую строку или 0 для falsey.

Объяснение:

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