%% Traveling Salesman Problem, 08/24/2012.
%% All cities connected to every other city, in both directions.
%% Find minimal Hamiltontian path length.
%% tsp2.m is only file required (this one).

% PROBLEM: works fine for generator length of 6, but not 7. We get a segmentation fault.
% solutions/2 takes all the time, n!. So focus on adding more memory via MERCURY_OPTIONS.
% Either I set it impoperly, the wrong option was chosen. Any suggestions? All I was trying to do
% was determine just how high I could go, before running out of memory, say 13. Not expecting to
% stop at 5040 = 7! permutations of a list length of 7. Any help would be appreciated. Thanks.

% Author: Luke P Immes
% Shrewsbury, MA
% USA
% 508 579 2683 (cell)
% lpimmes@townisp.com

%% The complexity issue is generating all solutions from which minimum distance can be obtained.
%% See tsp (same directory as this one) for other approachs which were not needed.

% tsp2 501>pwd
% /Users/lpimmes/Documents/lpimmesOnly/mercuryPrograms/algor91503/tsp2

% tsp2 494>uname -a
% Darwin luke-immess-imac-2.local 11.4.0 Darwin Kernel Version 11.4.0: Mon Apr  9 19:32:15 PDT 2012; root:xnu-1699.26.8~1/RELEASE_X86_64 x86_64

% tsp2 495>mmc -version
% mercury_compile: invalid grade `ion'
% Mercury Compiler, version 11.07.1, configured for x86_64-apple-darwin11.3.0
% Copyright (C) 1993-2012 The University of Melbourne
% Usage: mmc [<options>] <arguments>
% Use `mmc --help' for more information.

% tsp2 496>gcc -version
% i686-apple-darwin9-gcc-4.2.1: no input files
% tsp2 497>


% Using generator length of 7 (see code):  [2, 3, 4, 5, 6, 7, 8]
% tsp2 501>MERCURY_OPTIONS=--solutions-heap-size-kwords=1024000
% tsp2 501>echo $MERCURY_OPTIONS
% --solutions-heap-size-kwords=1024000
% tsp2 501>./tsp2
% Segmentation fault: 11
% tsp2 501>


% From mercury user's guide:
% MERCURY_OPTIONS
%     A list of options for the Mercury runtime system, which gets linked into every Mercury program. The options given in
%     this environment variable apply to every program;
% --solutions-heap-size size
%     Sets the size of the solutions heap to size kilobytes.
% --solutions-heap-size-kwords size
%     Sets the size of the solutions heap to size kilobytes multiplied by the word size in bytes.

% --runtime-flags

%% OK working, but still using solutions/2, and O(n!) for input size n, see minHamiltPath/2.
%% p(n, r) = n! / (n - r)!    where, in our case n = r, e.g. 6 things permuted 6 ways.
%%            = n! / 0! = n! / 1 = n!

% RUN
% tsp2 488>./tsp2
% #Permutations: 720, Generator length: 6 using [2 3 4 5 6 7 ],
% minimum distance 26: 1_3(5) 3_4(3) 4_5(1) 5_7(1) 7_2(4) 2_6(5) 6_1(7)
% tsp2 489>
	
%% tsp2 499>pwd
%% /Users/lpimmes/Documents/lpimmesOnly/mercuryPrograms/algor91503/tsp2

%% COMPILE
%% tsp2 495>tsp2.bash

:- module tsp2.			% This file name for now.
:- interface.
:- import_module io.

:- pred main(io, io).	    % main/2 used in interface, so include it!
:- mode main(di, uo) is cc_multi. % committed choice multideterminism- choose first goal that succeeds.
:- implementation.
:- import_module list, string, int, char, bool, solutions. % mercury itself

% Use [2, 3, 4, 5, 6, 7] for 1 to 7 cities (6 entries in dist/3) ;; works fine.
% Use [2, 3, 4, 5, 6, 7, 8] for 1 to 8 cities (7 entries in dist/3) ;; segmentation fault

				% Every city connected to every other city, and in both directions.
% Just add a new line for each section to increase generator length. Currently our generator will handle 6, or 6! = 720 permutations.
:- pred dist(int, int, int).
:- mode dist(in, in, out) is multi.
% dist(city1, city2, 10)
dist(1, 2, 10). % 7 entries
dist(1, 3, 5).
dist(1, 4, 9).
dist(1, 5, 4).
dist(1, 6, 7).
dist(1, 7, 6).
dist(1, 8, 2).

dist(2, 3, 6).
dist(2, 4, 9).
dist(2, 5, 8).
dist(2, 6, 5).
dist(2, 7, 4).
dist(2, 8, 9).

dist(3, 4, 3).
dist(3, 5, 2).
dist(3, 6, 6).
dist(3, 7, 5).
dist(3, 8, 5).

dist(4, 5, 1).
dist(4, 6, 7).
dist(4, 7, 2).
dist(4, 8, 8).

dist(5, 6, 3).
dist(5, 7, 1).
dist(5, 8, 7).

dist(6, 7, 8).
dist(6, 8, 2).

dist(7, 8, 7).

dist(A, B, D) :-
	% don't forget symmetry
	dist(B, A, D).

main(In, Out) :-
	%command_line_arguments(WrdsTags, In, Out9),

	(if
	 %% working, but uses solutions/2
	 % Generator is sorted, no duplicates, no gaps, beginning at 2, sorted.
	 % This works, and fairly quickly, but still O(n!) where n is input length here.
	% I can use:  [2, 3, 4, 5, 6, 7, 8], but then segmentation fault.
	% [2, 3, 4, 5, 6, 7] works fine, but total path length is one shorter.
	 Generator = [2, 3, 4, 5, 6, 7, 8], % No 1 in front, will put on front and back.
	minLenHamiltPath(Generator, MinHamtPath)
	 
	then
	format("%s\n", [s(MinHamtPath)], In, Out)
	
	 else
	 format("Failed to find minimum Hamiltonian path using given generator.\n", [], In, Out)
	).

% tsp2 489>./tsp2
% #Permutations: 720, Generator length: 6 using [2 3 4 5 6 7 ],
% minimum distance 26: 1_3(5) 3_4(3) 4_5(1) 5_7(1) 7_2(4) 2_6(5) 6_1(7)
% tsp2 489>

:- pred minLenHamiltPath(list(int), string).
:- mode minLenHamiltPath(in, out) is nondet.
minLenHamiltPath(LstGenerator, TotalDistStr) :-
	% LstGenerator is sorted, no duplicates, no gaps, beginning at 2
	solutions(list.perm(LstGenerator), HamiltPaths), % takes n! time, where n means length LstGenerator.
	getMinDist(10000, HamiltPaths, "", DistStr), % initial max is some # we don't expect to exceed
	length(HamiltPaths, LenP), 
	length(LstGenerator, LenG), lstNumDsp(LstGenerator, LsDsp),
	format("#Permutations: %i, Generator length: %i using %s,\nminimum distance %s",
	       [i(LenP), i(LenG), s(LsDsp), s(DistStr)], TotalDistStr).

:- pred getMinDist(int, list(list(int)), string, string).
:- mode getMinDist(in, in, in, out) is nondet.
getMinDist(_, [], Accum, Accum).
getMinDist(Max, [Perm | Perms], Accum, Result) :-
	getDist(Perm, Dist, DistStr),
	(
	 Dist < Max,
	 getMinDist(Dist, Perms, DistStr, Result)
	;
	 getMinDist(Max, Perms, Accum, Result)
	).

:- pred getDist(list(int), int, string).
:- mode getDist(in, out, out) is nondet.
getDist(LstNum, Dist, DistStr) :-
	append(LstNum, [1], L2),
	getDist(1, L2,    0, Dist,     "", DistPath),
	format("%i:%s", [i(Dist), s(DistPath)], DistStr).

:- pred getDist(int, list(int),  int, int,  string, string).
:- mode getDist(in, in,   in, out,   in, out) is nondet.
getDist(_, [],              AccN, AccN,         Accum, Accum).
getDist(D1, [D2 | Ds], AccN, ResultN,     Accum, Result) :-
	dist(D1, D2, D),
	format(" %i_%i(%i)", [i(D1), i(D2), i(D)], Acc),
	getDist(D2, Ds,
		AccN + D, ResultN,
		Accum ++ Acc, Result).

:- pred lstNumDsp(list(int), string).
:- mode lstNumDsp(in, out) is semidet.
lstNumDsp(Lst, R) :-
	lstNumDsp(Lst, "", Result),
	R = "[" ++ Result ++ "]".

:- pred lstNumDsp(list(int), string, string).
:- mode lstNumDsp(in, in, out) is semidet.
lstNumDsp([], Accum, Accum).
lstNumDsp([L | Lst], Accum, Result) :-
	format("%i", [i(L)], A),
	lstNumDsp(Lst, Accum ++ A ++ " ", Result).


				% from tsp
				% tsp 495>./tsp
% Number cities: 6, number subpaths: 120, 
% Distance: 30, 1_2(10) 2_3(6) 3_4(3) 4_5(1) 5_6(3) 6_1(7)
% Distance: 33, 1_2(10) 2_3(6) 3_4(3) 4_6(7) 6_5(3) 5_1(4)
% Distance: 33, 1_2(10) 2_3(6) 3_5(2) 5_4(1) 4_6(7) 6_1(7)
% Distance: 37, 1_2(10) 2_3(6) 3_5(2) 5_6(3) 6_4(7) 4_1(9)
% Distance: 34, 1_2(10) 2_3(6) 3_6(6) 6_4(7) 4_5(1) 5_1(4)
% Distance: 35, 1_2(10) 2_3(6) 3_6(6) 6_5(3) 5_4(1) 4_1(9)
% Distance: 34, 1_2(10) 2_4(9) 4_3(3) 3_5(2) 5_6(3) 6_1(7)
% Distance: 35, 1_2(10) 2_4(9) 4_3(3) 3_6(6) 6_5(3) 5_1(4)
% Distance: 35, 1_2(10) 2_4(9) 4_5(1) 5_3(2) 3_6(6) 6_1(7)
% Distance: 34, 1_2(10) 2_4(9) 4_5(1) 5_6(3) 6_3(6) 3_1(5)
% Distance: 38, 1_2(10) 2_4(9) 4_6(7) 6_3(6) 3_5(2) 5_1(4)
% Distance: 36, 1_2(10) 2_4(9) 4_6(7) 6_5(3) 5_3(2) 3_1(5)
% Distance: 37, 1_2(10) 2_5(8) 5_3(2) 3_4(3) 4_6(7) 6_1(7)
% Distance: 42, 1_2(10) 2_5(8) 5_3(2) 3_6(6) 6_4(7) 4_1(9)
% Distance: 35, 1_2(10) 2_5(8) 5_4(1) 4_3(3) 3_6(6) 6_1(7)
% Distance: 37, 1_2(10) 2_5(8) 5_4(1) 4_6(7) 6_3(6) 3_1(5)
% Distance: 39, 1_2(10) 2_5(8) 5_6(3) 6_3(6) 3_4(3) 4_1(9)
% Distance: 36, 1_2(10) 2_5(8) 5_6(3) 6_4(7) 4_3(3) 3_1(5)
% Distance: 29, 1_2(10) 2_6(5) 6_3(6) 3_4(3) 4_5(1) 5_1(4)
% Distance: 33, 1_2(10) 2_6(5) 6_3(6) 3_5(2) 5_4(1) 4_1(9)
% Distance: 31, 1_2(10) 2_6(5) 6_4(7) 4_3(3) 3_5(2) 5_1(4)
% Distance: 30, 1_2(10) 2_6(5) 6_4(7) 4_5(1) 5_3(2) 3_1(5)
% Distance: 32, 1_2(10) 2_6(5) 6_5(3) 5_3(2) 3_4(3) 4_1(9)
% Distance: 27, 1_2(10) 2_6(5) 6_5(3) 5_4(1) 4_3(3) 3_1(5)
% Distance: 31, 1_3(5) 3_2(6) 2_4(9) 4_5(1) 5_6(3) 6_1(7)
% Distance: 34, 1_3(5) 3_2(6) 2_4(9) 4_6(7) 6_5(3) 5_1(4)
% Distance: 34, 1_3(5) 3_2(6) 2_5(8) 5_4(1) 4_6(7) 6_1(7)
% Distance: 38, 1_3(5) 3_2(6) 2_5(8) 5_6(3) 6_4(7) 4_1(9)
% Distance: 28, 1_3(5) 3_2(6) 2_6(5) 6_4(7) 4_5(1) 5_1(4)
% Distance: 29, 1_3(5) 3_2(6) 2_6(5) 6_5(3) 5_4(1) 4_1(9)
% Distance: 35, 1_3(5) 3_4(3) 4_2(9) 2_5(8) 5_6(3) 6_1(7)
% Distance: 29, 1_3(5) 3_4(3) 4_2(9) 2_6(5) 6_5(3) 5_1(4)
% Distance: 29, 1_3(5) 3_4(3) 4_5(1) 5_2(8) 2_6(5) 6_1(7)
% Distance: 27, 1_3(5) 3_4(3) 4_5(1) 5_6(3) 6_2(5) 2_1(10)
% Distance: 32, 1_3(5) 3_4(3) 4_6(7) 6_2(5) 2_5(8) 5_1(4)
% Distance: 36, 1_3(5) 3_4(3) 4_6(7) 6_5(3) 5_2(8) 2_1(10)
% Distance: 38, 1_3(5) 3_5(2) 5_2(8) 2_4(9) 4_6(7) 6_1(7)
% Distance: 36, 1_3(5) 3_5(2) 5_2(8) 2_6(5) 6_4(7) 4_1(9)
% Distance: 29, 1_3(5) 3_5(2) 5_4(1) 4_2(9) 2_6(5) 6_1(7)
% Distance: 30, 1_3(5) 3_5(2) 5_4(1) 4_6(7) 6_2(5) 2_1(10)
% Distance: 33, 1_3(5) 3_5(2) 5_6(3) 6_2(5) 2_4(9) 4_1(9)
% Distance: 36, 1_3(5) 3_5(2) 5_6(3) 6_4(7) 4_2(9) 2_1(10)
% Distance: 30, 1_3(5) 3_6(6) 6_2(5) 2_4(9) 4_5(1) 5_1(4)
% Distance: 34, 1_3(5) 3_6(6) 6_2(5) 2_5(8) 5_4(1) 4_1(9)
% Distance: 39, 1_3(5) 3_6(6) 6_4(7) 4_2(9) 2_5(8) 5_1(4)
% Distance: 37, 1_3(5) 3_6(6) 6_4(7) 4_5(1) 5_2(8) 2_1(10)
% Distance: 40, 1_3(5) 3_6(6) 6_5(3) 5_2(8) 2_4(9) 4_1(9)
% Distance: 34, 1_3(5) 3_6(6) 6_5(3) 5_4(1) 4_2(9) 2_1(10)
% Distance: 36, 1_4(9) 4_2(9) 2_3(6) 3_5(2) 5_6(3) 6_1(7)
% Distance: 37, 1_4(9) 4_2(9) 2_3(6) 3_6(6) 6_5(3) 5_1(4)
% Distance: 41, 1_4(9) 4_2(9) 2_5(8) 5_3(2) 3_6(6) 6_1(7)
% Distance: 40, 1_4(9) 4_2(9) 2_5(8) 5_6(3) 6_3(6) 3_1(5)
% Distance: 35, 1_4(9) 4_2(9) 2_6(5) 6_3(6) 3_5(2) 5_1(4)
% Distance: 33, 1_4(9) 4_2(9) 2_6(5) 6_5(3) 5_3(2) 3_1(5)
% Distance: 36, 1_4(9) 4_3(3) 3_2(6) 2_5(8) 5_6(3) 6_1(7)
% Distance: 30, 1_4(9) 4_3(3) 3_2(6) 2_6(5) 6_5(3) 5_1(4)
% Distance: 34, 1_4(9) 4_3(3) 3_5(2) 5_2(8) 2_6(5) 6_1(7)
% Distance: 32, 1_4(9) 4_3(3) 3_5(2) 5_6(3) 6_2(5) 2_1(10)
% Distance: 35, 1_4(9) 4_3(3) 3_6(6) 6_2(5) 2_5(8) 5_1(4)
% Distance: 39, 1_4(9) 4_3(3) 3_6(6) 6_5(3) 5_2(8) 2_1(10)
% Distance: 37, 1_4(9) 4_5(1) 5_2(8) 2_3(6) 3_6(6) 6_1(7)
% Distance: 34, 1_4(9) 4_5(1) 5_2(8) 2_6(5) 6_3(6) 3_1(5)
% Distance: 30, 1_4(9) 4_5(1) 5_3(2) 3_2(6) 2_6(5) 6_1(7)
% Distance: 33, 1_4(9) 4_5(1) 5_3(2) 3_6(6) 6_2(5) 2_1(10)
% Distance: 29, 1_4(9) 4_5(1) 5_6(3) 6_2(5) 2_3(6) 3_1(5)
% Distance: 35, 1_4(9) 4_5(1) 5_6(3) 6_3(6) 3_2(6) 2_1(10)
% Distance: 33, 1_4(9) 4_6(7) 6_2(5) 2_3(6) 3_5(2) 5_1(4)
% Distance: 36, 1_4(9) 4_6(7) 6_2(5) 2_5(8) 5_3(2) 3_1(5)
% Distance: 40, 1_4(9) 4_6(7) 6_3(6) 3_2(6) 2_5(8) 5_1(4)
% Distance: 42, 1_4(9) 4_6(7) 6_3(6) 3_5(2) 5_2(8) 2_1(10)
% Distance: 38, 1_4(9) 4_6(7) 6_5(3) 5_2(8) 2_3(6) 3_1(5)
% Distance: 37, 1_4(9) 4_6(7) 6_5(3) 5_3(2) 3_2(6) 2_1(10)
% Distance: 35, 1_5(4) 5_2(8) 2_3(6) 3_4(3) 4_6(7) 6_1(7)
% Distance: 40, 1_5(4) 5_2(8) 2_3(6) 3_6(6) 6_4(7) 4_1(9)
% Distance: 37, 1_5(4) 5_2(8) 2_4(9) 4_3(3) 3_6(6) 6_1(7)
% Distance: 39, 1_5(4) 5_2(8) 2_4(9) 4_6(7) 6_3(6) 3_1(5)
% Distance: 35, 1_5(4) 5_2(8) 2_6(5) 6_3(6) 3_4(3) 4_1(9)
% Distance: 32, 1_5(4) 5_2(8) 2_6(5) 6_4(7) 4_3(3) 3_1(5)
% Distance: 35, 1_5(4) 5_3(2) 3_2(6) 2_4(9) 4_6(7) 6_1(7)
% Distance: 33, 1_5(4) 5_3(2) 3_2(6) 2_6(5) 6_4(7) 4_1(9)
% Distance: 30, 1_5(4) 5_3(2) 3_4(3) 4_2(9) 2_6(5) 6_1(7)
% Distance: 31, 1_5(4) 5_3(2) 3_4(3) 4_6(7) 6_2(5) 2_1(10)
% Distance: 35, 1_5(4) 5_3(2) 3_6(6) 6_2(5) 2_4(9) 4_1(9)
% Distance: 38, 1_5(4) 5_3(2) 3_6(6) 6_4(7) 4_2(9) 2_1(10)
% Distance: 33, 1_5(4) 5_4(1) 4_2(9) 2_3(6) 3_6(6) 6_1(7)
% Distance: 30, 1_5(4) 5_4(1) 4_2(9) 2_6(5) 6_3(6) 3_1(5)
% Distance: 26, 1_5(4) 5_4(1) 4_3(3) 3_2(6) 2_6(5) 6_1(7)
% Distance: 29, 1_5(4) 5_4(1) 4_3(3) 3_6(6) 6_2(5) 2_1(10)
% Distance: 28, 1_5(4) 5_4(1) 4_6(7) 6_2(5) 2_3(6) 3_1(5)
% Distance: 34, 1_5(4) 5_4(1) 4_6(7) 6_3(6) 3_2(6) 2_1(10)
% Distance: 30, 1_5(4) 5_6(3) 6_2(5) 2_3(6) 3_4(3) 4_1(9)
% Distance: 29, 1_5(4) 5_6(3) 6_2(5) 2_4(9) 4_3(3) 3_1(5)
% Distance: 37, 1_5(4) 5_6(3) 6_3(6) 3_2(6) 2_4(9) 4_1(9)
% Distance: 35, 1_5(4) 5_6(3) 6_3(6) 3_4(3) 4_2(9) 2_1(10)
% Distance: 34, 1_5(4) 5_6(3) 6_4(7) 4_2(9) 2_3(6) 3_1(5)
% Distance: 33, 1_5(4) 5_6(3) 6_4(7) 4_3(3) 3_2(6) 2_1(10)
% Distance: 26, 1_6(7) 6_2(5) 2_3(6) 3_4(3) 4_5(1) 5_1(4)
% Distance: 30, 1_6(7) 6_2(5) 2_3(6) 3_5(2) 5_4(1) 4_1(9)
% Distance: 30, 1_6(7) 6_2(5) 2_4(9) 4_3(3) 3_5(2) 5_1(4)
% Distance: 29, 1_6(7) 6_2(5) 2_4(9) 4_5(1) 5_3(2) 3_1(5)
% Distance: 34, 1_6(7) 6_2(5) 2_5(8) 5_3(2) 3_4(3) 4_1(9)
% Distance: 29, 1_6(7) 6_2(5) 2_5(8) 5_4(1) 4_3(3) 3_1(5)
% Distance: 33, 1_6(7) 6_3(6) 3_2(6) 2_4(9) 4_5(1) 5_1(4)
% Distance: 37, 1_6(7) 6_3(6) 3_2(6) 2_5(8) 5_4(1) 4_1(9)
% Distance: 37, 1_6(7) 6_3(6) 3_4(3) 4_2(9) 2_5(8) 5_1(4)
% Distance: 35, 1_6(7) 6_3(6) 3_4(3) 4_5(1) 5_2(8) 2_1(10)
% Distance: 41, 1_6(7) 6_3(6) 3_5(2) 5_2(8) 2_4(9) 4_1(9)
% Distance: 35, 1_6(7) 6_3(6) 3_5(2) 5_4(1) 4_2(9) 2_1(10)
% Distance: 35, 1_6(7) 6_4(7) 4_2(9) 2_3(6) 3_5(2) 5_1(4)
% Distance: 38, 1_6(7) 6_4(7) 4_2(9) 2_5(8) 5_3(2) 3_1(5)
% Distance: 35, 1_6(7) 6_4(7) 4_3(3) 3_2(6) 2_5(8) 5_1(4)
% Distance: 37, 1_6(7) 6_4(7) 4_3(3) 3_5(2) 5_2(8) 2_1(10)
% Distance: 34, 1_6(7) 6_4(7) 4_5(1) 5_2(8) 2_3(6) 3_1(5)
% Distance: 33, 1_6(7) 6_4(7) 4_5(1) 5_3(2) 3_2(6) 2_1(10)
% Distance: 36, 1_6(7) 6_5(3) 5_2(8) 2_3(6) 3_4(3) 4_1(9)
% Distance: 35, 1_6(7) 6_5(3) 5_2(8) 2_4(9) 4_3(3) 3_1(5)
% Distance: 36, 1_6(7) 6_5(3) 5_3(2) 3_2(6) 2_4(9) 4_1(9)
% Distance: 34, 1_6(7) 6_5(3) 5_3(2) 3_4(3) 4_2(9) 2_1(10)
% Distance: 31, 1_6(7) 6_5(3) 5_4(1) 4_2(9) 2_3(6) 3_1(5)
% Distance: 30, 1_6(7) 6_5(3) 5_4(1) 4_3(3) 3_2(6) 2_1(10)
% tsp 495>