Προγραμματιστική πρόκληση Νο 14 : Χιονονιφάδες

Χιονονιφάδες όλοι μας λένε πως δεν υπάρχουν δυο ίδιες, αλλά ισχύει αυτό; Θέλουμε να γραφτεί ένα πρόγραμμα που να βρίσκει σε μια συλλογή αν δυο χιονονιφάδες είναι ίδιες.

Το πρώτο πράγμα που θα πρέπει να κάνουμε είναι να κάνουμε μια αναπαράσταση και θα αναπαραστήσουμε μια με το μήκος των 6 πλευρών της. Έτσι μια χιονονιφάδα θα είναι για τον υπολογιστή οι αριθμοί \left\{4,3,2,1,6,5\right\}. Αυτή θα είναι ίδια με μια με αριθμούς \left\{5,6,1,2,3,4\right\} δηλαδή αν βλέπουμε την χιονονιφάδα ανάποδα, ή με την \left\{6,5,4,3,2,1\right\} ή με την \left\{6,1,2,3,4,5\right\}. Δηλαδή μπορούμε να περιστρέψουμε τους αριθμούς δεξιόστροφα ή αριστερόστροφα, είναι αριθμοί πάνω σε ενα κύκλο που δεν έχει κάποια αρχή.

Μπορούμε να έχουμε τον ίδιο αριθμό πολλές φορές \left\{6,1,4,1,2,1\right\}. Οι αριθμοί είναι στο διάστημα 0…255.

Έχουμε μετρήσει κάθε νιφάδα και την έχουμε βάλει σαν αριθμούς σε ένα αρχείο. Να γραφτεί πρόγραμμα που θα διαβάζει αυτούς τους αριθμούς και θα βρίσκει αν ο μύθος είναι αληθής ή όχι.

Αυτό είναι ένα ποιο απαιτητικό πρόβλημα, που θα δοκιμάσει την αλγοριθμική σας σκέψη. Μπορούμε όλοι μαζί να το λύσουμε; Πείτε ιδέες. Μπορούμε να το κάνουμε πολύ γρήγορο;

Πηγή

Δεν ξερω να φτιαξω το προγραμμα , αλλα θα ριξω ιδεες :slight_smile:
Η λογικη λεει οτι πιανουμε μια νιφαδα και την συγκρινουμε με τις υπολοιπες. Αν βρουμε μια που δεν ταιριαζει με καμμια αλλη , ο μυθος ειναι αληθης :slight_smile:
Αν η 1η νιφαδα βρεθει ομοια με καποια αλλη , υποθετω πιανουμε την επομενη και την συγκρινουμε με ολες τις υπολοιπες , εκτος την προηγουμενη που προφανως με αυτην εχει συγκριθει προηγουμενως…κ.ο.κ. μεχρι να βρουμε καποια που δεν ταιριαζει με καμμια…
Η συγκριση θα γινεται αριθμος αριθμος. Δηλαδη :
n1 = {a1,a2,a3,a4,a5,a6} , n2={b1,b2,b3,b4,b5,b6}…
Οποτε πιανουμε το a1 και το συγκρινουμε με τα b1,…,b6. Αν βρεθει με καποιο απο αυτα ομοιο , επαναλαμβανουμε με το a2 κ.ο.κ.
Προφανως ο ελεγχος σταματαει στον 1ο αριθμο (a1,…,a6) που θα βρεθει να μην ταιριαζει με κανεναν απο τους υπολοιπους (b1,…,b6). Και επισης ο ελεγχος προχωραει στον επομενο αριθμο , μολις ο προηγουμενος ελεγχος ειναι αληθης.

Φανταζομαι οτι τετοιες “συγκρισεις” ισως ειναι χρονοβορες διαδικασιες…
Οποτε σκεφτομαι και το εξης. Εφοσον μια νιφαδα μπορει να εχει καποιους απο τους 6 αριθμους ομοιους , τοτε μπορουμε να κανουμε εναν αρχικο ελεγχο μεσα στην ιδια την νιφαδα να δουμε αν καποιοι αριθμοι ειναι ομοιοι…
Αν βρεθουν ομοιοι αριθμοι , τοτε στον ελεγχο καποιοι αριθμοι δεν θα ελεγχθουν.
Για παραδειγμα αν η νιφαδα ειναι η { 6,1,4,1,2,1 } (που εγραψες παραπανω και συ) , τοτε οταν ελεγξουμε τον 2ο αριθμο , το 1 , και βρεθει οτι ταιριαζει με καποιον αριθμο μιας αλλης νιφαδας , για τον ελεγχο αυτον , με αυτην την νιφαδα , οι ελεγχοι των αριθμων #4 και #6 θα παραλειφθουν μιας και ειναι ιδιοι με τον αριθμο #2 που ελεγχθηκε.
Υποθετω ετσι μπορουν να απλοποιηθουν και να γινουν πιο γρηγοροι οι συνολικοι ελεγχοι.

Αυτα τα ολιγα απο εμενα :slight_smile:

Για αρχή ορίστε μια μέθοδος που δημιουργεί ένα αρχείο με χιονονιφάδες.

def create_dataset():
    number_of_snowflakes = 1000000
    start = datetime.now()
    f = open("dataset.txt", "w")
    for x in range(0, number_of_snowflakes):
        f.write(str(random.randint(0, 255)) + ",")
        f.write(str(random.randint(0, 255)) + ",")
        f.write(str(random.randint(0, 255)) + ",")
        f.write(str(random.randint(0, 255)) + ",")
        f.write(str(random.randint(0, 255)) + ",")
        f.write(str(random.randint(0, 255)) + "\n")
    f.close()
    finish = datetime.now()
    print("Dataset created in {}".format((finish - start)))

Υ.Γ. το έχω βάλει να φτιάχνει 1.000.000 χιονονιφάδες :cold_face: :cold_face:

2 «Μου αρέσει»

Γειά σου κόσμε!
Να προτείνω λοιπόν μία λύση σε 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
1 «Μου αρέσει»

Ευχαριστώ για τις πρώτες απαντήσεις. Πράγματι κάθε χιονονιφάδα είναι στην πραγματικότητα 12. Αυτό αυξάνει πολύ την πολυπλοκότητα και ο αλγόριθμος σέρνετε. Αν έχουμε 100.000 θα πρέπει να υπολογίσουμε 1.200.000 περιστροφές και κατοπτρισμούς, Κάθε φορά και ο κώδικάς θα σέρνετε. Μπορεί να βελτιωθεί; Μπορούμε να έχουμε κάποιο χρόνο για να δούμε αν και πόσο μπορεί να βελτιωθεί;

Δεν είμαι μαθηματικός και αυτά τα πράγματα δεν τα έχω διδαχτεί, αλλά αναγνωρίζω μια αβελιανή ομάδα συμμετρίας. Μπορεί κάποιος μαθηματικός να επιβεβαιώσει αν είμαι σωστός ή λάθος; Μπορεί να μας βοηθήσει σε κάπου αυτό; Δεν έχω ιδέα…

Έχω προσπαθήσει να σκεφτώ αν υπάρχει κάποια φυσική διάταξη, ίσως να φτιάξω κάποια “συνάρτηση ενέργειας” που η ελαχιστοποιήση της στην αρχή, αλλά με μέτρια αποτελέσματα και δεν κάθισα να λύσω πρώτα το πρόβλημα όπως συνήθως κάνω πριν βάλω μια προγραμματιστική πρόκληση. Υπάρχει κάποια ιδέα; Έχω σκεφτεί κάποιες, αλλά θα τις κρατήσω μυστικές για την ώρα :mask:

Περιμένω και τις δικές σας λύσεις. Μην ξεχνάμε πως σκοπός αυτής της σειράς είναι να παίξουμε, να βρούμε μια ευκαιρία να γράψουμε κώδικα και να γουστάρουμε. Και αν δεν ξέρεις κώδικα, ή τι είναι το ψαρωτικό αβελιανή όμάδα (λολ) πάλι μπορείς να βοηθήσεις. Πες την ιδέα σου όσο ακατέργαστη και αν είναι και ίσως κάποιος πιαστεί από αυτή

1 «Μου αρέσει»

Δεν είμαι μαθηματικός και αυτά τα πράγματα δεν τα έχω διδαχτεί, αλλά αναγνωρίζω μια αβελιανή ομάδα συμμετρίας.

Εγώ αναγνωρίζω έναν αλγεβριστή ανάμεσά μας.

Βρε ξέρεις αν είναι η λέω μαλ ανακρίβειες; Βοηθάει αυτό κάπως (αν είναι) στο να βρεις με κάποιο τρόπο μια “φυσική σειρά”; Κάποια συνάρτηση hash;

1 «Μου αρέσει»

Αυτό που λες για την hash αν ειναι Αβελιανή μου μοιάζει με Θ. Cayley, μπορεί και να μην είναι :slight_smile: . Πρέπει να ξεσκονίσω την Άλγεβρά μου.

Και εγώ κάτι σε hashing σκεφτόμουν για την απλοποίηση της σύγκρισης.

Ακόμα αναρωτιέμαι αν υπάρχει κάποια διανυσματική ή γεωμετρική λύση στο πρόβλημα. Η νιφάδα δηλαδή, παραμένει ένα σχήμα, που στον υπολογιστή το αποτυπώνουμε σε μία λίστα με βάση τα μήκη των πλευρών του. Οπότε ίσως να ήταν δυνατό να υπολογιστεί κάποιο γεωμετρικό μέγεθος, πχ το εμβαδό που να είναι κοινό στις ίδιες νιφάδες, η ακόμα και ένας συνδυασμός. Δύο ίδιες νιφάδες δηλαδή, θα είχαν ίδιο εμβαδόν και ίδια περίμετρο, αφού είναι απλά γυρισμένες σε διαφορετικό προσανατολισμό.
Αν και η περίμετρος όμως είναι εύκολη, το εμβαδό από την άλλη δύσκολα θα υπολογιζόταν σε τόσο ακανόνιστα σχήματα.

Επίσης κάπου στα σχόλια στην πηγή, διάβασα πως λέγανε κάτι για python one liner που λύνει το πρόβλημα και θα πραγματικά ήθελα να το δ αν υπάρχει κάτι τέτοιο.

Και με οδήγησες σε κάτι που είναι μπροστά στα μάτια μας: Αν είχαμε μια μοναδιαία μάζα σε κάθε κορυφή, τότε υπάρχουν δυο κύριοι άξονες αδράνειας. Αυτό μπορεί περιορίσει τις πιθανές διαμορφώσεις σε δυο. Μένει το πρόβλημα πως αυτό απαιτεί τετράγωνα και αναζητώντας μια λύση πάνω σε αυτό σκέφτηκα αν βοηθά να κάνεις ανύψωση μια διάσταση παραπάνω στις ακμές και να είναι οι 7 μάζες πάνω σε ένα μοναδιαίο κύκλο (όπως κάνουμε σε kohonen SOM). Η διαίσθηση μου λέει πως αυτό θα οδηγήσει σε ελάχιστα τετράγωνα. Και αυτό θα μπορεί να λυθεί με μια γραμμή.

Ίσως το υπεραναλύω, υπάρχει ένας απλός τρόπος να μειώσεις τις συγκρίσεις 100+ φορές, και που είναι και υπολογιστικά πολύ εύκολος (*), αλλά το κάνω αυτό όταν περπατάω και πάμε για κάτι παραπάνω :stuck_out_tongue:

(*) Και που μπορεί να τον σκεφτεί ο κάθε ένας, χωρίς πανεπιστημιακές γνώσεις ή γνώση προγραμματισμού. Απλά όπως αντιστρέφεις μια χιονονιφάδα, αντέστρεψε το κριτήριο που ψάχνεις …

1 «Μου αρέσει»

Ας φανταστούμε λοιπόν ότι τα μήκη των πλευρών της χιονονιφάδας είναι μάζες πάνω στον μοναδιαίο κύκλο απλωμένες με συμμετρικό τρόπο (με γωνία π/3 μεταξύ δύο διαδοχικών “μαζών”). Τότε εάν υπολογίσουμε το κέντρο μάζας τους συστήματος, ισχυρίζομαι πως θα απέχει την ίδια απόσταση από την αρχή των αξόνων, με οποιαδήποτε άλλη όμοιά της.

Επομένως αρκεί να βρούμε τα κέντρα μάζας δύο χιονονιφάδων και ελέγχοντας την εν λόγω απόσταση μπορούμε να αποφανθούμε αν είναι όμοιες ή όχι. Μία υλοποίση θα ήταν η εξής:

from collections import deque
from math import cos,sin, pi, sqrt

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 centerOfMass(snow):
    s = snow.split(" ")
    angle, x, y, total_mass = 0, 0, 0, 0
    
    for i in range(len(s)):
        mass = int(s[i])
        x += mass*cos(angle)
        y += mass*sin(angle)
        total_mass += mass
        angle += pi/3
    return (x/total_mass,y/total_mass)


for i in range(n):
    found = False
    snowflake = snowflakes.popleft()
    cm = centerOfMass(snowflake)
    for temp in snowflakes:
        cm_temp = centerOfMass(temp)
        if sqrt(cm[0]**2 + cm[1]**2) == sqrt(cm_temp[0]**2 + cm_temp[1]**2):
            found = True
    if found==True:
        print("Βρέθηκαν δύο όμοιες !")
        break

Θεωρητικά είναι σωστό αλλά καθώς τα νούμερα είναι μικρά με πολλά δεκαδικά ψηφία, εντοπίζω σφάλμα στο τελευυταίο ψηφίο, για παράδειγμα σε δύο όμοιες χιονονιφάδες υπολόγισα τις αποστάσεις :
0.3498258852521568 Για την μία
0.3498258852521567 Για την άλλη
Προφανώς αυτό το σφλάλμα επηρεάζει την λειτουργία του προγράμματος.

2 «Μου αρέσει»

Ενδιαφέρουσα λύση, αλλά αμφισβητώ το γεγονός πως το κέντρο βάρους αρκεί. Είναι ένας μέσος όρος και ο μέσος όρος δεν αποτυπώνει τα δεδομένα. Να το πως και αλλιώς σε μια τραμπάλα το κέντρο βάρους είναι στην μέση είτε παιδιά έχεις στην κάθε άκρη είτε ενηλίκους. Για αυτό είπα για πέρασμα από τις 6 διαστάσεις στις επτά (αλλά έμεινα στην σκέψη και δεν το δούλεψα).

Τώρα τεχνικά υπολογίζεις κάθε φορά τις τριγωνομετρικές σειρές ενώ ξέρεις τις τιμές τους, και κάποιες είναι μηδέν ή ένα.

Να πιάσουμε το ερώτημα αλλιώς; Αντί να κοιτάζουμε αν δυο νιφάδες είναι ίδιες να δούμε αν είναι σίγουρα διαφορετικές;

2 «Μου αρέσει»

Ναι αν κάνουμε scale μια χιονονιφαδα το κέντρο βάρους θα παραμείνει στο ίδιο σημείο. Βέβαια στην περίπτωση που είναι ίδια τα κέντρα βάρους θα μπορούσαμε να ελέγξουμε και το “συνολικό βάρος” ώστε να σιγουρευτούμε ότι δεν πέσαμε σε αυτή την παγίδα.

Το γεγονός ότι το κέντρο βάρους αποτελεί έναν μέσο όρο και δεν αποτυπώνει όλα τα δεδομένα, ήταν το επιθυμητό. Θυσιάζοντας μέρος της πληροφορίας “κατεβαίνει” η διάσταση του προβλήματος και ενδεχομένως να με οδηγούσε σε απλοποίηση του προβλήματος και μείωση των απαιτούμενων ελέγχων, πράγμα που έγινε, καθώς αν γνωρίζουμε το κέντρο μάζας και την συνολική μάζα μπορούμε να αποφανθούμε για το αν είναι όμοιες ή όχι, ενώ αρχικά έπρεπε να γνωρίζω τα μήκη όλων των πλευρών για να συγκρίνω.

Edit:
Στα μαθηματικά η έννοια της ομοιότητας ανάμεσα σε δύο σχήματα συνήθως είναι ένα λόγος ή καλύτερα μια αναλογία. Για παράδειγμα όλες οι τηλεοράσεις είναι όμοιες (έχουν λόγο 16:9) ή όλες οι ελλείψεις που έχουν ίδια εκκεντρότητα είναι όμοιες (έχουν ίδιο λόγο γ/α) ή στα τρίγωνα τα αντίστοιχα κριτήρια κτλπ…
Το ενδιαφέρον πάντως που προέκυψε είναι το εξής:

  • Σε δύο χιονονιφάδες αν το “κέντρο βάρους” απέχει την ίδια απόσταση από την αρχή των αξόνων, είναι όμοιες.
  • Δύο χιονονιφάδες αν είναι όμοιες και έχουν ίδια περίμετρο, τότε είναι ίδιες (όμοιες 1 προς 1)
1 «Μου αρέσει»

Μια πρώτη παρατήρηση: Οι αριθμοί είναι θετικοί, άρα αν δυο χιονονιφάδες είναι διαφορετικές τότε το άθροισμα τους είναι διαφορετικό. Μπορούμε να το χρησιμοποιήσουμε αυτό ως εξής: Θέλουμε μια δομή τύπου λεξικού. Το κλειδί θα είναι το άθροισμα των κλάδων και θα περιέχει για κάθε κλειδί μια λίστα με χιονονιφάδες. Μιας και το κλειδί είναι αριθμός ένα δέντρο θα βόλευε καλύτερα από ένα hash table.

Στην αρχή το πρόγραμμα θα διαβάσει το αρχείο γραμμή γραμμή, και θα τοποθετήσει τα πάντα σε αυτή την δομή. Στην συνέχεια ελέγχει αν υπάρχουν ίδιες χιονονιφάδες για τα κλειδιά που έχουν πάνω από μια καταχωρήσεις. Περιμένω υλοποιήσεις και βελτιώσεις σε αυτό το σχήμα :wink:. Για παράδειγμα να δούμε αν οι αριθμοί είναι και ίδιοι με μια ταξινόμηση.

Δεν ξέρω αν έτσι αξίζει τον κόπο να πας παραπέρα και να βρεις μια βέλτιστη (και μοναδική) απεικόνιση, η απόδοση έχει αυξηθεί κατά πολλές σκάλες μεγέθους από μια απλοϊκή αναζήτηση.

Αλλά σκέφτηκα το εξής: Ας υποθέσουμε για την ώρα πως όλα τα νούμερα σε μια χιονονιφάδα είναι διαφορετικά. Τότε θα υπάρχει ένα μικρότερο και ένα μεγαλύτερο νούμερο. Σκεφτείτε ένα ρολόι. Θα μπορούσαν αυτά να είναι οι δυο δείκτες και θα έχουμε μια ώρα. Μπορούμε να περιστρέψουμε το ρολόι με τέτοιο τρόπο ώστε να δείχνει στις 12:00, δηλαδή να κάνουμε μια αριστερή ή δεξιά ολίσθηση ώστε το μεγαλύτερο στοιχείο να είναι πρώτο. Ο λεπτοδείκτης θα είναι τότε ή στην αριστερή ή στη δεξιά πλευρά. Και στην μια περίπτωση λέμε “12 και κάτι” ενώ στην άλλη λέμε “12 παρά κάτι”. Μπορούμε να αντιστρέψουμε (αλλάζοντας την φορά του shift) την σειρά στην δεύτερη περίπτωση και να έχουμε έτσι μια μοναδική απεικόνιση. Τεχνικά την ελάχιστη απόσταση ανάμεσα στο μεγαλύτερο και το μικρότερο. Αλλά θα δουλέψει αυτό στην γενική περίπτωση που έχουμε 6 δείκτες; Και που μπορεί να έχουμε πολλά στοιχεία με τα ίδιο νούμερα; Αν το έκανα έτσι θα το τσέκαρα με πολλά test cases για σιγουριά.

Περιμένω τις λύσεις σας, ή και άλλες καλές ιδέες. Και μην ξεχνάμε, την πλάκα μας κάνουμε να θυμιθούμε ή να ασχοληθούμε με τον προγραμματισμό θέλουμε και μόνος κριτής είναι ο εαυτός μας. Δώστε τις λύσεις σας, όσο απλές και να είναι :yum:

Μερικές πρόσθετες σκέψεις

  1. Αν κάποιος πάει με την κλασσική μέθοδο και κάνει συγκρίσεις με δεξιόστροφες και αριστερόστροφες περιστροφές, ο κλασσικός τρόπος είναι να αλλάζει τις θέσεις του κάθε διανύσματος. Είναι ανάγκη να γίνει αυτό; Μια τέτοια υλοποίηση δεν θέλει ούτε βαριά μαθηματικά, ούτε είναι δύσκολη και πιστεύω πως είναι στα μέτρα του καθένα.

  2. Για το πως ανεβάζεις την διάσταση και κανονικοποιείς που είχα αναφέρει παραπάνω, να πως το κάνεις σε ένα νευρωνικό δίκτυο αν κάποιος θέλει να δοκιμάσει αυτή την προσέγγιση

2 «Μου αρέσει»

Καλημέρα σε όλους!
Έφτασα στο forum σας εξαιτίας αυτών των προγραμματιστικών threads στα αποτελέσματα της αναζήτησής μου.

Προσωπικά θα προσπαθούσα να μειώσω τον αριθμό των ελέγχων μεταξύ στοιχείων. Όπως έγραψε και ο @Asfodelus αν δεν ταιριάζει το άθροισμα μεταξύ στοιχείων τότε δεν υπάρχει περίπτωση να είναι ίδια όπως και να 'χει. Πρώτα λοιπόν θα έλεγχα το άθροισμα κάθε λίστας (χιονονιφάδας) που είναι η πιο “φθηνή” σύγκριση. Αν τα αθροίσματα τύχαινε παρ΄ όλα αυτά να είναι ίδια θα πήγαινα σε δεύτερου σταδίου έλεγχο των sorted lists. Αν για παράδειγμα η μια χιονονιφάδα ήταν [10,5,6,8,9,3] και η δεύτερη [7,5,7,3,9,10] (ίδια αθροίσματα ) η σύγκριση της sorted μορφής τους θα μου επέτρεπε να ξέρω αν πρέπει να πάω παρακάτω. Πιο ακριβή σύγκριση αλλά σίγουρα πιο φθηνή από τη σύγκριση με 12 διαφορετικές μορφές. Μόνο αν και ο δεύτερος έλεγχος ήταν θετικός θα πήγαινα σαν τρίτο στάδιο να ελέγξω την πρώτη χιονονιφάδα με τις 12 παραλλαγές της δεύτερης.

Αλγοριθμικά, για να αποφύγω την O(n^2) πολυπλοκότητα των πολλαπλών περασμάτων από τα στοιχεία της λίστας (δηλαδή σύγκρινε το πρώτο στοιχείο με όλα, αν δεν ταιριάζει πέτα το, σύγκρινε το επόμενο με όλα τα υπόλοιπα κλπ) θα έκανα πιθανότατα πρώτα ένα πέρασμα για δημιουργία tuples με πρώτο στοιχείο το άθροισμα και δεύτερο τη χιονονιφάδα. Αναγκαστικά δλδ ένα πρώτο Ο(n). Δεύτερο βήμα, θα έκανα ένα GroupBy των αποτελεσμάτων βάσει αθροίσματος (O(n*logn) με τη βιβλιοθήκη Data.List σε Haskell, χωρίς να έχω δοκιμάσει προσεγγίσεις στο stackexchange που ισχυρίζονται Ο(n) (λίγο απίθανο μου φαίνεται) αλλά και πάλι καλύτερο από Ο(n^2). Στη συνέχεια θα πετούσα τα singleton groups και θα ασχολιόμουν μόνο να συγκρίνω τα “ζευγαράκια” με το δεύτερο ή τρίτο check.

Καλώς μας βρήκες @bizi-betiko Talk is cheap. Show methe code :blush:

Να είσαι σίγουρος! Επειδή όμως το έκανα το λάθος παλιότερα, στα πρώτα μου βήματα, προτιμώ να σκέφτομαι πρώτα το πρόβλημα πριν αρχίσω να γράφω κώδικα. Αυτή άλλωστε ήταν και η προτροπή παραπάνω, να ρίξουμε ιδέες.
Καθώς ο ελεύθερος χρόνος μου ανά ημέρα κυμαίνεται ποικίλως από ανύπαρκτος έως περιορισμένος δεν πιστεύω να βιάζεται κανείς. I’ll be back :slight_smile:

Edit:
Οκ, μια πρώτη προσέγγιση, τρέχει σε GHCi (Haskell REPL) περιβάλλον σε ~5s, 10^6 χιονονιφάδες από 0 σε 255
Φυσικά δε βρίσκει τίποτα γιατί οι πιθανότητες είναι ελάχιστες, όπως και με τις πραγματικές χιονονιφάδες :slight_smile:
Αν το αλλάξω σε κλίμακα από 0 έως 10 θα βρει ένα μόνο, για λόγους απόδειξης ([[[3,10,0,3,2,8],[10,0,3,2,8,3]]])
Αν το τρέξω μεταγλωττισμένο σίγουρα θα τρέξει πιο γρήγορα

import Data.List
import System.Random

type Snowflake = [Int]

--create n (defined by the range) test snowflakes
snowflakes :: [Snowflake]
snowflakes = map (\n -> take 6 $ randomRs (0,255) (mkStdGen n)) [1 .. (10^6)]

--filter out those of different sum
equalSumFlakes :: [Snowflake] -> [[Snowflake]]
equalSumFlakes flakes = filter (\list -> length list > 1) groupedFlakes
   where groupedFlakes = groupBy (\a b -> sum a == sum b) flakes

--filter out those of different digits
sameDigitsFlakes :: [[Snowflake]] -> [[Snowflake]]
sameDigitsFlakes flakeGroups =  concat $ map (filter (\list -> length list > 1) . groupBy (\a b -> sort a == sort b)) flakeGroups

rotateL :: [a] -> Int -> [a]
rotateL [] _ = []
rotateL x 0 = x
rotateL x y
  | y > 0 = rotateL (tail x ++ [head x]) (y-1)
  | otherwise = rotateL (last x : init x) (y+1)

reflGroup :: [Int] -> [[Int]] 
reflGroup flake = concat $ map (\list -> (list:reverse list:[])) $ map (\n -> rotateL flake n) [1..6]

--filter out the different snowflakes
sameSnowFlakes :: [[Snowflake]] -> [[Snowflake]]
sameSnowFlakes flakeGroups = concat $ map (filter (\list -> length list > 1) . groupBy (\a b -> elem a (reflGroup b))) flakeGroups

τρέχει με

sameSnowFlakes $ sameDigitsFlakes $ equalSumFlakes snowflakes
δηλαδή τα αποτελέσματα σε σειρά.

Τώρα που το ποστάρισα συνειδητοποιώ ότι δεν έχετε ανεβάσει άλλα αποτελέσματα σε χρόνους

2 «Μου αρέσει»