Γειά σου κόσμε!
Να προτείνω λοιπόν μία λύση σε Python. Κοιτάζοντας την εκφώνηση από την πηγή του αρχικού προβλήματος, θα παραμείνω πιστός σε αυτήν όσον αφορά το input του προγράμματος, δηλαδή θα διαβάζει από ένα αρχείο στο οποίο στην πρώτη γραμμή υπάρχει ο πληθάριθμος των χιονονιφάδων (έστω n) και στις υπόλοιπες γραμμές θα υπάρχουν τα μήκη των πλευρών χωρισμένα με κενό.
Για παράδειγμα ένα αρχείο αυτής της μορφής θα ήταν το ακόλουθο:
2
1 2 3 4 5 6
4 3 2 1 6 5
Η υλοποίηση είναι η εξής :
from collections import deque
snowflakes = deque()
f = open("snowflakes.txt", mode="r", encoding="utf-8")
lines = f.read()
for line in lines.splitlines():
snowflakes.append(line)
f.close()
n = int(snowflakes.popleft())
def shiftR(snow):
s = snow.split(" ")
s = [*s[1:],s[0]]
return " ".join(s)
def inv(snow):
s = snow.split(" ")
s.reverse()
return " ".join(s)
for i in range(n):
found = False
snowflake = snowflakes.popleft()
for temp in snowflakes:
for _ in range(6):
temp = shiftR(temp)
if snowflake == temp or snowflake == inv(temp):
found = True
if found == True:
print("Βρέθηκαν δύο όμοιες !")
break
Θα παίρνουμε την πρώτη χιονονιφάδα και θα ελέγχουμε μία προς μία όλες τις υπόλοιπες για το αν είναι όμοιες. Εαν δεν είναι όμοιες τότε μπορούμε να την αφαιρέσουμε, επομένως θα χρησιμοποιήσουμε ένα deque() στο οποίο θα εκχωρίσουμε τις χιονονιφάδες, ώστε να γίνεται αποδοτικά το popleft().
Για τον έλεγχο ομοιότητας, θα πρέπει να κάνουμε 6 περιστροφές και 6 αναστροφές για κάθε χιονονιφάδα, ώστε να σιγουρευτούμε ότι δεν είναι ίδια με την αρχική. Με την βοήθεια της shiftR κάνουμε περιστροφή δεξιά κατά μία θέση, ενώ με την inv κάνουμε αναστροφή. π.χ. :
snowflake = "1 2 3 4 5 6"
shiftR(snowflake)
'2 3 4 5 6 1'
inv(snowflake)
'6 5 4 3 2 1'
Μόλις βρεθούν δύο όμοιες, το πρόγραμμα τερματίζει και τυπώνει το αντίστοιχο μήνυμα.
Με μια πρόχειρη σκέψη η χρονική πολυπλοκότητα είναι Ο(n^2).
Για παράδειγμα μπορέιτε να δοκιμάσετε τον κώδικα σε ένα αρχείο snowflakes.txt που ετοίμασα με 100 χιονονιφάδες, όπου η πρώτη και τελευταία χιονονιφάδα ταυτίζονται !
100
68 17 218 194 227 122
228 129 103 26 175 75
20 62 210 83 165 164
42 103 240 23 48 129
103 238 204 24 193 242
123 180 37 89 241 101
192 210 76 4 106 98
93 131 159 58 199 173
145 236 89 236 190 145
140 89 52 86 143 148
30 210 218 89 221 178
214 49 226 229 190 98
15 171 232 89 45 185
203 78 64 254 231 80
66 175 203 150 64 161
172 142 40 199 83 139
215 59 37 161 35 136
241 92 134 69 135 0
91 119 194 38 94 61
226 25 171 101 120 53
149 109 87 179 251 118
73 241 207 247 65 179
178 237 93 183 85 13
93 120 8 42 6 62
54 195 69 177 97 105
69 98 71 206 95 223
161 28 229 223 239 69
135 3 123 11 236 124
4 251 181 90 110 134
68 75 13 230 24 47
54 217 14 62 8 221
215 45 224 131 4 70
247 80 235 164 46 77
63 136 70 220 255 88
43 194 193 207 189 71
173 137 228 188 168 61
67 36 60 215 123 108
36 23 255 244 176 145
42 221 60 64 215 11
158 3 59 126 190 22
241 85 164 186 178 181
109 170 241 138 217 31
190 56 9 68 222 145
187 225 139 22 153 220
249 113 184 118 127 255
212 178 102 39 116 78
222 47 204 198 160 158
80 243 238 26 115 89
79 59 152 76 208 135
90 139 233 124 207 21
140 169 105 71 33 11
244 126 117 54 211 59
71 82 15 115 139 27
101 225 234 231 224 129
238 117 4 157 233 71
96 65 135 216 104 143
242 166 62 152 243 94
111 124 194 88 89 151
27 111 103 131 205 145
180 180 105 5 61 73
9 97 231 90 112 163
185 229 154 5 161 170
109 148 213 177 132 26
185 141 68 174 100 51
40 49 192 62 82 75
16 233 120 185 142 217
64 149 90 49 173 99
231 41 177 182 128 180
168 64 172 102 93 172
73 9 179 178 18 1
64 229 185 154 177 38
8 119 248 55 71 214
27 244 43 99 216 74
96 57 106 160 138 247
20 21 27 144 136 188
43 115 5 83 195 39
247 84 115 185 185 232
123 8 236 37 233 212
125 30 97 111 131 200
207 43 38 29 168 132
103 145 163 174 138 173
17 189 232 160 50 166
159 90 85 80 27 109
112 182 105 71 147 156
194 174 189 127 11 172
72 101 54 224 146 250
164 146 10 157 189 198
124 34 238 85 189 129
82 187 119 123 177 113
190 29 199 237 125 18
124 56 37 219 230 134
252 160 226 231 126 50
223 93 2 231 101 184
36 251 246 197 81 249
6 222 135 123 138 138
148 96 234 117 18 62
240 140 169 60 227 107
108 45 163 145 48 105
46 45 68 16 139 235
68 17 218 194 227 122
. Για παράδειγμα να δούμε αν οι αριθμοί είναι και ίδιοι με μια ταξινόμηση.
