Re: [eclipse-clp-users] Segmentation fault when loading large source file

From: Sergii Dymchenko <kit1980_at_gmail.com>
Date: Mon, 18 Feb 2013 17:48:01 -0800
Thank you, Joachim.

I can assure you that this is not a homework, this is a problem from
recent http://ch24.org/ test round, that took place last Friday.

BTW, I would like to recommend to participate in this contest to all
fellow ECLiPSe users - the contests rules allow to use any programming
language or system, and most of the problems have 10 input of
gradually increasing size, so constraint programming can be used to
quickly solve some of not so large inputs without inventing
specialized algorithm. The contest's electronic round scheduled to
this Saturday, but every team must consist of exactly three members
and the contest time is inconvenient for the USA.

As for your program, group_same_key_values looks a bit intimidating to
me. I don't think I could had come up with something like this during
the contest.

Sergii.


On Mon, Feb 18, 2013 at 5:28 PM, Joachim Schimpf <jschimpf_at_coninfer.com> wrote:
> On 18/02/2013 23:34, Sergii Dymchenko wrote:
>> Yes, this is generated (I can't imagine how crazy one should be to
>> type it by hand :-D)
>>
>> I used Python to generate the ECLiPSe program. I was very short on
>> time (it was a programming contest) and I didn't feel confident enough
>> to transform the data to constraints in ECLiPSe itself. In the end I
>> solved this particular input (there were ten inputs from very small to
>> this huge one) by generating a program for B-Prolog (while ECLiPSe was
>> much faster for all other inputs, probably because of OSI CLP solver
>> vs GLPK in B-Prolog).
>>
>> The task itself is really just a system of linear equations.
>>
>> For example, the simplest input was:
>>
>> 5 6
>> 1.638 1.483 1.779 1.304 1.108
>> 4 1 0.2955
>> 1 2 0.479
>> 1 3 0.2417
>> 2 3 0.2139
>> 4 5 0.451
>> 4 3 0.0398
>>
>> It means that there are 5 variables P1..P5 and 6 data lines describing
>> relations between variables. So
>> P1 = 1.638 + 0.0479 * P2 (corresponds to '1 2 0.479' in the input) +
>> 0.02417 * P3 (corresponds to '1 3 0.2417')
>> P2 = 1.483 + 0.2139 * P3 (corresponds '2 3 0.2139')
>> etc.
>>
>> The original problem description can be found on the page 13 of
>> http://ch24.org/static/archive/2013/2013_preec.pdf
>
>
> Well, I hope I am not doing someone's homework here, but it may be
> a nice illustrative example:
>
> :- lib(eplex).
>
> main(File) :-
>
>      % read the data file
>      open(File, read, Input),
>      read_numbers_list(Input, [NVars,NLines]),
>      read_numbers_list(Input, Consts),
>      ( for(_,1,NLines), foreach(Line,Lines), param(Input) do
>          read_numbers_list(Input, Line)
>      ),
>      close(Input),
>
>      % create the variable array P
>      dim(P, [NVars]),
>
>      % create the constraints
>      sort(1, =<, Lines, Sorted), % input looks unsorted
>      group_same_key_values(1, Sorted, Groups),
>      ( for(I,1,NVars), foreach(CI,Consts), fromto(Groups,Gs1,Gs2,[]), param(P) do
>          ( Gs1 = [Group|Gs2], Group=[[I,_,_]|_] ->
>              ( foreach([_I,J,C],Group), foreach(Term,Terms), param(P) do
>                  Term = C*P[J]
>              )
>          ;
>              % no data line for P[I]!
>              Terms = [], Gs2 = Gs1
>          ),
>
>          % state the constraint!
>          P[I] $= CI + sum(Terms)
>      ),
>
>      % solve
>      eplex_solver_setup(min(0)),
>      eplex_solve(_),
>      ( foreacharg(Pi, P) do
>          eplex_var_get(Pi, typed_solution, Val),
>          write(Val), write(' ')
>      ),
>      nl.
>
>
> % this is (almost) your own read_numbers_list/1 from comp.lang.prolog ;)
> read_numbers_list(Stream, Ns) :-
>      read_string(Stream, end_of_line, _, String),
>      split_string(String, " ", " ", Ss),
>      ( foreach(S, Ss), foreach(N, Ns) do
>          number_string(N, S)
>      ).
>
> % this should really be in a library...
> group_same_key_values(_Pos, [], []).
> group_same_key_values(Pos, [KV|List], [[KV|KVs]|GroupedList]) :-
>          arg(Pos, KV, K),
>          group_same_key_values2(Pos, List, K, KVs, GroupedList).
>
>      group_same_key_values2(_Pos, [], _, [], []).
>      group_same_key_values2(Pos, [KV|List], K, [KV|KVs], GroupedList) :-
>          arg(Pos, KV, K1), K == K1, !,
>          group_same_key_values2(Pos, List, K, KVs, GroupedList).
>      group_same_key_values2(Pos, [KV|List], _K, [], [[KV|KVs]|GroupedList]) :-
>          arg(Pos, KV, K),
>          group_same_key_values2(Pos, List, K, KVs, GroupedList).
>
>
> Cheers,
> Joachim
>
>
> ------------------------------------------------------------------------------
> The Go Parallel Website, sponsored by Intel - in partnership with Geeknet,
> is your hub for all things parallel software development, from weekly thought
> leadership blogs to news, videos, case studies, tutorials, tech docs,
> whitepapers, evaluation guides, and opinion stories. Check out the most
> recent posts - join the conversation now. http://goparallel.sourceforge.net/
> _______________________________________________
> ECLiPSe-CLP-Users mailing list
> ECLiPSe-CLP-Users_at_lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/eclipse-clp-users
Received on Tue Feb 19 2013 - 01:48:08 CET

This archive was generated by hypermail 2.2.0 : Tue Feb 19 2013 - 06:14:32 CET