solver for https://hard.mathler.com

hard.mathler.py

# solver for https://hard.mathler.com
# copyright@gooooloo

import random

def answer_to_score(answer):
    ret = 0
    for ch in answer:
        ret <<= 2
        if ch == 'g':
            ret |= 0
        elif ch == 'y':
            ret |= 1
        elif ch == 'b':
            ret |= 2
        else:
            assert(False)
    return ret

def calc_score(gt, guess):
    assert len(guess) == len(gt)

    gt = [ch for ch in gt]
    guess = [ch for ch in guess]
    answer = ['0' for _ in guess]
    for i,ch in enumerate(guess):
        if ch == gt[i]:
            answer[i] = 'g'
            gt[i] = ' '
            guess[i] = ' '
        
    for i,ch in enumerate(guess):
        if ch != ' ':
            k = next((i for i,chgt in enumerate(gt) if chgt == ch), None)
            if k is None:
                answer[i] = 'b'
            else:
                answer[i] = 'y'
                gt[k] = ' '

    return answer_to_score(answer)

def choose_guess(candidates):
    sample_size = 1024
    if len(candidates) > sample_size:
        print(f'sampling {sample_size} out of {len(candidates)} candidates...')
        candidates = random.sample(candidates, sample_size)

    best_guess = None
    best_mark = None
    for gi, guess in enumerate(candidates):
        if gi % 100 == 0:
            print(f'searching {gi} / {len(candidates)}')

        contour = {}
        for gt in candidates:
            score = calc_score(gt, guess)
            if score not in contour:
                contour[score] = set()
            contour[score].add(gt)

        mark = 0
        for k in contour:
            mark += len(contour[k]) ** 2

        if not best_mark or mark < best_mark:
            best_guess = guess
            best_mark = mark
    
    return best_guess

def ndigit(n):
    if 0 <= n <= 9:
        return 1
    if 10 <= n <= 99:
        return 2
    assert False

def yield_a_b_3():
    for a in range(10):
        for b in range(10):
            yield a, b

def yield_a_b_4():
    for a in range(10, 100):
        for b in range(10):
            yield a, b
            yield b, a

def yield_a_op_b():
    def mygenerator():
        yield from yield_a_b_3()
        yield from yield_a_b_4()

    for a, b in mygenerator():
        yield (f'{a}+{b}', a+b)
        yield (f'{a}*{b}', a*b)
        if a >= b:
            yield (f'{a}-{b}', a-b)
        if b and a % b == 0:
            yield (f'{a}/{b}', a//b)

def gen_all(v, nchar, allow_num, allow_add_sub, allow_mul_div, cache):
    thekey = (v, nchar, allow_num, allow_add_sub, allow_mul_div)
    if thekey in cache:
        return cache[thekey]
    else:
        thevalue = set(yield_all(v, nchar, allow_num, allow_add_sub, allow_mul_div, cache))
        assert all(nchar == len(s) for s in thevalue)
        cache[thekey] = thevalue
        return thevalue

def yield_all(v, nchar, allow_num, allow_add_sub, allow_mul_div, cache):
    assert allow_num or allow_add_sub or allow_mul_div

    if allow_num:
        if 0 <= v <= 99 and nchar == ndigit(v):
            yield f'{v}'
    
    if allow_add_sub and nchar >= 3:
        for k in range(100):
            # ANY + k
            for s in gen_all(v - k, nchar - ndigit(k) - 1, allow_num = True, allow_add_sub = True, allow_mul_div = True, cache = cache):
                yield f'{s}+{k}'

            # k + EXP
            for s in gen_all(v - k, nchar - ndigit(k) - 1, allow_num = False, allow_add_sub = False, allow_mul_div = True, cache = cache):
                yield f'{k}+{s}'

            # k + (EXP)
            for s in gen_all(v - k, nchar - ndigit(k) - 3, allow_num = False, allow_add_sub = True, allow_mul_div = True, cache = cache):
                yield f'{k}+({s})'

            # ANY - k
            for s in gen_all(v + k, nchar - ndigit(k) - 1, allow_num = True, allow_add_sub = True, allow_mul_div = True, cache = cache):
                yield f'{s}-{k}'

            # k - EXP
            for s in gen_all(k - v, nchar - ndigit(k) - 1, allow_num = False, allow_add_sub = False, allow_mul_div = True, cache = cache):
                yield f'{k}-{s}'

            # k - (EXP)
            for s in gen_all(k - v, nchar - ndigit(k) - 3, allow_num = False, allow_add_sub = True, allow_mul_div = True, cache = cache):
                yield f'{k}-({s})'

    if allow_add_sub and nchar >= 7:
        # EXP+EXP
        for s1,v1 in yield_a_op_b():
            for s2 in gen_all(v - v1, nchar - len(s1) - 1, allow_num = False, allow_add_sub = False, allow_mul_div = True, cache = cache):
                yield f'{s1}+{s2}'

        # EXP-EXP
        for s1,v1 in yield_a_op_b():
            for s2 in gen_all(v1 - v, nchar - len(s1) - 1, allow_num = False, allow_add_sub = False, allow_mul_div = True, cache = cache):
                yield f'{s1}-{s2}'

    if allow_mul_div and nchar >= 3 and v:
        for k in range(1, 100):
            if v % k == 0:
                # ANY * k
                for s in gen_all(v // k, nchar - ndigit(k) - 1, allow_num = True, allow_add_sub = False, allow_mul_div = True, cache = cache):
                    yield f'{s}*{k}'
                
                # (EXP) * k
                for s in gen_all(v // k, nchar - ndigit(k) - 3, allow_num = False, allow_add_sub = True, allow_mul_div = False, cache = cache):
                    yield f'({s})*{k}'
                
                # k * (EXP)
                for s in gen_all(v // k, nchar - ndigit(k) - 3, allow_num = False, allow_add_sub = True, allow_mul_div = True, cache = cache):
                    yield f'{k}*({s})'
            
            # k / (EXP)
            if v and k % v == 0:
                for s in gen_all(k // v, nchar - ndigit(k) - 3, allow_num = False, allow_add_sub = True, allow_mul_div = True, cache = cache):
                    yield f'{k}/({s})'

            # ANY / k
            for s in gen_all(k * v, nchar - ndigit(k) - 1, allow_num = True, allow_add_sub = False, allow_mul_div = True, cache = cache):
                yield f'{s}/{k}'
            
            # (EXP) / k
            for s in gen_all(k * v, nchar - ndigit(k) - 3, allow_num = False, allow_add_sub = True, allow_mul_div = False, cache = cache):
                yield f'({s})/{k}'

    if allow_mul_div and v == 0:
        # 0 / NUM
        # 0 * NUM
        # NUM * 0
        for k in range(1, 100):
            if nchar == ndigit(k) + 2:
                yield f'0/{k}'
                yield f'0*{k}'
                yield f'{k}*0'
        
        if nchar == 3:
            yield '0*0'

        # ...EXP... */ 0 */ ...EXP...
        def mygenerator():
            if nchar == 5:
                yield from yield_a_b_3()
            if nchar == 6:
                yield from yield_a_b_4()

        for a, b in mygenerator():
            yield f'{a}*{b}*0'
            yield f'{b}*{a}*0'
            yield f'0*{a}*{b}'
            yield f'0*{b}*{a}'
            yield f'{a}*0*{b}'
            yield f'{b}*0*{a}'
            if a:
                yield f'0/{a}*{b}'
                yield f'0*{b}/{a}'
                yield f'{b}*0/{a}'
            if b:
                yield f'0/{b}*{a}'
                yield f'0*{a}/{b}'
                yield f'{a}*0/{b}'
            if a and b:
                yield f'0/{a}/{b}'
                yield f'0/{b}/{a}'
            if b and a % b == 0:
                yield f'{a}/{b}*0'
            if a and b % a == 0:
                yield f'{b}/{a}*0'

def ask_target_n():
    n = input('please input the number:')
    print()
    return int(n)

def ask_answer():
    answer = input('\nplease input the check result(g/y/b):')
    if len(answer) != 8 or not all(ch in 'gyb' for ch in answer):
        answer = input('please input the check result(g/y/b):')
    print()

    return answer

def main():
    n = ask_target_n()
    assert n, 'n > 0 is required'

    print('generateing all candidates ...')
    candidates = gen_all(v=n, nchar=8, allow_num=True, allow_add_sub=True, allow_mul_div=True, cache={})
    print(f'{len(candidates)} candidates generated')

    while True:
        guess = choose_guess(candidates)
        print('guess: ', guess)

        answer = ask_answer()
        score = answer_to_score(answer)
        if score == 0:
            print('congratulations!')
            return

        candidates = [gt for gt in candidates if calc_score(gt, guess) == score]
        print(f'candidates limited to {len(candidates)} count')



if __name__ == '__main__':
    main()