Cable master program sources

Program Results

/*****************************************************************************

Project: CABLE_MASTER

FileName: CABLE_MASTER.PRO

Purpose: Cable master task solver

Written by: Serguei Penkov: spenkov@ozemail.com.au

Comments:

******************************************************************************/

global domains

SLIST = STRING*

ILIST = INTEGER*

FILE = input

BR_TREE = reference t(VAL,BR_TREE,BR_TREE)

VAL = INTEGER

predicates

predicates cable_master(SLIST INPUT_LINES)

predicates sort_integers(ILIST,ILIST) - (i,o)

procedure string_to_slist(STRING,STRING,SLIST) - (i,i,o)

procedure slist_to_integer_list(SLIST,ILIST) - (i,o)

procedure find_solution(ILIST CABLE_LENGTH_SORTED,INTEGER) - (i,i)

procedure total_length(ILIST,INTEGER LENGTH) - (i,o)

procedure min_number(ILIST,INTEGER,INTEGER MIN) - (i,i,o)

procedure max_number(ILIST,INTEGER,INTEGER MIN) - (i,i,o)

procedure max(INTEGER, INTEGER, INTEGER) - (i,i,o)

procedure min(INTEGER, INTEGER, INTEGER) - (i,i,o)

nondeterm for(INTEGER ,INTEGER Start,INTEGER Stop, INTEGER INCREMENT)

determ test_cable_length(INTEGER BEST_LENGTH,INTEGER REQUIRED_PIECES,ILIST CABLE_LENGTH_SORTED) - (i,i,i)

clauses

cable_master([FIRST_LINE|CABLE_LINES]):-

fronttoken(FIRST_LINE,TOTAL,PIECES),

str_int(TOTAL,TOTAL_CABLES),

str_int(PIECES,REQUIRED_PIECES),

slist_to_integer_list(CABLE_LINES,CABLE_LENGTH),

write("Total Cables - ",TOTAL_CABLES),nl,

write("Required Pieces - ",REQUIRED_PIECES),nl,

find_solution(CABLE_LENGTH,REQUIRED_PIECES),

find_solution(CABLE_LENGTH,REQUIRED_PIECES):-

sort_integers(CABLE_LENGTH, CABLE_LENGTH_SORTED),

write("Cable Length sorted ",CABLE_LENGTH_SORTED),nl,

total_length(CABLE_LENGTH_SORTED,TOTAL_LENGTH),

write("Total Cable Length ",TOTAL_LENGTH),nl, % calculate total cable length

MAX_SEGMENT = TOTAL_LENGTH div REQUIRED_PIECES,

write("Max possible segment ",MAX_SEGMENT),nl,

% now - generate and test. Generate a cable length and test,

% if it can fit into current cables

% Simple approach - generate and test

for(BEST_LENGTH,MAX_SEGMENT,0,-1),

test_cable_length(BEST_LENGTH,REQUIRED_PIECES,CABLE_LENGTH_SORTED),

% here we are with solution

find_solution(CABLE_LENGTH,REQUIRED_PIECES):-

write("No solution found\n"),

write("CABLES ",CABLE_LENGTH,", REQUIRED number of segments ",REQUIRED_PIECES),nl,

write("Max number of cables ",CABLE_LENGTH),nl,

test_cable_length(_,_,[]):-!,fail. % THIS CABLE LENGTH DOESN'T FIT

test_cable_length(BEST_LENGTH,REQUIRED_PIECES,_):-

REQUIRED_PIECES = 0,

!, % OK - here we are - found best fit cable length

write("\tFound solution - ",BEST_LENGTH," is the maximum length\n").

test_cable_length(BEST_LENGTH,REQUIRED_PIECES,[CABLE_LENGTH|CABLE_LENGTH_SORTED]):-

HOW_MANY_PIECES_IN_THIS_CABLE = CABLE_LENGTH div BEST_LENGTH,

NEXT_REQUIRED_PIECES = REQUIRED_PIECES - HOW_MANY_PIECES_IN_THIS_CABLE,

NEXT_REQUIRED_PIECES > 0,!,

test_cable_length(BEST_LENGTH,NEXT_REQUIRED_PIECES,CABLE_LENGTH_SORTED).

test_cable_length(BEST_LENGTH,_,_):-

write("\tFound solution - ",BEST_LENGTH," is the maximum length\n"),

% support predicates

for(I,I,_,_).

for(I,Start,Stop,INCREMENT):-

INCREMENT > 0,

Start < Stop,Next=Start+INCREMENT,

for(I,Next,Stop,INCREMENT).

for(I,Start,Stop,INCREMENT):-

INCREMENT < 0,

Start > Stop,Next=Start+INCREMENT,

for(I,Next,Stop,INCREMENT).

total_length([],0):-!.

total_length([LENGTH|ILIST],TOTAL_LENGTH):-!,

total_length(ILIST,TEMP),

TOTAL_LENGTH = TEMP + LENGTH.

string_to_slist(View,SEP,[Field|FieldList]):-

searchstring(View,SEP,FoundPos),

str_len(SEP,SEPLength),

Pos = FoundPos - 1,

frontstr(Pos,View,Field,RestString),

frontstr(SEPLength,RestString,_,Tail),!,

string_to_slist(Tail,SEP,FieldList).

string_to_slist(Field,_,[Field]).

slist_to_integer_list([],[]):-!.

slist_to_integer_list([LINE|DATA_LINES],[LENGTH_IN_CM|CABLE_LENGTH]):-

str_real(LINE,REAL),

LENGTH_IN_CM = val(INTEGER,REAL*100),!,

slist_to_integer_list(DATA_LINES,CABLE_LENGTH).

slist_to_integer_list([LINE|DATA_LINES],CABLE_LENGTH):-!,

write("Invalid input Data - length is not real - ",LINE),nl,

slist_to_integer_list(DATA_LINES,CABLE_LENGTH).

% min/max calculations

min_number([],MIN ,MIN):-!.

min_number([H|T],CURR_MIN ,MIN):-!,

min(H,CURR_MIN,TEMP),

min_number(T,TEMP,MIN).

max_number([],Max,Max):-!.

max_number([H|IndexList],Index,Max):-!,

max(H,Index,TempMax),

max_number(IndexList,TempMax,Max).

max(A,B,A):-A >= B,!.

max(_,B,B).

min(A,B,A):-A<=B,!.

min(_,B,B).

% sorting

PREDICATES

insert(INTEGER,BR_TREE)

instree(ILIST,BR_TREE)

nondeterm treemembers(INTEGER,BR_TREE)

CLAUSES

insert(Val,t(Val,_,_)):-!.

insert(NUMBER1,t(NUMBER2,Tree,_)):-

NUMBER1>NUMBER2,!,

insert(NUMBER1,Tree).

insert(Val,t(_,_,Tree)):-insert(Val,Tree).

instree([],_).

instree([H|T],Tree):-

insert(H,Tree),

instree(T,Tree).

treemembers(_,T):-free(T),!,fail.

treemembers(X,t(_,L,_)):-treemembers(X,L).

treemembers(X,t(NUMBER1,_,_)):-X=NUMBER1.

treemembers(X,t(_,_,R)):-treemembers(X,R).

sort_integers(L, L1) :-

instree(L,Tree),

findall(X,treemembers(X,Tree),L1).

goal

write("Cable master solution\n"),

syspath(ExeStartupPath,_),

filenamepath(FullName,ExeStartupPath,"input.txt"),

file_str(FullName,DATA_STRING),

string_to_slist(DATA_STRING,"\n",DATA_LINES),

cable_master(DATA_LINES).