Пролог - отслеживание нескольких счетчиков сумм - PullRequest
Новая
       41

Пролог - отслеживание нескольких счетчиков сумм

1 голос
/ 16 мая 2019

Итак, у меня есть список, который выглядит так: 

[ 
  ["p1", "p2", "100", "Storgatan"], 
  ["p1", "p3", "200", "Lillgatan"], 
  ["p2", "p4", "100", "Nygatan"], 
  ["p3", "p4", "50", "Kungsgatan"], 
  ["p4", "p5", "150", "Kungsgatan"]
]

Элементы в каждом вложенном списке представляют (по порядку):
1-й элемент = начальная точка
2-й элемент = конечная точка
3-й элемент = расстояние
4-й элемент = название улицы.

Теперь я должен написать предикат, который определяет, какая улица самая короткая, а какая самая длинная, а также их соответствующие (суммированные) расстояния.

Например, конечный результат должен выглядеть примерно так: 

Longest street: Kungsgatan, 200
Shortest street: Storgatan, 100

Я не очень понимаю, почему начальная и конечная точки являются важной информацией здесь. Моя текущая идея состоит в том, чтобы собрать все уникальные названия улиц, поместить их в отдельный список вместе со счетчиком для каждой улицы, которая начинается с нуля, а затем использовать этот список для накопления всех расстояний для каждой отдельной улицы.

Что-то вроде: 

create_sum_list([
   ["p1", "p2", "100", "Storgatan"], 
   ["p1", "p3", "200", "Lillgatan"], 
   ["p2", "p4", "100", "Nygatan"], 
   ["p3", "p4", "50", "Kungsgatan"], 
   ["p4", "p5", "150", "Kungsgatan"]
], SL).

SL= [[Storgatan, 0], [Lillgatan, 0],
     [Nygatan, 0], [Kungsgatan ,0]]

accumulate(SL, List).

List=[[Storgatan, 100], [Lillgatan, 200], 
      [Nygatan, 100], [Kungsgatan ,200]]

Это, вероятно, глупая идея, и, вероятно, есть способ лучше решить эту проблему. Я думал о многих разных идеях, когда я либо захожу в тупик, либо они слишком сложны для такой «простой» задачи.

Я могу легко достичь этого с помощью «нормального» императивного программирования, но я новичок в логическом программировании и прологе. Я понятия не имею, как этого добиться.

Помощь

Спасибо!

Ответы [ 2 ]

1 голос
/ 16 мая 2019

Если у вас уже есть список, и вы хотите сгруппировать по названию улицы и суммировать длины, вы должны решить, как вы будете группировать. Одним из способов является использование библиотеки (пар): 

streets_lengths(S, L) :-
    maplist(street_name_and_length, S, NL),
    keysort(NL, NL_sorted),
    group_pairs_by_key(NL_sorted, G),
    maplist(total_lengths, G, GT),
    transpose_pairs(GT, By_length), % sorts!
    group_pairs_by_key(By_length, L).

street_name_and_length([_, _, N, L], L_atom-N_number) :-
    number_string(N_number, N),
    atom_string(L_atom, L).

total_lengths(S-Ls, S-T) :-
    sum_list(Ls, T).

Вы можете использовать это так: 

?- streets_lengths([
   ["p1", "p2", "100", "Storgatan"],
   ["p1", "p3", "200", "Lillgatan"],
   ["p2", "p4", "100", "Nygatan"],
   ["p3", "p4", "50", "Kungsgatan"],
   ["p4", "p5", "150", "Kungsgatan"]
], SL).
SL = [100-['Storgatan', 'Nygatan'], 200-['Lillgatan', 'Kungsgatan']].

Поскольку улиц одинаковой длины может быть много, результаты возвращаются сгруппированными по длине. Вы можете получить «самый короткий» и «самый длинный», получив первый и последний элемент списка, например: 

L = [First|_], last(L, Last)
1 голос
/ 16 мая 2019

Поскольку это домашнее задание, я не дам вам весь ответ, но ключевую часть кода.

Как я отмечал в комментариях, формат структуры имеет значение, например, список, термины, атомы, строки и т. д. 

test(Street_lengths,Shortest) :-
    List =
        [
         street(p1, p2, 100, 'Storgatan'),
         street(p1, p3, 200, 'Lillgatan'),
         street(p2, p4, 100, 'Nygatan'),
         street(p3, p4, 50,  'Kungsgatan'),
         street(p4, p5, 150, 'Kungsgatan')
        ],
    street_lengths(List,Street_lengths),
    lengths1(Street_lengths,Lengths),
    min_list(Lengths,Min),
    convlist(value_shortest2(Min),Street_lengths,Shortest).

street_lengths([H|T],Street_lengths) :-
    merge_streets(H,T,Street_lengths).

% 2 or more items in list
merge_streets(street(_,_,Length0,Name),[street(_,_,Length1,Name),street(_,_,Length2,Name2)|Streets0],[street(Length,Name)|Streets]) :-
    Length is Length0 + Length1,
    merge_streets(street(_,_,Length2,Name2),Streets0,Streets).
merge_streets(street(_,_,Length0,Name0),[street(_,_,Length1,Name1)|Streets0],[street(Length0,Name0)|Streets]) :-
    Name0 \= Name1,
    merge_streets(street(_,_,Length1,Name1),Streets0,Streets).

% 1 item in list
merge_streets(street(_,_,Length0,Name),[street(_,_,Length1,Name)],[street(Length,Name)]) :-
    Length is Length0 + Length1.
merge_streets(street(_,_,Length0,Name0),[street(_,_,Length1,Name1)],[street(Length0,Name0)|Streets]) :-
    Name0 \= Name1,
    merge_streets(street(_,_,Length1,Name1),[],Streets).

% no item in list
merge_streets(street(_,_,Length,Name),[],[street(Length,Name)]).

lengths1(List,Lengths) :-
    maplist(value_length1,List,Lengths).

value_length1(street(Length,_),Length).

value_shortest2(Min,street(Min,Name),street(Min,Name)).

Пример выполнения: 

?- test(Street_lengths,Shortest).
Street_lengths = [street(100, 'Storgatan'), street(200, 'Lillgatan'), street(100, 'Nygatan'), street(200, 'Kungsgatan')],
Shortest = [street(100, 'Storgatan'), street(100, 'Nygatan')] ;
false.

Я оставил вам больше всего времени, но это должен быть поход по пирогу.

Для отображенияинформация, как вы отметили в вопросе, я бы использовал format / 2 .

Так что теперь вам нужно либо изменить способ считывания данных в формате для этого кода, либо изменить этот код для работы с тем, как вы структурировали данные.ИМХО, я бы изменил данные для работы с этой структурой.

Если вы хотите знать, насколько эффективен ваш код, вы можете использовать time / 1 

?- time(test(Street_lengths,Shortest)).
% 44 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
Street_lengths = [street(100, 'Storgatan'), street(200, 'Lillgatan'), street(100, 'Nygatan'), street(200, 'Kungsgatan')],
Shortest = [street(100, 'Storgatan'), street(100, 'Nygatan')] ;
% 17 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
false.
...