Challenge: Find the minimum amount of draws possible for a list of integers

[RaamGeneral]

TL;DR Summary

given a list of integers, find the minimum value of a certain property given by pairing the elements

Hello. Sorry if the title is a bit vague.

I'm doing this challenge (google foobar) and even though it's not very elegant to ask for help, it's not like I'm going to win any kind of prize for it. In any case I'd like some suggestions since my current solution fails 2 tests on 5. The most probable reasons might be:
- the algorithm is not correct (maybe it doesn't correctly evaluate some cases)
- the algorithm is too slow, which I'm pretty sure it is.

Given any two integers $a$ and $b$, suppose that $a<b$, and consider the function $f(a,b)=(2a, b-a)$. There are certain pairs such that repeated applications of $f$ produce a loop of results. I discovered that this does not happen when $$\frac{a}{a+b}=\frac{\mathrm{odd_number}}{2^k}$$ with $a/(a+b)$ reduced to their lowest terms: in this case I say that the pair (two elements) ends up in a draw.

The problem: you're given a list of non negative integers and must find the minimum amount of draws possible. I suppose that if the list contains an odd number of elements, one will never be paired and may be considered a draw too (one element).

For this problem I couldn't get a better algorithm than this one, although I tried a few other ways which made not much difference in run time (for certain cases).

def find_least_draws(seq):
    n = len(seq)
    if n <= 1:
        return n

    R = n
    for i in range(1, n):
        if seq[0] == seq[i]:
            continue

        # it returns 0 or 2
        A = does_draw(seq[0], seq[i])
        new_seq = [el for j, el in enumerate(seq) if j != 0 and j != i]
        B = find_least_draws(new_seq)
        C = A + B
        if C == n % 2:
            return C

        if C < R:
            R = C
            
    return R

I tried to avoid creating new lists (new_seq) and other "traversal strategies", but actually I'm still not sure where (if) the trick is (maybe to decrease the amount of possible checks/computations to make). I kind of see that this problems may have something to do with graphs or trees, but I don't find it simple to visualize the correct structure. I also have found a "matrix" representation, but again I'm not sure how to best manipulate such matrix to achieve the result.

A small suggestion is welcome. Thank you.

 

[anuttarasammyak]

$$f(a,\ b)=(2a,\ ba)$$
$$f^2(a,b):=f(f(a,\ b))=(4a,\ b-3a)$$
$$f^3(a,\ b)=(8a,\ b-7a)$$
$$f^n(a,\ b)=(2^na,\ b-(2^n-1)a)$$

 

[willem2]

- the algorithm is too slow, which I'm pretty sure it is.
I discovered that this does not happen when $$\frac{a}{a+b}=\frac{\mathrm{odd_number}}{2^k}$$ with $a/(a+b)$ reduced to their lowest terms: in this case I say that the pair (two elements) ends up in a draw.

We need some examples here. what happens if 2a becomes greater thant b-a, do you then exchange an and b? i don't see when a pair draws.

It does seem like the computation of does_draw() is the problem. You could use a table or the @cache function decorator to not compute this function over and over

Your recursion seem to use about n (n-2)(n-4) ..... 4. 2 steps for even n.

It can be made faster by only using the pairs that do draw in the recursion. We are only interested in finding pairs that draw.

You start the recursion by what you do now: finding a partner seq for seq[0], but now you only do the recursion if they do draw.
If seq[0] does not draw with anyone, you can just call find_least_draws() with a sequence without seq[0]
in it.

This should go much faster if there are more non draws than draws.

Another thing you could try is to check if the graph of the drawing numbers is connected, and if not, separate them, and compute the maximum number of draws for the different components separately.
It would be nice to have an example here too, of a list of numbers and the maximum amount of draws.

 

[RaamGeneral]

You're right about the function, I should show some examples or be more clear. In fact I was unprecise
f(a, b) = (2a, b-a) if a<b
(a-b, 2b) if b<a

Examples:
not does_draw:
0: (4, 6)
1: (8, 2)
2: (6, 4)
3: (2, 8)
4: (4, 6)

does_draw:
0: (3, 5)
1: (6, 2)
2: (4, 4)I'm pretty positive that the function does_draw is correct since it got extensive testing and theoretical-backed argument (I threw away the notes though, but they start as with @anuttarasammyak)As for @willem2 reply, I will have to read it carefully later.

 

[anuttarasammyak]

f(a, b) = (2a, b-a) if a<b
(a-b, 2b) if b<a

if a=b, f(a,a)= ?

 

[RaamGeneral]

For the context of this problem f(x, x) is undefined, but does_draw still works as expected. In fact a pair may either produce a loop of results (never reaching any (x, x)) or end up in (x, x), which is what does_draw lets us know (it can do of course by generating and inspecting results of application of f, or by the odd_number/2^k rule).

 

[pbuk]

Google use Foobar for sifting potential employees. This is not something that we should be doing here, and PF has no rights to publish the details of Foobar questions.

 

[anuttarasammyak]

Examples:
not does_draw:
0: (4, 6)
1: (8, 2)
2: (6, 4)
3: (2, 8)
4: (4, 6)

does_draw:
0: (3, 5)
1: (6, 2)
2: (4, 4)

A preliminary observation
Odd numbers can appear in 0: only.
If Max(a,b)/Min(a,b)=2 then in next next step it loops back.
If Max(a,b)/Min(a,b)=3 then in next step it draws.

 

[berkeman]

Google use Foobar for sifting potential employees. This is not something that we should be doing here, and PF has no rights to publish the details of Foobar questions.

Thread closed temporarily for Moderation...

 

[berkeman]

I'm doing this challenge (google foobar) and even though it's not very elegant to ask for help, it's not like I'm going to win any kind of prize for it.

After a Mentor discussion, the thread will remain closed.