Find nearest number in a given array

Question

This is inspired by a real world problem I had. I'm curious to see if there is any clever way to go about this.

You are given two unsorted arrays, A and B, each containing an arbitrary number of floats. A and B don't necessarily have the same lengths. Write a function that takes the elements of A sequentially and finds the nearest value in array B. The result has to be contained in a new array.

Win condition

Shortest code wins (as usual).

Answer 1

APL, 13 17

(21 byte in UTF-8)

B[{↑⍋|⍵-B}¨A]

If you want true lambda (A as left argument and B as right):

{⍵[⍺{↑⍋|⍺-⍵}¨⊂⍵]}

How it works:

{...}¨A invokes lambda function {...} with every A value (instead of invoking with A as array), gathering results to array of same shape

|⍵-B computes absolute values of difference between argument ⍵ and all in B (- is subtraction, | is abs).

↑⍋ takes index of least element (⍋ sorts array returning indices, ↑ get first element)

B[...] is just fetching element(s) by index(es).

The solution is quite strightforward, altough it uses wonderful feature of APL's sorting function returning permutation vector (sorted element's indices in original array) rather than sorted array itself.

Answer 2

Mathematica - 17

#&@@@Nearest@A/@B

How does it work? Yes, I admit that there's a bit of cheating here because Mathematica has built-in nearest functionality. The rest is straightforward and is concerned with arranging the result in a 1D array. It looks ugly only because of the extra effort to make it short.

Answer 3

C# - 103 97 87 Bytes

I'm not quite sure if I understood this question correctly but here is my solution anyway. I used Lists instead of arrays, because it allows me to write shorter code.

A integer array is shorter than a integer list.

Input:

t(new int[] { 0, 25, 10, 38 }, new int[] { 3, 22, 15, 49, 2 });

Method:

void t(int[]a,int[]b){var e=a.Select(c=>b.OrderBy(i=>Math.Abs(c-i)).First()).ToArray();

Output:

2, 22, 15, 49

If my answer isn't correct, please leave a comment below it.

EDIT: AS @grax pointed out, the question is now about floats. Therefore I'd like to include his answer too.

95 Bytes(Grax's answer)

float[]t(float[]a,float[]b){return a.Select(d=>b.OrderBy(e=>Math.Abs(e-d)).First()).ToArray();}

Answer 4

R, 41 chars

B[apply(abs(outer(A,B,`-`)),1,which.min)]

Explanation:

outer(A,B,`-`) computes for each element x of A the difference x-B and outputs the result as a matrix (of dimension length(A) x length(B)).
which.min picks the index of the minimal number.
apply(x, 1, f) applies function f on each row of matrix x.
So apply(abs(outer(A,B,`-`)),1,which.min) returns the indices of the minimal absolute difference between each element of A and the elements of vector B.

Usage:

> A <- runif(10,0,50)
> B <- runif(10,0,50)
> A
[1] 10.0394987 23.4564467 19.6667152 36.7101256 47.4567670 49.8315028  2.1321263 19.2866901  0.7668489 22.5539178
> B
[1] 44.010174 32.743469  1.908891 48.222695 16.966245 23.092239 24.762485 30.793543 48.703640  6.935354
> B[apply(abs(outer(A,B,`-`)),1,which.min)]
[1]  6.935354 23.092239 16.966245 32.743469 48.222695 48.703640  1.908891 16.966245  1.908891 23.092239

Answer 5

CJam - 14

q~
f{{1$-z}$0=\;}
p

The main code is on the second line, the rest is for using the standard input and pretty output.

Try it at http://cjam.aditsu.net/

Explanation:

q~ reads and evaluates the input
f{...} executes the block for each element of the first array and the next object (which is the second array), collecting the results in an array
{...}$ sorts the second array using the block to calculate a key for each item
1$ copies the current item from the first array
-z subtracts then takes the absolute value
0= takes the first value of the sorted array (the one with the minimum key)
\; discards the item from the first array
p prints the string representation of the result

Examples (inspired from other answers):

Input: [10.1 11.2 12.3 13.4 9.5] [10 12 14]
Output: [10 12 12 14 10]

Input: [0 25 10 38] [3 22 15 49 2]
Output: [2 22 15 49]

Answer 6

Python 3.x - 55 chars

f=lambda a,b:[min((abs(x-n),x)for x in b)[1]for n in a]

a and b are the input arrays, and the desired array is the expression's result.

Answer 7

Javascript (E6) 54 56 59

Minimize distance. Using square instead of abs just so save chars.
Edit algebra ...
Edit fix useless assignment (a remainder of a test w/o the function definition)

F=(A,B)=>A.map(a=>B.sort((x,y)=>x*x-y*y+2*a*(y-x))[0])

Was F=(A,B)=>D=A.map(a=>B.sort((x,y)=>((x-=a,y-=a,x*x-y*y))[0])

Test

F([10.1, 11.2, 12.3, 13.4, 9.5],[10, 12, 14])

Result: [10, 12, 12, 14, 10]

Answer 8

PowerShell - 44

$a|%{$n=$_;($b|sort{[math]::abs($n-$_)})[0]}

Example

With $a and $b set to:

$a = @(36.3, 9, 50, 12, 18.7, 30)
$b = @(30, 10, 40.5, 20)

Output is

40.5, 10, 40.5, 10, 20, 30

Answer 9

Haskell, 55

c a b=[[y|y<-b,(y-x)^2==minimum[(z-x)^2|z<-b]]!!0|x<-a]

At first, I thought to use minimumBy and comparing, but since those aren't in Prelude, it took a ton of characters to qualify them. Also stole the squaring idea from some other answers to shave off a character.

Answer 10

Ruby, 40

f=->a,b{a.map{|x|b.min_by{|y|(x-y)**2}}}

Same as the Python answer, but squaring is a little terser than any way I could think of to take absolute value.

Answer 11

TI-BASIC, 24

∟A+seq(min(∟B+i²∟A(N)),N,1,dim(∟A

Doesn't come close to APL, but uses less powerful functions-- this uses no "sorted by" or "index of least" function. The disadvantage of TI-BASIC here is its lack of those functions and multidimensional arrays.

Ungolfed:

seq(       ,N,1,dim(∟A           #Sequence depending on the Nth element of list A
    ∟A(N)+min(   +0i)            #Number with minimum absolute value, add to ∟A(N)
              ∟B-∟A(N)           #Subtracts Nth element of ∟A from all elements of B

The min( function has two behaviors: when used with real numbers or lists, it gives the smallest value; however, when used with complex numbers or lists, it gives the value with the smallest absolute value. Adding 0i or multiplying by i^2 causes the interpreter to use the second behavior, so min(1,-2) returns -2 whereas min(1+0i,-2+0i) returns 1.

Answer 12

Pyth - 12 11 bytes

Note: Pyth is much younger than this challenge, so this answer is not eligible to win.

Simple method, uses o order function to get minimal distance and maps it over list a.

mho.a-dNQvz

m    vz    Map over evaled first input and implicitly print
 ho Q      Minimal mapped over evaled second input
  .a-      Absolute difference
   d       Lambda param 1
   b       Lambda param 2

Try it online here.

Answer 13

Fortran 90: 88

function f();integer::f(size(a));f(:)=[(b(minloc(abs(a(i)-b))),i=1,size(a))];endfunction

This requires it to be contained within a full program:

program main
   real :: a(5), b(3)
   integer :: i(size(a))
   a = [10.1, 11.2, 12.3, 13.4, 9.5]
   b = [10, 12, 14]
   i = f()
   print*,i
 contains
   function f()
     integer :: f(size(a))
     f(:)=[(b(minloc(abs(a(i)-b))),i=1,size(a))]
   end function
end program main

The square braces declare an array while (...,i=) represents an implied do loop; I then return the value of b for which element a(i)-b is minimized.

Answer 14

Matlab: 48

f=@(a)B(abs(B-a)==min(abs(B-a)));C=arrayfun(f,A)

Assumes that A and B are 1D matrices in the workspace, Final result is C in the workspace. This would likely also work in Octave as well. Conditional indexing makes doing this fairly trivial.

Answer 15

C 144 163

#define f float
f T, *C, m;
f *q(f *A, f *B, int S, f s)
{
    if(m) 
        return abs(T - *A) - abs(T - *B);
    for ( 
        C = malloc(S * 4);
        m = S--;
        C[S] = *B
    ) 
        T = A[S], 
        qsort(B, s, 4, q);
    return C;
}

Okay... I think this little code needs explanation.

At first i tried to do the job with two level of for loop finding the min difference and set the current value to min of B's value. That's very basic.

The same thing can be reached with qsort and a comparator function. I make it sort B by the difference instead of B's elements. Too many functions for such a little algorithm. So the function q now serves two purposes. At first, it's the algorithm itself, secondly (when qsort calls it) a comparator. For communication between the two states, I had to declare globals.

m stands for whether it's in comparator state or the main one.

example:

float A[] = {1.5, 5.6, 8.9, -33.1};
float B[] = {-20.1, 2.2, 10.3};
float *C;

C = q(A, B, sizeof(A)/sizeof(*A), sizeof(B)/sizeof(*B));
// C holds 2.2,2.2,10.3,-20.1

Answer 16

GolfScript, 49 bytes

Note: this is a partial solution. I'm working on making it a complete solution

{{\.@\.[.,,\]zip@{[\~@-abs]}+%{~\;}$0=0==}%\;}:f;

Yes. GolfScript does support floating point. Try it out here. Example:

# B is [-20.1 2.2 10.3]
[-201 10 -1?*
22 10 -1?*
103 10 -1?*]

# A. No floating point numbers allowed here.
# This is because 1.5{}+ (where the 1.5 is a
# single floating point number, not 1.5,
# which would be 1 1 5) results in the block
# {1.5 }, which leads to 1 1 5 when executed
[1 5 9 -30]

Output:

[2.2 2.2 10.3 -20.1]

Answer 17

C# 262

Program finds min differences and saves closest value from Array B. I'll work on the golfing shortly.

List<float> F(List<float> a, List<float> b)
{
List<float> c = new List<float>();
float diff,min;
int k;
for(int i=0; i<a.Count;i++)
{
diff=0;
min=1e6F;
k = 0;
for(int j=0; j<b.Count;j++)
{
diff = Math.Abs(a[i] - b[j]);
if (diff < min)
{
min = diff;
k = j;
}
}
c.Add(b[k]);
}
return c;
}

Full program with test code

using System;
using System.Collections.Generic;
public class JGolf
{
    static List<float> NearestValues(List<float> a, List<float> b)
    {
        List<float> c = new List<float>();
        float diff,min;
        int k;
        for(int i=0; i<a.Count;i++)
        {
            diff=0;
            min=1e6F;
            k = 0;
            for(int j=0; j<b.Count;j++)
            {
                diff = Math.Abs(a[i] - b[j]);
                if (diff < min)
                {
                    min = diff;
                    k = j;
                }
            }
            c.Add(b[k]);
        }
        return c;
    }

    public static void Main(string[] args)
    {
        List<float> A = RandF(8413);
        Console.WriteLine("A");
        Print(A);
        List<float> B = RandF(9448);
        Console.WriteLine("B");
        Print(B);

        List<float> d = JGolf.NearestValues(A, B);
        Console.WriteLine("d");
        Print(d);
        Console.ReadLine();
    }

    private static List<float> RandF(int seed)
    {
        Random r = new Random(seed);
        int n = r.Next(9) + 1;
        List<float> c = new List<float>();
        while (n-- > 0)
        {
            c.Add((float)r.NextDouble() * 100);
        }
        return c;
    }

    private static void Print(List<float> d)
    {
        foreach(float f in d)
        {
            Console.Write(f.ToString()+", ");
        }
    }
}

Answer 18

C#: 120

Linq is awesome:

float[] t(float[] A, float[] B){return A.Select(a => B.First(b => Math.Abs(b-a) == B.Min(c=>Math.Abs(c-a)))).ToArray();}