Bài quyền Word Wrap

Ờ. Có một đoạn văn bản cho trước và một con số cho trước, cần ngắt đoạn văn bản ấy ra thành các dòng. Vị trí ngắt phải gần với con số hết mức có thể, làm sao cho mỗi dòng không dài hơn con số, và nếu có thể thì phải giữ được nguyên các từ.

text wrap

Dễ hiểu nhỉ. Vậy là tìm cách thay một số space nào đó bằng ký tự newline.

Uh đề bài dễ hiểu. Con định thiết kế như thế nào?

Dù gì thì chức năng cũng đơn giản là wrap, vậy tên cho hàm là wrap(). Nguyên mẫu của nó có thể là public String wrap(String, int).

Thế còn tên module?

StringUtilities cũng hợp lý, nhưng ngụ ý quá rộng. Wrapper thì vừa vặn hơn.

Viết kiểm thử đi con.

Con sẽ bắt đầu với những ca mà văn bản ngắn hơn con số, chủ yếu để làm lộ ra nguyên mẫu hàm.

package kata;

import org.junit.Test;

import static kata.Wrapper.wrap;
import static org.junit.Assert.assertEquals;

public class WrapperTest {
    @Test
    public void emptyString() {
        assertEquals("", wrap("", 10));
    }

    @Test
    public void stringShorterThanCol() {
        assertEquals("word", wrap("word", 10));
    }
}
package kata;

public class Wrapper {
    public static String wrap(String text, int col) {
        return text;
    }
}

Lên hình rồi, tiếp theo là gì?

Giờ con sẽ bắt wrapper phải ngắt rời từng từ một.

public class WrapperTest {
    @Test
    public void emptyString() {
        assertEquals("", wrap("", 10));
    }

    @Test
    public void stringShorterThanCol() {
        assertEquals("word", wrap("word", 10));
    }

    @Test
    public void wrapTwoWordsAfterSpace() {
        assertEquals("word\nword", wrap("word word", 6));
    }

    @Test
    public void wrapThreeWordsAfterFirstSpace() {
        assertEquals("word\nword\nword", wrap("word word word", 6));
    }
}
public class Wrapper {
    public static String wrap(String text, int col) {
        if (text.length() <= col) {
            return text;
        }
        return text.replaceAll(" ", "\n");
    }
}

Cái replaceAll là khá mưu hèn kế bẩn nhỉ.

Con sẽ lừa nó một chút.

    @Test
    public void wrapThreeWordsAfterSecondSpace() {
        assertEquals("word word\nword", wrap("word word word", 11));
    }
org.junit.ComparisonFailure:
  expected:<word word\nword>
  but was:<word\nword\nword>

…(sau rất lâu, rất nhiều mã, rất nhiều cách khác nhau, rất nhiều lần xóa rồi sửa): khó nhằn quá, mãi không ra.

Con đã viết quá nhiều mã, mà không hề có kiểm thử. Vấn đề không phải ở chỗ vấn đề nó khó. Vấn đề ở đây không hề khó, vấn đề ở đây là con đã cố vượt qua một kiểm thử SAI.

…? Con thấy nó đâu có sai?

Nó sai ngay từ khi con nhìn vào nó và không biết phải làm sao để vượt qua nó. Nó sai bởi vì nó bắt con phải vượt qua một mảng lớn trong vấn đề, nói trắng ra thì vượt qua kiểm thử này cũng bằng vượt qua toàn bộ bài toán. Con đã muốn cắn một miếng quá to. Đó không phải baby steps. Đó không phải TDD.

OK, cắn miếng nhỏ hơn, cắn cái miếng mà mình có thể hiểu được.

Vừa rồi khó ở đâu?

Chỗ thao tác tìm ra chính xác space nào cần phải được thay thế bằng newline. Uhm, con có thể quay sang thử với các văn bản không có space, cái đó chắc chắn là chỉ phải ngắt tại col là được.

public class WrapperTest {
    @Test
    public void emptyString() {
        assertEquals("", wrap("", 10));
    }

    @Test
    public void stringShorterThanCol() {
        assertEquals("word", wrap("word", 10));
    }

    @Test
    public void splitOneWord() {
        assertEquals("wo\nrd", wrap("word", 2));
    }
}
public class Wrapper {
    public static String wrap(String text, int col) {
        if (text.length() <= col)
            return text;
        return (text.substring(0, col) + "\n" + text.substring(col));
    }
}

Kiểm thử tiếp theo tương tự nhưng ngắt nhiều dòng hơn.

    @Test
    public void splitOneWordManyTimes() throws Exception {
        assertEquals("abc\ndef\nghi\nj", wrap("abcdefghij", 3));
    }

Giờ con sẽ làm gì?

Đưa một vòng lặp vào.

Nghe có vẻ dễ đấy.

Có thể triển khai vòng lặp bằng đệ quy, sẽ rất đẹp.

    public static String wrap(String text, int col) {
        if (text.length() <= col)
            return text;
        return (text.substring(0, col) + "\n" + wrap(text.substring(col), col));
    }

Mã này có tiềm năng đấy. Giờ sao?

Chắc chắn là các văn bản không có khoảng trắng là ok rồi. Giờ lân la sang các văn bản có khoảng trắng.

Cắn thật nhỏ.

Vậy thì một văn bản mà có khoảng trắng nằm ở ngay vị trí col.

    @Test
    public void wrapOnWordBoundary() throws Exception {
        assertEquals("word\nword", wrap("word word", 5));
    }
// expected:<word\nword> but was:<word \nword>

Dejavu, ha, replaceAll tiếp phỏng?

Không. Không phải không được nhưng thừa. Chỉ cần xem xem ký tự tại col có phải khoảng trắng không là được.

    public static String wrap(String text, int col) {
        if (text.length() <= col)
            return text;
        else if (text.charAt(col - 1) == ' ')
            return (text.substring(0, col - 1) + "\n" + wrap(text.substring(col), col));
        else
            return (text.substring(0, col) + "\n" + wrap(text.substring(col), col));
    }

Mã này gợi ý luôn kiểm thử tiếp theo là gì rồi ha.

Vâng, trước là space nằm ngay tại col, mã này có thể sửa một chút là đáp ứng được space nằm trước col.

    @Test
    public void wrapAfterWordBoundary() throws Exception {
        assertEquals("word\nword", wrap("word word", 6));
    }
    public static String wrap(String text, int col) {
        if (text.length() <= col)
            return text;
        int space = (text.substring(0, col).lastIndexOf(' '));
        if (space != -1)
            return (text.substring(0, space) + "\n" + wrap(text.substring(space + 1), col));
        else
            return (text.substring(0, col) + "\n" + wrap(text.substring(col), col));
    }

Ngon thật đấy, toàn bộ thuật toán cứ thế hiện ra trước mắt.

Kiểm Thử Lái” (Test Driven) là như vậy.

Để con thử thêm cú chót.

    @Test
    public void wrapWellBeforeWordBoundary() throws Exception {
        assertEquals("wor\nd\nwor\nd", wrap("word word", 3));
    }

Ôi nó cứ thế nó pass này. Xong hết luôn mất rồi.

Chưa xong đâu.

(…) ah còn trường hợp mà ngay sau col là một space.

    @Test
    public void wrapJustBeforeWordBoundary() throws Exception {
        assertEquals("word\nword", wrap("word word", 4));
    }
    public static String wrap(String text, int col) {
        if (text.length() <= col)
            return text;
        int space = (text.substring(0, col).lastIndexOf(' '));
        if (space != -1)
            return (text.substring(0, space) + "\n" + wrap(text.substring(space + 1), col));
        else if (text.charAt(col) == ' ')
            return (text.substring(0, col) + "\n" + wrap(text.substring(col + 1), col));
        else
            return (text.substring(0, col) + "\n" + wrap(text.substring(col), col));
    }

(cười) có vẻ qua hết rồi, nhưng phải làm sạch một chút.

Vâng, lặp nhiều quá.

public class Wrapper {
    private int col;

    private Wrapper(int col) {
        this.col = col;
    }

    public static String wrap(String s, int col) {
        return new Wrapper(col).wrap(s);
    }

    private String wrap(String text) {
        if (text.length() <= col)
            return text;
        int space = (text.substring(0, col).lastIndexOf(' '));
        if (space != -1)
            return breakLine(text, space, 1);
        else if (text.charAt(col) == ' ')
            return breakLine(text, col, 1);
        else
            return breakLine(text, col, 0);
    }

    private String breakLine(String text, int pos, int gap) {
        return text.substring(0, pos) + "\n" + wrap(text.substring(pos + gap), col);
    }
}

Thuật toán rất đơn giản đúng không?

Không hề khó hiểu. Nhưng lúc đầu con không thể tìm ra, bởi vì chọn sai kiểm thử.

Đúng vậy. Không chỉ cứ thế vẽ thêm kiểm thử dần dần là sẽ tìm ra cách giải, việc đánh giá kiểm thử cũng rất quan trọng.

Công nhận.


Tài nguyên tham khảo: Tôi đi làm thợ chương 62 – Lối đi tăm tối.

Nguồn: https://nguyenbinhson.com/2020/09/06/bai-quyen-word-wrap/


Hãy tham gia nhóm Học lập trình để thảo luận thêm về các vấn đề cùng quan tâm.

Leave a Reply

Your email address will not be published. Required fields are marked *

%d bloggers like this: