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

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

ตัวอย่างการส่งคำถาม 4 ครั้ง ซึ่งสามารถทำให้ระบุได้ว่าสายไฟเส้นตรงกลางต่อเชื่อมไปยังสวิตช์ตัวบน

โปรแกรมเชิงถามตอบ

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

from random import randrange

def initialize(n):
    wires = [randrange(n) for i in range(n)]
    switches = [False for _ in range(n)]
    return wires, switches

def judge(n=90, limit=900):
    wires, switches = initialize(n)
    print(n)
    for _ in range(limit):
        command, *rawindex = input().split()
        indexes = [int(r) for r in rawindex]
        if command == 'C':
            index = indexes[0]
            switches[index] = not switches[index]
            print('NY'[switches[index]])
        if command == 'T':
            index = indexes[0]
            print('NY'[switches[wires[index]]])
        if command == 'D':
            print('NY'[wires == indexes])
            return
    print('N')

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

ในระบบปฏิบัติการตระกูล POSIX เราคงคุ้นเคยกันดีกับการ pipe ส่งข้อมูลขาออกจากโปรแกรมแรกไปเป็นข้อมูลขาเข้าให้โปรแกรมที่สอง อย่างไรก็ตามในโจทย์ที่เรากำลังแก้นี้เราต้องการการพูดคุยแบบสองทาง โปรแกรมที่สองยังต้องสามารถส่งข้อมูลกลับไปยังโปรแกรมแรกได้ด้วย เราสามารถต่อ pipeline ให้กับระบบได้ผ่าน named pipe ในที่นี้จะเป็นการสร้าง pipe ที่ชื่อ comm ขึ้นมาก่อน แล้วจึงจับมันมาต่อเป็นลูปแบบนี้

mkfifo comm
<comm ./judge | ./contestant >comm

ถึงตอนนี้เราก็พร้อมที่จะโฟกัสกับการแก้โจทย์ปัญหาแล้ว

เทคนิคจากเลขฐานสอง

ลองโยนความคิดว่าเรามีสายไฟหลายเส้นทิ้งไปก่อน แล้วพิจารณาแค่ว่าเรามีสายไฟเพียงเส้นเดียวกับสวิตช์ $m$ ตัว เราจะแก้ปัญหานี้อย่างไร? ถ้าเราไล่เปิดสวิตช์ทีละตัวสลับกับวัดไฟไปเรื่อยๆ แม้โดยเฉลี่ยแล้วเราจะสับสวิตช์ไฟครึ่งหนึ่งถึงจะได้คำตอบ (รวมกับการวัดไฟคือใช้คำสั่งประมาณ $m$ ครั้ง) แต่ถ้าเราโชคร้ายก็อาจต้องสับสวิตช์เพื่อทดสอบทุกตัว ซึ่งก็คือเราจะใช้คำสั่งไปมากถึง $2m$ ครั้งเลยทีเดียว

แต่ระลึกไว้เสมอว่า เพื่อนแท้ที่ดีที่สุดของนักวิทยาการคอมพิวเตอร์ก็คือเลขฐานสอง เราอาจมองได้ว่าสวิตช์แต่ละตัวนั้นมีตัวเลขกำกับเป็นเลขฐานสองจาก $\lbrace0,1,10,11,100,\ldots,m{-}1\rbrace$ แล้วหลังจากนั้นเราจะสับสวิตช์หลายๆ ตัวให้เสร็จก่อนที่แล้วจึงค่อยทดสอบไฟ โดยครั้งแรกเราจะเปิดสวิตช์ทุกตัวที่มีบิตที่อยู่ขวาสุดเป็นหนึ่งแล้วทดสอบไฟ ครั้งถัดมาเราค่อยเปิดสวิตช์ทุกตัวที่มีบิตอยู่ในบิตที่สอง (อาจต้องสับสวิตช์บางตัวที่เคยเปิดในครั้งก่อนให้กลายเป็นปิด) แล้วทดสอบไฟ หลังจากนั้นก็สับสวิตช์และวัดไฟในทำนองนี้ไปเรื่อยๆ จนไล่ครบทุกบิต เช่นนี้แล้วการทดสอบไฟแต่ละครั้งก็คือการบอกว่าแต่ละบิตของตำแหน่งสวิตช์ไฟมีค่าเป็นเท่าไหร่

\[\begin{array}{c|cccccccccc} \text{round} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline 1 & \circ & \bullet & \circ & \bullet & \circ & \bullet & \circ & \bullet & \circ & \bullet \\ 2 & \circ & \circ & \bullet & \bullet & \circ & \circ & \bullet & \bullet & \circ & \circ \\ 3 & \circ & \circ & \circ & \circ & \bullet & \bullet & \bullet & \bullet & \circ & \circ \\ 4 & \circ & \circ & \circ & \circ & \circ & \circ & \circ & \circ & \bullet & \bullet \end{array}\]

ตัวอย่างการสับสวิตช์สิบตัว ณ รอบต่างๆ ดังนั้นหากไฟติดในรอบที่ $1,3$ และดับในรอบ $2,4$ นั่นหมายถึงสายไฟเชื่อมไปยังสวิตช์หมายเลข $(0101)_2 = 5$

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

\[\begin{array}{c|cccccccccc} \text{round} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline 1 & \circ & \bullet & \circ & \bullet & \circ & \bullet & \circ & \bullet & \circ & \bullet \\ 2 & \circ & \bullet & \bullet & \circ & \circ & \bullet & \bullet & \circ & \circ & \bullet \\ 3 & \circ & \bullet & \bullet & \circ & \bullet & \circ & \circ & \bullet & \circ & \bullet \\ 4 & \circ & \bullet & \bullet & \circ & \bullet & \circ & \circ & \bullet & \bullet & \circ \end{array}\]

ตัวอย่างการสับสวิตช์สิบตัวในอีกทางหนึ่ง ซึ่งหากไฟติดในรอบที่ $1,2$ และดับในรอบที่ $3,4$ จะตีความได้ว่ามีการเปลี่ยนแปลงเกิดขึ้นในรอบแรก (ถือว่ารอบก่อนรอบแรกไฟไม่ติด) และรอบที่สาม จึงได้ว่าสายไฟเชื่อมไปยังสวิตช์หมายเลข $(0101)_2 = 5$

สังเกตว่าวิธีนี้ใช้การส่งคำสั่งประมาณ $(\frac12m+1)\log_2m$ ครั้งเพื่อวัดสายไฟหนึ่งเส้น ซึ่งถ้าเทียบกับการไล่ถามตรงไปตรงมาที่ใช้ประมาณ $m$ ครั้งก็ดูจะแย่กว่า แต่อย่าลืมว่าเราต้องการหาการเชื่อมต่อของสายไฟหลายเส้น ดังนั้นจะเห็นว่าวิธีแบบเลขฐานสองนั้นจะกลายเป็นประหยัดได้ เพราะส่วนของการทดสอบสายไฟจะกลายเป็นตัวบวกแทนที่จะเป็นตัวคูณ ซึ่งก็คือถ้าเราต้องการทดสอบสายไฟ $n$ เส้น วิธีแบบตรงไปตรงมาจะต้องถามคำถามประมาณ $mn$ ครั้ง ส่วนวิธีแบบเลขฐานสองจะใช้แค่ $(\frac12m+n)\log_2m$ ครั้งเท่านั้น

ดังนั้นเราจึงได้โค้ดสำหรับแก้ปัญหานี้ว่า

def communicate(command, *values):
    print(command, *values)
    return {'N':0, 'Y':1}[input().strip()]

def bin_repr_search(n):
    prevs = [0 for _ in range(n)]
    wires = [0 for _ in range(n)]
    switches = [0 for _ in range(n)]
    for shift in range(ceil(log2(n))):
        mask = 1 << shift
        for i in range(n):
            if bool(i & mask):
                switches[i] = communicate('C', i)
        for i in range(n):
            curr = communicate('T', i)
            if curr != prevs[i]:
                wires[i] |= mask
            prevs[i] = curr
    return communicate('D', *wires)

ซึ่งสำหรับสายไฟและสวิตช์ $90$ ชุด จะได้ว่าเราต้องส่งคำถามเป็นจำนวน $906$ ครั้ง …

เลี่ยงการทดสอบสวิตช์ที่ไม่จำเป็น

หากเรามีสายไฟและสวิตช์เป็นจำนวนในรูป $2^k$ ยังไงซะเราก็ต้องไล่สับสวิตช์เพื่อทดสอบไปจนครบทุกวิธีการเขียนเลขฐานสองขนาด $k$ บิตทุกวิธีที่เป็นไปได้อยู่แล้ว แต่เนื่องจากว่าจำนวนสายไฟและสวิตช์ที่เราได้รับมานั้นมีค่าเท่ากับ $2^k$ พอดี นึ่จึงทำให้เราสามารถข้ามการทดสอบตัวเลขบางตัวไปได้ เช่น พิจารณากรณีที่ $m=90$ เราจะเขียนตัวเลขให้กับสวิตช์ตัวสุดท้ายในขนาด $k=7$ บิตได้เป็น $(1011001)_2=89$ นั่นหมายความว่าถ้าเราทดสอบไป $6$ บิตแล้วพบว่าค่า $x$ ที่เป็นคำตอบระหว่างทางนั้นอยู่ในช่วง $(011001)_2 < x \le (111111)_2$ นั่นหมายความว่าเราไม่จำเป็นต้องส่งคำถามเพื่อทดสอบบิตที่ $7$ แล้ว เพราะบิตนี้ต้องมีค่าเป็นศูนย์แน่นอน

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

def partition(candidates, lo, mid, hi, switch):
    for i in range(lo, mid):
        communicate('C', i)
    left, right = [], []
    for i in candidates:
        light = communicate('T', i)
        (right if light == switch else left).append(i)
    return left, right

def aux(candidates, lo, hi, switch=0):
    if hi - lo <= 1 or not candidates:
        return [(i,lo) for i in candidates]
    mid = (lo+hi) // 2
    left, right = partition(candidates, lo, mid, hi, switch)
    return aux(left, lo, mid, switch^1) + aux(right, mid, hi, switch)

def recursive_search(n):
    result = sorted(aux(range(n), 0, n))
    return communicate('D', *[str(v) for _, v in result])

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

neizod

author