Bloggang.com : chaowman - Solve ปัญหาการเลื่อนรถใน Brand Genius Exit

Bloggang.com : weblog for you and your gang

Just algorithm!

Solve ปัญหาการเลื่อนรถใน Brand Genius Exit

สวัสดีหลังปีใหม่ไทยครับ
จริง ๆ มีเรื่องอยากจะ Post ใน Bloggang นี้มากมาย
แต่เล่น Post ทีประมาณ 3-4 เดือนครั้ง
วันนี้เลยถึงรอบต้อง Post แล้วล่ะครับ อิอิ Smiley

Post ที่แล้ว มีน้อง Post ข้อความให้เล่นเกมส์ ฺBrand Genius Exit
เนื่องจากความโลภ บวกความขี้โกง คิดว่าเขียนโปรแกรมแล้วจะชนะได้
ผิดคาดครับ คนเก่ง ๆ ในไทยยังมีอีกมากมาย แต่ไม่แสดงตัวเท่านั้นเองครับ Smiley

งานนี้เลยได้แค่ Thumbdrive เป็นของขวัญปลอบใจ Smiley

ใครเล่นแล้วมาคุยกันได้ครับ ว่ามีวิธีการ 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 น.

1 comments

Counter : 1566 Pageviews.

ขอคารวะ หนึ่งเป๊ก ให้ท่าน chaowman ที่ยังคงถ่ายทอดบทความดีๆ อย่างนี้เสมอมา

โดย: Executive Toilet

วันที่: 30 สิงหาคม 2553 เวลา:13:12:35 น.

chaowman

Location :
กรุงเทพฯ Thailand

[Profile ทั้งหมด]

ฝากข้อความหลังไมค์

Smember

ผู้ติดตามบล็อก : 8 คน [?]

New Comments

Group Blog

All Blogs

Friends' blogs

[Add chaowman's blog to your web]

Links

BlogGang.com

Pantip.com | PantipMarket.com | Pantown.com | © 2004 BlogGang.com allrights reserved.