# Halloween Python Challenge

• (2 Pages)
• 1
• 2

## 26 Replies - 9036 Views - Last Post: 10 November 2012 - 11:17 AMRate Topic: 1 Votes //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=298097&amp;s=e14a3563e54416829c9d282b9090da66&md5check=' + ipb.vars['secure_hash'], cur_rating: 5, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #16 Python_4_President

• D.I.C Regular

Reputation: 53
• Posts: 321
• Joined: 13-August 11

## Re: Halloween Python Challenge

Posted 01 November 2012 - 08:30 AM

Ok, now it seems to work properly. I assume that if you go through an entire series of some particular tens (ie, 70-80) without finding any non-solutions, you're probably done. At least, my tests would indicate 10 is a good number. This is my first mathy combinatorial problem =)

Spoiler

This post has been edited by Python_4_President: 01 November 2012 - 09:09 AM

### #17 blackcompe

• D.I.C Lover

Reputation: 1159
• Posts: 2,547
• Joined: 05-May 05

## Re: Halloween Python Challenge

Posted 02 November 2012 - 01:32 AM

I did mine in Scala. Purely functional baby!! Can we get some test cases?? Am I correct in saying the equation must consist of co-prime coefficients only?

Updated code

Spoiler

This post has been edited by blackcompe: 02 November 2012 - 06:51 PM

### #18 Simown

• Blue Sprat

Reputation: 322
• Posts: 650
• Joined: 20-May 10

## Re: Halloween Python Challenge

Posted 02 November 2012 - 02:30 AM

They are not necessarily co-prime, but if they aren't there is no solution. So return 0, -1, or "none" or some indicator of that.

Test cases are a good idea. I will have to update the first post later, so check back!

### #19 blackcompe

• D.I.C Lover

Reputation: 1159
• Posts: 2,547
• Joined: 05-May 05

## Re: Halloween Python Challenge

Posted 02 November 2012 - 03:18 PM

Has anyone been able to get the correct output for 9x + 20y = N? It's 151, but using the algorithm given in the OCW handout gives 115. Below is the debugging output from my code. I get 115 as having no solutions and then immediately after I get 6 consecutive numbers with solutions. So 115, according to MIT is correct.

```115:false
116:true
117:true
118:true
119:true
120:true
121:true
(115,120)

```

It appears that this algorithm doesn't generalize at all. The only problem that's correctly solved is this the particular case of 6, 9, and 20. Heh, maybe that's what was intended. I also found a calculator for the Frobenius problem (McNuggets generalized).

This post has been edited by blackcompe: 02 November 2012 - 03:19 PM

### #20 jon.kiparsky

• Beginner

Reputation: 11022
• Posts: 18,805
• Joined: 19-March 11

## Re: Halloween Python Challenge

Posted 02 November 2012 - 03:28 PM

Yeah, 151 is what I get.

If you're talking about the six consecutive numbers, the generalization for that is, taking x to be the least term in the set, if you have x consecutive numbers then any number above that point must be a solution. Easy to prove: if p is a solution, then p+x is a solution. If xa + yb +c = p, then x(a+1) +yb+zc = p+x.

So in this case you need to look for 9 consecutive solutions.

### #21 blackcompe

• D.I.C Lover

Reputation: 1159
• Posts: 2,547
• Joined: 05-May 05

## Re: Halloween Python Challenge

Posted 02 November 2012 - 03:32 PM

Quote

If you're talking about the six consecutive numbers, the generalization for that is, taking x to be the least term in the set, if you have x consecutive numbers then any number above that point must be a solution. Easy to prove: if p is a solution, then p+x is a solution. If xa + yb +c = p, then x(a+1) +yb+zc = p+x.

Ah thanks Jon!

Edit:

I got it working.

This post has been edited by blackcompe: 02 November 2012 - 03:39 PM

### #22 jon.kiparsky

• Beginner

Reputation: 11022
• Posts: 18,805
• Joined: 19-March 11

## Re: Halloween Python Challenge

Posted 05 November 2012 - 08:26 PM

So I think we've had plenty of time for people to come up with solutions. Here's the one that I came up with, using a variation on the idea of the sieve: we don't need to test numbers which are congruent modulo x to a known solution. This limits the search space somewhat, resulting in improved running times.

There's an obvious improvement to make, of course - testing for GCD at the outset would tidy things up a little. However, the question of what number constitutes a reasonable upper bound is an interesting one, so I wanted to leave it in place while I think it over.

Spoiler

### #23 blackcompe

• D.I.C Lover

Reputation: 1159
• Posts: 2,547
• Joined: 05-May 05

## Re: Halloween Python Challenge

Posted 06 November 2012 - 08:51 AM

Cutting down the search space would definitely help my algorithm's efficiency. As of now, it's taking quite a while for even small coefficients.

Quote

we don't need to test numbers which are congruent modulo x to a known solution.

Can you expand on this? Perhaps give an example? When you say known solution, are you referring to a number that we find can (or can't) find a solution for? For instance, in the McNugget problem, the numbers that don't have solutions are:

1,2,3,4,5,7,8,10,11,13,14,16,17,19,22,23,25,28,31,34,37,43

So are the known solutions the complement of that set?

Secondly, what's x referring to here when you say "modulo x". Is it the a coefficient in the equation (e.g. 6 for the McNugget problem) or is it the value of the unknown x in the equation for that particular solution.

E.g. In finding a solution for N = 42 in the McNugget problem, we have:

6 * x + 9 * y + 20 * z = 42

A solution is [x = 7, y = 0, z = 0]

So the x you're referring to is then 7. So we'd have something like this:

42 = test_number (mod 7)

Obviously, there's no test_number that satisfies that congruence, so I know my logic is incorrect, but is this close to what you mean?

### #24 jon.kiparsky

• Beginner

Reputation: 11022
• Posts: 18,805
• Joined: 19-March 11

## Re: Halloween Python Challenge

Posted 06 November 2012 - 11:56 AM

Quote

When you say known solution, are you referring to a number that we find can (or can't) find a solution for

By "a known solution" I mean some number which is known to be a possible solution to that equation. So 42, as you say, is known to be a possible solution (and therefore 49 is as well)
The set of known solutions would be, as you say, the complement of the set of numbers which cannot be solutions.

Quote

Secondly, what's x referring to here when you say "modulo x". Is it the a coefficient in the equation (e.g. 6 for the McNugget problem) or is it the value of the unknown x in the equation for that particular solution.

Yes, I mean the "a" coefficient. Sorry, that was unclear. Particularly, I mean the least of the coefficients. So perhaps I should have said "a". That would have made more sense.

So from your example, if we know that 42 is a legitimate "move" in this game, then we can infer that 48, as well as 51, and 62, are legal moves. This is a simple rule of inference which in a way ignores the math of it, but it turns out to be correct, as we saw above.
In fact, we could reduce this to a simple nim-type "game", though not a very entertaining one. The rules are, you start from zero, and you can derive any number which you can reach by adding some member of the coefficient set. If you imagine a grid of "x" (a, really! ) rows, numbered 0..x-1 and filled in with the numbers in the obvious pattern (0..x-1, x..2x-1, etc), extending arbitrarily far to the right, you can imagine the goal being to "claim" rows by deriving the lowest possible number in that row, according to the simple rule of derivation.
My algorithm, basically, plays this game as a solitaire.

That game, by the way, is an example, or perhaps an illustration, of my assertion that "we don't need to test numbers which are congruent modulo x to a known solution." it should be obvious that once we reach any square on that grid, all of the squares to the right of it are known to be solutions. Therefore, finding the least value in each row, and then taking the largest of that set, is sufficient to solve the problem.

This post has been edited by jon.kiparsky: 06 November 2012 - 12:01 PM

### #25 blackcompe

• D.I.C Lover

Reputation: 1159
• Posts: 2,547
• Joined: 05-May 05

## Re: Halloween Python Challenge

Posted 06 November 2012 - 05:02 PM

Quote

Yes, I mean the "a" coefficient. Sorry, that was unclear. Particularly, I mean the least of the coefficients. So perhaps I should have said "a". That would have made more sense.

So from your example, if we know that 42 is a legitimate "move" in this game, then we can infer that 48, as well as 51, and 62, are legal moves.

I'm still unclear. Can you show the Math behind finding that 48, 51, and 62 are solutions. From what I understand, your saying (for the McNugget problem, where a = 6):

0 = 48 mod 6
3 = 51 mod 6
2 = 62 mod 6

0, 3, 2 are previously found known solutions, but for

1 = 43 mod 6

1 is a known solution, and therefore 43 is a known solution, which is obviously not true.

### #26 jon.kiparsky

• Beginner

Reputation: 11022
• Posts: 18,805
• Joined: 19-March 11

## Re: Halloween Python Challenge

Posted 06 November 2012 - 11:44 PM

1 is not a known solution - there's no way to get 1 to be a solution of 6x + 9y +20z. The rule of inference proceeds from zero. Zero can be a solution to any equation in this form, simply by setting x, y,z, ... to zero. And term in the list of coefficients can be a solution, simply by setting the appropriate x, y, z, ... to 1, and leaving the rest at zero. (That is, by adding that coeffeicient to zero.)

Okay, I admit that I've had a few beers at this point (happy re-election to all!) but there's three steps as I see it.

First of all, zero is a solution to any equation of this form. (see above)

Second, if the coefficients of the equation are listed as (a, b, c...) then any previously derived solution, increased by some member of that set, is also a solution.

Third, if we have a solution in row of this notional grid, described above, then we know that there is a point above which all integers are solutions to this equation.

I think each of these is proveable, and I think that

Fourth, taken together they establish that the algorithm is sound.

I would be happy to try to walk through any of these tomorrow evening, when I'm not at work and when I'm not just back from the bar. Let me know which you'd like.

### #27 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12278
• Posts: 45,364
• Joined: 27-December 08

## Re: Halloween Python Challenge

Posted 10 November 2012 - 11:17 AM

I've got a basic solution cranked out. I optimized to ignore coefficients that are greater than the sum, and to check right off if the remaining capacity (mod coefficient[i]) == 0. I also started the lowest non-solution as the lowest coefficient-1. Beyond that, I basically took the Sieve approach.

I did play around with upper bounds. I tried to guestimate that since the solution is coprime to all the coefficients, and the Sieve of Eratosthenes is O(n^1.5), then the upper bounds for the largest non-solution is (sum of coefficients)^1.5. Unfortunately, that didn't scale. The lower bounds I found was sqrt(3 * product(coefficients)) - (Sum of coefficients). My lower bounds was more efficient. Given the equation 77x + 42y = c, sqrt(3*77*42) - (77+42) < 0, and my lower bounds is 41 there.

Spoiler

This post has been edited by Simown: 10 November 2012 - 07:14 PM
Reason for edit:: Code tags?!