Impossible Puzzle
เขียนสักเรื่องก่อนเข้านอน 
ก่อนอื่นขอนอกเรื่องหน่อย
ในที่สุดเมื่อวานก็ทำ Score ใน Web Project Euler
เกิน 200 คะแนนซะที  เย้ เย้
เริ่มเล่นประมาณสิงหา ปีที่แล้ว
แต่ละคะแนนยากเย็นแสนเข็ญ เล่นกันเป็นปี ๆ
ถ้าใครชอบคณิตศาสตร์ แล้วอยากเปิดความรู้ใหม่ ๆ
เล่นให้ได้เลยนะครับ Web นี้ เยี่ยม! 
บทความนี้เรามาแก้ปัญหา Impossible Puzzle ด้วย Linq กัน
Puzzle นี้ชื่อ Impossible เพราะดูเหมือนจะแก้ไม่ได้นะครับ
แต่จริง ๆ แก้ได้ (และยิ่งใช้ Linq ล่ะง่ายมาก)
โจทย์มีอยู่ว่า มีนักคณิตศาสตร์ 2 คนชื่อ Patty และ Selma
ทั้ง 2 คนเป็นยอดอัจฉริยะ
มีวันหนึ่งทั้ง 2 คนได้โจทย์ในการหาค่า X และ Y
โดยที่ X และ Y เป็นจำนวนเต็มมีค่ามากกว่า 1 แต่ไม่เกิน 100
และ X น้อยกว่า Y
ทั้ง 2 คนได้ Hint คนละอย่าง
โดย Patty ได้ Hint ว่า X*Y มีค่าเท่าไหร่
ส่วน Selma ได้ Hint ว่า X+Y มีค่าเท่าไหร่
ต่างฝ่ายต่างรู้ว่าอีกฝ่ายได้ Hint แบบไหนแต่ไม่รู้ค่าของ Hint นั้น
Patty เอ่ยกับ Selma ว่า: "ฉันไม่รู้หรอกว่าคำตอบคืออะไร"
Selma ตอบกลับไปว่า: "ฉันรู้อยู่แล้วล่ะว่าเธอต้องไม่รู้คำตอบ"
Patty ยิ้มอย่างมั่นใจ และบอกว่า: "งั้นเหรอ ถ้างั้นชั้นรู้คำตอบแล้วล่ะ"
Selma ก็ยิ้ม และตอบอย่างมั่นใจเช่นกัน:" ถ้าเธอรู้ ชั้นก็รู้คำตอบเช่นกัน"
แล้วค่า X และ Y คือ อะไรครับ ...?
ลองคิดดูก่อนนะครับ ข้างล่างคือเฉลย
เริ่มแรกหาจำนวนที่เป็นไปได้ก่อนครับ
X และ Y เป็นจำนวนเต็มมีค่ามากกว่า 1 แต่ไม่เกิน 100
และ X น้อยกว่า Y
var nums = (from y in 3.To(100)
from x in 2.To(y - 1)
select new { x, y }).ToList();
เท่านี้ nums ก็มีทุกค่าที่เป็นไปได้ก่อนรู้ Hint ครับ
คำสั่ง ToList ด้านหลังเป็นการสั่งให้ประมวลผลและเก็บค่าเข้า List ทันที
โดยปกติถ้าใช้ Linq เฉย ๆ จะได้ Return เป็น IEnumerable<>
IEnumerable จะเป็นการประมวลผลแบบ Lazy
ซึ่งมีข้อดีคือ ทำงานเร็วเพราะไม่ต้องเสียเวลาเก็บข้อมูลเข้า Memory
แต่ก็มีข้อเสียคือ ถ้ามีการเรียกใช้มากกว่า 1 ครั้ง IEnumerable จะทำการประมวลผลใหม่ทุกครั้ง
ในกรณีนี้ เราจะเรียกใช้ nums มากกว่า 1 ครั้งเลยเก็บเป็น List แทนนะครับ
ต่อมา Patty ไม่รู้ว่าคำตอบคืออะไร
หมายความว่าผลคูณของ X และ Y เป็นไปได้มากกว่า 2 คำตอบ
เช่น 12 ซึ่งคำตอบอาจจะเป็น 2*6 หรือ 3*4
ดังนั้นเราต้อง Group ด้วยผลคูณ และเลือกเฉพาะผลคูณที่มีมากกว่า 1 คำตอบ
var patty = (from xy in nums
group xy by xy.x * xy.y into g
where g.Count() > 1
select g).ToDictionary(g => g.Key);
คำสั่ง ToDictionary จะคล้าย ๆ กับ ToList ข้างต้น
ToList จะเก็บข้อมูลประเภทเดียว
แต่ ToDictionary จะเก็บ Key และ Value
Key คือ ผลคูณ ส่วน Value คือ ค่า X และ Y ต่าง ๆ ที่คูณกันแล้วได้ผลคูณนั้น
ต่อมา Selma รู้อยู่แล้วว่า Patty ไม่รู้คำตอบ
หมายความว่าผลบวกทุกแบบ เมื่อมาคูณกันผลคูณจะต้องอยู่ใน list ของ Patty ทุกอัน
เช่น 11 ผลบวกอาจจะเป็น 2+9, 3+8, 4+7, 5+6
ซึ่งผลคูณแต่ละแบบ 18(2*9), 24(3*8), 28(4*7), หรือ 30(5*6)
ล้วนอยู่ใน list ของ Patty
var selma = (from xy in nums
group xy by xy.x + xy.y into g
where g.All(xy => patty.ContainsKey(xy.x * xy.y))
select g).ToDictionary(g => g.Key);
ต่อมา Patty รู้คำตอบได้ทันที
ดังนั้น ใน list ของ patty ต้องมีผลบวกแบบเดียวเท่านั้น ในแต่ละผลคูณ ที่อยู่ใน list ของ Selma
เช่น ผลคูณคือ 18 ซึ่งมาจาก 2*9, 3*6
ซึ่งผลมีเพียงผลบวกแบบเดียว 11(2+9) ที่อยู่ใน list ของ Selma
ดังนั้น ถ้า Patty ได้เลข 18, Patty จะได้คำตอบทันทีว่า 2 กับ 9
var patty2 = (from g in patty
where g.Value.Count(xy => selma.ContainsKey(xy.x + xy.y)) == 1
select g).ToDictionary(g => g.Key, g => g.Value);
และสุดท้าย Selma รู้คำตอบได้ทันทีเช่นกัน
เป็น Logic เดียวกับ Patty ด้านบน แต่สลับระหว่างบวกกับคูณ
var selma2 = (from g in selma
where g.Value.Count(xy => patty2.ContainsKey(xy.x * xy.y)) == 1
select g).ToDictionary(g => g.Key, g => g.Value);
สุดท้ายเราต้องรวม list ของ Patty และ list ของ Selma เข้าด้วยกัน
var ans = from p in patty2.SelectMany(g => g.Value)
join s in selma2.SelectMany(g => g.Value) on p equals s
select p;
ans.ForEach(Console.WriteLine);
//{ x = 4, y = 13 }
คำสั่ง SelectMany เป็นการดึง Value ที่โดน Group ไว้ในตอนแรก
ทำการ ungroup ออกมา
และเอามา Join กันโดยดูว่า X และ Y คู่ไหนที่อยู่ทั้งใน List ของ Patty และ Selma
จบแล้วครับตอบ X = 4, Y = 13
| Create Date : 23 พฤศจิกายน 2551 |
| Last Update : 23 พฤศจิกายน 2551 1:26:48 น. |
|
0 comments
|
| Counter : 1354 Pageviews. |
 |
|
เย้ เย้
ฝากข้อความหลังไมค์
Rss Feed
ผู้ติดตามบล็อก : 8 คน [
