python – Task-quest (search for an exit from the room)

Question:

There is a list of strings like this:

DKDDGKKDDKDD
DDKGDDKKKKKKD
DDDDKKKDDKGDKKDDD

Where: G – Player K – Key D – Door
For each line, you need to find out if the player (G) can get out of the doors and go free.
When one door is opened, the key is lost and cannot be used again.

Rules: The player can only move to the left or right, to avoid the trap, G must be at the beginning or at the end of the line.

My decision:

levels = []
for _ in range(int(input())):
    levels.append(input())


def get_g_index(data: list):
    for i, c in enumerate(data):
        if c == "G":
            return i


def get_key(data: list):
    index = get_g_index(data)
    if data[index + 1] == "K":
        return "p"
    if data[index - 1] == "K":
        return "l"
    return "s"


def count_doors(data: list):
    out = 0
    for c in data:
        if c == "D":
            out += 1
    return out


def count_keys(data: list):
    out = 0
    for c in data:
        if c == "K":
            out += 1
    return out


for level in levels:
    chars = list(level)
    keys = 0
    while get_g_index(chars) != 0 or get_g_index(chars) != len(chars) - 1:
        # print("".join(chars), keys)
        key_res = get_key(chars)
        g_index = get_g_index(chars)
        if g_index == 0 or g_index == len(chars) - 1:
            print("da")
            break
        if key_res == "s":
            if keys == 0:
                print("net")
                break
            left = count_keys(chars[:get_g_index(chars)])
            right = count_keys(chars[get_g_index(chars):])
            offset = 1 if right > left else -1
            if chars[g_index + offset] == "D":
                keys -= 1
                chars.pop(g_index + offset)
                continue
        elif key_res == "p":
            keys += 1
            chars.pop(g_index + 1)
        elif key_res == "l":
            keys += 1
            chars.pop(g_index - 1)
    # print("".join(chars), keys)

Answer:

Well… It's probably not optimal, because the brute-force and written, recursive solution in C ++ is used as the first zero approximation:

int k(string& s)
{
    int ks = 0;
    int pos = s.find('G');
    for(int p = pos; p >= 0 && s[p] != 'D'; --p)
        if (s[p] == 'K') { s[p] = ' '; ++ks; }
    for(int p = pos; p < s.size() && s[p] != 'D'; ++p)
        if (s[p] == 'K') { s[p] = ' '; ++ks; }
    return ks;
}


bool l(const string& s, int keys);
bool r(const string& s, int keys);

bool l(const string& s, int keys)
{
    int pos = s.find('G');
    if (pos == 0 || pos == s.size()-1) return true;
    string t = s;
    keys += k(t);
    int p = pos-1;
    for(; p >= 0; --p)
    {
        if (t[p] == 'D')
        {
            if (keys > 0)
            {
                t[p] = ' ';
                keys--;
                t[p] = 'G';
                t[pos] = ' ';
                return l(t,keys)||r(t,keys);
            }
            return false;
        }
    }
    return true;
}

bool r(const string& s, int keys)
{
    int pos = s.find('G');
    if (pos == 0 || pos == s.size()-1) return true;
    string t = s;
    keys += k(t);
    int p = pos+1;
    for(; p < t.size(); ++p)
    {
        if (t[p] == 'D')
        {
            if (keys > 0)
            {
                t[p] = ' ';
                keys--;
                t[p] = 'G';
                t[pos] = ' ';
                return l(t,keys)||r(t,keys);
            }
            return false;
        }
    }
    return true;
}

int main(int argc, char * argv[])
{
    
    string s = "DKDDGKKDDKDD";
    cout << (l(s,0)||r(s,0)) << endl;
    s = "DDKGDDKKKKKKD";
    cout << (l(s,0)||r(s,0)) << endl;
    s = "DDDDKKKDDKGDKKDDD";
    cout << (l(s,0)||r(s,0)) << endl;
    
}

Well, since they write here with paths … I'll write it too 🙂
See here .