Just a place to put some random thoughts..
Hi,
This post is about just one interesting thing that I did in the last week. Some days ago, I had posted about
quzzle (for some strange reason I called it Quazzle in that post). On of my colleague (hes a real brain.. THE best programmer I personally know) wrote a program to solve it in just an hour. That inspired me to give it a try. It took me almost three days to get it right. But atlast here it is. It was fun. I had to solve many problems in doing that. It was cool and kept me busy for some days. And in the end its VERY VERY satisfying. :). It also reminded me that I have a looong way to go before I call myself a good programmer. I am sure this one is also not very optimized.
Heres the thing: (If you are a programmer, please review and suggest improvements)
#include
#define TRUE 0
#define FALSE 1
#define UP 1
#define DOWN 2
#define RIGHT 3
#define LEFT 4
#define MAXDEPTH 116
typedef int state[10];
struct moves {
int block;
int direction;
};
struct old_states {
state saved_state;
int depth;
struct old_states *next_state;
};
struct old_states *states = NULL;
int depth = 0;
void free_old_states()
{
struct old_states *tmp_st, *new_st;
if(!states)
return;
if(!states->next_state){
free(states);
return;
}
for(tmp_st = states, new_st = states->next_state; tmp_st;
new_st = tmp_st->next_state, tmp_st = new_st){
free(tmp_st);
}
return;
}
int get_valid_moves(state st, struct moves *move)
{
int i, move_count = 0;
for(i = 0; i <= 8; i++){
if(((((st[i] | st[i] >> 4) ^ st[i]) & st[9]) ==
((st[i] | st[i] >> 4) ^ st[i])) && !(st[i] & 0xf)){
move[move_count].block = i;
move[move_count].direction = UP;
move_count++;
}
if(((((st[i] | st[i] << 4) ^ st[i]) & st[9]) ==
((st[i] | st[i] << 4) ^ st[i])) && !(st[i] & 0xf0000)){
move[move_count].block = i;
move[move_count].direction = DOWN;
move_count++;
}
if(((((st[i] | st[i] >> 1) ^ st[i]) & st[9]) ==
((st[i] | st[i] >> 1) ^ st[i])) && !(st[i] & 0x11111)){
move[move_count].block = i;
move[move_count].direction = RIGHT;
move_count++;
}
if(((((st[i] | st[i] << 1) ^ st[i]) & st[9]) ==
((st[i] | st[i] << 1) ^ st[i])) && !(st[i] & 0x88888)){
move[move_count].block = i;
move[move_count].direction = LEFT;
move_count++;
}
}
return move_count;
}
void add_state(state st)
{
struct old_states *new_st;
new_st = (struct old_states *)malloc(sizeof(struct old_states));
new_st->next_state = states;
new_st->depth = depth;
memcpy(&new_st->saved_state, st, sizeof(state));
states = new_st;
}
int is_old_state(state st)
{
struct old_states *tmp_st, *new_st;
for(tmp_st = states; tmp_st; tmp_st = tmp_st->next_state){
if(memcmp(&tmp_st->saved_state, st, sizeof(state)) == 0){
if(tmp_st->depth <= depth){
return TRUE;
} else {
tmp_st->depth = depth;
return FALSE;
}
}
}
add_state(st);
return FALSE;
}
void make_move(state st, struct moves *move, state *new_state)
{
int new_bits, old_bits;
int i = move->block;
memcpy(*new_state, st, sizeof(state));
switch(move->direction){
case UP:
new_bits = (st[i] | st[i] >> 4) ^ st[i];
old_bits = (st[i] | st[i] >> 4) ^ (st[i] >> 4);
(*new_state)[i] = (*new_state)[i] >> 4;
break;
case DOWN:
new_bits =(st[i] | st[i] << 4) ^ st[i];
old_bits = (st[i] | st[i] << 4) ^ (st[i] << 4);
(*new_state)[i] = (*new_state)[i] << 4;
break;
case LEFT:
new_bits =(st[i] | st[i] << 1) ^ st[i];
old_bits = (st[i] | st[i] << 1) ^ (st[i] << 1);
(*new_state)[i] = (*new_state)[i] << 1;
break;
case RIGHT:
new_bits =(st[i] | st[i] >> 1) ^ st[i];
old_bits = (st[i] | st[i] >> 1) ^ (st[i] >> 1);
(*new_state)[i] = (*new_state)[i] >> 1;
break;
}
(*new_state)[9] ^= new_bits;
(*new_state)[9] |= old_bits;
return;
}
int is_final(state st)
{
if(st[0] == 0x00033)
return TRUE;
return FALSE;
}
void print_move(struct moves *move)
{
printf("%d)move is %d to ", depth, move->block, move->direction);
switch(move->direction){
case UP: printf("UP\n"); break;
case DOWN: printf("DOWN\n"); break;
case LEFT: printf("LEFT\n"); break;
case RIGHT: printf("RIGHT\n"); break;
}
}
int solve(state st)
{
state new_state;
int moves, i;
struct moves move[36];
if(is_final(st) == TRUE){
return TRUE;
}
depth++;
if(depth >= MAXDEPTH){
depth--;
return FALSE;
}
if(is_old_state(st) == TRUE){
depth--;
return FALSE;
}
moves = get_valid_moves(st, &move[0]);
for(i = 0; i < moves; i ++){
make_move(st, &move[i], &new_state);
if(solve(new_state) == TRUE){
print_move(&move[i]);
depth--;
return TRUE;
}
}
depth--;
return FALSE;
}
int main()
{
state init_state;
init_state[0] = 0x000cc;
init_state[1] = 0x00003;
init_state[2] = 0x00220;
init_state[3] = 0x00110;
init_state[4] = 0x88000;
init_state[5] = 0x06000;
init_state[6] = 0x01000;
init_state[7] = 0x60000;
init_state[8] = 0x10000;
init_state[9] = 0x00c00;
if(solve(&init_state[0]) == TRUE)
printf("solved\n");
free_old_states();
return 0;
}
Yours Sinerely,
Hi,
This blog is quietly celebarting its first birthday today. There will not be any parties. Why should there be any when there is one less year before it dies. But even if it looks as if it is going nowhere, the blog heart is still beating there somewhere. Stay tuned. This blog is not dead!
Yours Sinerely,
Hi,
Some days back I had come across this . I had come across the implementation of the same at some months (maybe a year) back. That time I had thought that I could do it if I wanted to. Today I did it. It was not as simple as it looked. Took almost all day to get it right. Gray matter is sleeping!
------------------
#!/usr/bin/perl
$count = 0;
if($#ARGV < 2){
print "Usage ./phonechal.pl \n";
exit;
}
$number = $ARGV[0];
$dict = $ARGV[1];
$min_num = $ARGV[2];
builddicthash($dict);
part($number,"");
sub part {
my $string = shift;
my $prefix = shift;
if(length($string) <= 1){
print_ph("$prefix $string");
$combs[$count++] = "$prefix $string";
return;
}
$prefix1 = $prefix.substr($string, 0, 1);
$string1 = substr($string, 1, length($string) - 1);
part($string1, $prefix1);
if(length($prefix) > 0){
$prefix1 = $prefix." ".substr($string, 0, 1);
$string1 = substr($string, 1, length($string) - 1);
part($string1, $prefix1);
}
$combs[$count++] = "$prefix $string";
print_ph("$prefix $string");
}
sub builddicthash {
my $dict = shift;
open(FILE, $dict);
while($line = ){
@tsplit = split("", lc($line));
chomp($line);
$entry = "";
for($i = 0; $i <= $#tsplit; $i++){
if($tsplit[$i] eq 'a' || $tsplit[$i] eq 'b' || $tsplit[$i] eq 'c'){
$entry = $entry."2";
}
if($tsplit[$i] eq 'd' || $tsplit[$i] eq 'e' || $tsplit[$i] eq 'f'){
$entry = $entry."3";
}
if($tsplit[$i] eq 'g' || $tsplit[$i] eq 'h' || $tsplit[$i] eq 'i'){
$entry = $entry."4";
}
if($tsplit[$i] eq 'j' || $tsplit[$i] eq 'k' || $tsplit[$i] eq 'l'){
$entry = $entry."5";
}
if($tsplit[$i] eq 'm' || $tsplit[$i] eq 'n' || $tsplit[$i] eq 'o'){
$entry = $entry."6";
}
if($tsplit[$i] eq 'p' || $tsplit[$i] eq 'q' || $tsplit[$i] eq 'r'
|| $tsplit[$i] eq 's') {
$entry = $entry."7";
}
if($tsplit[$i] eq 't' || $tsplit[$i] eq 'u' || $tsplit[$i] eq 'v'){
$entry = $entry."8";
}
if($tsplit[$i] eq 'w' || $tsplit[$i] eq 'x' || $tsplit[$i] eq 'y'
|| $tsplit[$i] eq 'z'){
$entry = $entry."9";
}
}
if($#{$dicthash{$entry}} < 0){
$dicthash{$entry}[0] = $line;
}else{
$dicthash{$entry}[$#{$dicthash{$entry}}+1] = $line;
}
}
close(FILE);
}
sub print_ph{
my $no = shift;
my $loop = 1;
my $i, $j, $entry, $subscript, $c, @subscripts, $final, $words=0;
@phsplit = split(" ", $no);
for($i = 0; $i <= $#phsplit; $i++){
$c = $#{$dicthash{$phsplit[$i]}};
if($c >= 0){$loop = $loop * ($c+1)};
}
for($i = 0; $i < $loop; $i++){
$final = "";
$words = 0;
$wrap = 1;
for($j = 0; $j <= $#phsplit; $j++){
$entry = $dicthash{$phsplit[$j]}[$subscripts[$j]];
if(length($entry) > 0){
$final = $final." ".$entry." ";
$words++;
} else {
$final = $final.$phsplit[$j];
}
if($#{$dicthash{$phsplit[$j]}} >= 0){
if($wrap) {
$subscripts[$j]++;
}
if($subscripts[$j] > $#{$dicthash{$phsplit[$j]}}){
$subscripts[$j] %=
($#{$dicthash{$phsplit[$j]}}+1);
$wrap = 1;
}else{
$wrap = 0;
}
}
}
# if($words >= $min_num) {
if(!$added{$final}){
print "$final\n";
$added{$final} = 1;
}
# }
}
}
Yours Sinerely,
Hi,
I am back from a LONG weekend which I spent in mainly in the buses and other places like Pune, Mumbai. I had gone for friends wedding.
Thats it.
Yours Sinerely,
Hi,
Today, as I was going through the weekend slashdot stories, I found a story about a guy called . He calls it quazzle. The same thread has a link to . I got hooked on immediately and I knew I would not be able to do any work today until and unless I solve it. My method was simple. Brute force trial and error :). It took me almost half an hour to get it right. And I'm not sure if I can reproduce it.
Thats why, as soon as I was done, I took a sceenshot. Here it is.
How long did it take for you? :)
[Update: I wrote a program to solve it you can find it
here]
Yours Sinerely,
Hi,
The weekend was amazing. I had gone to . And I have some pretty snaps which I will upload later.
Kyathadevera Gudi is situated in Biligiri Ranganna Hills. (For cool people its K-Gudi and B-R-Hills.) Its situated at 3300 feet from the sealevel. We had booked tented cottages there a week before. Its an almost ideal weekend-gateaway if you are looking for peace, quiet and lots of fresh air.
We left at 6 in the morning from Bangalore and reached Mysore at 9 am. The road is good and its gonna get better. They are in process of building a 4 lane high way of which only 2 lanes are open for use now. From Mysore just follow the route given on the broucher and there are helpful boards that direct you to the jungle resort. The road was small after Mysore but it was very scenic with green-yellow crop fields all around. If you are not sure of the road just ask for "Chamraj Nagar" and people will direct you. When you reach the Ghat Section, you know you are almost there.
We reached there at 12:30 in the noon. It was cool and the tents gave a feeling that was a perfect combination of adventure and luxury. It was clean and neat. The staff was efficient and helpful.
We took two jeep safaris into the jungle. The jungle there is amazing. I have been to Bandipur and Banerghatta but this jungle stood apart. It was untamed and wild. I wasnt expecting to sight any animals but the jeep driver said there are tigers and leopards in the jungle. We dint see any of them. But just roaming in the jungle made it worthwhile for me. We saw deers and wild boars and bisons.
All-n-all it was a good trip and I would go there again.
Yours Sinerely,
Hi,
Yesterday someone was asking me "
What do you and Kareena Kapoor have in common?". This was not the first time I was asked this question. I thought that I should just post the answer on this blog here and point everyone to it (Sounds like a nice way to drive traffic to this blog). The answer is "
Nothing!". So please stop asking me this question again and again. And if someone tells you otherwise.. for god's sake dont believe them. I repeat, DO NOT BELIEVE AND SPREAD ROUMERS!
But thats not the whole truth either. but thats about it. Now, you media guys and paparazzis, please leave us alone.
Yours Sinerely,
Hi,
Day before yesterday, after a hard days work, me and my friend were on our way home. And somehow we were talking about changing jobs. He asked me what would I do if someone offers me a job that I dont want to accept. My solution was to ask for an unreasonable salary, which they wont be able to afford, rather than saying that their job sucks. I told him that I got to know about this trick when I was watching a talk show called "Coffee with Karan" somedays back. In that show, Karan Johar asked Kareena (Ooomph!) that what would she say if she was offerred "Murder". And her answer (which I though was pretty cool) was "5 crores!".
Then we started talking about Kareena and money she must be making. Eventually, we agreed that marrying a rich babe pays high dividends than spending (or wasting) your life in software industry hell. Marry someone like Kareena and then kill her is all you have to do and you will be chilling out somewhere in Alps or Bahamas for rest of your life.
According to my friend, getting away with a murder is not so easy. I, on the other hand, believe that you can get away with a murder if you have the right plan. So I started telling him what I would do.
Here's the plan :
Marry Kareena. Be amazingly loyal and nice to her for next two or three years. Find out how much money she has. Aim for 5% of that. One day take her to some high cliff or something. Make sure that if she falls from that height then the probability of her dying is more that 90%. And push her. Spend next two or three years in moarning. Let everyone know that you miss her a lot. Pretend to be depressed. Wait till people around you start telling you that life-must-go-on. Make them feel that you are moving on in life just for them. And THEN you are done. Its a 8-10 years plan but after 10 years you will have a lot more than what you might have if you continue in the software industry.
I think Shadid Kapoor is well on his way.
Scary.. isnt it? I have a criminal mind.
Yours Sinerely,
Hi,
Actually, I could have come up with a better title for this post but this blog has traditions and rituals. And one cannot and should not do away with the traditions which are harmless and somewhat useful. This "Hey" tradition goes a long way back with this blog. Every now and then this blog (or the author) comes across what the media calls as "Bloggers block". I prefer to call it laziness+boredom. When the sense of blog-must-go-on feeling kills this "bloggers block", I come up with a "Hey" post. So I'm just sticking to it because it has worked for me before
here,
here,
here,
here,
here,
here and
here.
Last week saw the author being busy with the work. My parents are here and I am having a nice time. Last weekend I had gone to . It was better than what I had expected. They have a safari there. Its not a wildlife sactuary or anything. Thay have divided the forest area into sections and put a fence. We saw tigers, lions, bears, deers, crocodiles and lots of them. It was the first time I saw tigers mating. Tiger porn is not very exciting. ;)
Thats it.
Yours Sinerely,
