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

  • #1
RaamGeneral
50
1
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).

Python:
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.
 
Technology news on Phys.org
  • #2
[tex]f(a,\ b)=(2a,\ ba)[/tex]
[tex]f^2(a,b):=f(f(a,\ b))=(4a,\ b-3a)[/tex]
[tex]f^3(a,\ b)=(8a,\ b-7a)[/tex]
[tex]f^n(a,\ b)=(2^na,\ b-(2^n-1)a)[/tex]
 
Last edited:
  • #3
RaamGeneral said:
- 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.
 
  • #4
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.
 
  • #5
RaamGeneral said:
f(a, b) = (2a, b-a) if a<b
(a-b, 2b) if b<a
if a=b, f(a,a)= ?
 
  • #6
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).
 
  • #7
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.
 
  • #8
RaamGeneral said:
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.
 
  • #9
pbuk said:
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...
 
  • #10
RaamGeneral said:
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.
 

1. What is the main goal of the challenge?

The main goal of this challenge is to find the minimum number of draws needed to guarantee that every integer in a given list will be drawn at least once.

2. How do you calculate the minimum number of draws?

The minimum number of draws can be calculated by taking the total number of integers in the list and adding one. This guarantees that each integer will be drawn at least once, no matter the order in which they are drawn.

3. Can the minimum number of draws be less than the total number of integers in the list?

No, the minimum number of draws will always be equal to or greater than the total number of integers in the list. This is because each integer must be drawn at least once, and each draw can only uncover one integer.

4. Are there any scenarios where the minimum number of draws may be greater than the total number of integers in the list?

Yes, this can happen if there are duplicate integers in the list. In this case, the minimum number of draws will be equal to the total number of distinct integers in the list, not including any duplicates.

5. Is there a specific order in which the integers should be drawn to achieve the minimum number of draws?

No, the order in which the integers are drawn does not affect the minimum number of draws. As long as each integer is drawn at least once, the minimum number of draws will be the same.

Similar threads

  • Programming and Computer Science
Replies
4
Views
927
  • Programming and Computer Science
Replies
17
Views
980
  • Programming and Computer Science
Replies
29
Views
1K
  • Programming and Computer Science
Replies
34
Views
2K
  • Programming and Computer Science
Replies
1
Views
1K
  • Programming and Computer Science
3
Replies
97
Views
7K
  • Programming and Computer Science
Replies
12
Views
1K
  • Programming and Computer Science
3
Replies
75
Views
4K
  • Programming and Computer Science
Replies
2
Views
2K
  • Programming and Computer Science
Replies
5
Views
1K
Back
Top