# -- Code Cell --
from collections import deque
import csv

LEFT, ISLAND, RIGHT = 0, 1, 2

# -- Code Cell --

def valid_bank(researchers_mask, agents_mask, n):
    for i in range(n):
        ri = (researchers_mask >> i) & 1
        ai = (agents_mask >> i) & 1
        if ri and not ai:
            if agents_mask & ~(1 << i):
                return False
    return True

# -- Code Cell --

def valid_state(posR, posA, boat_pos, n):
    for loc in (LEFT, ISLAND, RIGHT):
        rmask = 0
        amask = 0
        for i in range(n):
            if posR[i] == loc:
                rmask |= 1 << i
            if posA[i] == loc:
                amask |= 1 << i
        if not valid_bank(rmask, amask, n):
            return False
    return True

# -- Code Cell --
def encode(posR, posA, boat_pos):
    return (tuple(posR), tuple(posA), boat_pos)

def possible_passengers(posR, posA, boat_pos, n):
    people = []
    for i in range(n):
        if posR[i] == boat_pos:
            people.append(("R", i))
        if posA[i] == boat_pos:
            people.append(("A", i))
    res = []
    for p in people:
        res.append([p])
    for i in range(len(people)):
        for j in range(i + 1, len(people)):
            res.append([people[i], people[j]])
    return res

# -- Code Cell --
def neighbors(posR, posA, boat_pos, n):
    passenger_sets = possible_passengers(posR, posA, boat_pos, n)
    if boat_pos in (LEFT, RIGHT):
        dests = [ISLAND]
    else:
        dests = [LEFT, RIGHT]
    for dest in dests:
        for passengers in passenger_sets:
            newR = list(posR)
            newA = list(posA)
            for typ, idx in passengers:
                if typ == "R":
                    newR[idx] = dest
                else:
                    newA[idx] = dest
            if valid_state(newR, newA, dest, n):
                yield newR, newA, dest

def min_moves(n):
    startR = [LEFT] * n
    startA = [LEFT] * n
    q = deque([(startR, startA, LEFT, 0)])
    dist = {encode(startR, startA, LEFT)}
    goal = ([RIGHT] * n, [RIGHT] * n)
    while q:
        posR, posA, boat, d = q.popleft()
        if (posR, posA) == goal:
            return d
        for nR, nA, nB in neighbors(posR, posA, boat, n):
            key = encode(nR, nA, nB)
            if key not in dist:
                dist.add(key)
                q.append((nR, nA, nB, d + 1))


# -- Code Cell --
def build_output_csv(path="output.csv"):
    rows = []
    rows.append({"subtaskID": 1, "datapointID": 3, "answer": min_moves(3)})
    for n in range(4, 9):
        rows.append({"subtaskID": 2, "datapointID": n, "answer": min_moves(n)})
    with open(path, "w", newline="") as f:
        w = csv.DictWriter(f, fieldnames=["subtaskID", "datapointID", "answer"])
        w.writeheader()
        w.writerows(rows)
    rows

build_output_csv()