Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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

share|improve this question
1  
Round to the nearest integer? –  n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Jun 11 at 14:10
1  
@n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ I read that as "round each element of A to the nearest element of B" –  Jan Dvorak Jun 11 at 14:14
    
@JanDvorak: Well, I understand the part about rounding direction, but the problem didn't specify to how many digits. –  n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Jun 11 at 14:15
    
@n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Round to nearest float. The answer has to output floats from array/list B. –  Orhym Jun 11 at 14:16
1  
Will arrays A and B be sorted? –  steveverrill Jun 11 at 14:21

17 Answers 17

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.

share|improve this answer
1  
Ha! Welcome! :) –  belisarius Jun 12 at 0:52

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.

share|improve this answer
    
How does this work? –  Jan Dvorak Jun 11 at 14:30
    
Explained in answer –  Vovanium Jun 11 at 14:43
    
How on earth do you know how to write this? –  Martijn Jun 12 at 12:43
    
This is like writing chinese. For me, there's no great difference writing either alien words or alien characters... –  Vovanium Jun 18 at 20:42

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();}
share|improve this answer
    
Lists are fine too. –  Orhym Jun 11 at 14:15
1  
Rename item to i and you will safe 6 additional characters ;) –  Aschratt Jun 11 at 14:31
    
@Aschratt thank you very much! –  tsavinho Jun 11 at 14:38
3  
1. The function doesn't specifically say to return the new value, but I think you should. 2. Since the question called for float, I think you should use float float[] t(float[] a, float[] b) {return a.Select(d=>b.OrderBy(e=>Math.Abs(e-d)).First()).ToArray();} –  Grax Jun 11 at 14:51
    
@Grax As I wrote my first answer, the question wasn't about floats. Since the question has been updated, I included your answer too. Thank you very much. –  tsavinho Jun 12 at 9:16

TI-BASIC, 45 36

Assumes A and B already contain their arbitrary number of floats.

999→dim(A:999→dim(B:round(abs(A-B),0

Displays the answer as well as storing it in a new array (Ans), which was required. See round (TI-BASIC wiki) for help or explanations of round on lists (arrays). Also includes a link to abs with lists.

share|improve this answer
    
Please specify what version you are using - this does not work on my voyage 200. –  flawr Jun 12 at 8:28
1  
I would assume TI-83 style TI-BASIC. –  Kaslai Jun 12 at 10:04
    
@flawr TI-83/84/+/SE –  Timtech Jun 12 at 10:44
    
A and B can only represent single numbers in TI-BASIC, so I'm not sure how this is supposed to work. And even if they were lists, the algorithm does not seem correct. –  Runer112 Jun 12 at 21:10
    
@Runer112 Any variable can be a list, so long as it is initialized {1,2,3}->LA where -> is STO-> and L is the list character. –  Timtech Jun 13 at 12:03

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
share|improve this answer

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]

share|improve this answer
1  
D= isn't needed, as map returns a new array. Alternative (same length) sort function: (x,y)=>(x-=a)*x-(y-=a)*y –  nderscore Jun 11 at 16:42

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]

share|improve this answer

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.

share|improve this answer
    
I edited the answer to make it a function since the question requires a function. –  user80551 Jun 12 at 12:37

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.

share|improve this answer

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.

share|improve this answer

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
share|improve this answer
    
you could use floats in the example to make it clear it handles floats too –  bebe Jun 11 at 21:02
    
@bebe - Thanks, updated to make that clear. –  Rynant Jun 12 at 13:03

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.

share|improve this answer

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.

share|improve this answer

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
share|improve this answer
    
Does the 166/163 count the whitespace or not? –  Kyle Kanos Jun 11 at 16:31
    
Of course not. Spaces and newlines are for ease of understanding. –  bebe Jun 11 at 16:48

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]
share|improve this answer

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()+", ");
        }
    }
}
share|improve this answer

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();}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.