Buggy python submission (verdict: Time Limit Exceeded):
from queue import Queue
from collections import namedtuple


def get_offset(x, y):
    return 16 * y + 4 * x


def swap(board, orig_x, orig_y, dest_x, dest_y):
    orig_offset = get_offset(orig_x, orig_y)
    dest_offset = get_offset(dest_x, dest_y)
    try:
        dest_val = board & (0b1111 << dest_offset)
    except:
        print(orig_x, orig_y, dest_x, dest_y)
        raise
    offset_diff = dest_offset - orig_offset
    swap_val = dest_val >> offset_diff if offset_diff > 0 else dest_val << abs(offset_diff)
    return board - dest_val + swap_val


def put_next_puzzle(puzzle):
    board, x0, y0, count = puzzle.board, puzzle.x0, puzzle.y0, puzzle.count
    for move_horizontal in [0, 1]:
        for direction in [-1, 1]:
            if move_horizontal:
                new_x0, new_y0 = x0 + direction, y0
                if not 0 <= new_x0 < 4:
                    continue
            else:
                new_x0, new_y0 = x0, y0 + direction
                if not 0 <= new_y0 < 4:
                    continue
            new_board = swap(board, x0, y0, new_x0, new_y0)
            if new_board in cache:
                continue
            if new_board == CORRECT:
                return count + 1
            cache.append(new_board)
            puzzles.put(Puzzle(
                    board=new_board,
                    count=count + 1,
                    x0=new_x0,
                    y0=new_y0
            ))
    return -1


CORRECT = 0x0fedcba987654321
puzzles = Queue()
Puzzle = namedtuple('Puzzle', 'board count x0 y0')
cache = []
board = 0
x0 = y0 = -1

for j in range(4):
    for i, v in enumerate(map(int, input().strip().split())):
        board += v << get_offset(i, j)
        if v == 0:
            x0, y0 = i, j

# print('%x' % board)

puzzles.put(Puzzle(board=board, count=0, x0=x0, y0=y0))
cache.append(board)
result = None

while True:
    if puzzles.empty():
        break

    result = put_next_puzzle(puzzles.get())
    if result > -1:
        break

print(result)

Fixed submission:
from heapq import heappop, heappush

manhattan = [[abs((i % 4) - (j % 4)) + abs((i // 4) - (j // 4)) for j in range(16)] for i in range(16)]
movables = [{1, 4}, {0, 2, 5}, {1, 3, 6}, {2, 7}, {0, 5, 8}, {1, 4, 6, 9}, {2, 5, 7, 10}, {3, 6, 11},
            {4, 9, 12}, {5, 8, 10, 13}, {6, 9, 11, 14}, {7, 10, 15}, {8, 13}, {9, 12, 14}, {10, 13, 15}, {11, 14}]
swap_mul = [[(1 << mf) - (1 << mt) for mt in range(0, 64, 4)] for mf in range(0, 64, 4)]
destination = 0xfedcba9876543210

i = 0
board_init = 0
blank_init = 0
for _ in range(4):
    for n in map(int, input().split()):
        if n:
            n -= 1
        else:
            n = 15
            blank_init = i
        board_init += n * 16 ** i
        i += 1

estimation_init = sum(manhattan[i][((board_init >> (4 * i)) & 15)] for i in range(16) if i != blank_init)

queue = [(estimation_init, board_init, blank_init)]
visited = set()

while True:
    estimation, board, blank = heappop(queue)
    if board in visited:
        continue
    elif board == destination:
        print(estimation)
        break
    visited.add(board)
    for new_blank in movables[blank]:
        num = (board >> (4 * new_blank)) & 15
        new_board = board + swap_mul[new_blank][blank] * (15 - num)
        if new_board in visited:
            continue
        new_estimation = estimation + 1 - manhattan[new_blank][num] + manhattan[blank][num]
        if new_estimation > 45:
            continue
        heappush(queue, (new_estimation, new_board, new_blank))

Buggy python submission (verdict: Time Limit Exceeded):
from queue import Queue
from collections import namedtuple


def get_offset(x, y):
    return 16 * y + 4 * x


def get_candidate(pid):
    def check(pid, move):
        if abs(move) == 1:
            return pid // 4 == (pid + move) // 4
        else:
            return 0 <= pid + move < 16

    return tuple(pid + move for move in MOVE_CANDIDATE if check(pid, move))


def get_swap_values(orig):
    return {dest: (1 << OFFSET_MASTER[orig]) - (1 << OFFSET_MASTER[dest]) for dest in SWAP_CANDIDATE[orig]}


MOVE_CANDIDATE = (-4, -1, 1, 4)
SWAP_CANDIDATE = tuple(get_candidate(pid) for pid in range(16))
OFFSET_MASTER = tuple(get_offset(x, y) for y in range(4) for x in range(4))
SWAP_VALUE_MASTER = tuple(get_swap_values(pid) for pid in range(16))


def swap(board, orig, dest):
    dest_val = (board >> OFFSET_MASTER[dest]) & 0b1111
    return board + dest_val * SWAP_VALUE_MASTER[orig][dest]


def put_next_puzzle(is_reverse):
    global puzzles, cache
    puzzle = puzzles[is_reverse].get()
    board, id0, count, prev = puzzle.board, puzzle.id0, puzzle.count, puzzle.prev
    for new_id0 in SWAP_CANDIDATE[id0]:
        if new_id0 == prev:
            continue

        new_board = swap(board, id0, new_id0)
        if new_board in cache[is_reverse]:
            continue
        if new_board in cache[not is_reverse]:
            return cache[not is_reverse][new_board].count + count + 1
        new_puzzle = Puzzle(
                board=new_board,
                count=count + 1,
                id0=new_id0,
                prev=id0,
                trace=puzzle.trace * 16 + new_id0
        )
        cache[is_reverse][new_board] = new_puzzle
        puzzles[is_reverse].put(new_puzzle)
    return -1


CORRECT = 0x0fedcba987654321
Puzzle = namedtuple('Puzzle', 'board count id0 prev trace')
puzzles = (Queue(), Queue())
cache = ({}, {})
board = 0
id0 = -1

for j in range(4):
    for i, v in enumerate(map(int, input().strip().split())):
        board += v << get_offset(i, j)
        if v == 0:
            id0 = 4 * j + i

start = Puzzle(board=board, count=0, id0=id0, prev=-1, trace=0)
goal = Puzzle(board=CORRECT, count=0, id0=15, prev=-1, trace=0)
puzzles[0].put(start)
puzzles[1].put(goal)
cache[0][board] = start
cache[1][CORRECT] = goal
result = None
is_reverse = False

while True:
    result = put_next_puzzle(is_reverse)
    if result > -1:
        break
    is_reverse = not is_reverse

print(result)

Fixed submission:
from heapq import heappop, heappush

manhattan = [[abs((i % 4) - (j % 4)) + abs((i // 4) - (j // 4)) for j in range(16)] for i in range(16)]
movables = [{1, 4}, {0, 2, 5}, {1, 3, 6}, {2, 7}, {0, 5, 8}, {1, 4, 6, 9}, {2, 5, 7, 10}, {3, 6, 11},
            {4, 9, 12}, {5, 8, 10, 13}, {6, 9, 11, 14}, {7, 10, 15}, {8, 13}, {9, 12, 14}, {10, 13, 15}, {11, 14}]
swap_mul = [[(1 << mf) - (1 << mt) for mt in range(0, 64, 4)] for mf in range(0, 64, 4)]
destination = 0xfedcba9876543210

i = 0
board_init = 0
blank_init = 0
for _ in range(4):
    for n in map(int, input().split()):
        if n:
            n -= 1
        else:
            n = 15
            blank_init = i
        board_init += n * 16 ** i
        i += 1

estimation_init = sum(manhattan[i][((board_init >> (4 * i)) & 15)] for i in range(16) if i != blank_init)

queue = [(estimation_init, board_init, blank_init)]
visited = set()

while True:
    estimation, board, blank = heappop(queue)
    if board in visited:
        continue
    elif board == destination:
        print(estimation)
        break
    visited.add(board)
    for new_blank in movables[blank]:
        num = (board >> (4 * new_blank)) & 15
        new_board = board + swap_mul[new_blank][blank] * (15 - num)
        if new_board in visited:
            continue
        new_estimation = estimation + 1 - manhattan[new_blank][num] + manhattan[blank][num]
        if new_estimation > 45:
            continue
        heappush(queue, (new_estimation, new_board, new_blank))

Buggy python submission (verdict: Time Limit Exceeded):
import heapq

CORRECT = 0x0fedcba987654321
heap_puzzle = []
cache = {}


class Puzzle:
    DEST_BOARD_DICT = {CORRECT >> (4 * i) & 0b1111: i for i in range(16)}
    HEURISTICS = tuple(
            tuple(abs(dest // 4 - orig // 4) + abs(dest % 4 - orig % 4) for dest in range(16)) for orig in range(16))

    def __init__(self, board, pid0, count, prev, heuristic=None):
        self.board = board
        self.pid0 = pid0
        self.count = count
        self.prev = prev
        self.invalid = False
        self.heuristic = heuristic

    def swap(self, dest):
        global OFFSET_MASTER, SWAP_VALUE_MASTER
        dest_val = (self.board >> OFFSET_MASTER[dest]) & 0b1111
        return self.board + dest_val * SWAP_VALUE_MASTER[self.pid0][dest]

    def get_sum_heuristic(self):
        if self.heuristic is not None:
            return self.heuristic

        orig_board_dict = {i: self.board >> (4 * i) & 0b1111 for i in range(16)}
        self.heuristic = sum(self.HEURISTICS[pid][self.DEST_BOARD_DICT[val]] for pid, val in orig_board_dict.items())

        return self.heuristic

    def __lt__(self, other):
        return False


def get_offset(x, y):
    return 16 * y + 4 * x


def get_candidate(pid):
    global MOVE_CANDIDATE

    def check(pid, move):
        if abs(move) == 1:
            return pid // 4 == (pid + move) // 4
        else:
            return 0 <= pid + move < 16

    return tuple(pid + move for move in MOVE_CANDIDATE if check(pid, move))


def get_swap_values(orig):
    global OFFSET_MASTER, SWAP_CANDIDATE
    return {dest: (1 << OFFSET_MASTER[orig]) - (1 << OFFSET_MASTER[dest]) for dest in SWAP_CANDIDATE[orig]}


MOVE_CANDIDATE = (-4, -1, 1, 4)
SWAP_CANDIDATE = tuple(get_candidate(pid) for pid in range(16))
OFFSET_MASTER = tuple(get_offset(x, y) for y in range(4) for x in range(4))
SWAP_VALUE_MASTER = tuple(get_swap_values(pid) for pid in range(16))


def put_next_puzzle():
    global heap_puzzle, cache
    (cost, puzzle) = heapq.heappop(heap_puzzle)
    if puzzle.invalid:
        return -1
    board, pid0, count, prev = puzzle.board, puzzle.pid0, puzzle.count, puzzle.prev
    for new_pid0 in SWAP_CANDIDATE[pid0]:
        if new_pid0 == prev:
            continue

        new_board = puzzle.swap(new_pid0)

        if new_board == CORRECT:
            return count + 1

        heuristic = None
        if new_board in cache:
            closed_puzzle = cache[new_board]
            if closed_puzzle.count <= count:
                continue
            else:
                closed_puzzle.invalid = True
                heuristic = closed_puzzle.heuristic

        new_puzzle = Puzzle(
                board=new_board,
                count=count + 1,
                pid0=new_pid0,
                prev=pid0,
                heuristic=heuristic
        )
        new_cost = count + 1 + new_puzzle.get_sum_heuristic()
        heapq.heappush(heap_puzzle, (new_cost, new_puzzle))
        cache[new_board] = new_puzzle
    return -1


first_board = 0
first_pid0 = -1

for j in range(4):
    for i, v in enumerate(map(int, input().strip().split())):
        first_board += v << get_offset(i, j)
        if v == 0:
            first_pid0 = 4 * j + i

s_puzzle = Puzzle(board=first_board, count=0, pid0=first_pid0, prev=-1)
heapq.heappush(heap_puzzle, (s_puzzle.get_sum_heuristic(), s_puzzle))
cache[first_board] = s_puzzle
result = None

while True:
    result = put_next_puzzle()
    if result > -1:
        break

print(result)

Fixed submission:
from heapq import heappop, heappush

manhattan = [[abs((i % 4) - (j % 4)) + abs((i // 4) - (j // 4)) for j in range(16)] for i in range(16)]
movables = [{1, 4}, {0, 2, 5}, {1, 3, 6}, {2, 7}, {0, 5, 8}, {1, 4, 6, 9}, {2, 5, 7, 10}, {3, 6, 11},
            {4, 9, 12}, {5, 8, 10, 13}, {6, 9, 11, 14}, {7, 10, 15}, {8, 13}, {9, 12, 14}, {10, 13, 15}, {11, 14}]
swap_mul = [[(1 << mf) - (1 << mt) for mt in range(0, 64, 4)] for mf in range(0, 64, 4)]
destination = 0xfedcba9876543210

i = 0
board_init = 0
blank_init = 0
for _ in range(4):
    for n in map(int, input().split()):
        if n:
            n -= 1
        else:
            n = 15
            blank_init = i
        board_init += n * 16 ** i
        i += 1

estimation_init = sum(manhattan[i][((board_init >> (4 * i)) & 15)] for i in range(16) if i != blank_init)

queue = [(estimation_init, board_init, blank_init)]
visited = set()

while True:
    estimation, board, blank = heappop(queue)
    if board in visited:
        continue
    elif board == destination:
        print(estimation)
        break
    visited.add(board)
    for new_blank in movables[blank]:
        num = (board >> (4 * new_blank)) & 15
        new_board = board + swap_mul[new_blank][blank] * (15 - num)
        if new_board in visited:
            continue
        new_estimation = estimation + 1 - manhattan[new_blank][num] + manhattan[blank][num]
        if new_estimation > 45:
            continue
        heappush(queue, (new_estimation, new_board, new_blank))

Buggy python submission (verdict: Time Limit Exceeded):
import heapq

CORRECT = 0x0fedcba987654321
heap_puzzle = []
cache = {}


class Puzzle:
    DEST_BOARD_DICT = {CORRECT >> (4 * i) & 0b1111: i for i in range(16)}
    HEURISTICS = tuple(
            tuple(abs(dest // 4 - orig // 4) + abs(dest % 4 - orig % 4) for dest in range(16)) for orig in range(16))

    def __init__(self, board, pid0, count, prev, heuristic=None):
        self.board = board
        self.pid0 = pid0
        self.count = count
        self.prev = prev
        self.invalid = False
        self.heuristic = heuristic

    def swap(self, dest):
        global OFFSET_MASTER, SWAP_VALUE_MASTER
        dest_val = (self.board >> OFFSET_MASTER[dest]) & 0b1111
        return self.board + dest_val * SWAP_VALUE_MASTER[self.pid0][dest]

    def get_sum_heuristic(self):
        if self.heuristic is not None:
            return self.heuristic

        orig_board_dict = {i: self.board >> (4 * i) & 0b1111 for i in range(16)}
        self.heuristic = sum(self.HEURISTICS[pid][self.DEST_BOARD_DICT[val]] for pid, val in orig_board_dict.items())

        return self.heuristic

    def __lt__(self, other):
        return True


def get_offset(x, y):
    return 16 * y + 4 * x


def get_candidate(pid):
    global MOVE_CANDIDATE

    def check(pid, move):
        if abs(move) == 1:
            return pid // 4 == (pid + move) // 4
        else:
            return 0 <= pid + move < 16

    return tuple(pid + move for move in MOVE_CANDIDATE if check(pid, move))


def get_swap_values(orig):
    global OFFSET_MASTER, SWAP_CANDIDATE
    return {dest: (1 << OFFSET_MASTER[orig]) - (1 << OFFSET_MASTER[dest]) for dest in SWAP_CANDIDATE[orig]}


MOVE_CANDIDATE = (-4, -1, 1, 4)
SWAP_CANDIDATE = tuple(get_candidate(pid) for pid in range(16))
OFFSET_MASTER = tuple(get_offset(x, y) for y in range(4) for x in range(4))
SWAP_VALUE_MASTER = tuple(get_swap_values(pid) for pid in range(16))


def put_next_puzzle():
    global heap_puzzle, cache, SWAP_CANDIDATE, CORRECT
    (cost, puzzle) = heapq.heappop(heap_puzzle)
    if puzzle.invalid:
        return -1
    board, pid0, count, prev = puzzle.board, puzzle.pid0, puzzle.count, puzzle.prev
    for new_pid0 in SWAP_CANDIDATE[pid0]:
        if new_pid0 == prev:
            continue

        new_board = puzzle.swap(new_pid0)

        if new_board == CORRECT:
            return count + 1

        heuristic = None
        if new_board in cache:
            closed_puzzle = cache[new_board]
            if closed_puzzle.count <= count:
                continue
            else:
                closed_puzzle.invalid = True
                heuristic = closed_puzzle.heuristic

        new_puzzle = Puzzle(
                board=new_board,
                count=count + 1,
                pid0=new_pid0,
                prev=pid0,
                heuristic=heuristic
        )
        new_cost = count + 1 + new_puzzle.get_sum_heuristic()
        heapq.heappush(heap_puzzle, (new_cost, new_puzzle))
        cache[new_board] = new_puzzle
    return -1


first_board = 0
first_pid0 = -1

for j in range(4):
    for i, v in enumerate(map(int, input().strip().split())):
        first_board += v << get_offset(i, j)
        if v == 0:
            first_pid0 = 4 * j + i

s_puzzle = Puzzle(board=first_board, count=0, pid0=first_pid0, prev=-1)
heapq.heappush(heap_puzzle, (s_puzzle.get_sum_heuristic(), s_puzzle))
cache[first_board] = s_puzzle
result = None

while True:
    result = put_next_puzzle()
    if result > -1:
        break

print(result)

Fixed submission:
from heapq import heappop, heappush

manhattan = [[abs((i % 4) - (j % 4)) + abs((i // 4) - (j // 4)) for j in range(16)] for i in range(16)]
movables = [{1, 4}, {0, 2, 5}, {1, 3, 6}, {2, 7}, {0, 5, 8}, {1, 4, 6, 9}, {2, 5, 7, 10}, {3, 6, 11},
            {4, 9, 12}, {5, 8, 10, 13}, {6, 9, 11, 14}, {7, 10, 15}, {8, 13}, {9, 12, 14}, {10, 13, 15}, {11, 14}]
swap_mul = [[(1 << mf) - (1 << mt) for mt in range(0, 64, 4)] for mf in range(0, 64, 4)]
destination = 0xfedcba9876543210

i = 0
board_init = 0
blank_init = 0
for _ in range(4):
    for n in map(int, input().split()):
        if n:
            n -= 1
        else:
            n = 15
            blank_init = i
        board_init += n * 16 ** i
        i += 1

estimation_init = sum(manhattan[i][((board_init >> (4 * i)) & 15)] for i in range(16) if i != blank_init)

queue = [(estimation_init, board_init, blank_init)]
visited = set()

while True:
    estimation, board, blank = heappop(queue)
    if board in visited:
        continue
    elif board == destination:
        print(estimation)
        break
    visited.add(board)
    for new_blank in movables[blank]:
        num = (board >> (4 * new_blank)) & 15
        new_board = board + swap_mul[new_blank][blank] * (15 - num)
        if new_board in visited:
            continue
        new_estimation = estimation + 1 - manhattan[new_blank][num] + manhattan[blank][num]
        if new_estimation > 45:
            continue
        heappush(queue, (new_estimation, new_board, new_blank))

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappop, heappush

manhattan = [[abs((i % 4) - (j % 4)) + abs((i // 4) - (j // 4)) for j in range(16)] for i in range(16)]
movables = [{1, 4}, {0, 2, 5}, {1, 3, 6}, {2, 7}, {0, 5, 8}, {1, 4, 6, 9}, {2, 5, 7, 10}, {3, 6, 11},
            {4, 9, 12}, {5, 8, 10, 13}, {6, 9, 11, 14}, {7, 10, 15}, {8, 13}, {9, 12, 14}, {10, 13, 15}, {11, 14}]
destination = 0xfedcba9876543210

i = 0
board_init = 0
blank_init = 0
for _ in range(4):
    for n in map(int, input().split()):
        if n:
            n -= 1
        else:
            n = 15
            blank_init = i
        board_init += n * 16 ** i
        i += 1


def swap(board, move_from, move_to):
    mf, mt = 4 * move_from, 4 * move_to
    return board + ((1 << mf) - (1 << mt)) * (15 - ((board >> mf) & 15))


def estimate(board):
    return sum(manhattan[i][(board >> (4 * i)) & 15] for i in range(15))


queue = [(0, 0, board_init, blank_init)]
visited = set()

while True:
    _, cost, board, blank = heappop(queue)
    if board in visited:
        continue
    elif board == destination:
        print(cost)
        break
    visited.add(board)
    cost += 1
    for new_blank in movables[blank]:
        new_board = swap(board, new_blank, blank)
        if new_board in visited:
            continue
        new_estimation = cost + estimate(new_board)
        if new_estimation > 45:
            continue
        heappush(queue, (new_estimation, cost, new_board, new_blank))

Fixed submission:
from heapq import heappop, heappush

manhattan = [[abs((i % 4) - (j % 4)) + abs((i // 4) - (j // 4)) for j in range(16)] for i in range(16)]
movables = [{1, 4}, {0, 2, 5}, {1, 3, 6}, {2, 7}, {0, 5, 8}, {1, 4, 6, 9}, {2, 5, 7, 10}, {3, 6, 11},
            {4, 9, 12}, {5, 8, 10, 13}, {6, 9, 11, 14}, {7, 10, 15}, {8, 13}, {9, 12, 14}, {10, 13, 15}, {11, 14}]
swap_mul = [[(1 << mf) - (1 << mt) for mt in range(0, 64, 4)] for mf in range(0, 64, 4)]
destination = 0xfedcba9876543210

i = 0
board_init = 0
blank_init = 0
for _ in range(4):
    for n in map(int, input().split()):
        if n:
            n -= 1
        else:
            n = 15
            blank_init = i
        board_init += n * 16 ** i
        i += 1

estimation_init = sum(manhattan[i][((board_init >> (4 * i)) & 15)] for i in range(16) if i != blank_init)

queue = [(estimation_init, board_init, blank_init)]
visited = set()

while True:
    estimation, board, blank = heappop(queue)
    if board in visited:
        continue
    elif board == destination:
        print(estimation)
        break
    visited.add(board)
    for new_blank in movables[blank]:
        num = (board >> (4 * new_blank)) & 15
        new_board = board + swap_mul[new_blank][blank] * (15 - num)
        if new_board in visited:
            continue
        new_estimation = estimation + 1 - manhattan[new_blank][num] + manhattan[blank][num]
        if new_estimation > 45:
            continue
        heappush(queue, (new_estimation, new_board, new_blank))

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappop, heappush

manhattan = [[abs((i % 4) - (j % 4)) + abs((i // 4) - (j // 4)) for j in range(16)] for i in range(16)]
movables = [{1, 4}, {0, 2, 5}, {1, 3, 6}, {2, 7}, {0, 5, 8}, {1, 4, 6, 9}, {2, 5, 7, 10}, {3, 6, 11},
            {4, 9, 12}, {5, 8, 10, 13}, {6, 9, 11, 14}, {7, 10, 15}, {8, 13}, {9, 12, 14}, {10, 13, 15}, {11, 14}]
swap_cache = [[(1 << mf) - (1 << mt) for mt in range(0, 64, 4)] for mf in range(0, 64, 4)]
destination = 0xfedcba9876543210

i = 0
board_init = 0
blank_init = 0
for _ in range(4):
    for n in map(int, input().split()):
        if n:
            n -= 1
        else:
            n = 15
            blank_init = i
        board_init += n * 16 ** i
        i += 1


def swap(board, move_from, move_to):
    return board + swap_cache[move_from][move_to] * (15 - ((board >> (4 * move_from)) & 15))


queue = [(0, 0, board_init, blank_init)]
visited = set()

while True:
    _, cost, board, blank = heappop(queue)
    if board in visited:
        continue
    elif board == destination:
        print(cost)
        break
    visited.add(board)
    cost += 1
    for new_blank in movables[blank]:
        new_board = swap(board, new_blank, blank)
        if new_board in visited:
            continue
        new_estimation = cost + sum(manhattan[i][(new_board >> (4 * i)) & 15] for i in range(15))
        if new_estimation > 45:
            continue
        heappush(queue, (new_estimation, cost, new_board, new_blank))

Fixed submission:
from heapq import heappop, heappush

manhattan = [[abs((i % 4) - (j % 4)) + abs((i // 4) - (j // 4)) for j in range(16)] for i in range(16)]
movables = [{1, 4}, {0, 2, 5}, {1, 3, 6}, {2, 7}, {0, 5, 8}, {1, 4, 6, 9}, {2, 5, 7, 10}, {3, 6, 11},
            {4, 9, 12}, {5, 8, 10, 13}, {6, 9, 11, 14}, {7, 10, 15}, {8, 13}, {9, 12, 14}, {10, 13, 15}, {11, 14}]
swap_mul = [[(1 << mf) - (1 << mt) for mt in range(0, 64, 4)] for mf in range(0, 64, 4)]
destination = 0xfedcba9876543210

i = 0
board_init = 0
blank_init = 0
for _ in range(4):
    for n in map(int, input().split()):
        if n:
            n -= 1
        else:
            n = 15
            blank_init = i
        board_init += n * 16 ** i
        i += 1

estimation_init = sum(manhattan[i][((board_init >> (4 * i)) & 15)] for i in range(16) if i != blank_init)

queue = [(estimation_init, board_init, blank_init)]
visited = set()

while True:
    estimation, board, blank = heappop(queue)
    if board in visited:
        continue
    elif board == destination:
        print(estimation)
        break
    visited.add(board)
    for new_blank in movables[blank]:
        num = (board >> (4 * new_blank)) & 15
        new_board = board + swap_mul[new_blank][blank] * (15 - num)
        if new_board in visited:
            continue
        new_estimation = estimation + 1 - manhattan[new_blank][num] + manhattan[blank][num]
        if new_estimation > 45:
            continue
        heappush(queue, (new_estimation, new_board, new_blank))