🔒 Locked

Counting algorithm

Started by Nahrix Nov 15, 2009 at 6:07 PM 5 replies 1.7k views

Original Post

Nov 15, 2009 at 6:07 PM

I need help devising a counting algorithm using the following rules: I have a string where each character comes lexicographically after the last, ie if the first letter is 'a', then the next letter MUST be between 'b' and 'z'. So some valid words would be: abc abd bcd bdz wxy And invalid words would be: aaa aab zab zy ca Then I want to find its integer value, where it counts up. ie: a = 1 b = 2 ... z = 26 ab = 27 ac = 28 ad = 29 ... az = 51 bc = 52 bd = 53 be = 54 Note that ab = 27 (there is no aa = 27, because aa would be an invalid word, and so bc = 52 after az, because there is no ba, or bb) I'm looking for an algorithm that can determine the numeric value of a valid word based on that counting algorithm.

Antheus

Nov 15, 2009 at 7:04 PM

Quote:
I'm looking for an algorithm that can determine the numeric value

What you describe actually *is* an algorithm (a process, a method, a sequence of steps).

Perhaps you are looking for implementation? IIRC, this is a task from one of the coding competitions.

Nahrix

Nov 15, 2009 at 7:17 PM

Yeah sorry, I meant implementation. Does it have a name?

Antheus

Nov 15, 2009 at 7:44 PM

Quote:
Original post by Nahrix
Yeah sorry, I meant implementation. Does it have a name?

I can't recall one. Basically, just implement what is described above. Try to work out the formula.

How many values are between 'abc' and any other valid 3 letter word. How many are between 'aaaaa' and any other 5 letter word? How many are between 'ab' and 'abc'?

kindjie

Nov 15, 2009 at 7:58 PM

Do you just want an answer, or a hint to find it yourself? It's sort of like counting in base 26.

PS. I did Gr.12 at Sardis Secondary. :P

Nahrix

Nov 15, 2009 at 8:58 PM

I've been working on this for a long time. I haven't learned combinatorial mathematics yet, so I have tried to solve this using recursion. This is what I have so far. It doesn't work at all, but will show how I am thinking about the problem:

(Java)

public static int mapCodeword(String word) {    String alphabet = "abcdefghijklmnopqrstuvwxyz";    int     total = 0,            alphabetLocation = alphabet.indexOf(word.charAt(0));    alphabet = alphabet.substring(alphabetLocation);    if (word.length() == 1)        return alphabetLocation + 1;    for (int i = 0; i < word.length() + alphabetLocation - 1; ++i)        total += (alphabet.length() * (word.length() - 1)) + mapCodeword(word.substring(1));    return total;}

alvaro

Nov 15, 2009 at 9:30 PM

#include <string>int table[30][30];void initialize() {  for (int i='a'; i<='z'; ++i) {    table[0][i-'a']=i-'a'+1;  }  for (int n=1; n<30; ++n) {    for (int i='a'; i<='z'; ++i) {      table[n][i-'a']=table[n-1]['z'-'a']-table[n-1][i-'a']+        (i=='a' ? 0 : table[n][i-'a'-1]);    }  }}int value(std::string const &s) {  int result = 0;  for (unsigned i=0; i<s.size(); ++i) {    result += table[s.size()-i-1][s-'a'];  }  return result;}

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.