BoomBleBee: Probleme programare dinamică & recursivitate (2)

#5. Generarea tuturor parantezelor

Dându-se un număr n, să se genereze toate combinațiile de paranteze bine-formate. Adică: fiecare paranteză deschisă formează un cuplu cu o paranteză închisă și cuplul începe întotdeauna cu paranteza deschisă.

Exemplu: Input: n = 3

Output: ["((()))","(()())","(())()","()(())","()()()"]

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        // all strings will have 2*n length and are built from scratch
        generateParenthesis(2*n, n, "", result);
        return result;
    }

    private void generateParenthesis(int n, int initialN, String generated, List<String> result) {
        if (n == 1) {
            // in the last call we can only use )
            if (isValid(generated + ')', true, initialN)) {
                result.add(generated + ')');
            }
            return;
        }

        // recurse only if we are on the good path with the partial result
        if (isValid(generated + '(', false, initialN)) {
            generateParenthesis(n-1, initialN, generated + '(', result);
        }
        if (isValid(generated + ')', false, initialN)) {
            generateParenthesis(n-1, initialN, generated + ')', result);
        }        
    }

    private boolean isValid(String str, boolean checkFinal, int n) {
        int left = 0, right = 0;
        for (char c : str.toCharArray()) {
            if (c == '(') {
                left++;
            } else {
                right++;
                if (right > left) {
                    return false;
                }
            }
        }
        return checkFinal ? 
            left == right : // a well-formed string has the same number of ( and )
            left <= n;      // a partial result should not have ( count more than n
    }
}

#6. Asezarea unor cutii intr-o stiva

Avem N cutii, fiecare cutie fiind reprezentata in 3 dimensiuni (width, length, height). Ele se pot stivui astfel incat cutia aflata deasupra altei cutii va avea w2 <= w1, l2 <= l1 si h2 <= h1. Nu toate cutiile se pot stivui, dar ele se pot roti astfel incat o inaltime sa devina lungime etc. Care e inaltimea celei mai inalte stive posibile?

Nota: la prima vedere, problema este o variatie la problema Maximum subarray (aflarea sumei maxime a unui subsir dintr-un sir), la care se adauga cateva constrangeri. Am implementat urmatorii pasi:

transformarea obiectelor-cutie prin rotire astfel incat inaltimea sa fie dimensiunea cu valoarea cea mai mare dintre cele 3D (greedy)
sortarea cutiilor dupa inaltime, urmata de celelalte doua dimensiuni, descrescator (*)
aplicarea algoritmului pt Max subarray mentionat anterior, cu adaptarea constrangerilor pentru cutii (programare dinamica)

(*) neasteptat de tricky este sortarea cutiilor. Nu toate cutiile sunt ordonabile, iar un algoritm eficient precum Mergesort greseste pentru anumite cazuri. Asa ca am optat pentru un Bubblesort cu numar maxim de comparatii intre elemente, pentru a forta o relatie de ordonare intre oricare 2 elemente din sirul de cutii. (S-a dovedit si ca doar Bubblesort-ul cu 2 for-uri va functiona corect pentru toate testele!)

Nota: nu e extrem de eficient, dar e corect. Complexitate: timp O(N^2) determinata in principal de Bubblesort, spatiu O(N) pt un array suplimentar.

class Solution {
    public int maxHeight(int[][] boxes) {
        // boxes[i] = (w, len, h)

        rotateObjectsMaxHeight(boxes);

        if (boxes.length == 1) {
            return boxes[0][2];
        }

        sortByMaxHeightAndWLDesc(boxes);

        int maxSumHeight = boxes[0][2];
        int largest[] = new int[boxes.length];
        largest[0] = boxes[0][2];
        int lastAddedIndex = 0; // index of the last added box to obtain largest so far

        for (int i=1; i<boxes.length; i++) {
            if (canPlace(boxes[lastAddedIndex], boxes[i])) {
                largest[i] = largest[lastAddedIndex] + boxes[i][2];
            } else {
                largest[i] = boxes[i][2];
                // try to put current box on any previous box if it gives profit
                for (int j=0; j<i; j++) {
                    if (j != lastAddedIndex) {
                        if (canPlace(boxes[j], boxes[i]) && largest[i] < largest[j] + boxes[i][2]) {
                            largest[i] = largest[j] + boxes[i][2];
                        }
                    }
                }
            }

            if (maxSumHeight < largest[i]) {
                maxSumHeight = largest[i];
                lastAddedIndex = i;
            }
        }

        return maxSumHeight;
    }

    private void rotateObjectsMaxHeight(int[][] boxes) {
        // h = max(w, len, h) => swap h with the max
        for (int i=0; i<boxes.length; i++) {
            int max = Math.max(boxes[i][0], Math.max(boxes[i][1], boxes[i][2]));
            if (max != boxes[i][2]) {
                int aux = boxes[i][2]; // h
                boxes[i][2] = max;
                if (max == boxes[i][0]) { // w
                    boxes[i][0] = aux;
                } else if (max == boxes[i][1]) { // l
                    boxes[i][1] = aux;
                }
            }
        }
    }

    private boolean canPlace(int[] boxUnder, int[] boxTop) {
        boolean firstCheck = boxUnder[0] >= boxTop[0] && boxUnder[1] >= boxTop[1];
        boolean rotateCheck = boxUnder[0] >= boxTop[1] && boxUnder[1] >= boxTop[0];
        return firstCheck || rotateCheck;
    }

    private boolean equals(int[] boxUnder, int[] boxTop) {
        boolean firstCheck = boxUnder[0] == boxTop[0] && boxUnder[1] == boxTop[1];
        boolean rotateCheck = boxUnder[0] == boxTop[1] && boxUnder[1] == boxTop[0];
        return firstCheck || rotateCheck;
    }

    public void sortByMaxHeightAndWLDesc(int[][] boxes) {
        // max complexity bubble sort needed because we need to make as many comparisons as possible
        for (int i=0; i<boxes.length - 1; i++) {
            for (int j=i+1; j<boxes.length; j++) {
                boolean rightHeightHigher = boxes[i][2] < boxes[j][2];
                boolean equalHeightsWithRightBigger = boxes[i][2] == boxes[j][2] && 
                        canPlace(boxes[j], boxes[i]) &&
                        !equals(boxes[j], boxes[i]);
                if (rightHeightHigher || equalHeightsWithRightBigger) {
                    int[] aux = boxes[i];
                    boxes[i] = boxes[j];
                    boxes[j] = aux;
                }
            }
        }
    }
}

#7. In cate moduri se pot pune paranteze unei expresii booleene

Se da o expresie formata din valorile 0, 1 (false, true) si operatorii binari &, | si ^. In cate moduri se pot pune paranteze astfel incat evaluarea expresiei sa fie result? Parantezele de genul (( )) nu sunt valide.

Exemplu: countEval('1 & 0 | 1', true) = 2, posibilitatile sunt 1 & (0 | 1) si (1 & 0) | 1.

Rezolvare: cateva observatii:

cazuri de baza: countEval(Strings.EMPTY, result) = 0 si countEval(str, result) ~ str.equals(result) adica 0 sau 1, cand str are un singur caracter.
valorile 0 si 1 vor sta intotdeauna pe pozitiile 0, 2, 4, ... n , pe cand operatorii binari vor sta intotdeauna pe pozitiile 1, 3, 5, ... n-1

asta duce la un for (int i=1; i<str.length(); i+=2) in care sa calculam subproblemele

daca ne situam pe pozitia unui operator (i), putem calcula recursiv leftCountTrue = countEval(str.substring(0, i), true) si rightCountTrue = countEval(str.substring(i+1), true). Similar si leftCountFalse, rightCountFalse. Toate variabilele ne trebuie pentru ca la un '|', de exemplu, evaluarea uneia din parti poate fi si false, iar rezultatul final sa fie true.
se calculeaza totalCount = toate modurile posibile de a obtine orice rezultat al evaluarii, care consta din toate modurile de a aranja parantezele in partea stanga * toate modurile de a aranja parantezele in partea dreapta

totalCount = (leftTrue + leftFalse) * (rightTrue + rightFalse);

calculam totalCountTrue in functie de operatorul de pe pozitia i:

'&' --> totalCountTrue = leftCountTrue * rightCountTrue
'|' --> totalCountTrue = leftCountTrue * rightCountTrue + leftCountTrue * rightCountFalse + leftCountFalse * rightCountTrue;
'^' --> totalCountTrue = leftCountTrue * rightCountFalse + leftCountFalse * rightCountTrue;

in functie de rezultatul dorit, solutia subproblemei curente este totalCountTrue sau totalCount - totalCountTrue. Ea se adauga la variabila pentru pastrarea tuturor modurilor.

Optimizare: unele apeluri ale metodei countEval se repeta. Putem pastra un tabel unde stocam rezultatul apelului curent pe care sa-l obtinem rapid, daca exista, inainte de intrarea in for.

if (memo.containsKey(result + str)) return memo.get(result+str);
memo.put(result+str, countWays);

BoomBleBee

17 iulie 2024

Probleme programare dinamică & recursivitate (2)

Niciun comentariu: