mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Puzzles (https://www.mersenneforum.org/forumdisplay.php?f=18)
-   -   January 2022 (https://www.mersenneforum.org/showthread.php?t=27469)

Xyzzy 2022-01-05 17:50

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

Max0526 2022-01-07 05:04

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

Zoozie 2022-01-07 18:29

I can confirm those numbers...

/Thomas Egense

Max0526 2022-01-07 18:53

[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).

Zoozie 2022-01-07 19:01

[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.

Max0526 2022-01-07 22:00

[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!

Walter 2022-01-09 21:46

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

SmartMersenne 2022-01-09 22:35

[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.

Max0526 2022-01-10 04:24

> 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!

SmartMersenne 2022-01-10 04:49

[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.

Walter 2022-01-10 05:38

[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.

Max0526 2022-01-10 06:06

[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.

Walter 2022-01-10 07:33

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?

Zoozie 2022-01-10 11:17

I avoided posting the scores since this could make people skip exhaustive search to find the solution.

Max0526 2022-01-10 13:23

[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!

Max0526 2022-01-10 17:11

Just for the fun of it, anybody wants to try coding n = 9, d = 7 and n = 10, d = 8 cases?

Walter 2022-01-11 12:58

[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.

Max0526 2022-01-11 13:54

[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 **.

SmartMersenne 2022-01-11 22:47

[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.

Zoozie 2022-01-12 07:47

[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.

Max0526 2022-01-12 19:27

[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.

dg211 2022-01-17 14:09

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]

SmartMersenne 2022-01-17 21:12

[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).

dg211 2022-01-18 11:04

Sure, can do.

[QUOTE=SmartMersenne;598231]Maybe you can post your solution next month (after the solution is posted on IBM site).[/QUOTE]

dg211 2022-02-13 12:00

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 <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]

Yusuf 2022-02-14 01:08

[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 (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 <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 non-equivalent 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 N-1 digits and adjoining the Nth element to the end of every permutation I generated, which matches the (N-1)! 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.