# requires https://github.com/perrygeo/simanneal library
# Malbolge interpreter has been copypasted from https://github.com/Avantgarde95/pyMalbolge and reworked
# interpreter: http://malbolge.doleczek.pl/

from __future__ import print_function
from __future__ import with_statement
import math
import random
from simanneal import Annealer
import sys

TABLE_CRAZY = (
    (1, 0, 0),
    (1, 0, 2),
    (2, 2, 1)
)

ENCRYPT = map(ord,
              '5z]&gqtyfr$(we4{WP)H-Zn,[%\\3dL+Q;>U!pJS72FhOA1CB'\
              '6v^=I_0/8|jsb9m<.TVac`uY*MK\'X~xDl}REokN:#?G\"i@')

OPS_VALID2 = (4, 5, 23, 39, 40, 62, 68, 81)
OPS_VALID = (4, 5, 39, 40, 62, 68) # without 23 (read), 81 (end)

POW9, POW10 = 3**9, 3**10

# --------------------------------------------------

def rotate(n):
    return POW9*(n%3) + n/3

def crazy(a, b):
    result = 0
    d = 1

    for i in xrange(10):
        result += TABLE_CRAZY[(b/d)%3][(a/d)%3] * d
        d *= 3

    return result

def initialize(source, mem):
    i = 0

    for c in source:
        if c == ' ' or c == '\n':
            continue

        if (ord(c)+i) % 94 not in OPS_VALID2:
            print ('Invalid character in the source file:', ord(c)+i, ' at: ', i)
            sys.exit(1)

        if i == POW10:
            print ('Source file is too long')
            sys.exit(1)

        mem[i] = ord(c)
        i += 1

    while i < POW10:
        mem[i] = crazy(mem[i-1], mem[i-2])
        i += 1

def interpret(mem):
    written=""
    steps=0

    a, c, d = 0, 0, 0

    while 1:
        if mem[c] < 33 or mem[c] > 126:
            return written, steps

        v = (mem[c]+c) % 94

        if v == 4:                        # jmp [d]
            c = mem[d]
        elif v == 5:                      # out a
            #write(chr(a % 256))
            #flush()
            written=written+chr(a % 256)
        #elif v == 23:                     # in a
        #    a = ord(read(1))
        elif v == 39:                     # rotr[d]; mov a, [d]
            a = mem[d] = rotate(mem[d])
        elif v == 40:                     # mov d, [d]
            d = mem[d]
        elif v == 62:                     # crz [d], a; mov a, [d]
            a = mem[d] = crazy(a, mem[d])
        elif v == 68:                   # nop
             pass
        elif v == 81:                     # end
            return written, steps
        else:
            pass

        if mem[c] >= 33 and mem[c] <= 126:
            mem[c] = ENCRYPT[mem[c] - 33]

        c = 0 if c == POW10-1 else c+1
        d = 0 if d == POW10-1 else d+1
        steps=steps+1

    return written, steps

# --------------------------------------------------

def calc_fitness(state):

    mem = [0] * POW10
    if initialize("".join(state), mem)==False:
        return 0

    written, steps = interpret(mem)
    need="Hi"

    # bonus: 10 for each written character
    fitness=len(written)*10

    # bonus: 50 if only 2 characters written
    if len(written)==2:
        fitness=fitness+50

    # bonus: 50 if characters are different
    if len(written)>=2 and written[0]!=written[1]:
        fitness=fitness+50
    if written==need:
        print ("found!")
        print ("".join(state))
        exit(0)

    # bonus: 100 if character is what we need
    if len(written)==1:
        if written[0]==need[0]:
            fitness=fitness+100
    if len(written)==2:
        if written[1]==need[1]:
            fitness=fitness+100
    return -fitness

class TestProblem(Annealer):

    # pass extra data (the distance matrix) into the constructor
    def __init__(self, state):
        super(TestProblem, self).__init__(state)  # important!

    def move(self):
        while True:
            #if (ord(c)+i) % 94 not in OPS_VALID:
            idx = random.randint(0, len(self.state) - 2) # do not touch the last END ins
            a=random.choice(OPS_VALID)
            if a<idx:
                a=a+94
            if a-idx<32:
                continue
            if a-idx>127:
                continue
            t=chr(a-idx)
            if t!=' ' and t!='\n':
                self.state[idx] = t
                return

    def energy(self):
        return calc_fitness(self.state)

if __name__ == '__main__':

    init_state=[]
    pgm_len=13
    # fill with NOPs:
    for i in range(pgm_len):
        init_state.append(chr(68-i))
    # the last ins is END:
    init_state[pgm_len-1]=chr(81-(pgm_len-1))

    test = TestProblem(init_state)
    test.steps = 4000
    # since our state is just a list, slice is the fastest way to copy
    test.copy_strategy = "slice"
    state, e = test.anneal()

    print()
    print("%i energy:" % e)
    pgm="".join(state)
    print (pgm)

    mem = [0] * POW10
    initialize(pgm, mem)
    print (interpret(mem))