  function C4Check()
% Tabulates what happens when RomNumVal() is applied to every valid
% Roman Numeral.

clc
[RNsort,idx] = RomanPhoneBook();
% RNsort is a 3999-by-1 cell array of alphabetized Roman numerals.
% idx is a 3999-by-1 integer array with the property that idx(k)
%   is the numerical value of the Roman numeral RNsort{k}.
nBad = 0;
for k=1:length(idx)
    s = RNsort{k};
    Value = idx(k);
    otherValue = RomNumVal(s);
    if otherValue ~= Value
        fprintf('%s\n',s)
        nBad = nBad+1;
    end        
end
fprintf('\n\nNumber of valid Roman Numerals that are declared invalid = %1d\n',nBad)
Val_of_IXL = RomNumVal('IXL')
Val_of_XCM = RomNumVal('XCM')
Val_of_XXIXX = RomNumVal('XXIXX')

  function x = RomNumVal(s)
% Roman Numeral Checker
% s is a string. If it encodes a valid Roman numeral, then
% x is is numerical value.

if Rule1(s) && Rule2(s) && Rule3(s)
% if Rule1(s) && Rule2(s) && Rule3Mod(s)   % Closes some loopholes
   % valueVector houses the value of each Roman Numeral
   RN = [1 5 10 50 100 500 1000];
   valueVector(1) = RN(Occur(s(1),'IVXLCDM'));
   OK = 1;
   k=1;
   while OK && k<length(s)
      valueVector(k+1) = RN(Occur(s(k+1),'IVXLCDM'));
      if valueVector(k)<valueVector(k+1)
         % The next numeral has greater value, so check for validity and
         % adjust the value of the current numeral...
         OK = Occur(s(k:k+1),'IV IX XL XC CD CM');
         if OK
            valueVector(k) = -valueVector(k);
         end
      end 
      k = k+1;
   end
   if OK
      % The string s is a legal Roman Numeral...
      x = sum(valueVector);
   else
      % The string s is not a legal Roman Numeral...
      x = 0;
   end   
else 
   % The string s is not a legal Roman Numeral...
   x = 0;
end


  function alfa = Rule1(s)
% alfa is zero if length(s) == 0 or if s contains a character that is
% not in 'IVXLCDM'.
n = length(s);
if n==0
    alfa = 0;
else
    k = 1;
    while k<=n && length(Occur(s(k),'IVXLCDM'))==1
       k = k+1;
    end
    alfa = k==n+1;
end

   function alfa = Rule2(s)
 % alfa is true if and  only if the string s has at most one 'V', at most
 % one 'L', and at most one 'D'.
 alfa = length(Occur('V',s))<=1 && length(Occur('L',s))<=1 && length(Occur('D',s))<=1;
 
   function alfa = Rule3(s)
 % alfa is true if and  only if the string s has at most three 'I', at most
 % three 'X', at most three 'C', and at most three 'M'
 alfa = length(Occur('I',s))<=3 && length(Occur('X',s))<=3 && length(Occur('C',s))<=3  && length(Occur('M',s))<=3;
 
   function alfa = Rule3Mod(s)
 % Let z be any of the characters 'I', 'X', 'C', or 'D'
 % alfa is true if and only if the string s has either three or less z's or
 % four z's with exactly three being contiguous.
 I_ok = length(Occur('I',s))<=3 || (length(Occur('I',s))==4 && length(Occur('III',s))==1);
 X_ok = length(Occur('X',s))<=3 || (length(Occur('X',s))==4 && length(Occur('XXX',s))==1); 
 C_ok = length(Occur('C',s))<=3 || (length(Occur('C',s))==4 && length(Occur('CCC',s))==1);
 M_ok = length(Occur('M',s))<=3 || (length(Occur('M',s))==4 && length(Occur('MMM',s))==1);
 alfa = I_ok && X_ok && C_ok && M_ok;

  function i = Occur(s,t)
% s is a character and t is a string. i is a vector of subscripts
% with the property that strcmp(s,t(i(j)) is true for j=1:length(i)
% Thus the value of Occur('a','saadhjwad') is [2 3 8].
% If s does not Occur in t, then i is the empty vector.
i = [];
n = length(s);
m = length(t);
for k=1:m-n+1
    if strcmp(s,t(k:k+n-1))
        i  = [i k];
    end
end

function [RNsort,idx] = RomanPhoneBook()
% RNsort is a 3999-by-1 cell array of alphabetized Roman numerals.
% idx is a 3999-by-1 integer array with the property that idx(k)
%   is the numerical value of the Roman numeral RNsort{k}.

% Cell arrays for the 1's, 10's, 100's, and 1000's place...
C1 = {'', 'I', 'II', 'III', 'IV', 'V', 'VI', 'VII', 'VIII', 'IX'};
C2 = {'', 'X', 'XX', 'XXX', 'XL', 'L', 'LX', 'LXX', 'LXXX', 'XC'};
C3 = {'', 'C', 'CC', 'CCC', 'CD', 'D', 'DC', 'DCC', 'DCCC', 'CM'};
C4 = {'', 'M', 'MM', 'MMM'};

% Generate the unsorted cell array of Roman numeral strings...
RN = cell(3999,1);
k = 0;
for i4=1:4
    Thousands = C4{i4};         % Choose a thousands "digit"
    for i3 = 1:10
        Hundreds = C3{i3};      % Choose a hundreds "digit"
        for i2 = 1:10
            Tens = C2{i2};      % Choose a tens "digit"
            for i1 = 1:10
                Ones = C1{i1};  % Choose a ones "digit"
                if k > 0
                    RN{k} = [Thousands Hundreds Tens Ones];
                end
                k = k+1;
            end
        end
    end
end
% Now alphabetize...
[RNsort,idx] = sort(RN);

 
   

