/*
 * langford.c
 *
 *  Created on: 24/03/2017
 *      Author: pedro
 *
 *      http://www.csplib.org/Problems/prob024/
 *      https://github.com/MiniZinc/minizinc-benchmarks/tree/master/langford
 *      https://www.cril.univ-artois.fr/~lecoutre/benchmarks.html#
 *
 *		Langford's number problem:
 * Arrange 2 sets of positive integers 1..k to a sequence, such that, following the first occurrence of an integer i,
 * each subsequent occurrence of i, appears i+1 indices later than the last.
 * For example, for k=4, a solution would be 41312432
 */

#define LANGFORD 0

#include "langford.h"

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

#include "../config.h"
#include "../constraints/fake_all_different.h"
#include "../constraints/element.h"
#include "../constraints/lt.h"
#include "../constraints/minus_eq.h"
#include "../split.h"
#include "../variables.h"

#if LANGFORD == 0
/*
 * Solve the Langford number problem with N values
 */
void run_langford(int* csp_dims) {
	int n = csp_dims[0];
	unsigned long result;
	unsigned int* position = malloc((unsigned int)n * 2 * sizeof(unsigned int));
	unsigned int* solution = malloc((unsigned int)n * 2 * sizeof(unsigned int));
	int i;

	for (i = 0; i < n * 2; i++) {
		position[i] = v_new_range(1, 2 * (unsigned int)n, true);
	}
	for (i = 0; i < n * 2; i++) {
		solution[i] = v_new_range(0, (unsigned int)n - 1, false);
	}

	for (i = 0; i < n; i++) {
		c_minus_eq(position[i + n], position[i], i + 2);
		c_element(solution, 2 * (unsigned int)n, position[i], (unsigned int)i);
		c_element(solution, 2 * (unsigned int)n, position[(unsigned int)n + (unsigned int)i], (unsigned int)i);
	}

	c_fake_all_different(position, (unsigned int)n * 2);
	c_lt(solution[0], solution[2 * (unsigned int)n - 1]);

	if (FINDING_ONE_SOLUTION) {
		printf("\nFinding one solution for Langford's number with %u numbers on:\n", n);
	} else {
		printf("\nCounting all the solutions for Langford's number with %u numbers on:\n", n);
	}

	// Solve the CSP
	result = solve_CSP();

	if (FINDING_ONE_SOLUTION && result == 1) {
		printf("Solution:\n");

		vs_print_single_val(solution, (unsigned int)n * 2, 0);
		printf("\n");

	} else {
		printf("%lu solution(s) found\n", result);
	}

	free(position);
	free(solution);
}

#elif LANGFORD == 1

/*
 * Solve the Langford number problem with K sets and N values
 */
void run_langford(int* csp_dims) {
	int k = csp_dims[0];
	int n = csp_dims[1];
	unsigned long result;
	unsigned int* numbers = malloc(k * n * sizeof(unsigned int));
	unsigned int* ordered = malloc(k * n * sizeof(unsigned int));
	unsigned int i, j;

	for (i = 0; i < k * n; i++) {
		numbers[i] = v_new_range(0, k * n - 1, true);
	}

	c_fake_all_different(numbers, k * n);

	// don't generate solutions which correspond to exchanging the
	// positions of a number (and are, therefore, identical)
	for (i = 0; i < n; i++) {
		for (j = 0; j < k - 1; j++) {
			c_minus_eq(numbers[i * k + j + 1], numbers[i * k + j], i + 2);
		}
	}

	// don't generate symmetrical solutions
	unsigned int first = v_new_range(1, k * n, true);
	unsigned int last = v_new_range(1, k * n, true);
	c_element(numbers, k * n, first, 0);
	c_element(numbers, k * n, last, k * n - 1);
	c_lt(first, last);


	if (FINDING_ONE_SOLUTION) {
		printf("\nFinding one solution for Langford's number with N=%u and K=%u.\n", n, k);
	} else {
		printf("\nCounting all the solutions for Langford's number with N=%u and K=%u.\n", n, k);
	}

	// Solve the CSP
	result = solve_CSP();

	if (FINDING_ONE_SOLUTION && result == 1) {
		printf("Solution:\n");

		vs_print_single_val(numbers, k * n, 0);

		for (i = 0; i < k * n; i++) {
			ordered[v_get_value(i)] = i / k + 1;
		}
		for (i = 0; i < k * n; i++) {
			printf("%d, ", ordered[i]);
		}
		printf("\n");

	} else {
		printf("%lu solution(s) found\n", result);
	}

	free(numbers);
	free(ordered);
}

#endif