*ugh* Being Forced To Use Arrays

Discussion in 'Mac Programming' started by bobber205, Feb 10, 2007.

  1. macrumors 68020

    bobber205

    Joined:
    Nov 15, 2005
    Location:
    Oregon
    #1
    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?
     
  2. macrumors 65816

    Joined:
    Jan 6, 2004
    #2
    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?
     
  3. macrumors G3

    iMeowbot

    Joined:
    Aug 30, 2003
    #3
    That's along the line of the usual approach. You may find this easier if you include 0-9.
     
  4. thread starter macrumors 68020

    bobber205

    Joined:
    Nov 15, 2005
    Location:
    Oregon
    #4
    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*

    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

    Code:
    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.
     
  5. macrumors 65816

    Joined:
    Jan 6, 2004
    #5
    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.
     
  6. thread starter macrumors 68020

    bobber205

    Joined:
    Nov 15, 2005
    Location:
    Oregon
    #6
    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).
     
  7. macrumors regular

    Joined:
    Nov 23, 2006
    #7
    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...
     
  8. macrumors G3

    iMeowbot

    Joined:
    Aug 30, 2003
    #8
    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.
     
  9. macrumors 6502a

    Joined:
    Dec 4, 2006
    Location:
    Katy, Texas
    #9
    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
     
  10. thread starter macrumors 68020

    bobber205

    Joined:
    Nov 15, 2005
    Location:
    Oregon
    #10
    That's a good idea. I'll be sure to post everything here when I'm done.
     
  11. macrumors 603

    jeremy.king

    Joined:
    Jul 23, 2002
    Location:
    Fuquay Varina, NC
    #11
    Code:
    public static String convertToBase(int n, int base) {
      return Integer.toString(n, base);
    }
     
  12. macrumors 65816

    MarkCollette

    Joined:
    Mar 6, 2003
    Location:
    Calgary, Canada
    #12
    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.
     
  13. thread starter macrumors 68020

    bobber205

    Joined:
    Nov 15, 2005
    Location:
    Oregon
    #13
    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?
     
  14. macrumors 65816

    MarkCollette

    Joined:
    Mar 6, 2003
    Location:
    Calgary, Canada
    #14
    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.
     
  15. macrumors G4

    Joined:
    Jan 5, 2006
    Location:
    Redondo Beach, California
    #15
    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;
     
  16. macrumors 6502a

    Palad1

    Joined:
    Feb 24, 2004
    Location:
    London, UK
    #16
    We could easily make it a tad longer with array bounds checking ;)
     
  17. macrumors 65816

    Joined:
    Jan 6, 2004
    #17
    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
     
  18. macrumors 65816

    MarkCollette

    Joined:
    Mar 6, 2003
    Location:
    Calgary, Canada
    #18
    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.
     
  19. macrumors G4

    Joined:
    Jan 5, 2006
    Location:
    Redondo Beach, California
    #19
    "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.
     
  20. macrumors 65816

    MarkCollette

    Joined:
    Mar 6, 2003
    Location:
    Calgary, Canada
    #20
    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.
     
  21. macrumors 65816

    Joined:
    Jan 6, 2004
    #21
    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.
     
  22. macrumors G3

    iMeowbot

    Joined:
    Aug 30, 2003
    #22
    That's not a standard function, so you still need to write one and do some checking.
     
  23. macrumors 65816

    MarkCollette

    Joined:
    Mar 6, 2003
    Location:
    Calgary, Canada
    #23
    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.
     
  24. macrumors 65816

    MarkCollette

    Joined:
    Mar 6, 2003
    Location:
    Calgary, Canada
    #24
    Haven't verified if it compiles or works or whatever.

    Code:
    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();
    
     
  25. macrumors 65816

    MarkCollette

    Joined:
    Mar 6, 2003
    Location:
    Calgary, Canada
    #25
    And now, for the easier to read non-array version. Same disclaimers.

    Code:
    // 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();
    
     

Share This Page