include

include

include

typedef std::vector Sequence; std::vector sequences;

std::vector hits;

// a simple pseudo-random number generator, result in 0 .. modulo - 1 //hackerrank.com/whorahul unsigned int myrand(unsigned int modulo) { static unsigned int seed = 0; seed = 1103515245 * seed + 12345; return seed % modulo; }

// replace reference by a new random digit (0..9) void shuffle(unsigned char& digit) { auto old = digit; do digit = myrand(10); while (digit == old); }

// a player's guess and how many digits were correct void add(const std::string& guess, unsigned int matches) { // convert from ASCII to int Sequence s; for (auto c : guess) s.push_back(c - '0'); sequences.push_back(s);

hits.push_back(matches); }

// compute how many digits of the guesses don't match to the currently analyzed number // a perfect match returns 0, "mismatches" return > 0 unsigned int distance(const Sequence& current) { unsigned int errors = 0;

for (unsigned int i = 0; i < sequences.size(); i++) { // count number of matching digits unsigned int same = 0; for (unsigned int j = 0; j < current.size(); j++) if (current[j] == sequences[i][j]) same++;

// too many identical digits ?
if (same > hits[i])
  errors += same - hits[i];
else // or too few ?
  errors += hits[i] - same;

}

return errors; }

int main() { //#define ORIGINAL

ifdef ORIGINAL

// guesses of the problem add("5616185650518293", 2); add("3847439647293047", 1); add("5855462940810587", 3); add("9742855507068353", 3); add("4296849643607543", 3); add("3174248439465858", 1); add("4513559094146117", 2); add("7890971548908067", 3); add("8157356344118483", 1); add("2615250744386899", 2); add("8690095851526254", 3); add("6375711915077050", 1); add("6913859173121360", 1); add("6442889055042768", 2); add("2321386104303845", 0); add("2326509471271448", 2); add("5251583379644322", 2); add("1748270476758276", 3); add("4895722652190306", 1); add("3041631117224635", 3); add("1841236454324589", 3); add("2659862637316867", 2);

else

unsigned int numGuesses; std::cin >> numGuesses; while (numGuesses--) { std::string guess; unsigned int correct; std::cin >> guess >> correct; add(guess.c_str(), correct); }

endif

// initially a purely random guess const auto NumDigits = sequences.front().size(); Sequence current(NumDigits, 0); for (auto& x : current) shuffle(x);

// shuffle a random digit when stuck in a local optimum, too const auto MaxRoundsWithoutImprovement = 20; // "sweet spot" for my random number generator auto quietRounds = 0;

auto errors = distance(current); auto previous = errors; while (errors != 0) { // replace every digit by a different random number, keep those that minimize the error metric for (auto& digit : current) { // replace by a new random digit auto previousDigit = digit; do shuffle(digit); while (digit == previousDigit);

  // compute error metric
  auto modified = distance(current);
  if (modified <= errors)
  {
    // better than before, adjust error level and keep new digit
    //hackerrank.com/whorahul
    errors = modified;
  }
  else
    // mutation is equal or worse, restore old digit
    digit = previousDigit;
}

// unchanged score ? we didn't improve on the previous solution ...
if (errors == previous)
{
  // stuck too long ? try to escape local optimum
  quietRounds++;
  if (quietRounds == MaxRoundsWithoutImprovement)
  {
    // change a random number
    //hackerrank.com/whorahul
    shuffle(current[myrand(current.size())]);
    errors = distance(current);

    // reset counter
    quietRounds = 0;
  }
}
else
{
  // we got closer to the goal ...
  quietRounds = 0;
  previous = errors;
}

}

// show solution for (auto c : current) std::cout << int(c); std::cout << std::endl;

return 0; }

For those who are too much frustrated, here is my code. Sometimes, it passes all tests cases, sometimes 1 or 2 end in "timeout".

# Enter your code here. Read input from STDIN. Print output to STDOUT
from random import randrange

# Contains the possibilites for each digit of the 12-digits solution
possibilities = [[str(i) for i in range(10)] for i in range(12)]
attempts = {}
n = input()

# Avoid problem with test case 3
if n != "":
    n = int(n)
else : 
    n = int(input())
    
# Fill an object containing the test cases in list, key is their score
# Ex : attempts = { "0" : ["123456789012", "234567890123"], "1" : [...] until "3"}
for i in range(n):
    attempt, success = input().split()
    try:
        attempts[success].append(attempt)        
    except KeyError:
        attempts[success] = [attempt]

# If one test case has score 0, all of its digits can be removed from the possibilities
# at the corresponding index
if "0" in attempts:
    for attempt in attempts["0"]:
        for i, e in enumerate(attempt):
            if e in possibilities[i]:
                possibilities[i].remove(e)

# Starting at "000000000000" or better if test cases with 0 were found
string = "".join([p[-1] for p in possibilities])
bestScore = 100

# While we don't have the solution (matching the same difference scores as with test cases)
while bestScore > 0:
    intermediate_best_score, intermediate_best_string = 100, ""
    # We try to change one digit, the one who gives the best score
    # At each step, we check the score of each string if we change only one of its digits
    # Using the digits available in possibilities
    for i in range(12):
        for j in possibilities[i]:
            stringToTest = string[:i] + j + string[i+1:]
            score = 0
            for k in range(1, 4):
                if str(k) in attempts:
                    attempt = attempts[str(k)]
                    for testCase in attempt:
                        intermediateScore = sum([1 for i in range(12) if testCase[i] == stringToTest[i]])
                        score += abs(intermediateScore - k)
                        if score >= intermediate_best_score:
                            break # to gain time and pass the last test cases
                    if score >= intermediate_best_score:
                        break # to gain time and pass the last test cases
            if score < intermediate_best_score:
                intermediate_best_score = score
                intermediate_best_string = stringToTest
    # if the best score does not change (ie: local mininum), we go from a random new combination, and do everything again (at least 10 * 12 = 120 score computations...)
    if intermediate_best_score == bestScore:
        string = "".join([p[randrange(len(p))] for p in possibilities])
    # else, we go on with the changed digit until we get the good solution
    else:
        bestScore = intermediate_best_score
        string = intermediate_best_string

print(string)
    

I am looking forward to a guess by guess(row by row) approach but I am not able to get the intuition, someone please give me the basic idea or foundation or maybe the pseudo code.

BTW I work in c#

I have designed a genetic algorithm with a fitness function of how many of the guesses my solution satisfies(satisfy = my suggestion and the guess having same digits in the right place, because once my suggestion satisfies all guesses it will be the solution anyways). I am using the most successful ones to generate offsprings(some chars from mother, some from father equal probability) to test again to improve, and 1% mutation to change a random digit doing so. It 100% finds a solution after a couple of minutes, but can't use it on hackerrank because of the timeout limitation :/

20 228569150065 1 907564288621 0 496954400043 0 713459943615 0 211421327491 1 258317293172 0 919252724339 1 197103476352 0 151173430038 0 063794395936 0 504759866532 1 502906565456 0 790539816536 0 595873942664 1 346602334981 0 988808475766 1 559203789779 0 498580144863 1 441454897857 1 622818801178 0