#!/usr/bin/env python # coding: utf-8 # # การแก้ปัญหาแบบควายถึก (Brute Force) # จากวิดีโอคลิป [https://www.youtube.com/watch?v=0Ai9ygHu3L4] โจทย์คือ a, b, c, d เป็นจำนวนเต็มบวก ผลรวมของ a, b, c, d เท่ากับ 63 ให้หาค่าที่มากที่สุดของ ab + bc + cd ในวิดีโอแสดงวิธีทำด้วยรูปภาพ แต่สมมุติว่าเด็กๆไม่รู้ว่าจะทำอย่างไรแต่มีคอมพิวเตอร์อยู่ก็สามารถเขียนโปรแกรมให้คอมพิวเตอร์ไล่ตัวเลข a, b, c, d ดูได้ # # ผมบอกเด็กๆว่าเดี๋ยวนี้คอมพิวเตอร์เร็วมาก ถ้ามีของสักพันล้านชิ้นก็ยังให้มันไล่ดูให้เราได้โดยรอไม่นานนัก ในโจทย์นี้ค่าที่เป็นไปได้ของ a, b, c จะประมาณ 60 แบบของแต่ละตัว และค่าของ d จะเท่ากับ 63-(a+b+c) ดังนั้นค่าที่เป็นไปได้ทั้งหมดจะประมาณ 60x60x60 หรือประมาณ 200,000 เท่านั้น คอมพิวเตอร์ไล่ให้ได้ในเวลาไม่ถึงวินาที # In[1]: # โปรแกรมแรก ให้หาค่าที่มากที่สุดที่เป็นไปได้ของ ab+bc+cd # โดนที่ a, b, c, d เป็นจำนวนเต็มบวก # และ a+b+c+d = 63 # เราไล่ค่า a, b, c ให้เป็น 1 ถึง 62 และ d = 63-(a+b+c) # แล้วคำนวณ ab+bc+cd ว่าเป็นค่าที่มากกว่าที่เคยเห็นมาหรือเปล่า # ถ้าเป็นค่าที่มากกว่าที่เคยเห็นก็เก็บไว้เปรียบเทียบต่อไป max_value = -1 #max_value คือคือค่า ab+bc+cd ที่มากที่สุดที่เคยเห็น ตอนเริ่มเราใส่ค่าเป็นลบไว้ก่อน for a in range(1,63): for b in range(1,63): for c in range(1,63): #เราไล่ค่า a, b, c ให้เป็น 1 ถึง 62 และ d = 63-(a+b+c) d = 63 - (a+b+c) #ผลรวมของ a,b,c,d ต้องเท่ากับ 63 if d >= 1: #เช็คค่าว่า d ต้องเป็นจำนวนเต็มบวก if max_value < a*b + b*c + c*d: #ถ้่าค่า ab+bc+cd มากกว่าที่เคยเห็นมาเราก็เก็บค่าที่มากที่สุดตอนนี้ไว้ max_value = a*b + b*c + c*d print(max_value) #หลังจากวนค่าที่เป็นไปได้ทั้งหมดของ a,b,c,d แล้วค่า max_value จะเท่ากับ ab+bc+cd ที่มากที่สุด # In[2]: # ปรับปรุงจากแบบแรกโดยเก็บค่า a, b, c, d ที่ทำให้ ab+bc+cd มีค่ามากทีสุดด้วย # ถ้ามี a, b, c, d หลายชุดที่ทำให้ค่า ab+bc+cd มีค่ามากเท่ากันก็จะแสดงเฉพาะชุดแรก # หาค่าที่มากที่สุดที่เป็นไปได้ของ ab+bc+cd # โดนที่ a, b, c, d เป็นจำนวนเต็มบวก # และ a+b+c+d = 63 # เราไล่ค่า a, b, c ให้เป็น 1 ถึง 62 และ d = 63-(a+b+c) # แล้วคำนวณ ab+bc+cd ว่าเป็นค่าที่มากกว่าที่เคยเห็นมาหรือเปล่า # ถ้าเป็นค่าที่มากกว่าที่เคยเห็นก็เก็บไว้เปรียบเทียบต่อไป max_value = -1 #max_value คือคือค่า ab+bc+cd ที่มากที่สุดที่เคยเห็น ตอนเริ่มเราใส่ค่าเป็นลบไว้ก่อน for a in range(1,63): for b in range(1,63): for c in range(1,63): #เราไล่ค่า a, b, c ให้เป็น 1 ถึง 62 และ d = 63-(a+b+c) d = 63 - (a+b+c) #ผลรวมของ a,b,c,d ต้องเท่ากับ 63 if d >= 1: #เช็คค่าว่า d ต้องเป็นจำนวนเต็มบวก if max_value < a*b + b*c + c*d: #ถ้่าค่า ab+bc+cd มากกว่าที่เคยเห็นมาเราก็เก็บค่าที่มากที่สุดตอนนี้ไว้ max_value = a*b + b*c + c*d result = (a,b,c,d) #เก็บชุด a,b,c,d ไว้ในตัวแปรชื่อ result print(result, max_value) #หลังจากวนค่าที่เป็นไปได้ทั้งหมดของ a,b,c,d แล้วค่า max_value จะเท่ากับ ab+bc+cd ที่มากที่สุด # In[3]: # แบบที่สาม เก็บชุด (a,b,c,d) และค่า ab+bc+cd ทั้งหมดที่เป็นไปได้ # เก็บไว้ในดิกชันนารีชื่อ data ที่สมาชิกแต่ละตัวมี key = ab+bc+cd และ value คือลิสต์ของชุด (a,b,c,d) # เราเก็บ value เป็นลิสต์ของชุด (a,b,c,d) เพราะมีชุด (a,b,c,d) หลายแบบที่ให้ค่า ab+bc+cd เหมือนกัน # เช่น (1,30,31,1) และ (1,31,30,1) จะให้ค่า 991 เหมือนกัน data = {} for a in range(1,63): for b in range(1,63): for c in range(1,63): d = 63 - (a+b+c) if d >= 1: p = a*b + b*c + c*d #เรียกค่า ab+bc+cd ว่า p if p in data: data[p].append((a,b,c,d)) #ถ้าเคยมีค่า p ใน data แล้ว ให้ต่อ (a,b,c,d) เข้าไปในลิสต์ที่เป็น value ของ data[p] else: data[p] = [(a,b,c,d)] # ถ้าไม่เคยเห็นค่า p มาก่อน ให้สร้างลิสต์ขึ้นมาเก็บชุด (a,b,c,d) print(max(data), data[max(data)]) #max(data) คือ key ที่ใหญ่ที่สุด นั่นก็คือ ab+bc+cd ที่ใหญ่ที่สุดนั่นเอง # In[4]: # ข้อมูลที่เราเก็บไว้ในดิกชันนารีชื่อ data สามารถเอามาทำนู่นทำนี่ได้อีก # เช่นในที่นี้เราเอามาดูว่ามี (a,b,c,d) กี่แบบสำหรับแต่ละค่า ab+bc+cd ที่เป็นไปได้ # ใช้ barchart จาก matplotlib.pyplot มาวาดกราฟ get_ipython().run_line_magic('matplotlib', 'inline') import matplotlib.pyplot as plt x = sorted(data) #key ของ data ในรูปแบบเรียงจากมากไปน้อย y = [len(data[i]) for i in x] #นับว่าแต่ละ ab+bc+cd มี (a,b,c,d) กี่แบบ plt.bar(x,y) plt.xlabel('ค่า ab+bc+cd', fontname="Tahoma") plt.ylabel('จำนวนแบบทีเป็นไปได้', fontname="Tahoma") plt.title('ความถี่ของ ab+bc+cd', fontname="Tahoma") plt.show() # In[5]: # อันนี้ดูว่าค่า ab+bc+cd ที่น้อยที่สุดมี (a,b,c,d) กี่แบบ print(min(data), data[min(data)]) print(len(data[min(data)])) #จำนวนแบบ # In[6]: # อันนี้เป็นฟังชั่นหาว่า ถ้าใส่ค่า ab+bc+cd = p เข้าไป จะมี (a,b,c,d) กี่แบบ # p คือค่า ab+bc+cd ที่ต้องการ # dic คือดิกชันนารีที่เราให้มันเข้าไปหา ในที่นี้ควรใช้ดิกชันนารีชื่อ data ที่เราเก็บข้อมูลไว้ def how_many_patterns(p, dic): if p in data: return(len(dic[p])) else: return(0) # In[7]: # ดูว่าค่า ab+bc+cd เท่ากับ 991 มี (a,b,c,d) กี่แบบ how_many_patterns(991,data) # In[8]: # ดูว่าค่า ab+bc+cd ตั้งแต่ 60 ถึง 70 มี (a,b,c,d) กี่แบบ for i in range(60,71): print(i, how_many_patterns(i,data)) # In[9]: # ดูว่าค่า ab+bc+cd ตั้งแต่ 980 ถึง 999 มี (a,b,c,d) กี่แบบ for i in range(980,1000): print(i, how_many_patterns(i,data)) # # เฉลยการบ้าน: เข้ารหัสข้อความโดยเลื่อนตัวอักษร # # เราต้องการสร้างฟังก์ชั่นที่เปลี่ยนตัวอักษรเป็นตัวอื่น เพื่อให้ง่ายเราทำเฉพาะตัวอักษร a-z, A-Z เท่านั้น ตัวอื่นๆคงเดิมไว้ ฟังก์ชั่นควรรับค่าเข้าไปด้วยว่าให้เลื่อนตัวอักษรไปกี่ตัว เช่นถ้าให้เลื่อนไป 3 ตัว A ก็จะกลายเป็น D, B กลายเป็น E, C เป็น F, ฯลฯ # In[10]: # ทดสอบว่าเราพิมพ์ a-z ครบไหม len('abcdefghijklmnopqrstuvwxyz') # In[11]: # ทดสอบว่าเราพิมพ์ A-Z ครบไหม len('ABCDEFGHIJKLMNOPQRSTUVWXYZ') # In[12]: # ฟังชั่น ord จะให้ตัวเลขประจำตัวอักษรต่างๆ เช่นตัวเลขประจำของ 'A' คือ 65 ord('A') # In[13]: # ตัวเลขประจำของ 'Z' คือ 90 ord('Z') # In[14]: # ลองพิมพ์ตัวเลขของ A-Z for c in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ': print(ord(c), c) # In[15]: # ลองพิมพ์ตัวเลขของ a-z for c in 'abcdefghijklmnopqrstuvwxyz': print(ord(c), c) # In[16]: # มีช่วงตัวเลขระหว่าง "Z" แล "a" ที่ 91-96 ลองพิมพ์ออกมาดูว่าคืออะไร for n in range(91,97): print(chr(n)) # In[17]: # พิมพ์ตัวอักษรสำหรับตัวเลขตั้งแต่ 65 ถึง 122 for n in range(65,123): print(n, chr(n)) # In[18]: # สร้างฟังก์ชั่นเปลี่ยนตัวอักษร 1 ตัว # ใส่ตัวอักษร x และเลื่อนตำแหน่ง shift ตำแหน่ง # มีบั๊กตรงที่ไม่เปลี่ยนเฉพาะ a-z, A-Z เท่านั้น def shift_character(x, shift): n = ord(x) #หาตัวเลขประจำตัวอักษรที่ป้อนเข้ามา new_n = n + shift #หาตัวเลขที่เลื่อนไปเท่ากับ shift if new_n > 122: #ถ้าตัวอักษรไปไกลกว่า 'z' ให้ทบกลับไปแถวๆ 'A' ใหม่ new_n = 64 + (new_n - 122) if new_n < 65: #ถ้าตัวอักษรย้อนไปน้อยกว่า 'A' ให้ทยไปแถวๆ 'z' ใหม่ new_n = 123 - (65-new_n) return(chr(new_n)) # ฟังก์ชั่นที่จะเปลียนตัวอักษรของทั้งข้อความ m โดยเลื่อนไป shift ตำแหน่ง # ใช้ฟังก์ชั่น shift_character ข้างบนจัดการกับแต่ละอักษร def shift_message(m, shift): result = [] #เตรียมลิสต์ไว้เก็บตัวอักษรที่เลื่อนแล้ว for c in m: result.append(shift_character(c, shift)) #เอาอักษรที่เลื่อนแต่ละตัวเพิ่มเข้าไปในลิสต์ return( "".join(result) ) #ทำลิสต์ให้เป็นข้อความด้วย "".join(...) # In[19]: # ทดลองว่าทำงานได้ไหม เลื่อนไปข้างหน้าสามตำแหน่ง shift_message("Hello, World", 3) # In[20]: # ทดลองเลื่อนกลับสามตำแหน่ง ควรจะได้ข้อความเดิม แต่่ปรากฏว่าผิดเพราะคอมม่าและเว้นวรรค shift_message('Khoori]Zruog', -3) # In[21]: # แก้บั๊กโดยเปลี่ยนเฉพาะอักษร a-z และ A-Z เท่านั้น ถ้าอักษรเป็นตัวอื่นให้คงเดิมไว้ # เปลี่ยนฟังก์ชั่น shift_character def shift_character(x, shift): #ถ้าอักษร x ไม่อยู่ใน a-z, A-Z ให้คงเดิม if not (x in 'abcdefghijklmnopqrstuvwxyz' or x in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'): return(x) #ถ้าอยู่่ใน a-z, A-Z ก็เลื่อนตัวอักษร n = ord(x) new_n = n + shift if new_n > 122: new_n = 64 + (new_n - 122) if new_n < 65: new_n = 123 - (65-new_n) return(chr(new_n)) def shift_message(m, shift): result = [] for c in m: result.append(shift_character(c, shift)) return( "".join(result) ) # In[22]: # ทดลองใหม่ shift_message("Hello, World", 3) # In[23]: # ย้อนกลับแล้วได้ข้อความเดิม shift_message('Khoor, Zruog', -3) # In[24]: #ตัวอย่างสตริงข้อความยาวๆที่ก๊อปปี้มาจาก wikipedia #เก็บไว้ในตัวแปรชื่อ text text = """Godzilla (Japanese: ゴジラ Hepburn: Gojira) (/ɡɒdˈzɪlə/; [ɡoꜜdʑiɾa] (About this soundlisten)) is a fictional monster originating from a series of Japanese films of the same name. The character first appeared in Ishirō Honda's 1954 film Godzilla and became a worldwide pop culture icon, appearing in various media, including 32 films produced by Toho, three Hollywood films and numerous video games, novels, comic books and television shows. It is dubbed the King of the Monsters, a phrase first used in Godzilla, King of the Monsters!, the Americanized version of the original film. Godzilla is depicted as an enormous, destructive, prehistoric sea monster awakened and empowered by nuclear radiation. With the nuclear bombings of Hiroshima and Nagasaki and the Lucky Dragon 5 incident still fresh in the Japanese consciousness, Godzilla was conceived as a metaphor for nuclear weapons.[22] As the film series expanded, some stories took on less serious undertones, portraying Godzilla as an antihero, or a lesser threat who defends humanity. With the end of the Cold War, several post-1984 Godzilla films shifted the character's portrayal to themes including Japan's forgetfulness over its imperial past,[23] natural disasters and the human condition.[24] Godzilla has been featured alongside many supporting characters. It has faced human opponents such as the JSDF, or other monsters, including King Ghidorah, Gigan and Mechagodzilla. Godzilla sometimes has allies, such as Rodan, Mothra and Anguirus, and offspring, such as Minilla and Godzilla Junior. Godzilla has also fought characters from other franchises in crossover media, such as the RKO Pictures/Universal Studios movie monster King Kong and the Marvel Comics characters S.H.I.E.L.D.,[25] the Fantastic Four[26] and the Avengers.[27]""" # In[25]: # ลองเลื่อนไป 14 ตำแหน่งแล้วดูว่าข้อความเป็นอย่างไร shift_message(text, 14) # In[26]: #ทดสอบว่าเลือนไปแล้วเลื่อนกลับควรได้ข้อความเดิม text == shift_message(shift_message(text, 14), -14) # In[27]: # เราสามารถเขียนการเลื่อนตัวอักษรให้เข้าใจง่ายมากขึ้นโดยอ้างอิง ord() ของตัวอักษรโดยตรง # ในกรณีที่ shift มีค่ามากๆเราจะทำให้ค่า shift อยู่ในช่วง A-z ด้วย shift % (ord("z")-ord('A')+1) def shift_character(x, shift): shift = shift % (ord("z")-ord('A')+1) n = ord(x) if n < ord('A') or n > ord('z'): return(x) new_n = n + shift if new_n > ord('z'): new_n = new_n - ord('z') + ord('A') - 1 if new_n < ord('A'): new_n = ord('z') - (ord('A') - new_n) + 1 return(chr(new_n)) def shift_message(m, shift): result = [] for c in m: result.append(shift_character(c, shift)) return( "".join(result) ) # In[28]: shift_message("Hello, World", 3) # In[29]: # ทดสอบว่าเลือนไปแล้วเลื่อนกลับควรได้ข้อความเดิม text == shift_message(shift_message(text, 14), -14) # In[30]: # ทดสอบเลื่อนไปแล้วเลื่อนกลับด้วย shift = -150, -100, -50,..., 400, 450 # ควรได้ข้อความเดิม for shift in range(-150,500,50): print(f"shift = {shift}, Got original text back? ", text == shift_message(shift_message(text, shift), -shift)) # In[31]: # ทดสอบด้วยข้อความสุ่มๆและ shift สุ่มๆใน -200 ถึง 200 # ว่าเลื่อนไปแล้วเลื่อนกลับแล้วได้ข้อความเดิมไหม import random bug_found = False #พบความผิดพลาดการทำงานหรือยัง bug_info = [] #ถ้าพบข้อผิดพลาดให้เก็บรายละเอียดไว้ในลิสต์นี้ rounds = 1000 #จำนวนครั้งที่ทดสอบ for i in range(rounds): t = list(text) #เปลี่ยนสตริงให้เป็นลิสต์เพื่อจะได้สลับตัวอักษรไปมาได้ด้วย random.shuffle random.shuffle(t) t = ''.join(t) #แปลงลิสต์เป็นสตริงด้วย ''.join(...) shift = random.randint(-200, 200) #สุ่มขนาด shift ที่จะเลื่อนตัวอักษร if t != shift_message(shift_message(t, shift), -shift): #ถ้าเลื่อนไปแล้วเลื่อนกลับไม่ได้ข้อความเดิมแสดงว่ามีข้อผิดพลาด bug_found = True bug_info.append((shift, t)) #ถ้ามีข้อผิดพลาดให้เก็บข้อผิดพลาดไว้ตรวจสอบ if bug_found: print(bug.info) else: print(f'No bug found so far in {rounds} attempts.') #ถ้าไม่พบข้อผิดพลาดก็รายงานว่าไม่พบ # In[ ]: