11
\$\begingroup\$

Challenge

Assume two vectors \$\mathbf{a} = (a_1,a_2,\cdots,a_n)\$ and \$\mathbf{b} = (b_1,b_2,\cdots,b_n)\$ are given in an \$n\$-dimensional space, where at least one of \$b_1,\cdots,b_n\$ is nonzero. Then \$\mathbf{a}\$ can be uniquely decomposed into two vectors, one being a scalar multiple of \$\mathbf{b}\$ and one perpendicular to \$\mathbf{b}\$:

$$ \mathbf{a} = \mathbf{b}x + \mathbf{b^\perp}\text{, where }\mathbf{b^\perp} \cdot \mathbf{b}=0. $$

Given \$\mathbf{a}\$ and \$\mathbf{b}\$ as input, find the value of \$x\$.

This can be also thought of as the following: Imagine a line passing through the origin and the point \$\mathbf{b}\$. Then draw a perpendicular line on it that passes through the point \$\mathbf{a}\$, and denote the intersection \$\mathbf{c}\$. Finally, find the value of \$x\$ that satisfies \$\mathbf{c}=\mathbf{b}x\$.

You can use an explicit formula too (thanks to @xnor), which arises when calculating the projection:

$$ x=\frac{\mathbf{a} \cdot \mathbf{b}}{\mathbf{b} \cdot \mathbf{b}} $$

Standard rules apply. The shortest code in bytes wins.

Example

Here is an example in 2D space, where a=(2,7) and b=(3,1). Observe that (2,7) = (3.9,1.3) + (-1.9,5.7) where (3.9,1.3) is equal to 1.3b and (-1.9,5.7) is perpendicular to b. Therefore, the expected answer is 1.3.

enter image description here

Test cases

a         b          answer
(2,7)     (3,1)      1.3
(2,7)     (-1,3)     1.9
(3,4,5)   (0,0,1)    5
(3,4,5)   (1,1,1)    4
(3,4,5)   (1,-1,-1)  -2
(3,4,5,6) (1,-2,1,2) 1.2
\$\endgroup\$
  • \$\begingroup\$ Will the values of the input vectors always be integers? \$\endgroup\$ – Noodle9 Jun 10 at 12:23
  • 1
    \$\begingroup\$ @Noodle9 No, it may have non-integers. \$\endgroup\$ – Bubbler Jun 10 at 13:22
  • \$\begingroup\$ Can we take the dimension \$n\$ as additional argument? \$\endgroup\$ – Kevin Cruijssen Jun 10 at 14:20
  • 1
    \$\begingroup\$ @KevinCruijssen No, unless you're using pointer+length input. \$\endgroup\$ – Bubbler Jun 10 at 22:52

14 Answers 14

24
\$\begingroup\$

APL (Dyalog Unicode), 1 byteSBCS

Check all test cases! When used dyadically, X ⌹ Y solves the least squares* system \$Ya = X\$ for a result \$a\$ of the appropriate shape, e.g.:

  • if \$Y\$ is a matrix and \$X\$ is a vector, we try to solve a linear system of equations.
  • if \$Y\$ and \$X\$ are matrices, we compute \$Y\$'s (pseudo-)inverse and multiply it on the left of \$X\$.
  • when both \$X\$ and \$Y\$ are vectors, the least squares formulation reduces to what we want, namely

$$\frac{X \cdot Y}{||Y||^2}$$

*the least squares system \$Ya = X\$ can be understood as "what should \$a\$ be such that \$Ya\$ is as close as can be to \$X\$?", where closeness is measured with the usual L2 distance.

| improve this answer | |
\$\endgroup\$
  • 6
    \$\begingroup\$ We have a winner. I very much doubt any language can do this in 0 bytes. \$\endgroup\$ – Adám Jun 10 at 8:24
  • \$\begingroup\$ If I open a file and I see that thing in it, I will mark it as virus. \$\endgroup\$ – darksky Jun 12 at 3:40
  • \$\begingroup\$ @darksky a couple of months ago I would've done the exact same thing \$\endgroup\$ – RGS Jun 12 at 6:51
8
\$\begingroup\$

Haskell, 33 32 bytes

-1 byte thanks to @xnor!

(!)b=sum.zipWith(*)b
a#b=a!b/b!b

Try it online!


Coconut, 35 bytes

(a,b)->p(a,b)/p(b,b)
p=sum..map$(*)

Try it online!

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Save a byte by making definition of ! a bit less pointfree: (!)v=sum.zipWith(*)v \$\endgroup\$ – xnor Jun 10 at 19:40
4
\$\begingroup\$

R, 24 bytes

function(a,b)a%*%b/b%*%b

Try it online!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ lm(a~b-1) does slightly better. \$\endgroup\$ – Xi'an Jun 13 at 9:18
  • 1
    \$\begingroup\$ @Xi'an that's great, and it's also a principally different approach, so I'd suggest you to post it as a separate answer. \$\endgroup\$ – Kirill L. Jun 13 at 10:47
4
\$\begingroup\$

Python 3 + numpy, 20 bytes

lambda a,b:a@b/(b@b)

Try it online!

| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

MATL, 2 bytes

Y\

Try it online!

Least squares approach such as used in the APL answer.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Jelly, 6 5 bytes

ḋ`÷@ḋ

Try it online!

Simple translation of the given formula. Takes \$\mathbf{b}\$ as the left argument and \$\mathbf{a}\$ as the right argument.

ḋ        The dot product of b and
 `       itself,
  ÷@     dividing
    ḋ    the dot product of b and a.
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 21 18 bytes

F²⊞υΣEA×κ§θλI∕⊟υ⊟υ

Try it online! Link is to verbose version of code. Takes inputs in the order b, a. Explanation:

F²

Repeat twice...

⊞υΣEA×κ§θλ

Input a vector, take its dot product with b and push the result to the predefined empty list.

I∕⊟υ⊟υ

Retrieve the dot products and take their quotient.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ The previous version was lost because I happened to slip under the grace edit period by a couple of seconds, but you didn't miss much, just a one-byte golf from taking inputs in reverse order and separate a two-byte golf. \$\endgroup\$ – Neil Jun 10 at 10:42
2
\$\begingroup\$

05AB1E, 6 bytes

*OInO/

Try it online or verify all test cases.

Implements the given formula:

$$x = \frac{a_1\times b_1 + a_2\times b_2 + \dots + a_n\times b_n}{b_1^2 + b_2^2 + \dots + b_n^2}$$

Explanation:

*       # Multiply the values at the same indices in the two (implicit) input-lists
 O      # Sum this list
  I     # Push the second input-list again
   n    # Square each value
    O   # Take the sum of that
     /  # And divide the two values
        # (after which the result is output implicitly)
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

C (gcc), 84 74 73 bytes

Saved 10 bytes thanks to dingledooper!!!

Saved a byte thanks to ceilingcat!!!

float f(a,b,n)float*a,*b;{float x,y;for(;n--;y+=*b**b++)x+=*a++**b;x/=y;}

Try it online!

Inputs two pointers to vectors \$a,b\$ and their dimension \$n\$ and returns their component..

Uses given formula:

$$x = \frac{a_0\cdot b_0 + a_1\cdot b_1 + \dots + a_{n-1}\cdot b_{n-1}}{b_0^2 + b_1^2 + \dots + b_{n-1}^2}$$

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Wolfram Language (Mathematica), 9 bytes

#.#2/#.#&

Try it online! Pure function. Takes b followed by a as input and returns a rational number as output. It just directly uses Mathematica's notation for the dot product.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

[R], 22 bytes

Taking advantage of a resident regression function, lm

function(a,b)lm(a~b-1)

Try it online!

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Fortran >= 95, 66 bytes

Taking advantage of implicit typing for the return type.

function x(a,b)
real a(:),b(:)
x=dot_product(a,b)/norm2(b)**2
end
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Java 10, 84 74 bytes

a->b->{float A=0,B=0;int i=0;for(var t:b){A+=a[i++]*t;B+=t*t;}return A/B;}

Try it online.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Japt v2.0a0, 9 bytes

í*V x÷Vx²

Try it

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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