Marathon d'algorithmes

L’idée :

• Nécessairement lorsque l’élément 2 fait l’aller il est avec l’élément 1.
• Si l’élément 1 a passé la berge il revient systématiquement (sauf si pas d’autres éléments à aller chercher).

Donc la première étape on fait passer 1 & 2 ensemble et revenir 1 (puisque ça va forcément se produire à un moment ou à un autre autant le faire le plus tôt possible). Coût : t[1] + t[2]

Ensuite on a deux choix :

• Prendre l’élément 1 et le plus gros élément et faire revenir 1 (et on se retrouve dans la même situation). Coût t[1] + t[gros_element]
• Prendre les deux plus gros éléments et faire revenir 2. Coût t[gros_element] + t[2] On se retrouve avec dans la situation avec 1 & 2

À partir de ça on peut représenter un nœud par état (a, b, c) où

• a indique si l’élément 1 est présent (ça va toujours être le cas presque)
• b indique si l’élément 2 est présent
• c indique le nombre d’autres éléments restant (donc entre len(t) - 2 et 0)

Ainsi que des arêtes entre ces nœuds, et une liste d’adjacence.

Puis on utilise dijkstra (bon dans mon implémentation c’est le dijkstra sans heapq donc avec mauvaise complexité mais on peut avoir quelque chose de satisfaisant. Avec pour nœud de départ (True, True, 0) et pour nœud d’arrive (False, False, len(t) - 2)

Normalement on a ~ (2 len(t)) nœuds et ~ 3 len(t) arcs. Donc on pourrait avoir un algo en $\mathcal O(n * log(n))$ où $n$ est le nombre d’aventuriers (avec un Dijkstra propre).

import pprint
import sys

pp = pprint.PrettyPrinter(indent=4)

def traverse(t):
    # l’enseble des états
    states = [(False, False, len(t) - 2)] + [(True, True, x) for x in range(len(t) - 1)] + [(True, False, x) for x in range(len(t) - 1)]

    # liste d’adjacence
    adj_list = {}
    for state in states:
        x = state[2]
        if state[0] == True and state[1] == True:
            if (x == len(t) - 2):
                adj_list[state] = [(False, False, x, t[1], [(1, 2)])]
            else:
                adj_list[state] = [(True, False, x, t[1] + t[0], [(1, 2), (1)])]
        elif state[0] == True and state[1] == False:
            if (x == len(t) - 3):
                adj_list[state] = [(False, False, x+1, t[-(x+1)], [(1, 3)])]
            else:
                adj_list[state] = [
                    (True, False, x+1, t[-(x+1)] + t[0], [(1, len(t) - x), (1)]), # petit + gros + petit revient
                    (True, True, x+2, t[-(x+1)] + t[1], [(len(t) - x, len(t) - x + 1), (2)]), # 2 gros + 2eme petit revient 
                ]

    # notre PQ avec les traversées courante en plus pour les récupérer à la fin
    pq = {}
    for state in states:
       pq[state] = (sys.maxsize, [])
    pq[(True, True, 0)] = (0, [])

    # dijkstra
    while(len(pq)):
      min_k = None
      min_v = sys.maxsize
      min_pred = []
      for k, (v, pred) in pq.items():
          if (v <= min_v):
              min_k = k
              min_v = v
              min_pred = pred
      pq.pop(min_k)
      if (min_k == (False, False, len(t) - 2)):
          return min_v, min_pred

      for neighbor in adj_list[min_k]:
          neighbor_k = neighbor[0:3]
          neighbor_cost = neighbor[3]
          neighbor_pred = neighbor[4]

          try:
              (neighbor_current_cost, _) = pq[neighbor_k]
              if (neighbor_cost + min_v < neighbor_current_cost):
                  pq[neighbor_k] = neighbor_cost + min_v, min_pred + neighbor_pred
          except KeyError:
              pass

  
tests = [
  [10, 20, 30],
  [1, 2, 5, 10],
  [1, 3, 4, 6],
]

for t in tests:
    pp.pprint(traverse(t))

# Affiche
# (60, [(1, 2), 1, (1, 3)])
# (17, [(1, 2), 1, (4, 5), 2, (1, 2)])
# (15, [(1, 2), 1, (1, 4), 1, (1, 3)])

En partant de mon observation qu’il existe toujours (du moins dans mes tests) une solution optimale de la forme :

1. les deux plus rapides traversent, un des deux revient puis les deux plus lents traversent, le plus rapide de l’autre côté revient ;
2. à un certain point, le plus rapide traverse avec le plus lent et revient s’il y a encore quelqu’un à chercher.

J’ai pondu un petit algo en $O(n \log n)$ avec n le nombre de personnes. Je commence par trier la liste des vitesses en ordre croissant. Ensuite suivant les coûts des cas 1 vs cas 2 je choisis le mouvement optimal. Dans tous les cas de figures j’ai à l’issue de la procédure les deux plus rapides avant le pont et les deux plus lents de l’autre côté. Je résous ensuite récursivement le problème avec comme cas d’arrêt ceux où il n’y a plus que 1 ou 2 personnes (la ou les plus rapides) à faire traverser, ainsi que le cas à 3 personnes puisqu’en général je gère les cas où il y a au moins deux plus rapides et deux plus lents.

def solve(w):
    w.sort()
    if len(w)==0:
        return 0,[]
    elif len(w)==1:
        return w[0],[w[0]]
    elif len(w)==2:
        return w[1], [(w[0],w[1])]
    elif len(w)==3:
        # (0,1), 0, (0,2)
        return w[1]+w[0]+w[2], [ (w[0],w[2]), w[0], (w[0],w[1]) ]
    else:
        # cas 1: les deux plus rapides puis les deux plus lents
        #        (0,1),  0,     (-2,-1), 1
        cost1 =   w[1] + w[0] + w[-1] +  w[1]
        # cas 2: le plus rapide avec les deux plus lents à chaque traversée
        #        (0,-1), 0,     (0,-2), 0
        cost2 =  w[-1] + w[0] + w[-2] + w[0]

        if (cost1<cost2):
            cost = cost1
            moves = [ (w[0],w[1]), w[0], (w[-2],w[-1]), w[1] ]
        else:
            cost = cost2
            moves = [ (w[0],w[-1]), w[0], (w[0],w[-2]), w[0] ]
        subcost, submoves = solve(w[0:-2])
        return cost+subcost, moves+submoves

Cela semble faire l’affaire, mais cela reste à prouver. On pourrait également dérécursiver pour trouver le point de bascule entre les deux stratégies …

Ton algorithme compare quelle est la manière la plus performante de faire passer les deux plus lents et je pense qu’il est exhaustif dans les combinaisons qu’il essaie

Oui j’ai pas fait l’observation que je pouvais traiter les deux plus lents de manière systématique

Le principe est de tout d’abord déterminer la sous-chaine de longueur maximale contenant au plus un 0. C’est peut-être la partie la moins évidente, on maintient deux indices r et l dans la chaine, r avance systématiquement mais l n’avance que si la sous-chaine comprise entre l et r contient plus de un 0. r-l ne peut donc augmenter que quand la sous-chaine n’en contient qu’un au plus.

Ensuite c’est plus simple, on recherche d’abord le 0 à échanger (forcément unique) dans la sous-chaine, puis le 1 à échanger en dehors de la sous-chaine. Si le 0 n’est pas trouvé, le Big Schwap n’est pas possible. Si le 1 n’est pas trouvé, le Big Schwap est toujours possible si le 0 ne se situe pas à l’une des extrémités de la sous-chaine, en choisissant l’une d’elles.

Si je ne me trompe pas, la complexité est bien linéaire en temps (au pire 2 parcours complets de la chaine) et constante en espace (la fonction schwappable ne crée que des variables scalaires).

#include <stdio.h>
#include <stdlib.h>

int schwappable(char *, int *, int *);
int search_digit(char *, int, int, int, int *);

int main(int argc, char *argv[]) {
	int zero, one, r;
	if (argc != 2) {
		fprintf(stderr, "Usage: %s <binary string>\n", argv[0]);
		fflush(stderr);
		return EXIT_FAILURE;
	}
	r = schwappable(argv[1], &zero, &one);
	if (r == 1) {
		printf("Big Schwap found! Swap 0 at index %d with 1 at index %d.\n", zero, one);
	}
	else if (r == 0) {
		puts("Big Schwap not found.");
	}
	else {
		puts("Argument is not a binary string.");
	}
	fflush(stdout);
	return EXIT_SUCCESS;
}

int schwappable(char *str, int *zero, int *one) {
	int r, zeros = 0, l = 0, r_max = 0, l_max = 0;

	/* Search for the longest substring which contains at most one 0 */
	for (r = 0; str[r]; r++) {
		if (str[r] == '0') {
			zeros++;
		}
		else if (str[r] != '1') {
			return -1;
		}
		if (zeros > 1) {
			if (str[l] == '0') {
				zeros--;
			}
			l++;
		}
		if (r-l > r_max-l_max) {
			r_max = r;
			l_max = l;
		}
	}

	/* Check substring length */
	if (r_max-l_max < 1) {
		return 0;
	}

	/* Search for a 0 inside the substring */
	if (!search_digit(str, l_max, r_max+1, '0', zero)) {
		return 0;
	}

	/* Search for a 1 outside of the substring for the swap */
	if (!search_digit(str, 0, l_max, '1', one) && !search_digit(str, r_max+1, r, '1', one)) {

		/* If search fails and either first or last character of substring is 0, the Big Schwap cannot happen */
		if (*zero == l_max || *zero == r_max) {
			return 0;
		}

		/* Otherwise choose the first character of substring */
		*one = l_max;
	}
	return 1;
}

int search_digit(char *str, int a, int b, int val, int *pos) {
	for (*pos = a; *pos < b && str[*pos] != val; *pos += 1);
	return *pos < b;
}