-
Notifications
You must be signed in to change notification settings - Fork 0
/
puzzle_cfg.nim
165 lines (146 loc) · 5.1 KB
/
puzzle_cfg.nim
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
{.hint[XDeclaredButNotUsed]: off.}
type
Bounds* = tuple
md: int # Manhattan distance
ic: range[-1..high(int)] # inversion count; divide by rows or cols to get lower bound on moves
id: int # inversion distance
Config* = tuple
blank_row: Row
blank_col: Col
blank_index: Index
tiles: array[0 .. +last_index, Tile]
h_bounds: Bounds
v_bounds: Bounds
name: string
# Conversion to string
proc `*`*(s: string, count: int): string {.noSideEffect.} =
result = ""
for i in 1..count:
result.add(s)
proc `$`*(bounds: Bounds): string {.noSideEffect.} =
result = "md:" & strutils.align($bounds.md, 3) &
"; id:" & strutils.align($bounds.id, 3) &
" (" & strutils.align($bounds.ic, 3) & ")"
proc bound*(config: Config): int
proc `$`*(config: Config): string =
result = "┌" & ("──┬" * (cols - 1)) & "──┐ '" & config.name & "'\n"
var index = Index(0)
for row in all_rows():
result.add("│")
for col in all_cols():
result.add($(config.tiles[int(index)]))
result.add("│")
index.inc
if row == Row(0):
result.add(" horiz. ")
result.add($config.h_bounds)
if row < last_row:
result = result & "\n├" & ("──┼" * (cols - 1)) & "──┤"
if row == Row(0):
result.add(" vert. ")
result.add($config.v_bounds)
result.add("\n")
else:
result = result & "\n└" & ("──┴" * (cols - 1)) & "──┘ " & $(bound(config)) & "\n"
# Initialisation
proc init_md*(config: var Config) {.noSideEffect.} =
config.h_bounds.md = 0
config.v_bounds.md = 0
for index in 0 .. +last_index:
let tile = config.tiles[index]
if is_empty_tile(tile):
continue
config.h_bounds.md.inc abs(+homeCol(tile) - +toCol(Index(index)))
config.v_bounds.md.inc abs(+homeRow(tile) - +toRow(Index(index)))
proc init_id*(config: var Config) =
config.h_bounds.ic = 0
config.v_bounds.ic = 0
when use_id:
for i in 0 .. +last_index:
if i == +config.blank_index:
continue
for j in i+1 .. +last_index:
if j == +config.blank_index:
continue
if config.tiles[i] > config.tiles[j]:
config.v_bounds.ic.inc
if Index(j) >. Index(i) and config.tiles[i] >. config.tiles[j]:
config.h_bounds.ic.inc
if Index(j) <. Index(i) and config.tiles[i] <. config.tiles[j]:
config.h_bounds.ic.inc
config.v_bounds.id = (config.v_bounds.ic + rows - 2) div (rows - 1)
config.h_bounds.id = (config.h_bounds.ic + cols - 2) div (cols - 1)
proc init_sorted*(config: var Config) =
config.blank_row = Row(0)
config.blank_col = Col(0)
config.blank_index = Index(0)
for index in 0 .. +last_index:
config.tiles[index] = Tile(loc_list[index])
config.name = "sorted"
proc random_inclusive(a, b: int): int =
return a + math.random(b+1-a)
proc init_random*(config: var Config, name = "random", blank_in_home_position = false) =
init_sorted(config)
config.name = name
for i in countdown(+last_index, 1):
let j = random_inclusive(1, i)
if i != j:
swap(config.tiles[i], config.tiles[j])
config.blank_row = Row(0)
config.blank_col = Col(0)
config.blank_index = Index(0)
init_id(config)
if config.v_bounds.ic mod 2 == 1:
swap(config.tiles[1], config.tiles[2])
if not blank_in_home_position:
let blank = config.tiles[0]
let new_blank_index = Index(random_inclusive(0, +last_index))
var i = Index(0)
for j in canonical_path(Index(0), new_blank_index):
config.tiles[int(i)] = config.tiles[int(j)]
i = j
config.tiles[int(new_blank_index)] = blank
config.blank_row = toRow(new_blank_index)
config.blank_col = toCol(new_blank_index)
config.blank_index = new_blank_index
# Checking and computing bounds
proc is_solved(config: var Config): bool =
return config.h_bounds.md == 0 and config.v_bounds.md == 0
proc bound_md(config: Config): int =
return config.h_bounds.md + config.v_bounds.md
proc bound_md_id(config: Config): int =
var h_max = config.h_bounds.md
var v_max = config.v_bounds.md
if (config.h_bounds.id > h_max):
h_max = config.h_bounds.id
if (config.v_bounds.id > v_max):
v_max = config.v_bounds.id
h_max = h_max + ((h_max - config.h_bounds.md) and 1)
v_max = v_max + ((v_max - config.v_bounds.md) and 1)
return h_max + v_max
# Input/output
proc my_parse_int(s:string, number: var int, start: int): int =
var i = start
while s[i] == ' ':
i.inc
i = i + 1 + s.parse_int(number, i)
while s[i-1] == ',':
var number2: int
i = i + 1 + s.parse_int(number2, i)
number = number*1000 + number2
return i - 1 - start
proc read*(config: var Config, line: string) =
var
i = 0
t: int
for index in all_indices():
i = i + 1 + line.my_parse_int(t, i)
config.tiles[+index] = Tile(loc_list[t])
if t == 0:
config.blank_row = to_row(index)
config.blank_col = to_col(index)
config.blank_index = index
i = i + 1 + line.my_parse_int(t, i)
i = i + 1 + line.my_parse_int(t, i)
i = i + 1 + line.my_parse_int(t, i)
config.name = line[i .. line.high]