Google Code Jam 2013 – Qualification Round 1C

ตกรอบทั้งแผ่นดิน :\ rank 2691

รอบนี้เหมือนจะง่ายเลยครับ ก็

# Consonants

ข้อนี้ให้ string มา แล้วจะมีพยัญชนะติดกันหลายๆ ตัว ถามว่ามี substring ที่มีพยัญชนะติดกันมากกว่า n ตัวกี่ substring

(substring คือส่วนใดส่วนหนึ่งของ string ตั้งแต่ 1 ตัวข้ึนไป และ substring เขียนเหมือนกันแต่เป็นคนละตัวได้ถ้าตัดมาจากคนละท่อนกัน คือจุดเริ่มต้นหรือจุดสิ้นสุดเป็นคนละจุด)

ผมใช้วิธีโง่ๆ อีกแล้วคือหาก่อนว่ามี substring ที่ตรงตามเงื่อนไขที่ตำแหน่งไหนบ้าง พอได้ครบแล้วก็หา substring ทั้งหมดแล้วหาว่ามีส่วนใดส่วนหนึ่งของ substring ที่พบในตอนแรกมั้ย ถ้ามีก็ดูว่าครบตาม n ตัวก็ให้ผ่านได้

ข้อนี้ large ไม่ทันครับ ไฟล์มัน 4MB มีข้อดัก 5 ข้อที่ string น่าจะหลายล้านตัว (เปิดไฟล์มา sublime ผมค้าง หน้าจอมีแต่ rrrrrrrrrrrrrr)

# Pogo

ผมคิดว่ามันง่ายนะ แต่ผมไม่รู้เรื่องนี้

ให้หาเส้นทางจาก (0,0) ไปจุดที่กำหนด (อาจจะตำแหน่งติดลบได้) เดินทะแยงไม่ได้ โดยเดินครั้งแรกจะไปในทิศทางนั้น 1 จุด ครั้งที่ 2 ไป 2 จุด ฯลฯ ห้ามเกิน 500 ก้าว และข้อใหญ่ต้องตอบวิธีที่สั้นที่สุดเท่านั้น

# The Great Wall

ข้อนี้นี่อ่านแล้วยาวแต่สนุกดีครับ

กำแพงเมืองจีนยาวในแนวแกน x จาก -อนันต์ – +อนันต์ ถูกเผ่าต่างๆ โจมตีเข้ามาในแต่ละวัน โดยมีการกำหนดค่าเผ่าดังนี้

– วันแรกที่เข้าโจมตี
– จำนวนครั้งที่เข้าตี
– ตำแหน่งที่เข้าตี (range)
– ความแรงของการโจมตี
– วันต่อๆ ไปที่เข้าตี (จะเข้าโจมตีทุกๆ n วัน ตามค่านี้ จนกว่าจะครบจำนวนครั้ง)
– ระยะทางที่เผ่าเคลื่อนที่ไปในการโจมตีครั้งต่อๆ ไป
– ความแรงในการโจมตีครั้งต่อๆ ไป (จะลดหรือเพิ่มตามค่านี้ตลอดทุกการโจมตี)

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

ข้อนี้กลับมาได้ใช้ class อีกแล้วครับ ผมไม่แน่ใจว่า x position มันติดลบได้มั้ย เลยเขียน class ที่รองรับตำแหน่งติดลบได้ด้วย แล้วก็ยังมีระบบ rebuild queue อีกด้วย

ตอนแรกผมเขียน generator (function `__iter__`) ไว้สร้างการเข้าตีทั้งหมด แต่ผมพบว่าเวลาจะโค้ดผมน่าจะไล่ไปดูว่าวันนี้ใครจะตีบ้าง ก็ควรจะ generate ของแต่ละวันมาน่าจะดีกว่า เลยเขียน `atk_day` ซึ่งก็ต้องบวกลบเลขกันนิดนึง

สิ่งที่พลาดนานที่สุดในข้อนี้คือ range ครับ ผมนึกว่ามันคือ [0, 2] แต่จริงๆ มันคือ [0, 2) (ตำแหน่งที่ 2 ไม่มีการเข้าตี) แล้วก็มี test case ตัวอย่างที่ผิดด้วย แต่คำตอบมันถูก ทำผมเสียเวลา debug แต่พอแก้ได้ปุ๊บก็ทำถูกได้ก่อนเค้าประกาศแก้ไขโจทย์

เช่นเดียวกัน ข้อ large ข้อนี้รันไม่ทัน นั่งเช็คๆ ดูเหมือนว่าแค่ generate attack for tribes on everyday ก็ไม่ทันกินแล้ว :3

[Learning Ruby 3] unfairRandom

*หมายเหตุ: โพสต์นี้เขียนวันที่ 5 มกราคม 2556 แต่ delay การ publish ไว้*

@winwanwon [โยนคำถาม](http://twitter.yfrog.com/z/obem2rdp)มาครับ เป็นคำถามมาจากค่าย [IT CAMP 9](http://itcamp.in.th/camp9/) ค่ายย่อย Modern Developer ถามว่า

>มีฟังก์ชัน `unfairRandom()` มาให้ ซึ่งมีโอกาส 60% ที่จะให้ผลลัพธ์เป็นตัวเลข 0 และ 40% ให้ผลลัพธ์เป็นตัวเลข 1 จงหาวิธีสร้างฟังก์ชัน `fairRandom()` ซึ่งจะต้องสุ่มเลข 0 และ 1 อย่างยุติธรรมที่สุด ( โอกาส 50-50 ) โดยห้ามใช้ฟังก์ชันสุ่มอื่นๆ ที่นอกเหนือจาก `unfairRandom()`?

ตอนแรกก็จะใช้ Python ล่ะครับ แต่เรียนรูบี้อยู่ ลองดูสักตั้ง

~~~~~~
def unfair_rand
rand < 0.6 ? 0 : 1 end ~~~~~~ ฟังก์ชั่นนี้ก็ง่ายๆ ครับ คือ `rand` จะคืนค่าทศนิยมในช่วง [0-1) ออกมา สมมุติว่าฟังก์ชั่นนี้เป็นฟังก์ชั่นสุ่มที่มีความยุติธรรมแล้วกันนะครับ ก็ถ้ามันสุ่มมาได้น้อยกว่า 0.6 ก็ตอบ 0 ถ้ามากกว่าก็ตอบ 1 เสร็จแล้วก็ต้องมาตรวจคำตอบครับ ~~~~~~~ def random_check(x,times=1000.0) arr=[] times.to_i.times do arr << x.call; end (arr.count 0)/times end ~~~~~~~ ฟังก์ชั่น `random_check` จะตรวจสอบความยุติธรรมของฟังก์ชั่นที่มีคำตอบเป็น 0 และค่าอื่นอีก 1 ค่า (ในที่นี้คือ 1) เท่านั้นนะครับ โดยใช้วิธีทำการเรียกฟังก์ชั่นสุ่มตามจำนวนครั้งที่กำหนดไว้คือ 1,000 ครั้ง แล้วหาจำนวนเหตุการณ์ที่ออก 0 ทีนี้มันมีปัญหาละครับ ใน Ruby เนี่ย การเรียก function เหมือนตัวแปร มันไม่ได้เป็นการส่งตัวฟังก์ชั่นเข้าไปเป็น argument แต่มันเป็นการส่งผลของฟังก์ชั่นนั้นเข้าไป แล้วเราจะส่ง `unfair_rand` เข้าไปยังไงดี? ผมไป Google หาคำตอบมาครับ ก็เจอกับ[คำตอบ](http://alan.dipert.org/post/339368222/passing-methods-like-blocks-in-ruby) ~~~~~~ puts random_check(method(:unfair_rand)) ~~~~~~ ทีนี้ `random_check` ก็จะได้คลาส `Method` เข้าไปครับ เพียงแค่ใช้คำสั่ง `call` เข้าไปก็สามารถเรียกใช้ `Method` นั้นๆ ได้แล้ว สำหรับผลก็เป็นไปตามคาดครับ รันปุ๊บ คำตอบออกมาทันทีว่า 0.605 ค่อนข้างใกล้เคียงกับผลที่คาดไว้คือ 0.6 ทีนี้จะแก้ความแฟร์ยังไงดี ผมก็นั่งนึกอยู่หลายวิธีครับ เช่นว่าให้สุ่มหลายๆ ครั้งแล้วนับจำนวนครั้งที่ได้ 0 หรือ 1 ถ้าน้อยกว่าค่าหนึ่งก็ให้ตอบ 0 หรือตอบ 1 แต่มันก็ยังไม่ถูกเท่าไร จนกระทั่งวิธีนึงที่อยู่ดีๆ ปิ๊งออกมา ~~~~~ def fair_rand unfair_rand == unfair_rand ? 0 : 1 end ~~~~~ ลองเช็คดูด้วย `random_check` ผลออกมาได้ 0.52096 ใกล้เคียงกับคำตอบที่ต้องการคือ 0.5 อีกแล้ว ทีนี้มานั่งนึกๆ ดูครับว่าทำไมคำตอบถึงเป็นแบบนี้... เวลาสั่ง `unfair_rand` คำตอบที่ได้คือ 0 และ 1 ใช่ไหมล่ะครับ โดยโอกาสออก 0 มี 0.6 โอกาสออก 1 มี 0.4 ทีนี้ถ้าเราสุ่มสองครั้ง เหตุการณ์ที่เลขสองตัวออกเหมือนกันจะมีสองแบบคือ ออก 0 ทั้งคู่ และออก 1 ทั้งคู่ โดยโอกาสออก 0 ทั้งคู่ก็คือ `0.6 * 0.6 = 0.36` และโอกาสที่ออก 1 ทั้งคู่คือ `0.4 * 0.4 = 0.16` โอกาสที่เลขทั้งสองตัวออกมาเหมือนกัน อาจเป็นได้ทั้ง 0 และ 1 เหมือนกัน ก็จะมีค่าเท่ากับ `0.16 + 0.36 = 0.52` นั่นเอง ตรงกับคำตอบของโปรแกรมเลย *(อันที่จริงคำตอบของโปรแกรมเมื่อสักครู่นี้ผมปรับจำนวนรอบของ `random_check` เพิ่มขึ้นครับ ถ้ารอบน้อยๆ คำตอบออกมา 0.499 ยังมีเลย)* ผมไม่ค่อยชอบปัญหาพวกนี้นะ มันเหมือนปัญหาโปรแกรม แต่มันคือปัญหาเลขที่ใช้โปรแกรมแก้ ผมไม่ใช่นักคณิตศาสตร์ แต่บางทีเจอแล้วมันก็ติดกับนั่งทำอยู่เหมือนกัน เขียนพวกแสดง text เป็นกังหัน เป็นต้นไม้ เป็นดาว อะไรพวกนี้สนุกกว่า **สิ่งที่ได้จากโปรแกรมนี้:** - การส่งฟังก์ชั่นเข้าไปในฟังก์ชั่นด้วย `method`