Codegolf - Stars Make Stars

2022, Mar 08    
Category: codegolf
# ascii-art

Stars Make Stars

Mô tả ngắn gọn bài toán

Bài toán đơn giản chỉ là vẽ lại hình ngôi sao 6 cánh. Dưới đây là các thông số của ngôi sao 6 cánh:

star

properties

Phân tích bài toán

Ta định nghĩa hàm draw(N) để vẽ ngôi sao 6 cánh có độ cao tầng 1 là N:

def draw(n):
    # trả về 1 string chứa ngôi sao

print(draw(N))

Từ bảng thông số của ngôi sao 6 cánh, xét các trường hợp $N > 1$, ta thấy:

  • Giá trị Tri W = 3 * (2 * N - 1) = 6 * N - 3. Mặt khác Init Spc + 1 = Tri H, Init Spc + Tri H = Tri W, suy ra Init Spc = (6 * N - 3 - 1) / 2 = 3 * N - 2, Tri H = 3 * N - 1.

  • Số kí tự * ở mỗi dòng là số lẻ. Các kí tự * liền nhau và được căn giữa.

  • “Tầng 1” gồm $N$ hàng, số kí tự * ở mỗi dòng tăng dần từ 1.

  • “Tầng 2” gồm $2 * N - 1$ hàng, số kí tự * giảm dần từ 6 * N - 3 xuống 6 * N - 3 - 2 * (N - 1) = 4 * N - 1, rồi lại tăng từ 4 * N - 1 lên 6 * N - 3.

  • “Tầng 3” gồm $N$ hàng, ngược với tầng 1.

Với $N = 1$, ta dễ thấy Init Spc = 3 * N - 1 và Tri H = 3 * N, tức là 2 giá trị này cộng thêm 1 so với trường hợp $N > 1$.

Solution 1. Vẽ từng tầng

Trường hợp $N = 1$ ta vẽ riêng. Ta sẽ vẽ các trường hợp $N > 1$ trở đi.

Đối với tầng 1:

for i in range(N):
    res += ("*"*(2*i+1)).center(6*N-3)+"\n"

Để căn giữa 1 xâu, ta có nhiều cách làm. Một cách tường minh, ta có method .center() để căn giữa.

Với phiên bản Python 3.6 trở lên, ta có thể dùng f-string:

for i in range(N):
    res += f"{'*'*(2*i+1):^{6*N-3}}\n"

Ta cũng có thể dùng .format(), tuy nhiên đây là một bài codegolf nên ta ưu tiên code càng ngắn càng tốt.

Tầng 3 ta cũng làm tương tự, chỉ cần đổi chiều từ tăng thành giảm là được.

Ta tiến hành xử lý tầng 2. Số kí tự * giảm rồi lại tăng, rất giống 1 hàm trong tự nhiên, đó chính là hàm giá trị tuyệt đối.

img1

Tầng 3 gồm 2 * N - 1 hàng, ta tạo 1 biến i chạy từ - (N - 1) đến + (N - 1).

  • i = N - 1 thì số kí tự * là 6 * N - 3
  • i = 0 thì số kí tự * là 4 * N - 1

Suy ra số kí tự * ở dòng i bất kì là 4 * N - 1 + 2 * abs(i)

Ta có tầng 2 được vẽ như sau:

for i in range(-N+1, N):
    res += f"{'*'*(4*N-1+2*abs(i)):^{6*N-3}}\n"

Ta có đoạn code hoàn chỉnh version 1 như sau (golfed version - Try it online!):

def draw(N):
    if N == 1:
        return "  *\n*****\n*****\n  *"
    res = ""
    for i in range(N):
        res += f"{'*'*(2*i+1):^{6*N-3}}\n"
    
    for i in range(-N+1, N):
        res += f"{'*'*(4*N-1+2*abs(i)):^{6*N-3}}\n"

    for i in range(N):
        res += f"{'*'*(2*(N-i)-1):^{6*N-3}}\n"

    return res

Thành quả với N = 3:

       *       
      ***      
     *****     
***************
 ************* 
  ***********  
 ************* 
***************
     *****     
      ***      
       *

Ta mong muốn giảm thiểu số vòng for. Câu hỏi đặt ra là, ta có thể ghép các vòng for vào với nhau được hay không?

Nhận thấy hình ngôi sao 6 cánh này đối xứng ngang, vòng for thứ 2 có sử dụng hàm giá trị tuyệt đối nên ta sẽ thử áp dụng với miền của i chạy từ - (2 * N - 1) đến (2 * N - 1) xem sao.

Vì miền của i trong vòng for thứ 2 là [-(N-1), (N-1)] nên ta mong muốn “kết nối” miền của i trong 2 vòng for đầu tiên thành 1 miền liên tục. Trước hết ta đổi miền chạy vòng for đầu tiên sang [-2*N+1, -N]. Giá trị 2 * i + 1 ở miền cũ sẽ biến thành 2 * (2 * N - abs(i)) + 1 = 4*N + 1 - 2*abs(i) ở miền mới.

Tương tự, ta đổi miền ở vòng for thứ 3. Ta có đoạn code version 1.1:

def draw(N):
    if N == 1:
        return "  *\n*****\n*****\n  *"
    res = ""
    for i in range(-2*N+1, -N+1):
        res += f"{'*'*(4*N-1-2*abs(i)):^{6*N-3}}\n"
    
    for i in range(-N+1, N):
        res += f"{'*'*(4*N-1+2*abs(i)):^{6*N-3}}\n"

    for i in range(N, 2*N):
        res += f"{'*'*(4*N-1-2*abs(i)):^{6*N-3}}\n"  # abs(i) == i

    return res

Kết quả trông cũng khá đẹp đấy chứ nhỉ? Độ rộng của * là

hay

Trong codegolf, hàm chỉ trả về -1 hoặc +1 cũng có thể được thay bằng hàm (-1)**boolean.

Ta có đoạn code version 2 (Try it online!):

def draw(N):
    if N == 1:
        return "  *\n*****\n*****\n  *"
    res = ""
    for i in range(-2*N+1, 2*N):
        res += f"{'*'*(4*N-1-abs(i)*2*(-1)**(-N<i<N)):^{6*N-3}}\n"

    return res

và version 2.1 nếu bỏ biến res đi (Try it online!):

def draw(N):
    return
        "  *\n*****\n*****\n  *" if N == 1
        else "\n".join(
            f"{'*'*(4*N-1-abs(i)*2*(-1)**(-N<i<N)):^{6*N-3}}"
            for i in range(-2*N+1, 2*N)
        )
Twitter Facebook