Задачка-квест (поиск выхода из комнаты)

Question

Имеется список строк, примерно таких:

DKDDGKKDDKDD
DDKGDDKKKKKKD
DDDDKKKDDKGDKKDDD

Где: G - Игрок K - Ключ D - Дверь
Для каждой строки, нужно узнать может ли игрок (G) выбраться из дверей и выйти на свободу.
При открытии одной двери, ключ теряется и его нельзя больше использовать.

Правила: Игрок может двигаться только в лево или право, что бы избежать из ловушки, G должен быть на начале или на конце строки.

Мое решение:

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 1

Как минимум можно использовать

def get_g_index(data: list):
    return data.index('G')

def count_doors(data: list):
    return data.count('D')

def count_keys(data: list):
    return data.count('C')

Остальное понятно мало

Answer 2

Ну... Наверняка неоптимальное, потому что переборное и на коленке писанное, рекурсивное решение на С++ - в качестве ~~первого~~нулевого приближения:

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;
    
}

Ну, раз тут пишут с путями... Напишу и я :)
См. тут.

Answer 3

Вот решение на Python и без рекурсии. Ещё и приключенческий рассказ пишет. :)

(Первый вариант был красивый, но не совсем под условие задачи. Теперь вроде как решение соответствует заданию.)

Основной принцип алгоритма - сначала идём вправо. Если нашли ключ, то сохраняем состояние в стеке, чтобы из этой точки попытаться пойти налево в случае неудачи с правым путём. Если вправо упёрлись, то извлекаем состояние из стека, и пытаемся идти уже влево. Если идя влево найдём ключ, то алгоритм повторяется (пытаемся вправо, не получилось - откатываемся и пытаемся влево). И так пока либо не выйдем, либо стек состояний не опустеет (т.е. все варианты с найденными ключами перепробованы, и новых ключей не удаётся достать).

Если выхода нет, то path содержит самый короткий путь "убиться", а path из последнего элемента max_stack - самый длинный.

DOOR_LOCKED = 'D'
DOOR_OPENED = 'd'
PLAYER = 'G'
KEY    = 'K'
EMPTY  = '.'
LEFT   = -1
RIGHT  = +1
DIRS   = {RIGHT: '>>> Пойду направо', LEFT: '<<< Пойду налево'}

def solve(_maze, _print_path=False):
    maze  = list(_maze)
    pos   = maze.index(PLAYER)
    keys  = 0
    dir = RIGHT
    path  = []
    maze[pos] = EMPTY
    stack = [(maze[:], pos, keys, path[:])]
    max_stack = stack[:]
    while pos not in (-1, len(maze)):
        if DOOR_LOCKED == maze[pos]:
            if keys:
                keys -= 1
                maze[pos] = DOOR_OPENED
                path.append(f"   Дверь. Открываю. Осталось ключей: {keys}.")
            elif stack:
                maze, pos, keys, path = stack.pop()
                dir = LEFT
            else:
                maze, pos, keys, path = max_stack.pop()
                path.append("   Ключей больше нет. Я здесь умру! :(")
                if _print_path: 
                    print(_maze, "\nMoё смертельное приключение:\n"+"\n".join(path)+"\n")
                return False

        elif KEY == maze[pos]:
            keys += 1
            maze[pos] = EMPTY
            path.append(f"  Нашёл ключ. Стало ключей: {keys}.")
            stack.append((maze[:], pos, keys, path[:]))
            if len(stack) > len(max_stack): max_stack = stack[:]
            dir = RIGHT

        maze_tmp = maze[:]
        maze_tmp[pos] = "*"
        path.append("".join(maze_tmp) + " | " + DIRS[dir])
        pos += dir

    path.append(f"Ура! Я таки вышел! Осталось ключей: {keys}.")
    if _print_path: 
        print(_maze, "\nMoё успешное приключение:\n"+"\n".join(path)+"\n")
    return True

mazes = ["DKDDGKKDDKDD", "DDKGDDKKKKKKD", "DDDDKKKDDKGDKKDDD", "DDKGKDD", "DDDKGKDDKDD" ]
for maze in mazes:
    print(maze, "=>", "Ура! Выход есть!" if solve(maze, False) else "Увы. Выхода нет.")

#maze = "DDDDDDDDDKKDKKDKKDDDKGDKKKDDKDDKDDKD"
#maze = "DDDDDDDDDKKDKKDKKDDDKGDKKKDDKDDKDDKDDDDDDD"

for maze in ["DDGKKDKDDD", "DDDKDDKKGDKKDDDD"]:
    print(maze, "=>", "Ура! Выход есть!" if solve(maze, True) else "Увы. Выхода нет.", "\n")

DKDDGKKDDKDD => Ура! Выход есть!
DDKGDDKKKKKKD => Увы. Выхода нет.
DDDDKKKDDKGDKKDDD => Ура! Выход есть!
DDKGKDD => Ура! Выход есть!
DDDKGKDDKDD => Увы. Выхода нет.

DDGKKDKDDD 
Moё успешное приключение:
DD*KKDKDDD | >>> Пойду направо
  Нашёл ключ. Стало ключей: 1.
DD.*KDKDDD | >>> Пойду направо
  Нашёл ключ. Стало ключей: 2.
DD..*DKDDD | >>> Пойду направо
   Дверь. Открываю. Осталось ключей: 1.
DD...*KDDD | >>> Пойду направо
  Нашёл ключ. Стало ключей: 2.
DD...d*DDD | <<< Пойду налево
DD...*.DDD | <<< Пойду налево
DD..*d.DDD | <<< Пойду налево
DD.*.d.DDD | <<< Пойду налево
DD*..d.DDD | <<< Пойду налево
   Дверь. Открываю. Осталось ключей: 1.
D*...d.DDD | <<< Пойду налево
   Дверь. Открываю. Осталось ключей: 0.
*d...d.DDD | <<< Пойду налево
Ура! Я таки вышел! Осталось ключей: 0.

DDGKKDKDDD => Ура! Выход есть!

DDDKDDKKGDKKDDDD 
Moё смертельное приключение:
DDDKDDKK*DKKDDDD | <<< Пойду налево
  Нашёл ключ. Стало ключей: 1.
DDDKDDK*.DKKDDDD | >>> Пойду направо
DDDKDDK.*DKKDDDD | >>> Пойду направо
   Дверь. Открываю. Осталось ключей: 0.
DDDKDDK..*KKDDDD | >>> Пойду направо
  Нашёл ключ. Стало ключей: 1.
DDDKDDK..d*KDDDD | >>> Пойду направо
  Нашёл ключ. Стало ключей: 2.
DDDKDDK..d.*DDDD | <<< Пойду налево
DDDKDDK..d*.DDDD | <<< Пойду налево
DDDKDDK..*..DDDD | <<< Пойду налево
DDDKDDK.*d..DDDD | <<< Пойду налево
DDDKDDK*.d..DDDD | <<< Пойду налево
  Нашёл ключ. Стало ключей: 3.
DDDKDD*..d..DDDD | >>> Пойду направо
DDDKDD.*.d..DDDD | >>> Пойду направо
DDDKDD..*d..DDDD | >>> Пойду направо
DDDKDD...*..DDDD | >>> Пойду направо
DDDKDD...d*.DDDD | >>> Пойду направо
DDDKDD...d.*DDDD | >>> Пойду направо
   Дверь. Открываю. Осталось ключей: 2.
DDDKDD...d..*DDD | >>> Пойду направо
   Дверь. Открываю. Осталось ключей: 1.
DDDKDD...d..d*DD | >>> Пойду направо
   Дверь. Открываю. Осталось ключей: 0.
DDDKDD...d..dd*D | >>> Пойду направо
   Ключей больше нет. Я здесь умру! :(

DDDKDDKKGDKKDDDD => Увы. Выхода нет.

Answer 4

Поиск в ширину на ориентированном графе (не дереве) отыскивает самый короткий по числу ходов путь из лабиринта.

Узел графа - пара (число ключей, позиция). Вместе с узлом очередь хранит путь по которому можно прийти в этот узел. Путь нужен только для печати всех шагов. Если нужен только факт спасения, то можно и без пути. Граф представлен функциями completed (выбрались из ловушки) и neighbours (перебирает всех соседей узла).

bfs возвращает путь к узлу задом наперёд. print_path переворачивает его и печатает:

import collections


def bfs(start, neighbours, completed):
    visited = set()
    q = collections.deque()
    q.append(((0, start), None))
    while q:
        path = q.popleft()
        node = path[0]
        if node in visited:
            continue
        visited.add(node)
        if completed(node):
            return path
        for n in neighbours(node):
            q.append((n, path))
    return None


def completed(node):
    pose = node[1]
    return pose.startswith('G') or pose.endswith('G')


def neighbours(node):
    keys, pose = node
    g = pose.index('G')
    if g > 0:
        next_pose = pose[:g - 1] + 'G ' + pose[g + 1:]
        if pose[g - 1] == ' ':
            yield keys, next_pose
        elif pose[g - 1] == 'K':
            yield keys + 1, next_pose
        elif pose[g - 1] == 'D':
            if keys > 0:
                yield keys - 1, next_pose
        else:
            assert False
    if g < len(pose) - 1:
        next_pose = pose[:g] + ' G' + pose[g + 2:]
        if pose[g + 1] == ' ':
            yield keys, next_pose
        elif pose[g + 1] == 'K':
            yield keys + 1, next_pose
        elif pose[g + 1] == 'D':
            if keys > 0:
                yield keys - 1, next_pose
        else:
            assert False


def print_path(path, start):
    if path is None:
        print(start)
        print('no solution')
        return

    def poses(path):
        while path is not None:
            (_, pose), path = path
            yield pose

    p = tuple(poses(path))
    print(*reversed(p), sep='\n')
    print(f'{len(p) - 1} steps')


def main():
    start = input()
    path = bfs(start, neighbours, completed)
    print_path(path, start)


main()

$ echo DKDDGKKDDKDD | python 1d-quest.py 
DKDDGKKDDKDD
DKDD GKDDKDD
DKDD  GDDKDD
DKDD G DDKDD
DKDDG  DDKDD
DKDG   DDKDD
DKG    DDKDD
DG     DDKDD
G      DDKDD
8 steps

$ echo DDKGDDKKKKKKD | python 1d-quest.py 
DDKGDDKKKKKKD
no solution

$ echo DDDDKKKDDKGDKKDDD | python 1d-quest.py 
DDDDKKKDDKGDKKDDD
DDDDKKKDDG DKKDDD
DDDDKKKDD GDKKDDD
DDDDKKKDD  GKKDDD
DDDDKKKDD   GKDDD
DDDDKKKDD    GDDD
DDDDKKKDD   G DDD
DDDDKKKDD  G  DDD
DDDDKKKDD G   DDD
DDDDKKKDDG    DDD
DDDDKKKDG     DDD
DDDDKKKG      DDD
DDDDKKG       DDD
DDDDKG        DDD
DDDDG         DDD
DDDD G        DDD
DDDD  G       DDD
DDDD   G      DDD
DDDD    G     DDD
DDDD     G    DDD
DDDD      G   DDD
DDDD       G  DDD
DDDD        G DDD
DDDD         GDDD
DDDD          GDD
DDDD           GD
DDDD            G
26 steps

БЛОГ НА HUSL

Задачка-квест (поиск выхода из комнаты)

Ответы (4 шт):