/**
 * Copyright (c) 2017 Siemens AG
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * 1) Redistributions of source code must retain the above copyright notice, this
 *    list of conditions and the following disclaimer.
 *
 * 2) Redistributions in binary form must reproduce the above copyright notice,
 *    this list of conditions and the following disclaimer in the documentation
 *    and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
package at.ac.tuwien.kr.alpha.core.solver;

import static at.ac.tuwien.kr.alpha.core.test.util.TestUtils.collectRegressionTestAnswerSets;
import static at.ac.tuwien.kr.alpha.core.test.util.TestUtils.ignoreTestForNonDefaultDomainIndependentHeuristics;
import static at.ac.tuwien.kr.alpha.core.test.util.TestUtils.runWithTimeout;
import static org.junit.jupiter.api.Assertions.assertEquals;

import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;

import org.junit.jupiter.api.Disabled;

import at.ac.tuwien.kr.alpha.api.AnswerSet;

/**
 * Tests {@link AbstractSolver} using some pigeon-hole test cases (see https://en.wikipedia.org/wiki/Pigeonhole_principle).
 */
public class PigeonHoleTest {
	
	private static final long DEBUG_TIMEOUT_FACTOR = 5;
	
	@RegressionTest
	public void test2Pigeons2Holes(RegressionTestConfig cfg) {
		long timeout = 5000L;
		ignoreTestForNonDefaultDomainIndependentHeuristics(cfg);
		runWithTimeout(cfg, timeout, DEBUG_TIMEOUT_FACTOR, () -> testPigeonsHoles(2, 2, cfg));
	}

	@RegressionTest
	public void test3Pigeons2Holes(RegressionTestConfig cfg) {
		long timeout = 5000L;
		ignoreTestForNonDefaultDomainIndependentHeuristics(cfg);
		runWithTimeout(cfg, timeout, DEBUG_TIMEOUT_FACTOR, () -> testPigeonsHoles(3, 2, cfg));
	}

	@RegressionTest
	public void test2Pigeons3Holes(RegressionTestConfig cfg) {
		long timeout = 5000L;
		ignoreTestForNonDefaultDomainIndependentHeuristics(cfg);
		runWithTimeout(cfg, timeout, DEBUG_TIMEOUT_FACTOR, () -> testPigeonsHoles(2, 3, cfg));
	}

	@RegressionTest
	public void test3Pigeons3Holes(RegressionTestConfig cfg) {
		long timeout = 10000L;
		ignoreTestForNonDefaultDomainIndependentHeuristics(cfg);
		runWithTimeout(cfg, timeout, DEBUG_TIMEOUT_FACTOR, () -> testPigeonsHoles(3, 3, cfg));
	}

	@RegressionTest
	public void test4Pigeons3Holes(RegressionTestConfig cfg) {
		long timeout = 10000L;
		ignoreTestForNonDefaultDomainIndependentHeuristics(cfg);
		runWithTimeout(cfg, timeout, DEBUG_TIMEOUT_FACTOR, () -> testPigeonsHoles(4, 3, cfg));
	}

	@RegressionTest
	public void test3Pigeons4Holes(RegressionTestConfig cfg) {
		long timeout = 10000L;
		ignoreTestForNonDefaultDomainIndependentHeuristics(cfg);
		runWithTimeout(cfg, timeout, DEBUG_TIMEOUT_FACTOR, () -> testPigeonsHoles(3, 4, cfg));
	}

	@RegressionTest
	public void test4Pigeons4Holes(RegressionTestConfig cfg) {
		long timeout = 10000L;
		ignoreTestForNonDefaultDomainIndependentHeuristics(cfg);
		runWithTimeout(cfg, timeout, DEBUG_TIMEOUT_FACTOR, () -> testPigeonsHoles(4, 4, cfg));
	}

	@RegressionTest
	@Disabled("disabled to save resources during CI")
	public void test10Pigeons10Holes(RegressionTestConfig cfg) {
		long timeout = 60000L;
		runWithTimeout(cfg, timeout, DEBUG_TIMEOUT_FACTOR, () -> testPigeonsHoles(10, 10, cfg));
	}

	@RegressionTest
	@Disabled("disabled to save resources during CI")
	public void test19Pigeons20Holes(RegressionTestConfig cfg) {
		long timeout = 60000L;
		runWithTimeout(cfg, timeout, DEBUG_TIMEOUT_FACTOR, () -> testPigeonsHoles(19, 20, cfg));
	}

	@RegressionTest
	@Disabled("disabled to save resources during CI")
	public void test28Pigeons30Holes(RegressionTestConfig cfg) {
		long timeout = 60000L;
		runWithTimeout(cfg, timeout, DEBUG_TIMEOUT_FACTOR, () -> testPigeonsHoles(28, 30, cfg));
	}

	@RegressionTest
	@Disabled("disabled to save resources during CI")
	public void test37Pigeons40Holes(RegressionTestConfig cfg) {
		long timeout = 60000L;
		runWithTimeout(cfg, timeout, DEBUG_TIMEOUT_FACTOR, () -> testPigeonsHoles(37, 40, cfg));
	}

	@RegressionTest
	@Disabled("disabled to save resources during CI")
	public void test46Pigeons50Holes(RegressionTestConfig cfg) {
		long timeout = 60000L;
		runWithTimeout(cfg, timeout, DEBUG_TIMEOUT_FACTOR, () -> testPigeonsHoles(46, 50, cfg));
	}

	@RegressionTest
	@Disabled("disabled to save resources during CI")
	public void test55Pigeons60Holes(RegressionTestConfig cfg) {
		long timeout = 60000L;
		runWithTimeout(cfg, timeout, DEBUG_TIMEOUT_FACTOR, () -> testPigeonsHoles(55, 60, cfg));
	}

	/**
	 * Tries to solve the problem of assigning P pigeons to H holes.
	 */
	private void testPigeonsHoles(int pigeons, int holes, RegressionTestConfig cfg) {
		List<String> rules = new ArrayList<>();
		rules.add("pos(P,H) :- pigeon(P), hole(H), not negpos(P,H).");
		rules.add("negpos(P,H) :- pigeon(P), hole(H), not pos(P,H).");
		rules.add(":- pigeon(P), hole(H1), hole(H2), pos(P,H1), pos(P,H2), H1 != H2.");
		rules.add(":- pigeon(P), not hashole(P).");
		rules.add("hashole(P) :- pigeon(P), hole(H), pos(P,H).");
		rules.add(":- pigeon(P1), pigeon(P2), hole(H), pos(P1,H), pos(P2,H), P1 != P2.");

		addPigeons(rules, pigeons);
		addHoles(rules, holes);

		Set<AnswerSet> answerSets = collectRegressionTestAnswerSets(concat(rules), cfg);
		assertEquals(numberOfSolutions(pigeons, holes), answerSets.size());
	}

	private void addPigeons(List<String> rules, int pigeons) {
		addFacts(rules, "pigeon", 1, pigeons);
	}

	private void addHoles(List<String> rules, int holes) {
		addFacts(rules, "hole", 1, holes);
	}

	private void addFacts(List<String> rules, String predicateName, int from, int to) {
		for (int i = from; i <= to; i++) {
			rules.add(String.format("%s(%d).", predicateName, i));
		}
	}

	private String concat(List<String> rules) {
		String ls = System.lineSeparator();
		return rules.stream().collect(Collectors.joining(ls));
	}

	private long numberOfSolutions(int pigeons, int holes) {
		if (pigeons > holes) {
			return 0;
		} else if (pigeons == holes) {
			return factorial(pigeons);
		} else {
			return factorial(holes) / factorial(holes - pigeons);
			// could be replaced by more efficient implementaton (but performance is not so important here)
		}
	}

	private long factorial(int n) {
		return n <= 1 ? 1 : n * factorial(n - 1);
		// could be replaced by more efficient implementaton (but performance is not so important here)
		// see http://www.luschny.de/math/factorial/FastFactorialFunctions.htm
		// TODO: we could use Apache Commons Math
	}

}
