neizod's speculation

insufficient data for meaningful answer

แก้โจทย์ป้ายสมัครงาน Google แบบบรรทัดเดียว

Monday, September 3, 2012, 08:10 AM

นอนไม่หลับ บวกกับช่วงนี้แก้โจทย์เล่นเยอะไปหน่อย เหมือนสมองไม่อยากหยุดแก้โจทย์ 555

แล้วก็นึกได้ว่า ไอ้โจทย์ป้ายสมัครงานของ Google อันนี้ ยังไม่เคยแก้เล่นเองเลยนี่หว่า

แต่ถ้าจะให้แก้ตามปรกติธรรมดา ก็ดูจะไม่ท้าทายซักเท่าไหร่ไปแล้ว (เพราะเล่นไปอ่านเฉลยมาเรียบร้อย) แบบนี้เลยต้องเพิ่ม standard ให้กับตัวเองด้วยการเขียนเป็น one-liner โดยไม่พึ่งพา stdlib ซะเลย

ตัวโจทย์คงไม่ต้องแปลแล้ว? (ถ้าตีโจทย์ไม่ออกจริงๆ แนะนำบล็อก @khajochi ตอนนี้เลย) เอาเป็นว่าเริ่มกันเลยดีกว่านะ


โดย algorithm ที่จะใช้คำนวณหาค่า $e$ คือ

ต้องใช้ algorithm นี้เพราะว่ามันให้ค่าทศนิยมได้แม่นยำรวดเร็วพอสมควร และยัง implement ตามไม่ยากเท่าไหร่ ในที่นี้ใช้ถึงแค่พจน์ $\frac{1}{200!}$ ก็ให้ค่าออกมาแม่นยำเกือบ 400 ตำแหน่งแล้ว

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

factorial = lambda n: (lambda f, x: f(f, x))(lambda r, y: y*r(r, y-1) if y > 1 else 1, n)

(รายละเอียดอ่านได้จากตอนก่อนๆ)

ต่อมาคือการจับแต่ละพจน์มาบวกกัน ซึ่งจะ implement ตรงๆ แบบนี้ไม่ได้

sum(1/factorial(i) for i in range(200))

เพราะ float มันเก็บ precision ของทศนิยมได้เล็กนิดเดียว ดังนั้นเราต้องดัดแปลงสมการต้นแบบให้กลายเป็น

เทคนิคหนึ่ง (ใน Python) ที่ใช้ได้เสมอๆ เมื่อต้องการทศนิยมละเอียด $n$ ตำแหน่ง คือคูณด้วย $10^n$ เข้าไปเพื่อให้กลายเป็นจำนวนเต็ม แล้วค่อยนำไปหารปัดเศษทีหลังสุดนั่นเอง ดังนั้น

แต่จากการสังเกตที่เคยทำมาแล้ว เราต้องการ $n=400$ และไล่คูณค่า factorial ไปแค่ $200$ ก็พอ ไม่ต้องถึง $\infty$ ดังนั้น

จะเห็นว่าถ้าเรียงลำดับ operator ดีๆ เราจะไม่สูญเสีย precision เพราะไม่ต้องแปลงเลขไปเป็น float เลย

ได้แนวคิดแล้วก็เริ่ม implement กัน เริ่มโดยหา factorial ของพจน์ต่างๆ ตามปรกติ

fact_each = [factorial(i) for i in range(200)]

ทีนี้เพื่อป้องกันการคำนวณซ้ำหลายรอบ ก็เอา lambda มาห่อหุ้มมันซะ ซึ่งสิ่งที่เราต้องการต่อจากนี้คือผลคูณรวมของค่าทั้งหมด โดยเรายังคงต้องใช้ list เดิมนี้อยู่ ดังนั้น

prod_and_fact_each = (lambda l: [reduce(lambda x, y: x*y, l), l])(fact_each)

ถึงตอนนี้ก็ได้เวลาเอาผลคูณรวมของ factorial ทุกตัว มาหารแต่ละตัวใน list นั้นแล้ว (เรายังต้องใช้ผลคูณรวมอีกรอบ ดังนั้นส่งต่อมันด้วย)

prod_and_div_each = (lambda a, l: [a, [a // i for i in l]])(*prod_and_fact_each)

สุดท้ายก็จับทุกตัวมาบวกกัน คูณด้วย $10^{400}$ แล้วค่อยหารด้วยค่ารวมนั้น

e = str((lambda a, l: 10**400 * sum(l) // a)(*prod_and_div_each))

เท่านี้ก็ได้เลข $e$ ที่มีทศนิยมตามต้องการแล้วนะ <3


สำหรับส่วนที่สองจะมาดูที่จำนวนเฉพาะ เนื่องจากเลข 10 หลักค่าที่ใหญ่ที่สุดคือ $n=9999999999$ การที่จะบอกว่ามันเป็นจำนวนเฉพาะหรือไม่ ก็ทดสอบด้วยการเอาไปหารจำนวนเฉพาะทุกตัวที่น้อยกว่ามันไปจนถึง $\lfloor\sqrt{n}\rfloor$ ซึ่งหมายความว่าเราตรวจถึงแค่จำนวนเฉพาะที่น้อยกว่า $\lfloor\sqrt{9999999999}\rfloor=99999$ ก็พอแล้ว

เริ่มด้วยฟังก์ชั่นเพิ่มจำนวนเฉพาะเข้าไป

add_prime = lambda p, t: p + [t] if all(t % q for q in p) else p

ฟังก์ชั่นนี้จะรับตัวแปร 2 ตัวคือ list ของจำนวนเฉพาะก่อนหน้า และเลขที่จะตรวจว่าเป็นจำนวนเฉพาะหรือเปล่า ส่วนค่าที่คืนมานั้น ถ้าเป็นจำนวนเฉพาะจะคืน list ที่เพิ่มจำนวนที่ตรวจเข้าไปด้วย ดังนั้นสิ่งที่เราต้องทำคือใส่ list ว่างๆ เข้าไปก่อน แล้วส่งเลขที่น้อยที่สุดคือ $2$ เข้าไปตรวจ หลังจากได้ list ที่มีเลข $2$ ก็ส่งเลข $3,4,5,6,…,99999$ เข้าไปตรวจทีละตัว โดย list ที่เป็นผลลัพท์แต่ละครั้งที่ได้มาก็จะเก็บไว้ใช้ต่อไปเรื่อยๆ นี่ก็คือแนวคิดของ reduce นั่นเอง ซึ่งก็จะเขียนได้ว่า

p = reduce(add_prime, [[], 2] + range(3, 100000, 2))

ถึงตอนนี้ก็มีจำนวนเฉพาะทั้งหมดที่ต้องการสำหรับงานนี้แล้ว :3


สุดท้าย ได้เวลาจับทุกอย่างมารวมกัน เริ่มจากการพยายาม loop ไปยังเลข 10 หลักในทศนิยมของ $e$ ก่อน ซึ่งก็คือ

[e[i:10+i] for e in [e] for i in range(len(e)-9)]

แต่เนื่องจากเราต้องการ filter ตัวที่ไม่ใช่จำนวนเฉพาะออกไป ซึ่งคราวนี้เราจะเปลี่ยนมาทดสอบด้วยฟังก์ชั่น

test_prime = lambda p, e: all(int(e) % q for q in p)

ดังนั้นก็จะได้

[e[i:10+i] for e, p in [[e, p]] for i in range(len(e)-9) if test_prime(p, e[i:10+i])]

แน่นอนว่างานนี้เราต้องการแค่จำนวนเฉพาะตัวแรกที่เจอ ดังนั้นสามารถเปลี่ยนไปเขียน

next(e[i:10+i] for e, p in [[e, p]] for i in range(len(e)-9) if test_prime(p, e[i:10+i]))

ก็จะได้คำตอบแล้วหละ \(^0^)/


สำหรับ code ฉบับเต็มๆ ที่เป็น one-liner (แต่ขึ้นบรรทัดใหม่เพื่อให้อ่านสะดวก) คือ

next(e[i:10+i] for e, p in [[
        str((lambda a, l: 10**400 * sum(l) / a)(*
            (lambda a, l: [a, [a / i for i in l]])(*
                (lambda l: [reduce(lambda x, y: x*y, l), l])(
                    [(lambda f, x: f(f, x))(
                           lambda r, y: y * r(r, y-1) if y > 1 else 1, i)
                        for i in range(200)])))),
        reduce(
            lambda ps, t: ps + [t] if all(t % p for p in ps) else ps,
            [[], 2] + range(3, 100000, 2))]]
    for i in range(len(e)-9)
        if all(int(e[i:10+i]) % q for q in p))

happy coding นะครับ ^^