given some small and big numbers, make desired number - without loops

I'm solving the coding problems on codingbat in Python. The make_bricks problem is defined as:

We want to make a row of bricks that is goal inches long. We have a number of small bricks (1 inch each) and big bricks (5 inches each). Return True if it is possible to make the goal by choosing from the given bricks. This is a little harder than it looks and can be done without any loops.

make_bricks(3, 1, 8) → True
make_bricks(3, 1, 9) → False
make_bricks(3, 2, 10) → True

The first solution I came up with was:

from itertools import permutations

def make_bricks(small, big, goal):
    l = small*[1]+big*[5]
    return any([(goal in i) for i in ([[sum(j) for j in set(permutations(l,i))] \
    for i in range(2,len(l)+1)])])

Which is correct but got rejected by the judging software because imports are not allowed. So my next solution was:

def make_bricks(small, big, goal):
    bricks = small*[1]+big*[5]
    for step in range(len(bricks)+1,1,-1):
        for start in range(len(bricks)):
            if len(bricks[start:start+step])==step:
                if sum(bricks[start:start+step])==goal:
                    return True
    re开发者_如何学编程turn False

Which is also correct, but choked with a time-out on input like make_bricks(1000000, 1000, 1000100).

So, how would you solve this problem in Python, without using imports, without using loops and in the time-limit?

---

def make_bricks(small, big, goal):
  if goal > small + big * 5:
    return False
  else:
    return goal % 5 <= small

---

This is a math problem. Say you have S small bricks and B big bricks and you want a length L block.

You can use K = min(B, L div 5) big bricks, and L - 5K small bricks, so you just need to check if you have enough small bricks.

div is integer division (floor).

EDIT changed L-K to L-5K. typo.

---

Keep in mind, that you only have to reach the final size. Therefore, it does not matter at all in which order you place the bricks.

The next important idea then is to use 5-inch bricks whenever possible. You cover 5 inches if you use one of those, as well as if you use 5 of the 1-inch bricks. Hence, using up just one brick is preferable.

Now you're already done really: Check the maxmium length you can create with your given 5-inch bricks, until you either run out of 5-inch bricks or you have less than 5-inch missing for your target length. Either way, there is some distance missing, which you will have to fill up with the remaining 1-inch bricks.

I won't give any code here, because it's really a very simple problem and from what you have written above you should be easily able to solve it, once you understand how.

---

Not so difficult when you have single unit items and only one larger size items as you can always fill as many as you can with the larger ones.

Harder if you have quarters and dimes and try to make an amount exactly with them, eg if you have to make 55c you fail if you start with 2 quarters even though it is less than the target.

There are, of course other combinations you might have that will make the problem even more complex than "don't go closer than the amount - the smallest unit you have".

If you solve the congruent equation (Ax + By) % AB = C and you can always get more equations using A(x+B) + B(y-A) which will also equal to C so you can get around the limited quantity you have of your bricks / coins or whatever.

An example of an congruent equation is something like (7x + 9y) %63 = 47 and you can write a function to solve these. We break down to lowest terms so assume A and B are co-prime or reduce it by the HCF.

There is a unique solution with x= 0. In this case we will actually end up with x=8, y=6, each one at its maximum value 56+54=110 which is congruent to 47 mod 63 so if the target actually is 47 it is not solvable with any number of 7s and 9s.

If the target is 110 it can be solved if we have 8 bricks of 7 and 6 of 9. Otherwise there is no solution.

If the target is higher there will be multiple solutions with unlimited bricks but the number of 9 bricks we will require will always be 8 mod 9 so will be 8, 17, 26, etc. We take the highest number we have that fits this category and try to fill the rest with 7 bricks. If we have them we can make our target. If we have 33 bricks of 9, we must use 26 of them.

That is your algorithm once you have solved the congruency.

---

You can fill a size-5 hole with 1s or 5s, but you can only fill a less-than-five hole with 1s. For example: to make 19, you must have at least 4 1s - it doesn't matter if you have 100 5s, if you only have 3 1s you are out of luck.

So the trick is to see if you have enough 1s to fill the remainder-from-5, then enough 5s and 1s left over to make up the rest.

def make_bricks(small, big, goal):
  # minimum number of 1s needed
  rem = goal % 5   # ex: 19 % 5 == 4

  if rem > small:
    # too few 1s
    return false
  else:
    # we have enough 1s; deduct what we just used
    small -= rem
    goal -= rem

    # now see if what's left will fill the rest of the hole
    return small + 5*big >= goal

Hope that makes sense to you!

---

def make_bricks(s,b,g):
  return not(g>b*5+s or g%5>s)

s = small | b = big | g = goal

---

n=int(goal/5)

if goal>small+big*5: return False elif (goal<=small+big*5): if goal>n*5+small:
return False
else: return True

---

Here's the solution I came up with - not as condensed at this can get, but logic'd through easily enough:

def make_bricks(small, big, goal):
  if int(goal/5) < big:
    big -= big - int(goal/5)
  return big*5 + small >= goal

---

def make_bricks(small, big, goal):
    qu = goal/5
    rem = goal%5
    if big*5 <= goal and big*5 +small>= goal:
        return True
    else:
        return qu <= big and rem <= small

"I think we look like quotient and reminder of goal inches "