Пролог: как оптимизировать этот код (Решение головоломки 123456789=100)

Итак, возникла загадка:

Это уравнение неполное: 1 2 3 4 5 6 7 8 9 = 100. Один из способов сделать его точным — добавить семь знаков «плюс» и «минус», например: 1 + 2 + 3 — 4 + 5 + 6 + 78 + 9. = 100. Как это сделать, используя только 3 знака плюс или минус?

Я совсем новичок в Прологе, решил головоломку, но мне интересно, как ее оптимизировать

makeInt(S,F,FinInt):-
    getInt(S,F,0,FinInt).

getInt(Start, Finish, Acc, FinInt):-
    0 =< Finish - Start,
    NewAcc is Acc*10 + Start,
    NewStart is Start +1,
    getInt(NewStart, Finish, NewAcc, FinInt).
getInt(Start, Finish, A, A):- 
    0 > Finish - Start.

itCounts(X,Y,Z,Q):-
    member(XLastDigit,[1,2,3,4,5,6]),
    FromY is XLastDigit+1,
    numlist(FromY, 7, ListYLastDigit),
    member(YLastDigit, ListYLastDigit),
    FromZ is YLastDigit+1,
    numlist(FromZ, 8, ListZLastDigit),
    member(ZLastDigit,ListZLastDigit),
    FromQ is ZLastDigit+1, 
    member(YSign,[-1,1]),
    member(ZSign,[-1,1]),
    member(QSign,[-1,1]),
    0 is XLastDigit + YSign*YLastDigit + ZSign*ZLastDigit + QSign*9,
    makeInt(1, XLastDigit, FirstNumber),
    makeInt(FromY, YLastDigit, SecondNumber),
    makeInt(FromZ, ZLastDigit, ThirdNumber),
    makeInt(FromQ, 9, FourthNumber),
    X is FirstNumber,
    Y is YSign*SecondNumber,
    Z is ZSign*ThirdNumber,
    Q is QSign*FourthNumber,
    100 =:= X + Y + Z + Q.

optimization prolog cryptarithmetic-puzzle
person Yegor    schedule 07.04.2017    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Не уверен, что это означает оптимизацию. Просто код короче:

sum_123456789_eq_100_with_3_sum_or_sub(L) :-
    append([G1,G2,G3,G4], [0'1,0'2,0'3,0'4,0'5,0'6,0'7,0'8,0'9]),
    maplist([X]>>(length(X,N), N>0), [G1,G2,G3,G4]),
    maplist([G,F]>>(member(Op, [0'+,0'-]),F=[Op|G]), [G2,G3,G4], [F2,F3,F4]),
    append([G1,F2,F3,F4], L),
    read_term_from_codes(L, T, []),
    100 is T.
person CapelliC    schedule 07.04.2017

arrow_upward
0
arrow_downward

Мне потребовалось некоторое время, но я понял, что делает ваш код. Это что-то вроде этого:

itCounts(X,Y,Z,Q) :- % generate X, Y, Z, and Q s.t. X+Y+Z+Q=100, etc.
  generate X as a list of digits
  do the same for Y, Z, and Q
  pick the signs for Y, Z, and Q
  convert all those lists of digits into numbers
  verify that, with the signs, they add to 100.

Неэффективность здесь в том, что все тестирование проводится в последнюю минуту. Вы можете повысить эффективность, если сможете отбросить некоторые возможные решения, как только вы выберете одно из своих чисел, то есть протестировать раньше.

itCounts(X,Y,Z,Q) :- % generate X, Y, Z, and Q s.t. X+Y+Z+Q=100, etc.
  generate X as a list of digits, and convert it to a number
  if it's so big or small the rest can't possibly bring the sum back to 100, fail
  generate Y as a list of digits, convert to number, and pick it sign
  if it's so big or so small the rest can't possibly bring the sum to 100, fail
  do the same for Z
  do the same for Q

Ваша функция уже работает довольно быстро, даже если я ищу все возможные решения. Он выбирает только 6 X; 42 года; 224 Z; и 15 вопросов. Я не думаю, что оптимизация будет стоить вашего времени.

Но если вы действительно хотите: я проверил это, поместив функцию тестирования сразу после выбора X. Это уменьшило 6 X до 3 (все до того, как было найдено решение); от 42 до 30 лет; 224 Z до 184; и с 15 вопросов до 11. Я полагаю, что мы могли бы уменьшить его еще больше, проверив сразу после выбора Y, чтобы увидеть, является ли X YSign Y уже настолько большим или маленьким, что не может быть никакого решения.

В программах PROLOG, требующих больших вычислительных ресурсов, части "теста" помещаются раньше в алгоритмы создания и тестирования могут очень помочь.

person Topological Sort    schedule 09.04.2017