Câu đố: Code ngắn nhất?

Đề bài:
Biến đổi xâu S chỉ gồm kí tự A, G, T, C theo quy tắc sau:

  • A chuyển thành T và ngược lại;
  • G chuyển thành C và ngược lại:
  • đảo ngược xâu vừa tạo thành;

Ví dụ
Cho xâu AGTC biến thành TCAG, đảo ngược ta được GACT;

Hãy viết hàm sau để xử lý bài toán trên:

std::vector<std::string> geneticMicroRobots(int n, std::vector<std::string> sequences) {
    }

Đưa vào là n số lượng xâu và một vector chưa n xâu đó;
Đầu ra là một vector string tương ứng đã được biến đổi.

Đây là code ngắn nhất mà em có thể viết được (169 kí tự không kể dấu cách và xuống dòng), nhưng đó chưa phải là code tối ưu nhất. Có ai có thể viết ngắn hơn không?

auto geneticMicroRobots(int n, auto x)
{
    int i;
    while(n-i)
    {
        std::string t;
        for(int c:x[i])
            t=char(149 - c - 11*(c%4 > 1))+t;
        x[i++]=t;
    }
    return x;
}
2 Likes

2 cái này có vẻ không liên quan, đâu phải cứ ngắn nhất là tối ưu nhất :v

4 Likes

Ý em là chỉ cần giải đúng bài toán với độ dài code ngắn nhất có thể? Không cần quan tâm tới thời gian thực thi và số lệnh thực hiện ạ.

Code ngắn nhất có thể ko phải code tối ưu nhất…
Code ngắn không thể hiện trình độ của người lập trình đâu em :slight_smile:

1 Like

Đây là một câu đố vui mà anh.

‘A’ có giá trị là 65, ‘T’ là 84, có thể viết thành số tiết kiệm đi 2 ký tự.
dòng c = (...), có thể bỏ 2 dấu ngoặc đơn đi, tiết kiệm thêm 2 ký tự.

để tiết kiệm hơn nữa thì vì c chỉ có thể là A, T, G, hoặc C, như vậy khỏi cần kiểm tra c==A hay c==T mà lấy số dư c%x là biết rồi. Lập bảng

    A  T  C  G
   65 84 67 71
%2  1  0  1  1
%3  2  0  1  2
%4  1  0  3  3

như vậy c%4 mà lớn hơn 1 thì c là C hoặc G. vậy dòng c=(...), có thể viết lại thành
c = 149 - c - 11*(c%4 > 1),
từ 30 ký tự còn 19 ký tự :joy: tiết kiệm được 11 ký tự

2 Likes

Code ngắn hơn nữa:


auto geneticMicroRobots(int n, auto x)
{
    int i;
    while(n-i)
    {
        std::string t;
        for(int c:x[i])
            t=char((c=='T'||c=='A'?149:138)-c)+t;
        x[i++]=t;
    }
    return x;
}

Gồm 134 kí tự không kể dấu cách và xuống dòng.

hạng nhất là bao nhiêu ký tự?

Cám ơn anh, nhờ anh em đã có code ngắn hơn nữa :smiley:

auto geneticMicroRobots(int n, auto x)
{
    int i;
    while(n-i)
    {
        std::string t;
        for(int c:x[i])
            t=char(149 - c - 11*(c%4 > 1))+t;
        x[i++]=t;
    }
    return x;
}

Code chứa 124 kí tự

Đứng đầu là 96 kí tự anh ơi.

ghê vậy, theo hướng này tiết kiệm lắm rồi mà cũng phải hơn 100 ký tự :joy:

2 Likes

Đang phấn đấu để đánh bại 96 kí tự anh ơi :wink:

bỏ cái std:: ra khỏi std::string coi được ko? 5 ký tự :joy:

2 Likes

không được anh ơi :tired_face:

chỗ n-i gì ko cần i đâu. Xài n luôn:

while (n--)
{
... int c : x[n]
x[n] = t;
}

n là size của x thì while (n–) sẽ chạy n lần, và giá trị của n bên trong là từ size(x)-1 lùi về 0.

2 Likes

Tuyệt vời, còn 117kí tự :smile:

auto geneticMicroRobots(int n, auto x)
{
    while(n--)
    {
        std::string t;
        for(int c:x[n])
            t=char(149 - c - 11*(c%4 > 1))+t;
        x[n]=t;
    }
    return x;
}

xóa dòng int i; đi 5 ký tự :grin:

117 mà nó ép còn 96 chắc có trick gì khác :joy:

2 Likes

Xuống 117 :smile: Em cũng nghĩ giống anh? Có gì hiểm hóc ở đây?

có phải 96 ký tự mà code C++ ko hay là Python gì đó? :joy:

2 Likes

C++ anh ạ :slight_smile:

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?