{-# LANGUAGE FlexibleContexts #-}

module Main where

-- import Debug.Trace
import Data.List
import qualified Data.Set as Set
import qualified Data.Sequence as Seq
import qualified Data.ByteString.Char8 as B
import Data.Int
import Data.Word
import Data.Char
import Data.Bits
import Data.Array
-- import Data.Array.Unboxed
-- import Data.Array.IO
import Data.Maybe
-- import qualified Data.Map as M
import qualified Data.IntMap as M
-- import Control.Monad.ST
-- import Data.STRef
import Data.Ord
import Data.Functor
import Control.Applicative
import Control.Monad
import Text.Printf

size = 4
maxAdr = size*size -1

solver :: [[Int]] -> Int
solver lst = bfs start goalID where
    bfs start goalID = iter ((Seq.singleton (start, generateID start, 0)), M.empty) where
        iter (que, visited) = case Seq.viewr que of
            Seq.EmptyR -> error "No path found."
            que Seq.:> path@(b, bId, d)
                | bId == goalID -> d
                | otherwise -> iter (insertPaths que visited (nextPaths path)) where
                    insertPaths q v [] = (q, v)
                    insertPaths q v (p@(_,x,_):ps) = insertPaths (p Seq.<| q) (M.insert x () visited) ps
                    nextPaths path@(b, bId, d) = [(x, xId, d+1)| (x, xId) <- nextBoards, notVisited xId] where        
                        notVisited x = M.notMember x visited
                        boards = [swapAt (b !! q) b | q <- dest!p]
                        nextBoards = [(x, generateID x)| x <- boards]
                        p = fromJust $ elemIndex 0 b
    goalID = generateID [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0]
    start  = concat lst
    dest   = listArray (0, maxAdr) [[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]] 
    generateID board = foldl' (\b a-> shiftL b 4 .|. a) 0 board　-- << T.B.D

swapAt :: Int -> [Int] -> [Int]
swapAt v = foldr (\a b -> case a of
    _   | a == 0 -> v:b
        | a == v -> 0:b
        | otherwise -> a:b
     ) [] 

readIntLn:: IO Int
readIntLn = (fst . fromJust . B.readInt) <$> B.getLine

readIntList:: IO [Int]
readIntList = map (fst . fromJust . B.readInt) . B.words <$> B.getLine

main :: IO() 
main = do
    l <- replicateM size readIntList
    print $ solver l

