Saturday, 16 May 2015

[CodeGolf] Dài nhất và ngắn nhất

Đã có code Golang, các ngôn ngữ khác lại chờ bạn đóng góp :D 

Trong cuộc sống, người ta vẫn luôn quan tâm đến những cái nhất, nhất, nhất chứ không phải thứ 2 hay thứ 10.
WorldCup cứ 4 năm diễn ra, nóng bỏng là thế, nhưng vẫn có đội đề xuất bỏ hẳn trận đá tranh giải 3-4 vì người ta xem cũng chỉ quan tâm đội được nhất thôi.

Và để được nhớ mãi, hãy là dài nhất, hoặc ngắn nhất chứ đừng là dạng vừa:

Cho một danh sách các loài, tìm con nào tên dài nhất và ngắn nhất:
In [6]: xs = ['chim', 'bo', 'ga', 'vit', 'voi', 'buom', 'than lan']
Golang: http://play.golang.org/p/b5Zka-L5dm

Python:
Lợi dụng hàm sorted:
In [19]: sorted(xs, key=len)[-1]
Out[19]: 'than lan'

In [20]: sorted(xs, key=len)[0]
Out[20]: 'bo'
Nhưng khi nghe đến đề bài đã nghĩ tới ngay hai builtin-function min và max của Python, vấn đề là không phải ai cũng biết khả năng linh hoạt của chúng:
In [7]: max(xs, key=len)
Out[7]: 'than lan'

In [8]: min(xs, key=len)
Out[8]: 'bo'
argument key nhận giá trị là một function và function này được sử dụng trong việc tính toán để sắp xếp.

Không cần benchmark cũng thấy rõ max và min (O(n)) sẽ nhanh hơn sorted, và sự thật thì đúng là thế:
In [8]: %timeit sorted(xs, key=len)[-1]
The slowest run took 8.95 times longer than the fastest. This could mean that an intermediate result is being cached
100000 loops, best of 3: 1.89 µs per loop

In [9]: %timeit max(xs, key=len)
The slowest run took 10.41 times longer than the fastest. This could mean that an intermediate result is being cached
1000000 loops, best of 3: 778 ns per loop
Vậy trong cuộc tranh đấu về độ dài này, thằn lằn đã dành danh hiệu dài nhất,
bò thì là ngắn nhất rồi, mặc dù nó có thể chia sẻ với "gà".

Hết.
hvn@familug.org

10 comments:

  1. POSIX shell:

    set -- chim bo ga vit voi buom 'than lan'
    max=$1 min=$1
    shift
    for e do
    [ "${#e}" -gt "${#max}" ] && max=$e && continue
    [ "${#e}" -lt "${#min}" ] && min=$e
    done
    printf 'Max: %s\nMin: %s\n' "$max" "$min"

    This one does not work with multi bytes characters in some shell.

    ReplyDelete
  2. Cách của m không đúng khi trong list có hai string có độ dài bằng nhau :|

    ReplyDelete
    Replies
    1. nếu yêu cầu là in ra TẤT CẢ các string có độ dài ngắn nhất thì mới cần in hết, còn bình thường chỉ in 1 cái là thỏa mãn yêu cầu bài tóan.

      Delete
    2. ví dụ liên quan đến việc này là method "index" của list trong python không in ra TẤT CẢ index của các phần tử được "index":

      In [1]: xs = [1, 2, 3, 1, 1]

      In [2]: xs.index(1)
      Out[2]: 0

      Delete
  3. #!/usr/bin/python

    names = ['chim', 'bo', 'ga', 'vit', 'voi', 'hoa hong', 'buom', 'than lan']

    # Print out the list that contains longest items.
    print [name for name in names if len(name) == len(max(names, key = len))]


    # Print out the list that contains shortest items.
    print [name for name in names if len(name) == len(min(names, key = len))]

    ReplyDelete
  4. # max
    p ['chim', 'bo', 'ga', 'vit', 'voi', 'buom', 'than lan'].group_by(&:size).max.last

    # min
    p ['chim', 'bo', 'ga', 'vit', 'voi', 'buom', 'than lan'].group_by(&:size).min.last

    ReplyDelete
    Replies
    1. anh có thể việt sub được không ạ?
      group_by nghe ko giống hàm để sort lắm, rồi .min.last nghe rất magic như trong phim HarryBotter luôn :v

      Delete
    2. - .group_by(&:size) [1] là method của Ruby trả về 1 Hash,

      nó gom các phần tử có cùng size (độ dài) vào 1 nhóm, có key là size, value là 1 array chứa các phần tử cùng size đó.

      [27] pry(main)> foo = ['chim', 'bo', 'ga', 'vit', 'voi', 'buom', 'than lan']
      => ["chim", "bo", "ga", "vit", "voi", "buom", "than lan"]

      [29] pry(main)> foo.group_by(&:size)
      => {4=>["chim", "buom"], 2=>["bo", "ga"], 3=>["vit", "voi"], 8=>["than lan"]}


      - max/min kiếm thằng nhỏ nhất/lớn nhất theo key:

      [50] pry(main)> max = foo.group_by(&:size).max
      => [8, ["than lan"]]

      [54] pry(main)> min = foo.group_by(&:size).min
      => [2, ["bo", "ga"]]

      [58] pry(main)> p min.class, max.class
      Array
      Array

      min/max return ra array có 2 phần tử, với phần tử đầu tiên là độ dài, phần tử thứ 2 là các thằng đã bị group ở trển, dùng .last để get ra

      [62] pry(main)> min.last
      => ["bo", "ga"]
      [63] pry(main)> max.last
      => ["than lan"]


      Ref:
      [1]: http://ruby-doc.org/core-2.2.2/Enumerable.html#method-i-group_by

      Delete