ขี้เกียจเขียน For loop ภาค 3 – ของจริง!

อารมณ์ยังค้างไม่หายจากภาค 2 ที่เขียนไปเมื่อวานนี้ วันนี้ขอเขียนอย่างต่อเนื่องอีกซักบล๊อกนึง เช่นเคยใครยังไม่ได้อ่านตอนที่แล้ว เชิญติดตามได้ที่ ขี้เกียจเขียน For loop ภาค 2 ครับ

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

แต่โดยส่วนตัวมีความประทับใจกับการแก้โจทย์ข้อนี้ได้เป็นอย่างมาก เพราะเป็นครั้งแรกที่สามารถแก้ปัญหาแข่งขัน โดยไม่มีการ mutate ค่าของตัวแปร ได้สำเร็จเป็นครั้งแรก ถือเป็นหนึ่งใน achievement จากการที่นั่งขุดนั่งเล่น functional programming concept มาซักพัก

โจทย์เต็มๆ อยู่ที่นี่ Beautiful strings ไม่แน่ใจนะครับว่าคนที่ไม่ได้เข้าร่วมการแข่งขัน จะสามารถเข้าไปดูได้หรือเปล่า

โจทย์โดยสรุปมีอยู่ว่า เค้าให้ string ที่มีตัวอักษร a-z ปนตัวใหญ่ตัวเล็กแก่เรามา ให้ assign เลข 1 – 26 ให้แก่ตัวอักษรแต่ละตัว แบบไม่สนใจตัวใหญ่ตัวเล็ก ให้ได้ผลรวมเยอะที่สุด

เช่น ABbCcc => c*26 + b*25 + a*24 = 152

อย่าลืม ตามสไตล์พวกเรา ห้ามใช้ loop และห้าม reassign ค่าให้กับตัวแปรครับ

ผมแก้ปัญหาข้อนี้ได้ด้วย code ชุดนี้

s = 'ABbCcc'
s.split('').map(&:downcase).select { |c| c =~ /[a-z]/ }
 .group_by(&:to_s).map { |_,v| v.count }.sort { |x,y| y <=> x }
 .zip((1..26).to_a.reverse).inject(0) { |a, (n,e)| a + n*e }

เห็น code ต่อกันยาวพรึดแบบนี้ อาจจะดูน่ากลัวไปซักหน่อย แต่ถ้ามาเจาะดูแต่ละขั้นตอนแล้ว ทุกอย่างเข้าใจได้ง่ายมาก

s.split('') #=> ["A", "B", "b", "C", "c", "c"]
.map(&:downcase) #=> ["a", "b", "b", "c", "c", "c"]
.select { |c| c =~ /[a-z]/ } #=> ["a", "b", "b", "c", "c", "c"]
.group_by(&:to_s) #=> {"a"=>["a"], "b"=>["b", "b"], "c"=>["c", "c", "c"]}
.map { |_,v| v.count } #=> [1, 2, 3]
.sort { |x,y| y <=> x } #=> [3, 2, 1]
.zip((1..26).to_a.reverse) #=> [[3, 26], [2, 25], [1, 24]]
.inject(0) { |a, (n,e)| a + n*e } #=> 152

มาลองดูด้วย Clojure กันบ้าง

(->> "ABbCcc"
     (re-seq #"[a-zA-Z]")
     (map clojure.string/lower-case)
     (group-by identity)
     (map #(count (last %)))
     (sort >)
     (zipmap (range 26 1 -1))
     (map #(* (key %) (val %)))
     (reduce +))

ปล. แอบไปดูเฉลยจากทาง Facebook มา พบว่าเค้าใช้วิธีเดียวกับเราเป๊ะ แต่เขียนด้วย Python

Advertisements

5 thoughts on “ขี้เกียจเขียน For loop ภาค 3 – ของจริง!

  1. teerapap.c

    สงสัยว่ะ ห้าม reassign เพื่อ mutable/immutable ยังพอเข้าใจได้ แต่ทำไมต้องห้าม for loop นะ

    มันแค่ผลักไปให้ ข้างใต้ abstraction วน loop ให้หนิ

    Reply
    1. Tap Post author

      “มันแค่ผลักไปให้ ข้างใต้ abstraction วน loop ให้หนิ” ใช่แล้ว แต่มันก็เหตุผลเดียวกับ pointer ป่ะ เราคุมเองได้ แต่เราขี้เกียจและการที่เราให้ภาษาคุมให้มันทำให้เราโฟกัสที่ปัญหาของเราจริงๆ ได้มากขึ้น

      การทำความเข้าใจ loop เราต้องทำความเข้าใจหลายอย่าง ลูปจากไหนไปไหน ช่วงความกว้างเท่าไหร่ และใน loop มี operation อะไรบ้าง แต่พอเราเอา abstract มันลงไป เหลือแค่รูปฟังก์ชัน เราก็แค่สนใจว่า input คืออะไร output คืออะไร แค่นั้น

      ในความเป็นจริงๆ เราก็ต้องสลับใช้ตามความเหมาะสมแหละ แต่สำหรับการเรียนรู้ก็ต้องใส่กฎเกณฑ์ไปหน่อย ไม่งั้นก็จะวิ่งไปเขียน loop ตลอดเวลา แล้วไม่ได้เรียนรู้อะไร

      Reply
    2. Tap Post author

      อ่อ แล้วก็ พอเราห้าม reassign variable แล้ว เราจะ loop จะถูกลดประสิทธิ์ภาพลงไปครึ่งนึง เพราะจะเหลือประโยชน์แค่สำหรับ search และ read only แต่ไม่สามารถทำการแก้ไขอะไรได้

      Reply
  2. A+

    loop อย่างเดียวไม่มีความหมายอะไรมากไปกว่าต้องทำซ้ำ แต่จะทำกี้ครั้ง หยุดเมื่อไหร่ คำนาณแต่ละรอบแล้วทำอะไร คือเป้าหมายการทำ loop ตรงนี้เองที่ทำให้ loop เข้าใจยากและอาจจะผิดพลาดได้

    ดังนั้นการใช้ loop จะต้องมี logic ว่า loop เพื่ออะไร กระจายรวมอยู่กับ logic การคำนวณ เช่น เอาค่าแต่ละครั้งมารวมกัน, เอามาใส่ array, หยุดเมื่อเจอค่าที่ต้องการ ดังนั้นทำให้การอ่าน/เขียน code ทำได้ยาก มีโอกาสผิดพลาด

    แต่ถ้าใช้ map, filter, find, drop, drop-while, take, take-while, fold, reduce, … function เหล่านี้
    ซึ่งได้ รวม loop กับ logic ของเป้าหมายของ loop ไว้ด้วยกันทำให้ไม่มีโอกาสผิดพลาด
    และจะทำให้ code อ่านง่ายขึ้น เพราะสิ่งที่เราต้องเขียนคือ logic การ คำนวณ แล้วเลือก
    ใช้ logic loop ที่ต้องการได้เลย ทำให้ logic การคำนวณ เขียนได้ง่าย หรือไม่ต้องเขียนเลย
    เพราะมีให้เลือกใช้ อยู่แล้ว เวลา test ก็ง่ายเพราะถ้า logic การคำนวณถูก ทุกอย่างก็แทบจะถูกหมด

    เช่น logic การ sum เราสามารถเลือกใช้ operator + ร่วมกับ reduce ได้เลย :
    >> reduce( + , [1,2,3,4])
    code นี้จะไม่มีโอกาสผิดเลย ถ้า operator + ทำงานได้ถูกต้อง

    Reply
  3. A+

    นี้คือ code ส่วนทำงานจริงที่ผมส่งไปครับ

    def beauty(str: String) =
    str
    .toUpperCase
    .filter(ch => ch >= ‘A’ && ch ch)
    .toList
    .map(e => e._1 -> e._2.length)
    .sortBy(e => – e._2)
    .zipWithIndex
    .map(e => (26 – e._2)*e._1._2)
    .sum

    code แทบไม่ต่างกันเลย เพราะพอเขียนแบบ functional เราจะคิดแก้ปัญหาด้วย pattern เดียวกัน

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s