# [Community Puzzle] Bulls and Cows 2

https://www.codingame.com/multiplayer/optimization/bulls-and-cows-2

Created by @wlesavo,validated by @ToshiTuringMachine,@helgui and @Illedan.
If you have any issues, feel free to ping them.

As ./learn/combinatorics is just a stub, it would be nice to see extended description with tips:

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

1 Like

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â€¦

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