[C#] แก้ปัญหา 180 IQ ด้วย LINQ
สวัสดีครับ ไม่ได้เขียนใน Blog นี้นานมาก งานมันเยอะ (ข้ออ้าง  )
ก่อนอื่นขอประชาสัมพันธ์
ผมมีแผนจะทำ Training ให้บริษัท
โดยจะเอาเนื้อหามาทำเป็น Blog ด้วย
เนื้อหาจะเกี่ยวกับวิธีการทำให้เขียน Program ได้ดีขึ้น
แต่ไม่ได้เขียนที่ Blog นี้นะครับ
จะไปเขียนที่ CoreSharp.net web community ของเพื่อนผมเองครับ 
(ที่ไม่เขียนใน Blog นี้ เพราะ Target Audience เป็นผู้เขียน Program ทั่ว ๆ ไป
แต่ Blog นี้ เขียนตามความสะใจของเจ้าของ Blog  )
ยังไงก็ติดตามนะครับ อัพเรื่อย ๆ
เพื่อน ๆ รู้จักเกม 180 IQ ไหมครับ (ถ้ารู้จักแปลว่าแก่แล้ว  )
เป็นเกมที่จะให้เลขมาจำนวนนึง เช่น ให้เลข 1 2 5 8 มา
คุณจะ บวก ลบ คูณ หาร เลขสี่ตัวนี้ยังไง ให้ได้ผลลัพธ์ที่ต้องการ เช่น 27
คุณอาจจะเอา 8+5 ได้ 13 แล้วคูณด้วย 2 ได้ 26
แล้วบวก 1 ได้ 27
ง่ายไหมครับ? 
ลองแก้ปัญหาดูสักข้อก่อนอ่านต่อไป
1 2 5 8 = 44
...
ทีนี้ลองคิดดูว่าคุณจะ Solve ปัญหานี้โดยใช้ Computer ยังไง
จากตัวอย่างด้านบน ((8+5)*2) + 1 = 27
คุณจะเห็นว่าเลข 1 2 5 8 มันสลับกันไปหมดการสลับนี้ เราเรียกว่า Permutation ครับ
คุณสามารถสลับ 1 2 5 8 ได้ 4! = 24 วิธี
ต่อมาดูที่เครื่องหมาย + - * / คุณอาจจะใช้ + - * / มากกว่า 1 ครั้งก็ได้
การสลับแบบที่ใช้ตัวเลือกได้มากกว่า 1 ครั้ง เราเรียกว่า Permutation with Repetition ครับ
คุณสามารถสลับ + - * / ได้ อย่างละ 3 ครั้ง เป็น 4^3 = 64 วิธี
ต่อมาดูที่วงเล็บ คุณสามารถสลับวงเล็บได้ 5 วิธี คือ
(((a b) c) d)
((a (b c)) d)
((a b) (c d))
(a ((b c) d))
(a (b (c d)))
วิธีการสลับวงเล็บแบบนี้เราเรียกว่า Binary Bracketing
สรุปว่า วิธีการทั้งหมดที่จะทำให้เกิดคำตอบมีทั้งหมด 24 * 64 * 5 = 7,680 วิธี
เนื่องจาก Search Space มันแค่หลักพัน เราก็ให้ Computer มันหาทุกวิธีเลย
แล้วเอาคำตอบออกมา
แล้วการทำ Permutation กะ Binary Bracketing เนี่ยทำยังไงล่ะครับ
อย่าไปเครียด ผมทำไว้ให้คุณแล้ว อิอิ
เชิญไป Download ที่ CodePlex ครับ 
Library ชื่อ Combinatorics นะครับ
ผมทำไว้เป็น OpenSource ถ้าสนใจ Code ก็ลองเอาไปดูได้ว่า
Library สำหรับ Permutation กะ Binary Bracketing เนี่ย ทำยังไง
ก่อนอื่น ประกาศกลุ่มของตัวเลขก่อนครับ 1 2 5 8
var nums = new Expression[] {
Expression.Constant(1.0),
Expression.Constant(2.0),
Expression.Constant(5.0),
Expression.Constant(8.0) };
ต่อมาประกาศกลุ่มของ Operation คือ + - * /
var operations = new Func<Expression, Expression, Expression>[] {
Expression.Add,
Expression.Subtract,
Expression.Multiply,
Expression.Divide };
จะเห็นว่าผมประกาศเป็น Expression ทั้งหมด
เพราะผมต้องการแสดง Expression ของผลลัพธ์ด้วย
ถ้าคุณต้องการแค่ผลลัพธ์ ก็ใช้ double แทน Expression ไปเลย
ทำงานเร็วกว่ากันเยอะ
อ่านให้เข้าใจ รับรองประยุกต์ใช้ไม่ยาก
//Permute ตัวเลขทั้งหมด
var solutions = from numsPermute in nums.Permute()
//Permutation with Repetition operation ทั้งหมด 3 ที
from opsPermute in operations.Permute(3, CombinatoricModel.Repetition)
//เอาตัวเลข และ operation ต่าง ๆ ไปทำ Binary Bracketing
from results in numsPermute.BinaryBracketing(opsPermute)
//แปลง Expression เป็นผลลัพธ์
let computed = Expression.Lambda<Func<double>>(results).Compile()()
//เลือกเฉพาะค่า 1 - 100
where computed > 0.0 &&
computed <= 100.0 &&
Math.Floor(computed) == computed
//จัดกลุ่มตามผลลัพธ์
group results by computed into g
//จัดเรียงตามผลลัพธ์
orderby g.Key
//คืนค่า ผลลัพธ์ และ Expression ตัวแรก
select string.Format("{0} = {1}", g.Key, g.First());
//แสดงผล
solutions.ForEach(s => Console.WriteLine(s));
//1 = ((1 + (2 + 5)) / 8)
//2 = ((1 - (2 + 5)) + 8)
//3 = (1 + ((2 * 5) - 8))
//4 = (((1 + 5) * 2) - 8)
//5 = (((1 * 2) - 5) + 8)
//6 = (1 + ((2 - 5) + 8))
//7 = (((1 + 2) * 5) - 8)
//8 = (((1 - 5) + 8) * 2)
//9 = (((1 / 2) * 8) + 5)
//10 = (1 + (5 + (8 / 2)))
//11 = ((1 * (2 * 8)) - 5)
//12 = (((1 - 2) + 5) + 8)
//13 = (((1 + 8) * 2) - 5)
//14 = (((2 - 1) + 5) + 8)
//15 = (((1 * 2) + 5) + 8)
//16 = (1 + (2 + (5 + 8)))
//17 = (((2 * 5) - 1) + 8)
//18 = ((1 * (2 * 5)) + 8)
//19 = (1 + ((2 * 5) + 8))
//20 = (((1 / 2) * 5) * 8)
//21 = ((1 * (2 * 8)) + 5)
//22 = (1 + ((2 * 8) + 5))
//23 = (((1 + 2) * 5) + 8)
//24 = ((1 - 5) * (2 - 8))
//25 = (1 - ((2 - 5) * 8))
//26 = (1 * (2 * (5 + 8)))
//27 = (1 + (2 * (5 + 8)))
//28 = ((1 + (5 / 2)) * 8)
//29 = (((1 + 2) * 8) + 5)
//30 = (1 * (5 * (8 - 2)))
//31 = (1 - ((2 - 8) * 5))
//32 = (((1 - 2) + 5) * 8)
//33 = ((5 * (8 - 1)) - 2)
//34 = (2 - ((1 - 5) * 8))
//35 = (((1 - 2) + 8) * 5)
//36 = ((1 + 5) * (8 - 2))
//37 = (2 - ((1 - 8) * 5))
//38 = ((1 * (5 * 8)) - 2)
//39 = ((1 - 2) + (5 * 8))
//40 = ((2 - 1) * (5 * 8))
//41 = ((2 - 1) + (5 * 8))
//42 = ((1 * 2) + (5 * 8))
//43 = (1 + (2 + (5 * 8)))
//44 = (((1 / 2) + 5) * 8)
//45 = (((2 - 1) + 8) * 5)
//46 = (((1 + 5) * 8) - 2)
//47 = (((1 + 8) * 5) + 2)
//48 = (((2 - 1) + 5) * 8)
//49 = ((2 + 5) * (8 - 1))
//50 = (((1 * 2) + 8) * 5)
//51 = (1 + ((2 + 8) * 5))
//55 = ((1 + (2 + 8)) * 5)
//56 = (((1 * 2) + 5) * 8)
//57 = (1 + ((2 + 5) * 8))
//60 = ((1 + 5) * (2 + 8))
//63 = ((1 + 8) * (2 + 5))
//64 = ((1 + (2 + 5)) * 8)
//70 = (2 * (5 * (8 - 1)))
//72 = (((2 * 5) - 1) * 8)
//75 = (((2 * 8) - 1) * 5)
//78 = (2 * ((5 * 8) - 1))
//79 = ((2 * (5 * 8)) - 1)
//80 = (1 * (2 * (5 * 8)))
//81 = (1 + (2 * (5 * 8)))
//82 = ((1 + (5 * 8)) * 2)
//85 = ((1 + (2 * 8)) * 5)
//88 = ((1 + (2 * 5)) * 8)
//90 = ((1 + 8) * (2 * 5))
//96 = ((1 + 5) * (2 * 8))
แว๊ก! คำตอบออกมาเพียบเลย
จะเห็นว่าเขียนดี ๆ คุณสามารถแก้ปัญหา 180 IQ ได้ ด้วย Code LINQ ไม่เกิน 8 บรรทัด!!!
จบแล้วครับ ทีนี้จะหาเลขอะไรก็ง่าย ๆ แล้วใช่ไหมครับ
| Create Date : 26 เมษายน 2552 |
| Last Update : 26 เมษายน 2552 21:58:10 น. |
|
6 comments
|
| Counter : 8338 Pageviews. |
 |
|
|
| โดย: Grand IP: 118.174.132.241 วันที่: 15 สิงหาคม 2552 เวลา:17:34:26 น. |
|
|
|
| โดย: AlgoNerd IP: 202.151.7.30 วันที่: 8 กรกฎาคม 2553 เวลา:15:37:55 น. |
|
|
|
โดย: chaowman  วันที่: 12 กรกฎาคม 2553 เวลา:1:19:28 น. |
|
|
|
| โดย: zkaru IP: 180.210.216.131 วันที่: 26 สิงหาคม 2553 เวลา:12:50:35 น. |
|
|
|
| โดย: โหน่ง IP: 183.89.33.130 วันที่: 19 กุมภาพันธ์ 2554 เวลา:12:21:51 น. |
|
|
|
| โดย: ไม่รู้สินะ IP: 27.145.78.252 วันที่: 3 กุมภาพันธ์ 2558 เวลา:23:43:01 น. |
|
|
|
|
|
|
|
)
)
)
ฝากข้อความหลังไมค์
Rss Feed
ผู้ติดตามบล็อก : 8 คน [
ที่บอกให้
^_^