And here I was thinking that you resorted to such disgusting strategies. I should be ashamed 
Also check 0 at the end. After exhaust of guessing with all other digits.
1 Like
While this video is about a word puzzle and some frequency analysis (more common words), some ideas can be applied here too, so Iāll leave this link:
1 Like
Ow thanks, this actually dropped from 17 to 14 turns to guess a 10-digits number (using worst case, 9876543210)
I just donāt understand how itās statistically possibly to guess a 10 digit number in 11 tries (on average)ā¦ Even a 1 digit number will take on average 5 tries (no matter what you do)
My algorithm finds the correct answer 100% of the time and it can find a 10 digit number in 11 tries but the average for 10 digit is 20ish. My total score is usually in the 600s, which got me 97th rank currently. I guess I can improve it to 500 but I have no idea what I can do to make it 300.
Oh, and from reading the other answers it seems Iām taking a somewhat unique approach since I donāt generate any list of candidates, ever, but I (almost) always conclude something based on the previous guess.
There is only one exception, if the number has 10 digits and I donāt yet know any of the digits is correct and my current guess has 1 more or less bull than the previous guess then I canāt conclude anything and I have to take a random guess within the possibilities left (I donāt actually enumerate them but I know what is possible and not) and hope that I will learn more from this guess. I will always learn more from a guess if:
- I have 2 more bulls than before
- I have 2 less bulls than before
- I have the same number of bulls as before
- I have +1 or -1 bull but I know at least one digit that is correct
In the case of a 10 digit number I always swap 2 digits with one another, I donāt change any more digits at a time (with less than 10 digits I sometimes do slightly different things but very similar). Maybe Iām thinking incorrectly and I can learn more things if I change more than 2 digits at a time? Iām just not seeing how.
You get much more information in each turn than just a yes/no on a single digit. Any two nonnegative numbers that add up to 10 or less can be the bulls and cows number on the first guess. I count 66 ways to do that. If you could manage to pick 11 guesses that allowed all 66 as possible responses, youād have 66^11 (about 10^20) different outcomes. Thatās much larger than the 9*9! different permutations of 10 different digits. (Itās not 10! because starting with 0 isnāt allowed.)
I havenāt solved this either, mind you. My best efforts start timing out at 8 or 9 digits; and itās been over a year since Iāve looked at it. But the problem is not that you donāt have enough guesses.
input takes too much time
Iām trying to solve this code in python, and i got my code well optimized on my local machine.
When i run the code here it fails.
Just this line:
bulls, cows = [int(i) for i in input().split()]
in length=7 takes 0.026 seconds(!!!) thatās halve my time before i even make my first calculation.
furthermote, when length=10, i donāt even get to play at all
The code time out WHILE I AM WAITING FOR THE INPUT.
This really sucks.
Iām able to pass the cases of all lengths using Python.
For length = 7, Iāve just tested and the times taken fluctuate, they donāt always take that long:
1.535564661026001e-05
0.02330956608057022
0.015239864587783813
0.00899823009967804
0.01259557157754898
0.011282496154308319
0.01021578162908554
0.015029437839984894
0.011362001299858093
0.012918345630168915
0.019634902477264404
0.011520110070705414
0.007642380893230438
Congrats! You guessed the number!
How can i know why mine takes that much time?
I keep a numpy array of all permutations, maybe i override some cached data?
If so, it should be mentioned in the instructions.
If not - Iām not sure what causes this huge delay and I canāt debug at as itās inside the game-code.
I see you also have a case in which it takes 0.025 seconds, which is half the allocated time.
With length=7, i timed just this line:
inp = input()
START INPUT Time: 1.7642974853515625e-05
DONE INPUT Time: 0.03803086280822754
START INPUT Time: 1.9073486328125e-05
DONE INPUT Time: 0.026268720626831055
START INPUT Time: 2.002716064453125e-05
DONE INPUT Time: 0.04100823402404785
It may not be the entire turn, but itās NOT enough for almost any calculation
This is my entire code, it does nothing:
import sys
import math
import time
global stime
stime = time.time()
def dtime_reset():
global stime
stime = time.time()
def dtime(s='', reset=False):
global stime
duration = time.time() - stime
dprint(f"{s} Time: {duration}")
if reset:
stime = time.time()
return duration
def dprint(s=''):
print(s, file=sys.stderr, flush=True)
number_length = int(input())
# game loop
dmax = 0
while True:
dtime_reset()
dtime('Start')
bulls, cows = [int(i) for i in input().split()]
d = dtime('END')
dmax = max(d,dmax)
dprint(f"Max time: {dmax}")
print("1324568790")
And i get for length=10:
Max time: 0.038558244705200195
Iāve tried the following code for length = 10, and get the recorded times below that code. The times arenāt that long for a large part of the game.
import sys
import math
from time import perf_counter
number_length = int(input())
# game loop
while True:
start_time = perf_counter()
bulls, cows = [int(i) for i in input().split()]
print(perf_counter() - start_time, file=sys.stderr, flush=True)
print("1234567890")
List of times recorded
Standard Error Stream:
2.1832995116710663e-05
0.04851056495681405
0.011203338857740164
0.01132274093106389
0.008120694197714329
0.00765317864716053
0.007310169283300638
0.0066608828492462635
0.009849573951214552
0.007722716312855482
0.018940057139843702
0.006905001122504473
0.005635213106870651
0.007339745759963989
0.00820893282070756
0.014756064396351576
0.007134100887924433
0.008133003953844309
0.01498021511361003
0.012627769261598587
0.008482198230922222
0.007910226937383413
0.006433352828025818
0.012416699901223183
0.009007818065583706
0.005721257999539375
0.006209801882505417
0.009304319974035025
0.0060331979766488075
0.01030822191387415
0.006714434828609228
0.00912666181102395
0.00854891911149025
0.007036163937300444
0.006926204077899456
0.007145315874367952
0.006864085793495178
0.008713958319276571
0.0070131453685462475
0.006533164996653795
0.00813634367659688
0.016718624159693718
0.00515703484416008
0.006033619865775108
0.00529540004208684
0.007085264194756746
0.004975412972271442
0.005473676137626171
0.005278200842440128
0.006225326098501682
0.008122873026877642
0.005518936086446047
0.006805946119129658
0.007013560272753239
0.005405608098953962
0.012608364690095186
0.005443342961370945
0.006075853016227484
0.005168422125279903
0.008045937400311232
0.0053945486433804035
0.005412491969764233
0.006516255903989077
0.008382103871554136
0.005507662892341614
0.007765267044305801
0.005060988012701273
0.006292554084211588
0.005153043661266565
0.005471833050251007
0.00576329231262207
0.007457191124558449
0.0050997259095311165
0.005504042375832796
0.006605626083910465
0.005242499057203531
0.009328037966042757
0.005910682026296854
0.00668879970908165
0.005982124712318182
0.005772222764790058
0.008116756100207567
0.008189280983060598
0.005468567833304405
0.005896151997148991
0.010248994920402765
0.005280815996229649
0.005377830937504768
0.005514109041541815
0.005368374288082123
0.005500485189259052
0.005135403946042061
0.006388322915881872
0.005456575192511082
0.00557831721380353
0.008816211018711329
0.006846159230917692
0.008946141228079796
0.0052789971232414246
0.005599789787083864
0.005610658787190914
0.005143863148987293
0.006089252885431051
0.00944150798022747
0.0069542499259114265
0.005412740167230368
0.005286342930048704
0.005793424788862467
0.008955411147326231
0.005482455249875784
0.005384484305977821
0.005132854916155338
0.005531311966478825
0.0056592850014567375
0.006470925640314817
0.012313433922827244
0.006934424862265587
0.006583971902728081
0.005413301754742861
0.006634050980210304
0.005829107016324997
0.009558502119034529
0.005481414962559938
0.006656993646174669
0.005681703332811594
0.00551967415958643
0.005222317297011614
0.006835736334323883
0.005874833092093468
0.010742757935076952
0.006782039999961853
0.005530645605176687
0.005658007226884365
0.005331285763531923
0.006254707928746939
0.005810136906802654
0.005373618099838495
0.006040505133569241
0.007467079907655716
0.006033708807080984
0.005343814846128225
0.005922205280512571
0.006841821130365133
0.012026052922010422
0.005778345745056868
0.006592562887817621
0.005423287861049175
0.005461703985929489
0.005690340884029865
0.00717971520498395
0.005087513942271471
0.00539214676246047
0.005540275946259499
0.005535217002034187
0.005563380196690559
0.005569139961153269
0.013787732925266027
0.005376401357352734
0.0056265839375555515
0.0052224211394786835
0.005227777641266584
0.005778056103736162
0.005341788288205862
0.018871954642236233
0.006285991054028273
0.005114880856126547
0.005533048417419195
0.01469108834862709
0.00832545105367899
0.032197059132158756
0.03245544480159879
0.01815598178654909
0.005343573167920113
0.01833772612735629
0.005658203735947609
0.005522612016648054
0.005188432056456804
0.017937418073415756
0.005653757136315107
0.0050416430458426476
0.00574034359306097
0.005189239047467709
0.011412586085498333
0.005309756379574537
0.005352082662284374
0.00565468380227685
0.005269167944788933
0.005773092154413462
0.007216634228825569
0.025098122656345367
0.0065469080582261086
0.005957731977105141
0.009943525772541761
0.006650375202298164
0.00721840700134635
0.005339495837688446
0.0053886957466602325
0.005312708672136068
0.0052535259164869785
0.005100629758089781
0.02246202016249299
0.005330702755600214
0.005258026998490095
0.004927760921418667
0.0051682149060070515
0.010523824952542782
0.005174119956791401
0.01673404173925519
0.005824754945933819
0.005523484665900469
0.005090600810945034
0.005769295152276754
0.017884455155581236
0.006208417005836964
0.005899849813431501
0.005274991970509291
0.0050915018655359745
0.027104851324111223
0.006881516892462969
0.005585234146565199
0.005433966405689716
0.005740323103964329
0.006013913080096245
0.00577242486178875
0.005517646670341492
0.005374295171350241
0.005783169064670801
0.004933953285217285
0.005582096055150032
0.005154517944902182
0.005779712926596403
0.0050119319930672646
0.006400017067790031
0.005297662690281868
0.005642964970320463
0.005077763926237822
0.005585045088082552
0.005292743910104036
0.005190449766814709
0.005277623888105154
0.005499802064150572
0.005146795883774757
0.005490463692694902
0.005383310839533806
0.005765978712588549
0.005800134036689997
0.0053947363048791885
0.005973661784082651
0.005395007785409689
0.005741685628890991
0.006792502012103796
0.0051769376732409
0.005787896923720837
0.0053534298203885555
0.005642888136208057
0.007695146836340427
0.008554315194487572
0.0181162660010159
0.006083710119128227
0.005936425644904375
0.005335073918104172
0.005369009915739298
0.0058138309977948666
0.0056144739501178265
0.005687098018825054
0.015663533937186003
0.00568345794454217
0.005543026141822338
0.005675296764820814
0.005469447001814842
0.005587284918874502
0.005439779721200466
0.005376092158257961
0.006038063205778599
0.005810069385915995
0.005087878089398146
0.004594799131155014
0.005389377940446138
0.005210530012845993
0.005114603787660599
0.006755345966666937
0.005303084850311279
0.00975152337923646
0.005402442067861557
0.005393871106207371
0.01549962256103754
0.0056664892472326756
0.0051029147580266
0.008404106367379427
0.005346876103430986
0.007572655100375414
0.006185597740113735
0.005288087762892246
0.005206014029681683
0.005309124011546373
0.0055045937187969685
0.015376363415271044
0.005625119898468256
0.005445259623229504
0.004980958066880703
You did not make it in 300 turns!
Check the second line in your response:
0.04851056495681405
you got 2ms to respond. Itās simply not enough.
Hardly the promised 50ms
Probably not an issue, at least not for me. More info here: https://www.codingame.com/forum/t/questions-about-how-time-is-calculated/191835
What computation are you doing in 2ms?
Itās much less than specified.
And again, i can show you in my code on CodinGame env. that i timeout before the response.
Iāve spent hours on this solution and failing because the game does not match the criteria the it itself declared is not cool.
You can PM me your code to have a look.
Based on the explanation in the link above, I donāt think the time youāre talking about is relevant.
The 50ms per turn makes this puzzle frustrating since the timeout becomes the actual target for optimization, but itās affected by performance fluctuations so you can end up with different scores resubmitting the same solution. For instance, my best Python solution was 513, I spend some time trying to optimize it and got 567. I reloaded the 513 solution and resubmitted it without changes and got 532.
Maybe Iām wrong, but I feel like the ranking shouldnāt be affected by random factors like that.