Algorithm in Test01

1. Question

You are given string S. Delete of the K-th letter of S costs C[K]. After deleting a letter, the costs of deleting other letters do not change. For example: for S "ab" and C=[1,3], after deleting ’a’, deletion of b will still cost 3.

You want to delete some letters from S to obtain a string without two identical letters next to each other. What is the minimul total cost of deletions to achieve such a string?

Write a function:

int solution(string &S, vector<int> &C);

Such that, giveing S and array C of integers, both of length N, returns the minimum costs of all necessary deletions.

Examples:

Given S = “abccdb” and C = [0,1,2,3,4,5], solution is 2 because you can delete first occurence of ’c’ to achieve the goal.
Given S = “aabbcc”, and C = [1,2,1,2,1,2], function should return 3.
Given S = “aaaa” and C = [3,4,5,6], the solution is 12.
Given S = “ababa” and C = [10,5,10,5,10], the function should return 0 because there is no need to delete any letter.

Extra assumptions:

string S and Array C have length equal to N;
N is an integer with the range [1…100,000];
string S consist only of lowercase letter(’a’-’z’);
each element of array C is an integer within the range [0…,1000].

2. Solution in C++

#include <iostream>
#include <string>
#include <vector>
#include <assert.h>

using namespace std;

int cost(vector<int> &C, int i, int j) {

    int biggest = C[i];
    int acc = 0;
    for (int m = i; m <= j; m++) {
        acc += C[m];
        if (C[m] > biggest) {
            biggest = C[m];
        }
    }

    return acc - biggest;
}

int solution(string &S, vector<int> &C) {
    int j = 0;
    int acc = 0;
    int length = S.size();

    for (int i = 0; i < C.size(); ++i) {
        while ((i + j + 1 < length) &&(S[i] == S[i + j + 1])) {
            j = j + 1;
        }

        if (j > 0) {
            acc += cost(C, i, i + j);
            // i = i + j + 1; Don't +1 because i will be automatically + 1
            i = i + j;
        } else {
            i = i + 1;
        }

        j = 0;
    }

    return acc;
}


int main() {
    vector<int> vect1{0, 1, 2, 3, 4, 5};
    string str1 = "abccdb";
    assert(solution(str1, vect1) ==  2);

    vector<int> vect2{1,2,1,2,1,2};
    string str2 = "aabbcc";
    assert(solution(str2, vect2) == 3);

    vector<int> vect3{3,4,5,6};
    string str3 = "aaaa";
    assert(solution(str3, vect3) == 12);

    vector<int> vect4{10,5,10,5,10};
    string str4 = "ababa";
    assert(solution(str4, vect4) == 0);
}

3. Solution in Erlang

-module(q01).
-compile([export_all]).

test() ->
    2 = solution("abccdb", [0,1,2,3,4,5]),
    4 = solution("aabbccaa", [1,2,1,2,1,2,1,2]),
    12 = solution("aaaa", [3,4,5,6]),
    0 = solution("ababa", [10,5,10,5,10]),
    passed.

merge_lists([], _) ->
    [];
merge_lists(_, []) ->
    [];
merge_lists([H1|T1], [H2|T2]) ->
    [{H1, H2} | merge_lists(T1, T2)].


solution(Str, Costs) ->
    find_cost(merge_lists(Str, Costs)).

find_cost(L) ->
    find_cost_aux(L, 0).
find_cost_aux([], Total) ->
    Total;
find_cost_aux(L, Total) ->
    {Sub, Rest} = find_sub(L),
    find_cost_aux(Rest, Total + sub_cost(Sub)).

sub_cost(L) ->
    sub_cost_aux(L, 0, 0).
sub_cost_aux([], Acc, Max) ->
    Acc - Max;
sub_cost_aux([H|T], Acc, Max) ->
    {_, X} = H,
    if
	X > Max ->
	    sub_cost_aux(T, Acc + X, X);
	true ->
	    sub_cost_aux(T, Acc + X, Max)
    end.


peek([]) ->
    [];
peek([H|_]) ->
    H.


find_sub([]) ->
    {[], []};
find_sub(L) ->
    find_sub_aux([], L).
find_sub_aux(Acc, []) ->
    {Acc, []};
find_sub_aux([], [H|T]) ->
    find_sub_aux([H], T);
find_sub_aux(Acc, [H|T]) ->
    C = peek(Acc),
    {X1, _} = C,
    {X2, _} = H,
    case X1 == X2 of
	true ->
	    find_sub_aux([H|Acc], T);
	false when length(Acc) >= 2  ->
	    {Acc, [H|T]};
	false ->
	    find_sub_aux([H], T);
	_ ->
	    io:format("case??: ~p, ~p, ~p~n", [length(Acc), Acc, [H|T]])
    end.

4. Summary

The imperative style is difficult to debug because any variable is associated with big context. So, you could not reason about if a step is correct unless you following through every steps.
For example, take a look at
```
if (j > 0) {
    acc += cost(C, i, i + j);
    // i = i + j + 1; Don't +1 because i will be automatically + 1
    i = i + j;
 } else {
    i = i + 1;
 }
```
There is no way to reason why i = i + j instead of i = i + j + 1. It just don’t have enough context to reason it.
You have to follow through the loop step by step to make sure it does what you want.

In addtion, even loop every steps doesn’t make sure it works, you have to find something called loop-invariant to proof it. That is difficult.
The functional style is easy to reason because each function limits its context to itself. Therefore, you could reason each part of the program and test them easily. And recursion is induction makes it easy to proof it actually works for all cases.