Letter Frequency Histogram
Autumn Tournament (2011)
Submission name: frequency.cpp
Problem summary
Read text until the terminator @. Count Latin letters without distinguishing uppercase and lowercase. Print a vertical histogram: each column contains copies of its uppercase letter, above a separator of 26 hyphens and the alphabet.
Input
Any number of text lines ending at the first @.
Output
Histogram rows from highest to lowest, followed by -------------------------- and ABCDEFGHIJKLMNOPQRSTUVWXYZ. Column 1 corresponds to A, column 26 to Z; empty cells are spaces.
Constraints
The source does not specify a text-length bound. Process the text incrementally until @; ignore non-Latin-letter characters.
Worked example
Original statement sample, with whitespace restored where PDF extraction merges adjacent numbers.
Input
Tova e samo 1 malak PRIMER. VNIMAVAJTE!@
Output
A A A M A E M V A E I M O R T V A E IJKLMNOP RST V -------------------------- ABCDEFGHIJKLMNOPQRSTUVWXYZ
Solution analysis
- Use a 26-element frequency array. Read every character, including whitespace, with cin.get. Convert ASCII uppercase and lowercase letters to indices 0 through 25; ignore punctuation, digits and line breaks. Stop before counting @.
- Let height be the maximum frequency. For each level from height down to one, put letter A+i in column i if its count is at least that level; otherwise put a space. Removing trailing spaces does not change any column alignment.
- In the sample A occurs six times, M four times, E and V three times, and I, O, R and T twice. The highest two rows therefore contain only A. Lower rows gradually introduce the other letters. Finally print the separator and alphabet.
Why it works
Every input letter increments exactly its case-insensitive column. Column i is filled on precisely frequency[i] levels, so its height equals the required number of occurrences. Printing levels in descending order aligns the histogram above its labels.
Watch out. Do not use operator>> for a single whitespace-delimited word: the text can span lines. Do not count @ or punctuation. Preserve leading and internal spaces in histogram rows. No letters means only the separator and alphabet are printed.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<array>
#include<algorithm>
#include<string>
using namespace std;
int main(){
array<long long,26>frequency{};
char symbol;
while(cin.get(symbol)&&symbol!='@'){
if(symbol>='a'&&symbol<='z'){
++frequency[symbol-'a'];
}
else if(symbol>='A'&&symbol<='Z'){
++frequency[symbol-'A'];
}
}
long long height=*max_element(frequency.begin(),frequency.end());
for(long long level=height;level>=1;--level){
string row(26,' ');
for(int i=0;i<26;++i){
if(frequency[i]>=level){
row[i]=static_cast<char>('A'+i);
}
}
// Omit insignificant trailing spaces, preserving all columns.
while(!row.empty()&&row.back()==' '){
row.pop_back();
}
cout<<row<<'\n';
}
cout<<"--------------------------\nABCDEFGHIJKLMNOPQRSTUVWXYZ\n";
}