AI: A model-based vacuum

Give an agent a memory so that it knows when its job is done.

What to build

A model-based vacuum agent in a corridor that cleans every square and then stops.

Requirements

  • Each step: if the agent's square is dirty, Suck. Otherwise it records the square as clean; if every square is known to be clean, it does Stop and ends; otherwise it moves Left or Right toward the nearest square not yet known to be clean (on a tie, left).
  • Print the actions on one line separated by spaces, then cleaned C, moves M, score S, where S = 10 × C − M.

Input

One line: the corridor (D dirty, . clean) and the starting square (counted from 0).

Output

Two lines.

Constraints

The corridor has at most 30 squares.

Example

Input:

D..DD 2

Output:

Left Left Suck Right Right Right Suck Right Suck Stop
cleaned 3, moves 6, score 24

Why it works

The agent cannot see other squares, so only its memory of which ones it has checked lets it stop at the right moment.

Examples

Example 1 · Input
D..DD 2
Expected output
Left Left Suck Right Right Right Suck Right Suck Stop
cleaned 3, moves 6, score 24
Example 2 · Input
... 0
Expected output
Right Right Stop
cleaned 0, moves 2, score -2

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Keep a set of squares known to be clean; add the current square when it is perceived clean.

Hint 2

To choose a direction, find the nearest square not yet known to be clean; on a tie, go left.

Solution

Show one correct solution (try it yourself first)
world, start = input().split()
dirty = [c == "D" for c in world]
pos = int(start)
known, actions, cleaned, moves = set(), [], 0, 0
while True:
    if dirty[pos]:
        dirty[pos] = False
        cleaned += 1
        actions.append("Suck")
        continue
    known.add(pos)
    unknown = [i for i in range(len(world)) if i not in known]
    if not unknown:
        actions.append("Stop")
        break
    target = min(unknown, key=lambda i: (abs(i - pos), i))
    step = 1 if target > pos else -1
    pos += step
    moves += 1
    actions.append("Right" if step == 1 else "Left")
print(" ".join(actions))
print(f"cleaned {cleaned}, moves {moves}, score {10 * cleaned - moves}")

Lesson: Intelligent agents →