[exercise] character frequencies

[Matthew Fernandez]

As promised, here's this month's exercise. The goal is to take a
string as input and return a unique list of the characters in the
string in descending order of frequency. For example, the input "hello
world" should yield "lohewrd". You can take the input any way you like
(stdin, program argument, function argument) and return the output any
way you like. When two characters have the same frequency you can
return either one first.

For those for whom this task is trivial, please add your own
constraints to make the exercise harder for yourself. Some ideas: try
a language you've never used before; take the input and/or return the
output in an interesting or creative way; optimise your implementation
for memory or run time.

Post any solutions to the group. If you've got half an answer and
don't know how to finish it, feel free to ask the group.

[Patrick Coleman]

Thanks for the problem ) Posting answers to the group, yeah?

Now that I'm back from a week's holiday, I decided to try out JS's ability to do functional programming:

good = modern browsers seem to support Array.map(f) and Array.filter(f) :)

bad = there's no default support for String.count(char)

so, the chained functional one-liner:

ALPHA = "abcdefghijklmnopqrstuvwxyz"; INPUT = "Hello World";

ALPHA.split("").map(function(c) { 

  return [c, INPUT.split(new RegExp(c, "i")).length - 1]; 

}).sort(function(x, y) {

  return x[1] != y[1] ? y[1] - x[1] : x[0] - y[0]; // if equal, earlier letter first.

}).map(function(c){

  return c[1] > 0 ? c[0] : "";

}).join("")

Not sure if that's what was intended with the question, but hey. am tempted to try learning to do it in haskell, or some shortest-ruby-code if people are keen. BTW, anyone attending pycon this weekend? I'm not, but know many who are.

- Pat

[Matthew Fernandez]

Nice work, Pat. I too was planning to attempt a Haskell solution, but
don't have time this week so I resorted to C, a language I know
reasonably well. To make the problem a bit trickier I changed the aim
to just printing the most frequently occurring character, but added
the restriction that you're not allowed to use global variables or
allocate anything on the heap or stack.

#include <stdio.h>
#include <limits.h>

#if __WORDSIZE != 32
#error "This code only works on a 32-bit platform. Pass -m32 to
your compiler."
#endif

int main(int argc, char **argv) {
/* We know the name of this program is at least one character so use
* argv[0][0] to store the current character under consideration.
*/
argv[0][0] = 0;

/* We know the name of the program will be '\0' terminated so use
* argv[0][1] to store the currently known most frequent character.
*/
argv[0][1] = 0;

/* A little known fact is that argv is null terminated so use argv[2]
* (which should be 0 anyway) to store the count of the current leader in
* the high 16 bits and the count of the current candidate in the low 16
* bits. Note, this limits the maximum character count to 65535.
*/
argv[2] = 0;

if (argc != 2)
return -1;

for (argv[0][0] = CHAR_MIN; ; ++argv[0][0]) {

/* Reset the count of the current candidate. */
argv[2] = (char*)((unsigned int)argv[2] & 0xffff0000);

/* Count occurrences of this character. */
for (argc = 0; argv[1][argc] != '\0'; ++argc)
if (argv[1][argc] == argv[0][0])
++argv[2];

/* If this is greater than the current leader, make this character the
* leader.
*/
if (((unsigned int)argv[2] & 0x0000ffff) >
((unsigned int)argv[2] & 0xffff0000) >> 16) {
argv[2] = (char*)((unsigned int)argv[2] << 16);
argv[0][1] = argv[0][0];
}

/* If we're about to overflow the character type. */
if (argv[0][0] == CHAR_MAX)
break;
}

/* We can't use printf to show the results because the format string counts
* as a static global.
*/
putchar(argv[0][1]);
putchar('\n');
return 0;