A Star Search in SaleMan Delivery Problem: Rstudio

1 Description: Delivery Man Problem
2 Objective: SaleMan Project:
3 DeliveryMan software installation
4 My programming: function call ()
5 DeliveryMan : AStar Search Programming with R
6 Single Run:
7 Run 500 times :
8 The following results are based on set.seed(1234)
- 8.1 Z-test for no. of turns
- 8.2 Z-test for no. of steps
9 Conclusion :
10 References:

1 Description: Delivery Man Problem

Delivery Man Problem is a game: one car(blue) is randomly to pick one parcel (green) at a time and delivery to the designated location point. The parcel-pick-and-delivery process repeats for 5 times for one-cycle game completion. In this game, the number of turns is not equivalent to the number of steps, where the “turn” is the sum of fixed unit step-path cost G(s) and heuristic unit step-cost H(s). The heuristic unit step-cost H(s) of this game is generated randomly from one step-path to another while car moving. Players have to search an optimal path to minimize the number of turns to complete one cycle game. The challenge of this project is to optimize the number of turns for one cycle game completion. The unit cost of G(s) is fixed and uniformly distributed whereas the unit cost of H(s) is heuristic across grid path but fixed at each iteration respectively. Both unit costs depend on the numbers of step-path. Therefore , optimization of the total numbers of turns is equivalent to the compute suboptimal step-path of G(s) and the suboptimal step-path of H(s) separately at each iteration. This is, the two suboptimal step-path costs are separatable due to uniform distribution in unit costs at each iteration.

2 Objective: SaleMan Project:

The main purpose in this Project is to implement A* search algorithm to obtain the optimal of turns for one-cycle game completion with R

3 DeliveryMan software installation

R package of DeliveryMan_1.1.0 includes a main program (runDeliveryMan())and other subprograms
The dimension is fixed as a 10x10 road grid with 5-time parcel-pick-and-delivery processes.

4 My programming: function call ()

DKCDeliveryMan() : main program, modified directly from the orginal runDeliveryMan()
HCostpayoff() : heusitic cost within boundary
HCostpayoffboundary() : heusitic cost at the boundary
Rebalancepath() : compute the suboptimal step paths for H(s)
Steppath() : compute the suboptimal step paths for G(s)
myastarsearch() : A star search
mysearchDM() : subprogram to instruct the car how to perform A*search
program setting : all function are only valid for dimension = 10 and delivery = 5

5 DeliveryMan : AStar Search Programming with R

5.1 DKCDeliveryMan()

DKCDeliveryMan = function(carReady = mysearchDM, doPlot = T, pause = 0.1){

  dim = 10
  turns = 2000 
  del = 5 
  verbose = T
  roads = makeRoadMatrices(dim)
  car = list(x = 1, y = 1, wait = 0, load = 0, nextMove = NA, mem = list())
  packages = matrix(sample(1:dim, replace = T, 5 * del), ncol = 5)
  packages[, 5] = rep(0, del)

  Astar_optimal_path = myastarsearch(packages)
  Astar_optimal_path[[4]][,"Status"] = 0
  Astar_optimal_path_packages = Astar_optimal_path[[4]]
  packages = Astar_optimal_path_packages
  step_path  = Astar_optimal_path[[1]][, c("D_CP_X", "D_CP_Y", "D_PG_X", "D_PG_Y")]
  step_list_updated = (Steppath(step_path))[[3]]
  car$mem  = step_list_updated
  kk = 0
  jj = 0
  for (i in 1:turns) {
    roads = updateRoads(roads$hroads, roads$vroads)
    if (doPlot) {
      makeDotGrid(dim, i)
      plotRoads(roads$hroads, roads$vroads)
      points(car$x, car$y, pch = 16, col = "blue", cex = 3)
      plotPackages(packages)
    }
    if (car$wait == 0) {
      if (car$load == 0) {
        on = packageOn(car$x, car$y, packages)
        if (on != 0) {
          packages[on, 5] = 1
          step_list_updated = (Steppath(step_path))[[4+kk]]
          car$mem  = step_list_updated
          kk = kk +2
          car$load = on
        }
      }
      else if (packages[car$load, 3] == car$x && packages[car$load, 4] == car$y) {
        packages[car$load, 5] = 2
        step_list_updated = (Steppath(step_path))[[5+jj]]
        car$mem  = step_list_updated
        jj = jj +2
        car$load = 0
        if (sum(packages[, 5]) == 2 * nrow(packages)) {
          if (verbose){
            cat("\nCongratulations! You suceeded in", i, "turns!")
            cat("\nCongratulations! You suceeded in", myastarsearch(packages)[[2]], "Optimal-path steps!")} # add total Optimal-path steps
          return(list(i, myastarsearch(packages)[c(1,2,4)])) # optimal packages return-output
        }
      }
      car = carReady(roads, car, packages)
      car = processNextMove(car, roads, dim)
    }
    else {
      car$wait = car$wait - 1
    }
    if (pause > 0)
      Sys.sleep(pause)
  }
  cat("\nYou failed to complete the task. Try again.")

  return(NA)
}

5.2 HCostpayoff()

HCostpayoff = function(car, roads ){
  if(car$x != 1  & car$y != 1 & car$x != 10  & car$y != 10 ){
    move_E_6 = roads$hroads[car$x,car$y]
    move_W_4 = roads$hroads[(car$x-1),(car$y)]
    move_N_8 = roads$vroads[car$x,car$y]
    move_S_2 = roads$vroads[(car$x),(car$y-1)]
    dir_move_to_df = data.frame(matrix(NA,ncol=2,nrow=4))
    colnames(dir_move_to_df) = c("move_to", "payoff")
    rownames(dir_move_to_df) = c("move_E_6", "move_W_4", "move_N_8", "move_S_2 ")
    dir_move_to_df[,1] = c(6,4,8,2)
    dir_move_to_df[1,2] = move_E_6
    dir_move_to_df[2,2] = move_W_4
    dir_move_to_df[3,2] = move_N_8
    dir_move_to_df[4,2] = move_S_2
    dir_move_to_df_sort = dir_move_to_df[order(dir_move_to_df$payoff),]
  }else{dir_move_to_df_sort = NA}
  return(list(dir_move_to_df_sort, car) )
}

5.3 HCostpayoffboundary()

HCostpayoffboundary = function(car, roads ){

  if(car$x == 1  | car$y == 1 | car$x == 10  | car$y == 10 ){

    if(car$x != 10  ){move_E_6 = roads$hroads[car$x,car$y]}else{move_E_6 =NA}
    if(car$y != 10  ){move_N_8 = roads$vroads[car$x,car$y]}else{move_N_8 =NA}
    if(length(roads$hroads[(car$x-1),(car$y)]) != 0 ){ move_W_4 =roads$hroads[(car$x-1),(car$y)]}else{ move_W_4 =NA}
    if(length(roads$vroads[(car$x),(car$y-1)]) != 0 ){move_S_2 = roads$vroads[(car$x),(car$y-1)]}else{move_S_2 =NA}

    dir_move_away_from_boundary = data.frame(matrix(NA,ncol=2,nrow=4))
    colnames(dir_move_away_from_boundary) = c("move_to", "payoff")
    rownames(dir_move_away_from_boundary ) = c("move_E_6", "move_W_4", "move_N_8", "move_S_2 ")
    dir_move_away_from_boundary[,1] = c(6,4,8,2)
    dir_move_away_from_boundary[1,2] = move_E_6
    dir_move_away_from_boundary[2,2] = move_W_4
    dir_move_away_from_boundary[3,2] = move_N_8
    dir_move_away_from_boundary[4,2] = move_S_2
    dir_move_away_from_boundary_sort = dir_move_away_from_boundary[order(dir_move_away_from_boundary$payoff),]
  }else{dir_move_away_from_boundary_sort = NA}
  return(list(dir_move_away_from_boundary_sort, car))
}

5.4 Rebalancepath()

Rebalancepath =function(Target, car, roads ){

  if(car$x != 1  & car$y != 1 & car$x != 10  & car$y != 10 ){
    curr_Hcost = HCostpayoff(car, roads )
    curr_HC_move_order = curr_Hcost[[1]][, "move_to"]
    uniq = unique(Target)
    if (curr_HC_move_order[1] %in% Target) {
      move_first = intersect(curr_HC_move_order, uniq)
      nextMove =  move_first[1]
      Target[which(Target == nextMove)[1]] = NA
    }else if (curr_HC_move_order[2] %in% Target){
      move_first = intersect(curr_HC_move_order, uniq)
      nextMove =  move_first[1]
      Target[which(Target == nextMove)[1]] = NA
    } else{
      move_first = intersect(curr_HC_move_order, uniq)
      nextMove =  move_first[1]
      Target[which(Target == nextMove)[1]] = NA
    }
  }else{list(Target,curr_HC_move_order =NA,  nextMove=NA, curr_Hcost=NA)}

  return(list(Target,curr_HC_move_order,  nextMove, curr_Hcost))
}

5.5 Steppath()

Steppath = function(step_path){

  step_path_temp = step_path
  step_path_temp[, 1][which(step_path_temp[, 1] > 0)]   = 6
  step_path_temp[, 3][which(step_path_temp[, 3] > 0)]   = 6
  step_path_temp[, 1][which(step_path_temp[, 1] < 0)]   = 4
  step_path_temp[, 3][which(step_path_temp[, 3] < 0)]   = 4
  step_path_temp[, 1][which(step_path_temp[, 1] == 0)]  = 5
  step_path_temp[, 3][which(step_path_temp[, 3] == 0)]  = 5

  step_path_temp[, 2][which(step_path_temp[, 2] > 0)]   = 8
  step_path_temp[, 4][which(step_path_temp[, 4] > 0)]   = 8
  step_path_temp[, 2][which(step_path_temp[, 2] < 0)]   = 2
  step_path_temp[, 4][which(step_path_temp[, 4] < 0)]   = 2
  step_path_temp[, 2][which(step_path_temp[, 2] == 0)]  = 5
  step_path_temp[, 4][which(step_path_temp[, 4] == 0)]  = 5

  colnames(step_path_temp) = c("D_CP_X_S", "D_CP_Y_S", "D_PG_X_S", "D_PG_Y_S")
  movingstep_matrix = cbind(step_path, step_path_temp)
  movingstep_abs  = abs(movingstep_matrix)
  movingstep_abs[movingstep_abs == 0] = 1

  Total_path_step_list  = array()
  for (j in 1:dim(step_path)[1]){
    Parcel_01 = append(array(movingstep_abs[j,"D_CP_X_S"],movingstep_abs[j,"D_CP_X"] ), array(movingstep_abs[j,"D_CP_Y_S"],movingstep_abs[j,"D_CP_Y"] ) )
    Goal_01   = append(array(movingstep_abs[j,"D_PG_X_S"],movingstep_abs[j,"D_PG_X"] ), array(movingstep_abs[j,"D_PG_Y_S"],movingstep_abs[j,"D_PG_Y"] ) )
    Target_01 = append(Parcel_01, Goal_01)
    Total_path_step_list = append(Total_path_step_list, Target_01) }
    Total_path_step_list = Total_path_step_list[-1]

  Total_path_step_list_NA  = array()
  for (j in 1:dim(step_path)[1]){
    Parcel_01 = append(array(movingstep_abs[j,"D_CP_X_S"],movingstep_abs[j,"D_CP_X"] ), array(movingstep_abs[j,"D_CP_Y_S"],movingstep_abs[j,"D_CP_Y"] ) )
    Parcel_01 = c( Parcel_01 , NA)
    Goal_01   = append(array(movingstep_abs[j,"D_PG_X_S"],movingstep_abs[j,"D_PG_X"] ), array(movingstep_abs[j,"D_PG_Y_S"],movingstep_abs[j,"D_PG_Y"] ) )
    Goal_01   = c(Goal_01 , NA)
    Target_01 = append(Parcel_01, Goal_01)
    Total_path_step_list_NA = append(Total_path_step_list_NA, Target_01) }
    Total_path_step_list_NA = Total_path_step_list_NA[-1]

  Parcel_01 = append(array(movingstep_abs[1,"D_CP_X_S"],movingstep_abs[1,"D_CP_X"] ), array(movingstep_abs[1,"D_CP_Y_S"],movingstep_abs[1,"D_CP_Y"] ) )
  Goal_01   = append(array(movingstep_abs[1,"D_PG_X_S"],movingstep_abs[1,"D_PG_X"] ), array(movingstep_abs[1,"D_PG_Y_S"],movingstep_abs[1,"D_PG_Y"] ) )

  Parcel_02 = append(array(movingstep_abs[2,"D_CP_X_S"],movingstep_abs[2,"D_CP_X"] ), array(movingstep_abs[2,"D_CP_Y_S"],movingstep_abs[2,"D_CP_Y"] ) )
  Goal_02   = append(array(movingstep_abs[2,"D_PG_X_S"],movingstep_abs[2,"D_PG_X"] ), array(movingstep_abs[2,"D_PG_Y_S"],movingstep_abs[2,"D_PG_Y"] ) )

  Parcel_03 = append(array(movingstep_abs[3,"D_CP_X_S"],movingstep_abs[3,"D_CP_X"] ), array(movingstep_abs[3,"D_CP_Y_S"],movingstep_abs[3,"D_CP_Y"] ) )
  Goal_03   = append(array(movingstep_abs[3,"D_PG_X_S"],movingstep_abs[3,"D_PG_X"] ), array(movingstep_abs[3,"D_PG_Y_S"],movingstep_abs[3,"D_PG_Y"] ) )

  Parcel_04 = append(array(movingstep_abs[4,"D_CP_X_S"],movingstep_abs[4,"D_CP_X"] ), array(movingstep_abs[4,"D_CP_Y_S"],movingstep_abs[4,"D_CP_Y"] ) )
  Goal_04   = append(array(movingstep_abs[4,"D_PG_X_S"],movingstep_abs[4,"D_PG_X"] ), array(movingstep_abs[4,"D_PG_Y_S"],movingstep_abs[4,"D_PG_Y"] ) )

  Parcel_05 = append(array(movingstep_abs[5,"D_CP_X_S"],movingstep_abs[5,"D_CP_X"] ), array(movingstep_abs[5,"D_CP_Y_S"],movingstep_abs[5,"D_CP_Y"] ) )
  Goal_05   = append(array(movingstep_abs[5,"D_PG_X_S"],movingstep_abs[5,"D_PG_X"] ), array(movingstep_abs[5,"D_PG_Y_S"],movingstep_abs[5,"D_PG_Y"] ) )

  return(list(movingstep_matrix, Total_path_step_list, Parcel_01, Goal_01, Parcel_02, Goal_02, Parcel_03, Goal_03, Parcel_04, Goal_04, Parcel_05, Goal_05,  Total_path_step_list_NA ))
}

5.6 myastarsearch()

myastarsearch=function(packages){
  Car_pos = c(1,1) # current car position
  initial_packages = packages
  set_ID = c(1: dim(packages)[1])
  closed_list_optimal_path_updated = data.frame(matrix("NA",ncol=19,nrow=0))

  for (j in c(1:dim(packages)[1])){
    # create car position matrix same dimension as Parcels Matrix and Goal Matrix
    Car_pos_mat = packages
    Car_pos_mat = Car_pos_mat/Car_pos_mat
    Car_pos_mat[,1] = Car_pos_mat[,1]*Car_pos[1]
    Car_pos_mat[,2] = Car_pos_mat[,2]*Car_pos[2]

    Distance_CP = (packages[,1:2] - Car_pos_mat[,1:2])
    Distance_PG = (packages[,3:4] - packages[,1:2])
         MHD_CP = abs(Distance_CP)
    Sum_MHD_CP  = rowSums(MHD_CP, dims = 1)
         MHD_PG = abs(Distance_PG)
    Sum_MHD_PG  = rowSums(MHD_PG, dims = 1)
    Sum_MHD_CP_PG = MHD_CP + MHD_PG
    Total_MHD_CP_PG_XY = rowSums(Sum_MHD_CP_PG, dims = 1)

    optimal_path_mat = cbind(set_ID, Car_pos_mat[,1:2],packages,Distance_CP, Distance_PG , MHD_CP, MHD_PG, Sum_MHD_CP_PG ,Total_MHD_CP_PG_XY, Sum_MHD_CP, Sum_MHD_PG )
    optimal_path_df = data.frame(optimal_path_mat)
    colnames(optimal_path_df) = c("ID", "C_X", "C_Y","P_X", "P_Y", "G_X", "G_Y", "Status", "D_CP_X","D_CP_Y", "D_PG_X", "D_PG_Y", "MHD_CP_X", "MHD_CP_Y", "MHD_PG_X", "MHD_PG_Y", "S_MHD_CP_PG_X", "S_MHD_CP_PG_Y", "Tot_MHD_CP_PG_XY","Sum_MHD_CP","Sum_MHD_PG")

    optimal_path_df_sorted = optimal_path_df[order(optimal_path_df$Sum_MHD_CP),] 
    optimal_path_df_sorted[1,"Status"] = 2
    closed_list_optimal_path = optimal_path_df_sorted[1,]
    closed_list_optimal_path_updated = rbind(closed_list_optimal_path_updated, closed_list_optimal_path)
    curr_pos_car = optimal_path_df_sorted[1, c("G_X", "G_Y")]
    packages_onedim_less = optimal_path_df_sorted[-1,c(4,5,6,7,8)]

    #### another iterations : updates
    packages = packages_onedim_less
    Car_pos  = curr_pos_car
    Car_pos_mat = packages
    set_ID = optimal_path_df_sorted[-1, "ID"]
  }

  closed_list_optimal_path_updated
  total_no_of_steps  = sum(closed_list_optimal_path_updated$Tot_MHD_CP_PG_XY)
  final_optimal_path = closed_list_optimal_path_updated[,4:8]
  return(list(closed_list_optimal_path_updated, total_no_of_steps, initial_packages,final_optimal_path))
}

5.7 mysearchDM()

 mysearchDM= function (roads, car, packages)
{
  if (5 %in% car$mem ) {
    loc_5 = which(car$mem  == 5)
    if (loc_5[1]  != 1){
      split_5 = car$mem[1:(loc_5[1]-1)]
      if (car$x != 1  & car$y != 1 & car$x != 10  & car$y != 10 ) {
        HCcost_5 = HCostpayoff(car,roads )
      }else{ HCcost_5 = HCostpayoffboundary (car,roads )}
      Hcost =  HCcost_5[[1]][which(HCcost_5[[1]][,"payoff"] != "NA"),"move_to"]
      move_first = intersect(Hcost, split_5 )
      if (length(move_first) != 0) {
        delete_me = which(car$mem  ==  move_first[[1]])[[1]]
        car$mem = car$mem[-delete_me ]
        car$nextMove = move_first[[1]]
      }else{
        nextMove = car$mem[1]
        car$mem  =  car$mem[-1]
        car$nextMove = nextMove
      }
    }else{
      nextMove = car$mem[1]
       car$mem =  car$mem[-1]
      car$nextMove = nextMove
    }
  }else if(car$x != 1  & car$y != 1 & car$x != 10  & car$y != 10 ){
    Target_reb_path = Rebalancepath(Target = car$mem, car, roads)
    if ( 1 < sum(Target_reb_path[[4]][[1]][, "payoff"])  &  sum(Target_reb_path[[4]][[1]][, "payoff"]) <200) {
      nextMove = Target_reb_path[[3]]
      car$nextMove = nextMove
      car$mem =  sort(Target_reb_path[[1]])
      }
  }else if (car$x == 1  | car$y == 1 | car$x == 10  | car$y == 10){
    HCBoundary = HCostpayoffboundary(car, roads )
    move_BF = intersect(HCBoundary[[1]][which(HCBoundary[[1]][, "payoff"] != "NA"), "move_to"], car$mem)
    car$nextMove  =  move_BF[1]
    car$mem[which(car$mem == move_BF[1])[1]]= NA
    car$mem = sort(car$mem)
  }else{
    nextMove = car$mem[1]
     car$mem = car$mem[-1]
    car$nextMove = nextMove
  }
  return(car)
}

6 Single Run:

library(DeliveryMan)
set.seed(1234)
DKCDeliveryMan(carReady =  mysearchDM , doPlot = F, pause = -5)

## 
## Congratulations! You suceeded in 117 turns!
## Congratulations! You suceeded in 40 Optimal-path steps!

## [[1]]
## [1] 117
## 
## [[2]]
## [[2]][[1]]
##   ID C_X C_Y P_X P_Y G_X G_Y Status D_CP_X D_CP_Y D_PG_X D_PG_Y MHD_CP_X
## 3  1   1   1   5   2   4   8      2      4      1     -1      6        4
## 5  2   4   8   5   6   4   8      2      1     -2     -1      2        1
## 2  3   4   8   6   4   6   5      2      2     -4      0      1        2
## 4  4   6   5   9   7   8   4      2      3      2     -1     -3        3
##   MHD_CP_Y MHD_PG_X MHD_PG_Y S_MHD_CP_PG_X S_MHD_CP_PG_Y Tot_MHD_CP_PG_XY
## 3        1        1        6             5             7               12
## 5        2        1        2             2             4                6
## 2        4        0        1             2             5                7
## 4        2        1        3             4             5                9
##   Sum_MHD_CP Sum_MHD_PG
## 3          5          7
## 5          3          3
## 2          6          1
## 4          5          4
##  [ reached 'max' / getOption("max.print") -- omitted 1 rows ]
## 
## [[2]][[2]]
## [1] 40
## 
## [[2]][[3]]
##   P_X P_Y G_X G_Y Status
## 3   5   2   4   8      2
## 5   5   6   4   8      2
## 2   6   4   6   5      2
## 4   9   7   8   4      2
## 1  10   6  10   4      2

7 Run 500 times :

library(DeliveryMan)
set.seed(1234)
run_500_output = data.frame(matrix("NA",ncol=2,nrow=1))
run_500_output_updated = data.frame(matrix("NA",ncol=2,nrow=0))

for (i in 1:500) {
   run_500 = DKCDeliveryMan(carReady =  mysearchDM , doPlot = F, pause = -5)
    colnames(run_500_output) = c("turns", "steps")
    colnames(run_500_output_updated) = c("turns", "steps")
    run_500_output[, "turns"] = run_500[[1]]
    run_500_output[, "steps"] = run_500[[2]][2]
    run_500_output_updated = rbind(run_500_output_updated,run_500_output )
}

## 
## Congratulations! You suceeded in 117 turns!
## Congratulations! You suceeded in 40 Optimal-path steps!
## Congratulations! You suceeded in 167 turns!
## Congratulations! You suceeded in 58 Optimal-path steps!
## Congratulations! You suceeded in 217 turns!
## Congratulations! You suceeded in 68 Optimal-path steps!
## Congratulations! You suceeded in 175 turns!
## Congratulations! You suceeded in 50 Optimal-path steps!
## Congratulations! You suceeded in 216 turns!
## Congratulations! You suceeded in 59 Optimal-path steps!
## Congratulations! You suceeded in 241 turns!
## Congratulations! You suceeded in 66 Optimal-path steps!
## Congratulations! You suceeded in 170 turns!
## Congratulations! You suceeded in 51 Optimal-path steps!
## Congratulations! You suceeded in 181 turns!
## Congratulations! You suceeded in 52 Optimal-path steps!
## Congratulations! You suceeded in 158 turns!
## Congratulations! You suceeded in 50 Optimal-path steps!
## Congratulations! You suceeded in 179 turns!
## Congratulations! You suceeded in 59 Optimal-path steps!
## Congratulations! You suceeded in 187 turns!
## Congratulations! You suceeded in 59 Optimal-path steps!
## Congratulations! You suceeded in 198 turns!
## Congratulations! You suceeded in 60 Optimal-path steps!
## Congratulations! You suceeded in 162 turns!
## Congratulations! You suceeded in 49 Optimal-path steps!
## Congratulations! You suceeded in 293 turns!
## Congratulations! You suceeded in 80 Optimal-path steps!
## Congratulations! You suceeded in 171 turns!
## Congratulations! You suceeded in 60 Optimal-path steps!
## Congratulations! You suceeded in 137 turns!
## Congratulations! You suceeded in 42 Optimal-path steps!
## Congratulations! You suceeded in 134 turns!
## Congratulations! You suceeded in 37 Optimal-path steps!
## Congratulations! You suceeded in 243 turns!
## Congratulations! You suceeded in 66 Optimal-path steps!
## Congratulations! You suceeded in 240 turns!
## Congratulations! You suceeded in 62 Optimal-path steps!
## Congratulations! You suceeded in 243 turns!
## Congratulations! You suceeded in 68 Optimal-path steps!
## Congratulations! You suceeded in 197 turns!
## Congratulations! You suceeded in 60 Optimal-path steps!
## Congratulations! You suceeded in 141 turns!
## Congratulations! You suceeded in 40 Optimal-path steps!
## Congratulations! You suceeded in 143 turns!
## Congratulations! You suceeded in 45 Optimal-path steps!
## Congratulations! You suceeded in 233 turns!
## Congratulations! You suceeded in 62 Optimal-path steps!
## Congratulations! You suceeded in 164 turns!
## Congratulations! You suceeded in 54 Optimal-path steps!
## Congratulations! You suceeded in 103 turns!
## Congratulations! You suceeded in 36 Optimal-path steps!
## Congratulations! You suceeded in 257 turns!
## Congratulations! You suceeded in 74 Optimal-path steps!
## Congratulations! You suceeded in 213 turns!
## Congratulations! You suceeded in 63 Optimal-path steps!
## Congratulations! You suceeded in 171 turns!
## Congratulations! You suceeded in 53 Optimal-path steps!
## Congratulations! You suceeded in 161 turns!
## Congratulations! You suceeded in 53 Optimal-path steps!
## Congratulations! You suceeded in 156 turns!
## Congratulations! You suceeded in 47 Optimal-path steps!
## Congratulations! You suceeded in 164 turns!
## Congratulations! You suceeded in 51 Optimal-path steps!
## Congratulations! You suceeded in 191 turns!
## Congratulations! You suceeded in 55 Optimal-path steps!
## Congratulations! You suceeded in 220 turns!
## Congratulations! You suceeded in 70 Optimal-path steps!
## Congratulations! You suceeded in 179 turns!
## Congratulations! You suceeded in 57 Optimal-path steps!
## Congratulations! You suceeded in 227 turns!
## Congratulations! You suceeded in 66 Optimal-path steps!
## Congratulations! You suceeded in 165 turns!
## Congratulations! You suceeded in 54 Optimal-path steps!
## Congratulations! You suceeded in 225 turns!
## Congratulations! You suceeded in 67 Optimal-path steps!
## Congratulations! You suceeded in 165 turns!
## Congratulations! You suceeded in 49 Optimal-path steps!
## Congratulations! You suceeded in 282 turns!
## Congratulations! You suceeded in 67 Optimal-path steps!
## Congratulations! You suceeded in 221 turns!
## Congratulations! You suceeded in 60 Optimal-path steps!
## Congratulations! You suceeded in 135 turns!
## Congratulations! You suceeded in 40 Optimal-path steps!
## Congratulations! You suceeded in 124 turns!
## Congratulations! You suceeded in 44 Optimal-path steps!
## Congratulations! You suceeded in 154 turns!
## Congratulations! You suceeded in 45 Optimal-path steps!
## Congratulations! You suceeded in 172 turns!
## Congratulations! You suceeded in 58 Optimal-path steps!
## Congratulations! You suceeded in 178 turns!
## Congratulations! You suceeded in 53 Optimal-path steps!
## Congratulations! You suceeded in 156 turns!
## Congratulations! You suceeded in 55 Optimal-path steps!
## Congratulations! You suceeded in 124 turns!
## Congratulations! You suceeded in 43 Optimal-path steps!
## Congratulations! You suceeded in 191 turns!
## Congratulations! You suceeded in 61 Optimal-path steps!
## Congratulations! You suceeded in 209 turns!
## Congratulations! You suceeded in 53 Optimal-path steps!
## Congratulations! You suceeded in 309 turns!
## Congratulations! You suceeded in 74 Optimal-path steps!
## Congratulations! You suceeded in 133 turns!
## Congratulations! You suceeded in 47 Optimal-path steps!
## Congratulations! You suceeded in 177 turns!
## Congratulations! You suceeded in 61 Optimal-path steps!
## Congratulations! You suceeded in 207 turns!
## Congratulations! You suceeded in 60 Optimal-path steps!
## Congratulations! You suceeded in 193 turns!
## Congratulations! You suceeded in 62 Optimal-path steps!
## Congratulations! You suceeded in 193 turns!
## Congratulations! You suceeded in 71 Optimal-path steps!
## Congratulations! You suceeded in 174 turns!
## Congratulations! You suceeded in 47 Optimal-path steps!
## Congratulations! You suceeded in 177 turns!
## Congratulations! You suceeded in 53 Optimal-path steps!
## Congratulations! You suceeded in 216 turns!
## Congratulations! You suceeded in 63 Optimal-path steps!
## Congratulations! You suceeded in 115 turns!
## Congratulations! You suceeded in 39 Optimal-path steps!
## Congratulations! You suceeded in 166 turns!
## Congratulations! You suceeded in 52 Optimal-path steps!
## Congratulations! You suceeded in 150 turns!
## Congratulations! You suceeded in 48 Optimal-path steps!
## Congratulations! You suceeded in 140 turns!
## Congratulations! You suceeded in 46 Optimal-path steps!
## Congratulations! You suceeded in 151 turns!
## Congratulations! You suceeded in 48 Optimal-path steps!
## Congratulations! You suceeded in 121 turns!
## Congratulations! You suceeded in 37 Optimal-path steps!
## Congratulations! You suceeded in 236 turns!
## Congratulations! You suceeded in 65 Optimal-path steps!
## Congratulations! You suceeded in 123 turns!
## Congratulations! You suceeded in 40 Optimal-path steps!
## Congratulations! You suceeded in 157 turns!
## Congratulations! You suceeded in 53 Optimal-path steps!
## Congratulations! You suceeded in 200 turns!
## Congratulations! You suceeded in 62 Optimal-path steps!
## Congratulations! You suceeded in 246 turns!
## Congratulations! You suceeded in 66 Optimal-path steps!
## Congratulations! You suceeded in 167 turns!
## Congratulations! You suceeded in 55 Optimal-path steps!
## Congratulations! You suceeded in 205 turns!
## Congratulations! You suceeded in 60 Optimal-path steps!
## Congratulations! You suceeded in 159 turns!
## Congratulations! You suceeded in 55 Optimal-path steps!
## Congratulations! You suceeded in 113 turns!
## Congratulations! You suceeded in 39 Optimal-path steps!
## Congratulations! You suceeded in 186 turns!
## Congratulations! You suceeded in 55 Optimal-path steps!
## Congratulations! You suceeded in 124 turns!
## Congratulations! You suceeded in 39 Optimal-path steps!
## Congratulations! You suceeded in 150 turns!
## Congratulations! You suceeded in 48 Optimal-path steps!
## Congratulations! You suceeded in 237 turns!
## Congratulations! You suceeded in 72 Optimal-path steps!
## Congratulations! You suceeded in 217 turns!
## Congratulations! You suceeded in 64 Optimal-path steps!
## Congratulations! You suceeded in 144 turns!
## Congratulations! You suceeded in 47 Optimal-path steps!
## Congratulations! You suceeded in 170 turns!
## Congratulations! You suceeded in 54 Optimal-path steps!
## Congratulations! You suceeded in 184 turns!
## Congratulations! You suceeded in 57 Optimal-path steps!
## Congratulations! You suceeded in 201 turns!
## Congratulations! You suceeded in 54 Optimal-path steps!
## Congratulations! You suceeded in 257 turns!
## Congratulations! You suceeded in 70 Optimal-path steps!
## Congratulations! You suceeded in 253 turns!
## Congratulations! You suceeded in 71 Optimal-path steps!
## Congratulations! You suceeded in 155 turns!
## Congratulations! You suceeded in 39 Optimal-path steps!
## Congratulations! You suceeded in 112 turns!
## Congratulations! You suceeded in 38 Optimal-path steps!
## Congratulations! You suceeded in 179 turns!
## Congratulations! You suceeded in 52 Optimal-path steps!
## Congratulations! You suceeded in 190 turns!
## Congratulations! You suceeded in 55 Optimal-path steps!
## Congratulations! You suceeded in 170 turns!
## Congratulations! You suceeded in 53 Optimal-path steps!
## Congratulations! You suceeded in 142 turns!
## Congratulations! You suceeded in 42 Optimal-path steps!
## Congratulations! You suceeded in 226 turns!
## Congratulations! You suceeded in 69 Optimal-path steps!
## Congratulations! You suceeded in 145 turns!
## Congratulations! You suceeded in 45 Optimal-path steps!
## Congratulations! You suceeded in 161 turns!
## Congratulations! You suceeded in 55 Optimal-path steps!
## Congratulations! You suceeded in 202 turns!
## Congratulations! You suceeded in 53 Optimal-path steps!
## Congratulations! You suceeded in 117 turns!
## Congratulations! You suceeded in 45 Optimal-path steps!
## Congratulations! You suceeded in 186 turns!
## Congratulations! You suceeded in 55 Optimal-path steps!
## Congratulations! You suceeded in 177 turns!
## Congratulations! You suceeded in 57 Optimal-path steps!
## Congratulations! You suceeded in 165 turns!
## Congratulations! You suceeded in 49 Optimal-path steps!
## Congratulations! You suceeded in 199 turns!
## Congratulations! You suceeded in 64 Optimal-path steps!
## Congratulations! You suceeded in 136 turns!
## Congratulations! You suceeded in 48 Optimal-path steps!
## Congratulations! You suceeded in 261 turns!
## Congratulations! You suceeded in 82 Optimal-path steps!
## Congratulations! You suceeded in 117 turns!
## Congratulations! You suceeded in 41 Optimal-path steps!
## Congratulations! You suceeded in 273 turns!
## Congratulations! You suceeded in 73 Optimal-path steps!
## Congratulations! You suceeded in 311 turns!
## Congratulations! You suceeded in 85 Optimal-path steps!
## Congratulations! You suceeded in 237 turns!
## Congratulations! You suceeded in 64 Optimal-path steps!
## Congratulations! You suceeded in 252 turns!
## Congratulations! You suceeded in 78 Optimal-path steps!
## Congratulations! You suceeded in 203 turns!
## Congratulations! You suceeded in 59 Optimal-path steps!
## Congratulations! You suceeded in 129 turns!
## Congratulations! You suceeded in 46 Optimal-path steps!
## Congratulations! You suceeded in 181 turns!
## Congratulations! You suceeded in 55 Optimal-path steps!
## Congratulations! You suceeded in 169 turns!
## Congratulations! You suceeded in 44 Optimal-path steps!
## Congratulations! You suceeded in 267 turns!
## Congratulations! You suceeded in 64 Optimal-path steps!
## Congratulations! You suceeded in 115 turns!
## Congratulations! You suceeded in 34 Optimal-path steps!
## Congratulations! You suceeded in 136 turns!
## Congratulations! You suceeded in 44 Optimal-path steps!
## Congratulations! You suceeded in 142 turns!
## Congratulations! You suceeded in 45 Optimal-path steps!
## Congratulations! You suceeded in 267 turns!
## Congratulations! You suceeded in 67 Optimal-path steps!
## Congratulations! You suceeded in 133 turns!
## Congratulations! You suceeded in 44 Optimal-path steps!
## Congratulations! You suceeded in 140 turns!
## Congratulations! You suceeded in 47 Optimal-path steps!
## Congratulations! You suceeded in 155 turns!
## Congratulations! You suceeded in 52 Optimal-path steps!
## Congratulations! You suceeded in 123 turns!
## Congratulations! You suceeded in 41 Optimal-path steps!
## Congratulations! You suceeded in 219 turns!
## Congratulations! You suceeded in 61 Optimal-path steps!
## Congratulations! You suceeded in 207 turns!
## Congratulations! You suceeded in 60 Optimal-path steps!
## Congratulations! You suceeded in 271 turns!
## Congratulations! You suceeded in 77 Optimal-path steps!
## Congratulations! You suceeded in 169 turns!
## Congratulations! You suceeded in 52 Optimal-path steps!
## Congratulations! You suceeded in 207 turns!
## Congratulations! You suceeded in 60 Optimal-path steps!
## Congratulations! You suceeded in 155 turns!
## Congratulations! You suceeded in 53 Optimal-path steps!
## Congratulations! You suceeded in 106 turns!
## Congratulations! You suceeded in 34 Optimal-path steps!
## Congratulations! You suceeded in 155 turns!
## Congratulations! You suceeded in 46 Optimal-path steps!
## Congratulations! You suceeded in 268 turns!
## Congratulations! You suceeded in 76 Optimal-path steps!
## Congratulations! You suceeded in 205 turns!
## Congratulations! You suceeded in 65 Optimal-path steps!
## Congratulations! You suceeded in 126 turns!
## Congratulations! You suceeded in 41 Optimal-path steps!
## Congratulations! You suceeded in 201 turns!
## Congratulations! You suceeded in 64 Optimal-path steps!
## Congratulations! You suceeded in 146 turns!
## Congratulations! You suceeded in 45 Optimal-path steps!
## Congratulations! You suceeded in 213 turns!
## Congratulations! You suceeded in 60 Optimal-path steps!
## Congratulations! You suceeded in 231 turns!
## Congratulations! You suceeded in 57 Optimal-path steps!
## Congratulations! You suceeded in 229 turns!
## Congratulations! You suceeded in 71 Optimal-path steps!
## Congratulations! You suceeded in 228 turns!
## Congratulations! You suceeded in 62 Optimal-path steps!
## Congratulations! You suceeded in 276 turns!
## Congratulations! You suceeded in 78 Optimal-path steps!
## Congratulations! You suceeded in 130 turns!
## Congratulations! You suceeded in 41 Optimal-path steps!
## Congratulations! You suceeded in 223 turns!
## Congratulations! You suceeded in 55 Optimal-path steps!
## Congratulations! You suceeded in 220 turns!
## Congratulations! You suceeded in 70 Optimal-path steps!
## Congratulations! You suceeded in 137 turns!
## Congratulations! You suceeded in 43 Optimal-path steps!
## Congratulations! You suceeded in 319 turns!
## Congratulations! You suceeded in 85 Optimal-path steps!
## Congratulations! You suceeded in 155 turns!
## Congratulations! You suceeded in 59 Optimal-path steps!
## Congratulations! You suceeded in 149 turns!
## Congratulations! You suceeded in 49 Optimal-path steps!
## Congratulations! You suceeded in 150 turns!
## Congratulations! You suceeded in 49 Optimal-path steps!
## Congratulations! You suceeded in 119 turns!
## Congratulations! You suceeded in 43 Optimal-path steps!
## Congratulations! You suceeded in 168 turns!
## Congratulations! You suceeded in 56 Optimal-path steps!
## Congratulations! You suceeded in 224 turns!
## Congratulations! You suceeded in 66 Optimal-path steps!
## Congratulations! You suceeded in 180 turns!
## Congratulations! You suceeded in 61 Optimal-path steps!
## Congratulations! You suceeded in 236 turns!
## Congratulations! You suceeded in 73 Optimal-path steps!
## Congratulations! You suceeded in 223 turns!
## Congratulations! You suceeded in 57 Optimal-path steps!
## Congratulations! You suceeded in 308 turns!
## Congratulations! You suceeded in 78 Optimal-path steps!
## Congratulations! You suceeded in 182 turns!
## Congratulations! You suceeded in 48 Optimal-path steps!
## Congratulations! You suceeded in 179 turns!
## Congratulations! You suceeded in 50 Optimal-path steps!
## Congratulations! You suceeded in 207 turns!
## Congratulations! You suceeded in 58 Optimal-path steps!
## Congratulations! You suceeded in 150 turns!
## Congratulations! You suceeded in 46 Optimal-path steps!
## Congratulations! You suceeded in 145 turns!
## Congratulations! You suceeded in 42 Optimal-path steps!
## Congratulations! You suceeded in 149 turns!
## Congratulations! You suceeded in 44 Optimal-path steps!
## Congratulations! You suceeded in 198 turns!
## Congratulations! You suceeded in 60 Optimal-path steps!
## Congratulations! You suceeded in 179 turns!
## Congratulations! You suceeded in 56 Optimal-path steps!
## Congratulations! You suceeded in 146 turns!
## Congratulations! You suceeded in 44 Optimal-path steps!
## Congratulations! You suceeded in 162 turns!
## Congratulations! You suceeded in 47 Optimal-path steps!
## Congratulations! You suceeded in 156 turns!
## Congratulations! You suceeded in 44 Optimal-path steps!
## Congratulations! You suceeded in 225 turns!
## Congratulations! You suceeded in 72 Optimal-path steps!
## Congratulations! You suceeded in 229 turns!
## Congratulations! You suceeded in 65 Optimal-path steps!
## Congratulations! You suceeded in 133 turns!
## Congratulations! You suceeded in 44 Optimal-path steps!
## Congratulations! You suceeded in 153 turns!
## Congratulations! You suceeded in 54 Optimal-path steps!
## Congratulations! You suceeded in 225 turns!
## Congratulations! You suceeded in 63 Optimal-path steps!
## Congratulations! You suceeded in 256 turns!
## Congratulations! You suceeded in 66 Optimal-path steps!
## Congratulations! You suceeded in 180 turns!
## Congratulations! You suceeded in 48 Optimal-path steps!
## Congratulations! You suceeded in 111 turns!
## Congratulations! You suceeded in 41 Optimal-path steps!
## Congratulations! You suceeded in 152 turns!
## Congratulations! You suceeded in 41 Optimal-path steps!
## Congratulations! You suceeded in 173 turns!
## Congratulations! You suceeded in 53 Optimal-path steps!
## Congratulations! You suceeded in 150 turns!
## Congratulations! You suceeded in 52 Optimal-path steps!
## Congratulations! You suceeded in 184 turns!
## Congratulations! You suceeded in 54 Optimal-path steps!
## Congratulations! You suceeded in 250 turns!
## Congratulations! You suceeded in 68 Optimal-path steps!
## Congratulations! You suceeded in 135 turns!
## Congratulations! You suceeded in 39 Optimal-path steps!
## Congratulations! You suceeded in 163 turns!
## Congratulations! You suceeded in 58 Optimal-path steps!
## Congratulations! You suceeded in 289 turns!
## Congratulations! You suceeded in 86 Optimal-path steps!
## Congratulations! You suceeded in 152 turns!
## Congratulations! You suceeded in 51 Optimal-path steps!
## Congratulations! You suceeded in 176 turns!
## Congratulations! You suceeded in 54 Optimal-path steps!
## Congratulations! You suceeded in 185 turns!
## Congratulations! You suceeded in 50 Optimal-path steps!
## Congratulations! You suceeded in 245 turns!
## Congratulations! You suceeded in 74 Optimal-path steps!
## Congratulations! You suceeded in 220 turns!
## Congratulations! You suceeded in 74 Optimal-path steps!
## Congratulations! You suceeded in 148 turns!
## Congratulations! You suceeded in 50 Optimal-path steps!
## Congratulations! You suceeded in 209 turns!
## Congratulations! You suceeded in 65 Optimal-path steps!
## Congratulations! You suceeded in 208 turns!
## Congratulations! You suceeded in 58 Optimal-path steps!
## Congratulations! You suceeded in 171 turns!
## Congratulations! You suceeded in 54 Optimal-path steps!
## Congratulations! You suceeded in 159 turns!
## Congratulations! You suceeded in 49 Optimal-path steps!
## Congratulations! You suceeded in 157 turns!
## Congratulations! You suceeded in 51 Optimal-path steps!
## Congratulations! You suceeded in 245 turns!
## Congratulations! You suceeded in 66 Optimal-path steps!
## Congratulations! You suceeded in 202 turns!
## Congratulations! You suceeded in 59 Optimal-path steps!
## Congratulations! You suceeded in 160 turns!
## Congratulations! You suceeded in 53 Optimal-path steps!
## Congratulations! You suceeded in 187 turns!
## Congratulations! You suceeded in 57 Optimal-path steps!
## Congratulations! You suceeded in 261 turns!
## Congratulations! You suceeded in 79 Optimal-path steps!
## Congratulations! You suceeded in 305 turns!
## Congratulations! You suceeded in 69 Optimal-path steps!
## Congratulations! You suceeded in 134 turns!
## Congratulations! You suceeded in 50 Optimal-path steps!
## Congratulations! You suceeded in 232 turns!
## Congratulations! You suceeded in 66 Optimal-path steps!
## Congratulations! You suceeded in 161 turns!
## Congratulations! You suceeded in 57 Optimal-path steps!
## Congratulations! You suceeded in 202 turns!
## Congratulations! You suceeded in 61 Optimal-path steps!
## Congratulations! You suceeded in 116 turns!
## Congratulations! You suceeded in 38 Optimal-path steps!
## Congratulations! You suceeded in 216 turns!
## Congratulations! You suceeded in 64 Optimal-path steps!
## Congratulations! You suceeded in 208 turns!
## Congratulations! You suceeded in 63 Optimal-path steps!
## Congratulations! You suceeded in 165 turns!
## Congratulations! You suceeded in 53 Optimal-path steps!
## Congratulations! You suceeded in 260 turns!
## Congratulations! You suceeded in 70 Optimal-path steps!
## Congratulations! You suceeded in 158 turns!
## Congratulations! You suceeded in 52 Optimal-path steps!
## Congratulations! You suceeded in 170 turns!
## Congratulations! You suceeded in 48 Optimal-path steps!
## Congratulations! You suceeded in 163 turns!
## Congratulations! You suceeded in 47 Optimal-path steps!
## Congratulations! You suceeded in 145 turns!
## Congratulations! You suceeded in 49 Optimal-path steps!
## Congratulations! You suceeded in 339 turns!
## Congratulations! You suceeded in 89 Optimal-path steps!
## Congratulations! You suceeded in 250 turns!
## Congratulations! You suceeded in 67 Optimal-path steps!
## Congratulations! You suceeded in 278 turns!
## Congratulations! You suceeded in 71 Optimal-path steps!
## Congratulations! You suceeded in 164 turns!
## Congratulations! You suceeded in 46 Optimal-path steps!
## Congratulations! You suceeded in 210 turns!
## Congratulations! You suceeded in 67 Optimal-path steps!
## Congratulations! You suceeded in 157 turns!
## Congratulations! You suceeded in 52 Optimal-path steps!
## Congratulations! You suceeded in 140 turns!
## Congratulations! You suceeded in 42 Optimal-path steps!
## Congratulations! You suceeded in 183 turns!
## Congratulations! You suceeded in 53 Optimal-path steps!
## Congratulations! You suceeded in 164 turns!
## Congratulations! You suceeded in 51 Optimal-path steps!
## Congratulations! You suceeded in 172 turns!
## Congratulations! You suceeded in 52 Optimal-path steps!
## Congratulations! You suceeded in 224 turns!
## Congratulations! You suceeded in 65 Optimal-path steps!
## Congratulations! You suceeded in 154 turns!
## Congratulations! You suceeded in 52 Optimal-path steps!
## Congratulations! You suceeded in 150 turns!
## Congratulations! You suceeded in 53 Optimal-path steps!
## Congratulations! You suceeded in 218 turns!
## Congratulations! You suceeded in 66 Optimal-path steps!
## Congratulations! You suceeded in 228 turns!
## Congratulations! You suceeded in 73 Optimal-path steps!
## Congratulations! You suceeded in 210 turns!
## Congratulations! You suceeded in 57 Optimal-path steps!
## Congratulations! You suceeded in 176 turns!
## Congratulations! You suceeded in 55 Optimal-path steps!
## Congratulations! You suceeded in 154 turns!
## Congratulations! You suceeded in 52 Optimal-path steps!
## Congratulations! You suceeded in 134 turns!
## Congratulations! You suceeded in 45 Optimal-path steps!
## Congratulations! You suceeded in 137 turns!
## Congratulations! You suceeded in 41 Optimal-path steps!
## Congratulations! You suceeded in 140 turns!
## Congratulations! You suceeded in 44 Optimal-path steps!
## Congratulations! You suceeded in 158 turns!
## Congratulations! You suceeded in 48 Optimal-path steps!
## Congratulations! You suceeded in 276 turns!
## Congratulations! You suceeded in 78 Optimal-path steps!
## Congratulations! You suceeded in 178 turns!
## Congratulations! You suceeded in 54 Optimal-path steps!
## Congratulations! You suceeded in 213 turns!
## Congratulations! You suceeded in 62 Optimal-path steps!
## Congratulations! You suceeded in 262 turns!
## Congratulations! You suceeded in 75 Optimal-path steps!
## Congratulations! You suceeded in 229 turns!
## Congratulations! You suceeded in 69 Optimal-path steps!
## Congratulations! You suceeded in 259 turns!
## Congratulations! You suceeded in 76 Optimal-path steps!
## Congratulations! You suceeded in 228 turns!
## Congratulations! You suceeded in 65 Optimal-path steps!
## Congratulations! You suceeded in 214 turns!
## Congratulations! You suceeded in 65 Optimal-path steps!
## Congratulations! You suceeded in 151 turns!
## Congratulations! You suceeded in 54 Optimal-path steps!
## Congratulations! You suceeded in 262 turns!
## Congratulations! You suceeded in 83 Optimal-path steps!
## Congratulations! You suceeded in 129 turns!
## Congratulations! You suceeded in 43 Optimal-path steps!
## Congratulations! You suceeded in 246 turns!
## Congratulations! You suceeded in 60 Optimal-path steps!
## Congratulations! You suceeded in 157 turns!
## Congratulations! You suceeded in 44 Optimal-path steps!
## Congratulations! You suceeded in 144 turns!
## Congratulations! You suceeded in 48 Optimal-path steps!
## Congratulations! You suceeded in 192 turns!
## Congratulations! You suceeded in 58 Optimal-path steps!
## Congratulations! You suceeded in 380 turns!
## Congratulations! You suceeded in 95 Optimal-path steps!
## Congratulations! You suceeded in 142 turns!
## Congratulations! You suceeded in 46 Optimal-path steps!
## Congratulations! You suceeded in 180 turns!
## Congratulations! You suceeded in 56 Optimal-path steps!
## Congratulations! You suceeded in 159 turns!
## Congratulations! You suceeded in 49 Optimal-path steps!
## Congratulations! You suceeded in 191 turns!
## Congratulations! You suceeded in 64 Optimal-path steps!
## Congratulations! You suceeded in 110 turns!
## Congratulations! You suceeded in 35 Optimal-path steps!
## Congratulations! You suceeded in 246 turns!
## Congratulations! You suceeded in 67 Optimal-path steps!
## Congratulations! You suceeded in 209 turns!
## Congratulations! You suceeded in 56 Optimal-path steps!
## Congratulations! You suceeded in 182 turns!
## Congratulations! You suceeded in 59 Optimal-path steps!
## Congratulations! You suceeded in 208 turns!
## Congratulations! You suceeded in 59 Optimal-path steps!
## Congratulations! You suceeded in 176 turns!
## Congratulations! You suceeded in 55 Optimal-path steps!
## Congratulations! You suceeded in 177 turns!
## Congratulations! You suceeded in 57 Optimal-path steps!
## Congratulations! You suceeded in 159 turns!
## Congratulations! You suceeded in 47 Optimal-path steps!
## Congratulations! You suceeded in 226 turns!
## Congratulations! You suceeded in 57 Optimal-path steps!
## Congratulations! You suceeded in 209 turns!
## Congratulations! You suceeded in 59 Optimal-path steps!
## Congratulations! You suceeded in 135 turns!
## Congratulations! You suceeded in 46 Optimal-path steps!
## Congratulations! You suceeded in 220 turns!
## Congratulations! You suceeded in 64 Optimal-path steps!
## Congratulations! You suceeded in 164 turns!
## Congratulations! You suceeded in 48 Optimal-path steps!
## Congratulations! You suceeded in 254 turns!
## Congratulations! You suceeded in 86 Optimal-path steps!
## Congratulations! You suceeded in 248 turns!
## Congratulations! You suceeded in 66 Optimal-path steps!
## Congratulations! You suceeded in 144 turns!
## Congratulations! You suceeded in 51 Optimal-path steps!
## Congratulations! You suceeded in 163 turns!
## Congratulations! You suceeded in 55 Optimal-path steps!
## Congratulations! You suceeded in 226 turns!
## Congratulations! You suceeded in 69 Optimal-path steps!
## Congratulations! You suceeded in 184 turns!
## Congratulations! You suceeded in 60 Optimal-path steps!
## Congratulations! You suceeded in 170 turns!
## Congratulations! You suceeded in 49 Optimal-path steps!
## Congratulations! You suceeded in 162 turns!
## Congratulations! You suceeded in 53 Optimal-path steps!
## Congratulations! You suceeded in 236 turns!
## Congratulations! You suceeded in 60 Optimal-path steps!
## Congratulations! You suceeded in 153 turns!
## Congratulations! You suceeded in 54 Optimal-path steps!
## Congratulations! You suceeded in 213 turns!
## Congratulations! You suceeded in 65 Optimal-path steps!
## Congratulations! You suceeded in 188 turns!
## Congratulations! You suceeded in 57 Optimal-path steps!
## Congratulations! You suceeded in 141 turns!
## Congratulations! You suceeded in 41 Optimal-path steps!
## Congratulations! You suceeded in 210 turns!
## Congratulations! You suceeded in 61 Optimal-path steps!
## Congratulations! You suceeded in 202 turns!
## Congratulations! You suceeded in 61 Optimal-path steps!
## Congratulations! You suceeded in 327 turns!
## Congratulations! You suceeded in 87 Optimal-path steps!
## Congratulations! You suceeded in 176 turns!
## Congratulations! You suceeded in 53 Optimal-path steps!
## Congratulations! You suceeded in 97 turns!
## Congratulations! You suceeded in 35 Optimal-path steps!
## Congratulations! You suceeded in 204 turns!
## Congratulations! You suceeded in 55 Optimal-path steps!
## Congratulations! You suceeded in 376 turns!
## Congratulations! You suceeded in 79 Optimal-path steps!
## Congratulations! You suceeded in 173 turns!
## Congratulations! You suceeded in 54 Optimal-path steps!
## Congratulations! You suceeded in 202 turns!
## Congratulations! You suceeded in 56 Optimal-path steps!
## Congratulations! You suceeded in 187 turns!
## Congratulations! You suceeded in 59 Optimal-path steps!
## Congratulations! You suceeded in 202 turns!
## Congratulations! You suceeded in 60 Optimal-path steps!
## Congratulations! You suceeded in 234 turns!
## Congratulations! You suceeded in 70 Optimal-path steps!
## Congratulations! You suceeded in 240 turns!
## Congratulations! You suceeded in 76 Optimal-path steps!
## Congratulations! You suceeded in 178 turns!
## Congratulations! You suceeded in 50 Optimal-path steps!
## Congratulations! You suceeded in 129 turns!
## Congratulations! You suceeded in 39 Optimal-path steps!
## Congratulations! You suceeded in 205 turns!
## Congratulations! You suceeded in 64 Optimal-path steps!
## Congratulations! You suceeded in 157 turns!
## Congratulations! You suceeded in 49 Optimal-path steps!
## Congratulations! You suceeded in 208 turns!
## Congratulations! You suceeded in 55 Optimal-path steps!
## Congratulations! You suceeded in 249 turns!
## Congratulations! You suceeded in 72 Optimal-path steps!
## Congratulations! You suceeded in 144 turns!
## Congratulations! You suceeded in 46 Optimal-path steps!
## Congratulations! You suceeded in 260 turns!
## Congratulations! You suceeded in 68 Optimal-path steps!
## Congratulations! You suceeded in 163 turns!
## Congratulations! You suceeded in 53 Optimal-path steps!
## Congratulations! You suceeded in 184 turns!
## Congratulations! You suceeded in 59 Optimal-path steps!
## Congratulations! You suceeded in 163 turns!
## Congratulations! You suceeded in 50 Optimal-path steps!
## Congratulations! You suceeded in 183 turns!
## Congratulations! You suceeded in 58 Optimal-path steps!
## Congratulations! You suceeded in 226 turns!
## Congratulations! You suceeded in 66 Optimal-path steps!
## Congratulations! You suceeded in 156 turns!
## Congratulations! You suceeded in 53 Optimal-path steps!
## Congratulations! You suceeded in 172 turns!
## Congratulations! You suceeded in 60 Optimal-path steps!
## Congratulations! You suceeded in 266 turns!
## Congratulations! You suceeded in 73 Optimal-path steps!
## Congratulations! You suceeded in 73 turns!
## Congratulations! You suceeded in 26 Optimal-path steps!
## Congratulations! You suceeded in 203 turns!
## Congratulations! You suceeded in 59 Optimal-path steps!
## Congratulations! You suceeded in 178 turns!
## Congratulations! You suceeded in 62 Optimal-path steps!
## Congratulations! You suceeded in 164 turns!
## Congratulations! You suceeded in 43 Optimal-path steps!
## Congratulations! You suceeded in 188 turns!
## Congratulations! You suceeded in 63 Optimal-path steps!
## Congratulations! You suceeded in 99 turns!
## Congratulations! You suceeded in 34 Optimal-path steps!
## Congratulations! You suceeded in 186 turns!
## Congratulations! You suceeded in 60 Optimal-path steps!
## Congratulations! You suceeded in 150 turns!
## Congratulations! You suceeded in 53 Optimal-path steps!
## Congratulations! You suceeded in 173 turns!
## Congratulations! You suceeded in 53 Optimal-path steps!
## Congratulations! You suceeded in 170 turns!
## Congratulations! You suceeded in 54 Optimal-path steps!
## Congratulations! You suceeded in 145 turns!
## Congratulations! You suceeded in 44 Optimal-path steps!
## Congratulations! You suceeded in 152 turns!
## Congratulations! You suceeded in 48 Optimal-path steps!
## Congratulations! You suceeded in 243 turns!
## Congratulations! You suceeded in 69 Optimal-path steps!
## Congratulations! You suceeded in 147 turns!
## Congratulations! You suceeded in 46 Optimal-path steps!
## Congratulations! You suceeded in 219 turns!
## Congratulations! You suceeded in 61 Optimal-path steps!
## Congratulations! You suceeded in 201 turns!
## Congratulations! You suceeded in 67 Optimal-path steps!
## Congratulations! You suceeded in 145 turns!
## Congratulations! You suceeded in 49 Optimal-path steps!
## Congratulations! You suceeded in 137 turns!
## Congratulations! You suceeded in 44 Optimal-path steps!
## Congratulations! You suceeded in 200 turns!
## Congratulations! You suceeded in 59 Optimal-path steps!
## Congratulations! You suceeded in 252 turns!
## Congratulations! You suceeded in 69 Optimal-path steps!
## Congratulations! You suceeded in 126 turns!
## Congratulations! You suceeded in 42 Optimal-path steps!
## Congratulations! You suceeded in 139 turns!
## Congratulations! You suceeded in 43 Optimal-path steps!
## Congratulations! You suceeded in 196 turns!
## Congratulations! You suceeded in 56 Optimal-path steps!
## Congratulations! You suceeded in 143 turns!
## Congratulations! You suceeded in 52 Optimal-path steps!
## Congratulations! You suceeded in 199 turns!
## Congratulations! You suceeded in 57 Optimal-path steps!
## Congratulations! You suceeded in 173 turns!
## Congratulations! You suceeded in 52 Optimal-path steps!
## Congratulations! You suceeded in 161 turns!
## Congratulations! You suceeded in 51 Optimal-path steps!
## Congratulations! You suceeded in 179 turns!
## Congratulations! You suceeded in 56 Optimal-path steps!
## Congratulations! You suceeded in 175 turns!
## Congratulations! You suceeded in 54 Optimal-path steps!
## Congratulations! You suceeded in 266 turns!
## Congratulations! You suceeded in 74 Optimal-path steps!
## Congratulations! You suceeded in 228 turns!
## Congratulations! You suceeded in 66 Optimal-path steps!
## Congratulations! You suceeded in 171 turns!
## Congratulations! You suceeded in 53 Optimal-path steps!
## Congratulations! You suceeded in 166 turns!
## Congratulations! You suceeded in 48 Optimal-path steps!
## Congratulations! You suceeded in 171 turns!
## Congratulations! You suceeded in 56 Optimal-path steps!
## Congratulations! You suceeded in 176 turns!
## Congratulations! You suceeded in 52 Optimal-path steps!
## Congratulations! You suceeded in 154 turns!
## Congratulations! You suceeded in 50 Optimal-path steps!
## Congratulations! You suceeded in 205 turns!
## Congratulations! You suceeded in 53 Optimal-path steps!
## Congratulations! You suceeded in 153 turns!
## Congratulations! You suceeded in 49 Optimal-path steps!
## Congratulations! You suceeded in 232 turns!
## Congratulations! You suceeded in 65 Optimal-path steps!
## Congratulations! You suceeded in 172 turns!
## Congratulations! You suceeded in 50 Optimal-path steps!
## Congratulations! You suceeded in 255 turns!
## Congratulations! You suceeded in 71 Optimal-path steps!
## Congratulations! You suceeded in 166 turns!
## Congratulations! You suceeded in 52 Optimal-path steps!
## Congratulations! You suceeded in 163 turns!
## Congratulations! You suceeded in 47 Optimal-path steps!
## Congratulations! You suceeded in 158 turns!
## Congratulations! You suceeded in 49 Optimal-path steps!
## Congratulations! You suceeded in 113 turns!
## Congratulations! You suceeded in 41 Optimal-path steps!
## Congratulations! You suceeded in 202 turns!
## Congratulations! You suceeded in 59 Optimal-path steps!
## Congratulations! You suceeded in 244 turns!
## Congratulations! You suceeded in 69 Optimal-path steps!
## Congratulations! You suceeded in 251 turns!
## Congratulations! You suceeded in 69 Optimal-path steps!
## Congratulations! You suceeded in 135 turns!
## Congratulations! You suceeded in 49 Optimal-path steps!
## Congratulations! You suceeded in 212 turns!
## Congratulations! You suceeded in 59 Optimal-path steps!
## Congratulations! You suceeded in 397 turns!
## Congratulations! You suceeded in 110 Optimal-path steps!
## Congratulations! You suceeded in 174 turns!
## Congratulations! You suceeded in 58 Optimal-path steps!
## Congratulations! You suceeded in 237 turns!
## Congratulations! You suceeded in 64 Optimal-path steps!
## Congratulations! You suceeded in 105 turns!
## Congratulations! You suceeded in 36 Optimal-path steps!
## Congratulations! You suceeded in 180 turns!
## Congratulations! You suceeded in 53 Optimal-path steps!
## Congratulations! You suceeded in 147 turns!
## Congratulations! You suceeded in 50 Optimal-path steps!
## Congratulations! You suceeded in 103 turns!
## Congratulations! You suceeded in 39 Optimal-path steps!
## Congratulations! You suceeded in 154 turns!
## Congratulations! You suceeded in 50 Optimal-path steps!
## Congratulations! You suceeded in 156 turns!
## Congratulations! You suceeded in 47 Optimal-path steps!
## Congratulations! You suceeded in 211 turns!
## Congratulations! You suceeded in 53 Optimal-path steps!
## Congratulations! You suceeded in 168 turns!
## Congratulations! You suceeded in 49 Optimal-path steps!
## Congratulations! You suceeded in 172 turns!
## Congratulations! You suceeded in 55 Optimal-path steps!
## Congratulations! You suceeded in 214 turns!
## Congratulations! You suceeded in 64 Optimal-path steps!
## Congratulations! You suceeded in 111 turns!
## Congratulations! You suceeded in 38 Optimal-path steps!
## Congratulations! You suceeded in 258 turns!
## Congratulations! You suceeded in 78 Optimal-path steps!
## Congratulations! You suceeded in 186 turns!
## Congratulations! You suceeded in 57 Optimal-path steps!
## Congratulations! You suceeded in 174 turns!
## Congratulations! You suceeded in 54 Optimal-path steps!
## Congratulations! You suceeded in 256 turns!
## Congratulations! You suceeded in 65 Optimal-path steps!
## Congratulations! You suceeded in 248 turns!
## Congratulations! You suceeded in 68 Optimal-path steps!
## Congratulations! You suceeded in 233 turns!
## Congratulations! You suceeded in 63 Optimal-path steps!
## Congratulations! You suceeded in 253 turns!
## Congratulations! You suceeded in 69 Optimal-path steps!
## Congratulations! You suceeded in 192 turns!
## Congratulations! You suceeded in 54 Optimal-path steps!
## Congratulations! You suceeded in 218 turns!
## Congratulations! You suceeded in 64 Optimal-path steps!
## Congratulations! You suceeded in 206 turns!
## Congratulations! You suceeded in 59 Optimal-path steps!
## Congratulations! You suceeded in 266 turns!
## Congratulations! You suceeded in 77 Optimal-path steps!
## Congratulations! You suceeded in 226 turns!
## Congratulations! You suceeded in 70 Optimal-path steps!
## Congratulations! You suceeded in 154 turns!
## Congratulations! You suceeded in 45 Optimal-path steps!
## Congratulations! You suceeded in 193 turns!
## Congratulations! You suceeded in 62 Optimal-path steps!
## Congratulations! You suceeded in 252 turns!
## Congratulations! You suceeded in 72 Optimal-path steps!
## Congratulations! You suceeded in 153 turns!
## Congratulations! You suceeded in 53 Optimal-path steps!
## Congratulations! You suceeded in 207 turns!
## Congratulations! You suceeded in 63 Optimal-path steps!
## Congratulations! You suceeded in 240 turns!
## Congratulations! You suceeded in 70 Optimal-path steps!
## Congratulations! You suceeded in 138 turns!
## Congratulations! You suceeded in 42 Optimal-path steps!
## Congratulations! You suceeded in 179 turns!
## Congratulations! You suceeded in 58 Optimal-path steps!
## Congratulations! You suceeded in 233 turns!
## Congratulations! You suceeded in 68 Optimal-path steps!
## Congratulations! You suceeded in 228 turns!
## Congratulations! You suceeded in 65 Optimal-path steps!
## Congratulations! You suceeded in 254 turns!
## Congratulations! You suceeded in 68 Optimal-path steps!
## Congratulations! You suceeded in 156 turns!
## Congratulations! You suceeded in 51 Optimal-path steps!
## Congratulations! You suceeded in 235 turns!
## Congratulations! You suceeded in 67 Optimal-path steps!
## Congratulations! You suceeded in 350 turns!
## Congratulations! You suceeded in 78 Optimal-path steps!
## Congratulations! You suceeded in 269 turns!
## Congratulations! You suceeded in 70 Optimal-path steps!
## Congratulations! You suceeded in 290 turns!
## Congratulations! You suceeded in 74 Optimal-path steps!
## Congratulations! You suceeded in 154 turns!
## Congratulations! You suceeded in 48 Optimal-path steps!
## Congratulations! You suceeded in 146 turns!
## Congratulations! You suceeded in 48 Optimal-path steps!
## Congratulations! You suceeded in 149 turns!
## Congratulations! You suceeded in 46 Optimal-path steps!
## Congratulations! You suceeded in 204 turns!
## Congratulations! You suceeded in 62 Optimal-path steps!
## Congratulations! You suceeded in 189 turns!
## Congratulations! You suceeded in 58 Optimal-path steps!
## Congratulations! You suceeded in 179 turns!
## Congratulations! You suceeded in 57 Optimal-path steps!
## Congratulations! You suceeded in 293 turns!
## Congratulations! You suceeded in 74 Optimal-path steps!
## Congratulations! You suceeded in 175 turns!
## Congratulations! You suceeded in 58 Optimal-path steps!
## Congratulations! You suceeded in 286 turns!
## Congratulations! You suceeded in 70 Optimal-path steps!
## Congratulations! You suceeded in 222 turns!
## Congratulations! You suceeded in 63 Optimal-path steps!
## Congratulations! You suceeded in 175 turns!
## Congratulations! You suceeded in 53 Optimal-path steps!
## Congratulations! You suceeded in 130 turns!
## Congratulations! You suceeded in 45 Optimal-path steps!
## Congratulations! You suceeded in 194 turns!
## Congratulations! You suceeded in 55 Optimal-path steps!
## Congratulations! You suceeded in 303 turns!
## Congratulations! You suceeded in 84 Optimal-path steps!
## Congratulations! You suceeded in 211 turns!
## Congratulations! You suceeded in 65 Optimal-path steps!
## Congratulations! You suceeded in 234 turns!
## Congratulations! You suceeded in 65 Optimal-path steps!
## Congratulations! You suceeded in 137 turns!
## Congratulations! You suceeded in 46 Optimal-path steps!
## Congratulations! You suceeded in 198 turns!
## Congratulations! You suceeded in 59 Optimal-path steps!
## Congratulations! You suceeded in 167 turns!
## Congratulations! You suceeded in 54 Optimal-path steps!
## Congratulations! You suceeded in 191 turns!
## Congratulations! You suceeded in 56 Optimal-path steps!
## Congratulations! You suceeded in 158 turns!
## Congratulations! You suceeded in 47 Optimal-path steps!
## Congratulations! You suceeded in 228 turns!
## Congratulations! You suceeded in 59 Optimal-path steps!
## Congratulations! You suceeded in 142 turns!
## Congratulations! You suceeded in 48 Optimal-path steps!
## Congratulations! You suceeded in 124 turns!
## Congratulations! You suceeded in 43 Optimal-path steps!
## Congratulations! You suceeded in 205 turns!
## Congratulations! You suceeded in 58 Optimal-path steps!
## Congratulations! You suceeded in 225 turns!
## Congratulations! You suceeded in 66 Optimal-path steps!
## Congratulations! You suceeded in 313 turns!
## Congratulations! You suceeded in 78 Optimal-path steps!
## Congratulations! You suceeded in 138 turns!
## Congratulations! You suceeded in 45 Optimal-path steps!
## Congratulations! You suceeded in 209 turns!
## Congratulations! You suceeded in 63 Optimal-path steps!
## Congratulations! You suceeded in 193 turns!
## Congratulations! You suceeded in 58 Optimal-path steps!
## Congratulations! You suceeded in 187 turns!
## Congratulations! You suceeded in 55 Optimal-path steps!
## Congratulations! You suceeded in 192 turns!
## Congratulations! You suceeded in 63 Optimal-path steps!
## Congratulations! You suceeded in 192 turns!
## Congratulations! You suceeded in 60 Optimal-path steps!
## Congratulations! You suceeded in 168 turns!
## Congratulations! You suceeded in 57 Optimal-path steps!
## Congratulations! You suceeded in 226 turns!
## Congratulations! You suceeded in 66 Optimal-path steps!
## Congratulations! You suceeded in 180 turns!
## Congratulations! You suceeded in 51 Optimal-path steps!
## Congratulations! You suceeded in 277 turns!
## Congratulations! You suceeded in 73 Optimal-path steps!
## Congratulations! You suceeded in 205 turns!
## Congratulations! You suceeded in 62 Optimal-path steps!
## Congratulations! You suceeded in 162 turns!
## Congratulations! You suceeded in 58 Optimal-path steps!
## Congratulations! You suceeded in 180 turns!
## Congratulations! You suceeded in 54 Optimal-path steps!
## Congratulations! You suceeded in 162 turns!
## Congratulations! You suceeded in 49 Optimal-path steps!
## Congratulations! You suceeded in 138 turns!
## Congratulations! You suceeded in 40 Optimal-path steps!
## Congratulations! You suceeded in 196 turns!
## Congratulations! You suceeded in 57 Optimal-path steps!
## Congratulations! You suceeded in 183 turns!
## Congratulations! You suceeded in 55 Optimal-path steps!
## Congratulations! You suceeded in 178 turns!
## Congratulations! You suceeded in 55 Optimal-path steps!
## Congratulations! You suceeded in 196 turns!
## Congratulations! You suceeded in 59 Optimal-path steps!
## Congratulations! You suceeded in 205 turns!
## Congratulations! You suceeded in 62 Optimal-path steps!
## Congratulations! You suceeded in 186 turns!
## Congratulations! You suceeded in 57 Optimal-path steps!
## Congratulations! You suceeded in 120 turns!
## Congratulations! You suceeded in 47 Optimal-path steps!
## Congratulations! You suceeded in 142 turns!
## Congratulations! You suceeded in 48 Optimal-path steps!
## Congratulations! You suceeded in 186 turns!
## Congratulations! You suceeded in 57 Optimal-path steps!
## Congratulations! You suceeded in 187 turns!
## Congratulations! You suceeded in 57 Optimal-path steps!
## Congratulations! You suceeded in 232 turns!
## Congratulations! You suceeded in 68 Optimal-path steps!
## Congratulations! You suceeded in 219 turns!
## Congratulations! You suceeded in 65 Optimal-path steps!
## Congratulations! You suceeded in 249 turns!
## Congratulations! You suceeded in 71 Optimal-path steps!
## Congratulations! You suceeded in 145 turns!
## Congratulations! You suceeded in 50 Optimal-path steps!
## Congratulations! You suceeded in 163 turns!
## Congratulations! You suceeded in 46 Optimal-path steps!
## Congratulations! You suceeded in 186 turns!
## Congratulations! You suceeded in 59 Optimal-path steps!
## Congratulations! You suceeded in 239 turns!
## Congratulations! You suceeded in 73 Optimal-path steps!
## Congratulations! You suceeded in 197 turns!
## Congratulations! You suceeded in 64 Optimal-path steps!
## Congratulations! You suceeded in 239 turns!
## Congratulations! You suceeded in 64 Optimal-path steps!
## Congratulations! You suceeded in 173 turns!
## Congratulations! You suceeded in 58 Optimal-path steps!
## Congratulations! You suceeded in 195 turns!
## Congratulations! You suceeded in 56 Optimal-path steps!
## Congratulations! You suceeded in 186 turns!
## Congratulations! You suceeded in 59 Optimal-path steps!
## Congratulations! You suceeded in 188 turns!
## Congratulations! You suceeded in 55 Optimal-path steps!
## Congratulations! You suceeded in 199 turns!
## Congratulations! You suceeded in 62 Optimal-path steps!
## Congratulations! You suceeded in 216 turns!
## Congratulations! You suceeded in 65 Optimal-path steps!
## Congratulations! You suceeded in 253 turns!
## Congratulations! You suceeded in 72 Optimal-path steps!
## Congratulations! You suceeded in 119 turns!
## Congratulations! You suceeded in 38 Optimal-path steps!
## Congratulations! You suceeded in 166 turns!
## Congratulations! You suceeded in 45 Optimal-path steps!
## Congratulations! You suceeded in 129 turns!
## Congratulations! You suceeded in 38 Optimal-path steps!
## Congratulations! You suceeded in 140 turns!
## Congratulations! You suceeded in 46 Optimal-path steps!
## Congratulations! You suceeded in 173 turns!
## Congratulations! You suceeded in 55 Optimal-path steps!
## Congratulations! You suceeded in 149 turns!
## Congratulations! You suceeded in 46 Optimal-path steps!
## Congratulations! You suceeded in 151 turns!
## Congratulations! You suceeded in 48 Optimal-path steps!
## Congratulations! You suceeded in 188 turns!
## Congratulations! You suceeded in 53 Optimal-path steps!
## Congratulations! You suceeded in 226 turns!
## Congratulations! You suceeded in 62 Optimal-path steps!
## Congratulations! You suceeded in 189 turns!
## Congratulations! You suceeded in 58 Optimal-path steps!
## Congratulations! You suceeded in 141 turns!
## Congratulations! You suceeded in 46 Optimal-path steps!
## Congratulations! You suceeded in 247 turns!
## Congratulations! You suceeded in 69 Optimal-path steps!
## Congratulations! You suceeded in 214 turns!
## Congratulations! You suceeded in 65 Optimal-path steps!
## Congratulations! You suceeded in 127 turns!
## Congratulations! You suceeded in 38 Optimal-path steps!
## Congratulations! You suceeded in 210 turns!
## Congratulations! You suceeded in 61 Optimal-path steps!
## Congratulations! You suceeded in 178 turns!
## Congratulations! You suceeded in 55 Optimal-path steps!
## Congratulations! You suceeded in 141 turns!
## Congratulations! You suceeded in 48 Optimal-path steps!
## Congratulations! You suceeded in 209 turns!
## Congratulations! You suceeded in 57 Optimal-path steps!
## Congratulations! You suceeded in 181 turns!
## Congratulations! You suceeded in 50 Optimal-path steps!
## Congratulations! You suceeded in 158 turns!
## Congratulations! You suceeded in 44 Optimal-path steps!
## Congratulations! You suceeded in 193 turns!
## Congratulations! You suceeded in 55 Optimal-path steps!
## Congratulations! You suceeded in 132 turns!
## Congratulations! You suceeded in 43 Optimal-path steps!
## Congratulations! You suceeded in 226 turns!
## Congratulations! You suceeded in 69 Optimal-path steps!
## Congratulations! You suceeded in 165 turns!
## Congratulations! You suceeded in 40 Optimal-path steps!
## Congratulations! You suceeded in 149 turns!
## Congratulations! You suceeded in 46 Optimal-path steps!
## Congratulations! You suceeded in 148 turns!
## Congratulations! You suceeded in 48 Optimal-path steps!
## Congratulations! You suceeded in 127 turns!
## Congratulations! You suceeded in 45 Optimal-path steps!
## Congratulations! You suceeded in 167 turns!
## Congratulations! You suceeded in 48 Optimal-path steps!
## Congratulations! You suceeded in 204 turns!
## Congratulations! You suceeded in 56 Optimal-path steps!
## Congratulations! You suceeded in 187 turns!
## Congratulations! You suceeded in 53 Optimal-path steps!
## Congratulations! You suceeded in 223 turns!
## Congratulations! You suceeded in 65 Optimal-path steps!
## Congratulations! You suceeded in 232 turns!
## Congratulations! You suceeded in 66 Optimal-path steps!
## Congratulations! You suceeded in 164 turns!
## Congratulations! You suceeded in 49 Optimal-path steps!

mean(run_500_output_updated[,"turns"])

## [1] 189.506

mean(run_500_output_updated[,"steps"])

## [1] 56.626

scatter.smooth(run_500_output_updated)

hist(run_500_output_updated[,"turns"])

hist(run_500_output_updated[,"steps"])

summary(run_500_output_updated)

##      turns           steps       
##  Min.   : 73.0   Min.   : 26.00  
##  1st Qu.:155.0   1st Qu.: 48.75  
##  Median :181.0   Median : 55.50  
##  Mean   :189.5   Mean   : 56.63  
##  3rd Qu.:220.0   3rd Qu.: 64.00  
##  Max.   :397.0   Max.   :110.00

8 The following results are based on set.seed(1234)

library(BSDA)
sd_turns = sd(run_500_output_updated[,"turns"])
sd_steps = sd(run_500_output_updated[,"steps"])

8.1 Z-test for no. of turns

BSDA::z.test(run_500_output_updated[,"turns"], sigma.x = sd_turns , conf.level = 0.95)

## 
##  One-sample z-Test
## 
## data:  run_500_output_updated[, "turns"]
## z = 88.242, p-value < 2.2e-16
## alternative hypothesis: true mean is not equal to 0
## 95 percent confidence interval:
##  185.2969 193.7151
## sample estimates:
## mean of x 
##   189.506

8.2 Z-test for no. of steps

BSDA::z.test(run_500_output_updated[,"steps"], sigma.x = sd_steps , conf.level = 0.95)

## 
##  One-sample z-Test
## 
## data:  run_500_output_updated[, "steps"]
## z = 114.11, p-value < 2.2e-16
## alternative hypothesis: true mean is not equal to 0
## 95 percent confidence interval:
##  55.65338 57.59862
## sample estimates:
## mean of x 
##    56.626

9 Conclusion :

After runing 500 times with my A star search alorgithm, it found that
- the mean of optimal numbers of turns is 189.5 with 95% confident interval (185.2969 , 193.7151)
- the mean of optimal numbers of steps is 56.6 with 95% confident interval (55.65338 , 57.59862)

10 References:

Minieka (1989)
Chang, Chung, and Lin (2012)

Chang, Ronald Y., Wei-Ho Chung, and Sian-Jheng Lin. 2012. “A* Algorithm Inspired Memory-Efficient Detection for Mimo Systems.” IEEE WIRELESS COMMUNICATIONS LETTERS. https://ezp.sub.su.se/login?url=http://search.ebscohost.com/login.aspx?direct=true&db=edswsc&AN=000209696300026&site=eds-live&scope=site.

Minieka, Edward. 1989. “The Delivery Man Problem on a Tree Network.” Annals of Operations Research 18 (1): 261–66. https://doi.org/10.1007/bf02097807.

Written by DK WC

2019-10-04