[Community Puzzle] Bulls and Cows 2

And here I was thinking that you resorted to such disgusting strategies. I should be ashamed :slight_smile:

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:

  1. I have 2 more bulls than before
  2. I have 2 less bulls than before
  3. I have the same number of bulls as before
  4. 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.