gistfile1.txt

SECTION "NPUZZLE"

GET "utils"
GET "utils.b"


MANIFEST
{   board   = 0
    childs  = 1
    nchild  = 2
    hash    = 3
    cost    = 4
    
    nodeupb
    
    found   = maxint-1
}

STATIC
{   s.SZ
    s.SZ2
    s.node.start
    s.node.end
    s.atree
    
    s.f
    s.fpH
    s.result
    
    s.dbgNode
    s.dbgIter
}

LET start() = VALOF
{   s.fpH := taxicab
    //s.fpH := ham
    //s.fpH := mixit
    
    do_file("npdata\input1.txt", "npdata\o1.txt")
    do_file("npdata\input2.txt", "npdata\o2.txt")
    do_file("npdata\input3.txt", "npdata\o3.txt")
    do_file("npdata\input4.txt", "npdata\o4.txt")
    
    RESULTIS 0
}

AND do_file(inf, outf) BE
{   init(inf)
    
    s.dbgIter := 0
    
    start_timer()
    ida.star(s.node.start, s.node.end)
    stop_timer()
    
    writef("*n %s took %n ms *n", inf, get_time_taken_ms())
    
    set_outfile(outf)
    writef("solution: %n", s.result)
    cls_outfile()
    
    delnode(s.node.start)
    delnode(s.node.end)
}

AND init(fname) BE
{   LET i = ?

    IF NOT set_infile(fname) RETURN
    
    s.SZ    := readn()
    s.SZ2   := s.SZ * s.SZ
    
    s.node.start   := alnode()
    s.node.end     := alnode()
    
    FOR i = 0 TO s.SZ2-1 DO    s.node.start!board!i   := readn()
    FOR i = 0 TO s.SZ2-1 DO    s.node.end!board!i     := readn()

    s.node.start!hash   := hash.djb2(s.node.start!board,s.SZ2)
    s.node.end!hash     := hash.djb2(s.node.end!board,  s.SZ2)
    
    cls_infile()
}

AND alnode() = VALOF
{   LET node = ?
    
    node        := getvec(nodeupb)
    node!board  := getvec(s.SZ2)
    node!childs := 0
    node!nchild := 0
    node!hash   := 0
    node!cost   := 0
    
    RESULTIS    node
}

AND delnode(node) BE
{   freevec(node!board)
    freevec(node!childs)
    freevec(node)
}

AND mktree(root) = VALOF
{   LET troot = alnode()
    
    cpyb(troot, root)
    troot!hash := root!hash

    RESULTIS troot
}

AND deltree(root) BE
{   IF root!nchild > 0 DO    
    {   LET i = 0
        FOR i = 0 TO root!nchild-1 DO deltree(root!childs!i)
    }
    delnode(root)
}

AND chkdup(r, h) = VALOF
{/*   LET i = ?
    IF r!hash = h RESULTIS TRUE
    
    FOR i = 0 TO r!nchild-1 DO
    {   IF r!childs!i!nchild > 0 RESULTIS chkdup(r!childs!i, h)
    }
    */
    RESULTIS FALSE
}

AND expand(node) BE
{   LET zx, zy, idx = ?, ?, ?
    LET i, c, n     = 0, 0, ?
    
    LET zdx = idxOf(node!board, 0)
    LET t   = VEC 4
    
    zx := b.row(zdx)
    zy := b.col(zdx)
    
    IF valid_move(zx-1, zy) DO
    {   idx := ((zx-1) * s.SZ) + zy;
        n   := alnode()

        cpyb(n, node)
        swap(@n!board!idx, @n!board!zdx)
        n!hash := hash.djb2(n!board, s.SZ2)
 
        TEST NOT chkdup(s.atree, n!hash)
        THEN    { t!c := n; c := c + 1 }
        ELSE    delnode(n)

    }
    
    IF valid_move(zx+1, zy) DO
    {   idx := ((zx+1) * s.SZ) + zy;
        n   := alnode()

        cpyb(n, node)
        swap(@n!board!idx, @n!board!zdx)
        n!hash := hash.djb2(n!board, s.SZ2)

        TEST NOT chkdup(s.atree, n!hash)
        THEN    { t!c := n; c := c + 1 }
        ELSE    delnode(n)
    }
    
    IF valid_move(zx, zy-1) DO
    {   idx := (zx * s.SZ) + (zy-1);
        n   := alnode()

        cpyb(n, node)
        swap(@n!board!idx, @n!board!zdx)
        n!hash := hash.djb2(n!board, s.SZ2)

        TEST NOT chkdup(s.atree, n!hash)
        THEN    { t!c := n; c := c + 1 }
        ELSE    delnode(n)

    }
    
    IF valid_move(zx, zy+1) DO
    {   idx := (zx * s.SZ) + (zy+1);
        n   := alnode()

        cpyb(n, node)
        swap(@n!board!idx, @n!board!zdx)
        n!hash := hash.djb2(n!board, s.SZ2)

        TEST NOT chkdup(s.atree, n!hash)
        THEN    { t!c := n; c := c + 1 }
        ELSE    delnode(n)

    }
    
    s.dbgNode := s.dbgNode + c
    
    node!nchild := c
    node!childs := getvec(c)
    FOR i = 0 TO c-1 DO node!childs!i := t!i
}

AND cpyb(to, from) BE
{   LET i = ?
    FOR i = 0 TO s.SZ2-1 DO to!board!i := from!board!i
}

AND cmpnode(a, b) = VALOF
{   LET i = ?
    FOR i = 0 TO s.SZ2-1 IF a!board!i ~= b!board!i RESULTIS FALSE
    
    RESULTIS TRUE
}

AND ida.star(root, goal) = VALOF
{   
    LET is_goal(node) = node!hash = s.node.end!hash -> TRUE, FALSE
    //LET is_goal(node) = cmpnode(node, s.node.end)
    
    LET dfs.contour(n, g, b) = VALOF
    {   LET min, i, t = ?, ?, ?
        s.f := g + s.fpH(n, s.node.end)
       
        IF s.f > b      RESULTIS s.f
        IF is_goal(n)   DO {s.result := n!cost; RESULTIS found}
            
        min := maxint
        expand(n)
        FOR i = 0 TO n!nchild-1 DO
        {   n!childs!i!cost := n!cost + 1
            t := dfs.contour(n!childs!i, g + 1, b)

            IF t = found RESULTIS found    
            IF t < min DO min := t
        }
        RESULTIS min
    }
    
    LET bound   = s.fpH(root, goal)
    LET t       = ?
    
    {   s.atree     := mktree(s.node.start)  
        s.dbgNode   := 1
        t           := dfs.contour(s.atree, 0, bound)

        deltree(s.atree)

        IF t = found    RESULTIS found
        IF t = maxint   RESULTIS ~found
        bound := t
        
        s.dbgIter := s.dbgIter + 1
        writef("*nIteration [%n] Bound [%n] Nodes [%n]...", s.dbgIter, bound, s.dbgNode)
        
    }   REPEAT
    
    RESULTIS 0
}

AND b.row(pos) = pos / s.SZ
AND b.col(pos) = pos MOD s.SZ

AND idxOf(b, c) = VALOF
{   LET i = ?
    FOR i = 0 TO s.SZ2-1 IF b!i = c RESULTIS i
}

AND swap(to, from) BE
{   LET t = !to
    !to     := !from
    !from   := t
}

AND valid_move(x, y) = x >= 0 & x < s.SZ & y >= 0 & y < s.SZ -> TRUE, FALSE 

AND taxicab(n, e) = VALOF
{   LET m, i = 0, ?
    
    FOR i = 1 TO s.SZ2-1 DO
    {   LET nx, ny, ex, ey = ?, ?, ?, ?
        
        nx := b.row(idxOf(n!board, i))
        ny := b.col(idxOf(n!board, i))
        
        ex := b.row(idxOf(e!board, i))
        ey := b.col(idxOf(e!board, i))
        
        m := m + (ABS(ex - nx) + ABS(ey - ny))
    }
    RESULTIS m 
}

AND ham(n, e) = VALOF
{   LET h, i = 1, ?
    FOR i = 0 TO s.SZ2-1 IF n!board!i ~= e!board!i DO h := h + 1
    RESULTIS h
}

AND mixit(n, e) = taxicab(n, e) + ham(n, e)

AND hash.djb2(b, l) = VALOF
{   LET h = 5381
    LET i = ?
    FOR i = 0 TO l-1 DO h := ((h << 5) + h) + b!i
    RESULTIS h
}