https://www.codingame.com/multiplayer/optimization/bulls-and-cows-2
Send your feedback or ask for help here!
Created by @wlesavo,validated by @ToshiTuringMachine,@helgui and @Illedan.
If you have any issues, feel free to ping them.
Pretty addictive puzzle.
As ./learn/combinatorics is just a stub, it would be nice to see extended description with tips:
LEARN ALGORITHMS ASSOCIATED WITH THIS PUZZLE
External resources
1 Like
I’m stuck on lenght = 7. Come on guys, share some ideas - whisper an info about data structure or algorithms 
If you just want to get a 100% correct, here’s a replay to give you an idea (not describing the algo, some work remaining for you): https://www.codingame.com/replay/490623647
For a score around 320 in total it’s just enumerating all possible numbers. Then taking one of them, reducing the list of candidates based on the answer. Keep trying until you got the right one. That’s pretty quick actually (about 11 attempts for a 10 digit number).
But needs some speed optimizations. I failed with C# and had to convert my code to C++.
2 Likes
Getting 100% in Python would make me content.
Thanks for the link - it should help, as I understood what the first stage is.
“Reducing the list of candidates based on the answer” - is tricky though.
I started with set of all possible permutations but it fails due to memory or time limitation. I guess it should be bytearrayes used or numpy, but it will increase calculation time.
Well, the idea is to create set of possible permutation when the first stage is done.
Thanks for help, again.
1 Like
Using itertools.permutations to generate the numbers to guess times out at length=9.
I didn’t even implement any game loop yet, and it times out already.
Not sure how to use python to solve this.
Did you read my post above?
As this is an optimization problem I see nothing wrong with faster languages having an advantage. Choose the right tool for the right problem. You wouldn’t fight a nail with a screwdriver either.
1 Like
Yes, I managed to optimize Python for a 100% correct. The total guesses is 3000+ though, so it is definitely not optimal.
I simply ignored the cows, and also used a generator instead of a list for itertools.
Also, I only evaluated codeword’s eligibility based on the previous guess’s result.
Any further optimization would result in a timeout:(
1 Like
don’t do that -> list(permutations((1,2,3,4,5,6,7,8,9,0), 10))
Build an algorithm according to this principle -> for guess in permutations((1,2,3,4,5,6,7,8,9,0), 10):
This has been frustrating me for weeks now (on and off…not beating a dead horse). I started with a simple Python routine that timed out at n=9 just like others have, and converted to C++. Semi-nice C++, at first, and that still timed out on simple approaches. It’s morphed into a C/C++ mess in two “game loop” phases.
It works fine offline, but croaks at CG. Is there some trap in the library to inhibit use of timers to guard against using them as a timeout-avoidance watchdog? Nothing I’ve timed separately uses even 5 ms if I keep the blocksize down, but I still get timeouts–usually while growing my data. Is a 48MB array too big for this? How would I find out about environmental limits like that?
See here:
There are other interesting pragmas to use but the last one given will already make a difference.
Found this one in another thread for example:
#pragma GCC optimize(“unroll-loops”)
Personally my algorithm doesn’t manage to clear all possibilities in one turn (but my code might be suboptimal) I need several turns before knowing exactly the number of possibilities left. At each turn I prune possibilities as long as I have time left.
A way to track time is to use chrono::high_resolution_clock => start the timer after reading the 1st input, and ensure you print a response before you run out of time (you might want to take a 5-10ms buffer)
Also I think cg “timeout” error isn’t always a real timeout. Sometimes it might be because you run out of memory (but the max memory is around 700MB so unless you have memory leaks it shouldn’t be a pb for you if you only use 48MB) or other issues.
That’s exactly what I’m doing, except that I’ve used the recommendation (from cppreference.com) to use steady_clock instead of high-resolution_clock; presumably for better portability between Windows and Linux. I did try high_precision_clock first, though.
I don’t begin generating candidates until after getting a few responses random guesses, just to cut down the size of the candidates vector, and preallocate the maximum during the first turn (assuming that vector<>.reserve() actually does that on g++/linux). And I limit the number of entries to inspect to under 10,000 (have tried 1000…it’s a template parameter for my solver engine…no luck there) and give up attempts to compute more after 40 ms (have tried 30, no luck).
It’s twisted. I’m positive the issue is in my code, but I just can’t reproduce any measurable long delays with MinGW on my desktop. Maddening!
PS: You mentioned “700MB or so”…How would I find out what that limit it? Is it trial-and-error, or is there some page at CodinGame that lists general limits?
Thanks. I’ll play with that. Normally, I avoid pragmas (non-portable), so I wouldn’t have even looked for something like this.
Yes, that’s the ticket. Thanks!
My approach is to create an array of size 10! at the first turn where I store all the possibilities. Then I never reallocate memory (so no risk of memory leaks), based on the results of my guesses I just update the initial array (my updates only consists in overriding values in the array => possibilities[i]=newValue;) and store a few indexes of interest to know what are the possibilities left. Note the number of indexes I store is close to the number of guesses I made or less.
Then regarding the C++ pragma, I usually use the following for CG:
#pragma GCC target(“avx”)
#pragma GCC optimize(“O3”)
#pragma GCC optimize(“omit-frame-pointer”)
#pragma GCC optimize(“unsafe-math-optimizations”)
#pragma GCC optimize(“unroll-all-loops”)
#pragma GCC optimize(“inline”)
1 Like
That’s almost revised approach, btw, but it’s 9*9! instead of 10!. The first digit can’t be a zero in this problem. I’m depending on vector<>::reserve() right now. If I have to toss that and keep track of the size myself, I’ll probably switch to an array.
Thanks for the feedback. I’ll probably come back to this problem in couple of days, but it’s on hold for now.
Could someone explain to me how do you do better than the algorithm that eliminates permutations that don’t agree with the bulls/cows quantities given in the previous iteration?
My guess is that you just fiddle with the order of the initial candidates until you find one that gives the best overall lower score for the validators and then spam submits…
1 Like
I try to generate some statistics how the possible outcomes of my next guess are distributed.
Let’s assume you currently have 10 candidates. One guess reduces it to either 2 or 8 candidates depending on the outcome. Another possible guess would split the candidates evenly so you have 5 candidates remaining (simplified, the game works a little different).
What would be the better guess?
It can even be a good decision to guess an impossible number.
If your first guess is “12” and you have 1 matching digit, do you really want to continue with “13”, “14”, …, “19”? Or might “34”, “56”, … be better, even if that’s surely not the right one?
3 Likes