Software Design

💊 ยาต้านโควิด

โจทย์สอบสัมภาษณ์เข้า Saladpuk

🥳 โจทย์

ทรัพยากรทั้งโลกสามารถผลิตยาต้านโควิดได้แค่ 1,000 ขวดเท่านั้น แต่ก็ดันมีคนร้ายแอบผสมยาพิษลงไป 1 ขวด ซึ่งยาพิษตัวนี้ตรวจด้วยวิธีการใดๆก็ไม่พบ และคนที่กินก็จะตายในอีก 23 ชั่วโมงหลังจากที่กินเข้าไป ประจวบกับคนสำคัญทั่วโลกต้องได้รับยาตัวนี้ภายใน 24 ชั่วโมงไม่งั้นจะไม่สามารถรักษาชีวิตพวกเขาไว้ได้ ซึ่งทั่วทั้งโลกมีอาสาสมัครเพียงแค่ 10 คนเท่านั้น ที่พร้อมจะกินยาเหล่านั้นแม้รู้ว่าอาจจะตายก็ตาม

  • ในขวดมียาหลายเม็ด ส่วนคนกินแค่เม็ดเดียวก็พอ

  • ทุกเม็ดในขวดยาพิษกินแล้วตายใน 23 ชม เหมือนกัน

  • จะให้คนกินกี่เม็ดก็ได้ กี่ขวดก็ได้ กินขวดซ้ำกันก็ได้

  • จะใช้อาสาสมัครทุกคน หรือ แค่บางคนก็ได้ แต่ต้องไม่เกิน 10 คนที่กำหนดไว้

  • ถ้าจะช่วยผู้ป่วยได้ครบต้องมียาเหลือเกิน 900 กระปุก

เราจะทำยังไงเพื่อรักษาชีวิตคนให้ได้มากที่สุด โดยที่เสียยาไปน้อยที่สุด?

แนะนำให้อ่าน บทความนี้เป็นส่วนหนึ่งของ 🧠 Challenges ที่จะคอยรวบรวมโจทย์ที่น่าสนุกคิดเพลินๆ หากใครสนใจอยากดูว่ามีโจทย์อะไรบ้างก็อัญเชิญกดที่ชื่อสีฟ้าๆไปเสพต่อได้เบย ส่วนใครที่คิดว่ามีโจทย์น่าสนใจก็สามารถส่งมาได้ที่ Saladpuk Fanclub นะกั๊ฟ 😘

🙇‍♂️ กราบขออภัย

โจทย์ข้อนี้พอเอามาให้โปรแกรมเมอร์เล่นแล้วพบว่ามี bug เยอะมาก เพราะตัวโจทย์ไม่ได้เคลียเรื่องเวลา มันต้องเอาไปใช้จริงหรือเปล่า บลาๆ ดังนั้นกระผมขอทราบขออภัยที่ไม่ได้ระวังในเรื่องนี้ก่อนครับ 🙇‍♂️ ดังนั้นแมวน้ำจะขอเฉลยในรูปแบบต่างๆตามด้านล่างนี้ละกันนะ

🤠 วิธีคิด

จำนวนผู้อาสาสมัคร 10 คนนั้น ถ้าเราวางแผนดีๆก็จะสามารถระบุขวดยาพิษได้ 100% เลย โดยการ สลับกันกินคนละครึ่ง ตามตารางด้านล่างนี้

คนที่

ขวดยาที่เหลือ (เริ่มที่ 1,000)

1

500

2

250

3

125

4

62.5

5

31.25

6

15.625

7

7.8125

8

3.90625

9

1.953125

10

0.9765625

จากตารางด้านบนจะทำให้เรารู้ว่า ถ้าใช้คน 1 คน เราจะเสียขวดยาแค่ 500 ขวด แต่ถ้าใช้ 2 คนช่วยกันจะเสียขวดย่แค่ 250 ขวด ไปเรื่อยๆจนอาสาสมัคร 10 คนช่วยกันก็จะเสียขวดยาแค่เพียง 1 ขวดเท่านั้น (เศษปัดขึ้นทุกกรณี)

🤔 กินยาไง? (แบบมนุษย์เข้าใจ)

เพื่อให้เขาใจง่ายๆเลยขอแปลงยาทั้ง 1000 ขวดเป็นตามรูปด้านล่าง ซึ่งในกรอบสีขาวหมายถึงยังไม่มีคนกินยาเลย

ถัดมาให้อาสาคนแรกกินยาไปครึ่งหนึ่ง (1000 / 2 = 500 ขวด) ก็จะได้ตามรูปด้านล่าง

จากรูปด้านบนถ้าโชคดี/โชคร้าย เราก็จะมั่นใจได้ว่ามียาที่ปลอดภัยแน่ๆ 500 ขวด และมีอีก 500 ขวดที่ยังมั่นใจไม่ได้ ดังนั้นเราก็จะให้อาสาสมัครรายที่ 2 ไปช่วยกิน ซึ่งเราก็จะให้เขากิน 500 ขวดเหมือนกัน แต่จะให้เว้นช่วงเป็นครึ่งหนึ่งของคนแรก (500 /2 = 250) ดังนั้นอาสาคนนี้จะกินยา 250 ขวดแล้วเว้นไว้ 250 ขวด สลับไปเรื่อยๆ ตามรูปด้านล่าง

จากรูปด้านบนถ้าโชคดีไม่มีคนตายเลย เราก็จะมั่นใจได้ว่ายาที่อาสาทั้งสองกิน 750 ขวดนั้นปลอดภัย โดยเทียบกับตารางด้านล่างนี้

เหตุการณ์ที่เกิดขึ้น

ยาพิษอยู่ในกลุ่ม

รอดทั้งคู่

F

คนที่ 2 ตายคนเดียว

E

คนที่ 1 ตายคนเดียว

D

ตายทั้งคู่

C

ดังนั้นจากที่ว่ามาเราก็สามารถทำแบบนี้ให้กับอาสามัครไปเรื่อยๆ ให้ทุกคนกินเว้นระยะกันไปแบบนี้เรื่อยๆก็จะทำให้เราได้ผลลัพท์ออกมาราวๆนี้

ดังนั้นจากรูปด้านบนก็จะทำให้เรารู้ว่า กรณีที่ดีที่สุดคืออาสาหมายเลข 10 ตายคนเดียว และ กรณีที่เลวร้ายที่สุดก็อาจจะตายหมดก็ได้ 😥 แต่ไม่ว่ายังไงก็ตาม เราก็จะสามารถระบุขวดที่เป็นยาพิษได้ 100% นั่นเอง

สาเหตุที่ใช้คำว่าอาจจะตายหมด เพราะขึ้นอยู่กับว่าเราจะให้อาสาสมัครกินขวดที่คร่อมกันยังไงนั่นเอง เพราะจำนวนคน 10 คนนั้นสามารถทำความน่าจะเป็นออกมาได้ทั้งหมด 2 ยกกำลัง 10 = 1,024 แบบนั่นเอง

😎 กินยาไง? (ฉบับขาเดฟ)

เราก็ให้อาสาสมัครทั้ง 10 คนมายืนตามตำแหน่งด้านล่าง

ถัดมาเราก็ให้อาสาสมัครกินตามเงื่อนไขของตัวเองตามนี้

อธิบายด้านบนนิด เราจะติดเลขไว้บนขวดยาไว้ตั้งแต่ 1~1000 และใส่ขวดยาเปล่าที่ติดเลข 0 ไว้ แล้วส่งไปให้อาสาสมัครทีละขวดตามลำดับ

  1. พอขวดยาขวดแรกที่เป็นเลข 0 มา ก็จะไม่มีใครกินเพราะทุกคนต้องปล่อยให้ขวดยาไหนผ่านเท่ากับตัวเลขที่อยู่ตรงหน้า

  2. ขวดถัดมาที่เป็นเลข 1 ไหลมาปุ๊ป ผู้อาสาคนแรกก็จะเปิดกินเพราะเขาปล่อยขวดยาไหลผ่านครบเงื่อนไขหนึ่งขวดแล้ว ส่วนคนอื่นๆยังไม่ครบก็จะไม่มีใครกิน

  3. ขวดถัดมาที่เป็นเลข 2 ไหลมาปุ๊ป ผู้อาสาคนแรกก็จะไม่กินเพราะกินครบแล้วต้องรอให้มันไหลผ่านไป แต่อาสาหมายเลขสองจะต้องกินเพราะเขาปล่อยขวดยาไหลผ่านไป 2 ขวดครบตามเงื่อนไขแล้ว

ทั้งหมดก็ทำวนแบบนี้ไปเรื่อยๆ

พออธิบายมาถึงตรงนี้เหล่าขาเฟทั้งหลายก็น่าจะถึงบางอ้อนว่า การกินยาเขาไปนั้นก็มีโอกาสแค่ เป็น กับ ตาย เท่านั้น ซึ่งมันก็เหมือนกับ Binary ที่มีค่าเป็น 0 กับ 1 ดังนั้นสมมุติว่าอาสาสมัครหมายเลข 9 กับ 4 ตายเราก็จะรู้เลยว่าขวดยาพิษนั้นเป็นหมายเลข 264 นั่นเอง ตามรูปด้านล่าง

วิธีกินยาแบบนี้กับแบบแรกจริงๆคือแบบเดียวกัน แต่เอามาอธิบายให้ต่างกันนิดหน่อยโดยการกลับด้านเจ๋ยๆ ไม่เชื่อลองเอาคนที่ 10 ของวิธีนี้ไปเทียบกับคนที่ 1 ของวิธีแรกจิ ซึ่งจะเห็นว่ามันไม่ต่างอะไรกันเลยนั่นเอง 😁

🤪 Genius

อย่างที่บอกว่าโจทย์นี้มี bug เรื่องเวลา ซึ่งถ้ายาพิษมันออกฤทธิ์แบบเที่ยงตรงระดับ millisecond นั่นหมายความว่า เราสามารถให้ผู้สมัครคนเดียวกินยาทั้ง 1,000 ขวด โดยเว้นระยะห่างกัน 0.0001 ms แล้วก็รอดู 23 ชั่วโมงให้หลังว่าเขาจะตาย ms ที่เท่าไหร่นั่นเอง 👏

🎯 ข้อคิดที่ได้

ของทุกอย่างที่อยู่ในมือเราจะทำแค่ พอผ่าน หรือ ดีเยี่ยม ก็ได้ แต่ไม่ใช่ว่าทุกครั้งจะทำแบบพอผ่านหรือดีเยี่ยมเสมอ เราต้องดูสถานะการณ์ปัจจุบันด้วยว่า ความพอดีมันอยู่ที่ตรงไหน เพราะในบางครั้งที่เรา develope อะไรซักอย่าง เราก็รู้ว่ามันยังทำให้ดียิ่งขึ้นได้อีก แต่จะต้องแลกกับเวลาที่มากขึ้นซึ่งทำให้ส่งงานไม่ได้ ดังนั้นเราก็ควรจะชั่งน้ำหนักว่าจุดไหนคือ ทางสายกลาง ของเรานั่นเองครับ

โจทย์ข้อนี้ถ้าทำพอผ่านก็ให้อาสาสมัคร 10 คนกินยาคนละ 100 ขวด ก็จะผ่านเงื่อนไขขั่นต่ำแล้วนั่นเอง แต่ถ้าจะรีดเน็นจริงๆแล้วคงต้องใช้เวลาคิดมากกว่านี้ ซึ่งถ้าต้องแลกกับเวลาเลี้ยงลูกเลี้ยงเมียมากเกินไป ก็เอาเวลาไปทำในส่วนอื่นจะเหมาะกว่านะ (เมียแอบกระซิบมา) 🤣