% Avaliação do terceiro guião - MPEI 21/22
% Marcus Peterson Matos das Neves Filho - 101080
% Ana Luisa Silva Loureiro - 104063

% Questão 03
% Letra B.
% C A S O FIM
mtz = [0 1/3 0 1/3 0;
       1/2 0 1/3 0 0;
       0 1/3 0 1/3 0;
       1/2 0 1/3 0 0;
       0 1/3 1/3 1/3 0];

letras = 'CASO'; palavras = cell(1e5, 1);

% 1 = C, 2 = A, 3 = S, 4 = O, 5 = 0;
%situ = mtz
%situ = estadoInicial*mtz
for i = 1:1e5
    rand = randi(4);
    if rand == 1
        situ = mtz*[1; 0; 0; 0; 0];
    elseif rand == 2
        situ = mtz*[0; 1; 0; 0; 0];
    elseif rand == 3
        situ = mtz*[0; 0; 1; 0; 0];
    else
        situ = mtz*[0; 0; 0; 1; 0];
    end
    state = crawl(situ, 1, 5);
    temp = state(1:end-1);
    palavras{i, 1} = letras(temp);
end

% Random walk on the Markov chain
% Inputs:
% H - state transition matrix
% first - initial state
% last - terminal or absorving state
function state = crawl(H, first, last)
     % the sequence of states will be saved in the vector "state"
     % initially, the vector contains only the initial state:
     state = (first);
     % keep moving from state to state until state "last" is reached:
     while (1)
          state(end+1) = nextState(H, state(end));
          if (state(end) == last)
              break;
          end
     end
end

% Returning the next state
% Inputs:
% H - state transition matrix
% currentState - current state
function state = nextState(H, currentState)
     % find the probabilities of reaching all states starting at the current one:
     probVector = H(:,currentState)';  % probVector is a row vector 
     n = length(probVector);  %n is the number of states
     % generate the next state randomly according to probabilities probVector:
     state = discrete_rnd(1:n, probVector);
end

% Generate randomly the next state.
% Inputs:
% states = vector with state values
% probVector = probability vector 
function state = discrete_rnd(states, probVector)
     U=rand();
     i = 1 + sum(U > cumsum(probVector));
     state = states(i);
end