×

To be able to write in the forum you need to authenticate. Meanwhile it's read-only.

Change History

Need a challenge checker made or improved? This is where you should post your request.

Message: Re: GC87FM1 Countries, Types, 4x4 Matrix

Changed By: PattuX
Change Date: October 11, 2019 03:03AM

Re: GC87FM1 Countries, Types, 4x4 Matrix
Alright, quick update.

So first of all there are two possibilities with the preprocessing here:

1. It's done exhaustively once before the backtracking stuff, like you did for your account. Now this works well for your account in particular since you have many countries with few finds. However for other users, such as the two you listed, it doesn't help that much and it still times out since after ~10 deductions there are only countries with 4 different types and/or only country-type combinations with two or more DT-ratings left, leaving no further deductions.

2. It's done exaustively once before the guessing and again (exhaustively) every time a cache is added via guessing. This makes it [b]significantly[/b] faster for users fulfilling the challenge like the two you listed since there are far less choices on the way towards the solution. However, the issue here is that for a user who does not fulfill the challenge by a small margin (i.e. when simple heuristics can't tell that the user can't fulfill the challenge) the search tree is necessarily traversed completely (i.e. every possible choice is tried) and for every step this preprocessing is done, i.e. tens of thousands of times, which consumes lots of time. Arguably the search tree gets slightly smaller by doing the deductions but with quite some users I tried this knocks them over the timeout barrier.

I'll think about it a bit more and see whether I can get the second option to work for negative results at a speed that is at least as good as the script w/o preprocessing. Sounds like it should be possible...

edit: Oh, and of course, if you want to try it for yourself: https://project-gc.com/Challenges//45632
In the debug output tab there's also a list of how many times each country, and how many times each combination of country/type is included in the final matrix. This should make it easier to check if a result is correct, since you only need to check if all numbers are at most 3 or 1 respectively. I haven't found any wrong output yet.
Changed By: PattuX
Change Date: October 11, 2019 02:20AM

Re: GC87FM1 Countries, Types, 4x4 Matrix
Alright, quick update.

So first of all there are two possibilities with the preprocessing here:

1. It's done exhaustively once before the backtracking stuff, like you did for your account. Now this works well for your account in particular since you have many countries with few finds. However for other users, such as the two you listed, it doesn't help that much and it still times out since after ~10 deductions there are only countries with 4 different types and/or only country-type combinations with two or more DT-ratings left, leaving no further deductions.

2. It's done exaustively once before the guessing and again (exhaustively) every time a cache is added via guessing. This makes it [b]significantly[/b] faster for users fulfilling the challenge like the two you listed since there are far less choices on the way towards the solution. However, the issue here is that for a user who does not fulfill the challenge the search tree is necessarily traversed completely (i.e. every possible choice is tried) and for every step this preprocessing is done, i.e. tens of thousands of times, which consumes lots of time. Arguably the search tree gets slightly smaller by doing the deductions but with quite some users I tried this knocks them over the timeout barrier.

I'll think about it a bit more and see whether I can get the second option to work for negative results at a speed that is at least as good as the script w/o preprocessing. Sounds like it should be possible...

edit: Oh, and of course, if you want to try it for yourself: https://project-gc.com/Challenges//45632
In the debug output tab there's also a list of how many times each country, and how many times each combination of country/type is included in the final matrix. This should make it easier to check if a result is correct, since you only need to check if all numbers are at most 3 or 1 respectively. I haven't found any wrong output yet.
Changed By: PattuX
Change Date: October 11, 2019 02:15AM

Re: GC87FM1 Countries, Types, 4x4 Matrix
Alright, quick update.

So first of all there are two possibilities with the preprocessing here:

1. It's done exhaustively once before the backtracking stuff, like you did for your account. Now this works well for your account in particular since you have many countries with few finds. However for other users, such as the two you listed, it doesn't help that much and it still times out since after ~10 deductions there are only countries with 4 different types and/or only country-type combinations with two or more DT-ratings left, leaving no further deductions.

2. It's done exaustively once before the guessing and again (exhaustively) every time a cache is added via guessing. This makes it [b]significantly[/b] faster for users fulfilling the challenge like the two you listed since there are far less choices on the way towards the solution. However, the issue here is that for a user who does not fulfill the challenge the search tree is necessarily traversed completely (i.e. every possible choice is tried) and for every step this preprocessing is done, i.e. tens of thousands of times, which consumes lots of time. Arguably the search tree gets slightly smaller by doing the deductions but with quite some users I tried this knocks them over the timeout barrier.

I'll think about it a bit more and see whether I can get the second option to work for negative results at a speed that is at least as good as the script w/o preprocessing. Sounds like it should be possible...

edit: Oh, and of course, if you want to try it for yourself: https://project-gc.com/Challenges//45632

Original Message

Author: PattuX
Date: October 11, 2019 02:13AM

Re: GC87FM1 Countries, Types, 4x4 Matrix
Alright, quick update.

So first of all there are two possibilities with the preprocessing here:

1. It's done exhaustively once before the backtracking stuff, like you did for your account. Now this works well for your account in particular since you have many countries with few finds. However for other users, such as the two you listed, it doesn't help that much and it still times out since after ~10 deductions there are only countries with 4 different types and/or only country-type combinations with two or more DT-ratings left, leaving no further deductions.

2. It's done exaustively once before the guessing and again (exhaustively) every time a cache is added via guessing. This makes it [b]significantly[/b] faster for users fulfilling the challenge like the two you listed since there are far less choices on the way towards the solution. However, the issue here is that for a user who does not fulfill the challenge the search tree is necessarily traversed completely (i.e. every possible choice is tried) and for every step this preprocessing is done, i.e. tens of thousands of times, which consumes lots of time. Arguably the search tree gets slightly smaller by doing the deductions but with quite some users I tried this knocks them over the timeout barrier.

I'll think about it a bit more and see whether I can get the second option to work for negative results at a speed that is at least as good as the script w/o preprocessing. Sounds like it should be possible...