พอดีเพิ่งเขียนเสร็จเลยเอามาปะไว้ เผื่อวันไหนจะใช้จะได้หาเจอ (ฮา) สคริปท์เป็น python เพราะว่าตอนจะรันไม่ต้องคอมไพล์ ง่ายดี (แต่อาจจะดีบั๊กลำบากนิดนึง) ใครสนใจก็แกะโค๊ดเองละกันนะครับ 😀

มีจุดที่ hard code อยู่หลายที่เหมือนกัน (โดยเฉพาะชื่อไฟล์) ว่าง ๆ ค่อยแก้ ใช้แบบนี้ไปก่อน ยังไง ๆ ก็คงไม่เขียนเป็นโปรแกรมเต็ม ๆ อยู่แล้ว

ปล. link ข้างในยังผิดอยู่ ตอนนี้ manual edit ใน text editor ไปก่อน ไม่ได้ลำบากอะไรนัก

import html.parser

class ContentParser(html.parser.HTMLParser):
	
	tdcount = 0
	count = 0
	
	start = None
	end = None

	def handle_starttag(self, tag, attrs):
		if(tag == 'td'):
			if(self.count == 2 and self.tdcount == 0 ):
				start = self.getpos()
				self.start = (start[0] , start[1] + len(self.get_starttag_text()) )
				print(self.start)
			self.tdcount = self.tdcount + 1
	
	def handle_endtag(self, tag):
		if(tag == 'td'):
			self.tdcount = self.tdcount - 1
			if(self.tdcount == 0):
				if( self.count == 2):
					self.end = self.getpos()
					print(self.end)
					
				self.count = self.count + 1
	
	def gen_content(self, lines):
		lineno = self.start[0] - 1
		output = ""

		while(lineno <= self.end[0] -1):
			start = 0
			end = len(lines[lineno])
			if(lineno == self.start[0] - 1):
				start = self.start[1]
				
			if(lineno == self.end[0] - 1) :
				end = self.end[1]
			output = output + lines[lineno][start:end] + "n"
			lineno = lineno+1
		return output
        
class HhcParser(html.parser.HTMLParser):
	parsed = 0
	output = ""
	def handle_starttag(self, tag, attrs):
		if (tag == "param" and attrs[0][1] == "Local"):
			# if(self.parsed == 4) : return
			
			htmlFile = open(attrs[1][1])
			print("Processing : " + attrs[1][1])
			lines = htmlFile.readlines()
			parser = ContentParser()
			
			for line in lines :
				parser.feed(line)
			
			self.output = self.output + parser.gen_content(lines) + "n"
			parser.close()
			htmlFile.close()
			self.parsed = self.parsed + 1
			
			return 1
	

hhcFile = open('0672325969.hhc')
output = open('output/index.html', 'w')
parser = HhcParser()
output.write('')
line = hhcFile.readline()

while (line != ""):
	parser.feed(line)
	line = hhcFile.readline()

parser.close()	
hhcFile.close()
output.write( parser.output)
output.write(' ')
output.close()

3

อันนี้เป็นหนึ่งในโปรเจคที่ผมเคยทำ่ส่งอาจารย์เมื่อนานมาแล้วนะครับ พอดีว่าเหงา ๆ มือ ก็เลยเอามาเขียนเล่นแก้เซ็ง 😛

Disjoint Set เป็นลักษณะของ Data Structure ประเภทหนึ่ง มันเป็นเซ็ตที่ไม่มีการทับซ้อนกันระหว่างเซ็ต ก็คือ สมาชิกของเซ็ตเซ็ตหนึ่งจะไม่สามารถเป็นสมาชิกของอีกเซ็ตหนึ่งได้ครับ

หาอ่านเพิ่มเติมได้ที่ Wikipedia นะครับ http://en.wikipedia.org/wiki/Disjoint_set_data_structure

ทีนี้ ผมเอา Disjoint Set มาประยุกต์สร้างเขาวงกต (หรือ Maze) โดยวิธีการสุ่มครับ ก็คือ Output ที่ได้จะแตกต่างกันทุกครั้งในการสร้างมันขึ้นมา ลักษณะพิเศษของเขาวงกตที่ได้คือ จะมีเพียงเส้นทางเดียวเท่านั้น จากจุดใด ๆ A ไปยังจุดใด ๆ B ครับ

ส่วนวิธีการสร้างเขาวงกตนี้นั้น ก็ตามนี้

  1. สร้างห้อง (ผมจะมองว่าแต่ละจุดของเขาวงกตเป็นห้องหนึ่งห้องครับ เพื่อความเข้าใจง่าย) ตามจำนวนที่ต้องการ กว้างกี่ห้อง ยาวกี่ห้องก็แล้วแต่ จำนวนของห้องตรงนี้จะเป็นจำนวนของห้องทั้งหมดใน Universe ครับ
  2. สร้าง Set ขึ้นมาให้เท่ากับจำนวนห้อง และให้แต่ละห้องเป็นสมาชิกของ Set (หนึ่งเซ็ตมีหนึ่งห้อง)
  3. สุ่มห้องขึ้นมาห้องหนึ่ง และสุ่มว่าจะให้เชื่อมต่อกับห้องไหน (ต้องเป็นห้องที่อยู่ติดกันนะครับ)
  4. เช็คดูว่าทั้งสองห้องที่สุ่มขึ้นมานั้นเป็นสมาชิกของ Set เดียวกันหรือไม่
    • ถ้าเป็นสมาชิกของ Set เดียวกันก็หมายความว่า ทั้งสองห้องนี้เชื่อมถึงกันอยู่แล้ว
    • ถ้าไม่เป็นสมาชิกของ Set เดียวกัน ก็ให้เชื่อมสัมพันธไมตรี โดยทำการรวม Set ที่ทั้งสองห้องนั้นเป็นสมาชิกให้การเป็น Set เดียวกัน (หรือที่เรียกว่าการ Union) ผลลัพท์ก็คือ ทุก ๆ ห้องใน Set จะเชื่อมต่อถึงกันหมด
  5. ย้อนกลับไปที่ข้อ 3. จนกระทั่งทุก ๆ ห้องเป็นสมาชิกของ Set เดียวกัน (นั่นหมายถึง Set นี้จะมีสมาชิกเป็นทุก ๆ ห้องใน Universe นั่นเอง)

maze

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

สำหรับการ Implement ผมใช้ List ในการ Implement นะครับ เพราะว่ามันง่ายดี จุดที่ต้องระวังก็มีแค่คุณลักษณะของ Disjoint Set (คือ สมาชิกในเซ็ตใด ๆ จะต้องไม่เป็นสมาชิกของเซ็ตอื่น ๆ ) และ คุณลักษณะของ Set ก็คือ ในแต่ละเซ็ตจะไม่มีสมาชิกที่ซ้ำกันนะครับ (อันนี้ต้องระวัง) แต่การ Implement จริง ๆ ผมแทบจะไม่ต้องมานั่งคิดพะวงเรื่องของคุณสมบัติพวกนี้เท่าไหร่นักครับ

ผมเขียนโค๊ดบน C# ก่อน แล้ว Port ไปเป็น C++ ซึ่งโค๊ดที่ผมจะเอามาแสดงไว้ข้างล่างเป็นภาษา C# ครับ

ผมจะเริ่มจาก Room ก่อนนะครับ

[Flags]
enum Connection
{
    None = 0, North = 1, South = 2, East = 4, West = 8
}

class Room
{
        private int x;
        private int y;
        private Connection connection;

        private List set;
}

x,y นั้นเป็นตำแหน่งของห้องครับ ส่วน connection นั้นเป็นตัวที่บอกว่าห้องนี้เชื่อมต่อกับห้องที่ติดกันห้องไหนบ้าง (เช่น ห้องทางเหนือ ทางใต้ เป็นต้น) ตรงนี้ผมใช้ Flag Enum ครับ

Method ที่สำคัญสำหรับคลาสนี้คือ ConnectTo ซึ่งใช้ในการเชื่อมห้องสองห้องเข้าด้วยการ

public bool ConnectTo(Room room, Connection con)
{
    if (room.set == this.set)
        return false;

    List temp = room.set;

    for (int i = 0; i < temp.Count; i++)
    {
        temp[i].set = this.set;
    }
    this.set.AddRange(temp);

    switch (con)
    {
        case Connection.North:
            room.connection |= Connection.South;
            break;
        case Connection.South:
            room.connection |= Connection.North;
            break;
        case Connection.East:
            room.connection |= Connection.West;
            break;
        case Connection.West:
            room.connection |= Connection.East;
            break;
    }
    this.connection |= con;

    return true;
}

สิ่งที่มันทำ คือ ทั้งสองห้องเป็นสมาชิกของห้องเดียวกันหรือเปล่า พอดีว่าห้องแต่ละห้องจะมี set เป็น member พอดี และ set ที่ว่านี้เนี่ยก็จะมีห้องเป็นสมาชิกของเซ็ตนี้พอดีด้วย (เพื่อลดความสับสน ผมใช้คำว่า member สำหรับส่วนที่เป็นภาษาเขียนโปรแกรม ส่วนสมาชิกนั้นใช้กับเรื่องเซ็ตครับ) ผมเลยจับเอาสมาชิกสองตัวนี้มาเทียบกันได้เลย และ ถ้าสองห้องนี้มี set เป็นตัวเดียวกัน ก็ return ออกไปเลยว่าไม่ได้มีการเชื่อมเกิดขึ้น

ส่วนต่อไปเป็นการรักษาคุณสมบัติข้างบน (ที่ว่าห้องจะมี set เป็น member โดยที่เซ็ตนี้จะมีห้องเป็นสมาชิกในเซ็ตอีกที) เนื่องจากว่าห้องทั้งหมดที่อยู่ในเซ็ตของห้องที่เราจะเอามาต่อเชื่อมนั้น จะต้องถูกย้ายมาเป็นสมาชิกของเซ็ตของห้องที่จะถูกต่อเชื่อม เราก็ทำการ assign ค่าตรงนี้ไป แล้วก็ทำการย้ายสมาชิกจากอีกเซ็ตนึงเข้าสู่อีกเซ็ตนึง

จากนั้น เซ็ตที่ไม่ใช้แล้วก็จะต้องถูกลบ เผอิญว่า C# นั้นมีส่วนที่จัดการตรงนี้อยู่แล้วก็เลยละไปได้ แต่ถ้าคุณเขียน C++ คุณต้องลบเซ็ตที่ไม่ใช้ทิ้งด้วยนะครับ

สุดท้ายก็เป็นการตั้ง flag ว่าห้องนี้ถูกเชื่อมกับห้องที่ติดกันห้องใดบ้าง และ ห้องที่ถูกเชื่อมก็ต้องตั้ง flag ให้รู้ว่ามันเชื่อมอยู่กับห้องนี้โดยตรงครับ

อีกคลาสนึงที่จะพูดถึงคือ คลาส Maze ซึ่งจะเป็นตัว Universe (บอกว่าตัวเขาวงกตนั้นมีกี่ห้องอยู่ตรงไหนบ้าง) และเป็นตัวสุ่มเชื่อมห้องแต่ละห้อง

class Maze
{
    Room[,] rooms;
    int width;
    int height;
}

ส่วน Method ที่สำคัญ ก็คือ Generate ซึ่งผมใช้สำหรับการสุ่มเชื่อมห้อง ตามวิธีที่ว่าไว้แล้ว โดยหน้าตาก็จะเป็นดังนี้

private void Generate()
{
    Random random = new Random();
    while (true)
    {
        int x = random.Next(0, width);
        int y = random.Next(0, height);

        Room currentRoom = rooms[x, y];

        int connectIndex;
        List aplicConTypeList = new List();

        if (x != 0)
            aplicConTypeList.Add(Connection.West);
        else if (x != width - 1)
            aplicConTypeList.Add(Connection.East);

        if (y != 0)
            aplicConTypeList.Add(Connection.North);
        else if (y != height - 1)
            aplicConTypeList.Add(Connection.South);

        connectIndex = random.Next(0, aplicConTypeList.Count);

        Room connectedRoom = null;
        switch (aplicConTypeList[connectIndex])
        {
            case Connection.North:
                connectedRoom = rooms[x, y - 1];
                break;
            case Connection.South:
                connectedRoom = rooms[x, y + 1];
                break;
            case Connection.East:
                connectedRoom = rooms[x + 1, y];
                break;
            case Connection.West:
                connectedRoom = rooms[x - 1, y];
                break;
        }

        currentRoom.ConnectTo(connectedRoom, aplicConTypeList[connectIndex]);

        if (currentRoom.ConnectedRoomCount == width * height)
        {
            break;
        }
    }
}

โดยหลัก ๆ ก็แค่ ทำการสุ่มหาห้องที่จะถูกเชื่อม หาห้องที่ติดกันที่จะเอามาเชื่อม แล้วก็เชื่อมไปเลย โดยส่วนที่เช็คว่าเชื่อมได้หรือไม่ได้นั้นอยู่ใน Room.ConnectTo อยู่แล้ว เลยไม่ต้องทำการเช็คอะไรครับ ตรงนี้จะเชื่อมไปเรื่อย ๆ จนกว่าทุก ๆ ห้องเป็นสมาชิกของห้องเดียวกันครับ

หลาย ๆ คนคงสนใจ output มากกว่า ... อืม พอดีผมขี้เกียจเขียน graphic output น่ะครับ ขออนุญาตใช้เป็น Text Output ละกัน เอาเป็น 30 * 30 นะครับ

╔╦══╗╥╥╞╦═╡╞══╦═╗╔╡╥╞╗╔══╦╦╗╔╡
║╨╥╔╝╠╝╔╣╥╥╞╗╥╨╞╣╠═╣╔╬╬╡╞╣║║╠╗
╨╞╣╠╡╚╗║╨╚╣╥║║╔╦╬╩╡╨╨╨╨╔═╣╨╨║╨
╥╥╠╣╞═╩╣╥╥║╚╬╝║║╚╗╞╦╡╞╗╠╡╚══╬╗
║╠╝╨╥╥╔╩╝║║╥╠╡╨║╞╣╔╝╔═╬╣╔╡╔╡╨╨
╚╬╡╔╩╣╠═╡╠╩╝╠═╦╩╗╚╩╡╚╡║╠╣╔╩═╗╥
╔╩╗╨╞╣║╞╗╠╗╥╨╔╝╥╚╡╥╥╥╔╝║╨╨╔═╩╝
║╔╬╡╞╣║╥╠╝╠╝╔╝╔╬═╦╝╚╣╠╗╨╥╞╩═╗╥
║╨╚╦═╝╚╣╚╗╨╥╠╦╝║╞╣╥╔╩╣╠╦╬╦╡╔╬╣
╠╡╔╩╡╔╡╚╗║╞╬╣╚╡║╥╚╩╬╗╨╨║║╚═╝╨║
╨╔╩╦╡╠═╡╠╬╗╨╚═╡╠╣╔╡║╨╥╥║╠╡╔═╡╨
╥╨╞╩╗║╔═╣╨╨╞╦═╡║╚╩╡║╔╬╝╨╠═╝╔╡╥
╚═╗╞╬╩╣╥╨╔═╗║╥╞╣╔╡╥╠╣║╔╦╩═╗╠╗║
╞╗╚╦╝╞╝║╞╬╡╨╚╩╗╚╣╞╩╣╨╨║║╞═╬╝╠╣
╞╬═╝╥╥╥║╔╩╡╞╗╞╣╔╝╞╦╣╥╥╨╚╗╥╨╔╣║
╔╬╡╥║╚╣╚╣╞╦╡╠╡╠╩╗╞╣╠╬╬═╡╨╠╦╣║║
╨╠╗╚╬═╩═╬╦╝╞╣╥╨╞╣╞╝║╨║╔╦═╝╨║╨╨
╞╝╠╗╚╗╥╞╣╠╡╔╩╣╔═╩╡╞╬╗║╨║╥╥╥╚╗╥
╔╗║╨╔╣╠╗╨╨╞╣╥╠╝╥╞╗╔╣╨╨╞╝║╠╣╔╣║
║╨╠╦╝║║╚╗╔╗╚╝╚═╝╞╩╝╚═╦╗╥╚╣╨╨╠╝
╚═╝║╞╣╠╗║║╚╡╥╞╗╞╦══╗╞╝║║╔╝╥╞╬╗
╥╔╗╠╡║║║╨╚╦═╬═╩╗║╔╡╨╞═╬╩╩═╣╥║╨
╠╝║╚╗║║║╔╡║╔╝╔═╩╝║╥╞═╗╚╡╞╦╝╚╬╗
╚╡╚═╝║║╨╠╡╨╠╗╚╡╞╦╝╠╦╡╚═╦╦╝╔╦╝╨
╞╦═╦═╝╠═╩╗╥║╚╗╥╔╩╡╨║╞══╝╨╔╝╨╔╡
╞╣╞╬╗╥╨╞═╬╩╩╡╠╩╝╔╡╥╚═══╦╗╚╦═╩╗
╥╠╗╨╚╩══╦╩╡╞═╣╥╥╠═╣╔═╦╡╨║╔╩═╡╨
╠╝╚╡╥╞╗╥║╥╥╥╔╩╬╣╨╥╠╩╡╚═╦╝╠═╡╔╡
╠╗╥╔╬╗╠╩╣╠╝╚╝╥║╠╦╩╣╥╥╔═╬═╩╦╦╝╥
╨╨╚╝╨╚╩╡╚╩╡╞═╩╝╨╚╡╚╝╚╩╡╚═╡╨╚═╝

หรือถ้า ไม่เห็นว่าข้างบนเป็นรูปก็ ... เอารูปไปดูแทนละกันครับ (อันนี้เผื่อเฉย ๆ)
Output จากโปรแกรมครับ
(สองอันข้างบนไม่เหมือนกันนะครับ)

ไม่รู้จะมองเป็นเขาวงกตกันหรือเปล่า ให้ดูข้างในเส้นระหว่างสองเส้นแคบๆ นะครับ ไม่ใช่ด้านกว้าง (พอดีว่า Console มันได้แค่นี้น่ะครับ)

สุดท้ายก็ต้องเป็น Code สินะ ... Visual C# Express 2008 นะครับ ลองเล่นดูได้
mazegenerator.zip

ลองเล่นแล้วเป็นไง เอามาบอกผมบ้างนะครับ

ปล. ผมเคยทำเวอร์ชั่นที่เป็นกราฟิคมาก่อน เลยรู้ว่า กว่าจะเล่น Maze ขนาด 30 * 30 ผ่าน (ผมตั้งกฎว่าให้เดินจากห้องมุมซ้ายบน ไปยังห้องมุมขวาล่าง) ได้ เล่นเอาเหงื่อตกครับ แล้วโปรแกรมนี้สามารถสร้าง Maze ระดับหลายหมื่นห้องได้สบาย ๆ ... ก็ลองดูแล้วกันนะครับว่าจะเป็นยังไง อิอิ ...

ปลล. โปรเจคนี้ได้คะแนนเท่าไหร่เหรอ ????? จำได้ว่าประมาณ A- หรือ B+ ครับ อ.บอกว่าต้องทำเฉลยมาด้วย ไม่งั้นได้ A ไปละ 😛