PDA

View Full Version : *ugh* Being Forced To Use Arrays




bobber205
Feb 10, 2007, 07:31 PM
For my programming class, I have to make a app that converts whatever base into whatever else base.

Not hard. At all.

The only thing I'm wrestling over before I start actually coding is how I should use arrays.
I was just going to make a string and store each new 0-9 or A-Z character in there. Do you think he's wanting us to use an array to store the result?

I was thinking more along the lines of having an array that holds the characters A-Z for numbers 10-36 and having the function access that array and then return the appropriate character by a value passed to that function.

So.. what do you guys think?



darkwing
Feb 10, 2007, 09:26 PM
For my programming class, I have to make a app that converts whatever base into whatever else base.

Not hard. At all.

The only thing I'm wrestling over before I start actually coding is how I should use arrays.
I was just going to make a string and store each new 0-9 or A-Z character in there. Do you think he's wanting us to use an array to store the result?

I was thinking more along the lines of having an array that holds the characters A-Z for numbers 10-36 and having the function access that array and then return the appropriate character by a value passed to that function.

So.. what do you guys think?

I like your second approach... but when you say "whatever base into whatever other base" does that mean that you only support up to Z? Hex is A-F of course, but that's established for base 16. Would base 15 only go to E? It just seems odd.

For printing hex, for example, I like to store 0-9, A-F in an array and then I can go through a nibble at a time and print that character. Perhaps you can type up the assignment?

iMeowbot
Feb 10, 2007, 09:47 PM
I was thinking more along the lines of having an array that holds the characters A-Z for numbers 10-36 and having the function access that array and then return the appropriate character by a value passed to that function.

That's along the line of the usual approach. You may find this easier if you include 0-9.

bobber205
Feb 10, 2007, 10:21 PM
0-9 stay the same.

10-36 are A-Z.

I'm just hoping he's not wanting us to do the final answer in an array.

*launches word and waits and waits*


Purpose: For this lab you will write a program to convert numbers to different bases. For example:

FF16 = 25510 = 3778 = 111111112 = C321 = 73 36

Your program will prompt the user to enter a “number” and the base of the number. You will then ask what base to convert the number to. I expect you to handle bases 2 – 36.

Stipulations:
1) The program must continue until the user chooses to quit.
2) If the user enters a base outside the range stated above, display an error message and make them re-enter the base.
3) If the number doesn’t match the base they typed in, display an error message and have them re-enter all of the information again. (ie. The character A is invalid for a base 10 number.)
4) The number displayed to the user should be displayed in uppercase.
5) You must use functions and arrays.
6) Be sure your output is self-documenting. For example:
FF (base 16) = 255 (base 10).

Hints:
1) The maximum digit that can be in a number is one less than its base. For example: 7 is the maximum digit in a base 8 number, 1 is the maximum digit in a base 2 number.
2) Convert all numbers to base 10 first and then convert them to the desired base.

Due Date: Friday, February 23, 2007.
WARNING: Get started early!


Lol. We got this assignment a few days ago. I'll be done with it tomorrow. :D


Want to know something funny? On our first test, right before we learned about for loops, I was marked off on that test because I said


cin << name1 << name2;


was a legitimate line of code. WTF. It is and it was in our reading for that week. The reason he made it "wrong" was because he wanted us to us some gay for loop to get 4 values.

Lol.

darkwing
Feb 10, 2007, 10:39 PM
The best thing to do, imho, is to convert all numbers in any base to base 10, and go from there. This provides a good use for arrays at the end.

I'm going to assume that you know how to convert to base 10, so a good use for an array would be when going from base 10 to another number. As you move through the number with loops, division, and modulus, you can print the proper character from an array like:

static const char array[] = { '0', '1', '2', ..., '9', 'A', 'B', ... 'Z' };

then, as you convert from base 10 you have the character for each digit in this array. Then, store that in another array because you will need to print the results backwards. (usually base 10 to base x routines produce the lower digits first) Or, use a mehod that produces the larger numbers first.

Just a thought.

bobber205
Feb 10, 2007, 11:13 PM
I guess I will have to use an array to loop backwards in.

oh well. ;) It's easier than making everything a string and reversing it (like how I did this for base-2 in java).

bronxbomber92
Feb 10, 2007, 11:30 PM
How would you from base 16 to another base? I'v done base 2 to base 10, and base 10 to, well, base 2 and to roman numerals (:p)... Hexadecimal seems, different...

iMeowbot
Feb 11, 2007, 01:23 AM
How would you from base 16 to another base? I'v done base 2 to base 10, and base 10 to, well, base 2 and to roman numerals (:p)... Hexadecimal seems, different...
You already know how to do this (in decimal). Remember when you were taught that 345 is 300 + 40 + 5 ? It works the same way for any other base, the only thing that changes is the size of the number you can fit into each digit.

toddburch
Feb 11, 2007, 08:37 AM
As an FYI, when bobber205 is done with his assignment, I'll post a Ruby script I wrote about a month ago that does base to base conversions. I find it interesting to see and compare the different techniques used to tackle the same problem.

Todd

bobber205
Feb 11, 2007, 12:35 PM
That's a good idea. I'll be sure to post everything here when I'm done.

jeremy.king
Feb 13, 2007, 11:15 AM
It's easier than making everything a string and reversing it (like how I did this for base-2 in java).

public static String convertToBase(int n, int base) {
return Integer.toString(n, base);
}

MarkCollette
Feb 13, 2007, 01:48 PM
If you have to use arrays, then you could make a 2d array, where the first index is the base, and the second index is for every ASCII character, mapping to its base 10 value. Invalid values would map to a sentinel value (some arbitrary constant where 36 < SENTINEL <= 255). Hell, even if your lookup tables were 16 bit char arrays, we're only talking about 36 * 64KB memory overhead.

I personally wouldn't use a lookup table for such a trivial calculation, but it might demonstrate knowledge of arrays quite well.

bobber205
Feb 14, 2007, 12:02 AM
Is there an efficient way to convert chars to an integer? or should I just make a function that does this with 10 switch cases?

MarkCollette
Feb 14, 2007, 12:45 AM
Do you means chars like '0' through '9' ?

char typedInChar = '5';
int numericValue = typedInChar - '0';

Or 'A' through 'Z' ?

char typedInChar = 'M';
int numericValue = typedInChar - 'A' + 10;

You don't have to cast when converting from a char to an int, since the language already defines what happens. In this case, both typedInChar and 'A' are chars, so the subtraction involves no conversion, but 10 is an int, so the addition will promoted the result of the previous subtraction to an int. There's no more conversions, because the result of the addition is an int, and so is numericValue.

When converting from a char to an int, which are both signed in Java/C/C++, there is a possible sign extension. Basically chars are usually less bits than ints, so the extra bits of the int are made up by taking the single highest bit of the char and duplicating it. Now, chars are a weird beast, since they're signed numeric values, but are interpretted as characters, where sign doesn't really apply. So when calculating the integral value of these arbitrary based characters, you probably don't want funky Unicode characters to come across as negative valued integers. Luckily, you know that you max base is 36, and its max value is 35, which is a positive value, so should not present an issue for sign extension. You should probably check the input value against the max value for whichever base before you do any calculations with it. So, if it passes the test, then you're golden.

ChrisA
Feb 14, 2007, 02:09 AM
Is there an efficient way to convert chars to an integer? or should I just make a function that does this with 10 switch cases?

Some "Pseudo C". Can anyone do this any shorter? Beats doing 36 switch cases


int myfunct(char xx) {
char a[]=0123456789abcdefghi....;
if(num = strnchr(a, xx, base) ){
return (int)(num - &(xx[0]));
else
print error "invalid character"
return -1;

Palad1
Feb 14, 2007, 06:29 AM
We could easily make it a tad longer with array bounds checking ;)

darkwing
Feb 14, 2007, 07:45 AM
We could easily make it a tad longer with array bounds checking ;)

This can be solved by design. One of the advantages to what I suggested by converting things to base 10.

Mark, I thought about what you said but then decided it would be too much to type and kind of beyond the scope of the assignment to write a program (or script) to generate a source file for you. :P Besides, you should have a 3-dim array. array[base][desired_conversion_base][value] and then move through one digit at a time.

This is getting too crazy. :D

MarkCollette
Feb 14, 2007, 09:40 AM
darkwing, I envisionned it as the two stage conversion, of:

1. Convert from arbitrary input base to summable ints components, using the two dimensional array, instead of multiplication

2. Convert from int to arbitrary output base, using calculation

Since the input range of each char is limited, and thus could use arrays, but the intermediate int/long could be quite large, so the output is bounded so high that an array in stage two in not useful.

ChrisA
Feb 14, 2007, 01:28 PM
We could easily make it a tad longer with array bounds checking ;)

"strnchr" does the array bound check for us.

Notice "strnchr" vs. "strchr". It will stop scanning the string after looking at "base" characters and return a NULL if not found. The NULL is used to indicate back to the user that he typed an invalid character.

MarkCollette
Feb 14, 2007, 01:34 PM
This brings to mind another question: what is the maximum value being converted?

Let's say, as an example, that the input is in hexadecimal, and the typed in value is FFFF. Then the conversion could be done with an int. But, if the input value were FFFFFFFFFFFFFFFFFFFFFFFF, then a completely different type of solution would be required.

darkwing
Feb 14, 2007, 02:44 PM
darkwing, I envisionned it as the two stage conversion, of:

1. Convert from arbitrary input base to summable ints components, using the two dimensional array, instead of multiplication

2. Convert from int to arbitrary output base, using calculation

Since the input range of each char is limited, and thus could use arrays, but the intermediate int/long could be quite large, so the output is bounded so high that an array in stage two in not useful.

There is bounding if you take the approach of one character at a time. As you move through each "digit" in the base, you have a bound and a value as long as you apply some multiple to it. Of course this won't be as fast as having vast arrays for every possible conversion, but it is a good compromise. This is what I had in mind.

iMeowbot
Feb 14, 2007, 02:57 PM
"strnchr" does the array bound check for us.
That's not a standard function, so you still need to write one and do some checking.

MarkCollette
Feb 14, 2007, 03:03 PM
There is bounding if you take the approach of one character at a time. As you move through each "digit" in the base, you have a bound and a value as long as you apply some multiple to it. Of course this won't be as fast as having vast arrays for every possible conversion, but it is a good compromise. This is what I had in mind.

Oh, you mean having an output array like:

char[] output = new char[] { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', ... , 'Z' };

And when you calculate each output component in the output base, you then use it as an index into this table? Like if the value was 227 (base10) and the output was in base 14, so we extract out component values of: 196 + 28 + 3 (base 10) or 1x14^2 + 2x14^1 + 3x14^0. So we feed in 1,2,3 into the table, and get out '1', '2', '3'?

Or do you mean that we have:

char output[NUM_BASES][NUM_POWERS_OF_BASE][VALUES] ?

Because we'd still have to worry about the size of NUM_POWERS_OF_BASE, which would be tied to the output string length.

MarkCollette
Feb 14, 2007, 03:54 PM
Haven't verified if it compiles or works or whatever.

final int MAX_BASE = 36;
final int NUM_CHARS = 65536;
final int SENTINEL_VALUE = 255;

int convertInputToComponentValue[MAX_BASE][];
for(int base = 2; base < MAX_BASE; base++) {
// Make it large enough to take any user input char
convertInputToComponentValue[base] = new int[NUM_CHARS];
// Default every input as an invalid character
for(int i = 0; i < NUM_CHARS; i++)
convertInputToComponentValue[base][i] = SENTINEL_VALUE;
// Map the relevant parts of '0'-'9', in the current base, to their integral value
// Eg; For base 2, only {'0' -> 0, '1' -> 1} are relevant
for(int input = 0; input <= Math.min(9,base-1); input++) {
int actualCharIndex = input + '0';
convertInputToComponentValue[base][actualCharIndex] = input;
}
// Map the relevant parts of 'A'-'Z', in the current base, to their integral value
// Eg; For base 13, only {'A' -> 10, 'B' -> 11, 'C' -> 12} are relevant
for(int input = 10; input < Math.min(MAX_BASE,base); input++) {
int actualCharIndex = input - 10 + 'A';
convertInputToComponentValue[base][actualCharIndex] = input;

// Hell, why not cover lower case as well
actualCharIndex = input - 10 + 'a';
convertInputToComponentValue[base][actualCharIndex] = input;
}
}

char[] convertComponentValueToOutput = new char[MAX_BASE];
for(int i = 0; i < 10; i++)
convertComponentValueToOutput[i] = i + '0';
for(int i = 10; i < MAX_BASE; i++)
convertComponentValueToOutput[i] = i - 10 + 'A';

// Now take an inputted value, and convert each char into component values
int inputBase = 5;
String inputString = "2130";

int totalValue = 0;
for(int i = 0; i < inputString.length(); i++) {
int componentValue = convertInputToComponentValue[inputBase][inputString.charAt(i)];
if( componentValue == SENTINEL_VALUE )
System.out.println("ARGH, the hills be swarming with orcs!");
totalValue *= inputBase;
totalValue += componentValue;
}

// In this case, each componentValue was: 2,1,3,0 so totalValue was: 2,11,58,_290_

int outputBase = 7;
StringBuffer reversedOutputString = new StringBuffer();

// Now output the value, as discrete component characters
do {
int componentValue = totalValue % outputBase;
totalValue -= componentValue;
totalValue /= outputBase;

char componentChar = convertComponentValueToOutput[componentValue];
reversedOutputString.add( componentChar );
} while(totalValue != 0);

// In this case, each componentValue was: 3, 6, 5
// So the proper output is "563"
// Double-check 5x7^2 + 6x7^1 + 3x7^0 = 245 + 42 + 3 = 290

String outputString = reversedOutputString.reverse.toString();

MarkCollette
Feb 14, 2007, 04:03 PM
And now, for the easier to read non-array version. Same disclaimers.

// Now take an inputted value, and convert each char into component values
int inputBase = 5;
String inputString = "2130";

int totalValue = 0;
for(int i = 0; i < inputString.length(); i++) {
int componentValue = 0;

char curr = inputString.charAt(i);
if( curr >= '0' && curr <= '9' )
componentValue = curr - '0';
else if( curr >= 'A' && curr <= 'Z' )
componentValue = curr - 'A';
else if( curr >= 'a' && curr <= 'z' )
componentValue = curr - 'a';
else
System.out.println("ARGH, the hills be swarming with orcs!");
if( componentValue >= inputBase )
System.out.println("ARGH, the hills be swarming with orcs!");

totalValue *= inputBase;
totalValue += componentValue;
}

// In this case, each componentValue was: 2,1,3,0 so totalValue was: 2,11,58,_290_

int outputBase = 7;
StringBuffer reversedOutputString = new StringBuffer();

// Now output the value, as discrete component characters
do {
int componentValue = totalValue % outputBase;
totalValue -= componentValue;
totalValue /= outputBase;

char componentChar = componentValue + (componentValue <= 9 ? '0' : 'A');
reversedOutputString.add( componentChar );
} while(totalValue != 0);

// In this case, each componentValue was: 3, 6, 5
// So the proper output is "563"
// Double-check 5x7^2 + 6x7^1 + 3x7^0 = 245 + 42 + 3 = 290

String outputString = reversedOutputString.reverse.toString();

iMeowbot
Feb 14, 2007, 04:08 PM
Beware arithmetic against character constants. EBCDIC happens.

MarkCollette
Feb 14, 2007, 04:16 PM
Beware arithmetic against character constants. EBCDIC happens.

Luckily, not in Java :)

But yes, people should also beware of UTF-8 and UTF-16 which allow for escape characters so that the next "char" is additional information for the current "char".

darkwing
Feb 14, 2007, 05:51 PM
Oh, you mean having an output array like:

char[] output = new char[] { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', ... , 'Z' };

And when you calculate each output component in the output base, you then use it as an index into this table? Like if the value was 227 (base10) and the output was in base 14, so we extract out component values of: 196 + 28 + 3 (base 10) or 1x14^2 + 2x14^1 + 3x14^0. So we feed in 1,2,3 into the table, and get out '1', '2', '3'?

Or do you mean that we have:

char output[NUM_BASES][NUM_POWERS_OF_BASE][VALUES] ?

Because we'd still have to worry about the size of NUM_POWERS_OF_BASE, which would be tied to the output string length.

I guess I'm not making myself clear. The idea would be that he work with one digit at a time and its value is referred to in an array. But, he'd know which stage in the process he was in (^0, ^1, ^2, etc) to modify that value. This gives you an upper limit on the array size. Obviously using an array in the way I suggested would ahve lots of wasted space for lower bases.

If I wasn't in a meeting right now I'd type something up. :P

bobber205
Feb 14, 2007, 08:26 PM
I solved the problem.

Because we couldn't use strings, I was told to make my number character array very large, (200).

This let to many weird data sets in my array. I attempted to use isalnum on each entry, but Visual Studio kept crapping out with "unknown errors". :mad:

So I sent each array entry through an already made function that basically checked to see if it was 09 or A-Z. If it wasn't, I just returned a -1.

When it's time to print out the array, if the return from the test isn't -1, then it's ok. :D

Easy. (this assignment is due for over another week. lol)

darkwing
Feb 14, 2007, 09:02 PM
So post your code and we can comment on it!

bobber205
Feb 14, 2007, 09:45 PM
So post your code and we can comment on it!

I want to clean it up a bit first. ;)

Palad1
Feb 15, 2007, 04:50 AM
Well, we can convert your elegant arrayless version into an elegant array full version ;)

<code lang="pseudo_c" quality="www.thedailywtf.com">

#include "elegant.h" /* let's assume we have our int readFromBase(int base,char** string, int stringLength) elegant method defined in there*/

typedef int (*readFrombaseFunc)(int, char**, int);
typedef struct (readFromBaseFunc func,int base} converter;

converter[17] converters={
{null,null},
{null,null},
{&readFromBase,2},
{&readFromBase,3},
{&readFromBase,4},
{&readFromBase,5},
{&readFromBase,6},
{&readFromBase,7},
{&readFromBase,8},
{&readFromBase,9},
{&readFromBase,10},
{&readFromBase,11},
{&readFromBase,12},
{&readFromBase,14},
{&readFromBase,15},
{&readFromBase,16}
};
int convertWithArrays(int fromBase,char**string, int stringLength)
{
converter conv=converters[fromBase];
if(conv.func){
return (*conv.func)(conv.base,string,stringlength);
}else{
errno=1004577;
return -1;
}
}

</code>

Function pointers FTW!

darkwing
Feb 15, 2007, 08:00 AM
Function pointers FTW!

I love function pointers. I often use an array of two function pointers and index them with a boolean expression in hard realtime applications because it's a cross-platform way to add determinism.

bobber205
Feb 19, 2007, 10:30 PM
Well. My project is done at last.. I wanted to be sure I got all the docs done with it before posting it here. I do know there's some debug output but I didn't think you guys would mind.

I'm not ready to get rid of it yet.

MarkCollette
Feb 20, 2007, 02:25 PM
Minor detail, but you're not converting to base 10 as an intermediary step. You're summing the components in int variables, which means, you're converting them to binary, not base 10. True, if you then print out those ints, they will show up as base 10, but that's only because the print routines enterpret the binary ints, and display them in base 10.