#!/usr/bin/python
# -*- coding: utf-8 -*-

# Copyright (C) 2016 Rod Engerstad

import random
from random import randint

import Tkinter as tk
from pzl_lib import PzlG
from pzl_lib import SettingsB
from pzl_lib import Preferences
from pzl_lib import MenuItem
from pzl_lib import Flasher
from pzl_lib import ViewB
from follow_123_data import ModelData


class Sgg(object):
    SQUARE = 4
    OCTAGONAL = 8
    SOLVE = 0
    HINT = 1
    GIVE_HINT = 0
    APPLY_HINT = 1
    ADD = 1
    DELETE = 0
    SET_GUESS = 2
    width = None
    height = None
    shape = None


class Settings(SettingsB):

    def __init__(self):
        SettingsB.__init__(self)
        self.dic = {}
        self.dic['font_size'] = '8'
        self.menu_items = []
        self.preferences = Preferences(self.dic)
        self.preferences.load()
        self.load_menus()
        self.count = len(self.menu_items)
        self.set_fonts()
        self.make_help()
        self.make_tooltip()

    def make_help(self):
        self.help_text = _("There are two sets of puzzles: one of size 8x8 with clues labelled 1,2,3; and the other of size 6x6 with clues labelled 1,2,3,4. For each puzzle of size 8x8 there is a single path which follows the clues 1,2,3,4,1,2,3 and so on, through the whole grid, starting at the green clue labelled 1. The path connects orthogonally. Similarly for the 6x6 puzzles, except here the connections can also be diagonal. All possible connections are marked with faint lines. Add connections using left clicks on the lines; right clicks will undo your connections. The jigsaw symbol is a menu for configuring the game. A left click on the PZL follow_123 symbol next to it starts a new game by loading a randomly selected puzzle; a right click selects the next game in sequence. The wand will perform the hint operation. Clicking the hand checks the current grid for errors, a second click will remove them. The sad smiley will display the solution. The entry box contains the current puzzle number and can be used to enter puzzle numbers. The number to its right is the puzzle difficulty score. To its right is a clock. The game contains 1000 of each puzzle type.")

    def make_tooltip(self):
        self.tooltip_text = [_('Left-mouse random puzzle, right-mouse next puzzle'), _('Give hint, Apply hint'), _('Check for errors, correct errors'), _('Show solution')]

    def load_menus(self):
        self.menu_items.append(MenuItem(
            _('Grid Spacing'),
            ['8',
             '9',
             '10',
             '11',
             '12',
             '13'],
            '',
            ['8',
             '9',
             '10',
             '11',
             '12',
             '13'],
            'font_size'
            ))
        self.menu_items.append(MenuItem(
            _('Save Settings'),
            '',
            '',
            '',
            'save_settings'
        ))
        self.menu_items.append(MenuItem(
            _('Help'),
            '',
            '',
            '',
            'help'
        ))
        self.menu_items.append(MenuItem(
            _('About'),
            '',
            '',
            '',
            'about'
        ))

    def do_scaling(self):
        inc = 0.1
        mult = int(self.dic['font_size'])
        factor = 0.8 + mult * inc
        self.square_size = 30
        self.square_size = int(self.square_size * factor)


class CObject(object):
    """
    Canvas objects: vertices and lines (edges).
    User only interacts with edges.
    grid coords x, y with 0, 0 at top left
    self.widget_dic[jd] = CObject(self.board,
                                       [((x0, y0), (x1, y1)), jd])
    """

    def __init__(self, canvas, data):
        self.canvas = canvas
        self.cid = data[1]
        self.active = False
        self.callback = None
        self.coords = data[0]
        self.canvas.tag_bind(self.cid, "<ButtonRelease-1>", self.command)
        self.canvas.tag_bind(self.cid, "<ButtonRelease-3>", self.command)
        self.canvas.tag_bind(self.cid, "<Enter>", self.command)
        self.canvas.tag_bind(self.cid, "<Leave>", self.command)

    def command(self, event):
        if event.type == "7":
            self.active = True
        if event.type == "8":
            self.active = False
        if event.type == "5" and self.active:
            mouse_index = event.num
            if mouse_index == 1 or mouse_index == 3:
                if mouse_index == 1:
                    event_code = 1
                elif mouse_index == 3:
                    event_code = 2
                self.callback(event_code, self.cid)


class Board(tk.Frame):
    def __init__(self, parent, settings, model, images):
        self.settings = settings
        self.model = model
        self.images = images
        self.vertex_dic = None
        self.widget_dic = {}
        self.grid_width = None
        self.grid_height = None
        self.canvas_width = None
        self.canvas_height = None
        self.grid_unit = self.settings.square_size
        self.grid_margin = 15
        bg = self.settings.green
        tk.Frame.__init__(self, parent, relief='flat',
                          highlightbackground=self.settings.grey,
                          highlightthickness=2,
                          bd=2, bg=bg)
        self.grid_width = Sgg.width
        self.grid_height = Sgg.height
        self.canvas_width = 2 * self.grid_margin + self.grid_unit * \
                            (self.grid_width - 1)
        self.canvas_height = 2 * self.grid_margin + self.grid_unit * \
                             (self.grid_height - 1)

        self.tk_focusFollowsMouse()
        bg = self.settings.white
        self.board = tk.Canvas(self, width=self.canvas_width,
                               height=self.canvas_height,
                               bg=bg)

        self.board.grid(row=0, column=0, sticky='NSEW')
        self.grid(row=0, column=0)

    def my_destroy(self):
        self.destroy()

    def add_callbacks(self, func):
        for key, widget in list(self.widget_dic.items()):
            widget.callback = func

    def draw_vertex(self, datum):
        x = self.grid_margin + datum.key[0] * self.grid_unit
        y = self.grid_margin + datum.key[1] * self.grid_unit
        if datum.key == self.model.start_datum.key or\
           datum.key == self.model.end_datum.key:
            image = self.images.bridges_green_number[datum.clue]
            jd = self.board.create_image(x, y, image=image)
        else:
            image = self.images.bridges_number[datum.clue]
            jd = self.board.create_image(x, y, image=image)
        datum.grey_id = jd
        image = self.images.bridges_red_number[datum.clue]
        jd = self.board.create_image(x, y, image=image)
        self.board.itemconfig(jd, state='hidden')
        datum.red_id = jd

    def draw_edge(self, coord_0, coord_1):
        state = 'hidden'
        state = 'normal'
        width = 2
        activewidth = 4
        activefill = '#82c026'
        fill = '#d0dbb9'

        x2 = self.grid_margin + coord_0[0] * self.grid_unit
        y2 = self.grid_margin + coord_0[1] * self.grid_unit
        x3 = self.grid_margin + coord_1[0] * self.grid_unit
        y3 = self.grid_margin + coord_1[1] * self.grid_unit
        jd = self.board.create_line(x2, y2, x3, y3, width=width,
                                    fill=fill,
                                    state=state,
                                    activefill=activefill,
                                    activewidth=activewidth)
        self.widget_dic[jd] = CObject(self.board,
                                      [(coord_0, coord_1), jd])
        return jd

    def make_edges(self):
        """
        edge_dic[edge] = [coord_0, coord_1, is_path]
        Use edge_dic to draw possible connections between vertices
        and create CObjects for them.
        Then add the widget id's to edge_dic.
        """
        tmp_dic = {}
        for key, edge in list(self.model.edge_dic.items()):
            jd = self.draw_edge(key[0], key[1])
            tmp_dic[key] = jd

        # Add id's to edge_dic

        for key, jd in list(tmp_dic.items()):
            self.model.edge_dic[key].append(jd)

    def draw_puzzle(self, vertex_dic):
        self.vertex_dic = vertex_dic
        self.widget_dic = {}
        self.make_edges()
        # add the vertices and create hidden green and red versions
        for key, datum in list(self.vertex_dic.items()):
            x0 = key[0]
            y0 = key[1]
            self.draw_vertex(datum)
        self.update_idletasks()

    def switch_vertex(self, jd, vertex_on):
        if vertex_on:
            self.board.itemconfig(jd, state='normal')
        else:
            self.board.itemconfig(jd, state='hidden')

    def show_hint(self):
        if self.model.hint:
            self.board.itemconfig(self.vertex_dic[self.model.hint[0]].red_id,
                                  state='normal')

    def unshow_hint(self):
        if self.model.hint:
            self.board.itemconfig(self.vertex_dic[self.model.hint[0]].red_id,
                                  state='hidden')

    def show_edge(self, jd):
        fill = 'black'
        self.board.itemconfig(jd, width=3, fill=fill)

    def add_user_edge(self, jd):
        fill = 'black'
        self.board.itemconfig(jd, width=3, fill=fill)

    def delete_user_edge(self, jd):
        fill = '#d0dbb9'
        self.board.itemconfig(jd, width=2, fill=fill)

    def show_solution(self):
        for key, edge in list(self.model.edge_dic.items()):
            if edge[-2]:
                self.board.itemconfigure(edge[-1], width=3, fill='black')
            else:
                self.board.itemconfigure(edge[-1], state='hidden')

    def colour_edges(self, colour):
        if colour:
            fill = 'red'
            for key, item in list(self.model.error_dic.items()):
                jd = self.model.edge_dic[key][1]
                self.board.itemconfig(jd, width=3, fill=fill)
        else:
            for key, item in list(self.model.error_dic.items()):
                jd = self.model.edge_dic[key][1]
                self.delete_user_edge(jd)

class View(ViewB):
    """
    Stick blobs on the screen and respond to callbacks
    When a puzzle is first drawn we show all possible connections
    as a single thin line. The user may place links
    between the vertices, or may remove them. These links may be part
    of the correct solution.
    widgets: edges and vertices.
    """

    def __init__(self, master, settings):
        ViewB.__init__(self, master, settings)
        self.model = None
        self.show_connections = False
        self.image_dic = {}
        self.make_image_dic()
        self.image_dic['start'] = [self.images.start_follow_123, 0, True]
        self.do_layout(self)
        self.entry_box.activate()

    def make_board(self):
        """
        draw the squares
        """

        if self.board is not None:
            self.board.my_destroy()
        self.board = Board(self.top_frame, self.settings,
                           self.model, self.images)

    def draw_puzzle(self, vertex_dic):
        # draw the underlying faint grid lines
        self.board.draw_puzzle(vertex_dic)


class Datum(object):
    """
    Cell item
    """
    def __init__(self, key):
        self.key = key
        self.trail = None
        self.neighbours = None
        self.path_out = None
        self.path_in = None
        self.clue = None
        self.guess_out = None
        self.guess_in = None
        self.grey_id = None
        self.red_id = None


class Model(object):
    """
    Solving algorithms
    """
    def __init__(self, model_data):
        self.model_data = model_data
        self.datum_dic = {}
        self.edge_dic = {}
        self.error_dic = {}
        self.vertex_dic = {}
        self.ends = [(), ()]
        self.incs = []
        self.min_score = 4
        self.difficulty = None
        self.start_datum = None
        self.end_datum = None
        self.hampath = None
        self.hint = []
        self.min_puzzles = 1000
        self.min_mix = 1000
        self.freq = 5
        self.status = True

    def init_grid(self):
        self.datum_dic = {}
        height = Sgg.height
        width = Sgg.width
        for y in range(height):
            for x in range(width):
                key = (x, y)
                self.datum_dic[key] = Datum(key)

    def get_octagonal_neighbours(self, key):
        """
        Order: up screen (towards origin!) , then clockwise
        """
        neighbours = []
        x = key[0]
        y = key[1]

        neighbour_key = (x, y - 1)
        if neighbour_key in self.datum_dic:
            neighbour_datum = self.datum_dic[neighbour_key]
        else:
            neighbour_datum = None
        neighbours.append(neighbour_datum)

        neighbour_key = (x + 1, y - 1)
        if neighbour_key in self.datum_dic:
            neighbour_datum = self.datum_dic[neighbour_key]
        else:
            neighbour_datum = None
        neighbours.append(neighbour_datum)

        neighbour_key = (x + 1, y)
        if neighbour_key in self.datum_dic:
            neighbour_datum = self.datum_dic[neighbour_key]
        else:
            neighbour_datum = None
        neighbours.append(neighbour_datum)

        neighbour_key = (x + 1, y + 1)
        if neighbour_key in self.datum_dic:
            neighbour_datum = self.datum_dic[neighbour_key]
        else:
            neighbour_datum = None
        neighbours.append(neighbour_datum)

        neighbour_key = (x, y + 1)
        if neighbour_key in self.datum_dic:
            neighbour_datum = self.datum_dic[neighbour_key]
        else:
            neighbour_datum = None
        neighbours.append(neighbour_datum)

        neighbour_key = (x - 1, y + 1)
        if neighbour_key in self.datum_dic:
            neighbour_datum = self.datum_dic[neighbour_key]
        else:
            neighbour_datum = None
        neighbours.append(neighbour_datum)

        neighbour_key = (x - 1, y)
        if neighbour_key in self.datum_dic:
            neighbour_datum = self.datum_dic[neighbour_key]
        else:
            neighbour_datum = None
        neighbours.append(neighbour_datum)

        neighbour_key = (x - 1, y - 1)
        if neighbour_key in self.datum_dic:
            neighbour_datum = self.datum_dic[neighbour_key]
        else:
            neighbour_datum = None
        neighbours.append(neighbour_datum)

        return neighbours

    def get_square_neighbours(self, key):
        """
        Order: up screen (towards origin!) , then clockwise
        """
        neighbours = []
        x = key[0]
        y = key[1]

        neighbour_key = (x, y - 1)
        if neighbour_key in self.datum_dic:
            neighbour_datum = self.datum_dic[neighbour_key]
        else:
            neighbour_datum = None
        neighbours.append(neighbour_datum)

        neighbour_key = (x + 1, y)
        if neighbour_key in self.datum_dic:
            neighbour_datum = self.datum_dic[neighbour_key]
        else:
            neighbour_datum = None
        neighbours.append(neighbour_datum)

        neighbour_key = (x, y + 1)
        if neighbour_key in self.datum_dic:
            neighbour_datum = self.datum_dic[neighbour_key]
        else:
            neighbour_datum = None
        neighbours.append(neighbour_datum)

        neighbour_key = (x - 1, y)
        if neighbour_key in self.datum_dic:
            neighbour_datum = self.datum_dic[neighbour_key]
        else:
            neighbour_datum = None
        neighbours.append(neighbour_datum)

        return neighbours

    def set_neighbours(self):
        if Sgg.shape == Sgg.OCTAGONAL:
            get_neighbours = self.get_octagonal_neighbours
        elif Sgg.shape == Sgg.SQUARE:
            get_neighbours = self.get_square_neighbours

        for key, datum in list(self.datum_dic.items()):
            datum.neighbours = get_neighbours(key)
            neighbours = datum.neighbours
            count = 0
            for neighbour in neighbours:
                if neighbour is not None:
                    count += 1

    def zero_datum(self):
        for key, datum in list(self.datum_dic.items()):
            datum.trail = None

    def ready_for_user(self):
        for key, datum in list(self.datum_dic.items()):
            datum.guess_in = None
            datum.guess_out = None
        self.reset_errors()

    def is_wrong(self, datum):
        ret = False
        if datum.guess_in is not None and\
           datum.guess_in != datum.path_in:
            ret = True
        if datum.guess_out is not None and\
           datum.guess_out != datum.path_out:
            ret = True
        return ret

    def check_errors(self):
        self.status = True
        for key, datum in list(self.datum_dic.items()):
            if self.is_wrong(datum):
                self.status = False

    def make_edges(self):
        """
        Before we get here we have used a trail of numbers 1 to
        width*height to add the clues 1,2,3(,4) to the
        corresponding datum.clue
        We draw possible links between all consecutive clue values.
        Make edge_dic[edge] = [is_path]
        where edge = ((x, y), (nx, ny)) so we know which
        guess_in and guess_out to set and is_path is True
        if the path is in the solution.
        nb later we append the widget id for edges to get:
        edge_dic[((x, y), (nx, ny))] = [is_path, widget_id]
        which means we have an association between coords and widgets
        and via widget_dic between widget_id and coords:
        coords = widget_dic[widget_id].coords
        """
        if Sgg.shape == Sgg.SQUARE:
            oks_in = [(1, 2), (2, 3), (3, 1)]

            def distance(key_0, key_1):
                # taxicab distance
                return int(abs(key_0[0] - key_1[0]) +
                           abs(key_0[1] - key_1[1]))

        else:
            oks_in = [(1, 2), (2, 3), (3, 4), (4, 1)]

            def distance(key_0, key_1):
                # chebyshev distance
                return int(max(abs(key_0[0] - key_1[0]),
                               abs(key_0[1] - key_1[1])))

        ranges = [-1, 0, 1]
        edge_dic = {}
        for y in range(Sgg.height):
            for x in range(Sgg.width):
                for yd in ranges:
                    ny = y + yd
                    for xd in ranges:
                        nx = x + xd
                        if nx > -1 and nx < Sgg.width and\
                           ny > -1 and ny < Sgg.height and\
                           distance((x, y), (nx, ny)) == 1:
                            clue_0 = self.datum_dic[x, y].clue
                            clue_1 = self.datum_dic[nx, ny].clue
                            if (clue_0, clue_1) in oks_in:

                                # clues for (x, y) lead directly to (nx, ny)
                                # is_path True if this edge is in the solution
                                # in which case [x,y]path_out == [nx,ny]path_in

                                is_path = self.datum_dic[x, y].path_out ==\
                                          self.datum_dic[nx, ny]
                                edge_dic[((x, y), (nx, ny))] = [is_path]
        self.edge_dic = edge_dic

    def get_puzzle(self, puzzle_number):
        puzzle = self.model_data.get_puzzle(puzzle_number)
        if puzzle:
            self.difficulty = int(puzzle[0])
            Sgg.shape = int(puzzle[1])
            Sgg.width = int(puzzle[2])
            Sgg.height = int(puzzle[3])
            start_index = int(puzzle[4])
            end_index = int(puzzle[5])
            self.init_grid()
            self.set_neighbours()
            start_key = (start_index % Sgg.width, start_index // Sgg.width)
            self.start_datum = self.datum_dic[start_key]
            end_key = (end_index % Sgg.width, end_index // Sgg.width)
            self.end_datum = self.datum_dic[end_key]
            pos = 6
            for y in range(Sgg.height):
                for x in range(Sgg.width):
                    key = (x, y)
                    self.datum_dic[key].trail = puzzle[pos]
                    pos += 1
            self.trail_to_clues()
            # self.print_trail()
            # self.print_clues()
            self.apply_algorithm(0)
            self.make_edges()
            self.ready_for_user()

    def is_finished(self):
        ret = True
        for key, datum in list(self.datum_dic.items()):
            if datum.guess_in is None:
                if self.start_datum != datum:
                    ret = False
            if datum.guess_out is None:
                if self.end_datum != datum:
                    ret = False
        return ret

    def solve_123f(self, datum, next_value):
        """
        If a datum can only link one way we know the path
        """
        possible = None
        for neighbour in datum.neighbours:
            if neighbour is not None and neighbour.clue == next_value:
                if neighbour.guess_in is None:
                    if possible is None:
                        possible = neighbour
                    else:
                        # > 1 possibilities so fail and return False
                        possible = None
                        break
        return possible

    def solve_123b(self, datum, prev_value):
        """
        If a datum can only link one way we know the path
        """
        possible = None
        for neighbour in datum.neighbours:
            if neighbour is not None and neighbour.clue == prev_value:
                if neighbour.guess_out is None:
                    if possible is None:
                        possible = neighbour
                    else:
                        # > 1 possibilities so fail and return False
                        possible = None
                        break
        return possible

    def solve_it(self, next_value, prev_value):
        """
        Algorithm:
        1. can a cell only extend forwards one way?
        2. can a cell only extend backwards one way?
        If so set guess_in and guess_out accordingly.

        path_in and path_out are the solution and set elsewhere.
        """
        progress = True
        rounds = 0
        while progress:
            rounds += 1
            progress = False
            for key, datum in list(self.datum_dic.items()):
                # forwards
                if datum.guess_out is None and\
                   datum.clue is not None and\
                   datum != self.end_datum:
                    ret = self.solve_123f(datum, next_value(datum.clue))
                    if ret is not None:
                        datum.guess_out = ret
                        ret.guess_in = datum
                        progress = True
                # backwards
                if datum.guess_in is None and\
                   datum.clue is not None and\
                   datum != self.start_datum:
                    ret = self.solve_123b(datum, prev_value(datum.clue))
                    if ret is not None:
                        datum.guess_in = ret
                        ret.guess_out = datum
                        progress = True
        return rounds

    def do_hint(self, next_value, prev_value):
        hint = []
        for key, datum in list(self.datum_dic.items()):
            # forwards
            if datum.guess_out is None and\
               datum.clue is not None and\
               datum != self.end_datum:
                ret = self.solve_123f(datum, next_value(datum.clue))
                if ret is not None:
                    hint = [datum.key, ret.key]
                    break
            # backwards
            if datum.guess_in is None and\
               datum.clue is not None and\
               datum != self.start_datum:
                ret = self.solve_123b(datum, prev_value(datum.clue))
                if ret is not None:
                    hint = [ret.key, datum.key]
                    break
        return hint

    def apply_algorithm(self, job):
        """
        Use solver algorithms to look for consecutive vertices.
        """

        if Sgg.shape == Sgg.SQUARE:
            def next_value(value):
                nums = [0, 2, 3, 1]
                return nums[value]

            def prev_value(value):
                nums = [0, 3, 1, 2]
                return nums[value]
        else:
            def next_value(value):
                nums = [0, 2, 3, 4, 1]
                return nums[value]

            def prev_value(value):
                nums = [0, 4, 1, 2, 3]
                return nums[value]

        if job == 0:
            ret = self.solve_it(next_value, prev_value)
        else:
            ret = self.do_hint(next_value, prev_value)
        return ret

    def set_edge(self, datum_out, datum_in):
        datum_out.guess_out = datum_in
        datum_in.guess_in = datum_out
        if self.is_wrong(datum_out) or self.is_wrong(datum_in):
            self.status = False

    def add_user_edge(self, coords):
        """
        Convention for coords is (datum_out.key, datum_in.key)
        Once status is False all user edges are errors.
        """

        coord_0 = coords[0]
        coord_1 = coords[1]
        datum_out = self.datum_dic[coord_0]
        datum_in = self.datum_dic[coord_1]
        datum_out.guess_out = datum_in
        datum_in.guess_in = datum_out
        if self.is_wrong(datum_out) or self.is_wrong(datum_in):
            self.status = False
        if not self.status:
            self.error_dic[tuple(coords)] = True

    def delete_user_edge(self, coords):
        """
        Convention for coords is (datum_out.key, datum_in.key)
        Once status is False all user edges are errors.
        """

        coord_0 = coords[0]
        coord_1 = coords[1]
        datum_out = self.datum_dic[coord_0]
        datum_in = self.datum_dic[coord_1]
        datum_out.guess_out = None
        datum_in.guess_in = None
        try:
            del self.error_dic[coords]
        except KeyError:
            pass
        if not self.error_dic:
            self.status = True

    def trail_to_clues(self):
        """
        The datums have been assigned a number trail which denotes the order
        of the path through the grid starting at start_datum.
        Here we use the numbers to follow the trail and assign "clues"
        to the datums and to set the path directions in the datums.
        """
        if Sgg.shape == Sgg.SQUARE:
            def lookup(value):
                nums = [1, 2, 3]
                pointer = value % len(nums)
                return nums[pointer - 1]
        else:
            def lookup(value):
                nums = [1, 2, 3, 4]
                pointer = value % len(nums)
                return nums[pointer - 1]

        clue = 0
        current_datum = self.start_datum
        while current_datum != self.end_datum:
            next_trail = current_datum.trail + 1
            clue = lookup(current_datum.trail)

            # find next cell in neighbours

            for neighbour in current_datum.neighbours:
                if neighbour is not None and neighbour.trail == next_trail:
                    current_datum.clue = clue
                    current_datum.path_out = neighbour
                    neighbour.path_in = current_datum
                    current_datum = neighbour
                    break
        clue = lookup(current_datum.trail)
        current_datum.clue = clue

    def reset_errors(self):
        self.error_dic = {}

    """
    def print_clues(self):
        print self.start_datum.key, self.end_datum.key
        for y in range(Sgg.height):
            for x in range(Sgg.width):
                num = self.datum_dic[(x, y)].clue
                print num,
            print
        print

    def print_trail(self):
        print self.start_datum.key, self.end_datum.key
        for y in range(Sgg.height):
            for x in range(Sgg.width):
                num = self.datum_dic[(x, y)].trail
                print num,
            print
        print
    """

    def save_puzzles(self, puzzles):
        puzzles = sorted(puzzles)
        filename = str(Sgg.shape) + '_' +\
                   str(Sgg.width) + 'x' +\
                   str(Sgg.height) + '.txt'
        with open(filename, "w") as fo:
            rec = ''
            for puzzle in puzzles:
                for item in puzzle:
                    rec += str(item)
                    rec += ','
            fo.write(rec)

    def save_puzzle(self, rounds):
        puzzle = []
        puzzle.append(rounds)
        puzzle.append(Sgg.shape)
        puzzle.append(Sgg.width)
        puzzle.append(Sgg.height)
        start_index = self.start_datum.key[0] +\
                      self.start_datum.key[1] * Sgg.width
        puzzle.append(start_index)
        end_index = self.end_datum.key[0] +\
                    self.end_datum.key[1] * Sgg.width
        puzzle.append(end_index)
        for y in range(Sgg.height):
            for x in range(Sgg.width):
                key = (x, y)
                clue = self.datum_dic[key].trail
                puzzle.append(clue)
        return puzzle

    def make_plough(self):
        coords = []
        width = Sgg.width
        height = Sgg.height
        for y in range(height):
            if y % 2 == 0:
                x0 = width - 1
                xinc = -1
            else:
                x0 = 0
                xinc = 1
            for xi in range(width):
                coords.append((x0, y))
                x0 += xinc
        return coords

    def get_ends(self):
        """
        Get ends in a specific order
        """
        self.ends = []
        for coord, path in list(self.vertex_dic.items()):
            if not path[0]:
                self.ends.append(coord)
                break
        for coord, path in list(self.vertex_dic.items()):
            if not path[1]:
                self.ends.append(coord)
                break

    def in_grid(self, coord):
        ret = False
        x = coord[0]
        y = coord[1]
        if x > -1 and x < Sgg.width and y > -1 and y < Sgg.height:
            ret = True
        return ret

    def enumerate_path(self):
        direction = 1
        vertex = self.ends[0]
        count = 0
        while count < Sgg.width * Sgg.height:
            count += 1
            self.datum_dic[vertex].trail = count
            vertex = self.vertex_dic[vertex][direction]

    def get_path(self, vertex_in, direction):
        directions = [1, 0]
        vertex = self.vertex_dic[vertex_in][directions[direction]]
        tmp = []
        while True:
            if vertex in tmp:
                break
            else:
                tmp.append(vertex)
                vertex = self.vertex_dic[vertex][direction]
        return tmp

    def do_back_bite(self):
        """
        chosen_end is connected randomly to an adjacent neighbour
        named new_link.
        new_link now has 3 links and we find which of the original
        links is now part of a cycle
        named cycle_link.
        This link is broken at new_link and cycle_link.
        https://arxiv.org/pdf/cond-mat/0508094.pdf
        Secondary Structures in Long Compact Polymers
        """

        while True:
            direction = random.randint(0, 1)
            chosen_end = self.ends[direction]
            poss = []
            for inc in self.incs:
                new_x = chosen_end[0] + inc[0]
                new_y = chosen_end[1] + inc[1]
                new_coord = new_x, new_y
                if self.in_grid(new_coord) and\
                   new_coord not in self.ends and\
                   new_coord not in self.vertex_dic[chosen_end]:
                    poss.append(new_coord)
            if poss:
                break

        choice = random.randint(0, len(poss) - 1)
        new_link = poss[choice]

        # add to chosen_end

        links = self.vertex_dic[tuple(chosen_end)]
        if not links[0]:
            self.vertex_dic[tuple(chosen_end)] = [new_link, links[1]]
        else:
            self.vertex_dic[tuple(chosen_end)] = [links[0], new_link]

        self.vertex_dic[new_link].append(tuple(chosen_end))
        cycle_link = self.vertex_dic[new_link][direction]
        del self.vertex_dic[new_link][direction]

        # now remove link from cycle_link to new_link

        self.vertex_dic[cycle_link].remove(tuple(new_link))
        if direction == 0:
            self.vertex_dic[cycle_link] = [(), self.vertex_dic[cycle_link][0]]
        else:
            self.vertex_dic[cycle_link].append(())

        # need to reverse part of path, so get it

        path = self.get_path(cycle_link, direction)

        # not last item

        path.pop()

        # reverse rest

        for item in path:
            vertex = self.vertex_dic[item]
            tmp0 = vertex[0]
            tmp1 = vertex[1]
            self.vertex_dic[item] = [tmp1, tmp0]

        # set new ends

        self.get_ends()

    def progress_vertex_dic(self):
        for i in range(self.min_mix):
            self.do_back_bite()
            self.get_ends()

    def init_vertex_dic(self, coords):
        vertex_dic = {}
        vertex_dic[coords[0]] = [(), coords[1]]
        for i in range(1, len(coords) - 1):
            vertex_dic[coords[i]] = [coords[i - 1], coords[i + 1]]
        vertex_dic[coords[-1]] = [coords[-2], ()]
        self.vertex_dic = vertex_dic

    def generate_1(self, min_puzzles):
        """
        # we make a plough followed by min_mix generations
        # to mix the paths up before using them regularly.
        Generate a Hamiltonian path through the grid.
        enumerate_path sets a trail of numbers 1 to grid_size.
        trails_to_clues sets clue values for the user
        solver attemps to solve the grid using the clues, and if it succeeds
        the puzzle is saved using save_puzzle.
        """
        puzzles = []
        coords = self.make_plough()
        self.init_vertex_dic(coords)
        self.get_ends()
        self.progress_vertex_dic()

        while True:
            for i in range(self.freq):
                self.do_back_bite()
                self.get_ends()

            # get datums

            self.init_grid()
            self.enumerate_path()
            self.start_datum = self.datum_dic[self.ends[0]]
            self.end_datum = self.datum_dic[self.ends[1]]
            self.set_neighbours()
            self.trail_to_clues()
            rounds = self.apply_algorithm(0)
            if self.is_finished() and rounds >= self.min_score:
                # self.print_trail()
                # self.print_clues()
                self.make_edges()
                puzzle = self.save_puzzle(len(self.edge_dic))
                puzzles.append(puzzle)
                # print 'puzzle_count',len(puzzles), rounds, len(self.edge_dic)
                if len(puzzles) >= min_puzzles:
                    break

        puzzles = sorted(puzzles)
        self.save_puzzles(puzzles)
        return puzzles

    def generate(self):
        self.min_mix = 500
        self.freq = 5
        seed = 1
        random.seed(seed)
        Sgg.shape = Sgg.SQUARE
        min_puzzles = 10
        #shapes = [Sgg.SQUARE, Sgg.OCTAGONAL]
        #shapes = [Sgg.OCTAGONAL]
        shapes = [Sgg.SQUARE]
        for shape in shapes:
            Sgg.shape = shape
            if shape == Sgg.OCTAGONAL:
                Sgg.width = 6
                Sgg.height = 6
                self.min_score = 5
                self.incs = [(1, 0), (-1, 0), (0, 1), (0, -1),
                             (1, 1), (1, -1), (-1, 1), (-1, -1)]
            elif shape == Sgg.SQUARE:
                Sgg.width = 8
                Sgg.height = 8
                self.min_score = 5
                self.incs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
            self.generate_1(min_puzzles)
        exit(1)


class Controller(object):
    """
    Set up and control
    """

    def __init__(self, root):
        self.settings = Settings()
        self.master = root
        self.flasher = None
        self.model_data = ModelData()
        self.model = None
        self.view = View(root, self.settings)
        self.status = False
        self.active = False
        self.error_detected = False
        self.hint_status = Sgg.GIVE_HINT
        self.puzzle_number = None
        puzzle_number = None
        self.model = Model(self.model_data)
        self.start_game(puzzle_number)

    def start_game(self, puzzle_number):
        # self.test()
        self.model = Model(self.model_data)
        #self.model.generate()
        self.set_puzzle_number(puzzle_number)
        self.hint_status = Sgg.GIVE_HINT
        self.view.clock_init()
        self.view.clock_restart()
        self.flasher = Flasher(self.view.clock.box.label,
                               self.master, self.settings)
        PzlG.logger.logger.info("get_puzzle " + str(self.puzzle_number))
        self.model.get_puzzle(self.puzzle_number)
        self.view.model = self.model
        self.view.make_board()
        self.view.draw_puzzle(self.model.datum_dic)
        self.view.game_on()
        self.view.hint_off()
        self.add_callbacks()
        self.error_detected = False
        self.active = True
        self.view.entry_box.clear()
        self.view.entry_box.write_box(str(self.puzzle_number))
        self.view.update_score_box(self.model.difficulty)
        self.status = False

    def test(self):
        bad = []
        for puzzle_number in range(self.model_data.puzzle_count):
            self.model = Model(self.model_data)
            self.model.get_puzzle(puzzle_number)
            rounds = self.model.apply_algorithm(0)
            if not self.model.is_finished():
                bad.append(puzzle_number)

        # print 'bad', bad, len(bad), self.model_data.puzzle_count
        exit(4)

    def add_callbacks(self):
        self.view.add_menu_callback(self.service_menu)
        self.view.add_toolbar_callback(self.service_toolbar)
        self.view.entry_box.add_callback(self.get_puzzle_number)
        self.view.board.add_callbacks(self.board_event)

    def service_menu(self, *args):
        """
        Respond to menu choices
        """

        strargs = ''
        for item in args:
            strargs += ' ' + item
        PzlG.logger.logger.info("service_menu " + strargs)
        name = args[0]
        if name == 'font_size':
            self.set_font_size()
        elif name == 'save_settings':
            self.settings.preferences.save()
        elif name == 'about':
            self.view.about()
        elif name == 'help':
            self.view.help()

    def service_toolbar(self, button_index, mouse_index):
        PzlG.logger.logger.info("service_toolbar " +
                                str(button_index) +
                                ' ' +
                                str(mouse_index))
        if mouse_index == 2:
            alg_index = None
            if self.model.hint:
                alg_index = self.model.hint[0]
            self.view.do_tooltip(button_index, alg_index)
        elif mouse_index == 3:
            if button_index == 0:
                puzzle_number = self.puzzle_number + 1
                self.start_game(puzzle_number)
        elif mouse_index == 1:
            if button_index == 0:
                self.start_game(None)
            elif button_index == 1:
                if not self.model.is_finished():
                    self.give_hint()
                    self.check_finished()
            elif button_index == 2:
                if not self.model.is_finished():
                    self.check_errors()
            elif button_index == 3:
                self.show_solution()

    def board_event(self, event_code, widget_id):
        if self.active:
            self.view.board.unshow_hint()
            if event_code == 1:
                self.view.board.add_user_edge(widget_id)
                coords = self.view.board.widget_dic[widget_id].coords
                text = 'Board_event: add_user_edge at ' + str(coords)
                PzlG.logger.logger.info(text)
                self.model.add_user_edge(coords)
            elif event_code == 2:
                coords = self.view.board.widget_dic[widget_id].coords
                text = 'Board_event: delete_user_edge at ' + str(coords)
                PzlG.logger.logger.info(text)
                self.view.board.delete_user_edge(widget_id)
                self.model.delete_user_edge(coords)

            self.ready_for_hint()
            self.check_finished()

    def give_hint(self):
        if self.hint_status == Sgg.GIVE_HINT:
            if not self.model.status:
                self.view.thumbs_down()
                self.error_detected = True
                self.view.board.colour_edges(True)
            else:
                self.model.hint = self.model.apply_algorithm(1)
                self.view.board.show_hint()
                self.view.hint_on()

            self.hint_status = Sgg.APPLY_HINT
        else:
            coord_0 = self.model.hint[0]
            coord_1 = self.model.hint[1]
            datum_out = self.model.datum_dic[coord_0]
            datum_in = self.model.datum_dic[coord_1]
            self.model.set_edge(datum_out, datum_in)
            self.view.board.add_user_edge(self.model.edge_dic[(coord_0,
                                                               coord_1)][1])
            self.view.board.unshow_hint()
            self.view.hint_off()
            self.hint_status = Sgg.GIVE_HINT

    def ready_for_hint(self):
        if not self.model.is_finished():
            self.hint_status = Sgg.GIVE_HINT
            if self.model.status:
                self.view.board.unshow_hint()
                self.error_detected = False
                self.view.hint_off()
                self.view.thumbs_up()
            self.view.clock.set_show(True)

    def check_finished(self):
        """
        Check if finished.
        If so, handle buttons, flasher and clock
        """
        if self.active:
            if self.model.is_finished():
                self.view.game_over()
                self.view.clock.set_show(True)
                self.view.clock_stop()
                self.show_solution()
                self.flasher.flash()
                self.active = False

    def undo_errors(self):
        for key, item in list(self.model.error_dic.items()):
            self.model.delete_user_edge(key)
        self.model.reset_errors()

    def tidy_error(self):
        self.error_detected = False
        self.view.thumbs_up()
        self.view.board.colour_edges(False)
        self.undo_errors()

    def check_errors(self):
        # have we already detected errors ?
        if self.error_detected:
            # we know there's an error already, so now we correct it
            self.tidy_error()
            self.ready_for_hint()
        else:
            if self.model.error_dic:
                self.view.thumbs_down()
                self.error_detected = True
                self.view.board.colour_edges(True)

    def show_solution(self):
        self.tidy()
        self.view.board.unshow_hint()
        self.view.board.show_solution()
        self.view.game_over()
        self.view.clock_stop()
        self.active = False

    def set_puzzle_number(self, puzzle_number):
        if puzzle_number is None or puzzle_number < 0 or \
                puzzle_number > self.model_data.puzzle_count - 1:
            puzzle_number = randint(0, self.model_data.puzzle_count - 1)
        self.puzzle_number = puzzle_number

    def tidy(self):
        self.hint_status = Sgg.GIVE_HINT
        self.error_detected = False
        self.view.thumbs_up()
        self.model.reset_errors()

    def get_puzzle_number(self, text):
        self.tidy()
        if text.find('XYZZY') != -1:
            self.view.xyzzy()
            self.view.entry_box.clear()
        else:
            try:
                puzzle_number = int(text)
                self.start_game(puzzle_number)
            except ValueError:
                self.view.entry_box.clear()

    def set_font_size(self):
        self.settings.do_scaling()
        self.start_game(self.puzzle_number)


INITIALISE = PzlG()
if __name__ == '__main__':
    try:
        ROOT = tk.Tk()
        ROOT.withdraw()
        APP = Controller(ROOT)
        ROOT.mainloop()
        PzlG.logger.logger.info("Stop program")
    except:
        PzlG.logger.logger.info("Failure!")
        PzlG.logger.logger.exception("Unhandled exception during main")
