January 2022
[url]https://research.ibm.com/haifa/ponderthis/challenges/January2022.html[/url]

Min/max for 7/5 case? 446/3051?

I can confirm those numbers...
/Thomas Egense 
[QUOTE=Zoozie;597383]I can confirm those numbers...
/Thomas Egense[/QUOTE] Thank you! I sent my 7/5 solution yesterday. What did you code in? What was the total runtime? I coded in Python, it took ~24 minutes to solve the n = 7, d = 5 case. Java should be faster for sure. Is anybody working on n = 8, d = 6? It would be nice to see the min/max counts (please don't post the solutions, just the counts). 
[QUOTE=Max0526;597387]Thank you! I sent my 7/5 solution yesterday.
What did you code in? What was the total runtime? I coded in Python, it took ~24 minutes to solve the n = 7, d = 5 case. Java should be faster for sure. Is anybody working on n = 8, d = 6? It would be nice to see the min/max counts (please don't post the solutions, just the counts).[/QUOTE] It took about 2 minutes to solve in java for n=7,d=5. I did not really optimize except first generating cache of small primes. The n=8, d=6 was solved in some hours, did not time it. For n=8, d=6: wheeel for maximum solution had 1992 primes wheel for minimum solution had 741 primes. 
[QUOTE=Zoozie;597388]It took about 2 minutes to solve in java for n=7,d=5. I did not really optimize except first generating cache of small primes. The n=8, d=6 was solved in some hours, did not time it.
For n=8, d=6: wheeel for maximum solution had 1992 primes wheel for minimum solution had 741 primes.[/QUOTE] Zoozie, could you please look up the max/min scores, not the number of primes? Thank you! 
I can confirm the scores for n = 7 and d = 5.
For n = 8 and d = 6, I get the following scores: max: 19690 min: 6905 Average execution time (using Cython, and only one thread  could be easily parallelized): n = 7, d = 5: ~120 seconds n = 8, d = 6: ~1100 seconds 
[QUOTE=Walter;597506]I can confirm the scores for n = 7 and d = 5.
For n = 8 and d = 6, I get the following scores: max: 19690 min: 6905 Average execution time (using Cython, and only one thread  could be easily parallelized): n = 7, d = 5: ~120 seconds n = 8, d = 6: ~1100 seconds[/QUOTE] I have a circle with score 21617 but my min is not even close to yours. 
> but my min is not even close to yours.
It might be that the problem got edited after the initial posting. The first sentence reads: "Seven [B]distinct[/B] digits are placed on a circle." (also, "placed" is misspelled in the original) I had much lower min scores (60 instead of 446) when the circle of 7 was allowed to have duplicates. No duplicates allowed, neither in the circle, nor in the numbers. Thank you for posting your scores and times! 
[QUOTE=Max0526;597533]> but my min is not even close to yours.
I had much lower min scores (60 instead of 446) when the circle of 7 was allowed to have duplicates. No duplicates allowed, neither in the circle, nor in the numbers. [/QUOTE] I meant my minimum is much higher. I do hope someone who solved the bonus can post their scores for min and max. 
[QUOTE=SmartMersenne;597535]I meant my minimum is much higher. I do hope someone who solved the bonus can post their scores for min and max.[/QUOTE]
Just to add on to my previous response: the number of primes that can be generated with the max and min wheel in my solution corresponds to the same values that Zoozie posted (741 primes for the min wheel and 1992 primes for the max wheel). Now, to be fair, I see multiple wheels that generate the same number of primes, but it gives me some additional confidence that my solution is right. 
[QUOTE=Walter;597538]Just to add on to my previous response: the number of primes that can be generated with the max and min wheel in my solution corresponds to the same values that Zoozie posted (741 primes for the min wheel and 1992 primes for the max wheel). Now, to be fair, I see multiple wheels that generate the same number of primes, but it gives me some additional confidence that my solution is right.[/QUOTE]
If I skip 5 and 8 in my circle: PRIMES: 1860, CMAX = 21258 > 19690. Greater number of primes doesn't necessarily mean higher score of the circle. Also, below 8300 for the min so far. 
Oops. I had hard coded something for the n=7/d=5 case. After changing this, I am getting the following values:
min: 8265 max: 23209 Anyone else getting those values? 
I avoided posting the scores since this could make people skip exhaustive search to find the solution.

[QUOTE=Walter;597544]Oops. I had hard coded something for the n=7/d=5 case. After changing this, I am getting the following values:
min: 8265 max: 23209 Anyone else getting those values?[/QUOTE] Got the same min/max! [QUOTE=Zoozie;597388]It took about 2 minutes to solve in java for n=7,d=5. I did not really optimize except first generating cache of small primes. The n=8, d=6 was solved in some hours, did not time it. For n=8, d=6: wheeel for maximum solution had 1992 primes wheel for minimum solution had 741 primes.[/QUOTE] And the same number of primes! 
Just for the fun of it, anybody wants to try coding n = 9, d = 7 and n = 10, d = 8 cases?

[QUOTE=Max0526;597582]Just for the fun of it, anybody wants to try coding n = 9, d = 7 and n = 10, d = 8 cases?[/QUOTE]
With n = 9, d = 7 I get the following values: min: 117390 max: 194304 And with n = 10, d = 8: min: 1747537 max: 1772281 The runtime was about 13000 seconds for the n = 9 case. For the n = 10 case, I used 4 threads, which resulted in a runtime of 12400 seconds. 
[code]
With n = 9, d = 7 I get the following values: min: 117390 max: 194304 And with n = 10, d = 8: min: 1747537 max: 1772281 [/code] Massive amount of computation is done here! I need to rewrite Python into Java to be able to compete with your run times. Will post my results when it's done. Send these min/max results to IBM too. Sometimes they award **. 
[QUOTE=Max0526;597655]
Send these min/max results to IBM too. Sometimes they award **.[/QUOTE] Not with the new puzzlemaster. He is lazy to do anything extra or even the minimum expected things on time. 
[QUOTE=SmartMersenne;597694]Not with the new puzzlemaster. He is lazy to do anything extra or even the minimum expected things on time.[/QUOTE]
Agree! He updates scores only 2 times a month. We can still not see who has solved this month. Also solution to December challenge still gives a 404. 
[QUOTE=Zoozie;597736]Agree! He updates scores only 2 times a month. We can still not see who has solved this month.
Also solution to December challenge still gives a 404.[/QUOTE] Both are available as of this morning. 
I get the same answers for n = 9, d = 7 and n = 10, d = 8. It is possible to do it with a lot less computation  my single threaded C++ code took about 3.5s for n = 9, d = 7 and about 32s for n = 10, d = 8. Almost all of the time for n = 10 (like 31.9s) was spent generating a list of 8 digit primes.
[QUOTE=Walter;597648]With n = 9, d = 7 I get the following values: min: 117390 max: 194304 And with n = 10, d = 8: min: 1747537 max: 1772281 The runtime was about 13000 seconds for the n = 9 case. For the n = 10 case, I used 4 threads, which resulted in a runtime of 12400 seconds.[/QUOTE] 
[QUOTE=dg211;598172]I get the same answers for n = 9, d = 7 and n = 10, d = 8. It is possible to do it with a lot less computation  my single threaded C++ code took about 3.5s for n = 9, d = 7 and about 32s for n = 10, d = 8. Almost all of the time for n = 10 (like 31.9s) was spent generating a list of 8 digit primes.[/QUOTE]
Maybe you can post your solution next month (after the solution is posted on IBM site). 
Sure, can do.
[QUOTE=SmartMersenne;598231]Maybe you can post your solution next month (after the solution is posted on IBM site).[/QUOTE] 
The solution is up on the IBM site now, so sharing my code as SmartMersenne suggested.
The key observations I used to make it reasonably fast were:  You can rotate the whole circle without affecting the score so e.g. 2345671 is equivalent to 1234567. That means for any set of n digits you can pick an arbitrary one to be first in the circle, and only look at (n1)! arrangements rather than n!  Rearranging the digits in the circle doesn't affect the primes you can make, only the score. And you can count how many times each digit follows each other digit in the list of primes that are makeable. So for example 32467 contributes one instance of a 3 followed by a 2, one 2 followed by 4, etc. Then when you rearrange the digits, you just need to calculate how much score a 3 followed by a 2 will contribute for that arrangement and add that to the score for each instance of 3 followed by 2 in the set of makeable primes, and so on. That means you don't have to completely start from scratch for a circle like 3762451 if you have already computed the score for the circle 1234567. My GetPrimes function is not very efficient and was the bottleneck for n = 10 by miles. I did write another one which was a lot better (about 1s for n = 10) but I'm sure it's possible to do better still. [CODE]#include <vector> #include <intrin.h> #include <algorithm> #include <chrono> std::vector<uint64_t> GetPrimes(uint64_t n) { std::vector<uint64_t> primes = {2}; for (uint64_t i = 3; i < n; i+=2) { bool isPrime = true; for (auto p : primes) { if (i % p == 0) { isPrime = false; break; } if (p * p > i) { break; } } if (isPrime) { primes.push_back(i); } } return primes; } int main() { int n = 8; int d = 6; auto startTime = std::chrono::steady_clock::now(); uint64_t powersOfTen[11]; powersOfTen[0] = 1i64; for (int i = 1; i < 11; i++) { powersOfTen[i] = powersOfTen[i  1] * 10i64; } std::vector<int> digits; digits.resize(n); auto primes = GetPrimes(powersOfTen[d]); printf("t = %llu ms\n", std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now()  startTime).count()); std::vector<uint64_t> allowedPrimes; for (auto p : primes) { if (p >= powersOfTen[d  1] && p < powersOfTen[d]) { // check the digits are distinct int digitCount[10] = {0}; bool digitsDistinct = true; uint64_t t = p; while (t > 0) { digitCount[t % 10] += 1; if (digitCount[t % 10] > 1) { digitsDistinct = false; } t /= 10; } if (digitsDistinct) { allowedPrimes.push_back(p); } } } uint64_t maxScore = 0; uint64_t minScore = 1 << 30; std::vector<int> minScoreDigits; std::vector<int> maxScoreDigits; for (int i = 0; i < (1 << 10); i++) { if (__popcnt(i) == n) { int k = 0; for (int j = 0; j < 10; j++) { if (i & (1 << j)) { digits[k++] = j; } } uint64_t digitTransitions[10][10]; memset(digitTransitions, 0, 100 * sizeof(uint64_t)); for (auto p : allowedPrimes) { bool canMakePrime = true; uint64_t t = p; while (t > 0) { int m = 1 << (t % 10); if ((m & i) == 0) { canMakePrime = false; } t /= 10; } if (canMakePrime) { uint64_t t = p; int lastDigit = t % 10; t /= 10; while (t > 0) { digitTransitions[t % 10][lastDigit] += 1; lastDigit = t % 10; t /= 10; } } } do { uint64_t score = 0; int digitPositions[10] = {0}; int j = 0; for (auto d : digits) { digitPositions[d] = j++; } for (int j = 0; j < 10; j++) { for (int k = 0; k < 10; k++) { if (digitTransitions[j][k] > 0) { int digitDistance = (digitPositions[j] + n  digitPositions[k]) % n; digitDistance = std::min(digitDistance, n  digitDistance); score += digitTransitions[j][k] * digitDistance; } } } if (score < minScore) { minScore = score; minScoreDigits = digits; } if (score > maxScore) { maxScore = score; maxScoreDigits = digits; } } while (std::next_permutation(digits.begin() + 1, digits.end())); } } for (auto d : minScoreDigits) { printf("%i", d); } printf(", %lli\n", minScore); for (auto d : maxScoreDigits) { printf("%i", d); } printf(", %lli\n", maxScore); printf("t = %llu ms", std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now()  startTime).count()); return 0; }[/CODE] 
[QUOTE=dg211;599969]The solution is up on the IBM site now, so sharing my code as SmartMersenne suggested.
The key observations I used to make it reasonably fast were:  You can rotate the whole circle without affecting the score so e.g. 2345671 is equivalent to 1234567. That means for any set of n digits you can pick an arbitrary one to be first in the circle, and only look at (n1)! arrangements rather than n!  Rearranging the digits in the circle doesn't affect the primes you can make, only the score. And you can count how many times each digit follows each other digit in the list of primes that are makeable. So for example 32467 contributes one instance of a 3 followed by a 2, one 2 followed by 4, etc. Then when you rearrange the digits, you just need to calculate how much score a 3 followed by a 2 will contribute for that arrangement and add that to the score for each instance of 3 followed by 2 in the set of makeable primes, and so on. That means you don't have to completely start from scratch for a circle like 3762451 if you have already computed the score for the circle 1234567. My GetPrimes function is not very efficient and was the bottleneck for n = 10 by miles. I did write another one which was a lot better (about 1s for n = 10) but I'm sure it's possible to do better still. [CODE]#include <vector> #include <intrin.h> #include <algorithm> #include <chrono> std::vector<uint64_t> GetPrimes(uint64_t n) { std::vector<uint64_t> primes = {2}; for (uint64_t i = 3; i < n; i+=2) { bool isPrime = true; for (auto p : primes) { if (i % p == 0) { isPrime = false; break; } if (p * p > i) { break; } } if (isPrime) { primes.push_back(i); } } return primes; } int main() { int n = 8; int d = 6; auto startTime = std::chrono::steady_clock::now(); uint64_t powersOfTen[11]; powersOfTen[0] = 1i64; for (int i = 1; i < 11; i++) { powersOfTen[i] = powersOfTen[i  1] * 10i64; } std::vector<int> digits; digits.resize(n); auto primes = GetPrimes(powersOfTen[d]); printf("t = %llu ms\n", std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now()  startTime).count()); std::vector<uint64_t> allowedPrimes; for (auto p : primes) { if (p >= powersOfTen[d  1] && p < powersOfTen[d]) { // check the digits are distinct int digitCount[10] = {0}; bool digitsDistinct = true; uint64_t t = p; while (t > 0) { digitCount[t % 10] += 1; if (digitCount[t % 10] > 1) { digitsDistinct = false; } t /= 10; } if (digitsDistinct) { allowedPrimes.push_back(p); } } } uint64_t maxScore = 0; uint64_t minScore = 1 << 30; std::vector<int> minScoreDigits; std::vector<int> maxScoreDigits; for (int i = 0; i < (1 << 10); i++) { if (__popcnt(i) == n) { int k = 0; for (int j = 0; j < 10; j++) { if (i & (1 << j)) { digits[k++] = j; } } uint64_t digitTransitions[10][10]; memset(digitTransitions, 0, 100 * sizeof(uint64_t)); for (auto p : allowedPrimes) { bool canMakePrime = true; uint64_t t = p; while (t > 0) { int m = 1 << (t % 10); if ((m & i) == 0) { canMakePrime = false; } t /= 10; } if (canMakePrime) { uint64_t t = p; int lastDigit = t % 10; t /= 10; while (t > 0) { digitTransitions[t % 10][lastDigit] += 1; lastDigit = t % 10; t /= 10; } } } do { uint64_t score = 0; int digitPositions[10] = {0}; int j = 0; for (auto d : digits) { digitPositions[d] = j++; } for (int j = 0; j < 10; j++) { for (int k = 0; k < 10; k++) { if (digitTransitions[j][k] > 0) { int digitDistance = (digitPositions[j] + n  digitPositions[k]) % n; digitDistance = std::min(digitDistance, n  digitDistance); score += digitTransitions[j][k] * digitDistance; } } } if (score < minScore) { minScore = score; minScoreDigits = digits; } if (score > maxScore) { maxScore = score; maxScoreDigits = digits; } } while (std::next_permutation(digits.begin() + 1, digits.end())); } } for (auto d : minScoreDigits) { printf("%i", d); } printf(", %lli\n", minScore); for (auto d : maxScoreDigits) { printf("%i", d); } printf(", %lli\n", maxScore); printf("t = %llu ms", std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now()  startTime).count()); return 0; }[/CODE][/QUOTE] I had a similar approach but programmed in Java. I found that the set of all nonequivalent circles are formally called a "[URL="https://en.wikipedia.org/wiki/Necklace_(combinatorics)"]necklace[/URL]". Since the elements of the circles are always unique, I was able to generate necklaces of a length N circle by first generating all permutations of the first N1 digits and adjoining the Nth element to the end of every permutation I generated, which matches the (N1)! number of arrangements you mentioned. 
All times are UTC. The time now is 15:49. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2022, Jelsoft Enterprises Ltd.