63 lines
2.1 KiB
Python
Executable File
63 lines
2.1 KiB
Python
Executable File
#!/usr/bin/env python3
|
|
|
|
import math
|
|
import config
|
|
|
|
def hamming_distance(grid):
|
|
h = 0
|
|
for i, v in enumerate(grid):
|
|
if i != config.goal.index(v):
|
|
h += 1
|
|
return h
|
|
|
|
def manhattan_distance(grid):
|
|
h = 0
|
|
size = int(math.sqrt(len(grid)))
|
|
for i, v in enumerate(grid):
|
|
if i != config.goal.index(v):
|
|
curr_col = i % size
|
|
curr_row = i // size
|
|
target_col = (config.goal.index(v)) % size
|
|
target_row = (config.goal.index(v)) // size
|
|
h += abs(target_col - curr_col) + abs(target_row - curr_row)
|
|
return h
|
|
|
|
def linear_conflict_manhattan_distance(grid):
|
|
h = manhattan_distance(grid)
|
|
size = int(math.sqrt(len(grid)))
|
|
for i, v in enumerate(grid):
|
|
if i != config.goal.index(v):
|
|
curr_col = i % size
|
|
curr_row = i // size
|
|
target_col = (config.goal.index(v)) % size
|
|
target_row = (config.goal.index(v)) // size
|
|
#move left
|
|
if target_col - curr_col > 0:
|
|
while (curr_col < target_col):
|
|
i += 1
|
|
curr_col = i % size
|
|
if (grid[v] - 1) // size == target_row:
|
|
h += 1
|
|
#move right
|
|
elif target_col - curr_col < 0:
|
|
while (curr_col > target_col):
|
|
i -= 1
|
|
curr_col = i % size
|
|
if (grid[v] - 1) // size == target_row:
|
|
h += 1
|
|
#move up
|
|
if target_row - curr_row > 0:
|
|
while (curr_row < target_row):
|
|
i += 3
|
|
curr_row = i // size
|
|
if (grid[i] - 1) % size == target_col:
|
|
h += 1
|
|
#move down
|
|
elif target_row - curr_row < 0:
|
|
while (curr_row > target_row):
|
|
i -= 3
|
|
curr_row = i // size
|
|
if (grid[i] - 1) % size == target_col:
|
|
h += 1
|
|
return h
|