1# Source: https://github.com/python/pyperformance
2# License: MIT
3
4# Solver of Hexiom board game.
5# Benchmark from Laurent Vaucher.
6# Source: https://github.com/slowfrog/hexiom : hexiom2.py, level36.txt
7# (Main function tweaked by Armin Rigo.)
8
9
10##################################
11class Dir(object):
12    def __init__(self, x, y):
13        self.x = x
14        self.y = y
15
16
17DIRS = [Dir(1, 0), Dir(-1, 0), Dir(0, 1), Dir(0, -1), Dir(1, 1), Dir(-1, -1)]
18
19EMPTY = 7
20
21##################################
22
23
24class Done(object):
25    MIN_CHOICE_STRATEGY = 0
26    MAX_CHOICE_STRATEGY = 1
27    HIGHEST_VALUE_STRATEGY = 2
28    FIRST_STRATEGY = 3
29    MAX_NEIGHBORS_STRATEGY = 4
30    MIN_NEIGHBORS_STRATEGY = 5
31
32    def __init__(self, count, empty=False):
33        self.count = count
34        self.cells = None if empty else [[0, 1, 2, 3, 4, 5, 6, EMPTY] for i in range(count)]
35
36    def clone(self):
37        ret = Done(self.count, True)
38        ret.cells = [self.cells[i][:] for i in range(self.count)]
39        return ret
40
41    def __getitem__(self, i):
42        return self.cells[i]
43
44    def set_done(self, i, v):
45        self.cells[i] = [v]
46
47    def already_done(self, i):
48        return len(self.cells[i]) == 1
49
50    def remove(self, i, v):
51        if v in self.cells[i]:
52            self.cells[i].remove(v)
53            return True
54        else:
55            return False
56
57    def remove_all(self, v):
58        for i in range(self.count):
59            self.remove(i, v)
60
61    def remove_unfixed(self, v):
62        changed = False
63        for i in range(self.count):
64            if not self.already_done(i):
65                if self.remove(i, v):
66                    changed = True
67        return changed
68
69    def filter_tiles(self, tiles):
70        for v in range(8):
71            if tiles[v] == 0:
72                self.remove_all(v)
73
74    def next_cell_min_choice(self):
75        minlen = 10
76        mini = -1
77        for i in range(self.count):
78            if 1 < len(self.cells[i]) < minlen:
79                minlen = len(self.cells[i])
80                mini = i
81        return mini
82
83    def next_cell_max_choice(self):
84        maxlen = 1
85        maxi = -1
86        for i in range(self.count):
87            if maxlen < len(self.cells[i]):
88                maxlen = len(self.cells[i])
89                maxi = i
90        return maxi
91
92    def next_cell_highest_value(self):
93        maxval = -1
94        maxi = -1
95        for i in range(self.count):
96            if not self.already_done(i):
97                maxvali = max(k for k in self.cells[i] if k != EMPTY)
98                if maxval < maxvali:
99                    maxval = maxvali
100                    maxi = i
101        return maxi
102
103    def next_cell_first(self):
104        for i in range(self.count):
105            if not self.already_done(i):
106                return i
107        return -1
108
109    def next_cell_max_neighbors(self, pos):
110        maxn = -1
111        maxi = -1
112        for i in range(self.count):
113            if not self.already_done(i):
114                cells_around = pos.hex.get_by_id(i).links
115                n = sum(
116                    1 if (self.already_done(nid) and (self[nid][0] != EMPTY)) else 0
117                    for nid in cells_around
118                )
119                if n > maxn:
120                    maxn = n
121                    maxi = i
122        return maxi
123
124    def next_cell_min_neighbors(self, pos):
125        minn = 7
126        mini = -1
127        for i in range(self.count):
128            if not self.already_done(i):
129                cells_around = pos.hex.get_by_id(i).links
130                n = sum(
131                    1 if (self.already_done(nid) and (self[nid][0] != EMPTY)) else 0
132                    for nid in cells_around
133                )
134                if n < minn:
135                    minn = n
136                    mini = i
137        return mini
138
139    def next_cell(self, pos, strategy=HIGHEST_VALUE_STRATEGY):
140        if strategy == Done.HIGHEST_VALUE_STRATEGY:
141            return self.next_cell_highest_value()
142        elif strategy == Done.MIN_CHOICE_STRATEGY:
143            return self.next_cell_min_choice()
144        elif strategy == Done.MAX_CHOICE_STRATEGY:
145            return self.next_cell_max_choice()
146        elif strategy == Done.FIRST_STRATEGY:
147            return self.next_cell_first()
148        elif strategy == Done.MAX_NEIGHBORS_STRATEGY:
149            return self.next_cell_max_neighbors(pos)
150        elif strategy == Done.MIN_NEIGHBORS_STRATEGY:
151            return self.next_cell_min_neighbors(pos)
152        else:
153            raise Exception("Wrong strategy: %d" % strategy)
154
155
156##################################
157
158
159class Node(object):
160    def __init__(self, pos, id, links):
161        self.pos = pos
162        self.id = id
163        self.links = links
164
165
166##################################
167
168
169class Hex(object):
170    def __init__(self, size):
171        self.size = size
172        self.count = 3 * size * (size - 1) + 1
173        self.nodes_by_id = self.count * [None]
174        self.nodes_by_pos = {}
175        id = 0
176        for y in range(size):
177            for x in range(size + y):
178                pos = (x, y)
179                node = Node(pos, id, [])
180                self.nodes_by_pos[pos] = node
181                self.nodes_by_id[node.id] = node
182                id += 1
183        for y in range(1, size):
184            for x in range(y, size * 2 - 1):
185                ry = size + y - 1
186                pos = (x, ry)
187                node = Node(pos, id, [])
188                self.nodes_by_pos[pos] = node
189                self.nodes_by_id[node.id] = node
190                id += 1
191
192    def link_nodes(self):
193        for node in self.nodes_by_id:
194            (x, y) = node.pos
195            for dir in DIRS:
196                nx = x + dir.x
197                ny = y + dir.y
198                if self.contains_pos((nx, ny)):
199                    node.links.append(self.nodes_by_pos[(nx, ny)].id)
200
201    def contains_pos(self, pos):
202        return pos in self.nodes_by_pos
203
204    def get_by_pos(self, pos):
205        return self.nodes_by_pos[pos]
206
207    def get_by_id(self, id):
208        return self.nodes_by_id[id]
209
210
211##################################
212class Pos(object):
213    def __init__(self, hex, tiles, done=None):
214        self.hex = hex
215        self.tiles = tiles
216        self.done = Done(hex.count) if done is None else done
217
218    def clone(self):
219        return Pos(self.hex, self.tiles, self.done.clone())
220
221
222##################################
223
224
225def constraint_pass(pos, last_move=None):
226    changed = False
227    left = pos.tiles[:]
228    done = pos.done
229
230    # Remove impossible values from free cells
231    free_cells = range(done.count) if last_move is None else pos.hex.get_by_id(last_move).links
232    for i in free_cells:
233        if not done.already_done(i):
234            vmax = 0
235            vmin = 0
236            cells_around = pos.hex.get_by_id(i).links
237            for nid in cells_around:
238                if done.already_done(nid):
239                    if done[nid][0] != EMPTY:
240                        vmin += 1
241                        vmax += 1
242                else:
243                    vmax += 1
244
245            for num in range(7):
246                if (num < vmin) or (num > vmax):
247                    if done.remove(i, num):
248                        changed = True
249
250    # Computes how many of each value is still free
251    for cell in done.cells:
252        if len(cell) == 1:
253            left[cell[0]] -= 1
254
255    for v in range(8):
256        # If there is none, remove the possibility from all tiles
257        if (pos.tiles[v] > 0) and (left[v] == 0):
258            if done.remove_unfixed(v):
259                changed = True
260        else:
261            possible = sum((1 if v in cell else 0) for cell in done.cells)
262            # If the number of possible cells for a value is exactly the number of available tiles
263            # put a tile in each cell
264            if pos.tiles[v] == possible:
265                for i in range(done.count):
266                    cell = done.cells[i]
267                    if (not done.already_done(i)) and (v in cell):
268                        done.set_done(i, v)
269                        changed = True
270
271    # Force empty or non-empty around filled cells
272    filled_cells = range(done.count) if last_move is None else [last_move]
273    for i in filled_cells:
274        if done.already_done(i):
275            num = done[i][0]
276            empties = 0
277            filled = 0
278            unknown = []
279            cells_around = pos.hex.get_by_id(i).links
280            for nid in cells_around:
281                if done.already_done(nid):
282                    if done[nid][0] == EMPTY:
283                        empties += 1
284                    else:
285                        filled += 1
286                else:
287                    unknown.append(nid)
288            if len(unknown) > 0:
289                if num == filled:
290                    for u in unknown:
291                        if EMPTY in done[u]:
292                            done.set_done(u, EMPTY)
293                            changed = True
294                        # else:
295                        #    raise Exception("Houston, we've got a problem")
296                elif num == filled + len(unknown):
297                    for u in unknown:
298                        if done.remove(u, EMPTY):
299                            changed = True
300
301    return changed
302
303
304ASCENDING = 1
305DESCENDING = -1
306
307
308def find_moves(pos, strategy, order):
309    done = pos.done
310    cell_id = done.next_cell(pos, strategy)
311    if cell_id < 0:
312        return []
313
314    if order == ASCENDING:
315        return [(cell_id, v) for v in done[cell_id]]
316    else:
317        # Try higher values first and EMPTY last
318        moves = list(reversed([(cell_id, v) for v in done[cell_id] if v != EMPTY]))
319        if EMPTY in done[cell_id]:
320            moves.append((cell_id, EMPTY))
321        return moves
322
323
324def play_move(pos, move):
325    (cell_id, i) = move
326    pos.done.set_done(cell_id, i)
327
328
329def print_pos(pos, output):
330    hex = pos.hex
331    done = pos.done
332    size = hex.size
333    for y in range(size):
334        print(" " * (size - y - 1), end="", file=output)
335        for x in range(size + y):
336            pos2 = (x, y)
337            id = hex.get_by_pos(pos2).id
338            if done.already_done(id):
339                c = done[id][0] if done[id][0] != EMPTY else "."
340            else:
341                c = "?"
342            print("%s " % c, end="", file=output)
343        print(end="\n", file=output)
344    for y in range(1, size):
345        print(" " * y, end="", file=output)
346        for x in range(y, size * 2 - 1):
347            ry = size + y - 1
348            pos2 = (x, ry)
349            id = hex.get_by_pos(pos2).id
350            if done.already_done(id):
351                c = done[id][0] if done[id][0] != EMPTY else "."
352            else:
353                c = "?"
354            print("%s " % c, end="", file=output)
355        print(end="\n", file=output)
356
357
358OPEN = 0
359SOLVED = 1
360IMPOSSIBLE = -1
361
362
363def solved(pos, output, verbose=False):
364    hex = pos.hex
365    tiles = pos.tiles[:]
366    done = pos.done
367    exact = True
368    all_done = True
369    for i in range(hex.count):
370        if len(done[i]) == 0:
371            return IMPOSSIBLE
372        elif done.already_done(i):
373            num = done[i][0]
374            tiles[num] -= 1
375            if tiles[num] < 0:
376                return IMPOSSIBLE
377            vmax = 0
378            vmin = 0
379            if num != EMPTY:
380                cells_around = hex.get_by_id(i).links
381                for nid in cells_around:
382                    if done.already_done(nid):
383                        if done[nid][0] != EMPTY:
384                            vmin += 1
385                            vmax += 1
386                    else:
387                        vmax += 1
388
389                if (num < vmin) or (num > vmax):
390                    return IMPOSSIBLE
391                if num != vmin:
392                    exact = False
393        else:
394            all_done = False
395
396    if (not all_done) or (not exact):
397        return OPEN
398
399    print_pos(pos, output)
400    return SOLVED
401
402
403def solve_step(prev, strategy, order, output, first=False):
404    if first:
405        pos = prev.clone()
406        while constraint_pass(pos):
407            pass
408    else:
409        pos = prev
410
411    moves = find_moves(pos, strategy, order)
412    if len(moves) == 0:
413        return solved(pos, output)
414    else:
415        for move in moves:
416            # print("Trying (%d, %d)" % (move[0], move[1]))
417            ret = OPEN
418            new_pos = pos.clone()
419            play_move(new_pos, move)
420            # print_pos(new_pos)
421            while constraint_pass(new_pos, move[0]):
422                pass
423            cur_status = solved(new_pos, output)
424            if cur_status != OPEN:
425                ret = cur_status
426            else:
427                ret = solve_step(new_pos, strategy, order, output)
428            if ret == SOLVED:
429                return SOLVED
430    return IMPOSSIBLE
431
432
433def check_valid(pos):
434    hex = pos.hex
435    tiles = pos.tiles
436    # fill missing entries in tiles
437    tot = 0
438    for i in range(8):
439        if tiles[i] > 0:
440            tot += tiles[i]
441        else:
442            tiles[i] = 0
443    # check total
444    if tot != hex.count:
445        raise Exception("Invalid input. Expected %d tiles, got %d." % (hex.count, tot))
446
447
448def solve(pos, strategy, order, output):
449    check_valid(pos)
450    return solve_step(pos, strategy, order, output, first=True)
451
452
453# TODO Write an 'iterator' to go over all x,y positions
454
455
456def read_file(file):
457    lines = [line.strip("\r\n") for line in file.splitlines()]
458    size = int(lines[0])
459    hex = Hex(size)
460    linei = 1
461    tiles = 8 * [0]
462    done = Done(hex.count)
463    for y in range(size):
464        line = lines[linei][size - y - 1 :]
465        p = 0
466        for x in range(size + y):
467            tile = line[p : p + 2]
468            p += 2
469            if tile[1] == ".":
470                inctile = EMPTY
471            else:
472                inctile = int(tile)
473            tiles[inctile] += 1
474            # Look for locked tiles
475            if tile[0] == "+":
476                # print("Adding locked tile: %d at pos %d, %d, id=%d" %
477                #      (inctile, x, y, hex.get_by_pos((x, y)).id))
478                done.set_done(hex.get_by_pos((x, y)).id, inctile)
479
480        linei += 1
481    for y in range(1, size):
482        ry = size - 1 + y
483        line = lines[linei][y:]
484        p = 0
485        for x in range(y, size * 2 - 1):
486            tile = line[p : p + 2]
487            p += 2
488            if tile[1] == ".":
489                inctile = EMPTY
490            else:
491                inctile = int(tile)
492            tiles[inctile] += 1
493            # Look for locked tiles
494            if tile[0] == "+":
495                # print("Adding locked tile: %d at pos %d, %d, id=%d" %
496                #      (inctile, x, ry, hex.get_by_pos((x, ry)).id))
497                done.set_done(hex.get_by_pos((x, ry)).id, inctile)
498        linei += 1
499    hex.link_nodes()
500    done.filter_tiles(tiles)
501    return Pos(hex, tiles, done)
502
503
504def solve_file(file, strategy, order, output):
505    pos = read_file(file)
506    solve(pos, strategy, order, output)
507
508
509LEVELS = {}
510
511LEVELS[2] = (
512    """
5132
514  . 1
515 . 1 1
516  1 .
517""",
518    """\
519 1 1
520. . .
521 1 1
522""",
523)
524
525LEVELS[10] = (
526    """
5273
528  +.+. .
529 +. 0 . 2
530 . 1+2 1 .
531  2 . 0+.
532   .+.+.
533""",
534    """\
535  . . 1
536 . 1 . 2
5370 . 2 2 .
538 . . . .
539  0 . .
540""",
541)
542
543LEVELS[20] = (
544    """
5453
546   . 5 4
547  . 2+.+1
548 . 3+2 3 .
549 +2+. 5 .
550   . 3 .
551""",
552    """\
553  3 3 2
554 4 5 . 1
5553 5 2 . .
556 2 . . .
557  . . .
558""",
559)
560
561LEVELS[25] = (
562    """
5633
564   4 . .
565  . . 2 .
566 4 3 2 . 4
567  2 2 3 .
568   4 2 4
569""",
570    """\
571  3 4 2
572 2 4 4 .
573. . . 4 2
574 . 2 4 3
575  . 2 .
576""",
577)
578
579LEVELS[30] = (
580    """
5814
582    5 5 . .
583   3 . 2+2 6
584  3 . 2 . 5 .
585 . 3 3+4 4 . 3
586  4 5 4 . 5 4
587   5+2 . . 3
588    4 . . .
589""",
590    """\
591   3 4 3 .
592  4 6 5 2 .
593 2 5 5 . . 2
594. . 5 4 . 4 3
595 . 3 5 4 5 4
596  . 2 . 3 3
597   . . . .
598""",
599)
600
601LEVELS[36] = (
602    """
6034
604    2 1 1 2
605   3 3 3 . .
606  2 3 3 . 4 .
607 . 2 . 2 4 3 2
608  2 2 . . . 2
609   4 3 4 . .
610    3 2 3 3
611""",
612    """\
613   3 4 3 2
614  3 4 4 . 3
615 2 . . 3 4 3
6162 . 1 . 3 . 2
617 3 3 . 2 . 2
618  3 . 2 . 2
619   2 2 . 1
620""",
621)
622
623
624###########################################################################
625# Benchmark interface
626
627bm_params = {
628    (100, 100): (1, 10, DESCENDING, Done.FIRST_STRATEGY),
629    (1000, 1000): (1, 25, DESCENDING, Done.FIRST_STRATEGY),
630    (5000, 1000): (10, 25, DESCENDING, Done.FIRST_STRATEGY),
631}
632
633
634def bm_setup(params):
635    try:
636        import uio as io
637    except ImportError:
638        import io
639
640    loops, level, order, strategy = params
641
642    board, solution = LEVELS[level]
643    board = board.strip()
644    expected = solution.rstrip()
645    output = None
646
647    def run():
648        nonlocal output
649        for _ in range(loops):
650            stream = io.StringIO()
651            solve_file(board, strategy, order, stream)
652            output = stream.getvalue()
653            stream = None
654
655    def result():
656        norm = params[0] * params[1]
657        out = "\n".join(line.rstrip() for line in output.splitlines())
658        return norm, ((out == expected), out)
659
660    return run, result
661