UVA: 706 Programming Challenges (Skiena & Revilla) Volume-1

UVA:706:LC DISPLAY

Background- This is very interesting problem to code the LC Display of numbers but I had tough time match the judges requirement. Though my implementation has 0.028 sec timing and 848 rank but still I feel there is lot of scope to optimize this again interestingly people out there who managed to get this done in 0.000 sec. I am still thinking how can it be rendered in O(1) timing when it desired to render it linearly. Any way this is still a matter of work for me to figure out the way to solve it in just no time.

C++ Implementation - 

#include <iostream>
#include <string>
#include <stdio.h>
using namespace std;
char number[20];

// string table[s][n][l];
string table[10][10][5] = {
{{" - ", "| |", "   ", "| |", " - "},{
"   ", "  |", "   ", "  |", "   "},{
" - ", "  |", " - ", "|  ", " - "},{
" - ", "  |", " - ", "  |", " - "},{
"   ", "| |", " - ", "  |", "   "},{
" - ", "|  ", " - ", "  |", " - "},{
" - ", "|  ", " - ", "| |", " - "},{
" - ", "  |", "   ", "  |", "   "},{
" - ", "| |", " - ", "| |", " - "},{
" - ", "| |", " - ", "  |", " - "}
},{{
" -- ", "|  |", "    ", "|  |", " -- "},{
"    ", "   |", "    ", "   |", "    "},{
" -- ", "   |", " -- ", "|   ", " -- "},{
" -- ", "   |", " -- ", "   |", " -- "},{
"    ", "|  |", " -- ", "   |", "    "},{
" -- ", "|   ", " -- ", "   |", " -- "},{
" -- ", "|   ", " -- ", "|  |", " -- "},{
" -- ", "   |", "    ", "   |", "    "},{
" -- ", "|  |", " -- ", "|  |", " -- "},{
" -- ", "|  |", " -- ", "   |", " -- "}
},{{
" --- ", "|   |", "     ", "|   |", " --- "},{
"     ", "    |", "     ", "    |", "     "},{
" --- ", "    |", " --- ", "|    ", " --- "},{
" --- ", "    |", " --- ", "    |", " --- "},{
"     ", "|   |", " --- ", "    |", "     "},{
" --- ", "|    ", " --- ", "    |", " --- "},{
" --- ", "|    ", " --- ", "|   |", " --- "},{
" --- ", "    |", "     ", "    |", "     "},{
" --- ", "|   |", " --- ", "|   |", " --- "},{
" --- ", "|   |", " --- ", "    |", " --- "}
},{{
" ---- ", "|    |", "      ", "|    |", " ---- "},{
"      ", "     |", "      ", "     |", "      "},{
" ---- ", "     |", " ---- ", "|     ", " ---- "},{
" ---- ", "     |", " ---- ", "     |", " ---- "},{
"      ", "|    |", " ---- ", "     |", "      "},{
" ---- ", "|     ", " ---- ", "     |", " ---- "},{
" ---- ", "|     ", " ---- ", "|    |", " ---- "},{
" ---- ", "     |", "      ", "     |", "      "},{
" ---- ", "|    |", " ---- ", "|    |", " ---- "},{
" ---- ", "|    |", " ---- ", "     |", " ---- "}
},{{
" ----- ", "|     |", "       ", "|     |", " ----- "},{
"       ", "      |", "       ", "      |", "       "},{
" ----- ", "      |", " ----- ", "|      ", " ----- "},{
" ----- ", "      |", " ----- ", "      |", " ----- "},{
"       ", "|     |", " ----- ", "      |", "       "},{
" ----- ", "|      ", " ----- ", "      |", " ----- "},{
" ----- ", "|      ", " ----- ", "|     |", " ----- "},{
" ----- ", "      |", "       ", "      |", "       "},{
" ----- ", "|     |", " ----- ", "|     |", " ----- "},{
" ----- ", "|     |", " ----- ", "      |", " ----- "}
},{{
" ------ ", "|      |", "        ", "|      |", " ------ "},{
"        ", "       |", "        ", "       |", "        "},{
" ------ ", "       |", " ------ ", "|       ", " ------ "},{
" ------ ", "       |", " ------ ", "       |", " ------ "},{
"        ", "|      |", " ------ ", "       |", "        "},{
" ------ ", "|       ", " ------ ", "       |", " ------ "},{
" ------ ", "|       ", " ------ ", "|      |", " ------ "},{
" ------ ", "       |", "        ", "       |", "        "},{
" ------ ", "|      |", " ------ ", "|      |", " ------ "},{
" ------ ", "|      |", " ------ ", "       |", " ------ "}
},{{
" ------- ", "|       |", "         ", "|       |", " ------- "},{
"         ", "        |", "         ", "        |", "         "},{
" ------- ", "        |", " ------- ", "|        ", " ------- "},{
" ------- ", "        |", " ------- ", "        |", " ------- "},{
"         ", "|       |", " ------- ", "        |", "         "},{
" ------- ", "|        ", " ------- ", "        |", " ------- "},{
" ------- ", "|        ", " ------- ", "|       |", " ------- "},{
" ------- ", "        |", "         ", "        |", "         "},{
" ------- ", "|       |", " ------- ", "|       |", " ------- "},{
" ------- ", "|       |", " ------- ", "        |", " ------- "}
},{{
" -------- ", "|        |", "          ", "|        |", " -------- "},{
"          ", "         |", "          ", "         |", "          "},{
" -------- ", "         |", " -------- ", "|         ", " -------- "},{
" -------- ", "         |", " -------- ", "         |", " -------- "},{
"          ", "|        |", " -------- ", "         |", "          "},{
" -------- ", "|         ", " -------- ", "         |", " -------- "},{
" -------- ", "|         ", " -------- ", "|        |", " -------- "},{
" -------- ", "         |", "          ", "         |", "          "},{
" -------- ", "|        |", " -------- ", "|        |", " -------- "},{
" -------- ", "|        |", " -------- ", "         |", " -------- "}
},{{
" --------- ", "|         |", "           ", "|         |", " --------- "},{
"           ", "          |", "           ", "          |", "           "},{
" --------- ", "          |", " --------- ", "|          ", " --------- "},{
" --------- ", "          |", " --------- ", "          |", " --------- "},{
"           ", "|         |", " --------- ", "          |", "           "},{
" --------- ", "|          ", " --------- ", "          |", " --------- "},{
" --------- ", "|          ", " --------- ", "|         |", " --------- "},{
" --------- ", "          |", "           ", "          |", "           "},{
" --------- ", "|         |", " --------- ", "|         |", " --------- "},{
" --------- ", "|         |", " --------- ", "          |", " --------- "}
},{{
" ---------- ", "|          |", "            ", "|          |", " ---------- "},{
"            ", "           |", "            ", "           |", "            "},{
" ---------- ", "           |", " ---------- ", "|           ", " ---------- "},{
" ---------- ", "           |", " ---------- ", "           |", " ---------- "},{
"            ", "|          |", " ---------- ", "           |", "            "},{
" ---------- ", "|           ", " ---------- ", "           |", " ---------- "},{
" ---------- ", "|           ", " ---------- ", "|          |", " ---------- "},{
" ---------- ", "           |", "            ", "           |", "            "},{
" ---------- ", "|          |", " ---------- ", "|          |", " ---------- "},{
" ---------- ", "|          |", " ---------- ", "           |", " ---------- "}}};



void prepare_dc(short size, string& str) {
    for(short l = 0; l<5; l++) {
        string r;
        short i = 0;
        short sz = size;
        while(number[i] != '\0') {
            r += table[size-1][((short)number[i]-48)][l];
            if(number[i+1] != '\0')
                r += " ";
            i++;
        }
        str += r + '\n';
        sz--;
        while ((l & 0x01) != 0 && sz > 0 ) {
            str += r + '\n';
            sz--;
        }
    }
}


/* main
 * */

int main() {
    while ( true ) {
        unsigned long n =0;
        short size = 0;
        fill(number, number+10, '\0');
        cin >> size >> n;
        if (size == 0) { 
            return 0;
        }
        sprintf(number, "%lu", n);
        string str;
        prepare_dc(size, str);
        cout << str <<  endl;
    }
}

After Thoughts -  

• The above attempt has been made to print the number's digits  line by line instead of printing each digit and moving to next. Lines of each digit having size one to ten has been precomputed to reduce the execution timing.
• I have also tried using stream instead of using multiple cout but surprisingly it has time overhead.
• The above implementation doesn't consider the prpreceding zeros, since judges test cases don't complain so left it as it is.
• There is nothing special in this problem but still execution timing is a challenge.

Give it a try and do share your feedback -