5
\$\begingroup\$

One of your acquaintances has a hobby of making make-shift electrical gadgets using various types of batteries. However, since they're thrifty, they want to use as few batteries as possible for their projects. This challenge uses several types of batteries; your job is to output the fewest number of batteries that will output a given voltage when chained together.

The batteries you'll be using

Here are the types of batteries you will be using, along with their ID numbers (I assigned those for this challenge) and their output voltages:

  1. AA 1.5V
  2. Button battery 3V
  3. Li-ion battery 3.7V
  4. 9V battery 9V
  5. Car battery 12V

Batteries can also be half-charged, meaning that their voltage is half of what it is fully charged (I've removed any batteries who's half-voltages are the voltages of any full batteries):

  1. ½ AA .75V
  2. ½ Li-ion 1.85V
  3. ½ 9V battery 4.5V
  4. ½ Car battery 6V

The rules

  • Input i must be a float where 1 ≤ i ≤ 100, and where i has 1 or 2 decimal digits.
  • Output must be a list of the fewest number of battery ID numbers (as listed above) that, when combined, will output the voltage, or an empty list (or any other empty value) if the voltage can't be produced using the above batteries. Alternatively, the list can consist of the voltages of the batteries used; however, the voltages must correspond with one of the batteries above.

Here are some test cases (the numbers aren't very large right now because of the time it takes to run the code for large numbers):

input: 1.5
output: [1.5]

input: 2
output: [] or None

input: 7.5
output: [6, 1.5]

input: 15
output: [12, 3]

This is a challenge, so the fewest bytes wins!

\$\endgroup\$
18
  • \$\begingroup\$ 3.7 != 2*1.875: did you mean 3.75 instead? \$\endgroup\$ Mar 28 at 18:15
  • 1
    \$\begingroup\$ This makes the 1/2 Li-ion only as 9.25 \$\endgroup\$
    – l4m2
    Mar 28 at 18:45
  • 2
    \$\begingroup\$ Can you please clarify in the spec what it means for batteries to 'make up' a voltage? \$\endgroup\$
    – chunes
    Mar 28 at 18:51
  • 2
    \$\begingroup\$ @SylvesterKruin It is still not clear to me, as I am not well-versed in physics. Is the final voltage simply the sum of the voltages of the batteries that are chained together? \$\endgroup\$
    – chunes
    Mar 28 at 18:56
  • 2
    \$\begingroup\$ Please consider provide some testcases so everyone may test their answers. \$\endgroup\$
    – tsh
    Mar 29 at 1:54

6 Answers 6

3
\$\begingroup\$

JavaScript (Node.js), 98 bytes

f=(v,s=[],...y)=>s[v*7|0]?'':eval(s)+v?f(v,...y,...[1.5,3,3.7,9,12,.75,1.85,4.5,6].map(e=>s+-e)):s

Try it online!

Return voltages splitted by -

f=(v,s=[],...y)=> // s,...y as testing buffer
    s[v*7|0]?'':  // The longest outputLength/input case, -0.75, need *6.67
    eval(s)+v?    // not equal?
        f(        // continue
            v,
            ...y,
            ...[1.5,3,3.7,9,12,.75,1.85,4.5,6].map(e=>s+-e))
    :s
\$\endgroup\$
8
  • \$\begingroup\$ The spec (currently) says we must output an empty list if not possible - this keeps recursing - 3.25 for example. \$\endgroup\$ Mar 28 at 18:44
  • \$\begingroup\$ @SylvesterKruin Yes this requires lots of memory and time to return an empty list because I stop loop only using s[v*99|0] \$\endgroup\$
    – l4m2
    Mar 28 at 18:46
  • \$\begingroup\$ @JonathanAllan Get enough RAM and enough patience, 3.25 would take 10^70 time and memory \$\endgroup\$
    – l4m2
    Mar 28 at 18:49
  • 1
    \$\begingroup\$ @JonathanAllan this usually require lots of stack \$\endgroup\$
    – l4m2
    Mar 28 at 18:52
  • 3
    \$\begingroup\$ Probably worth explicitly stating the quirks in your answer :) \$\endgroup\$ Mar 28 at 18:56
2
\$\begingroup\$

Python, 170 169 bytes

from itertools import*
f=lambda i:next(filter(None,(next((x for x in product([1.5,3,3.75,9,12,.75,1.85,4.5,6],repeat=n)if sum(x)==i),0)for n in range(int(i/.75)+2))),())

Attempt This Online!

10 bytes could be saved by replacing range(int(i/.75)+2) with range(41), but then it may not find the correct solution if i>30. I prefer the longer version, since it is correct for any (numeric) input.

Note: it is extremely inefficient, but it eventually terminates for every input.

\$\endgroup\$
2
\$\begingroup\$

05AB1E, 25 bytes

•UyмµñFb₃^•₅в20/₃иæé.ΔOQ

Outputs a list of the voltages of the batteries, and -1 if it can't find a result.

(Don't) try it online. (Will time out for all test cases.)

If we remove the é it can be somewhat tested, but it won't output the required shortest result anymore: try it online. (And might still time-out.)
And with only •UyмµñFb₃^•₅в20/₃иæ we can see all the possible powerset lists: try it online.

Explanation:

•UyмµñFb₃^•     # Push compressed integer 540570253786318174620
 ₅в             # Convert it to base-255 as list: [30,60,74,180,240,15,37,90,120]
   20/          # Divide each by 20: [1.5,3,3.7,9,12,0.75,1.85,4.5,6]
      ₃и        # Cycle-repeat this list 95 times
                # (95 is the lowest 1-byte constant above 40, which is required to
                # reach the maximum to support input 30 with the lowest voltage 0.75)
        æ       # Pop and push its powerset
         é      # Sort it by length
          .Δ    # Find the first inner list which is truthy for:
                # (or -1 if none were truthy)
            O   #  Sum the list
             Q  #  Check if it's equal to the (implicit) input-float
                # (after which the result is output implicitly)

See this 05AB1E tip (sections How to compress large integers? and How to compress integer lists?) to understand why •UyмµñFb₃^• is 540570253786318174620 and •UyмµñFb₃^•₅в is [30,60,74,180,240,15,37,90,120].

\$\endgroup\$
2
\$\begingroup\$

Python 3.8 (pre-release), 126 bytes

Recursive brute-force solution.
Throws exception if no solution is found.

lambda n:(g:=lambda i,s=0,l=[]:[l]*(s==i)if s>=i else[b[0]for a in[12,9,6,4.5,3.7,3,1.85,1.5,.75]if(b:=g(i,s+a,l+[a]))])(n)[0]

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Python 3 (PyPy), 95 bytes

Returns a singleton list containing the solution. Based on friddo's answer.

f=lambda i,*l:sum([f(i,*l,ord(b)/20)for b in'ð´xZJ<%'],[])[:1]if i>sum(l)else[l][sum(l)>i:]

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ Woah, can you please explain that cryptic string? \$\endgroup\$
    – friddo
    Mar 29 at 9:39
  • \$\begingroup\$ @friddo If you multiply the voltage values by 20 you get integers. Each character in the string represents such a voltage*20 by its unicode codepoint. \$\endgroup\$
    – ovs
    Mar 29 at 10:13
  • \$\begingroup\$ ah!, that makes sense \$\endgroup\$
    – friddo
    Mar 29 at 10:20
2
\$\begingroup\$

Vyxal, 29 bytes

» 3J↔kṫ₅uR»₈τ20/41ẋfṗÞṡ'∑⁰=;h

Don't try it online! (it times out)

Add vøḋ to the end if it can't be returned as list of rationals instead of decimals. vøḋ will return a list of strings, tho. Returns 0 if it can't find a solution.

You can somewhat test it without the Þṡ, but it won't return the optimal answer: Try it Online!

Extremely slow.

Port of 05AB1E.

How?

» 3J↔kṫ₅uR»                   # Push compressed integer 557746805944978070136
           ₈τ                 # Convert to base 256: [30, 60, 74, 180, 240, 15, 37, 90, 120]
             20/              # Divide each by 20: [1.5, 3.0, 3.7, 9.0, 12.0, 0.75, 1.85, 4.5, 6.0]
                41ẋ           # Repeat that list 41 times: [[1.5, 3.0, ...], [1.5, 3.0, ...], ...]
                   f          # Flatten it: [1.5, 3.0, ..., 1.5, 3.0, ..., ...]
                    ṗ         # Powerset
                     Þṡ       # Sort by length (this is what slows it down so much)
                       '   ;  # Filter for:
                        ∑⁰=   # The sum of this list is equal to the input
                            h # Get the first item
\$\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.