J'ai un problème de combinatoire que j'aimerais mettre sur l' OEIS - le problème est que je n'ai pas assez de termes. Ce défi de code est de m'aider à calculer plus de termes, et le gagnant sera l'utilisateur avec la soumission contenant le plus grand nombre de termes.

Le problème

Supposons que je vous donne un tableau triangulaire d'ampoules de longueur latérale :$n$

     o
    o o
   o o o
  o o o o
 o o o o o
o o o o o o
1 2  ...  n

Je vais allumer trois ampoules qui forment un triangle équilatéral "vertical" comme dans l'exemple suivant:

     o
    o x
   o o o
  o o o o
 o x o o x
o o o o o o

Avant d'allumer les lumières, votre travail consiste à retirer autant d'ampoules que possible de la matrice, sans perdre la possibilité de déduire le triangle d'ampoules allumées. Pour être clair, si une ampoule a été retirée, elle ne s'allume pas lorsque sa position est allumée.

Par exemple, si vous supprimiez les ampoules suivantes (marquées par .), vous ne verriez que les deux lumières suivantes s'allumer (marquées par x), ce qui suffit à déduire uniquement la troisième position (non éclairée):

     .              .
    . o            . x
   . . o          . . o
  o o o .   =>   o o o .
 o o o o .      o x o o . <- the third unlit position
o . . . o o    o . . . o o

Soit a(n)le nombre maximum d'ampoules pouvant être retirées sans introduire d'ambiguïtés.

Exemple

Avec un algorithme naïf, j'ai vérifié les valeurs jusqu'à un triangle de longueur de côté 7, comme indiqué ci-dessous:

                                                                      .
                                                      .              . o
                                        .            . o            o . o
                           .           . .          . . o          . o o .
              .           . .         . o o        o o o .        o o . o .
 .           . .         . o o       o o . o      o o o o .      o . o . o o
. .         . o o       . o o o     o . . o o    o . . . o o    o . o . o o o

a(2) = 3    a(3) = 4    a(4) = 5    a(5) = 7     a(6) = 9       a(7) = 11

Notation

La soumission qui calcule la séquence [a(2), a(3), ..., a(n)]des n plus grands gains. Si deux soumissions ont des séquences identiques, alors celle qui a été publiée plus tôt l'emporte.

Bien que cela ne soit pas nécessaire pour la soumission, ce serait instructif pour moi si vous postez une construction des tableaux triangluar résultants, comme dans l'exemple ci-dessus.

Python 3 ,n=8

import itertools
from ortools.sat.python import cp_model


def solve(n):
    model = cp_model.CpModel()
    solver = cp_model.CpSolver()
    cells = {
        (y, x): model.NewBoolVar(str((y, x)))
        for y in range(n) for x in range(y + 1)}
    triangles = [
            {cells[v] for v in ((y1, x1), (y2, x1), (y2, x1 + y2 - y1))}
            for (y1, x1) in cells.keys() for y2 in range(y1 + 1, n)]
    for t1, t2 in itertools.combinations(triangles, 2):
        model.AddBoolOr(t1.symmetric_difference(t2))
    model.Minimize(sum(cells.values()))
    solver.Solve(model)
    return len(cells) - round(solver.ObjectiveValue())


for n in itertools.count(2):
    print('a(%d) = %d' % (n, solve(n)))

Utilise le solveur CP-SAT de Google OR-Tools .

Après avoir fonctionné pendant environ 30 secondes, il génère les informations suivantes:

a(2) = 3
a(3) = 4
a(4) = 5
a(5) = 7
a(6) = 9
a(7) = 11
a(8) = 13

Je n'ai pas essayé d'attendre n=9car cela prendrait probablement des heures (le nombre de contraintes augmente comme )$n^6$ . Après moins de 30 minutes de calcul, je l'ai découvert a(9)=15. Je laisse mon score n=8car pour le moment les contraintes de temps ne sont pas claires, mais une demi-heure est probablement trop longue.

Comment ça fonctionne

Prenez deux triangles équilatéraux distincts et . Pour éviter toute ambiguïté, il devrait y avoir au moins une ampoule sur un sommet appartenant exactement à l' un de et .T 2 T 1 T $T_1$$T_2$$T_1$$T_2$

Ainsi, la question peut être reformulée comme un problème SAT, avec une contrainte pour chaque paire de triangles.

PS: J'aimerais beaucoup inclure un exemple pour n=8, mais j'ai des problèmes avec le solveur SAT qui veut apparemment garder les solutions pour lui tout seul.

Obtenir les solutions du programme de @ Delfad0r

J'ai étendu le programme de @ Delfad0r aux solutions de sortie. Il donne également des résultats intermédiaires, vous obtenez donc une sortie comme celle-ci:

Solving n = 8:
a(8) >= 9
a(8) >= 10
a(8) >= 11
a(8) >= 12
a(8) >= 13
       o
      . o
     . o o
    . o o .
   o o . o o
  o o o o . .
 o . . o o o .
o . . o . o o o
a(8) = 13

Solving n = 9:
a(9) >= 10
a(9) >= 13
a(9) >= 14
a(9) >= 15
        o
       o o
      o . .
     o . o o
    . o . o o
   . o o o o o
  o o o . o . .
 o o o . . . o o
. o o o o o o . .
a(9) = 15

Ce calcul a pris plusieurs heures.

Si vous devenez impatient et appuyez sur Ctrl-Caprès qu'une solution éventuellement non optimale ait été trouvée, le programme affichera cette solution. Il ne faut donc pas longtemps pour obtenir ceci:

                   .
                  o o
                 . o o
                . o o o
               o o . o o
              o . o o o .
             o . o . o o o
            . o o o o o . o
           o . . o o o o o o
          o o o o o o o o o .
         o o . o o o o . o o o
        o o o o o o . o . o o o
       o . o o . o o o o o o o o
      o o o . o o o o o . o o o o
     o o o . o o o o o o o o . . o
    o o o o o o o o o o o . o . . o
   o o o o . o o o o . o o o o o . o
  o o o o o o o o . o o . . o o o o .
 o o o o . o o . o . o o o o o o . o o
o o . o o . o o o o . o o o . o o o o o
a(20) >= 42

Voici le programme étendu:

import itertools
from ortools.sat.python import cp_model

class ReportPrinter(cp_model.CpSolverSolutionCallback):

    def __init__(self, n, total):
        cp_model.CpSolverSolutionCallback.__init__(self)
        self.__n = n
        self.__total = total

    def on_solution_callback(self):
        print('a(%d) >= %d' %
              (self.__n, self.__total-self.ObjectiveValue()) )

def solve(n):
    model = cp_model.CpModel()
    solver = cp_model.CpSolver()
    cells = {
        (y, x): model.NewBoolVar(str((y, x)))
        for y in range(n) for x in range(y + 1)}
    triangles = [
            {cells[v] for v in ((y1, x1), (y2, x1), (y2, x1 + y2 - y1))}
            for (y1, x1) in cells.keys() for y2 in range(y1 + 1, n)]
    for t1, t2 in itertools.combinations(triangles, 2):
        model.AddBoolOr(t1.symmetric_difference(t2))
    model.Minimize(sum(cells.values()))
    print('Solving n = %d:' % n)
    status = solver.SolveWithSolutionCallback(model, ReportPrinter(n,len(cells)))
    if status == cp_model.OPTIMAL:
        rel = '='
    elif status == cp_model.FEASIBLE:
        rel = '>='
    else:
        print('No result for a(%d)\n' % n)
        return
    for y in range(n):
        print(' '*(n-y-1), end='')
        for x in range(y+1):
            print('.o'[solver.Value(cells[(y,x)])],end=' ')
        print()
    print('a(%d) %s %d' % (n, rel, len(cells) - solver.ObjectiveValue()))
    print()

for n in itertools.count(2):
    solve(n)

Python 3

Basé fortement sur la réponse de Delfad0r , suit principalement la même progression logique en vérifiant les paires de triangles et en validant la configuration si elle ne contient pas de paires de triangles qui échouent à cette validation. Comme je n'ai utilisé aucune bibliothèque à part itertools et copy, j'ai un contrôle total sur la sauvegarde des exemples rencontrés tout au long du programme.

examples = dict() # stores examples by key pair of n to a tuple with the triangle and number of lights turned off

for n in range(3, 8):
    tri = [] # model of the triangle, to be filled with booleans representing lights
    tri_points = [] # list of tuples representing points of the triangle
    for i in range(n):
        tri.append([True]*(i + 1))
        for j in range(i+1):
            tri_points.append((i, j))

    t_set = [] # list of all possible triangles from tri, represented by lists of points
    for i in range(n):
        for j in range(len(tri[i])):
            for k in range(1, n - i):
                t_set.append([(i, j), (i + k, j), (i + k, j + k)])

    from itertools import combinations
    import copy

    # validates whether or not a triangle of n lights can have i lights turned off, and saves an example to examples if validated
    def tri_validate(x):
        candidate_list = list(combinations(tri_points, x))
        tri_pairs = list(combinations(t_set, 2))
        for candidate in candidate_list:
            temp_tri = copy.deepcopy(tri)
            valid = False
            for point in candidate:
                (row, col) = point
                temp_tri[row][col] = False
            for pair in tri_pairs:
                valid = False
                (tri1, tri2) = pair
                for point in tri1:
                    if not valid:
                        if point not in tri2:
                            (row, col) = point
                            if temp_tri[row][col]:
                                valid = True
                for point in tri2:
                    if not valid:
                        if point not in tri1:
                            (row, col) = point
                            if temp_tri[row][col]:
                                valid = True
                if not valid:
                    break
            if valid:
                examples[n] = (temp_tri, x)
                return True
        return False

    # iterates up to the point that validation fails, then moves on to the next n
    for i in range(len(tri_points)):
        if tri_validate(i + 1):
            continue
        break

Le problème est que ce n'est pas très efficace. Il fonctionne très vite n=5, mais commence à ralentir considérablement au-delà de ce point. À n=6, cela prend environ une minute pour fonctionner, et c'est beaucoup plus lent n=7. J'imagine qu'il y a beaucoup de correctifs d'efficacité qui peuvent être faits avec ce programme, mais c'est un brouillon rapide d'une bonne solution avec beaucoup plus de flexibilité pour vérifier le fonctionnement interne de cette méthode. J'y travaillerai progressivement au fil du temps.