solve_well_ordered.py

def find_n(haystack, needle, n):
    st = haystack.find(needle)
    while st >= 0 and n >= 1:
        st = haystack.find(needle, st + 1)
        n -= 1
    return st


def mod_input(user_input, position, character):
    user_input = list(user_input)
    user_input[position] = character
    return "".join(user_input)


class rule:
    first_char = ""
    first_index = 0
    second_char = ""
    second_index = 0
    rules = []
    prev_rule = None

    def __init__(self, a, b, c, d, prev_rule):
        self.first_index = int(a)
        self.first_char = b
        self.second_index = int(c)
        self.second_char = d
        self.prev_rule = prev_rule

    def print(self):
        print(
            "{} index of {} before {} index {}".format(
                self.first_index, self.first_char, self.second_index, self.second_char
            )
        )

    def check(self, buf, no_prev_check=False):

        a = find_n(buf, self.first_char, self.first_index)
        b = find_n(buf, self.second_char, self.second_index)

        # Check local rule first
        if a >= b:
            return False

        # Must pass previous rules
        # self.print()
        if self.prev_rule and not no_prev_check:
            if not self.prev_rule.check(buf):
                return False

        return a < b

    def fix(self, buf):
        return self.try_move(buf)

    def move_first_back(self, buf):
        a = find_n(buf, self.first_char, self.first_index)
        # print(a)
        i = a
        while i >= 0:
            b = list(buf)
            d = b.pop(a)
            b.insert(i, d)
            n_buf = "".join(b)
            if self.first_char == "c":
                print(n_buf)

            if self.check(n_buf):
                return n_buf
            i -= 1
        return ""

    def move_first_forward(self, buf):
        a = find_n(buf, self.first_char, self.first_index)
        i = a
        while i < 40:
            b = list(buf)
            d = b.pop(a)
            b.insert(i, d)
            n_buf = "".join(b)

            if self.check(n_buf):
                return n_buf
            i += 1
        return ""

    def move_sec_back(self, buf):
        a = find_n(buf, self.second_char, self.second_index)
        i = a
        while i >= 0:
            b = list(buf)
            d = b.pop(a)
            b.insert(i, d)
            n_buf = "".join(b)

            if self.check(n_buf):
                return n_buf
            i -= 1
        return ""

    def move_sec_forward(self, buf):
        a = find_n(buf, self.second_char, self.second_index)
        i = a
        while i < 40:
            b = list(buf)
            d = b.pop(a)
            b.insert(i, d)
            n_buf = "".join(b)

            if self.check(n_buf):
                return n_buf
            i += 1
        return ""

    def try_move(self, buf):
        n_buf = self.move_first_back(buf)
        if n_buf:
            return n_buf
        n_buf = self.move_first_forward(buf)
        if n_buf:
            return n_buf
        n_buf = self.move_sec_forward(buf)
        if n_buf:
            return n_buf
        n_buf = self.move_sec_back(buf)
        if n_buf:
            return n_buf

        return ""


# Use radare2 to pull out the rules:
# r2 -> s main;pdc|grep before
rules = """
1 R 6 _
0 N 5 _
0 s 4 _
0 d 3 3
2 3 3 _
0 2 2 0
0 F 2 3
0 R 2 _
0 c 1 5
0 e 1 e
0 r 1 3
1 0 1 r
1 3 1 _
3 _ 1 1
3 3 1 R
5 _ 1 0
0 0 0 u
0 _ 0 5
0 1 0 F
0 3 0 _
0 4 0 k
0 5 0 U
0 8 0 c
0 a 0 8
0 i 0 N
0 k 0 3
0 l 0 1
0 m 0 4
0 u 0 R
0 U 0 r
0 y 0 0
1 _ 0 y
1 1 0 s
1 5 0 2
1 r 0 d
2 0 0 e
2 _ 0 l
4 _ 0 i
6 _ 0 a
"""

import random

buf = "_______3333000RRrr5511NSdF2recyUumlkia84"
buf = "m4k3_a8_y0uR_____5Ur3e020Rcr5l11iNSdF3re"
buf = "m4k3_5Ur3_y0uR_l1F3__iN_R_a80c520er1Sdre"
buf = "m4k3_5Ur3_y0uR_l1F3__iN_R_a80c520er1sdre"
buf = "m4k3_5Ur3_y0uR_l1F3_1s_iN_0rd3R_a8c520ee"
buf = "m4k3_5Ur3_y0uR_l1F3_1s_iN_0rd3R_a8c520ee"
buf = "Uirr3180N_Fs4y_032k_m0eR5_c_3l_Reau1d_35"

# m4k3_5Ur3_y0uR_l1F3__iN_R_a80c520er1Sdre
# m4k3_5Ur3_y0uR_l1F3__iN_R_a80c520er1Sdre
rules = rules.split("\n")

# There are issues in my solve, but randomness fixes it!
while True:
    rules_list = []
    n_rule = None
    prev_rule = None
    i = 0
    random.shuffle(rules)
    for line in rules:
        sp = line.split(" ")
        print(sp)
        if len(sp) > 2:
            n_rule = rule(sp[0], sp[1], sp[2], sp[3], prev_rule)
            # n_rule.print()
            if n_rule.check(buf):
                print(buf)
            else:
                a = n_rule.try_move(buf)
                if a == "":
                    break

                print(a)
                buf = a
            prev_rule = n_rule
    # break