Combinatorial Pipes

You're a plumber working on a house, and there's some pipes that must be connected at weird angles. You have 8°, 11.25°, 22.5°, 45°, and 90° fittings at your disposal, and you want to use as few as possible to match the angle as closely as possible.

Goal

• Match the desired angle as closely as possible, with as few fittings as possible. It can be over or under the desired angle.
• Accuracy is more important than the number of fittings
• In the case of two different sets of fittings with the same resulting angle, whichever has the fewest number of fittings should be selected.
• If the two sets use different fittings, match the same angle, and have the same number of fittings, either may be chosen.
• Your fittings cannot add up to greater than 360 degrees (i.e. no looping all the way around)

Input

Your input is a random integer between (non-inclusive) 0° and 180°, which represents the desired angle.

Output

Your output should be an array where [0]-># of 8° fittings, [1]-># of 11.25° fittings, etc. If your language does not support arrays, you may output a comma separated list, where the first value represents the number of 8° fittings, and so on and so forth.

Test Cases

90° ->[0,0,0,0,1]
24°-> [3,0,0,0,0] ([0,0,1,0,0] uses less fittings, but is less accurate and therefore incorrect)
140°->[2,1,1,0,1]
140°->"2,1,1,0,1" acceptable if language does not support arrays


Scoring

Lowest byte count for each language wins a high five from me if we ever bump into each other (and the challenge).

• I always comment on new users' posts because they so rarely use the sandbox, and then I check immediately afterwards in case they did to make sure my comment's correct (I've now deleted it). Thanks for using the sandbox! However, while we'd typically recommend leaving your challenges in the sandbox for at least 3 days, you should probably wait for at least one person to upvote it or to leave a comment to show they've checked it, because this was a pretty well-specified challenge but the few edits we've made already should tell you there were still improvements to be made. Jun 11, 2021 at 17:04
• @pxeger that's how you have got Pundit :P Jun 11, 2021 at 17:41
• Shouldn't that last case be 2,1,1,0,1?
– Neil
Jun 11, 2021 at 17:49
• @Neil Yep, whoops! I'll fix it Jun 11, 2021 at 18:35
• To connect pipes at (almost) an angle of 4 degrees, one could use 44x 8-degree fittings plus one 11.25 degree fitting to get a total angle of 363.25 = one full loop and a resulting angle of 3.25 degrees (error of 0.75 degrees). Is this the correct answer for 4? If not, are loops forbidden? Jun 11, 2021 at 19:49

Jelly, 21 bytes

Ḷṗ5SÞðḋ90H3Ð¡;8¤ạðÞḢṚ


Try it online!

Note - after Nick Kennedy's golfs, this answer is actually identical to Jonathan Allan's answer, which they arrived at independently. Make sure to upvote them.

-9 bytes thanks to Nick Kennedy by rewriting the conversion from counts to total angle

ḶṗSÞ5ðḋ90H3Ð¡;8¤ạðÞḢṚ  Main Link
Ḷ                      Lowered range; [0, 1, ..., N-1]
ṗ5                    Cartesian product; size 5 lists of the above elements
SÞ                  Sort by sum
ð           ðÞ    Sort by:
ạ      - absolute difference of the following and the input:
ḋ                - dot product with
90H3Ð¡;8¤       - [90, 45, 22.5, 11.25, 8] via the following
90                - 90
3Ð¡            - repeat 3 times and collect results:
H               - halve
;8          - append 8
Ḣ   take the first one (since it'll already be sorted by count and it's stable)
Ṛ  reverse it

• -8 bytes Ḷṗ5ðḋ90H3Ð¡;8¤ạðÞḢṚ Jun 11, 2021 at 22:06
• @NickKennedy Oh dot product is smart here. And I don't know how I didn't see that pattern lol; thank you. Jun 12, 2021 at 1:57
• You've missed the "absolute difference" from your explanation Jun 12, 2021 at 14:44
• @cairdcoinheringaahing oops :p Jun 12, 2021 at 15:01

Jelly, 21 bytes

Ḷṗ5SÞḋ90H3Ð¡;8¤ạɗÞ⁸ḢṚ


A monadic Link that accepts an integer in $$\[0,180]\$$ and yields a list of the five pipe counts in the prescribed order.

Try it online! although it'll time out for inputs above $$\15\$$ :(

How?

Builds all selections of pipes consisting of less than input-angle of each pipe, sorts these by their number of pipes, then (stable) sorts by the difference between the angle-sum and input-angle and yields the first.

Ḷṗ5SÞḋ90H3Ð¡;8¤ạɗÞ⁸ḢṚ - Link: angle, A
Ḷṗ5                   - (A) Cartesian product 5 -> all selections of the five pipes with
up to A-1 of each pipe
SÞ                 - sort by sum (number of pipes)
Þ    - sort (the elements X of that) by:
ɗ ⁸   -   last three links as a dyad - f(X, A)
90              -       90
3Ð¡          -       collect & repeat three times:
H             -         halve -> [90, 45, 22.5, 11.25]
;8        -       concatenate 8 -> [90, 45, 22.5, 11.25, 8]
ḋ                -     (X) dot-product (that)
ạ      -     (that) absolute-difference (A)
Ṛ - reverse (to the prescribed order of pipe counts)

• I’ve just realised that my golfs to @hyper-neutrino’s answer have given the same answer as yours - I hadn’t seen your answer before suggesting them, but was combining the best bits of my answer with his existing one. Jun 12, 2021 at 6:58
• Well almost the same anyway… Jun 12, 2021 at 7:14

Jelly, 22 bytes

ṗⱮẎSạ¥ÞḢċⱮ⁸
90H3Ð¡;8Ṛç


Try it online!

A pair of links which takes a single argument, the number of degrees to match, and returns a list of 5 integers. Hopelessly slow for increasing values, but should theoretically work for all of the required range.

This is a much more efficient implementation but is three bytes longer.

R, 958887 86 bytes

Edit: -1 byte thanks to pajonk

function(a,b=expand.grid(rep(list(23:0),5)))b[order((c(8,90/2^(3:0))%*%t(b)-a)^2)[1],]


Try it online!

Ungolfed code

fittings=
function(a){                        # a=desired angle
b=expand.grid(rep(list(23:0),5))    # b=all combinations of 5 elements of 23..0 (note: largest-to-smallest - see below)
# (23 is number of smallest (8-degree) fittings needed to get over 180 degrees)
c=colSums(t(b)*c(8,2^(-2:1)*45))    # c=the total angle made by each combination of fittings
d=which.min((d-a)^2)                # d=the first combination that minimized the absolute difference to angle a
# (we take the square to save a byte getting the absolute difference,
# and we automatically get the combination with the smallest numbrer of fittings
# since we constructed the combinations largest-to-smallest)
return(b[d,])                       # finally, return that element of b

• -1 byte Jun 13, 2021 at 13:04
• @pajonk - Thank you! The cleverest tricks always seem so obvious once somebody has shown them to me... Jun 13, 2021 at 13:36

Julia 0.7, 93 bytes

!x=minimum(i->((4x-[32,45,90,180,360]⋅i)^2,sum(i),i),Iterators.product(fill(0:22,5)...))[3]


Try it online!

JavaScript (ES6), 129 bytes

f=(n,a=[0,0,0,0,0],c=e=C=1/0)=>n<(n*n<e|n*n==e&c<C&&[e=n*n,C=c,o=a])?o:a.map((_,i,[...a])=>f(n-(i?90/(16>>i):8),a,-~c,a[i]++))&&o


Try it online!

Commented

f = (                    // f is a recursive function taking:
n,                     //   n = input
a = [0, 0, 0, 0, 0],   //   a[] = pipe counters
c =                    //   c = current number of pipes
e =                    //   e = best (smallest) squared error
C = 1 / 0              //   C = number of pipes for the best solution
) =>                     //
n < (                    //
n * n < e |            // if the current error is less than the best error
n * n == e & c < C &&  // or they're equal but we're using less pipes:
[ e = n * n,           //   update the best error
C = c,               //   update the best count
o = a                //   update the output
]                      // if e, C and o have been updated, we compare n with
// an array, which is always falsy
) ?                      // otherwise, we test whether n is negative:
o                      //   in which case we return o[]
:                        // else:
a.map(                 //
(_, i, [...a]) =>      //   for each value at position i in a[], using a copy
//   of a[]:
f(                   //     do a recursive call:
n - (              //       subtract from n:
i ?              //         if i is not equal to 0:
90 / (16 >> i) //           11.25, 22.5, 45 or 90
:                //         else:
8              //           8
),                 //
a,                 //       pass the copy of a[]
-~c,               //       increment c
a[i]++             //       increment a[i]
)                    //     end of recursive call
) && o                 //   end of map(); return o[]


Charcoal, 60 bytes

≔↔⁻ＮＥφ⁺×¹¹·²⁵﹪ι¹⁶×⁸÷ι¹⁶θ≔Ｅ⌕Ａθ⌊θ…⮌⊞Ｏ↨⁺¹⁶ι²÷ι¹⁶¦⁵θＩ⊟Φθ⁼Σι⌊ＥθΣλ


Try it online! Link is to verbose version of code. Outputs using Charcoal's default array format i.e. each element on its own line. Explanation:

≔↔⁻ＮＥφ⁺×¹¹·²⁵﹪ι¹⁶×⁸÷ι¹⁶θ


Calculate the possible angles using sets of up to 999 8° fittings and optionally one each of each of the other fittings, and see how closely they compare to the input.

≔Ｅ⌕Ａθ⌊θ…⮌⊞Ｏ↨⁺¹⁶ι²÷ι¹⁶¦⁵θ


Find the indices of the most accurate sets and calculate the fittings corresponding to each of those indices.

Ｉ⊟Φθ⁼Σι⌊ＥθΣλ


Output the last set with the fewest fittings.