neizod's speculation

insufficient data for meaningful answer

เฉลย Code Jam ข้อ Cubic UFO อย่างละเอียด

Saturday, April 14, 2018, 06:51 AM

สัปดาห์ก่อนเขียนเฉลย Code Jam 2018 รอบคัดเลือกไป ซึ่งก็แอบอู้ไม่อธิบายข้อสุดท้าย เอากระดานที่ทดสมการมาแปะแทน … หลายคนน่าจะแอบด่าในใจไปแล้วว่าอ่านไม่เห็นรู้เรื่องเลย 555 งั้นตอนนี้ขอแก้ตัวอธิบายวิธีทำข้อ Cubic UFO อย่างละเอียดละกันครับ

แนวคิดพื้นฐาน

สังเกตว่าลูกบาศก์ 3 มิติ เมื่อฉายเงา (projection) ลงมาใน 2 มิติ คือการตัดค่าตำแหน่งในแกนตั้งออกไปนั่นเอง (โจทย์ข้อนี้กำหนดให้แกนตั้งคือแกน Y … น่าแปลกใจมากว่าทำไมไม่ใช้แกน Z กำหนดแบบนี้แล้วเห็นมีคนพลาดตั้งหลายคน)

ดังนั้นลูกบาศก์หนึ่งหน่วยที่อยู่นิ่งๆ ยังไม่ได้หมุนอะไร ก็จะมีจุดยอดของเงาอยู่ 4 จุด (มีทั้งหมด 8 จุดแต่ซ้ำกันไปซะครึ่ง) ได้แก่

เกิดเป็นเงารูปสี่เหลี่ยมจัตุรัส มีขนาดพื้นที่เป็น 1 ตารางหน่วย

ทีนี้เมื่อเราหมุนลูกบาศก์ตามแกน X จะเห็นว่ารูปร่างเงาเปลี่ยนไปเป็นสี่เหลี่ยมผืนผ้า ดังภาพประกอบที่ 1

ภาพที่ 1: พื้นที่เงาต่างๆ เมื่อหมุนลูกบาศก์ตามแกน X

พื้นที่สี่เหลี่ยมผืนผ้าที่ได้เมื่อหมุนลูกบาศก์ จะมีขนาดตั้งแต่ 1 ถึง $\sqrt{2}$ ตารางหน่วย โดยลูกบาศก์ต้องถูกหมุนไป 45 องศาพอดีเพื่อให้มีพื้นที่มากที่สุด หากอนุญาตให้หมุนแค่แกน X แกนเดียว

แต่เรื่องสุดสนุกกำลังจะเกิดขึ้นเมื่อเราเริ่มหมุนแกนที่สองหลังจากหมุนแกนแรกจนได้พื้นที่มากที่สุดไปแล้ว … แน่นอนคำถามที่ตามมาคือ แล้วจะหมุนแกนไหนดีหละ?

หากเราหมุนแกน Y ก็จะได้ผลลัพธ์ตามภาพประกอบที่ 2 นี้

ภาพที่ 2: พื้นที่เงาต่างๆ เมื่อหมุนลูกบาศก์ตามแกน Y หลังจากหมุนแกน X ไปแล้ว 45 องศา

น่าจะเห็นชัดแล้วว่าการหมุนตามแกน Y ไม่ช่วยอะไรเลย!

ส่วนการหมุนตามแกน Z ให้ผลลัพธ์ตามภาพประกอบที่ 3

ภาพที่ 3: พื้นที่เงาต่างๆ เมื่อหมุนลูกบาศก์ตามแกน Z หลังจากหมุนแกน X ไปแล้ว 45 องศา

พื้นที่เงาที่มีขนาดใหญ่ที่สุด เกิดขึ้นเมื่อหมุนลูกบาศก์ตามแกน X ไป 45 องศา แล้วจึงหมุนตามแกน Z ไปอีก $\arctan\frac{1}{ \sqrt{3} }$ (หรือประมาณ 35.26) องศา ซึ่งให้ขนาดเงาเป็นรูปหกเหลี่ยมด้านเท่า ที่ขนาด $\sqrt{3}$ ตารางหน่วย

ถึงตอนนี้ถ้าเรารู้จักอัลกอริทึม binary search, convex hull, shoelace formula, และ rotation matrix ก็สามารถแก้ไขปัญหานี้ได้แล้วด้วยโค้ดเทียมต่อไปนี้

CONSTANTS:
    corners = { (+-0.5, +-0.5, +-0.5) }
    faces = { (0.5, 0, 0), (0, 0.5, 0), (0, 0, 0.5) }

FUNCTION binary_search(corners, area, lower, upper):
    LOOP:
        angle = (lower+upper)/2
        points = rotate_x(corners, angle)
        points_on_plane = projection_xz(points)
        corners_on_plane = convex_hull(points_on_plane)
        guess_area = shoelace(corners_on_plane)
        IF guess_area < area:
            lower = angle
        ELSE IF guess_area > area:
            upper = angle
        ELSE:
            RETURN angle

FUNCTION solve():
    READ FLOAT required_area
    IF 1 <= required_area <= sqrt(2):
        angle = binary_search(corners, required_area, 0, 45)
        out_faces = rotate_x(faces, angle)
    ELSE IF sqrt(2) < required_area <= sqrt(3):
        tmp_corners = rotate_x(corners, 45)
        angle = binary_search(tmp_corners, required_area, 0, atan(1/sqrt(2)))
        tmp_faces = rotate_x(faces, 45)
        out_faces = rotate_z(tmp_faces, angle)
    PRINT out_faces

หามุมที่ใช่โดยไม่ต้องแบ่งเคสการหมุน

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

แต่หากเราพิจารณาการหมุนทั้งหมด จะเห็นว่าพื้นที่เงามันครอบคลุมพื้นที่ตั้งแต่ช่วง 1 ถึง $\sqrt{3}$ เช่นกัน นี่หมายความว่าเราไม่จำเป็นต้องแบ่งคิดเป็นช่วงๆ ก็ได้ แต่เปลี่ยนวิธีคิดเป็นดังนี้

เริ่มจากหมุนลูกบาศก์ตามแกน Y ไป 45 องศา (สังเกตว่าตอนนี้พื้นที่ยังเป็น 1 ตารางหน่วย) แล้วต่อมาจึงหาว่าต้องหมุนตามแกน Z (หรือแกน X ก็ได้) อีกกี่องศาจึงจะได้พื้นที่ตามที่ต้องการ

...

FUNCTION solve():
    READ FLOAT required_area
    adjust_corners = rotate_y(faces, 45)
    angle = binary_search(adjust_corners, required_area, 0, 90-atan(1/sqrt(2)))
    tmp_faces = rotate_y(faces, 45)
    out_faces = rotate_x(tmp_faces, angle)
    PRINT out_faces

ตรีโกณมิติหาคำตอบพอดี

วิธีข้างบนๆ นั้นเขียนเร็วและง่าย (และก็เพียงพอที่จะทำงานทัน) แต่หากลงแรงคิดต่อไปอีกนิด ก็จะพบว่ามีคำตอบที่ไม่ต้อง binary search เช่นกัน

ภาพที่ 4: มุมและความยาวสำคัญต่างๆ สำหรับคำนวณพื้นที่เงา เมื่อหมุนลูกบาศก์ตามแกน Y ไป 45 องศา แล้วหมุนตามแกน Z อีก θ องศา

พิจารณาภาพประกอบที่ 4 จะเห็นว่าเราสามารถคำนวนพื้นที่รูป 6 เหลี่ยมได้โดยตรง โดยไม่ต้องพึ่ง convex hull และ shoelace formula แล้ว ซึ่งก็คือ

แต่เนื่องจาก

ดังนั้น

แม้ฝั่งขวาของสมการจะติดฟังก์ชันตรีโกณมิติ 2 ฟังก์ชัน แต่ถ้ายังจำเอกลัษณ์ตรีโกณมิติกันได้ จะพบว่าสามารถจัดรูปให้เป็น

ซึ่งก็คือ

เพราะฉะนั้น

ดังนั้น

และเมื่อหาฟังก์ชันผกผันเพื่อคำนวนมุมจากพื้นที่ ก็จะได้เป็น

ซึ่งนำไปเขียนโค้ดเทียมได้สั้นลงเหลือแค่นี้

FUNCTION solve():
    READ FLOAT required_area
    angle = asin(required_area/sqrt(3)) - asin(1/sqrt(3))
    tmp_faces = rotate_y(faces, 45)
    out_faces = rotate_z(tmp_faces, angle)
    PRINT out_faces

ก็ถือว่าจบการเฉลยในข้อนี้

ป.ล. ภาพประกอบพล๊อตขึ้นจากภาษา R ตามไฟล์นี้