Reverse each word in a string

/*************************************************** *
* Reverse each word is a string
*
*
*****************************************************/
#include "iostream"
using namespace std;
void reverse(char *, int , int);
int main()
{
char src[] = "My name is Abc Xyz. My dog's name is Max.";

int len = strlen(src);

int s = 0; //start index of a word
int t = 0; //end index of a word

while(t < len){
while((isalpha(src[t]) || src[t] == '\'') && t < len) t++; //find the end index of a word
reverse(src,s,t-1); //reverse the word at [s, t-1]
while(!isalpha(src[t]) && t < len) t++; //find the start index of next word
s = t; // set the start index of the next word
}
cout << src << endl;


}

/****************************************
* *
* reverse a word *
* *
*****************************************/
void reverse(char *str, int s, int t)
{
char temp;
while (s < t){
temp = str[s];
str[s] = str[t];
str[t] = temp;
t--;
s++;
}

}

K Reverse linked list

Given a linked list, we need to write a function that reverses the nodes of a linked list ‘k’ at a time and returns modified linked list.

The following are the constraints given:

• You have to retain the memory address of the nodes without modifying it i.e. you can’t just interchange the values in the nodes
• Only constant memory is allowed

For example the linked list given is as follows:

Linked List : 1->2->3->4->5->6->7->8->9->10->11 -> null

For k = 2

Return Value: 2->1->4->3->6->5->8->7->10->9->11 ->null

For k = 3

Return value: 3->2->1->6->5->4->9->8->7->10->11 -> null

Solution:

#include "iostream"
using namespace std;

const int N = 10;

//Linked List Class
class LinkedList
{
private:
struct Node{
int data;
struct Node *next;
Node(){next = NULL;};
};
struct Node * Head;
public:
LinkedList();
bool create();
void print();
void reverse(int k);
};

//Print the List
void LinkedList::print()
{
Node *p = Head;
while(p)
{
cout <<>data << " ";
p = p->next;
}
cout << endl;
}

//CTR
LinkedList::LinkedList()
{
Head = NULL;
}

//Create the Linked List 1->2->3->4->5->6->7->8->9->10
bool LinkedList::create()
{
Head = new (struct Node);
Head->data = 1;
Node *p=Head;
Node *t;
for(int i = 2; i <= N; i++){
t = new (struct Node);
t->data = i;
p->next = t;
p = p->next;
}
return true;

}

//Reverse the Linked List within K nodes
void LinkedList::reverse(int k)
{
Node *p = Head;
Node *q = Head;
Node *t = p->next;
Node *r = p->next;
Node *last = p;
p->next = NULL;
int i = 1;
bool flag = false;
while(r)
{
//reverse the list
r = r->next;
t->next = p;
q->next = r;
p = t;
t = r;

i++;
// when k nodes are reversed, start from the next k nodes
if(i >= k||r == NULL){
i = 1;
if(!flag){
Head = p;
flag = true;
}
else
last->next = p;

last = q; // link the last k nodes to the next k nodes
p = r;
q = r;
if(p){
r = p->next;
t = p->next;
}
else{
r= NULL;
t = NULL;
}
}

}
}


int main(int argc, char* argv[])
{
LinkedList L;
L.create();
L.print();
L.reverse(4);
L.print();
return 0;
}

TinyOS: Control servo motor using telosb

For the class project, we made a robot that can be controlled by a Telosb mote. We used two Parallax modified (we did not modify it. The one can continuously rotate is called modified servo) servo motor. The servo motor is shown in figure. This servo motor can be controlled by PWM. The servo motor PWM timing diagram is shown in Figure. The wiring diagram for Parallax servo motor is shown in Figure. So the servo motor can be controlled by providing PWM to the I/O pin. You can try this by using a simple ciruit. PWM can also control the speed of the servo motor.

Now, lets see how we connect the servo motor to the Telosb. Telosb has two expansion connectors. We use the 10-pin connector. Pin 9 is ground. We used two servo motors, so that the robot can turn in Tank style. Therefore, we used Pin-3 and Pin-5 to control two servo motors. To forward straight, two servo motor must rotate in opposite direction. You will see it when you construct your robot. Now, we Telosb ADC converer to send PWM signal to Pin-3 and Pin-5. From the msp430 manual, you know that pins 60 and 61 are the ones you want to use. There is the NesC code for that.

In your configuration file:

components HplMsp430GeneralIOC;

App.Pin0 ->HplMsp430GeneralIOC.Port60;
App.Pin1 ->HplMsp430GeneralIOC.Port61;

In Module use the interfaces:

interface HplMsp430GeneralIO as Pin0;
interface HplMsp430GeneralIO as Pin1;

That is it. Now only thing you have to is is call
call Pin0.clr() or call Pin1.set();
in your timer. You can try this on your Oscilloscope if you are not sure. The only thing left is timing. We used three timers. One with period 18. Other two timers are fires once in 1 or 2 ms after the first timer starts. Here is the code for that. This code randomly sets the movement of the robot.

event void Boot.booted()
{
call Timer0.startPeriodic(18);
}


void forward()
{
call Timer1.startOneShot(1);
call Timer2.startOneShot(2);
}

void reverse()
{
call Timer1.startOneShot(2);
call Timer2.startOneShot(1);

}

void turnright()
{
call Timer1.startOneShot(2);
call Timer2.startOneShot(2);
}
void turnleft()
{
call Timer1.startOneShot(1);
call Timer2.startOneShot(1);
}

event void Timer0.fired()
{
count++;
call Pin1.set();
call Pin0.set();

switch(action){
case 1:
forward(); break;
case 2:
reverse(); break;
case 3:
turnright();break;
case 4:
turnleft();break;
default:
forward();

}

if(count % 100 == 0)
{

action = call Random.rand16() % 4 + 1;
if(action == 1 || action == 2)
count = 0;
else
count = 80;
}
}


event void Timer1.fired()
{
call Pin1.clr();

}
event void Timer2.fired()
{
call Pin0.clr();
}

That is pretty much everything. The source code is here: servo-telosb.zip

TinyOS: setting transmission power for telosb (cc2420 chips)

A homework asked us to localize a mobile mote using RSSI. In short range, the RSSI is inaccurate. To reduce the interference between motes, I reduced the transmission power of mobile mote. It worked very well. Only close neighbors received the signal from the mobile mote. Here is the mobile mote code.
------------------------------------
File: LowPowerSendAppC.nc

/*
* Setting Transmission Power for CC2420 Chips (Telosb, Micaz)
*
* Author: Anwar Mamat anwar at cse.unl.edu
* 04/01/2009
*/


enum {
AM_RSSIMSG = 10
};

typedef nx_struct RssiMsg{
nx_int16_t rssi;
} RssiMsg;

configuration LowPowerSendAppC{

}
implementation {
components ActiveMessageC, MainC;
components new AMSenderC(AM_RSSIMSG) as RssiMsgSender;
components new TimerMilliC() as SendTimer;
components CC2420ActiveMessageC;

components LowPowerSendC as App;


App.Boot -> MainC;
App.SendTimer -> SendTimer;

App.RssiMsgSend -> RssiMsgSender;
App.RadioControl -> ActiveMessageC;
App-> CC2420ActiveMessageC.CC2420Packet;
}

-------------------------------------
File: LowPowerSendC.nc

module LowPowerSendC{
uses interface Boot;
uses interface Timer as SendTimer;
uses interface AMSend as RssiMsgSend;
uses interface SplitControl as RadioControl;
uses interface CC2420Packet;

}
implementation{

message_t msg;
uint16_t SEND_INTERVAL_MS = 100;
uint8_t TRANS_POWER = 3;

event void Boot.booted(){
call RadioControl.start();
}

event void RadioControl.startDone(error_t result){
call SendTimer.startPeriodic(SEND_INTERVAL_MS);
}

event void RadioControl.stopDone(error_t result){}


event void SendTimer.fired(){
call CC2420Packet.setPower(&msg, TRANS_POWER);
call RssiMsgSend.send(AM_BROADCAST_ADDR, &msg, sizeof(RssiMsg));
}

event void RssiMsgSend.sendDone(message_t *m, error_t error){}
}

--------------------------------
File: Makefile

COMPONENT=LowPowerSendAppC
include $(MAKERULES)

HelloWorld for TinyOS

This semester I took "Embedded Systems". I have always liked playing with the sensors and ADC kind of stuff. I checked out few Telosb motes from the lab, installed TinyOS 2.1 on my OpenSuse11.1 desktop, and tried my first "HelloWorld" program. The "HelloWorld" for TinyOS is not that straightforward. Here are the step to make the "HelloWorld" code work on your mote.

1. Install TinyOS. Please refer http://www.tinyos.net/tinyos-2.x/doc/html/install-tinyos.html
2. Make sure you have the correct version of Java on your machine. The default Java on your machine may confilct with the required one.
3. mkdir HelloWorld
4. HelloWorldAppC.nc file:
configuration HelloWorldAppC {
}
implementation {
components HelloWorldC;
components MainC,LedsC;
components new TimerMilliC() as Timer0;

HelloWorldC.Boot-> MainC.Boot;
HelloWorldC.Leds-> LedsC;
HelloWorldC.Timer0->Timer0;
}
5. HelloWorldC.nc file:
module HelloWorldC{
uses{
interface Boot;
interface Leds;
interface Timer as Timer0;
}
}

implementation{
uint16_t count = 0;
event void Boot.booted()
{
call Timer0.startPeriodic(500);
}

event void Timer0.fired()
{
count++;
if (count & 0x0004)
call Leds.led2On();
else
call Leds.led2Off();
if (count & 0x0002)
call Leds.led1On();
else
call Leds.led1Off();
if (count & 0x0001)
call Leds.led0On();
else
call Leds.led0Off();
}
}
6. The Makefile:
COMPONENT=HelloWorldAppC
include $(MAKERULES)

7. So, now you have the HelloWorldAppC.nc, HelloWorldC.nc and Makefile, 3 files in your folder.
8. compile the code: make telosb or make micaz
9. If no error messages, then upload the binary to the mote:
make telosb reinstall
10. Now, you should see the mote saying "HelloWorld" by blinking the 3 Leds.

That is it. Enjoy your TinyOS.

enumerate all cycles in a graph c++ code

Finding all cycles in an undirected graph is an interesting problem. Few days ago, I tried to count all the cycles in a K6, a complete graph with 6 vertices. Finding the 7 cycles from a K4 is easy. But finding the 197 cycles in a K6 is not that trivial. Then I wrote a c++ code to enumerate all cycles in a graph. I tested it on some connected graphs and the results seem correct. Here are the results for the complete graphs, which I can verify by (sum_{k=3}^{n}{1/2 * nCr(n,k)*(k-1)!}.
Number of vertices, number of cycles
3, 1
4,7
5,37
6,197
7,1172
8,8018
9,62814
10,556014
11,5,488,059
20,174548332364311563

Here is the code: graph.txt allcycles.cpp

C++ STL SET example: How to insert objects (ADT) into the set

If your set elements are ADTs or class objects, the elements must be comparable to be inserted into SET container. There is an example. Set example