/****************************************************
 * Title: Solving Puzzle in JavaScript
 * Author: Osami Yamamoto (osami@meijo-u.ac.jp)
 * Date: Fri Feb 14 15:12:10 JST 2014
 ****************************************************/

/*
 * Suppose that there is a board on which five balls are
 * initially located randomly, where three of them are
 * labeled 'R' and other two balls are labeled 'B'.
 * For instance, the configuration is like
 *  +---+
 *  |BRB|
 *  |RR |
 *  +---+
 * You can move a ball to the empty place in one step, and, 
 * only a ball which faces to the empty place or a ball which
 * can reach the empty place by flying across one ball which
 * is labeled differently can move to the empty place.  Find
 * a sequence of moves from the initial configuration to the
 * following goal configuration with the minimal number of steps:
 *  +---+
 *  |B R|
 *  |BRR|
 *  +---+
 *
 */


var queue = []
var t_table = []
var n_mk_config = 0
var outstr = ""
var agenda = []

function print_it(str){
    outstr = outstr + "\n" + str
}


/*========================*
 * mk_config(c, parent)
 *========================*/
function mk_config(c, parent){
    m = {}
    m.a = c.split('')
    m.parent = parent
    n_mk_config += 1
    return m
} /* mk_config */

/*========================*
 * print_config(pt){
 *========================*/
function print_config(pt){
    var s = "+---+\n"
    for (var i = 0; i < 6; i++){
        s += ((i % 3 == 0)?'|':'') + pt.a[i]
        if ((i + 1) % 3 == 0) s += "|\n" 
    } /* for */
    print_it(s + "+---+")
} /* print_config */

/*========================*
 * eq_config(pt1, pt2)
 *========================*/
function eq_config(pt1, pt2){
    for(var i = 0; i < 6; i++)
        if (pt1.a[i] != pt2.a[i]) return false
    return true
} /* eq_config */

/*========================*
 * blank_pos(pt)
 *========================*/
function blank_pos(pt){
    for(var i = 0; i < 6; i++)
        if (pt.a[i] == ' ') return i
    return -1;
} /* blank_pos */

/*========================*
 * init_queue()
 *========================*/
function init_queue(){
    queue = []
    t_table = []
    agenda = []
    n_mk_config = 0
} /* init_queue */

/*========================*
 * enqueue(a)
 * dequeue()
 * push_TT(a)
 * int2str(i)
 *========================*/
function enqueue(a){queue.push(a)}
function dequeue(){return queue.shift()}
function push_TT(a){t_table.push(a)}
function int2str(i){ return ((i < 10)?"  ":" ") + i}

/*========================*
 * search_TT(a)
 *========================*/
function search_TT(a){
    for (var i in t_table)
        if (eq_config(a, t_table[i])) return 1
    return 0
} /* search_TT */

/*========================*
 * print_action(result)
 *========================*/
function print_action(result){
    var n = result.length
    for (var i = n - 1; i >= 1; i--){
        var p0 = result[i - 1].action_from 
        var p1 = result[i - 1].action_to
        var x0 = p0 % 3; var y0 = Math.floor(p0 / 3)
        var x1 = p1 % 3; var y1 = Math.floor(p1 / 3)
        var opt = "."
        if (Math.abs(p0 - p1) == 2) opt = " jumping over (" + 
            (x0 + x1) / 2 + ", " + y0 + ")."
        print_it(int2str(n - i) + ". Move the ball at (" + x0 + ", " + y0 +
                    ") to (" + x1 + ", " + y1 + ")" +opt)
	add_agenda(result[i], result[i - 1], p0, p1)
    } /* for */
} /* print_action */

function add_agenda(from_conf, to_conf, from_pos, to_pos){
    var dist = 11
    if (Math.abs(from_pos - to_pos) == 2){
	add_agenda2(from_conf, to_conf, from_pos, to_pos, dist * 2)
    } else{
	add_agenda1(from_conf, to_conf, from_pos, to_pos, dist)
    }
}

function add_agenda1(from_conf, to_conf, from_pos, to_pos, dist){
    var x0 = from_pos % 3; var y0 = Math.floor(from_pos / 3)
    var x1 = to_pos % 3; var y1 = Math.floor(to_pos / 3)
    var c = from_conf.a[from_pos]
    var vv = 10
    var pat = []
    for (var i = 0; i < 6; i++){
	if (i == from_pos) pat[i] = ' '
	else pat[i] = from_conf.a[i]
    }
    pat = pat.join("")
    if (x0 == x1){
	var x = 55 + x0 * 110
	var y = 55 + y0 * 110
	var v = vv
	if (y1 < y0) v = -vv
	for (var ii = 0; ii <= dist; ii++){
	    agenda.push(mk_agenda_element(pat, c, x, y, 37))
	    y = y + v
	} /* for */
    } else {
	var x = 55 + x0 * 110
	var y = 55 + y0 * 110
	var v = vv
	if (x1 < x0) v = -vv
	for (var ii = 0; ii <= dist; ii++){
	    agenda.push(mk_agenda_element(pat, c, x, y, 37))
	    x = x + v
	} /* for */
    }
}

function add_agenda2(from_conf, to_conf, from_pos, to_pos, dist){
    var x0 = from_pos % 3; var y0 = Math.floor(from_pos / 3)
    var x1 = to_pos % 3; var y1 = Math.floor(to_pos / 3)
    var c = from_conf.a[from_pos]
    var vv = 10
    var pat = []
    for (var i = 0; i < 6; i++){
	if (i == from_pos) pat[i] = ' '
	else pat[i] = from_conf.a[i]
    }
    pat = pat.join("")
    for (var r = 37; r >= 20; r--)
	agenda.push(mk_agenda_element(pat, c, 55 + x0 * 110,
				      55 + y0 * 110, r))
    if (x0 == x1){
	var x = 55 + x0 * 110
	var y = 55 + y0 * 110
	var v = vv
	if (y1 < y0) v = -vv
	for (var ii = 0; ii <= dist; ii++){
	    agenda.push(mk_agenda_element(pat, c, x, y, 20))
	    y = y + v
	} /* for */
    } else {
	var x = 55 + x0 * 110
	var y = 55 + y0 * 110
	var v = vv
	if (x1 < x0) v = -vv
	for (var ii = 0; ii <= dist; ii++){
	    agenda.push(mk_agenda_element(pat, c, x, y, 20))
	    x = x + v
	} /* for */
    }
    for (var r = 20; r <= 37; r++)
	agenda.push(mk_agenda_element(pat, c, 55 + x1 * 110,
				      55 + y1 * 110, r))
}

/*========================*
 * print_solution(pt)
 *========================*/
function print_solution(pt){
    result = []
    print_it("Result::");
    while (pt != null){
        result.push(pt)
        pt = pt.parent
    } /* while */
    var n = result.length
    var one_line = function(ff){
        var s = ""
        for (var i = n - 1; i>= 0; i--) s += ff(i)
        print_it(s)
    } /* one_line */
    print_it('')
    one_line(function(i){return "  " + "+---+"})
    one_line(function(i){return "  |" +
                         result[i].a[0]+result[i].a[1]+result[i].a[2] +"|"})
    one_line(function(i){
        return ((i == n - 1)?"  |":"=>|") + 
            result[i].a[3] + result[i].a[4] + result[i].a[5] + "|"})
    one_line(function(i){return "  " + "+---+"})
    one_line(function(i){return "  " + int2str(n - i - 1) + "  "})
    print_it('')
    print_action(result)
    print_it('')
    print_it("Transfered in " + (n - 1) + " step(s).")
} /* print_solution */

/*========================*
 * do_loop(final)
 *========================*/
function do_loop(final){
    while (queue.length != 0){
        var m = dequeue()
        if (eq_config(m, final)){
            print_solution(m)
            break
        }  /* if */
        if (search_TT(m)) continue;
        push_TT(m)
        var p = blank_pos(m)
        var x = p % 3
        var y = Math.floor(p / 3)
        var mm = m.a.join('')
        var move_func = function(pos){
            var pt = mk_config(mm, m)
            pt.a[p] = pt.a[pos]
            pt.a[pos] = ' '
            pt.action_from = pos
            pt.action_to = p
            enqueue(pt)
        } /* move_func */
        if (x < 2) move_func(p + 1)
        if (x > 0) move_func(p - 1)
        if (y > 0) move_func(p - 3)
        if (y < 1) move_func(p + 3)
        if (x == 0 && m.a[p + 2] != m.a[p + 1]) move_func(p + 2)
        if (x == 2 && m.a[p - 2] != m.a[p - 1]) move_func(p - 2)
    } /* while */
} /* do_loop */


function mk_agenda_element(base_pat, color, posx, posy, rad){
    var ele = {mm: 23}
    ele.base_pat = base_pat
    ele.color = color
    ele.posx = posx
    ele.posy = posy
    ele.rad = rad
    return ele
}

/*========================*
 * agenda2str()
 *========================*/
function agenda2str(){
    var s = ""
    for (var i = 0; i < agenda.length; i++){
	var aa = agenda[i]
	s = s + (i + ": '" + aa.base_pat + "' + c(" + aa.color  + ") + pos(" +
		 aa.posx + ", " + aa.posy + ") + rad(" + aa.rad + ")\n")
    }
    return s
}

/*========================*
 * init()
 *========================*/
function init(){
    var cv = document.getElementById("puzzle_canvas")
    var context = cv.getContext('2d') 
    var w = cv.width
    var h = cv.height
    draw_bg(context, w, h)
    draw_base(context)
    draw_base_balls(context, $(".i_data").val())
} /* init */

window.onload = init

/*========================*
 * final()
 *========================*/
function final(){
    var cv = document.getElementById("puzzle_canvas")
    var context = cv.getContext('2d') 
    var w = cv.width
    var h = cv.height
    draw_bg(context, w, h)
    draw_base(context)
    draw_base_balls(context, $(".f_data").val())
} /* final */

/*========================*
 * solve_puzzle()
 *========================*/
function solve_puzzle(){
    var start = mk_config($(".i_data").val(), null)
    var final = mk_config($(".f_data").val(), null)
    init_queue()
    enqueue(start)
    var ele = mk_agenda_element(start.a.join(''), 0, -1, -1, -1)
    for (var k = 0; k < 5; k++) agenda.push(ele)
    outstr = ""
    do_loop(final)
    print_it("number of mk_config = " + n_mk_config)
    print_it("length of t_table = " + t_table.length)
    print_it("agenda.length = " + agenda.length)
    /* $(".result").text(outstr + "\n" + agenda2str()) */
    $(".result").text(outstr)
    var cv = document.getElementById("puzzle_canvas")
    var context = cv.getContext('2d') 
    play_agenda0(context, cv.width, cv.height)
} /* solve_puzzle */

/*========================*
 * exchange()
 *========================*/
function exchange(){
    var start = $(".i_data").val()
    var final = $(".f_data").val()
    $(".i_data").val(final)
    $(".f_data").val(start)
    init()
} /* exchange */
 
/*========================*
 * example(i)
 *========================*/
function example(i){
    var start = ""
    var final = ""
    if (i == 0){
        start = "RBBRR "
    	final = "B RBRR"
    } else if (i == 1){
        start = "RBBRR "
    	final = "RRRBB "
    } else if (i == 2){
        start = "RRRBB "
    	final = "BBRRR "
    }
    $(".i_data").val(final)
    $(".f_data").val(start)
    init()
} /* example */