Solve ปัญหาการเลื่อนรถใน Brand Genius Exit
สวัสดีหลังปีใหม่ไทยครับ จริง ๆ มีเรื่องอยากจะ Post ใน Bloggang นี้มากมาย แต่เล่น Post ทีประมาณ 3-4 เดือนครั้ง วันนี้เลยถึงรอบต้อง Post แล้วล่ะครับ อิอิ
Post ที่แล้ว มีน้อง Post ข้อความให้เล่นเกมส์ ฺBrand Genius Exit เนื่องจากความโลภ บวกความขี้โกง คิดว่าเขียนโปรแกรมแล้วจะชนะได้ ผิดคาดครับ คนเก่ง ๆ ในไทยยังมีอีกมากมาย แต่ไม่แสดงตัวเท่านั้นเองครับ งานนี้เลยได้แค่ Thumbdrive เป็นของขวัญปลอบใจ ใครเล่นแล้วมาคุยกันได้ครับ ว่ามีวิธีการ Solve กันยังไง
เกมส์เค้าจบไปสักพักแล้ว ผมก็เลยเอา Code มาแชร์กัน ก็แล้วกันครับ เริ่มด้วยสร้าง Class สำหรับเก็บการเลื่อนรถในแต่ละครั้ง
class BoardState { public char Target { get; set; } public string Board { get; set; } public int TabletCount { get; set; } }
Target คือ เลื่อนรถคันไหน ฺBoard คือ รูปแบบของรถหลังจากเลื่อนไปแล้ว TabletCount คือ เหลือ Tablet ให้ใช้อีกกี่เม็ด
ก่อนอื่นต้องทำความเข้าใจก่อนว่ารถแต่ละคันผมจะแทนด้วยตัวอักษร A-J แทนรถขนาดเล็กที่วางขวางตามแนวนอน โดยที่ A คือ รถของเรา K-T แทนรถขนาดใหญ่ที่วางขวางตามแนวนอน a-j แทนรถขนาดเล็กที่วางขวางตามแนวตั้ง k-t แทนรถขนาดใหญ่ที่วางขวางตามแนวตั้ง 0 แทนกรวย ช่องว่างแทนช่องว่างที่ไม่มีรถ
ต่อมา สร้าง Function สำหรับการเลื่อนรถ
static BoardState[] carMove(string startBoard, int tabletCount) { //startBoard คือ รูปแบบของรถเริ่มต้น //tabletCount คือ จะอนุญาตให้ใช้ Tablet กี่เม็ดสำหรับ Level นี้ //ค่าที่คืนสำหรับ Function นี้คือ วิธีการเลื่อนรถที่ดีที่สุด (ถ้าเป็น null คือ ไม่มีคำตอบ) //ตารางเป็น 6 x 6 เสมอทุกด่าน int col = 6; int row = 6;
//move คือ วิธีการเลื่อน ขวา ลง ซ้าย ขึ้น ตามลำดับ int[][] moves = new[] { new[] { +1, 0 }, new[] { 0, +1 }, new[] { -1, 0 }, new[] { 0, -1 }, };
//เก็บรถที่ต้องการเลื่อน ไม่นับช่องว่าง ไม่นับกรวย (0 คือ กรวย) string targets = startBoard.Where(c => c != ' ' && c != '0') .Distinct() .ToString(""); //Function สำหรับจบเกมส์ //รถ A ซึ่งเป็นรถของเราจะต้องย้ายไปอยู่ที่ช่องขวาสุด Func<string, bool> predicate = board => board[4 + 2 * col] == 'A' && board[5 + 2 * col] == 'A'; //สร้างรูปแบบของรถอันแรก BoardState boardState = new BoardState() { Target = ' ', Board = startBoard, TabletCount = tabletCount };
//สร้าง Set สำหรับเก็บรูปแบบการเลื่อนรถ ป้องกันการเลื่อนไป-กลับ HashSet<string> foundPattern = new HashSet<string>(); foundPattern.Add(boardState.Board);
//Function สำหรับทดสอบว่าเลื่อนรถได้หรือไม่ Func<string, char, int[], bool> canMove = (board, target, move) => board.All((c, i) => {
//ถ้าไม่ใช่รถที่ต้องการ ก็ไม่ต้องสนใจ if (c != target) return true; //ถ้าเลื่อนแล้วจะหลุดนอกกรอบ ก็ไม่ผ่าน int[] pos = new[] { (i % col) + move[0], (i / col) + move[1] }; if (pos[0] < 0 || pos[0] == col || pos[1] < 0 || pos[1] == row) return false;
//Set ค่าตำแหน่งใหม่หลังจากเลื่อนไปแล้ว int newIndex = pos[0] + pos[1] * col;
//ถ้าตำแหน่งใหม่คือช่องว่าง หรือเป็นรถคันเดียวกันก็ผ่านได้ return board[newIndex] == ' ' || board[newIndex] == target; });
//Function สำหรับเลื่อนรถ string emptyBoard = new string(' ', startBoard.Length); Func<BoardState, char, int[], IEnumerable<BoardState>> moveNext = (b, target, move) => { //ทดสอบว่า ต้องใช้ Tablet หรือไม่ //แต่ถ้าไม่มี Tablet แล้ว หรือรถที่ต้องใช้ Tablet เป็นรถเราเอง ก็คืนค่าว่าง int iTablet = b.TabletCount; if ((target <= 'Z') ? move[1] != 0 : move[0] != 0) { if (iTablet == 0 || target == 'A') return Enumerable.Empty<BoardState>(); iTablet -= 1; }
//ลองเลื่อนไปเรื่อย ๆ เพราะเลื่อน 1 ครั้งสามารถเลื่อนรถได้จนสุด //จึงคืนค่าการเลื่อนทีละครั้ง ทุกรูปแบบ List<BoardState> list = new List<BoardState>(); while (canMove(b.Board, target, move)) { var board = emptyBoard.ToCharArray(); int addIndex = move[0] + move[1] * col; b.Board.ForEach((c, i) => { if (c == target) board[i + addIndex] = target; else if (c != ' ') board[i] = c; }); b = new BoardState { Target = target, Board = new string(board), TabletCount = iTablet }; list.Add(b); } return list; };
//สร้างวิธีการเลื่อนรถ var boards = new[] { new[] { boardState } }; BoardState[] sol = null; while (boards.Length > 0) {
//ถ้าเจอคำตอบก็ออก sol = boards.FirstOrDefault(board => predicate(board.Last().Board)); if (sol != null) break;
//สร้างวิธีการเลื่อนรถรูปแบบถัดไป boards = (from board in boards //รูปแบบปัจจุบันทั้งหมด from target in targets //รถที่เลื่อนได้ทั้งหมด from move in moves //วิธีการเลื่อนทั้งหมด
//ลองเลื่อนและสร้างรูปแบบใหม่ from nextMove in moveNext(board.Last(), target, move)
//ถ้าเป็นรูปแบบที่ไม่เคยพบก็ผ่านได้ where foundPattern.Add(nextMove.Board)
//เอารูปแบบปัจจุบัน + กับรูปแบบใหม่ select board.Append(nextMove)).ToArray(); }
//ได้คำตอบ! return sol; }
และสุดท้าย Function สำหรับการแสดงผล
static string buildSolution(BoardState[] sol) { int col = 6; int row = 6;
StringBuilder sb = new StringBuilder(); int oldTablet = sol[0].TabletCount;
foreach (var item in sol) { if (oldTablet != item.TabletCount) { oldTablet = item.TabletCount; sb.AppendLine("Use Tablet!"); } sb.Append("Move ").AppendLine(item.Target.ToString()); sb.AppendLine("------"); for (int y = 0, z = 0; y < row; y++) { for (int x = 0; x < col; x++, z++) sb.Append(item.Board[z]); sb.AppendLine(); } sb.AppendLine(); } return sb.ToString(); }
เริ่มกันเลยครับ หน้าตาของตัว Input ก็ประมาณนี้
kBBCC kKKKa kbAAa DDbEEc dFF c d GGHH
k เล็กคือ รถขนาดใหญ่ที่จอดแนวตั้ง ส่วน K ใหญ่คือ รถขนาดใหญ่ที่จดตามแนวนอน ลองจินตนาการดูนะครับ
แล้วก็โยนเข้า Function โดยทั่วไปผมจะต้องการคำตอบ 2 แบบ แบบไม่ใช้ Tablet และแบบใช้ Tablet แค่ 1 อัน
//เอาบรรทัดใหม่ออก string startBoard = Board.Text.Replace("rn", "");
//แบบไม่ใช้ Tablet BoardState[] sol = carMove(startBoard, 0); if (sol == null) { level.NoUseScore = int.MaxValue; level.NoUseSolution = string.Empty; } else { level.NoUseScore = sol.Length; level.NoUseSolution = buildSolution(sol); }
//แบบใช้ Tablet sol = carMove(startBoard, 1); if (sol == null) { level.UseScore = int.MaxValue; level.UseSolution = string.Empty; } else { level.UseScore = sol.Length; level.UseSolution = buildSolution(sol); }
Board.Text คือ ตัว TextBox สำหรับ Input level คือ Class สำหรับ Output ซึ่งคุณสามารถสร้างและใช้ชื่อของคุณเอง และนี่คือ Output ครับ
Level 198
kBBCC kKKKa kbAAa DDbEEc dFF c d GGHH | | Not Use Tablet 20 Moves | Use Tablet 4 Moves | Move ------ kBBCC kKKKa kbAAa DDbEEc dFF c d GGHH
Move F ------ kBBCC kKKKa kbAAa DDbEEc d FFc d GGHH
Move G ------ kBBCC kKKKa kbAAa DDbEEc d FFc dGG HH
Move H ------ kBBCC kKKKa kbAAa DDbEEc d FFc dGGHH
Move c ------ kBBCC kKKKa kbAAa DDbEE d FFc dGGHHc
Move a ------ kBBCC kKKK kbAAa DDbEEa d FFc dGGHHc
Move K ------ kBBCC k KKK kbAAa DDbEEa d FFc dGGHHc
Move b ------ kBBCC kbKKK kbAAa DD EEa d FFc dGGHHc
Move D ------ kBBCC kbKKK kbAAa DDEEa d FFc dGGHHc
Move d ------ kBBCC dkbKKK dkbAAa DDEEa FFc GGHHc
Move D ------ kBBCC dkbKKK dkbAAa DD EEa FFc GGHHc
Move G ------ kBBCC dkbKKK dkbAAa DD EEa FFc GG HHc
Move b ------ kBBCC dk KKK dk AAa DD EEa bFFc GGbHHc
Move K ------ kBBCC dkKKK dk AAa DD EEa bFFc GGbHHc
Move a ------ kBBCC dkKKKa dk AAa DD EE bFFc GGbHHc
Move E ------ kBBCC dkKKKa dk AAa DD EE bFFc GGbHHc
Move D ------ kBBCC dkKKKa dk AAa DDEE bFFc GGbHHc
Move k ------ BBCC dkKKKa dk AAa kDDEE bFFc GGbHHc
Move B ------ BB CC dkKKKa dk AAa kDDEE bFFc GGbHHc
Move C ------ BBCC dkKKKa dk AAa kDDEE bFFc GGbHHc
Move a ------ BBCCa dkKKKa dk AA kDDEE bFFc GGbHHc
Move A ------ BBCCa dkKKKa dk AA kDDEE bFFc GGbHHc | Move ------ kBBCC kKKKa kbAAa DDbEEc dFF c d GGHH
Use Tablet! Move k ------ k BBCC k KKKa k bAAa DDbEEc dFF c d GGHH
Move B ------ kBB CC k KKKa k bAAa DDbEEc dFF c d GGHH
Move C ------ kBBCC k KKKa k bAAa DDbEEc dFF c d GGHH
Move a ------ kBBCCa k KKKa k bAA DDbEEc dFF c d GGHH
Move A ------ kBBCCa k KKKa k b AA DDbEEc dFF c d GGHH |
Create Date : 25 เมษายน 2553 | | |
Last Update : 25 เมษายน 2553 20:06:29 น. |
Counter : 1565 Pageviews. |
| |
|
|
|
|
เขียนโปรแกรม Solve RedStone บน Android
สวัสดีครับ ไม่ได้ update ซะนาน
พอดีมีรุ่นพี่คนนึง เค้าเอาเกมส์บน Android มาให้เล่น เกมส์มีชื่อว่า RedStone
จุดมุ่งหมายของเกมส์คือเลื่อนให้หินก้อนใหญ่ออกประตูให้ได้ พอเล่นดูสักพักก็รู้ว่า ยากโครต ผมคงไม่มีความสามารถในการจบเกมส์นี้ได้แน่ เนื่องจากไอ้หินก้อนใหญ่เนี่ย ใหญ่เทอะทะมาก จะลากไปทางไหนก็ติดไปหมด เลยต้องเขียนโปรแกรมช่วยสักหน่อย
ตอนแรกก็สร้างรูปแบบการเดินก่อน มี ขวา ลง ซ้าย ขึ้น
int[][] moves = new[] { new[] { +1, 0 }, new[] { 0, +1 }, new[] { -1, 0 }, new[] { 0, -1 }, };
ต่อมาก็สร้างหิน ใช้ ABC แทนหินแต่ละก้อน
string startBoard = " AB " + "ECDF" + "EIIF" + "GJJH" + "GJJH";
เพื่อป้องกันไม่ให้ลากก้อนหินวนไปวนมาแล้วเป็นรูปแบบเดิม ก็เลยจำเป็นต้องมี Set สำหรับเก็บรูปแบบที่เคยทำมาแล้วไว้
HashSet<string> foundPattern = new HashSet<string>(); Func<string, string> normalize = s => new string( s.Select(c => { if (c <= ' ') return ' '; else if (c <= 'D') return 'o'; else if (c <= 'H') return 'v'; else if (c <= 'I') return 'h'; else return 'x'; }).ToArray() ); foundPattern.Add(normalize(startBoard));
Function ชื่อ normalize เป็นการเปลี่ยนชื่อของหิน (A, B, C) เป็นรูปแบบของหิน (ก้อนเล็ก, ก้อนยาว, ก้อนใหญ่) เพราะหินอาจจะสลับตำแหน่งกัน แต่เป็นรูปแบบเดิมก็ได้ เวลาจำก็เลยจำแต่รูปแบบของหินก็พอ
ต่อมาก็สร้างอีก 2 Functions เพื่อทดสอบและทำการเลื่อนหิน
Func<string, char, int[], bool> canMove = (s, target, move) => s.All((c, i) => { if (c != target) return true; int[] pos = new[] { (i % 4) + move[0], (i / 4) + move[1] }; if (pos[0] < 0 || pos[0] == 4 || pos[1] < 0 || pos[1] == 5) return false; int newIndex = pos[0] + pos[1] * 4; return s[newIndex] == ' ' || s[newIndex] == target; }); string emptyBoard = new string(' ', 20); Func<string, char, int[], string> moveNext = (s, target, move) => { var board = emptyBoard.ToCharArray(); int addIndex = move[0] + move[1] * 4; s.ForEach((c, i) => { if (c == target) board[i + addIndex] = target; else if (c != ' ') board[i] = c; }); return new string(board); };
เริ่มทำการค้นหาคำตอบเลยครับ
var boards = new[] { new[] { startBoard } }; string[] sol = null; while (true) { sol = boards.FirstOrDefault(board => board.Last()[1] == 'J' && board.Last()[2] == 'J'); if (sol != null) break; boards = (from board in boards from target in "ABCDEFGHIJ" from move in moves where canMove(board.Last(), target, move) select board.Append(moveNext(board.Last(), target, move)) into nextBoard where foundPattern.Add(normalize(nextBoard.Last())) select nextBoard).ToArray(); }
Algorithm ที่ใช้คือ Breath-First-Search เพราะต้องการหา Solution ที่สั้นที่สุด แต่ละชั้นที่ต้องการหาคำตอบ จะเก็บในตัวแปรชื่อ boards และจะวนลูปเรื่อย ๆ จนกว่าจะเจอคำตอบ
เสร็จแล้วก็พิมพ์ข้อความออกมา
foreach (var item in sol) { for (int y = 0, z = 0; y < 5; y++) { for (int x = 0; x < 4; x++, z++) Console.Write(item[z]); Console.WriteLine(); } Console.WriteLine(); } // AB //ECDF //EIIF //GJJH //GJJH
//EAB //ECDF // IIF //GJJH //GJJH
//EABF //ECDF // II //GJJH //GJJH
//EABF //ECDF // II //GJJH //GJJH
//EABF //E DF // CII //GJJH //GJJH
//EABF //E DF //C II //GJJH //GJJH
//EABF //E DF //CII //GJJH //GJJH
//EAB //E DF //CIIF //GJJH //GJJH
//EA B //E DF //CIIF //GJJH //GJJH
//E AB //E DF //CIIF //GJJH //GJJH
// EAB // EDF //CIIF //GJJH //GJJH
// EAB //CEDF // IIF //GJJH //GJJH
//CEAB // EDF // IIF //GJJH //GJJH
//CEAB // EDF //II F //GJJH //GJJH
//CEAB // E F //IIDF //GJJH //GJJH
//CE B // EAF //IIDF //GJJH //GJJH
//CEB // EAF //IIDF //GJJH //GJJH
//CEBF // EAF //IID //GJJH //GJJH
//CEBF // EAF //II D //GJJH //GJJH
//CEBF // EAF // IID //GJJH //GJJH
//CEBF // EAF //GIID //GJJH // JJH
//CEBF //GEAF //GIID // JJH // JJH
//CEBF //GEAF //GIID //JJ H //JJ H
//CEBF //GEAF //GIID //JJH //JJH
//CEBF //GEAF //GII //JJHD //JJH
//CEBF //GEAF //GII //JJH //JJHD
//CEB //GEAF //GIIF //JJH //JJHD
//CE B //GEAF //GIIF //JJH //JJHD
//CE B //GEA //GIIF //JJHF //JJHD
//CE B //GE A //GIIF //JJHF //JJHD
//C EB //G EA //GIIF //JJHF //JJHD
// CEB //G EA //GIIF //JJHF //JJHD
// EB //GCEA //GIIF //JJHF //JJHD
//G EB //GCEA // IIF //JJHF //JJHD
//G EB //GCEA //II F //JJHF //JJHD
//G B //GCEA //IIEF //JJHF //JJHD
//G B //GCEA //IIEF //JJHF //JJHD
//GB //GCEA //IIEF //JJHF //JJHD
//GBE //GCEA //II F //JJHF //JJHD
//GBE //GCEA //IIHF //JJHF //JJ D
//GBE //GCEA //IIHF //JJHF //JJD
//GBE //GCEA //IIH //JJHF //JJDF
//GBE //GCE //IIHA //JJHF //JJDF
//GB E //GC E //IIHA //JJHF //JJDF
//GB E //GCHE //IIHA //JJ F //JJDF
//GBHE //GCHE //II A //JJ F //JJDF
//GBHE //GCHE //IIA //JJ F //JJDF
//GBHE //GCHE //II //JJAF //JJDF
//GBHE //GCHE // II //JJAF //JJDF
// BHE //GCHE //GII //JJAF //JJDF
//B HE //GCHE //GII //JJAF //JJDF
//BCHE //G HE //GII //JJAF //JJDF
//BCHE //G HE //G II //JJAF //JJDF
//BCHE // GHE // GII //JJAF //JJDF
// CHE //BGHE // GII //JJAF //JJDF
//C HE //BGHE // GII //JJAF //JJDF
//CGHE //BGHE // II //JJAF //JJDF
//CGHE //BGHE // II //JJAF //JJDF
//CGHE //BGHE // IIF //JJAF //JJD
//CGHE //BGHE // IIF //JJAF //JJ D
//CGHE //BGHE // IIF //JJ F //JJAD
//CGHE //BGHE //II F //JJ F //JJAD
//CG E //BGHE //IIHF //JJ F //JJAD
//CG E //BG E //IIHF //JJHF //JJAD
//C GE //B GE //IIHF //JJHF //JJAD
//C GE // BGE //IIHF //JJHF //JJAD
//CBGE // GE //IIHF //JJHF //JJAD
//CBGE //IIGE // HF //JJHF //JJAD
//CBGE //IIGE //JJHF //JJHF // AD
//CBGE //IIGE //JJHF //JJHF // A D
//CBGE //IIGE //JJHF //JJHF //A D
//CBGE //IIGE //JJHF //JJHF //A D
//CBGE //IIGE //JJHF //JJHF //AD
//CBGE //IIGE //JJH //JJHF //AD F
//CBG //IIGE //JJHE //JJHF //AD F
//CBG //IIGE //JJ E //JJHF //ADHF
//CB //IIGE //JJGE //JJHF //ADHF
//C B //IIGE //JJGE //JJHF //ADHF
//C B //IIGE //JJGE //JJHF //ADHF
// C B //IIGE //JJGE //JJHF //ADHF
// CB //IIGE //JJGE //JJHF //ADHF
//IICB // GE //JJGE //JJHF //ADHF
//IICB //JJGE //JJGE // HF //ADHF
//IICB //JJGE //JJGE //A HF // DHF
//IICB //JJGE //JJGE //A HF //D HF
//IICB //JJGE //JJGE //AH F //DH F
//IICB //JJ E //JJGE //AHGF //DH F
//IICB //JJ E //JJ E //AHGF //DHGF
//IICB // JJE // JJE //AHGF //DHGF
//IICB // JJE //AJJE // HGF //DHGF
//IICB //AJJE // JJE // HGF //DHGF
//IICB //AJJE // JJE //DHGF // HGF
//IICB //AJJE //DJJE // HGF // HGF
//IICB //AJJE //DJJE //H GF //H GF
//IICB //AJJE //DJJE //HG F //HG F
//IICB //AJJE //DJJE //HGF //HGF
//IICB //AJJ //DJJE //HGFE //HGF
//IICB //AJJ //DJJ //HGFE //HGFE
//IICB //A JJ //D JJ //HGFE //HGFE
//IICB // AJJ //D JJ //HGFE //HGFE
//IICB // JJ //DAJJ //HGFE //HGFE
// CB //IIJJ //DAJJ //HGFE //HGFE
// C B //IIJJ //DAJJ //HGFE //HGFE
// CB //IIJJ //DAJJ //HGFE //HGFE
//C B //IIJJ //DAJJ //HGFE //HGFE
//CB //IIJJ //DAJJ //HGFE //HGFE
//CBJJ //IIJJ //DA //HGFE //HGFE
//CBJJ //IIJJ //D A //HGFE //HGFE
//CBJJ //IIJJ //D A //HGFE //HGFE
//CBJJ //IIJJ // D A //HGFE //HGFE
//CBJJ //IIJJ // DA //HGFE //HGFE
//CBJJ // JJ //IIDA //HGFE //HGFE
//C JJ // BJJ //IIDA //HGFE //HGFE
//C JJ //B JJ //IIDA //HGFE //HGFE
//CJJ //BJJ //IIDA //HGFE //HGFE
ดูคำตอบเพลินดีไหมครับ เดินทั้งหมด 114 ตา ใครจะไล่คำตอบตามต้องจินตนาการหน่อยนะครับ เช่น J 4 ตัวคือก้อนหินใหญ่หนึ่งก้อน มันจะย้ายตามกันเสมอครับ
ถ้าใครจะลองเขียนตาม แล้ว Run ไม่ได้ อาจจะต้องไปหา Extension ในโพสเก่า ๆ ของผมนะครับ
จบแล้วครับ ไว้เจอกันใหม่ครับ
Create Date : 31 มกราคม 2553 | | |
Last Update : 31 มกราคม 2553 10:28:06 น. |
Counter : 997 Pageviews. |
| |
|
|
|
|
แก้โจทย์ Knight's Tour ด้วย C#
ช่วงนี้ไม่ค่อยมีเวลามาเขียนโปรแกรมแก้โจทย์ Algorithm เล่นนานละ แต่ไปเจอโจทย์นึงที่ Web TwoGuru ชื่อว่า Knight's Tour น่าสนใจเลยลองเขียนดูบ้าง
Knight's Tour คือ การเดินม้าในตารางหมากรุก 8x8 โดยเริ่มที่ช่องใดก็ได้ เดินไปเรื่อย ๆ ห้ามทับจุดเดิม และเดินให้ครบทุกช่อง เห็นโจทย์ก็รู้เลยน่าสนใจ ซึ่งดูผิวเผินน่าจะยาก จากการคำนวนของ Web TwoGuru เห็นว่ามีรูปแบบเป็น สี่แสนล้านล้านล้านล้านล้านล้านรูปแบบ !!! แต่คิดว่าหลักการของ Functional Programming น่าจะแก้ปัญหานี้ได้ไม่ยาก
ไม่พูดพร่ำทำเพลง เขียนรูปแบบการเดินของม้าก่อนเลย
int[][] moves = new[] { new[] {+1, -2}, new[] {+2, -1}, new[] {+2, +1}, new[] {+1, +2}, new[] {-1, +2}, new[] {-2, +1}, new[] {-2, -1}, new[] {-1, -2}, };
ต่อด้วยหากระดาน กระดาน 8x8 ซึ่งใช้ 64 ช่อง ตอนแรกคิดว่าจะใช้ BitArray ขนาด 64 ช่อง แต่คิดไปคิดมา ulong ก็เป็น Type ที่มี 64bit นี่หว่า เลยตัดสินใจใช้ ulong ก็เลยต้องเขียนสูตรการแปลงจากตำแหน่งบนกระดานเป็น ulong และก็แปลงกลับ
Func<int[], ulong> positionToULong = pos => 1UL << (pos[1] * 8 + pos[0]); Func<ulong, int[]> ulongToPosition = u => { int log2 = 0, x, y; while (u != 1) { log2++; u >>= 1; } y = Math.DivRem(log2, 8, out x); return new[] { x, y }; };
ต่อมาก็เขียนสูตรการเดินของม้าซะ ในแต่ละช่องม้าสามารถเดินไปจุดไหนบ้างใช้สูตรนี้
Func<ulong, ulong[]> nextPoint = u => { var pos = ulongToPosition(u); return (from move in moves select new[] { pos[0] + move[0], pos[1] + move[1] } into nextPos where nextPos[0] >= 0 && nextPos[0] < 8 && nextPos[1] >= 0 && nextPos[1] < 8 select positionToULong(nextPos)).ToArray(); }; nextPoint = nextPoint.Memoize();
ในสูตรถ้าม้าตัวไหนเดินออกนอกตารางก็ตัดทิ้งไป แล้วก็จะเห็นคำสั่ง Memoize ในบรรทัดสุดท้าย เป็นการทำให้ Function จำคำตอบได้ไม่ต้องคำนวณใหม่ อ่าน Article เก่า เพิ่มเติมครับ
และก็มาถึง Function สุดท้าย เป็น Algorithm การเดินม้าให้ครบ 64 ตาแล้วครับ
Func<ulong, ulong, IEnumerable<IEnumerable<ulong>>> func = null; func = (board, u) => { //ถ้าเดินทับจุดเดิม ก็ไม่มีผลลัพธ์ if ((board & u) > 0) return Enumerable.Empty<IEnumerable<ulong>>();
//ถ้าเดินครบ 64 ตา ก็คืนค่าตำแหน่งสุดท้าย var newBoard = board | u; if (newBoard == ulong.MaxValue) return u.ToEnumerable().ToEnumerable();
//เอาตาเดินม้าถัดไป มาวนใส่ Function นี้ //ได้ผลลัพธ์ ก็เอาตำแหน่งปัจจุบันมารวมกับคำตอบที่ได้ return from px in nextPoint(u) from sol in func(newBoard, px) select new[] { u }.Concat(sol); };
ป๊าด!!! จบแล้วครับ เริ่มรันได้เลย
var result = (from pos in func(0, 1).First().Select(ulongToPosition).WithIndex() group pos by pos.B[1] into g orderby g.Key select (from pos2 in g orderby pos2.B[0] select pos2.A.ToString("00")).Join(" ")).Join("rn"); Console.WriteLine(result);
//00 37 54 33 02 35 18 21 //53 46 01 36 19 22 03 16 //38 55 32 45 34 17 20 09 //47 52 39 56 23 10 15 04 //58 31 44 51 40 25 08 11 //43 48 57 24 61 14 05 26 //30 59 50 41 28 07 12 63 //49 42 29 60 13 62 27 06
ใช้เวลาไป 2 วินาทีกว่า ๆ!! โค๊ดแปลงเป็นตารางมี Function แปลก ๆ ไม่ต้องงงว่ามาจากไหน เป็น Function ที่ผมเขียนใช้เอง สนใจไปหาดาวน์โหลดใน Framework ของผมนะครับ
เพื่อนผมมันบอกว่า Functional Programming อ่านยาก เอาไปใช้ใน Production ไม่ได้ ผมก็ว่าจริงครับ ถ้าเขียนแล้วคนอื่นอ่านไม่เข้าใจ ก็เป็นโค๊ดที่ Maintain ไม่ได้ แต่มันก็เขียนสนุกครับ ตอนนี้เลยได้แต่เขียนคนเดียว มันส์คนเดียว คนไหนเขียน Functional Programming บ้าง ยกมือขึ้นครับ !!! (จะมีมั้ยเนี่ย หายากจริง ๆ)
Create Date : 04 สิงหาคม 2552 | | |
Last Update : 4 สิงหาคม 2552 0:45:26 น. |
Counter : 2873 Pageviews. |
| |
|
|
|
|
[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 น. |
Counter : 8336 Pageviews. |
| |
|
|
|
|
มีอะไรใหม่ใน C# 4.0
เมื่อสักครู่ เพิ่งดู Video Future of C# ของ Anders Hejlsberg จบ ประทับใจมาก เลยเอามาเขียนสรุปคร่าว ๆ มาให้อ่านกัน
ประวัติของ C# C# 1.0 - คือ จุดเริ่มต้นของภาษา C แบบ Managed Code ซึ่งทำให้การเขียน Code ปลอดภัยและไม่ซับซ้อน ไม่ต้องยุ่งกับ Memory C# 2.0 - เพิ่ม Generics (และ features อีกมากมาย) ทำให้ Collections ต่าง ๆ Type Safety และมีประสิทธิภาพ C# 3.0 - Version ปัจจุบัน เพิ่ม LINQ ทำให้เราสามารถ Query Collections ต่าง ๆ ง่ายดาย และ C# 4.0 - คือยุคของ Dynamic Programming ซึ่งจะพูดถึงต่อไป
แนวโน้มของภาษา Declarative - คือ แค่บอกว่าจะทำอะไร ไม่ต้องระบุว่าจะทำอย่างไร เช่น LINQ แค่สั่ง orderby ไม่ต้องเขียน for-loop Dynamic - เพื่อให้ทำงานร่วมกับภาษา Dynamic ต่าง ๆ เช่น Python, Ruby, JavaScript, และ COM Concurrency - ปกติการเขียน Code แบบ Muti-Thread จะยุ่งยาก แต่ Parallel Library จะจัดการส่วนที่ยุ่งยากให้
สิ่งใหม่ ๆ ใน C# 4.0 Dynamic Language Support Feature ชูโรงของ C# 4.0 Static Type คือ การกำหนด Type และกำหนด Method ต่าง ๆ ตอน Compile ทำให้ Application มีประสิทธิภาพ แต่ Dynamic Type จะกำหนด Type และ Method ที่ใช้ตอน Runtime ซึ่งมีข้อดีคือเขียนง่าย เร็ว C# 4.0 บอกว่าต่อไปนี้เราจะมี Type พิเศษ คือ dynamic ถ้า object ไหนเป็น dynamic ก็จะเรียก Method, Property, หรือ Index อะไรก็ได้ เช่น
dynamic d = GetDynamic(); d.Foo(); Object "d" อาจไม่มี method ชื่อ Foo ก็ได้ แต่จะ Compile ผ่านเสมอ มีประโยชน์ เช่น App ของ SilverLight เวลาไปคุยกับ JavaScript ทำให้ SilverLight สามารถเรียกคำสั่งต่าง ๆ ใน JavaScript ได้เลย (ใน Demo จะมีการเลือกชื่อ Contact ใน SilverLight แล้วตอนเลือก .Net จะเรียกคำสั่งดึงข้อมูล Map ผ่าน JavaScript แล้วเอาข้อมูลของ Map นั้นมาแสดงใน SilverLight)
Optional and Named Parameters เป็น Feature ล้าหลังมาก ซึ่ง VB.NET มีตั้งแต่ Version แรกแล้ว ปกติเราจะเขียน Method นึงที่รับหลาย ๆ parameter แต่บาง parameter มี default value ซึ่งไม่ต้องใส่ก็ได้ ก่อนหน้านี้เราต้องทำ method overloading สร้าง method หลาย ๆ ตัว เช่น public void MyMethod(string name, string location) { Console.WriteLine("Name is {0}, Location is {1}", name, location); } public void MyMethod(string name) { MyMethod(name, "Bangkok"); } แต่ Optional Parameter ทำให้เราเขียนแบบนี้ได้เลย public void MyMethod(string name, string location = "Bangkok") { Console.WriteLine("Name is {0}, Location is {1}", name, location); } COM Interoperability การทำงานกับ COM เขียนง่ายขึ้น หลัก ๆ ก็มาจาก dynamic และ named parameters และเพิ่มว่าไม่ต้องใส่ ref missing อีกต่อไป เช่น obj.Foo(ref missing, ref missing, ref missing, ref missing, 5, ref missing, ref missing, ref missing); เป็น obj.Foo(fooID: 5); จะเห็นว่าเขียนง่ายขึ้นเยอะ
Co- and Contra-Variance คือ การแปลง Type ของ Generic Type ปกติ เราไม่สามารถ assign IEnumerable<string> ไปที่ IEnumerable<object> ได้ แต่ C# 4.0 ทำได้
มีข้อกำหนดนิดหน่อยว่า คุณไม่สามารถทำ Co-Variance และ Contra-Variance พร้อมกันได้ คุณสามารถทำ Co-Variance ในกรณีที่ Type นั้นเป็น output ของ Method เท่านั้น เช่น IEnumerable<T> มี Method เดียวคือ IEnumerator<T> GetEnumerator() จะเห็นว่า T อยู่ในส่วนของ output ดังนั้นเราจึงทำ Co-Variance ได้ IEnumerable<string> เป็น IEnumerable<object> ได้
ส่วน Contra-Variance จะทำได้ในกรณี Type นั้นเป็น input ของ Method เท่านั้น เช่น IComparer<T> มี Method เดียวคือ int Compare(T a, T b) จะเห็นว่า T อยู่ในส่วนของ input ดังนั้นเราจึงทำ Contra-Variance ได้ IComparer<object> เป็น IComparer<string> ได้
และมีกรณีที่ไม่สามารถทำทั้ง Co- และ Contra-Variance ได้ คือ Type นั้นเป็น Value Type เช่น IEnumerable<int> ไม่สามารถเป็น IEnumerable<object> ได้ อีกแบบคือ Type นั้นเป็นทั้ง Input และ Output ของ Method เช่น List<T> มีทั้ง T List.get_Item(int a) และ void List.set_Item(int a, T item) จะเห็นว่า T อยู่ทั้งในส่วนของ Input และ Output จึงไม่สามารถทำ Co- และ Contra-Variance ได้
และจะมีอะไรใน C# 5.0? ใน Video จะมีปิดท้าย โชว์ Compiler as a Service ของ C# ถัดไปอีก เหมือนกับ Eval ใน JavaScript ที่สามารถเขียน Code ด้วย string ได้ (ซึ่งมีเป็นชาติแล้ว) ใน Video โชว์การทำ C# Shell ประมาณว่า เขียน Loop เขียน Function สร้าง Form จาก Shell ได้เลย
ถ้ามีเวลาว่างลองโหลดดูขำ ๆ ครับ ชั่วโมงกว่าเอง โหลด ที่นี่
Create Date : 16 มีนาคม 2552 | | |
Last Update : 16 มีนาคม 2552 1:27:09 น. |
Counter : 2569 Pageviews. |
| |
|
|
|
|
| |