Λοιπόν, προσπαθώ να φτιάξω ένα πρόγραμμα σε prolog που θα δέχεται σαν όρισμα έναν πίνακα από πίνακες με στοιχεια αριθμούς από το 0-9. Φανταστειτε ότι κάθε πίνακας είναι ένας αριθμός π.χ.[1,2,3]-->123. Σκοπός μου είναι να μεγιστοποιήσω το άθροισμα των αριθμών αυτών με τις παρακάτω δύο διαδικασίες:
α) Μπορώ να "διαστρέψω" έναν αριθμό (κατά γραμμή) δηλαδή [α,β,γ]---->[9-α,9-β,9-γ]
β)Μπορώ να διαστρέψω κάθε ψηφίο ίδιας "σημαντικότητας" από κάθε αριθμό (κατά στήλη) δηλαδή [[α,β,γ],[δ,ε,ζ],[η,θ,ι]]----->[[α,9-β,γ],[δ,9-ε,ζ],[η,9-θ,ι]]
Ο αλγόριθμος που έχω σκεφτεί πάει ως εξής βλέπω ποιοι αριθμοί έχουν το MSB τους μεγαλύτερο του 5 και τους διαστρέφω κατά γραμμή και στη συνέχεια βλέπω ποια από τις στήλες έχει άθροισμα μικρότερο από (9*(length του πίνακα των πινάκων)) div 2 και τη διαστρέφω κατά στήλη.
Ο αλγόριθμός αυτός δουλεύει (στο χέρι) για κάθε test case που έχω ( γνωρίζω πως ανάλογα με τους αριθμούς μπορεί να βρεθεί αποδοτικότερος απλά αυτό δεν επηρεάζει την συγκεκριμένη απορία μου).
Παραθέτω τον κώδικα της υλοποίησης μέχρι εκεί που έχω φτάσει
- Spoiler: εμφάνιση/απόκρυψη
[code]diastrofi1([],[]).
diastrofi1([H|T],[S|E]):- // κατά γραμμη
S is 9-H,
diastrofi1(T,E).
dias([],[],_). //διαστρέφει ένα συγκεκριμένο ψηφίο του αριθμού (χρησιμοποιείται στη διαστροφή κατά στήλη
dias([H|T],[S|E], N) :-
((N=:=0)
->S is 9-H
; S=H),
NewN is N-1,
dias(T, E, NewN).
diastrofi2([],[],_). //κατά στήλη
diastrofi2([H|T],[S|E],N):-
dias(H,S,N),
diastrofi2(T,E,N).
chck([H|T],[S|E]):- //ελέγχει αν κάποιος αριθμός έχει ΜΣΒ μεγακλυτερο του 5 και αν ναι τον διαστρέφει
(H>=5)
->diastrofi1([H|T],[S|E])
;[H|T]=[S|E].
check1([],[]). //εφαρμόζει το παραπάνω σε όλο τον πίνακα
check1([H|T],[S|E]):-
chck(H,S),
check1(T,E).
mySum([],_,0). // Αθροίζει τα ψηφία κάποιας συγκεκριμένης σημαντικότητας από κάθε αριθμό του πίνακα
mySum([H|T],N,Sum):-
nth0(N,H,X),
mySum(T,N,TailSum),
Sum is X+TailSum.
check2(L1,0,L1). // Ελέγχει αν κάποια στήλη έχει άθροισμα μικρότερο από (9*(length του πίνακα των πινάκων)) div 2 και αν ναι τον διαστρέφει.
check2(L1,N,L2):-
(N=\=0)
->mySum(L1,N,Sum),
length(L1,Temp1),
Temp2 is Temp1*9,
NewN is (N-1),
check2(L1,NewN,L3),
(Sum =<(Temp2//2))->
(diastrofi2(L3,L2,N))
;check2(L1,NewN,L2).
[/code]
Λοιπόν το πρόβλημα είναι το εξής στο τελευταίο κατηγόρημα αν σε κάποιο testcase κάποια στήλη πληρεί την συνθήκη και κάποια άλλη όχι δίνει πάντα false αντί να επιστρέψει τον πίνακα. ΑΝτίθετα αν σε ένα testcase όλες οι στήλες πληρούν την συνθήκη ή όλες οι στήλες δεν πληρούν την συνθήκη τότε το κατηγόρημα επιστρέφει τον πίνακα φτιαγμένο όπως πρέπει. Οπότε θα μπορούσε κάποιος να μου πει γιατί επιστρέφει false?
Π.Χ.
?- check2([[1,2,3,4,5],[2,3,4,5,9],[0,0,9,3,9],[7,6,9,4,9]],1,L).
L = [[1, 7, 3, 4, 5], [2, 6, 4, 5, 9], [0, 9, 9, 3, 9], [7, 3, 9, 4, 9]].
και
?- check2([[1,2,3,4,5],[2,3,4,5,9],[0,0,9,3,9],[7,6,9,4,9]],2,L).
false.
?- check2([[1,2,3,4,5],[2,3,4,5,9],[0,0,9,3,9],[7,6,9,4,9]],4,L).
false.