Avgvst 2016 - Page 2

firejuggler · 2016-08-04, 20:09

1-2-5-9-13-17-21-25-29-33 well that was easy...
since there can be only 3 bag with fake coin ...

total excepted : 1550 with no fake
1549 bag 1 is fake
1548 bag 2 is fake
1547 bag1 and 2 are fake
1546 impossible
1545 bag 3 is fake
1544 bag 3/1 are fake
1543 bag 3/2 are fake
1542 bag 3/2/1 are fake
etc...

axn · 2016-08-05, 02:51

Quote:

Originally Posted by firejuggler

1-2-5-9-13-17-21-25-29-33 well that was easy...
since there can be only 3 bag with fake coin ...

total excepted : 1550 with no fake
1549 bag 1 is fake
1548 bag 2 is fake
1547 bag1 and 2 are fake
1546 impossible
1545 bag 3 is fake
1544 bag 3/1 are fake
1543 bag 3/2 are fake
1542 bag 3/2/1 are fake
etc...

5+9 = 13+1
17+5 = 21+1
...
Did I just get trolled?

LaurV · 2016-08-05, 04:57

Well, there is no magic in the powers of two, just that every power is the sum of all the other, plus one. That is why the 1, 2, 4, 8, 16, 32, 64, 128, 256, 512 solution allows finding ANY combination of bad bags, because the sums of any of them are different, because it is at least one lower that the next number in the string. So, 1+2+1=4, 1+2+4+1=8, 1+2+4+8+1=16, etc. Now, knowing that there are maximum 3 bad bags, this is already a huge restriction, we won't need to sum all the previous values, but only the biggest 3, and add 1. Therefore, the starting point is already: 1, 1+1=2, 1+2+1=4, 1+2+4+1=8, but now to get to the next, we would only need to sum the last 3, because maximum 3 bags can be bad. Then, 2+4+8+1=15, and then 4+8+15+1=28, etc.

This already brings us to the 1, 2, 4, 8, 15, 28, 52, 96, 177, 326. In this combination, no matter how you sum one, two or three of them, you will always get a different number, and there is already a big improvement, 326 instead of 512.

Now, is this solution optimum? Certainly not, and the reason is not "because they asked for 174". First we see that many values are skipped, using this method. For example, nothing sums to 22, and nothing sums to 26. But we can't use 22 or 26 instead of 28, because in that case, we would have 22+1=15+8, respective 26+1=15+8+4, so we would need in this case to modify either 15, either 8, etc. to avoid the conflict. But we may be able to lower the other numbers, toward the end of the string, where more and more values are "skipped", the "gaps" are bigger there.

Of course, the easiest is to start from the end and play with the values, using some heuristic to generate different combinations and test them for conflict. Testing for conflict is the most time-consuming, but we came up with a very clever idea to do so

. This way we were able to find by hand (YES!) solutions like:

1, 2, 4, 8, 15, 28, 52, 96, 165, 278, or
1, 2, 4, 8, 15, 28, 52, 102, 171, 240, or even better,
1, 2, 4, 8, 15, 29, 70, 121, 167, 213.

We also found (by hand too!) solutions which do not start with 1, like:

2, 3, 4, 8, 16, 29, 52, 88, 147, 265, or
2, 4, 5, 8, 16, 30, 53, 106, 172, 238

for which we are already very proud, in spite of the fact that we were not able to go under 200.

Then we put it in a program, and understood why the guys asked for 174: they want to give a chance to poor guys too, hehe. The 174 solution was spitted out by the program in about 6-7 minutes, but the program continued to run for another 4-5 hours without producing a smaller solution.

The program starts with N=326, and testes all combinations in lexicographic order, using a clever idea to find the conflicts once a new combination is generated. Well, not all combinations, many of them are skipped, for example if the conflict is found at the fifth position, the fifth quantity is changed (and all after it), skipping a lot of combinations which have no chance to generate a better solution. This is shortening the search time a lot (about 45 times!).

When a solution with a n<=N is found, the new N becomes n-1, and the program continues. This way, it will produce smaller and smaller solutions, until the whole combination set is exhausted. But that could take about 25 days, running in 4 cores, and we will not let it do so!. Therefore we included the possibility to start with a random combinations, and tried our luck, giving a random start and run for 2-3 minutes, many times. We did this for few hours last evening, but the best we could come with, was some N about ~190.

Then we gave up. Totally.

We are not going to send out our 174 solution (too easy to find it!).

And unless we come up, during our sleep in the night, with a much MUCH cleverer idea how to solve this problem, or how to improve testing for conflicts, this problem is dead for us. There must be a better idea to find smaller solutions, the exhaustive search is not feasible here. This idea we don't know, but we are patient and we will find it after the solution is published at the end of the month

Or you must have a tone of luck to start with some suitable random combination. We may try some more of this luck, if we have time in the future.

As a diversion: We also tried to find solutions where all quantities are higher than 100, for which the search was completed, and took ~3 hours (because there are few combinations possible when all the 10 quantities are so high). There is no solution for N<175, where all quantities are higher or equal to 100 (and no, the answer is NOT obvious! Solutions with N smaller than 200 exist with this condition).

I don't think I spoil anything if I post what the program outputs in those ~6-7 minutes of run, excluding of course the 174 solution, which came immediately after, as explained in the beginning. (This obviously includes the solutions we found by hand, for which we are very proud!)

Code:

1, 2, 4, 8, 15, 28,  52,  96, 165, 278
1, 2, 4, 8, 15, 28,  52, 102, 171, 240
1, 2, 4, 8, 15, 28,  83, 128, 178, 228
1, 2, 4, 8, 15, 29,  70, 115, 165, 215
1, 2, 4, 8, 15, 29,  70, 121, 167, 213
1, 2, 4, 8, 15, 97, 126, 155, 179, 203
1, 2, 4, 8, 41, 74,  88, 144, 172, 196
1, 2, 4, 8, 42, 61,  80, 156, 170, 184
1, 2, 4, 8, 44, 63,  82, 154, 168, 182
1, 2, 4, 8, 73, 93, 123, 138, 153, 178
--then the right solution here-- (~6-7 minutes)
then nothing..... (few hours)
only a minuscule fraction of the set searched!
(the whole search could take as much as 25 days)

firejuggler · 2016-08-05, 13:12

Quote:

Originally Posted by axn

5+9 = 13+1
17+5 = 21+1
...
Did I just get trolled?

no, I have been dumb.

axn · 2016-08-06, 11:45

Quote:

Originally Posted by LaurV

Then we put it in a program, and understood why the guys asked for 174: they want to give a chance to poor guys too, hehe. The 174 solution was spitted out by the program in about 6-7 minutes, but the program continued to run for another 4-5 hours without producing a smaller solution.

What are you using for your programming? Some kind of scripting language or compiled ones?

My C proggy has found a 172 (starting element 3) after about 1.5 hrs (single core of i3-6098p). Exhaustive search might take a couple of days.

axn · 2016-08-06, 12:50

There is an improvement to 157! Unfortunately I don't know what it is as the output scrolled off the screen

LaurV · 2016-08-06, 14:16

Then your algorithm is (much) better them mine. I use blind C compiled with Visual C++, so if the speed is low, then not the compiler is the problem, but the programmer. I still have no better idea how to make it faster, but don't say it if you know. Already the fact that a solution can be found starting with 3 is a bit of spoiling the things... Now I could run my slow program starting with 3 and find the solution in... how long? a week? hmmm... Maybe I will re-visit this problem if Mrs LaurV does not have shopping plans tomorrow (if so, I'll have to drive, she can't drive).

R. Gerbicz · 2016-08-06, 23:49

Quote:

Originally Posted by axn

What are you using for your programming? Some kind of scripting language or compiled ones?

My C proggy has found a 172 (starting element 3) after about 1.5 hrs (single core of i3-6098p). Exhaustive search might take a couple of days.

Quote:

Originally Posted by LaurV

Then your algorithm is (much) better them mine. I use blind C compiled with Visual C++, so if the speed is low, then not the compiler is the problem, but the programmer. I still have no better idea how to make it faster, but don't say it if you know. Already the fact that a solution can be found starting with 3 is a bit of spoiling the things... Now I could run my slow program starting with 3 and find the solution in... how long? a week? hmmm... Maybe I will re-visit this problem if Mrs LaurV does not have shopping plans tomorrow (if so, I'll have to drive, she can't drive).

Yeah, you guys have some programming issues, using a single thread on a Core-i3 laptop my very first solution found N=174 in 36 seconds, my second code found this in 2 seconds and in 6 minutes reached * so N<174.

axn · 2016-08-07, 03:18

Quote:

Originally Posted by R. Gerbicz

my second code found this in 2 seconds and in 6 minutes reached * so N<174.

How long did it take to do the exhaustive search?

FWIW, my overnight run finished, and assuming that there were no programming errors, came up with 157 as the minimal.

R. Gerbicz · 2016-08-07, 05:23

Quote:

Originally Posted by axn

How long did it take to do the exhaustive search?

Not that very very fast, it took 10 hours on a single thread. (I could easily do a parallel code)

axn · 2016-09-04, 11:40

Solution

2016-08-05, 04:57	#14
LaurV Romulan Interpreter Jun 2011 Thailand 7·1,373 Posts	Well, there is no magic in the powers of two, just that every power is the sum of all the other, plus one. That is why the 1, 2, 4, 8, 16, 32, 64, 128, 256, 512 solution allows finding ANY combination of bad bags, because the sums of any of them are different, because it is at least one lower that the next number in the string. So, 1+2+1=4, 1+2+4+1=8, 1+2+4+8+1=16, etc. Now, knowing that there are maximum 3 bad bags, this is already a huge restriction, we won't need to sum all the previous values, but only the biggest 3, and add 1. Therefore, the starting point is already: 1, 1+1=2, 1+2+1=4, 1+2+4+1=8, but now to get to the next, we would only need to sum the last 3, because maximum 3 bags can be bad. Then, 2+4+8+1=15, and then 4+8+15+1=28, etc. This already brings us to the 1, 2, 4, 8, 15, 28, 52, 96, 177, 326. In this combination, no matter how you sum one, two or three of them, you will always get a different number, and there is already a big improvement, 326 instead of 512. Now, is this solution optimum? Certainly not, and the reason is not "because they asked for 174". First we see that many values are skipped, using this method. For example, nothing sums to 22, and nothing sums to 26. But we can't use 22 or 26 instead of 28, because in that case, we would have 22+1=15+8, respective 26+1=15+8+4, so we would need in this case to modify either 15, either 8, etc. to avoid the conflict. But we may be able to lower the other numbers, toward the end of the string, where more and more values are "skipped", the "gaps" are bigger there. Of course, the easiest is to start from the end and play with the values, using some heuristic to generate different combinations and test them for conflict. Testing for conflict is the most time-consuming, but we came up with a very clever idea to do so . This way we were able to find by hand (YES!) solutions like: 1, 2, 4, 8, 15, 28, 52, 96, 165, 278, or 1, 2, 4, 8, 15, 28, 52, 102, 171, 240, or even better, 1, 2, 4, 8, 15, 29, 70, 121, 167, 213. We also found (by hand too!) solutions which do not start with 1, like: 2, 3, 4, 8, 16, 29, 52, 88, 147, 265, or 2, 4, 5, 8, 16, 30, 53, 106, 172, 238 for which we are already very proud, in spite of the fact that we were not able to go under 200. Then we put it in a program, and understood why the guys asked for 174: they want to give a chance to poor guys too, hehe. The 174 solution was spitted out by the program in about 6-7 minutes, but the program continued to run for another 4-5 hours without producing a smaller solution. The program starts with N=326, and testes all combinations in lexicographic order, using a clever idea to find the conflicts once a new combination is generated. Well, not all combinations, many of them are skipped, for example if the conflict is found at the fifth position, the fifth quantity is changed (and all after it), skipping a lot of combinations which have no chance to generate a better solution. This is shortening the search time a lot (about 45 times!). When a solution with a n<=N is found, the new N becomes n-1, and the program continues. This way, it will produce smaller and smaller solutions, until the whole combination set is exhausted. But that could take about 25 days, running in 4 cores, and we will not let it do so!. Therefore we included the possibility to start with a random combinations, and tried our luck, giving a random start and run for 2-3 minutes, many times. We did this for few hours last evening, but the best we could come with, was some N about ~190. Then we gave up. Totally. We are not going to send out our 174 solution (too easy to find it!). And unless we come up, during our sleep in the night, with a much MUCH cleverer idea how to solve this problem, or how to improve testing for conflicts, this problem is dead for us. There must be a better idea to find smaller solutions, the exhaustive search is not feasible here. This idea we don't know, but we are patient and we will find it after the solution is published at the end of the month Or you must have a tone of luck to start with some suitable random combination. We may try some more of this luck, if we have time in the future. As a diversion: We also tried to find solutions where all quantities are higher than 100, for which the search was completed, and took ~3 hours (because there are few combinations possible when all the 10 quantities are so high). There is no solution for N<175, where all quantities are higher or equal to 100 (and no, the answer is NOT obvious! Solutions with N smaller than 200 exist with this condition). I don't think I spoil anything if I post what the program outputs in those ~6-7 minutes of run, excluding of course the 174 solution, which came immediately after, as explained in the beginning. (This obviously includes the solutions we found by hand, for which we are very proud!) Code: 1, 2, 4, 8, 15, 28, 52, 96, 165, 278 1, 2, 4, 8, 15, 28, 52, 102, 171, 240 1, 2, 4, 8, 15, 28, 83, 128, 178, 228 1, 2, 4, 8, 15, 29, 70, 115, 165, 215 1, 2, 4, 8, 15, 29, 70, 121, 167, 213 1, 2, 4, 8, 15, 97, 126, 155, 179, 203 1, 2, 4, 8, 41, 74, 88, 144, 172, 196 1, 2, 4, 8, 42, 61, 80, 156, 170, 184 1, 2, 4, 8, 44, 63, 82, 154, 168, 182 1, 2, 4, 8, 73, 93, 123, 138, 153, 178 --then the right solution here-- (~6-7 minutes) then nothing..... (few hours) only a minuscule fraction of the set searched! (the whole search could take as much as 25 days) Last fiddled with by LaurV on 2016-08-05 at 05:38 Reason: tyops, grammar, being stupid, etc...

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
July 2016	Xyzzy	Puzzles	4	2016-08-06 22:51
June 2016	Xyzzy	Puzzles	16	2016-07-07 02:51
EM 2016	Cybertronic	Soap Box	1	2016-06-26 21:03
May 2016	Xyzzy	Puzzles	6	2016-06-06 19:02
April 2016	Xyzzy	Puzzles	10	2016-05-05 05:42

2016-08-04, 20:09	#12
firejuggler Apr 2010 Over the rainbow 2³·5²·13 Posts	1-2-5-9-13-17-21-25-29-33 well that was easy... since there can be only 3 bag with fake coin ... total excepted : 1550 with no fake 1549 bag 1 is fake 1548 bag 2 is fake 1547 bag1 and 2 are fake 1546 impossible 1545 bag 3 is fake 1544 bag 3/1 are fake 1543 bag 3/2 are fake 1542 bag 3/2/1 are fake etc...

2016-08-06, 12:50	#17
axn Jun 2003 2²×3×421 Posts	There is an improvement to 157! Unfortunately I don't know what it is as the output scrolled off the screen

2016-08-06, 14:16	#18
LaurV Romulan Interpreter Jun 2011 Thailand 7×1,373 Posts	Then your algorithm is (much) better them mine. I use blind C compiled with Visual C++, so if the speed is low, then not the compiler is the problem, but the programmer. I still have no better idea how to make it faster, but don't say it if you know. Already the fact that a solution can be found starting with 3 is a bit of spoiling the things... Now I could run my slow program starting with 3 and find the solution in... how long? a week? hmmm... Maybe I will re-visit this problem if Mrs LaurV does not have shopping plans tomorrow (if so, I'll have to drive, she can't drive).