Thread: January 2022 View Single Post
 2022-02-13, 12:00 #25 dg211   Jun 2016 19 Posts 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 (n-1)! 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 #include #include #include std::vector GetPrimes(uint64_t n) { std::vector 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 digits; digits.resize(n); auto primes = GetPrimes(powersOfTen[d]); printf("t = %llu ms\n", std::chrono::duration_cast(std::chrono::steady_clock::now() - startTime).count()); std::vector 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 minScoreDigits; std::vector 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::steady_clock::now() - startTime).count()); return 0; }