fork download
copy 
  1. # Copyright Big-O Coding
  2.  
  3. secret_string_S = "Big-O Coding {le@rn a1g0ri7ths vv1th 3xp3rt5}"
  4. secret_string_length = len(secret_string_S)
  5.  
  6. def count_correct_characters(user_string):
  7.     assert len(user_string) == secret_string_length
  8.     count = 0
  9.     for i in range(len(user_string)):
  10.         if user_string[i] == secret_string_S[i]:
  11.             count += 1
  12.  
  13.     return count
  14.  
  15. def check_answer(user_string):
  16.     assert len(user_string) == secret_string_length
  17.  
  18.     correct_count = count_correct_characters(user_string)
  19.  
  20.     if correct_count == secret_string_length:
  21.         return True
  22.  
  23.     return False
  24.  
  25. import random
  26. characters_set = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOP"\
  27. "QRSTUVWXYZ 1234567890, .-;:_!\"#%&/()=?@${[]}" # Các ký tự hợp lệ
  28.  
  29. population = 100 # Số lượng cá thể trong một thế hệ
  30. carried_over_rate = 0.1 # Tỉ lệ cá thể có chỉ số khỏe mạnh được cao được mang trực tiếp sang thế hệ sau
  31. parent_portion = 0.5 # Tỉ lệ cá thể được lựa chọn để kết hợp với nhau
  32. mutation_rate = 0.05 # Tỉ lệ đột biến
  33.  
  34. def initialize_generation():
  35.     first_generation = []
  36.     for i in range(population):
  37.         string = ""
  38.         for j in range(secret_string_length):
  39.             # Thêm một ký tự ngẫu nhiên trong 
  40.             # characters_set vào chuỗi hiện tại
  41.             string += random.sample(characters_set, 1)[0]
  42.  
  43.         # Tìm chỉ số khỏe mạnh của chuỗi
  44.         fitness_score = count_correct_characters(string)
  45.  
  46.         # Thêm cá thể vào trong thế hệ hiện tại
  47.         first_generation.append((string, fitness_score))
  48.  
  49.     return first_generation
  50.  
  51. def perform_selection(first_str, second_str):
  52.     assert len(first_str) == len(second_str)
  53.  
  54.     L = len(first_str)
  55.     result = ""
  56.  
  57.     # Kết hợp hai chuỗi với nhau
  58.     for i in range(L):
  59.         choice = random.randint(0, 1)
  60.         result += first_str[i] if choice else second_str[i]
  61.  
  62.     # Thực hiện đột biến
  63.     for i in range(L):
  64.         choice = random.random()
  65.         if choice < mutation_rate:
  66.             result = result[:i] + random.sample(characters_set, 1)[0] + result[i+1:]
  67.  
  68.     # Tìm chỉ số khỏe mạnh của chuỗi
  69.     fitness_score = count_correct_characters(result)
  70.  
  71.     return (result, fitness_score)
  72.  
  73. def solve():
  74.     generation_id = 0
  75.     next_generation = initialize_generation()
  76.     current_generation = []
  77.  
  78.     while True:
  79.         generation_id += 1
  80.         current_generation = next_generation
  81.         next_generation = []
  82.  
  83.         # Sắp xếp các cá thể theo chỉ số khỏe mạnh giảm dần
  84.         current_generation.sort(key=lambda tup: -tup[1])
  85.  
  86.         # In cá thể tốt nhất của từng thế hệ
  87.         best = current_generation[0]
  88.         # Khắc phục tràn stdout trên ideone
  89.         if generation_id > 300:
  90. 	        print(f"Generation {generation_id}")
  91. 	        print(f"Best string: {best[0]}")
  92. 	        print(f"Fitness score: {best[1]}")
  93. 	        print("--------------------------")
  94.         if best[1] == secret_string_length:
  95.             break
  96.  
  97.         # Chọn 10% cá thể có chỉ số khỏe mạnh cao nhất
  98.         # để mang sang thể hệ sau
  99.         carried_over_idx = int(population * carried_over_rate)
  100.         next_generation += current_generation[:carried_over_idx]
  101.  
  102.         # Chọn 50% cá thể có chỉ số khỏe mạnh cao nhất
  103.         # để kết hợp với nhau
  104.         parent_idx = int(population * parent_portion)
  105.         parent_group = current_generation[:parent_idx]
  106.  
  107.         while len(next_generation) < population:
  108.             # Chọn ngẫu nhiên hai cá thể
  109.             first, second = random.sample(parent_group, 2)
  110.  
  111.             new_child = perform_selection(first[0], second[0])
  112.  
  113.             next_generation.append(new_child)
  114.  
  115. solve()
  116.  
Success #stdin #stdout 3.34s 11724KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Generation 301
Best string: Big-O Coding {le@rn a1g0ri ths v91th 3xp3rt5}
Fitness score: 43
--------------------------
Generation 302
Best string: Big-O Coding {le@rn a1g0ri ths v91th 3xp3rt5}
Fitness score: 43
--------------------------
Generation 303
Best string: Big-O Coding {le@rn a1g0ri ths v91th 3xp3rt5}
Fitness score: 43
--------------------------
Generation 304
Best string: Big-O Coding {le@rn a1g0ri ths v91th 3xp3rt5}
Fitness score: 43
--------------------------
Generation 305
Best string: Big-O Coding {le@rn a1g0ri ths v91th 3xp3rt5}
Fitness score: 43
--------------------------
Generation 306
Best string: Big-O Coding {le@rn a1g0ri ths v91th 3xp3rt5}
Fitness score: 43
--------------------------
Generation 307
Best string: Big-O Coding {le@rn a1g0ri ths v91th 3xp3rt5}
Fitness score: 43
--------------------------
Generation 308
Best string: Big-O Coding {le@rn a1g0ri ths v91th 3xp3rt5}
Fitness score: 43
--------------------------
Generation 309
Best string: Big-O Coding {le@rn a1g0ri ths v91th 3xp3rt5}
Fitness score: 43
--------------------------
Generation 310
Best string: Big-O Coding {le@rn a1g0ri ths v91th 3xp3rt5}
Fitness score: 43
--------------------------
Generation 311
Best string: Big-O Coding {le@rn a1g0ri ths v91th 3xp3rt5}
Fitness score: 43
--------------------------
Generation 312
Best string: Big-O Coding {le@rn a1g0ri ths v91th 3xp3rt5}
Fitness score: 43
--------------------------
Generation 313
Best string: Big-O Coding {le@rn a1g0ri ths v91th 3xp3rt5}
Fitness score: 43
--------------------------
Generation 314
Best string: Big-O Coding {le@rn a1g0ri ths v91th 3xp3rt5}
Fitness score: 43
--------------------------
Generation 315
Best string: Big-O Coding {le@rn a1g0ri ths v91th 3xp3rt5}
Fitness score: 43
--------------------------
Generation 316
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 317
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 318
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 319
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 320
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 321
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 322
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 323
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 324
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 325
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 326
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 327
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 328
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 329
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 330
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 331
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 332
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 333
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 334
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 335
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 336
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 337
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 338
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 339
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 340
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 341
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 342
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 343
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 344
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 345
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 346
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 347
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 348
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 349
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 350
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 351
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 352
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 353
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 354
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 355
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 356
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 357
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 358
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 359
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 360
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 361
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 362
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 363
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 364
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 365
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 366
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 367
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 368
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 369
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 370
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 371
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 372
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 373
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 374
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 375
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 376
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 377
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 378
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 379
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 380
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 381
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 382
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 383
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 384
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 385
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 386
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 387
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 388
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 389
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 390
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 391
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 392
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 393
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 394
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 395
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 396
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 397
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 398
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 399
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 400
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 401
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 402
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 403
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 404
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 405
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 406
Best string: Big-O Coding {le@rn a1g0ri7ths vv1th 3xp3rt5}
Fitness score: 45
--------------------------
https://ideone.com/hKsi93
language:
Python 3 (python  3.12)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!