UVA Problem 10878 – Decode the tape Solution

UVA Problem 10878 – Decode the tape Solution:


Click here to go to this problem in uva Online Judge.

Solving Technique:

The problem may seem easy to some and maybe hard for some. There are multiple ways of solving this. Please take a look at this if don’t have a good understanding if binary numbers. Also learn Bitwise operations. Do not print a new line for this problem.

At first glance it doesn’t make sense. But trying to match characters we see a pattern. Like whenever we see

|  o  .   |

we see there is a space. Each line represents a character we can find this easily by counting characters in the given output and counting lines on input tape. This we can match every character to its corresponding line on the tape. But in the last line we see there is an extra line on the ( not the blank line ) tape. That represents the newline.

Now there are only two types of data on the tape a space character and a hole ( o character ). One example for problem like this when writing in the exams we fill in ID box with pencils by circling the numbers that match our id number.

So since there are only two types ( Forget . and | ) of data it is either 0 or 1 meaning binary. So now when we assign a value to each binary digits we can see that when we add values for 1 we get ASCII value of the character.  

Now that we understand the problem we can solve this in different ways. One approach can be for every loop we can check the value of that character. It is possible since the tape length is always same. if it is 1 we add the corresponding decimal number for that binary digit. Ex:

/* I skip s[0] because it is not a space or o character in tape */
if(s[1] == 'o') sum = sum + 128;
if(s[2] == 'o') sum = sum + 64;
/* keep going like this for each hole or space character */

My approach is bit shifting. By bit shifting we get the same result. Since the string consisting of ( space and hole ) is always 8 characters long. Starting from left we can assign values by increasing power by 1 for each value to left.

128  64  32  16  8   4   2   1
2^7 2^6 2^5 2^4 2^3 2^2 2^1 2^0
 1   1   1   1   1   1   1   1

If I search the string from left then I need set bit to 128 and shift right ( making them smaller for each values to right ). That what I did here. So here values are decreasing right to left. 

Another approach is start from the end of string and set the bit to 1. Now we shift bits to left every time we find a space or a hole. So, here values are increasing left to right.

for(i = strlen(s) - 1; i >= 0; --i){
        if(s[i] == ' '){
            bit <<= 1;
        }else if(s[i] == 'o'){
            sum += bit;
            bit <<= 1;
        }
}

Important:  The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.


Input:

___________
| o   .  o|
|  o  .   |
| ooo .  o|
| ooo .o o|
| oo o.  o|
| oo  . oo|
| oo o. oo|
|  o  .   |
| oo  . o |
| ooo . o |
| oo o.ooo|
| ooo .ooo|
| oo o.oo |
|  o  .   |
| oo  .oo |
| oo o.ooo|
| oooo.   |
|  o  .   |
| oo o. o |
| ooo .o o|
| oo o.o o|
| ooo .   |
| ooo . oo|
|  o  .   |
| oo o.ooo|
| ooo .oo |
| oo  .o o|
| ooo . o |
|  o  .   |
| ooo .o  |
| oo o.   |
| oo  .o o|
|  o  .   |
| oo o.o  |
| oo  .  o|
| oooo. o |
| oooo.  o|
|  o  .   |
| oo  .o  |
| oo o.ooo|
| oo  .ooo|
|  o o.oo |
|    o. o |
___________

Output:

A quick brown fox jumps over the lazy dog.

Code:

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 */

#include<stdio.h>

static char s[64];

int main(){
    register unsigned int i;
    unsigned sum, found;

    while(gets(s)){
        unsigned int bit = 128;     /* Since the binary form is 8 characters long ( not including . or | ) 2^7 = 128 ( 7 but not 8 starts from 0. 2^0....2^7 total 8 digits ) we keep left shifting and adding only if we find a hole */

        i = sum = found = 0;
        if(s[i] != '|') continue;   /* We don't want to print anything for lines not starting with | */

        for(; s[i]; ++i){
            if(s[i] == ' ')
                bit >>= 1;          /* keep shifting bits right ( makes them smaller. Ex, 128 = 2^7. So, 128 >> 1 = 64, 2^7 >> 1 = 2^6 = 64 ) OR, you can shift bits to left make them bigger but then you have search the string in reverse order */
            else if(s[i] == 'o'){
                sum += bit;         /* Add the bits where we find a hole */
                bit >>= 1;
            }
        }

        printf("%c", sum);          /* Print the sum. No need to print newline. The last line of tape represents a newline character |    o. o | */
    }
    return 0;
}

One thought on “UVA Problem 10878 – Decode the tape Solution

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s