Marathon d'algorithmes

a marqué ce sujet comme résolu.

@Tchaïkovski: oui, je pense que le 0 représente la première case du tableau et pas une case qui contient 0. La deuxième interprétation n’est pas très intéressante puisque cela voudrais dire que le joueur ne peut jamais bouger.

@fifo: Je ne connaissait pas cette notation, mais oui, le problème n’a pas de solution (connu) en temps polynomial. Je ne pense pas qu’implémenter une solution soit si difficile que ça, mais vu que ça reste quand même nettement plus difficile que les problèmes précédents je vais un changer le problème pour passer d’une solution optimale à une "bonne" solution.

+0 -0

Dans ce cas voici une tentative en Python. :D 

def list_scheduling(tasks, machine_count):
	"""
	Returns a schedule as a list of tuples (key, machine, start_time),
	where `key` is the task key, `machine` is the selected resource and
	`start_time` is the time at which the task execution will begin,
	as well as the corresponding makespan (i.e., the maximum completion
	time among the tasks).

	This yields a (2-1/machine_count)-approximation as it uses a
	list-scheduling algorithm.
	"""
	# Schedule structure
	sched = [(key, -1, -1) for key, _, _ in tasks]
	
	# Mark the state of each task
	waiting = [key for key, _, dependencies in tasks if len(dependencies) > 0]  # Not-ready tasks, waiting for dependencies
	ready = [key for key, _, dependencies in tasks if len(dependencies) <= 0]   # Ready tasks (i.e., all dependencies are completed)
	pending = []                                                                # Started tasks, not yet completed
	completed = []                                                              # Completed tasks

	# Keep track of the temporary start time on each machine
	start_times = [0 for machine in range(machine_count)]
	
	while len(waiting) > 0 or len(ready) > 0:
		# Get the machine with the earliest start time
		machine = min(range(machine_count), key=lambda index: start_times[index])
		current_time = start_times[machine]

		# Mark completed tasks
		_pending = []
		for key in pending:
			if sched[key][2] + tasks[key][1] <= current_time:
				completed.append(key)
			else:
				_pending.append(key)
		pending = _pending

		# Mark ready tasks; a task becomes ready if its dependencies are completed
		_waiting = []
		for key in waiting:
			if all(dep in completed for dep in tasks[key][2]):
				ready.append(key)
			else:
				_waiting.append(key)
		waiting = _waiting

		if len(ready) > 0:
			# At least one task is ready; mark it as pending
			# and add it to the schedule
			key = ready.pop(0)
			pending.append(key)

			# Update the schedule
			sched[key] = (key, machine, current_time)
			# Update current start time
			start_times[machine] += tasks[key][1]
		else:
			# No task is ready; jump to the next time where a pending task will complete
			min_start_time = min(sched[key][2] + tasks[key][1] for key in pending)
			for machine in range(machine_count):
				start_times[machine] = max(start_times[machine], min_start_time)

	return sched, max(start_times)


# Example

MACHINE_COUNT = 2
TASKS = [(0, 5, []), (1, 5, [0]), (2, 10, [])]

sched, makespan = list_scheduling(TASKS, MACHINE_COUNT)

print(f"Instance with {len(TASKS)} tasks and {MACHINE_COUNT} machines:")
for key, duration, dependencies in TASKS:
	print(f"\tTask {key} - Duration = {duration} - Dependencies = {dependencies}")

print(f"\nSchedule (makespan = {makespan}):")
for key, machine, start_time in sched:
	print(f"\tTask {key} starts on machine {machine} at time {start_time}")

L’idée est d’utiliser un algorithme de liste pour produire une (2−1/m)(2-1/m)-approximation (avec mm le nombre de machines), qui est un résultat classique en théorie de l’ordonnancement1. Cela ne donne donc pas systématiquement une solution optimale, mais ça a l’avantage d’être relativement simple tout en garantissant une "assez bonne" solution.

EDIT : simplification et ajout de la source.

EDIT 2 : corrections.

EDIT 3 : corrections (je ne suis décidément pas un expert de Python !).

  1. Graham, R. L. (1966). Bounds for certain multiprocessing anomalies. Bell system technical journal, 45(9), 1563–1581.↩
+1 -0

Voici une solution en C.

Le principe est basique et ne produira pas une solution optimale (ok cependant pour les cas très simples fournis par Berdes).

A chaque étape de la résolution, on choisit une machine, et une tâche à assigner à cette machine:

  • La machine choisie est celle ou le moins de temps a été consommé.
  • La tâche choisie doit être éligible (tous ses prédécesseurs déjà assignés) et sera celle qui pourra démarrer au plus tôt sur la machine choisie. En cas d’égalité entre deux tâches sur ce critère, celle qui sera choisie sera la plus longue en durée.

Les données sont lues sur l’entrée standard, je fournirai des exemples du format attendu un peu plus tard :)

EDIT Format attendu pour la 3ème entrée du sujet

EDIT2 Suppression de l’appel récursif du solveur, remplacé par une boucle

3     # Nombre de tâches
5     # Tâche 0 - Durée
0     # Tâche 0 - Nb prédecesseurs
5     # Tâche 1 - Durée
1     # Tâche 1 - Nb prédecesseurs
0     # Tâche 1 - Index prédecesseur 1
10    # Tâche 2 - Durée
0     # Tâche 2 - Nb prédecesseurs
2     # Nombre de machines

Sortie correspondante

Id 0 Machine 1 Start 0
Id 1 Machine 1 Start 5
Id 2 Machine 0 Start 0
Total duration 10

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

typedef struct {
	int id;
	int elapsed;
}
machine_t;

typedef struct task_s task_t;

struct task_s {
	int id;
	int duration;
	int predecessors_n;
	int *predecessors;
	machine_t *machine;
	int start;
	task_t *last;
	task_t *next;
};

int set_task(task_t *, int);
void set_machine(machine_t *, int);
void solve(void);
int is_eligible_task(task_t *);
void print_task(task_t *);
void link_tasks(task_t *, task_t *);
void free_tasks(int);

int tasks_n, machines_n;
machine_t *machines;
task_t *tasks, *tasks_header;

int main(void) {
	int i;

	/* Initialisation des tâches */
	if (scanf("%d", &tasks_n) != 1 || tasks_n < 1) {
		fprintf(stderr, "Invalid number of tasks\n");
		fflush(stderr);
		return EXIT_FAILURE;
	}
	tasks = malloc(sizeof(task_t)*(size_t)(tasks_n+1));
	if (!tasks) {
		fprintf(stderr, "Could not allocate memory for tasks\n");
		fflush(stderr);
		return EXIT_FAILURE;
	}
	for (i = 0; i < tasks_n; i++) {
		if (!set_task(tasks+i, i)) {
			free_tasks(i);
			return EXIT_FAILURE;
		}
	}
	tasks_header = tasks+tasks_n;
	link_tasks(tasks_header, tasks);
	for (i = 0; i < tasks_n; i++) {
		link_tasks(tasks+i, tasks+i+1);
	}

	/* Initialisation des machines */
	if (scanf("%d", &machines_n) != 1 || machines_n < 1) {
		fprintf(stderr, "Invalid number of machines\n");
		fflush(stderr);
		free_tasks(tasks_n);
		return EXIT_FAILURE;
	}
	machines = malloc(sizeof(machine_t)*(size_t)machines_n);
	if (!machines) {
		fprintf(stderr, "Could not allocate memory for machines\n");
		fflush(stderr);
		free_tasks(tasks_n);
		return EXIT_FAILURE;
	}
	for (i = 0; i < machines_n; i++) {
		set_machine(machines+i, i);
	}

	/* Lancement du solveur */
	solve();

	/* Fin du programme */
	free(machines);
	free_tasks(tasks_n);
	return EXIT_SUCCESS;
}

/* Initialisation d'une tâche */
int set_task(task_t *task, int id) {
	int predecessor_idx, i;
	task->id = id;
	if (scanf("%d", &task->duration) != 1 || task->duration < 1) {
		fprintf(stderr, "Invalid duration\n");
		fflush(stderr);
		return 0;
	}
	if (scanf("%d", &task->predecessors_n) != 1 || task->predecessors_n < 0) {
		fprintf(stderr, "Invalid number of predecessors\n");
		fflush(stderr);
		return 0;
	}
	if (task->predecessors_n > 0) {
		task->predecessors = malloc(sizeof(int)*(size_t)task->predecessors_n);
		if (!task->predecessors) {
			fprintf(stderr, "Could not allocate memory for predecessors\n");
			fflush(stderr);
			return 0;
		}
	}
	for (i = 0; i < task->predecessors_n; i++) {
		if (scanf("%d", &predecessor_idx) != 1 || predecessor_idx < 0 || predecessor_idx >= tasks_n || predecessor_idx == id) {
			fprintf(stderr, "Invalid predecessor\n");
			fflush(stderr);
			free(task->predecessors);
			return 0;
		}
		task->predecessors[i] = predecessor_idx;
	}
	task->machine = NULL;
	return 1;
}

/* Initialisation d'une machine */
void set_machine(machine_t *machine, int id) {
	machine->id = id;
	machine->elapsed = 0;
}

/* Solveur */
void solve(void) {
	int i;
	while (tasks_header->next != tasks_header) {
		machine_t *machine_min;
		task_t *task_min, *task;

		/* Recherche de la machine à laquelle assigner une tâche */
		machine_min = machines;
		for (i = 1; i < machines_n; i++) {
			if (machines[i].elapsed < machine_min->elapsed) {
				machine_min = machines+i;
			}
		}

		/* Recherche de la tâche à assigner */
		task_min = tasks_header;
		for (task = tasks_header->next; task != tasks_header; task = task->next) {
			task->start = machine_min->elapsed;
			if (is_eligible_task(task) && (task_min == tasks_header || task->start < task_min->start || (task->start == task_min->start && task->duration > task_min->duration))) {
				task_min = task;
			}
		}

		/* Aucune tâche éligible trouvée, impossible de trouver une solution */
		if (task_min == tasks_header) {
			break;
		}

		/* Assignation de la tâche à la machine */
		machine_min->elapsed += task_min->start+task_min->duration-machine_min->elapsed;
		task_min->machine = machine_min;
		link_tasks(task_min->last, task_min->next);
	}

	/* Si toutes les tâches ont été assignées, affichage de la solution */
	if (tasks_header->next == tasks_header) {
		machine_t *machine_max;
		for (i = 0; i < tasks_n; i++) {
			print_task(tasks+i);
		}
		machine_max = machines;
		for (i = 1; i < machines_n; i++) {
			if (machines[i].elapsed > machine_max->elapsed) {
				machine_max = machines+i;
			}
		}
		printf("Total duration %d\n", machine_max->elapsed);
		fflush(stdout);
	}
}

/* Test de l'égibilité d'une tâche et calcul de son démarrage au plus tôt */
int is_eligible_task(task_t *task) {
	int i;
	for (i = 0; i < task->predecessors_n; i++) {
		task_t *predecessor = tasks+task->predecessors[i];
		if (!predecessor->machine) {
			return 0;
		}
		if (predecessor->start+predecessor->duration > task->start) {
			task->start = predecessor->start+predecessor->duration;
		}
	}
	return 1;
}

/* Affichage d'une tâche assignée */
void print_task(task_t *task) {
	printf("Id %d Machine %d Start %d\n", task->id, task->machine->id, task->start);
}

/* Chainage de deux tâches */
void link_tasks(task_t *last, task_t *next) {
	last->next = next;
	next->last = last;
}

/* Libération de la mémoire des tâches */
void free_tasks(int tasks_max) {
	int i;
	for (i = 0; i < tasks_max; i++) {
		if (tasks[i].predecessors_n > 0) {
			free(tasks[i].predecessors);
		}
	}
	free(tasks);
}
+1 -0

En cas d’égalité entre deux tâches sur ce critère, celle qui sera choisie sera la plus longue en durée.

fromvega

Bonne idée ! La stratégie LPT (Longest Processing Time) est efficace pour le problème sans contrainte de précédence (et même asymptotiquement optimale il me semble), c’est pas bête de l’utiliser dans ce cas précis. Je me demande si ça améliore le ratio d’approximation.

+0 -0

@fifo: ta solution me semble correcte, je te passe la main.

L’idée générale est bonne, mais j’ai l’impression qu’il y aurait moyen d’améliorer la qualité de la planification en exécutant en priorité les tâches qui sont les plus critiques en terme de dépendances. Le score de priorité d’une tâche TT peut être donné par le temps d’exécution maximum nécessaire pour exécuter toutes les tâches qui dépendent directement ou indirectement de TT en supposant un parallélisme infini.

En utilisant cette priorité, on se garantie d’exécuter l’exemple suivant de manière optimale:

Tâches: [{id: 1, durée: 5, dépendances: []},
         {id: 2, durée: 5, dépendances: [1]},
         {id: 3, durée: 5, dépendances: []},
         {id: 4, durée: 5, dépendances: []}]
Nombre de machines: 2

La tâche 1 a une priorité de 10 alors que les tâches 3 et 4 ont une priorité de 5. La tâche 1 démarre immédiatement en même temps que 3 ou 4. Tout sera fini après 10 unités de temps. Avec ton algo, il est possible de lancer 3 et 4 au début et de se retrouver à commencer 1 après 5 unités de temps, ce qui délaye la fin d’exécution à 15 unités de temps. Par contre, j’ai aucune idée de si ça améliore le ratio d’approximation.

Sur l’implémentation en elle-même, je pense qu’il y a moyen d’améliorer le trucs nettement en utilisant des files de priorités pour éviter de parcourir tes listes entièrement en permanence. Au passage, l’utilisation de tuples rend le code peu lisible parce que ce n’est pas clair ce que le [1] représente dans une expression tel que [tasks[key][1].

@fromvega: ta solution me semble aussi correcte, mais j’ai eu un peu de mal pour suivre le code. Les commentaires au sein du code aident bien, mais il aurait probablement été utile d’avoir une explication un peu plus haut-niveau sur les structures de données utilisés. Il y a deux points non-triviaux qui rendent les choses compliqués à comprendre:

  • Les tâches sont à la fois dans un tableau (pour les stocker) et une liste doublement chaînée qui contient uniquement les tâches qui ne sont pas encore planifiés. Et il y a une fausse tâche pour désigner la fin de la liste.
  • La fonction solve est récursive. Pour le coup, j’ai vraiment du mal à comprendre pourquoi. Les lignes 182 à 185 ne me semble pas particulièrement utile puisqu’elles sont exécutés uniquement une fois que la résolution est fini et qu’il est temps de désallouer les ressources. À partir de là, au lieux d’avoir une fonction récursive, on peut simplement utiliser une boucle while(tasks_header->next != tasks_header) et afficher la solution une fois la boucle fini.

Edit: Et tant que j’y suis, voici ma première solution. C’est globalement le même principe que vos deux solutions, mais en utilisant une file de priorité pour savoir quand la prochaine tâche se fini. La complexité est de O(D+Tlog⁡(M))\mathcal{O}(D + T\log(M)) avec DD le nombre de liens de dépendances, TT le nombre de tâches et MM le nombre de machines.

#include <iostream>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

struct Task {
  int id;
  int execution_time;
  std::vector<int> dependencies;
};
std::ostream& operator<<(std::ostream& os, const Task& t) {
  os << "Task {id=" << t.id << ", execution_time=" << t.execution_time
     << ", dependencies=[";
  int i = 0;
  for (const int dep : t.dependencies) {
    os << dep;
    if (i < t.dependencies.size() - 1) {
      os << ", ";
    }
    ++i;
  }
  os << "]}";
  return os;
}

struct TaskSchedule {
  int id;
  int machine;
  int start_time;
};
std::ostream& operator<<(std::ostream& os, const TaskSchedule& t) {
  os << "Execute task " << t.id << " on machine " << t.machine << " at time "
     << t.start_time;
  return os;
}

std::pair<std::vector<TaskSchedule>, int> Solve(const std::vector<Task>& tasks,
                                                const int num_machines) {
  if (tasks.empty() || num_machines <= 0) {
    return {};
  }

  // Copy tasks to an internal format and create:
  //   1. a map of id to task
  //   2. a list of available tasks
  struct InternalTask {
    int execution_time;
    std::unordered_set<int> dependencies;
    // List of tasks that have a dependency on this one.
    std::vector<int> next_tasks;
  };
  std::unordered_map<int, InternalTask> task_map;
  std::queue<int> available_tasks;
  for (const Task& t : tasks) {
    task_map[t.id].execution_time = t.execution_time;
    task_map[t.id].dependencies.insert(t.dependencies.begin(),
                                       t.dependencies.end());
    if (t.dependencies.empty()) {
      available_tasks.push(t.id);
    }
    for (const int id : t.dependencies) {
      task_map[id].next_tasks.push_back(t.id);
    }
  }

  // Heap of when tasks are going to finish.
  struct TaskExecution {
    int machine_id;
    int task_id;
    int end_time;
    bool operator<(const TaskExecution& other) const {
      return end_time > other.end_time;
    }
  };
  std::priority_queue<TaskExecution> end_times;

  // List of available machines.
  std::queue<int> available_machines;
  for (int i = 0; i < num_machines; ++i) {
    available_machines.push(i);
  }

  int current_time = 0;
  std::vector<TaskSchedule> schedule;
  do {
    // Schedule tasks we have both available tasks and machines.
    while (!available_tasks.empty() && !available_machines.empty()) {
      const int machine = available_machines.front();
      available_machines.pop();
      const int task = available_tasks.front();
      available_tasks.pop();

      end_times.push(
          {machine, task, current_time + task_map[task].execution_time});
      schedule.push_back({task, machine, current_time});
    }
    // Go to the next finished task.
    const auto [machine_id, task_id, end_time] = end_times.top();
    end_times.pop();
    available_machines.push(machine_id);
    current_time = end_time;
    // Potentially free up tasks depending on the finished one.
    for (const int next_task : task_map[task_id].next_tasks) {
      task_map[next_task].dependencies.erase(task_id);
      if (task_map[next_task].dependencies.empty()) {
        available_tasks.push(next_task);
      }
    }
  } while (!available_tasks.empty() || !end_times.empty());
  return {schedule, current_time};
}

void PrintSolution(const std::vector<Task>& tasks, const int num_machines) {
  std::cout << "Tasks:\n";
  for (const Task& t : tasks) {
    std::cout << "  - " << t << "\n";
  }
  std::cout << "Number of machines: " << num_machines << "\n";
  std::cout << "Solution:\n";
  const auto [scheduling, end_time] = Solve(tasks, num_machines);
  for (const TaskSchedule& t : scheduling) {
    std::cout << "  - " << t << "\n";
  }
  std::cout << "End time: " << end_time << "\n\n";
}

int main() {
  PrintSolution({}, 1);
  PrintSolution({}, 2);
  PrintSolution({{1, 5, {}}}, 1);
  PrintSolution({{1, 5, {}}}, 2);
  PrintSolution({{1, 5, {}}, {2, 5, {1}}}, 1);
  PrintSolution({{1, 5, {}}, {2, 5, {1}}}, 2);
  PrintSolution({{1, 5, {}}, {2, 5, {1}}, {3, 10, {}}}, 1);
  PrintSolution({{1, 5, {}}, {2, 5, {1}}, {3, 10, {}}}, 2);
  PrintSolution({{1, 5, {}}, {2, 5, {1}}, {3, 5, {}}, {4, 5, {}}}, 2);
  PrintSolution({{1, 5, {}}, {2, 5, {}}, {3, 5, {1, 2}}}, 2);
}
+1 -0

L’idée générale est bonne, mais j’ai l’impression qu’il y aurait moyen d’améliorer la qualité de la planification en exécutant en priorité les tâches qui sont les plus critiques en terme de dépendances. Le score de priorité d’une tâche TT peut être donné par le temps d’exécution maximum nécessaire pour exécuter toutes les tâches qui dépendent directement ou indirectement de TT en supposant un parallélisme infini.

Berdes

Oui j’ai voulu utiliser un algo assez simple, mais on peut sans doute faire mieux (au moins pour une majorité d’instances) en choisissant un mécanisme de priorité plus pertinent. La méthode du chemin critique est sans doute une bonne piste.

Sur l’implémentation en elle-même, je pense qu’il y a moyen d’améliorer le trucs nettement en utilisant des files de priorités pour éviter de parcourir tes listes entièrement en permanence. Au passage, l’utilisation de tuples rend le code peu lisible parce que ce n’est pas clair ce que le [1] représente dans une expression tel que [tasks[key][1].

Berdes

Absolument, l’implémentation en elle-même est médiocre, je suis allé vite (et je ne suis pas très bon en Python). :-°

Je réfléchis à un problème sympa !

+0 -0

@fromvega: ta solution me semble aussi correcte, mais j’ai eu un peu de mal pour suivre le code. Les commentaires au sein du code aident bien, mais il aurait probablement été utile d’avoir une explication un peu plus haut-niveau sur les structures de données utilisés. Il y a deux points non-triviaux qui rendent les choses compliqués à comprendre:

  • Les tâches sont à la fois dans un tableau (pour les stocker) et une liste doublement chaînée qui contient uniquement les tâches qui ne sont pas encore planifiés. Et il y a une fausse tâche pour désigner la fin de la liste.
  • La fonction solve est récursive. Pour le coup, j’ai vraiment du mal à comprendre pourquoi. Les lignes 182 à 185 ne me semble pas particulièrement utile puisqu’elles sont exécutés uniquement une fois que la résolution est fini et qu’il est temps de désallouer les ressources. À partir de là, au lieux d’avoir une fonction récursive, on peut simplement utiliser une boucle while(tasks_header->next != tasks_header) et afficher la solution une fois la boucle fini.
Berdes

Merci pour tes retours, tu as raison sur tous ces points. Pour la récursivité j’étais parti sur une 1ère solution optimale avec plusieurs choix possibles à chaque étape d’où le backtrack. Puis j’ai abandonné car trop complexe mais j’ai conservé la fonction récursive. Je vais éditer mon programme pour améliorer ça :)

+0 -0

Voici un petit problème ma foi assez simple, mais dont j’aime l’élégance des solutions.

Algo n°4

Détection de cycle dans une suite ultimement périodique

Soient EE un ensemble fini et f:E→Ef:E\to E une fonction donnée. Considérons la suite xi=f(xi−1)x_i=f(x_{i-1}) pour tout i>0i>0, avec x0∈Ex_0\in E. Étant donnés ff et x0x_0, trouver deux indices jj et kk tels que j≠kj\ne k et xj=xkx_j=x_k.

Entrée :
  • Une fonction ff telle que précédemment définie (attention: on suppose qu’on ne connaît ni EE, ni le cardinal de EE);
  • L’élement initial x0∈Ex_0\in E.
Sortie :
  • Un couple (j,k)(j,k) tel que xj=xkx_j=x_k.
Exemple :

Soient E={0,1,2,3,4,5}E=\{0,1,2,3,4,5\}, x0=0x_0=0 et ff telle que :

x f(x)
0 1
1 2
2 3
3 4
4 5
5 2

Solution : (4,8)(4,8)

Contrainte obligatoire :

Donner un algorithme ayant une complexité en espace de O(1)O(1).

Bonus :

En plus du couple (j,k)(j,k), donner la longueur du cycle et le nombre d’éléments en dehors du cycle. Dans l’exemple donné, il y a 4 éléments dans le cycle et 2 éléments à l’extérieur du cycle.

EDIT : précision sur le paramètre d’entrée ff.

+2 -0

Ah, le bon vielle algo du lièvre et de la tortue!

Puisqu’on est sur une solution élégante, autant la faire dans un langage élégant. Voici ma solution en Haskell:

import Data.List

main :: IO ()
main = do
  print . take 10 $ iterate f1 0
  print $ solve f1 0
  print . take 10 $ iterate f2 0
  print $ solve f2 0
  print . take 10 $ iterate f3 0
  print $ solve f3 0
  print . take 10 $ iterate f4 0
  print $ solve f4 0
  where f1 x = (x + 1) `mod` 4
        f2 x = (x + 2) `mod` 5
        f3 x = x
        f4 0 = 1
        f4 1 = 2
        f4 x = ((x + 1) `mod` 4) + 2

-- Returns a list of matching elements and their indices
getMatches :: Eq a => [a] -> [a] -> [(a, Int)]
getMatches [] _ = []
getMatches _ [] = []
getMatches (x:xs) (y:ys)
  | x == y    = (x, 0):otherMatches
  | otherwise = otherMatches
  where otherMatches = [(a, i+1) | (a, i) <- getMatches xs ys]

-- Outputs the length of the cycle and the number of elements before the cycle
solve :: Eq a => (a -> a) -> a -> (Int, Int)
solve f x0 = (mu, lambda)
  where -- First position at which the hare and tortoise have the same value
        _:(x_m, m):_ = getMatches (iterate f x0) (iterate (f . f) x0)
        -- Number of elements outside the cycle
        (x_lambda, lambda):_ = getMatches (iterate f x0) (iterate f x_m)
        -- Length of the cycle
        _:mu:_ = elemIndices x_lambda $ iterate f x_lambda

Petite explication pour ceux qui ne seraient pas familier avec le Haskell.

Ligne 33, iterate f x0 donne une liste infini contenant [x0, f(x0), f(f(x0)), …]. iterate (f . f) x0 fait la même chose mais en appliquant f deux fois à chaque itération. getMatches nous donne la liste (infini) des éléments égaux entre les deux liste et leur position. Le premier élément des deux liste est x0x_0, donc on ignore cette première égalité. Le deuxième élément correspond à la première fois que le lièvre et la tortue ont la même valeur xmx_m.

Ligne 35, on fait quelque chose de similaire mais en cherchant le plus petit λ\lambda tel que fλ(x0)=fλ(xm)f^{\lambda}(x_0) = f^{\lambda}(x_m). λ\lambda correspond au nombre d’élément avant le cycle.

Ligne 37, on cherche le plus petit μ>0\mu > 0 tel que fμ(xλ)=xλf^{\mu}(x_{\lambda}) = x_{\lambda}. μ\mu correspond à la longueur du cycle. Là encore, on ignore la première égalité parce que le premier élément de iterate f x_lambda est x_lambda.

Si le compilo Haskell est assez intelligent, l’algo devrait être effectivement en O(1)\mathcal{O}(1), mais mon petit doigt me dit que c’est pas le cas :D

Je préfère laisser d’autres personnes participer, donc je ne prends pas la main (si ma solution est correcte).

+1 -0

La solution est pas du tout unique ? Avant de faire la suite, je me rends bien compte que (2,6)(2, 6) est solution. J’avoue que j’ai eu du mal avec l’énoncé. Au début, j’ai bloqué sur « ben (0,0)(0, 0) » >_<, puis sur l’unicité (ça c’est moi), puis je me suis emmêle avec EE vs les indices. Et maintenant sur la signification de O(1)O(1) (si je dois lire ff sur l’entré standard sans la stocker ou pas).

Je sais pas trop si ma solution pourra être acceptée en O(1)O(1), je stocke ff quand même.

x_0 = 0
f = {
        0: 1,
        1: 2,
        2: 3,
        3: 4,
        4: 5,
        5: 2,
    }
nbE = len(f.keys())


x_nbE = x_0
for i in range(nbE):
    x_nbE = f[x_nbE]

x_n = x_0
for i in range(nbE):
    if x_n == x_nbE:
        print (i, nbE)
        break

    x_n = f[x_n]

L’idée si j’ai bien compris c’est que x#Ex_{\#E} est forcément redondant (euh je l’ai pas prouvé mais il est forcément dans le cycle d’après moi). Du coup, je le calcule le retrouve dans la suite.

J’ai le sentiment de pas avoir compris un truc.

+0 -0

La solution est pas du tout unique ? Avant de faire la suite, je me rends bien compte que (2,6)(2, 6) est solution.

ache

C’est exact, il y a effectivement une infinité de couples (j,k)(j,k) (avec j≠kj\ne k) qui sont solutions.

J’avoue que j’ai eu du mal avec l’énoncé. Au début, j’ai bloqué sur « ben (0,0)(0, 0) » >_<, puis sur l’unicité (ça c’est moi), puis je me suis emmêle avec EE vs les indices. Et maintenant sur la signification de O(1)O(1) (si je dois lire ff sur l’entré standard sans la stocker ou pas).

ache

Je devrais effectivement préciser qu’on veut une solution (j,k)(j,k) telle que j≠kj\ne k. Quant à la signification de O(1)O(1), c’est sans compter l’espace occupé par ff (ici tu stockes ff explicitement, mais ça pourrait tout aussi bien être une simple fonction Python).

Je sais pas trop si ma solution pourra être acceptée en O(1)O(1), je stocke ff quand même.

x_0 = 0
f = {
        0: 1,
        1: 2,
        2: 3,
        3: 4,
        4: 5,
        5: 2,
    }
nbE = len(f.keys())


x_nbE = x_0
for i in range(nbE):
    x_nbE = f[x_nbE]

x_n = x_0
for i in range(nbE):
    if x_n == x_nbE:
        print (i, nbE)
        break

    x_n = f[x_n]

L’idée si j’ai bien compris c’est que x#Ex_{\#E} est forcément redondant (euh je l’ai pas prouvé mais il est forcément dans le cycle d’après moi). Du coup, je le calcule le retrouve dans la suite.

J’ai le sentiment de pas avoir compris un truc.

ache

Ta solution me semble correcte ! Si nn est le cardinal de EE, xnx_n est effectivement forcément dans le cycle. L’algorithme que tu proposes a bien une complexité en espace O(1)O(1), donc ça répond aux consignes.

La subtilité de ce problème est qu’il existe un algorithme ayant une complexité en temps O(n)O(n). Ta solution est en O(n2)O(n^2).

Par contre, c’est un peu tricher de supposer que tu connais EE ou nn. Ton algorithme ne fonctionne pas si ff n’est pas décrit explicitement comme tu le fais.

Mais disons que j’accepte la solution, les spécifications n’étaient pas assez précises (c’est ma faute), et tu t’en es sorti grâce à une astucieuse interprétation. ^^

EDIT : pardon, je dis n’importe quoi (fatigué !).

EDIT 2 : précisions.

+0 -0

Par contre, c’est un peu tricher de supposer que tu connais EE ou nn. Ton algorithme ne fonctionne pas si ff n’est pas décrit explicitement comme tu le fais.

Mais disons que j’accepte la solution, les spécifications n’étaient pas assez précises (c’est ma faute), et tu t’en es sorti grâce à une astucieuse interprétation. ^^

fifo

Désolé, j’avais effectivement le sentiment de tricher mais ce n’était pas mon intention. Ne connaissant pas l’algorithme du lièvre et de la tortue (et en m’interdisant d’aller y jeter un œil) j’ai vraiment eu du mal à m’imposer les bonnes contraintes. C’est un problème plutôt abstrait et j’ai pas l’habitude de ce genre de cas, pour moi ff était concret.

Bon du coup, je prend la main. J’ai essayé de trouver un truc pas super trivial, désolé s’il l’est ou si ma solution est fausse.

Algo n°5

Détermination du nombre de points à l’intérieur d’un polygone strictement convexe

Soit un polygone PP non dégénéré convexe défini par ses sommets sur Z2\mathbb{Z}^2 (et donc donné dans un ordre cohérent).
Déterminer le nombre de points de Z2\mathbb{Z}^2 à l’intérieur de ce polygone.

Entrée :

Une suite de points représentant les sommets de PP dans un ordre non dégénéré.

Sortie :

Le nombre de points entiers contenus dans PP.

Exemples :
Polygones Nombre de points intérieurs
((0,0),(0,1),(1,0))((0, 0), (0, 1), (1, 0)) 0
((2,5),(3,5),(4,4),(3,3),(2,4))((2, 5), (3, 5), (4, 4), (3, 3), (2, 4)) 1
((2,0),(3,0),(3,1),(2,1))((2, 0), (3, 0), (3, 1), (2, 1)) 0
Figures dessinant les polygones ci-dessus
Figures dessinant les polygones ci-dessus
Bonus :

Déterminer un algorithme linéaire en le nombre de sommets du polygone.

Surtout amusez-vous !

+1 -0

Voici ma proposition en C, linéaire en le nombre de sommets du polygone (ou de côtés, ça dépend comment on voit les choses :p ), le résultat est celui attendu pour les exemples donnés et quelques autres que j’ai testés.

EDIT Correction de la fonction calculant le nombre de points de coordonnées entières par côté.

En cherchant une solution au problème, je suis tombé sur le théorème de Pick, permettant de calculer l’aire d’un polygone (A), construit dans une grille points de coordonnées entières, en fonction du nombre de points du bord du polygone (b) et du nombre de points à l’intérieur du polygone (i).

A=i+b/2−1A = i + b/2 - 1

On peut déduire facilement de ce théorème une formule permettant de calculer i, le nombre que l’on recherche:

i=A−b/2+1i = A - b/2 + 1

L’aire du polygone correspondant à la valeur absolue de la somme des déterminants de chaque côté divisée par 2.

Le programme attend sur l’entrée standard le nombre de points du polygone, suivi des coordonnées de chaque points, puis effectue le calcul de la formule ci-dessus.

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

typedef struct {
	int x;
	int y;
}
point_t;

int determinant(point_t *, point_t *);
int points_on_edge(point_t *, point_t *);
int gcd(int, int);
int interior_points(double, int);

int main(void) {
	int points_n, determinants_sum, boundary_points, i;
	point_t *points;

	/* Initialisation du polygone */
	if (scanf("%d", &points_n) != 1 || points_n < 3) {
		fprintf(stderr, "Invalid number of points\n");
		fflush(stderr);
		return EXIT_FAILURE;
	}
	points = malloc(sizeof(point_t)*(size_t)points_n);
	if (!points) {
		fprintf(stderr, "Could not allocate memory for points\n");
		fflush(stderr);
		return EXIT_FAILURE;
	}
	for (i = 0; i < points_n; i++) {
		if (scanf("%d%d", &points[i].x, &points[i].y) != 2) {
			fprintf(stderr, "Invalid point\n");
			fflush(stderr);
			free(points);
			return EXIT_FAILURE;
		}
	}

	/* Calcul du déterminant et du nombre de points pour chaque côté */
	determinants_sum = determinant(points+points_n-1, points);
	boundary_points = points_on_edge(points+points_n-1, points);
	for (i = 1; i < points_n; i++) {
		determinants_sum += determinant(points+i-1, points+i);
		boundary_points += points_on_edge(points+i-1, points+i);
	}

	/* Calcul et affichage du nombre de points à l'intérieur du polygone */
	printf("interior points = %d\n", interior_points(abs(determinants_sum)/2.0, boundary_points));
	fflush(stdout);

	/* Fin du programme */
	free(points);
	return EXIT_SUCCESS;
}

int determinant(point_t *a, point_t *b) {
	return a->x*b->y-a->y*b->x;
}

int points_on_edge(point_t *a, point_t *b) {
	int dx = abs(a->x-b->x), dy = abs(a->y-b->y);
	if (dx > dy) {
		if (dy == 0) {
			return dx;
		}
		return gcd(dx, dy);
	}
	if (dx == 0) {
		return dy;
	}
	return gcd(dy, dx);
}

int gcd(int a, int b) {
	int m = a%b;
	if (m > 0) {
		return gcd(b, m);
	}
	return b;
}

int interior_points(double area, int boundary_points) {
	return (int)(area-boundary_points/2.0)+1;
}
+1 -0

Bien joué !

C’était également ma méthode, j’ai du étudié ça pour assister un de mes professeurs. Je suis étonné par ta méthode de calcul du nombre de pixels sur le bord. On a deux méthodes différentes également pour la calcul de l’air du polygone.

Bref, j’étudie ta solution. En attendant, voilà la mienne :

def gcd(a, b):
    """Return the Greater Commun Divisor of the two integers.

    The gcd of two integers different from zero is the largest **postive** integer
    that divides the two integers.

    Otherwise, if one of them is equal to zero, the gcd is the absolute value
    of the other integer. The gcd between 0 and 0 is set to 0 for convenience.
    >>> gcd(0, 0)
    0
    >>> gcd(12, 4)
    4
    >>> gcd(6, 8)
    2
    >>> gcd(21, 91)
    7
    >>> gcd(-1, -1)
    1
    >>> gcd(-1, 0)
    1
    """

    # An embed function to comptute gcd of two integers different from zero.
    # It's a recursive version of the Euclidean algorithm.
    def gcd_aux(a, b):
        return abs(a) if b == 0 else gcd_aux(b, a % b)

    if a == 0:
        return abs(b)
    if b == 0:
        return abs(a)
    return gcd_aux(a, b)


def computeConvexeArea(convexe):
    """ Compute the inside area of the convexe

        The basic idea is to compute the area of the trapezium made by the
        each vector and the ordinate axis. Easy to compute as if you replicate
        the trapezium you end up with a rectangle so the area of each
        trapezium is (b+B)*h/2.

    >>> computeConvexeArea([(0, 0), (1, 0), (1, 1), (0, 1)]) # The unit square
    1.0

    >>> computeConvexeArea([(0, 0), (1, 1), (1, 0)])
    0.5

    >>> computeConvexeArea([(0, 0), (5, 2), (3, 7), (-2, 5)]) # Pythagore said ...
    29.0
    """
    convexe = convexe + [convexe[0]]
    area = 0

    for i in range(len(convexe)-1):
        p1 = convexe[i]
        p2 = convexe[i+1]

        # Area = b+B * h / 2
        # h can be negative !
        # b+B = p1[0] + p2[0]
        # h = p2[1] - p1[1]

        area += (p1[0] + p2[0]) * (p2[1] - p1[1])

    # We divise by 2 at the last moment to keep it precise
    return area/2

def computeAngle(points):
    """
        Generate the angles (the vectors) of a polygone.
    """
    pts = points
    for i in range(len(points) - 1):
        yield (pts[i+1][0] - pts[i][0], pts[i+1][1] - pts[i][1])
    yield (pts[0][0] - pts[-1][0], pts[0][1] - pts[-1][1])

def countBorderPixels(angles):
    return sum(map(lambda x: gcd(*x), angles))

def reversePickFormula(pixBorder, area):
    """ Compute the number of internal pixels of a figure based
        on the area and reversed Pick formula

        If Area = pixBorder/2 + pixInside - 1
        Then pixInside = Area - pixBorder/2 + 1

    >>> reversePickFormula(14, 15)
    9
    >>> reversePickFormula(5, 2.5)
    1
    """
    # int() because, it can't be a floting number
    return int(area - pixBorder/2 + 1)


polys = [
    [(0, 0), (1, 0), (1, 1), (0, 1)],
    [(0, 0), (1, 1), (1, 0)],
    [(0, 0), (1, 1), (1, 0)],
    [(0, 0), (5, 2), (3, 7), (-2, 5)],
    [(0, 0), (6, 0), (6, -4)],
    [(0, 0), (1, 2), (2, 5), (1, 3)],
    [(2, 5), (3, 5), (4, 4), (3, 3), (2, 4)],
    [(2, 0), (3, 0), (3, 1), (2, 1)],
    [(0, 0), (6, 12), (12, 4)],
    [(4, 2), (5, 2), (3, -3), (0, 0)],
    [(4, 2), (7, 3), (3, -3), (0, 0)],
 ]

for poly in polys:
    print(reversePickFormula(countBorderPixels(computeAngle(poly)), abs(computeConvexeArea(poly))))
+1 -0

Je suis étonné par ta méthode de calcul du nombre de pixels sur le bord.

ache

Tu as raison d’être étonné :-° … Ma fonction ne marchait que si la différence entre les coordonnées du bord pour x et y sont premières entre elles. j’ai corrigé ma solution en utilisant le calcul du pgcd.

+0 -0

Je ne crois pas avoir eu le go officiel mais je me permet de relancer le marathon :) avec un nouveau problème pas compliqué à mon avis, mais demandant une petite dose de réflexion quand même.

Algo n°6

Prochain palindrome

Un nombre palindrome est un entier qui est le même quand il est lu en sens inverse en base 10, comme 12321 ou 9449.

Etant donné un nombre entier positif, trouvez le plus petit palindrome supérieur à ce nombre.

nextpal(808) => 818
nextpal(999) => 1001
nextpal(2133) => 2222

Contrainte

Votre solution doit être bien plus efficace que d’incrémenter et vérifier chaque nombre pour déterminer si c’est un palindrome.

Trouvez nextpal(3**39) avant de poster votre solution. Cela devrait être quasi-instantané ou prendre une fraction de seconde suivant votre langage de programmation.

Bonus

Faites évoluer votre solution afin qu’elle puisse trouver le prochain palindrome exprimé dans d’autres bases que la base 10.

Quel est le prochain palindrome de 256344510514743751332437247280545791 (que je laisse volontairement en base 10), exprimé en base 36 (chiffres [0..9A..Z]) ?

+0 -0

Je ne crois pas avoir eu le go officiel mais je me permet de relancer le marathon :)

fromvega

Oh pardon ! J’ai oublié, effectivement c’est à toi.

+1 -0

Ma solution en JS :

Ma solution pas très propre en js, j’ai pas trouvé comment gérer le cas spécifique où l’on a que des 9 de manière jolie.

L’idée : on coupe le nombre en deux. La première moitié doit forcément être égale à la première moitié précédente (ou la moitié précédente + 1) sinon le nouveau nombre n’est pas supérieur. On fait les deux cas et on renvoie le plus petit qui est supérieur à notre entrée.

Complexité en O(log10(num)+1)\mathcal{O}(log_{10}(num) + 1) non ?

const getLength = (num) => (num <= 9 || 1 + getLength(Math.floor(num / 10)));

const getPalFromHalf = (half, numLength) => {
  const firstHalf = half.toString();
  const secondHalf = (numLength % 2 ? firstHalf.slice(0, -1) : firstHalf)
    .split("")
    .reverse()
    .join("");

  return firstHalf + secondHalf;
};

const nextPalindrome = (num) => {
  /* Special case for number only made of 0 */
  const numCopy = num;
  let specialSolution = 1;
  while (num >= 9) {
    if (num === 9) {
      return specialSolution * 10 + 1;
    } else if (num % 10 === 9) {
      num = Math.floor(num / 10);
      specialSolution *= 10;
    } else {
      break;
    }
  }

  /* Generic case */
  num = numCopy;
  const numLength = getLength(num);
  for (let i = 0; i < Math.floor(numLength / 2); ++i) {
    num = Math.floor(num / 10);
  }
  const pal1 = getPalFromHalf(num, numLength);
  const pal2 = getPalFromHalf(num + 1, numLength);

  return pal1 > numCopy ? pal1 : pal2;
};
+1 -0

Bon un quick and dirty en C.

j’implémente directement une solution en base B quelconque (2≤B≤36). Dans la suite du texte je note Δ le plus grand chiffre de cette base (9 en base 10, F en base 16, 1 en base 2, …). L’idée de base commence par éliminer deux cas particuliers :

  • les nombres composés uniquement de chiffres Δ (comme 11111 en base 2, 9 en base 10 ou encore BBBBBB en base 12). Cela me permet d’éviter le cas où le palindrome suivant contient plus de chiffres que le nombre de départ. Pour un palindrome du type Δⁿ, nextpal(Δⁿ)=1Δⁿ⁻¹1 ;
  • puis les nombres composés d’un seul chiffre strictement plus petits que Δ, dans ce cas nextpal(n)=n+1 ;

Après ce filtre, on se retrouve donc avec un nombre d’au moins deux chiffres dont le palindrome suivant possédera le même nombre de chiffres.

Mon algo traverse ensuite plusieurs étapes :

  1. on part du milieu du nombre pour déterminer le plus grand palindrome interne, comme par exemple 22 dans 1223 ou 54345 dans 895434512 ;
  2. on copie la partie à gauche (si elle existe) du palindrome interne à sa droite ;
  3. si le nombre entier était un palindrome ou si le chiffre à gauche du palindrome interne était plus petit que celui à sa droite alors j’ajoute 1 à partir du milieu du nombre en propageant la retenue et en copiant en miroir à droite.

Par exemple : 808 → plus grand palindrome interne 808 → ajout de 1 à partir du milieu → 818 898 → plus grand palindrome interne 898 → ajout de 1 à partir du milieu → 908 → copie miroir → 909 3221 → plus grand palindrome interne 3221 → copie miroir hors palindrome interne → 3223 12328 → plus grand palindrome interne 12328, chiffre à gauche plus petit que celui à droite → copie miroir → 12321 → ajout de 1 à partir du milieu 12421 → copie miroir → 12421 3284 → plus grand palindrome interne 3284 → chiffre à plus petit que celui à doite → copie miroir → 3223 → ajout de 1 à partir du milieu → 3323 → copie miroir → 3333

code vite fait :

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static char digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
static uint8_t values[] = {
    ['0'] = 0,  ['1'] = 1,  ['2'] = 2,  ['3'] = 3,  ['4'] = 4,  ['5'] = 5,
    ['6'] = 6,  ['7'] = 7,  ['8'] = 8,  ['9'] = 9,  ['a'] = 10, ['b'] = 11,
    ['c'] = 12, ['d'] = 13, ['e'] = 14, ['f'] = 15, ['g'] = 16, ['h'] = 17,
    ['i'] = 18, ['j'] = 19, ['k'] = 20, ['l'] = 21, ['m'] = 22, ['n'] = 23,
    ['o'] = 24, ['p'] = 25, ['q'] = 26, ['r'] = 27, ['s'] = 28, ['t'] = 29,
    ['u'] = 30, ['v'] = 31, ['w'] = 32, ['x'] = 33, ['y'] = 34, ['z'] = 35,
    ['A'] = 10, ['B'] = 11, ['C'] = 12, ['D'] = 13, ['E'] = 14, ['F'] = 15,
    ['G'] = 16, ['H'] = 17, ['I'] = 18, ['J'] = 19, ['K'] = 20, ['L'] = 21,
    ['M'] = 22, ['N'] = 23, ['O'] = 24, ['P'] = 25, ['Q'] = 26, ['R'] = 27,
    ['S'] = 28, ['T'] = 29, ['U'] = 30, ['V'] = 31, ['W'] = 32, ['X'] = 33,
    ['Y'] = 34, ['Z'] = 35,
};
static bool valid[] = {
    ['0'] = true, ['1'] = true, ['2'] = true, ['3'] = true, ['4'] = true,
    ['5'] = true, ['6'] = true, ['7'] = true, ['8'] = true, ['9'] = true,
    ['a'] = true, ['b'] = true, ['c'] = true, ['d'] = true, ['e'] = true,
    ['f'] = true, ['g'] = true, ['h'] = true, ['i'] = true, ['j'] = true,
    ['k'] = true, ['l'] = true, ['m'] = true, ['n'] = true, ['o'] = true,
    ['p'] = true, ['q'] = true, ['r'] = true, ['s'] = true, ['t'] = true,
    ['u'] = true, ['v'] = true, ['w'] = true, ['x'] = true, ['y'] = true,
    ['z'] = true, ['A'] = true, ['B'] = true, ['C'] = true, ['D'] = true,
    ['E'] = true, ['F'] = true, ['G'] = true, ['H'] = true, ['I'] = true,
    ['J'] = true, ['K'] = true, ['L'] = true, ['M'] = true, ['N'] = true,
    ['O'] = true, ['P'] = true, ['Q'] = true, ['R'] = true, ['S'] = true,
    ['T'] = true, ['U'] = true, ['V'] = true, ['W'] = true, ['X'] = true,
    ['Y'] = true, ['Z'] = true,
};

typedef struct {
  char *input;
  int base;

  bool done;
  size_t number_len;
  uint8_t *number;
  size_t nextpal_len;
  uint8_t *nextpal;

} input_data_t;

input_data_t get_data(const char *input, int base);
void compute_nexpal(input_data_t *data);
void display(input_data_t data);

int main(int argc, char *argv[]) {
  input_data_t data = get_data(argv[1], argv[2] ? atoi(argv[2]) : 10);
  compute_nexpal(&data);
  display(data);
}

input_data_t get_data(const char *input, int base) {
  if (base < 2 || base > 36) {
    fprintf(stderr, "base invalide\n");
    exit(EXIT_FAILURE);
  }

  input_data_t data;
  data.input = strdup(input);
  data.base = base;
  data.number_len = strlen(input);
  if (data.number_len < 1) {
    fprintf(stderr, "nombre invalide\n");
    exit(EXIT_FAILURE);
  }

  data.number = malloc(data.number_len * sizeof *data.number);

  bool all_last_digit = true;
  for (size_t i = 0; i < data.number_len; i++) {
    if (!valid[(int)input[i]]) {
      fprintf(stderr, "caractère invalide\n");
      exit(EXIT_FAILURE);
    }
    uint8_t value = values[(int)input[i]];
    if (value != base - 1)
      all_last_digit = false;
    if (value >= base) {
      fprintf(stderr, "chiffre invalide\n");
      exit(EXIT_FAILURE);
    }
    data.number[i] = value;
  }

  if (all_last_digit) {
    data.done = true;
    data.nextpal_len = data.number_len + 1;
    data.nextpal = calloc(data.nextpal_len, sizeof *data.nextpal);
    data.nextpal[0] = data.nextpal[data.nextpal_len - 1] = 1;
  } else if (data.number_len == 1) {
    data.done = true;
    data.nextpal_len = data.number_len;
    data.nextpal = calloc(data.nextpal_len, sizeof *data.nextpal);
    data.nextpal[0] = values[(int)input[0]] + 1;
  } else {
    data.done = false;
    data.nextpal_len = data.number_len;
    data.nextpal = calloc(data.nextpal_len, sizeof *data.nextpal);
    memcpy(data.nextpal, data.number, data.number_len);
  }

  return data;
}

void compute_nexpal(input_data_t *data) {
  if (data->done)
    return;
  ssize_t middle = data->nextpal_len / 2;
  ssize_t left = middle - 1;
  ssize_t right = middle + (data->nextpal_len % 2);
  bool left_smaller = false;
  while (left >= 0 && data->nextpal[left] == data->nextpal[right]) {
    left--;
    right++;
  }
  left_smaller = (left < 0 || data->nextpal[left] < data->nextpal[right]);
  while (left >= 0) {
    data->nextpal[right] = data->nextpal[left];
    right++;
    left--;
  }

  if (left_smaller) {
    int carry = 1;
    left = middle - 1;
    if (data->nextpal_len % 2) {
      data->nextpal[middle] += carry;
      carry = data->nextpal[middle] / data->base;
      data->nextpal[middle] %= data->base;
      right = middle + 1;
    } else {
      right = middle;
    }
    while (left >= 0) {
      data->nextpal[left] += carry;
      carry = data->nextpal[left] / data->base;
      data->nextpal[left] %= data->base;
      data->nextpal[right++] = data->nextpal[left--];
    }
  }

  data->done = true;
}

void display(input_data_t data) {
  printf("le palindrome suivant %s en base %d est : ", data.input, data.base);
  for (size_t i = 0; i < data.nextpal_len; i++)
    putchar(digits[data.nextpal[i]]);
  putchar('\n');
}

Le code mériterait largement une simplification. J’ai pris le parti de ne saisir que des chaînes que je transforme en tableau d’entiers pour les manipulations.

Du coup en base 36, nextpal(256344510514743751332437247280545791⏨,36)=256344510514743751399753977111200702⏨

voilà voilà

+2 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte