[Simown]

This challenge comes via jon.kiparsky, so thanks to him for suggesting it. It's based on based on problem set 2 of the MIT opencourseware Python course, the "McNuggets" problem, with a suitable twist, of course!

The question is, given an equation of the form:

ax+by+cz+... = N

where all quantities are integers, what is the maximal value of N which is not a solution?

So, in terms of the original problem, if I sell zombie fingers in packs of 6, 9, and 20, it's clear that you can't buy exactly 19 fingers without bribing me to slip an extra into one pack. It's also clear that you can easily buy 52 zombie fingers, by buying two packs of 20 and two of 6. What is the largest number of zombie fingers that you can't buy as an exact quantity?

The general problem, and the challenge, is to write the most efficient program to determine the maximal non-solution N for any arbitrary list of coefficients, where the list can be of any length.

Various rules:
* Any language will be accepted, but Python is prefered
* Python 2 or 3 is fine for the Python entries
* Anyone submitting a solution please use SPOILER tags
* I'd ask for Python experts to hold off a bit before posting a solution, to give other people a shot - please do show interest though, and discussion is always welcome.
* Any questions, just use this forum. No PMs please, everyone should benefit!
* You'll be pleased to hear, the Simown constraint is not in effect in this challenge.

And finally, good luck! Happy challenging!

This post has been edited by Simown: 31 October 2012 - 02:39 PM

[jon.kiparsky]

Thanks for posting this, Simown. Just a quick technical note: as I wrote it, this is a function which takes a tuple of coefficients and returns a number. I actually return a tuple, the second member of which is the number of times it hit my inner loop, which is a useful indicator of efficiency.

That is, to represent 6a + 9b + 20c= n, I use the tuple (6, 9, 20), and I return (43,12), meaning I found this in 12 hits of the inner loop. The latter number is not important to a solution, but it might serve as a useful target.

There is a brute-force approach to this problem, which scales appallingly badly. This is worth writing, but you can do better. If you want to do better, and you can't see the way in, there's a good hint (possibly unintentional) in the original problem set.

Quote

* I'd ask for Python experts to hold off a bit before posting a solution, to give other people a shot - please do show interest though, and discussion is always welcome.

I like this idea, but I don't know what the correct value for "a bit" should be. This is a small program, so I'd think a day or two should be enough for anyone to find the time to write it, but then I've already written it, so what do I know?

Suggestions would be welcome.

Finally, I suspect that there is a closed-form solution to this general problem, and that it may be known. I say this based on the fact that it smells like a solveable problem, and that it seems the sort of problem someone would have solved. In fact, it was looking for that closed-form solution that led me to the algorithm that I used, which is (I think) a pretty good one.
Clearly, finding and implementing this closed-form solution would be a good way to win this challenge.

[Simown]

I think "a bit" is subjective, imagine you were new to programming? It could take you a whole weekend or longer to write this program, even a brute force one perhaps, and we want it to be accessable - I think if people showed their interest by posting, and then give it a day or two while they cook up a solution.

I'm going to post a solution over the weekend some time, it's a really nice problem actually, is there an accessible list of these somewhere?

I don't *think* the distinction of taking a tuple or a list is important to the algorithm if you aren't going to change the parameter in any way just indexing it, the difference to speed, I don't know - but it will be tested in the same manner.

[jon.kiparsky]

Right, it's not critical that it be a tuple or a list or a set, since they're all interchangeable anyway. My point there, which I didn't get across very clearly, is that the representation of the equation is simply the set of coefficients. I remember that when I first tried to solve this sort of problem, the representation was always a hard hurdle, so this might help someone to get to the actual problem.

[Python_4_President]

It's easy for me to get 19 zombie fingers from you. Order 2 packs, and cut one off the delivery man!!!
But seriously, I don't know that I could solve this problem... Hmmmmm...... or can I?

[jon.kiparsky]

Quote

It's easy for me to get 19 zombie fingers from you. Order 2 packs, and cut one off the delivery man!!!

You got zombie delivery men? Rough neighborhood...

Quote

But seriously, I don't know that I could solve this problem... Hmmmmm...... or can I?

Yes, I think you can. Start by developing a brute-force solution. If nothing else, this will help you sort out the issues in play, and give you ideas for a better way.

[Python_4_President]

jon.kiparsky, on 31 October 2012 - 07:26 PM, said:

Quote

It's easy for me to get 19 zombie fingers from you. Order 2 packs, and cut one off the delivery man!!!

You got zombie delivery men? Rough neighborhood...

Quote

But seriously, I don't know that I could solve this problem... Hmmmmm...... or can I?

Yes, I think you can. Start by developing a brute-force solution. If nothing else, this will help you sort out the issues in play, and give you ideas for a better way.

hahaha.. I think I got it, actually. It definitely won't win any speed tests, but it takes arbitrary packing structures.

Yes, I believe I have one of the worst solutions to the "Appallingly badly" scaling one.

Spoiler

def calc(packages, looping_vals):
    packlen = len(packages)
    return sum([packages[i]*looping_vals[i] for i in range(packlen)])

def gen_for(packages, maxVal):
    iNeed = len(packages)
    c = """def calc(packages, looping_vals):
    packlen = len(packages)
    return sum([packages[i]*looping_vals[i] for i in range(packlen)])\n\n\n"""
    d = ""
    c += "ld = []\n"
    c += "maxVal = {0}\n".format(maxVal)
    c += "for n in range(1, maxVal):\n"
    for i in range(0, iNeed):
        c += (" "*4)*(i+1)+"for x{0} in range(n):\n".format(i)
        d += "x{0},".format(i)
    d = "["+d.rstrip(",")+"]"
    c += (" "*4)*(i+2)+"comb = calc({0}, {1})\n".format(packages, d)
    c += (" "*4)*(i+2)+"if n == comb:\n"
    c += (" "*4)*(i+3)+"if n not in ld:\n"
    c += (" "*4)*(i+4)+"print 'You can buy {0}'.format(n)\n"
    c += (" "*4)*(i+4)+"ld.append(n)\n"
    c += "print 'The biggest number (up to {0}) that you cannot buy is: {1}'.format(maxVal, sorted([x for x in range(maxVal) if x not in ld and x], reverse=True)[0])"
    return c 
  
def fixMyPackingProblem(packages, maxVal):
    exec(compile(gen_for(packages, maxVal), "<String>", "exec"))

if __name__ == "__main__":
    fixMyPackingProblem((6, 9, 20), 40)

I wrote that while fighting zombies, btw.

This post has been edited by Python_4_President: 31 October 2012 - 09:16 PM

[jon.kiparsky]

Excellent. Once again, you'll notice that I was right.
Looking forward to seeing it!

[Python_4_President]

You should definitely check inside the spoiler then.

[jon.kiparsky]

I'm curious to know how you came up with that upper limit...

[Python_4_President]

You mean 40? I tried a couple dozen different values, then thought I'd try 400, but it would probably take 6 hours or so to complete, so I removed a 0. 40.

[jon.kiparsky]

I see a wee hitch in your getalong there, in that your solution requires you to know the answer in advance. For example, if you knew in advance that no solution could be found for 43, you might have set your threshold a little higher and got a different result. Fortunately there's a way to know when you've reached a maximal value - it's outlined in the original problem set.

[Python_4_President]

Huh...

I'm guessing there's more to what you just said than I realize at this time. I'll check it out more tomorrow, but if I understand correctly, there's not anything logical stopping you from setting maxVal to infinity (or a close approximation thereof). You'll need lots of RAM, though, and will probably want to switch to xrange in the for loops.


Wait a tic... I know what you're talking about. I noticed that after a while, pretty much every value was possible. I kept figuring, "Surely there must be SOME big value of N out there that isn't exactly composed of the available pack quantities."

Maybe there isn't... hmm...

This post has been edited by Python_4_President: 31 October 2012 - 10:50 PM

[Simown]

It's not usually a huge number (and it will be a finite number if all the coefficients don't share a common divisor except 1!). As was rightly suggested much of it is figuring out the threshold value in advance, so you don't have to guess perhaps and brute-force it.

I say that like it's easy, I'm still thinking up a solution

This post has been edited by Simown: 01 November 2012 - 06:22 AM

[jon.kiparsky]

The other thing to think about is that at any point there is a positive test to see if you have hit the end. Looking at the original MIT OCW problem set, you'll find that test is described there. So if the set of terms you're looking at does in fact terminate, there is a way to know that it has terminated. Although you won't know until some point after that has happened, you will know from the outset how far past the termination you have to go.