clc
clear
close all

tic
disp('starting...')

%Parsing into struct
x = importdata('input.txt');
L = size(x,1);
for i=1:L
    z  = strsplit(x{i}(1:end-1),',');
    z1 = strsplit(z{1},' bags contain ');
    bags.(erase(z1{1},' ')) = {erase(z1{2}(3:end-4),' '),str2double(z1{2}(1))};
    for j=2:size(z,2)
        bags.(erase(z1{1},' '))(end+1,:) = {erase(z{j}(3:end-4),' '),str2double(z{j}(2))};
    end
end

%Part A:
parentBags  = getParentBags(bags,'shinygold');
cnt         = size(parentBags,2);
while 1
    newParents = {};
    for k=1:size(parentBags,2)
        newParents = [newParents, getParentBags(bags,parentBags{k})];
    end
    parentBags=unique([parentBags,newParents]);
    if size(parentBags,2)==cnt % No new parents found
        break
    else
        cnt=size(parentBags,2);
    end
end
disp(cnt)

%Part B
disp(getNumberOfChildBags(bags,'shinygold'))

toc
disp('Finished')

% functions
function parentBags = getParentBags(bags,childname)
    % Returns cell array with bags that can contain the child directly
    parentBags = {};
    fnames = fieldnames(bags);

    for i=1:size(fnames,1)
        z = bags.(fnames{i});
        for j=1:size(z,1)
            if strcmp(z{j,1},childname)
                parentBags{end+1}= fnames{i};
            end
        end
    end
end

function N = getNumberOfChildBags(bags,parentBag)
    N = 0;
    z = bags.(parentBag);
    if isnan(z{1,2}) % end of the line, no more bags
        return
    end
    for k=1:size(z,1)
        N = N + z{k,2} + z{k,2} * getNumberOfChildBags(bags,z{k,1});
    end
end