Stacked people

Computer Science Level 4

In a grand circus event performers are about to do a stunt where each performer stands atop of the others shoulder. For practical reasons, each person must be strictly both shorter and lighter than the person below him or her.

Given the height and weight of each performers respectively in the text file, what is the maximum number of people that can be included in the stunt?

The answer is 8.

1 solution

Joe Mansley
Jan 7, 2021

Here's my MATLAB code. (The first 7 lines are just getting the data from the file into an array.) It's probably not the best solution, but it does the job.

fileID=fopen("6m45imuS.txt");
str=fscanf(fileID,'%c');
numbers=regexp(str,'\d*',"match");
numbers=str2double(convertCharsToStrings(numbers));
h=numbers(1:2:28);
w=numbers(2:2:28);
A=[h;w];

f(A)

function [maxNum]=f(A)
    maxNum=0;
    for i=1:size(A,2)
        a=A;
        for j=size(A,2):-1:1
            if ~(A(1,j)>A(1,i) && A(2,j)>A(2,i))
                a(:,j)=[];
            end
        end
        maxNum=max(maxNum,1+f(a));
    end
end

Stacked people

The answer is 8.

1 solution

0 pending reports