NPTEL- Design and analysis of algorithms (2016)

 

Week - 2

SMS Dictionary

Due on 2016-08-05, 23:59 IST

SMS Dictionary

(Indian National Olympiad in Informatics, INOI, 2007)

In the pre-smartphone era, most mobile phones with numeric keypads had a private dictionary of words to allow users to type messages quicker. On a typical phone of this type, each number key is assigned a subset of the alphabet {a,b,…,z}: 2 is assigned the subset {a,b,c}, 3 is assigned {d,e,f}, 4 is assigned {g,h,i}, 5 is assigned {j,k,l}, 6 is assigned {m,n,o}, 7 is assigned {p,q,r,s}, 8 is assigned {t,u,v} and 9 is assigned {w,x,y,z}.

When the user types a sequence of numbers, this sequence is mapped to all possible words that can be constructed from the key assignment. For instance, if the user types 66, this could correspond to any one of the letter sequences "mm", "mn", "mo", "nm", "nn", "no", "om", "on" or "oo". These letter sequences are looked up in the dictionary stored in the phone and all matches are reported. For instance, if the phone's dictionary contains only "on" and "no" from this set of sequences, the user will be offered a choice of "on" or "no" to insert in the message. Similarly, the input 4663 might be interpreted as either "good" or "home". An input sequence may have a unique interpretation---for example, the only word in the dictionary matching the input 28 may be "at". Other sequences may not match any word in the dictionary—for instance, 99999.

Your task is the following. Given the typical assignment from number keys to letters of the alphabet given above and given a dictionary of words, report the input sequence that matches the largest number of words in the dictionary. For example, if the dictionary consists of the words {at,on,good,no} then the answer is 66, because 66 matches both "on" and "no" while no other input matches more than one word in the dictionary. On the other hand, with the dictionary {at,on,good,no,home,gone}, the answer is 4663, because 4663 matches three words, "good", "home" and "gone" in the dictionary.

Solution hint

For each word in the input, compute the number key sequence that creates it by inverting the mapping 2→{a,b,c}, 3→{d,e,f} etc. Store the number corresponding to the word in an array.

After reading all the input, sort the numbers in the array.

Input format

The first line of input is an integer M, the number of words in the dictionary. This is followed by M lines of input. Each line contain one word from the dictionary, where a word is sequence of characters from the lowercase alphabet {a,b,c,…,z}.

Note: Each word in the dictionary is, in general, an arbitrary sequence of letters from {a,b,c,…,z}. In particular, it is not assumed that the words stored in the dictionary are valid words in English or any other language.

Output format

A single line containing the input sequence that matches the maximum number of words in the dictionary. If multiple input sequences qualify for the maximum number of matches, it suffices to report any one.

Test data

For all inputs, 1 ≤ M ≤ 100000. Each word in the dictionary is at most 8 characters long. In 50% of the inputs, 1 ≤ M ≤ 1000.

Example

Here is the sample input and output corresponding to the example discussed above.

Sample input 1

4
at
on
good
no

Sample output 1

66

Sample input 2

6
at
on
good
no
home
gone

Sample output 2

4663

Code :

#include<iostream>
#include<algorithm>
using namespace std;
long long temp[100000];
main()
{
    long long i,j,k,t,cnt=0;
    cin>>t;
    string s[t];
    for(i=0;i<t;i++)
    {
        cin>>s[i];
    }
    for(i=0;i<t;i++)
    {
        for(j=0;j<s[i].length();j++)
        {
            if(s[i][j]=='a'||s[i][j]=='b'||s[i][j]=='c')
            {
                cnt=cnt*10+2;
            }
            else if(s[i][j]=='d'||s[i][j]=='e'||s[i][j]=='f')
            {
                cnt=cnt*10+3;
            }
            else if(s[i][j]=='g'||s[i][j]=='h'||s[i][j]=='i')
            {
                cnt=cnt*10+4;
            }
            else if(s[i][j]=='j'||s[i][j]=='k'||s[i][j]=='l')
            {
                cnt=cnt*10+5;
            }
            else if(s[i][j]=='m'||s[i][j]=='n'||s[i][j]=='o')
            {
                cnt=cnt*10+6;
            }
            else if(s[i][j]=='p'||s[i][j]=='q'||s[i][j]=='r'||s[i][j]=='s')
            {
                cnt=cnt*10+7;
            }
            else if(s[i][j]=='t'||s[i][j]=='u'||s[i][j]=='v')
            {
                cnt=cnt*10+8;
            }
            else if(s[i][j]=='w'||s[i][j]=='x'||s[i][j]=='y'||s[i][j]=='z')
            {
                cnt=cnt*10+9;
            }
              else if(s[i][j]==' ')
            {
                  cnt = cnt*10;
            }

        }
        temp[i]=cnt;
            cnt=0;
            //cout<<temp[i]<<endl;
    }
  sort(temp,temp+t);
    long long x=0,x2;
    for(i=0;i<t;i++)
    {
        if(count(temp,temp+t,temp[i])>x)
        {
            x=count(temp,temp+t,temp[i]);
            x2=temp[i];
        }
    }
    cout<<x2<<endl;

}

How to Interface 7-Segment LED using 8 GPIO of Arduino Uno?

7-Segment Led Interfacing Using GPIOs

How many TV shows and movies have some mysterious device counting down to zero those displays are 7 segment displays.With the 7 segment displays you can display any number or some alphabets that your heart desires.

At first controlling a 7 segment display seems quite complex but it quickly becomes clear.

What follows is a quick guide to control a 7 segment display with a arduino board.

• First let me do it on proteus simulator.

Proteus file

• Arduino Code:

1. void setup()
2. {
3.  int i=0;
4.  for(i=0;i<8;i++) 
5.  {
6.    pinMode(i,OUTPUT);
7.  }
8. }
9. void loop()
10. {
11.  char x=0x00;
12.  PORTD = x;
13.  x++;
14.  delay(500);
15. }

Common Configuration(Anod/Cathod)

This post is all about how to interface a seven segment display with microcontroller. In this particular example I will interface one seven segment display with PIC24. You may download Proteus Simulations and code from the links given at the bottom of this page.

1. 
   
               I am using MPLAB X IDE and C30 Compiler for 16bit microcontrollers. I supposed that you know how to blink an LED (if not then I suggest you to read this (link) first before continuing this post) and how to generate a delay without timers or with timers ((if not then I suggest you to read this (link1 and Link2) first before continuing this post).
   
   
               There are two types of seven segments available in the market
   1)      Common anode.
   2)      Common cathode.
   
   
   I will go through from both of them in order to make you understand that what differences will be caused in hardware and software.
   
   
   In hardware they are arrange in following type:
   
   
   
   

   

   Common Anode Internal configuration.

   
   
   Truth table for Common Anode:

   
   

   	Dp (MSB)	G	F	E	D	C	B	A (LSB)	Value in hex
   0	1	1	0	0	0	0	0	0	0xC0
   1	1	1	1	1	1	0	0	1	0xF9
   2	1	0	1	0	0	1	0	0	0xA4
   3	1	0	1	1	0	0	0	0	0xB0
   4	1	0	0	1	1	0	0	1	0x99
   5	1	0	0	1	0	0	1	0	0x92
   6	1	0	0	0	0	0	1	0	0x82
   7	1	1	1	1	1	0	0	0	0xF8
   8	1	0	0	0	0	0	0	0	0x80
   9	1	0	0	1	1	0	0	0	0x98

   
   

   
   

   Common Cathode Internal configuration.
   
   
   
   
   
   
   

   For Reference:

   http://www.instructables.com/id/Seven-Segment-Display-Tutorial/

What is Redundant Network Topology ?

Redundancy is a system design in which a component is duplicated so if it fails there will be a backup. Redundancy has a negative connotation when the duplication is unnecessary or is simply the result of poor planning.

NETWORK REDUNDANCY

The underlying concept behind network redundancy is to provide alternate paths for data to travel along in case a cable is broken or a connector accidentally un-plugged. However, Ethernet as standard cannot have rings or loops in the network as this will cause broadcast storms* and can ultimately cause the network to stop working. An Ethernet network cannot have two paths from point A to point B without a mechanism in place to support this type of topology. To achieve redundancy, the network infrastructure (switches) must support redundancy protocols designed to negate the usual problems of putting loops into an Ethernet network, maintaining a default data path and switching to an alternate one when a fault occurs.

CLASSIC STAR TOPOLOGY

A typical Ethernet network employs a star topology as detailed in Figure 1 below. There are several mechanisms for providing redundancy in a network, the most common being LACP*, RSTP* and ring redundancy. All switches must support the required redundancy capability and the switches must be connected to each other in an appropriate configuration. For simplicity and ease of expansion, ‘redundant rings’ are becoming the most popular redundancy solution for the BMS market.

REDUNDANT RING TOPOLOGY

Using “Industrial Ethernet switches” it is possible to build a ring topology that can suffer a single point failure (cable broken or connector unplugged) and continue to operate as if nothing had changed. This will keep BMS controllers and outstations communicating with each other even in the event of a network failure. Comparing Figure 1 and Figure 2, the difference between a star and a ring network topology is clearly visible.

Back to top

HOW DOES RING REDUNDANCY WORK?

Consider Figure 2. The network traffic from outstation A follows the default path through the network from switch 2 to switch 1 to switch 4 to the destination - the Supervisor PC. If a cable is broken or a connector un-plugged along this default route, the switches will automatically reconfigure to transmit data the alternative way around the ring – switch 2 to switch 3 to switch 4 to Supervisor. This network reconfiguration can happen in as little as 20mS. Poorly designed redundant networks can have a much higher re-configuration time with BMS data potentially disappearing from the screen for several minutes. Without redundancy, the BMS system may stop working effectively for several days. Figure 2 shows a network with redundancy at the “network layer” but no redundancy at the “device layer”. If the single link from the Supervisor to the network were broken, access to the live BMS data would be lost. The next logical step is to dual attach the Supervisor PC to the network removing the single point of failure. Dual attachment of Ethernet devices is not always a trivial process. Amplicon’s technical team can help with such requirements. Redundant Ring topology with all devices dual attached In highly critical applications, it may be necessary to dual attach all devices (outstations and PCs) to the network to provide a very high level of redundancy. This provides maximum reliability but also generates maximum cost and complexity. Most vendors of Industrial Ethernet products support a version of the ‘redundant ring’ technology described above. It should be noted that the protocols used are not based on a standard and are generally not interoperable amongst the different switch manufacturers.

Back to top

SPANNING TREE

TCP provides many network services but is best known for multiplexing, flow control and provision of an entry / exit point to the network. Applications (email, web browser, BMS software) access the network through ports*. By giving each piece of software its own port, it is possible to identify many different applications on a single network device and thus allow many applications on a single to use the same physical network without data getting delivered to the wrong place. This process is referred to as multiplexing as it allows many different data packets to be multiplexed over the network. At the receiving end, TCP de-multiplexes the data stream, distributing the right data packets to the correct applications. Multiple paths exist between switches in a “mesh” providing a high degree of network redundancy.

POWER REDUNDANCY

Many Industrial Ethernet switches support power redundancy, allowing 2 or more power inputs to be used in case of failure of the primary input. This can be a useful selling point for your network over a competitor’s solution and costs little extra to implement.

Reference Link:

https://www.amplicon.com/building/network-redundancy.cfm