# Conversions Galore!

Imagine that there are $$\n\$$ different types of objects $$\O_1,O_2,O_3,\ldots,O_n\$$ and they each have a conversion factor $$\k_1,k_2,k_3,\ldots,k_n\$$. You can, for any $$\1\le i\le n\$$, convert $$\k_i\$$ amount of $$\O_i\$$ into $$\1\$$ of any other type of object.

Your objective is to output all the possible ending configurations of the amount of each of the $$\n\$$ objects after all possible conversions have been made, given the initial amount of each object $$\A=a_1,a_2,a_3,\ldots,a_n\$$ and a list $$\K\$$ of the conversion factor of each object. Duplicate outputs are not allowed. It is guaranteed that all conversion factors are greater than $$\1\$$ to prevent infinite conversions.

# Example

Let's say that the amount of each object is A=[4,1,0] and the conversion factors are K=[2,3,4].

One way to go about converting each of these is to first convert all the $$\O_1\$$'s into $$\O_3\$$'s, resulting in [0,1,2]. We can also convert some of the $$\O_1\$$'s to $$\O_2\$$'s and the rest to $$\O_3\$$, resulting in [0,2,1].

But if we convert all the $$\O_1\$$'s to $$\O_2\$$'s, we get [0,3,0], which can still be reduced. From [0,3,0] we can either convert to $$\O_1\$$ or $$\O_3\$$, resulting in [1,0,0] and [0,0,1] respectively.

So the final output would be:

[0,1,2]
[0,2,1]
[1,0,0]
[0,0,1]


# Test Cases

A, K ->
output

[4,1,0], [2,3,4] ->
[0,1,2]
[0,2,1]
[1,0,0]
[0,0,1]

[99,99,99], [99,100,100] ->
[1,0,99]
[1,99,0]
[1,0,0]
[0,1,0]
[0,0,1]

[3,0,0], [3,3,3] ->
[0,1,0]
[0,0,1]

[3,0,0,3], [3,3,3,3] ->
[0,0,1,1]
[0,1,0,1]
[1,0,0,1]
[0,1,1,0]
[1,0,1,0]
[1,1,0,0]
[0,0,2,0]
[0,2,0,0]

[4,5], [3,3] ->
[0,1]


If you want to generate more test cases, check out this reference implementation that I wrote (if you find any bugs in it, please tell me! I'm not 100% sure that it's right...).

This is , so the shortest code in bytes wins!

• @97.100.97.109 Ummm... not sure what you mean by that. I'm just saying that there are $n$ objects (they can be apples, bananas, books, anything you can think of) and that you can "convert" $k_i$ of some object $O_i$ to any one of the other objects. The wording itself isn't too important to the challenge anyways, you can think of them however you want. Oct 23, 2022 at 1:18
• Can we output duplicate elements? Oct 23, 2022 at 21:19
• @AZTECCO No. I will clarify that in my post, but if you look in my reference implementation, you can see a section of the code dedicated to removing duplicates. Oct 23, 2022 at 21:52

# Charcoal, 56 bytes

⊞υθＦυＦΦＬι¬‹§ικ§ηκＦ⁻ＥΦＬι⁻λκＥι⎇⁼ξκ⁻ν§ηκ⁺ν⁼ξλυ⊞υλＩΦυ⬤ι‹λ§ημ


Try it online! Link is to verbose version of code. Explanation:

⊞υθ


Start a breadth-first search for reachable configurations.

Ｆυ


Loop over the reachable configurations as they are found.

ＦΦＬι¬‹§ικ§ηκ


Loop over the available conversion sources.

Ｆ⁻ＥΦＬι⁻λκＥι⎇⁼ξκ⁻ν§ηκ⁺ν⁼ξλυ


Loop over the possible conversion destinations, generating the resulting configurations, but exclude previously seen configurations.

⊞υλ


Save the new configuration for further processing.

ＩΦυ⬤ι‹λ§ημ


Output only the ending configurations.

# Python 3, 175 173 bytes

def g(a,b,r,t=1):
A=enumerate(a)
for i,x in A:
for j,y in A:
if(i!=j)*x>=b[i]:c=[*a];c[i]-=b[i];c[j]+=1;t=g(c,b,r)
if t:r+=[(*a,)]
def f(a,b):g(a,b,r:=[]);return{*r}


Attempt This Online!

Returns the set of arrays (as tuples).

• The output in the 140 byte version doesn't seem to be matching the test cases, and the 173 byte version straight up isn't working (even after switching the language to 3.8+), though I think it's a problem with the test suite, not your actual code. Oct 23, 2022 at 21:56
• @AidenChow I've removed the in-place version, and fixed the test cases for the other one. I'm not quite sure why the in-place version doesn't work still... Oct 28, 2022 at 21:29

# Python3, 225 bytes:

E=enumerate
def f(a,b):
q,s=[a],[a]
while q:
a,F=q.pop(0),0
for j,k in E(a):
if k>=b[j]:
F=1
for i,A in E(a):
Y=eval(str(a));Y[j]-=b[j];Y[i]+=1
if Y not in s and i!=j:q+=[Y];s+=[Y]
if 0==F:yield a


Try it online!

• 206 Oct 23, 2022 at 4:03
• It can actually be 204 by removing the parens around i:=i+1 if you use a newer version: ATO Oct 23, 2022 at 4:04
• @Sʨɠɠan Thank you for the suggestions, but the output from those links is not correct. Oct 23, 2022 at 4:09
• Ah oops, sorry. Changing i!=j to i-1!=j works. I forgot that I incremented the variable first. Oct 23, 2022 at 4:11

# JavaScript (ES6), 109 bytes

Expects (K)(A). Returns a set of strings.

(K,s=new Set)=>g=A=>K.map((v,i)=>A[i]<v||A.map((_,j,[...B])=>j-i&&g(B,B[i]-=v,A.u=++B[j])))|A.u?s:s.add(A+'')


Try it online!

import Data.List
f v i l=take i l++v+l!!i:drop(i+1)l
o!k|l<-[0..length o-1]=nub$(#k)=<<[f 1j$f(0-k!!i)i o|j<-l,i<-l,o!!i>=k!!i,j/=i]
e#k|e!k>[]=e!k|1>0=[e]


Try it online!

• Imported Data.List for removing duplicates using nub.
• f modify element in list at i
• o!k converts k*1 of each o in every ways
• e#k returns e if not convertible, else apply ! again

# Pyth, 51 bytes

DydI!s/VdQRaYdVldVldI&nNHg@dN@QN yXHXN=Gd_@QN1;yE{Y


Try it online!

### Explanation

Dyd                                                    define y(d)
I!s/VdQRaYd                                         if no conversions left, put d in Y and end function
Vld                                      for N in range(len(d))
Vld                                   for H in range(len(d))
I&nNHg@dN@QN                       if N!=H and d[N] is large enough to be converted
yXHXN=Gd_@QN1;        convert type N to type H and recursively call y on the new list
yE      call y on the input list
{Y    remove duplicates from the output Y