UVA Problem 10851 – 2D Hieroglyphs decoder Solution

UVA Problem 10851 – 2D Hieroglyphs decoder Solution:


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

Solving Technique:

This problem may look a little hard at first but the problem could be easily reverse engineered from the problem statement. Before starting this if you are familiar with UVA PROBLEM 10878 – DECODE THE TAPE then apply that knowledge. This problem is also very similar.

It is also possible to pre calculate a pattern table based on printable ASCII character then apply a string matching algorithm ( which is harder than this ). This is a reminder for myself and anyone else who wants to implement this method.

Here \forall is called universal quantifier, so \forall can be termed as for all and \in means member of or, element of or, in.


Dissecting problem statement to create pattern generator:

H is a 2D array. It is filled following rules below. I have used H as a function to generate the 2D pattern,

H_{i,j} =     \begin{cases}       ' \backslash ' & \forall i = 0, j \in (0, 1, ..., M + 1)  \\      ' \backslash ' & \forall i = 9, j \in (0, 1, ..., M + 1)  \\      ' \backslash ' & \forall j = 0, j \in (0, 1, ..., 9)  \\      ' \backslash ' & \forall j = M + 1, i \in (0, 1, ..., 9)  \\      b(i - 1, c_{j-1}) & \forall i \in (1, 2, ..., 8) , j \in (1, ..., M)  \\    \end{cases}

Its Helper function,

b(i, c) =   \begin{cases}  ' / ' & if, \ \frac{c}{2^i} \ mod \ 2 \ == \ 0 \\  ' \backslash ' &  if, \ \frac{c}{2^i} \ mod \ 2 \ == \ 1 \\  \end{cases}

As described in the problem statement M is the length of the string and their are M + 2 columns ( from 0 to M + 1 columns ). Also there will always be 10 rows of input.

When i is 0 or, i is 9 and j is from 0 to M + 1 print backslash.
Also when j is 0 or, j is M + 1 ( last column ) and i is from 0 to 9 then print backslash.

From above it is clearly visible there are two functions. H function depends on the b function to print slashes when i is 1 to 8 and j is 1 to M ( Length of String ). This means omitting the first, last row and first, last column.

When i is 1 to 8 and j is 1 to M the output depend on b(i,c) function. Which prints a slash based on input. It checks if character ASCII decimal value divided by 2^i is even or, odd and based on that prints a slash.

Using these relations the pattern generator can be created.


Tracing the output:

It is not possible for me to show the whole string since it will be very large. I will show with String being, c[M] = ``bc" .

When, i = 1 \ and \ j = 1 the call to b(i,c) begins with parameter b(i-1, c[j - 1]) which is,

b(1-1, c[1-1]) = b(0,c[0]) = b(0, 'b')

It loops M (strings) times for each row. Which in this case is 2 times,

b(1-1, c[2-1]) = b(0, 'c')

In the b(i,c) function it checks if, character divided by 2^i is even or odd and prints slashes based on that.

for b(0,'b') it is calculated, (98 / 2^0) % 2 which is 0 so prints forward slash ‘/’.
for b(0,'c') it is calculated, (99 / 2^0)% 2 which is 1 so prints backslash ‘\’.

The b(i,c) is called M times for each row and 8 times for each column and a slash is printed based on that. The rest two times slashes are printed from the condition of H_{i,j} function.

From this relation, setting 0 for forward slashed and 1 for backward slashed the column wise string looks like its in binary format. Where the top row is Least significant bit (LSB) and bottom row is Most significant bit (MSB). In case of ‘b’ character only first column shown from the above example string,

row sign binary value
0 / 0 0
1 \ 1 2
2 / 0 0
3 / 0 0
4 / 0 0
5 \ 1 32
6 \ 1 64
7 / 0 0

Their sum is = 2 + 32 + 64 = 98 or, converting the binary to decimal gives a value of 98 which is the ASCII decimal value of ‘b’. Similarly, more characters are calculated if there are more columns.


Shortcut Technique:

Basically first, last row and column are useless. A character is decoded based on each column. A forward slash means 0 and a backslash mean 1. Just apply bit wise shift for each row in a column and add the value when backslash is found. From that value print is equivalent ASCII character.

 

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer. Please compile with c++ compiler as some of my codes are in c and some in c++.


More Inputs of This Problem on uDebug.


Input:

2
///////////
/\/\/\/\/\/
//\\//\\///
////\\\\///
////////\\/
///////////
/\\\\\\\\\/
/\\\\\\\\\/
///////////
///////////

///////////////////////////////////////
//\///\/\\/\//\\/\//\/\\/\/\/\\/\/\//\/
///////\////\/\/\//////\//\////\/\/////
/\//\\\\///\\//\\/\\//\//\\//\///\/\\//
/\//\\//\///\////\\\//////\//\////\\\//
//////\\//////\/\//////\/\/////\/\/////
///\//////\//\///////\//\///\//////////
/\\/\\\\\\/\\/\\\\\\\/\\/\\\/\\\\\\\\\/
///////////////////////////////////////
///////////////////////////////////////

 


Output:

abcdefghi
LA LLUVIA EN SEVILLA ES UNA MARAVILLA

Critical Input Generator:

Warning!!!
This is not the solution just input generator for the problem. The Solution code is below this code.

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 10851 - 2D Hieroglyphs Decoder Pattern / Input Generator
 */

#include<stdio.h>
#include<string.h>
#include<math.h>

//static char c[] = "bc";
//static char c[] = "abcdefghi";
static char c[] = "LA LLUVIA EN SEVILLA ES UNA MARAVILLA";


void b(int i, char ch){
    // May be do a bitwise shift since power of 2
    if( (ch / (long long) pow(2, i) ) % 2 == 0 )
        printf("/");
    else
        printf("\\");
}


void H(int row, int M){
    // String length is M and column is M + 2 so from 0 to M - 1
    M = M + 2;

    for(int i = 0; i < row; ++i ){

        // This can be moved outside loop with little adjustment
        if(i == 0 || i == row - 1){
            for(int j = 0; j < M; ++j)
                printf("/");
        }

        else{
            for(int j = 0; j < M; ++j){
                // Since M = M + 2 so j is j == (M - 1) = (M + 2 - 1) = (M + 1)
                if(j == 0 || j == M - 1)
                    printf("/");
                else
                    b(i - 1, c[j - 1]);
            }
        }

        printf("\n");
    }

}


int main(){

    H(10, strlen(c) );

    return 0;
}

Solution Code:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 10851 - 2D Hieroglyphs Decoder
 * Technique: Binary to Decimal, 2D row wise calculation.
 */

#include<stdio.h>
#include<string.h>

static char c[10][80];

int main(){

    int n, i;

    scanf("%d", &n);
    getchar();

    while( n-- ){

        /**
         * Reset each of the strings ignoring first and last row.
         */
        for(i = 1; i < 9; ++i)
            memset(c[i], 0, sizeof c[i]);


        /**
         * Reuse i for taking string inputs.
         */
        i = 0;


        /**
         * Take input of 10 rows.
         * Another logic is to discard first and last line when taking input.
         * But this method is easier to code.
         */
        while(gets(c[i]) && strlen(c[i]))
            ++i;


        /**
         * Take count of the column.
         * Since input is a rectangle so any column length will work.
         */
        int cols = strlen(c[0]);


        /**
         * Ignore last column.
         * Also last row.
         */
        cols = cols - 1;
        i = i - 1;


        /**
         * k represents columns and j represents rows.
         * k starts from 1 ignoring first column.
         */
        for(int k = 1; k < cols; ++k){

            // Reset for each column.
            int sum = 0;
            int shift = 1;

            /**
             * Ignoring the first and last character.
             * i starts from 1 ignoring first row.
             */
            for(int j = 1; j < i; ++j){

                // Double slash means (for this case) in binary 1 and add that value.
                // Otherwise its zero and no need to calculate in that case.
                if( c[j][k] == '\\' )
                    sum = sum + shift;

                // Bitwise shift left once for each column.
                shift = shift << 1;
            }

            // Print character wise or use string then print outside this loop.
            printf("%c", sum);
        }

        printf("\n");

    }

    return 0;
}
Advertisements

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