11
\$\begingroup\$

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.

Task

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!

\$\endgroup\$
3
  • \$\begingroup\$ @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. \$\endgroup\$
    – Aiden Chow
    Oct 23, 2022 at 1:18
  • \$\begingroup\$ Can we output duplicate elements? \$\endgroup\$
    – AZTECCO
    Oct 23, 2022 at 21:19
  • \$\begingroup\$ @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. \$\endgroup\$
    – Aiden Chow
    Oct 23, 2022 at 21:52

6 Answers 6

3
\$\begingroup\$

Charcoal, 56 bytes

⊞υθFυFΦL鬋§ικ§ηκF⁻EΦLι⁻λκEι⎇⁼ξκ⁻ν§ηκ⁺ν⁼ξλυ⊞υλIΦυ⬤ι‹λ§ημ

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

⊞υθ

Start a breadth-first search for reachable configurations.

Fυ

Loop over the reachable configurations as they are found.

FΦL鬋§ικ§ηκ

Loop over the available conversion sources.

F⁻EΦLι⁻λκEι⎇⁼ξκ⁻ν§ηκ⁺ν⁼ξλυ

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

⊞υλ

Save the new configuration for further processing.

IΦυ⬤ι‹λ§ημ

Output only the ending configurations.

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

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

\$\endgroup\$
3
  • 2
    \$\begingroup\$ 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. \$\endgroup\$
    – Aiden Chow
    Oct 23, 2022 at 21:56
  • \$\begingroup\$ @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... \$\endgroup\$ Oct 28, 2022 at 21:29
  • \$\begingroup\$ You forgot to include the TIO link in your answer. \$\endgroup\$
    – Aiden Chow
    Oct 28, 2022 at 22:21
1
\$\begingroup\$

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!

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

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!

\$\endgroup\$
1
\$\begingroup\$

Haskell, 155 bytes

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
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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