[core] [pixncross] [puzzlemadness] [onlinenonograms] Add new module and capability

This MR adds the following:

• A picross capability, suitable for:

  • Websites or applications wanting to fetch picross puzzles published on given websites (eventually curated as well!).
  • Bots wanting to test their picross solving algorithms (could be a learning project for some students).

• An implementation of this capability for pix-n-cross, with quite a few puzzles on there already.

• An implementation of this capability for puzzlemadness, in order to make it two modules and justify the capability entirely. :-)

• An implementation of this capability for onlinenonograms, in order to have a demonstration of how to decode and represent colored picrosses.

• A small demonstration solver for the picross capability.

It's more of a fun week-end project than anything, and something I've had at the back of my head for a few months now. I do not pretend to have made something useful with this MR, au contraire, I'll let it up to you to see if this should be merged or not 😄

Some scripts to test this MR:

try_woob.py (basic interactions using the picross capability and pix-n-cross)

#!/usr/bin/env python3

import os
import sys
import tempfile

import coloredlogs

from woob.core.woob import Woob
from woob.tools.log import settings as log_settings

coloredlogs.install(loglevel='DEBUG')
os.environ['WOOB_USE_OBSOLETE_RESPONSES_DIR'] = '1'

responses_dirname = tempfile.mkdtemp(prefix='woob_session_')
print(
    'Debug data will be saved in this directory:',
    responses_dirname,
    file=sys.stderr,
)

log_settings['responses_dirname'] = responses_dirname

woob = Woob()
woob.load_backends()
backend = woob.get_backend('pixncross')

if False:
    picross = backend.get_picross_puzzle('aut123')
    print(picross.to_dict())

if True:
    for i, picross in enumerate(backend.iter_picross_puzzles()):
        if i >= 5:
            break
        print(picross.to_dict())

try_solver.py (solver that gets a puzzle and publishes a solution using woob)

#!/usr/bin/env python3

import os
import sys
import tempfile

import coloredlogs

from woob.capabilities.picross import PicrossSolution, PicrossSolvedStatus
from woob.core.woob import Woob
from woob.tools.log import settings as log_settings

coloredlogs.install(loglevel='DEBUG')


class PicrossSolver:
    @staticmethod
    def combinations(fmt, length):
        """ Réalise des combinaisons. """

        min_length = sum(fmt) + len(fmt) - 1
        if min_length > length:
            return []

        def combinations_recur(fmt, spaces):
            if not fmt:
                yield ' ' * spaces
                return

            fst, *rest = fmt
            for current_spaces in range(0, spaces + 1):
                for combination in combinations_recur(
                    rest,
                    spaces - current_spaces,
                ):
                    yield (
                        ' ' * current_spaces + 'x' * fst
                        + (' ' if rest else '') + combination
                    )

        return list(combinations_recur(fmt, length - min_length))

    @staticmethod
    def precise(combinations, current_row):
        for i in range(len(combinations) - 1, -1, -1):
            incompatible = False
            for cc, cx in zip(combinations[i], current_row):
                if cx != '?' and cx != cc:
                    incompatible = True
                    break

            if incompatible:
                del combinations[i]

        return combinations

    @staticmethod
    def intersection(combinations):
        def intersection_inner(combinations):
            for s in zip(*combinations):
                if all(c == s[0] for c in s[1:]):
                    yield s[0]
                else:
                    yield '?'

        return ''.join(intersection_inner(combinations))

    def solve(self, puzzle):
        """
        Solve a given picross puzzle.

        Returns a PicrossSolution.
        """

        w, h = len(puzzle.columns), len(puzzle.lines)
        ye = puzzle.columns
        xe = puzzle.lines

        yc = [self.combinations(fmt, h) for fmt in ye]
        xc = [self.combinations(fmt, w) for fmt in xe]

        current = [self.intersection(c) for c in xc]

        while True:
            no_unknown = True

            for x in range(w):
                if len(yc) == 1:
                    continue

                current_column = ''.join(s[x] for s in current)
                yc[x] = self.precise(yc[x], current_column)
                new_column = self.intersection(yc[x])
                if '?' in new_column:
                    no_unknown = False

                for y, c in enumerate(new_column):
                    s = current[y]
                    current[y] = s[:x] + c + s[x + 1:]

            for y in range(h):
                if len(xc) == 1:
                    continue

                current_row = current[y]
                xc[y] = self.precise(xc[y], current_row)
                new_row = self.intersection(xc[y])
                if '?' in new_row:
                    no_unknown = False

                current[y] = new_row

            if no_unknown:
                break

        # Make the solution out of the current state.

        solution = PicrossSolution()
        solution.lines = current

        return solution


class PicrossSolverBot:
    def __init__(self):
        responses_dirname = tempfile.mkdtemp(prefix='woob_session_')
        print(
            'Debug data will be saved in this directory:',
            responses_dirname,
            file=sys.stderr,
        )

        log_settings['responses_dirname'] = responses_dirname
        os.environ['WOOB_USE_OBSOLETE_RESPONSES_DIR'] = '1'

        self.woob = Woob()
        self.woob.load_backends()
        self.backend = self.woob.get_backend('pixncross')
        self.solver = PicrossSolver()

    def __del__(self):
        if self.woob:
            self.woob.deinit()

    def solve_two(self):
        for i, puzzle in enumerate(
            self.backend.iter_picross_puzzles(PicrossSolvedStatus.UNSOLVED),
        ):
            if i >= 2:
                break

            solution = self.solver.solve(puzzle)
            self.backend.submit_picross_puzzle_solution(puzzle, solution)

    def solve(self, id_):
        puzzle = self.backend.get_picross_puzzle(id_)
        solution = self.solver.solve(puzzle)
        self.backend.submit_picross_puzzle_solution(puzzle, solution)


if __name__ == '__main__':
    bot = PicrossSolverBot()
    bot.solve('pic198')