8-Queens Matrix is Stored using JSON/XML having first Queen placed, use back-tracking to place remaining Queens to generate final 8-queen’s Matrix using Python.

PROGRAM

filename: b1.py

import json

def isattack(board,r,c):
    for i in range(r):
        if(board[i][c]==1):
            return True
    
    i=r-1
    j=c-1
    while((i>=0) and (j>=0)):
        if(board[i][j]==1):
            return True
        i=i-1
        j=j-1
    
    i=r-1
    j=c+1
    while((i>=0) and (j<8)):
        if(board[i][j]==1):
            return True
        i=i-1
        j=j+1
    return False
    
def solve(board,row):
    i=0
    while(i<8):
        if(not isattack(board, row, i)):
            board[row][i]=1
            if(row==7):
                return True
            else:
                if(solve(board, row+1)):
                    return True
                else:
                    board[row][i]=0
        i=i+1
    
    if(i==8):
        return False
    
def printboard(board):
    for i in range(8):
        for j in range(8):
            print str(board[i][j])+"  ",
        print "\n"
        
board = [[0 for x in range(8)] for x in range(8)]

if __name__ == '__main__':
    data=[]
    with open('input.json') as f:
        data=json.load(f)
    
    if(data["start"]<0 or data["start"]>7):
        print "Invalid JSON input"
        exit()
    
    board[0][data["start"]]=1
    if(solve(board, 1)):
        print "Queens problem solved!!!"
        print "Board Configuration:"
        printboard(board)
    else:
        print "Queens problem not solved!!!"
    
filename: input.json
{"start":4}


OUTPUT

Amols-Air:b1 Darwin$ python solve.py
Queens problem solved!!!
Board Configuration:
0   0   0   0   1   0   0   0   

1   0   0   0   0   0   0   0   

0   0   0   1   0   0   0   0   

0   0   0   0   0   1   0   0   

0   0   0   0   0   0   0   1   

0   1   0   0   0   0   0   0   

0   0   0   0   0   0   1   0   

0   0   1   0   0   0   0   0  

Implement a simple approach for k-means/ k-medoids clustering using C++

PROGRAM

filename: a6.cpp

#include<iostream>
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
using namespace std;

class kmeans
{

struct points
{
 float x;
 float y;
};
public:
struct points p[8];
struct points c[3];
void input();
int km();
float distance(float a,float b,float x,float y);
};
int tally[8][10];
int count;
int n;

void kmeans::input()
{
 p[0].x=2;p[0].y=2;
 p[1].x=1;p[1].y=14;
 p[2].x=10;p[2].y=7;
 p[3].x=1;p[3].y=11;
 p[4].x=3;p[4].y=4;
 p[5].x=11;p[5].y=8;
 p[6].x=4;p[6].y=3;
 p[7].x=12;p[7].y=2;
int i,random=0;
srand(time(NULL));
for(i=0;i<3;i++)
{
 random=(rand())%7;
 c[i].x=p[random].x;
 c[i].y=p[random].y;
}
}

float kmeans::distance(float a,float b,float x,float y)
{
float t1=a-x;
float t2=b-y;
if(t1<0)
 t1=-t1;
if(t2<0)
 t2=-t2;
return (t1+t2);
}

int kmeans::km()
{
int i,j;
float table[8][4];
for(i=0;i<n;i++)
{
 table[i][0]=distance(p[i].x,p[i].y,c[0].x,c[0].y);
 table[i][1]=distance(p[i].x,p[i].y,c[1].x,c[1].y);
 table[i][2]=distance(p[i].x,p[i].y,c[2].x,c[2].y);
 if(table[i][0]<=table[i][1] && table[i][0]<=table[i][2])
 {
  tally[i][count]=0;
  table[i][3]=table[i][0];
 }
 else if(table[i][1]<=table[i][0] && table[i][1]<=table[i][2])
 {
  tally[i][count]=1;
  table[i][3]=table[i][1];
 }
 else if(table[i][2]<=table[i][0] && table[i][2]<=table[i][1])
 {
  tally[i][count]=2;
  table[i][3]=table[i][2];
 }
}
cout<<"TABLE: "<<count+1<<endl;
cout<<"Centroids are: ("<<c[0].x<<","<<c[0].y<<"), ("<<c[1].x<<","<<c[1].y<<"), ("<<c[2].x<<","<<c[2].y<<")"<<endl;

cout<<"c1\tc2\tc3\tmin"<<endl;
cout<<"-------------------------"<<endl;
for(i=0;i<n;i++)
{
 for(j=0;j<4;j++)
 {
 cout<<table[i][j]<<"\t";
 }
cout<<endl;
}
cout<<"-------------------------"<<endl;

float c0=0,c1=0,c2=0,c0x=0,c0y=0,c1x=0,c1y=0,c2x=0,c2y=0;
for(i=0;i<n;i++)
{
if(tally[i][count]==0)
{
c0x+=p[i].x;
c0y+=p[i].y;
c0++;
}
else if(tally[i][count]==1)
{
c1x+=p[i].x;
c1y+=p[i].y;
c1++;
}
else if(tally[i][count]==2)
{
c2x+=p[i].x;
c2y+=p[i].y;
c2++;
}
}
c[0].x=c0x/c0;
c[0].y=c0y/c0;
c[1].x=c1x/c1;
c[1].y=c1y/c1;
c[2].x=c2x/c2;
c[2].y=c2y/c2;

int flag=0;
if(count!=0)
{
for(i=0;i<n;i++)
{
 if(tally[i][count]==tally[i][count-1])
   flag++;
}
}
count++;
return flag;
}

int main()
{
kmeans k;
k.input();
n=8;
count=0;
int flag=k.km();
while(flag!=8)
 flag=k.km();
if(flag==8)
 cout<<"Centroids found"<<endl;
for(int i=0;i<n;i++)
{
 for(int j=0;j<count;j++)
  cout<<tally[i][j]<<"  ";
 cout<<endl;
}
return 0;
}


OUTPUT

amodi@localhost ~]$ g++ a6.cpp
[amodi@localhost ~]$ ./a.out
TABLE: 1
Centroids are: (11,8), (3,4), (10,7)
c1 c2 c3 min
-------------------------
15 3 13 3
16 12 16 12
2 10 0 0
13 9 13 9
12 0 10 0
0 12 2 0
12 2 10 2
7 11 7 7
-------------------------
TABLE: 2
Centroids are: (11.5,5), (2.2,6.8), (10,7)
c1 c2 c3 min
-------------------------
12.5 5 13 5
19.5 8.4 16 8.4
3.5 8 0 0
16.5 5.4 13 5.4
9.5 3.6 10 3.6
3.5 10 2 2
9.5 5.6 10 5.6
3.5 14.6 7 3.5
-------------------------
TABLE: 3
Centroids are: (12,2), (2.2,6.8), (10.5,7.5)
c1 c2 c3 min
-------------------------
10 5 14 5
23 8.4 16 8.4
7 8 1 1
20 5.4 13 5.4
11 3.6 11 3.6
7 10 1 1
9 5.6 11 5.6
0 14.6 7 0
-------------------------
Centroids found
1  1  1  
1  1  1  
2  2  2  
1  1  1  
1  1  1  
0  2  2  
1  1  1  
0  0  0 

Intermediate code generation for sample language using LEX and YACC

PROGRAM

filename: my.l

%{
#include<stdio.h>
#include<string.h>
#include "y.tab.h"
%}

%%
[ \n\t]+ ;
main {return MAIN;}
int|float|double|char {strcpy(yylval.string,yytext); return TYPE; }
[a-zA-Z][a-zA-Z0-9_]*    {strcpy(yylval.string,yytext);return ID; }
[0-9]+ {yylval.ival=atoi(yytext);return NUMBER;}
. return yytext[0];
%%
int yywrap(){
return 1;
}


filename: my.y

%{
    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>    

  int Index=0;
  int temp_var=0;
  
  void addQuadruple(char [],char [],char [],char []);
  void display_Quadruple();
  void push(char*);
  char* pop();
  
  struct Quadruple
  {
    char operator[5];
    char operand1[10];
    char operand2[10];
    char result[10];
  }QUAD[25];

 struct Stack
  {
    char *items[10];
    int top;
  }Stk;
%}

%union 
{
  int ival;
  char string[10];
}

%token <ival> NUMBER
%token <string> TYPE
%token <string> ID
%type <string> varlist
%type <string> expr
%token MAIN
%left '+' '-'
%left '*' '/'

%%
program:MAIN '('')''{' body '}';

body: varstmt stmtlist ;

varstmt: vardecl varstmt|;

vardecl:TYPE varlist ';' ;

varlist: varlist ',' ID 

| ID'='NUMBER            

|varlist ',' ID '=' NUMBER 

|ID ;

stmtlist: stmt stmtlist| ;

stmt : ID '=' NUMBER ';' {
                       char temp[10];
                       sprintf(temp,"%d",(int)$3);
                       addQuadruple("=","",temp,$1);}                   
| ID '=' ID ';'{addQuadruple("=","",$3,$1);}
| ID '=' expr ';'   { addQuadruple("=","",pop(),$1); } ;

expr :expr '+' expr {
                    char str[5],str1[5]="t";
                    sprintf(str, "%d", temp_var);    
                    strcat(str1,str);
                    temp_var++;
                    addQuadruple("+",pop(),pop(),str1);                                
                    push(str1);}
|expr '-' expr {
                    char str[5],str1[5]="t";
                    sprintf(str, "%d", temp_var);    
                    strcat(str1,str);
                    temp_var++;
                    addQuadruple("-",pop(),pop(),str1);
                    push(str1);}   

|expr '*' expr {
                char str[5],str1[5]="t";
                sprintf(str, "%d", temp_var);        
                strcat(str1,str);
                temp_var++;
                addQuadruple("*",pop(),pop(),str1);
                push(str1);}       
|expr '/' expr {
                char str[5],str1[5]="t";
                sprintf(str, "%d", temp_var);        
                strcat(str1,str);
                temp_var++;
                addQuadruple("/",pop(),pop(),str1);
                push(str1);}        
|ID {push($1);}
|NUMBER {  char temp[10];
           sprintf(temp,"%d",$1);    
           push(temp);};

%%
extern FILE *yyin;
int main()
{ 
  Stk.top = -1;
  yyin = fopen("input.txt","r");
  yyparse();
  display_Quadruple();
  printf("\n");
  return(0);
}

void display_Quadruple()
{
  int i;
  printf("The INTERMEDIATE CODE Is:\n");
  printf("The Quadruple Table\n");
  printf("\nResult  Operator  Operand1  Operand2  ");
  for(i=0;i<Index;i++)
    printf("\n %s          %s          %s          %s",QUAD[i].result,QUAD[i].operator,QUAD[i].operand1,QUAD[i].operand2);
}
void yyerror()
{
   printf("\nERROR!!\n");
}

void push(char *str)
{
  Stk.top++;
    Stk.items[Stk.top]=(char *)malloc(strlen(str)+1);
  strcpy(Stk.items[Stk.top],str);
}

char * pop()
{
  int i;
  if(Stk.top==-1)
  {
     printf("\nStack Empty!! \n");
     exit(0);
  }
  char *str=(char *)malloc(strlen(Stk.items[Stk.top])+1);
  strcpy(str,Stk.items[Stk.top]);
  Stk.top--;
  return(str);
}
 void addQuadruple(char op[10],char op2[10],char op1[10],char res[10])
{
strcpy(QUAD[Index].operator,op);
strcpy(QUAD[Index].operand2,op2);
strcpy(QUAD[Index].operand1,op1);
strcpy(QUAD[Index].result,res);
Index++;
}

filename: input.txt

main()
{
int a=10,b,c;
a=10;
b=a;
c=a+10;
c=a+b*a;
}

OUTPUT

[amodi@localhost ~]$ lex my.l
[amodi@localhost ~]$ yacc -d my.y
yacc: 2 shift/reduce conflicts.
[amodi@localhost ~]$ gcc lex.yy.c y.tab.c
[amodi@localhost ~]$ ./a.out
The INTERMEDIATE CODE Is:
The Quadruple Table

Result  Operator  Operand1  Operand2  
 a          =          10          
 b          =          a          
 t0          +          10          a
 c          =          t0          
 t1          *          a          b
 t2          +          t1          a
 c          =          t2          

Parser for sample language using YACC

PROGRAM

file name: a4.l

%{
#include "y.tab.h"
#include<stdio.h>
extern int yylval;
%}

%%
[0-9]+ {yylval=atoi(yytext);return DIGIT;}
"#include <"[.a-zA-Z]*">\n" {return HEADER;}
"{"[\n]* {return STB;}
"}"[\n]* {return ENB;}
";"[\n]* {return ENDS;}
"main()"[\n]* {return MAIN;}
int|char|double {return DTYPE;}
"," {return SEP;}
[+-/*] {return OP;}
"=" {return EQ;}
"(" {return OPB;}
")" {return CLB;}
"if" {return IF;}
"else" {return ELSE;}
"printf("[^\)]*")" {printf("Function call\n");return FUNC;}
"scanf("[^\)]*")" {printf("Function call\n");return FUNC;}
[a-zA-Z][a-zA-Z0-9]* {return VAR;}
[ \t]+ ;

%%

int yywrap()
{
 return 1;
}

a4.y

%{
#include<stdio.h>
extern FILE* yyin;
%}

%token DIGIT VAR OP DTYPE EQ IF ELSE HEADER ENDS SEP OPB CLB STB ENB MAIN FUNC

%%
St: S MAIN STB stmts ENB {printf("Program within main\n");};
S: HEADER S| HEADER {printf("Headers\n");};
stmts: stmt|stmts stmt|;
stmt: IF OPB CLB STB stmts ENB {printf("IF statement\n");};
stmt: IF OPB CLB STB stmts ENB ELSE STB stmts ENB {printf("IF ELSE statement\n");};
stmt: exp|DTYPE varlist ENDS|FUNC ENDS {printf("Statement\n");};
varlist: VAR | varlist SEP VAR ;
exp: VAR EQ dv opn ENDS {printf("Expression\n");};
dv: DIGIT| VAR
opn: OP dv|OP dv opn|;
%%

void yyerror(char *s)
{
 printf("Incorrect syntax\n");
}

main()
{
char filename[20];
printf("Enter file name: ");
scanf("%s",filename);
yyin=fopen(filename,"r");
yyparse();
}


main.c

#include <stdio.h>
#include <iostream.h>
#include <math.h>
main()
{
printf("Hello");
int a,b,c;
c=5;
b=7+c;
scanf("%d",a);

if()
{
}

if()
{
}
else
{
}
}


OUTPUT

[amodi@localhost ~]$ lex a4.l
[amodi@localhost ~]$ yacc -d a4.y
yacc: 12 shift/reduce conflicts, 1 reduce/reduce conflict.
[amodi@localhost ~]$ gcc lex.yy.c y.tab.c
[amodi@localhost ~]$ ./a.out
Enter file name: main.c
Headers
Function call
Statement
Expression
Expression
Function call
Statement

IF statement


IF ELSE statement
Program within main

Lexical analyser for sample language using LEX

PROGRAM

file name a3.l

%{
#include<stdio.h>
#include<string.h>
char err[20][50],name[20][20];
int lno=1,cnt=0,ecnt=0,elno[20];
%}

%%
[0-9]+ {printf("%d %s Number\n",lno,yytext);}
[+-/*] {printf("%d %s Operator\n",lno,yytext);}
= {printf("%d %s Assignment\n",lno,yytext);}
main|return|include {printf("%d %s Keyword\n",lno,yytext);}
int|double|char|float {printf("%d %s Data type\n",lno,yytext);}
[\t ]      ;
\n {lno++;}
(\/\/.*) ;
(\/\*[^*/]*\*\/) ;
(\/\*[^*/]*) {elno[ecnt]=lno;char str[100]="Unterminated comment";strcpy(err[ecnt],str);ecnt++;}
printf|scanf {printf("%d %s Library function\n",lno,yytext);}
[a-z]+[a-zA-Z0-9]* {printf("%d %s Identifier\n",lno,yytext);st_add(yytext);}
([a-zA-Z0-9]+\.h) {printf("%d %s Header\n",lno,yytext);}
\( {printf("%d %s Open bracket\n",lno,yytext);}
\) {printf("%d %s Close bracket\n",lno,yytext);}
\< {printf("%d %s Less than\n",lno,yytext);}
\> {printf("%d %s Greater than\n",lno,yytext);}
\{ {printf("%d %s Block start\n",lno,yytext);}
\} {printf("%d %s Block end\n",lno,yytext);}
# {printf("%d %s Preprocessor\n",lno,yytext);}
; {printf("%d %s Terminator\n",lno,yytext);}
(\"[^\"]*\") {printf("%d %s String literal\n",lno,yytext);}
(\"[^\"\n]*\n) {elno[ecnt]=lno;char str[100]="Unterminated quote";strcpy(err[ecnt],str);ecnt++;lno++;}

[0-9]+[a-zA-z]* {elno[ecnt]=lno;char str[100]="Unrecognized token";strcpy(err[ecnt],str);ecnt++;}
%%
void st_add(char s[20])
{
int i;
for(i=0;i<cnt;i++)
{
if(strcmp(name[i],s)==0)
return;
}
strcpy(name[cnt],s);
cnt++;
}
main()
{
char file[20];
printf("Enter file name:");
scanf("%s",file);
yyin=fopen(file,"r");
printf("Line No. Lexeme Token\n");
yylex();

printf("Number of errors: %d\n",ecnt);
int i=0;
for(i=0;i<ecnt;i++)
 printf("Line no.: %2d %s\n",elno[i],err[i]);

printf("Symbol Table\n");
for(i=0;i<cnt;i++)
 printf("%s\n",name[i]);
return 0;
}

int yywrap()
{
return 1;
}


main.c

#include<stdio.h>
int main() 
{
6s
int a = 1;
float b=0;
printf(");
return 0;
/*
}


OUTPUT

[amodi@localhost ~]$ lex a3.l
[amodi@localhost ~]$ gcc lex.yy.c
a3.l:36:6: warning: conflicting types for ‘st_add’ [enabled by default]
 {
      ^
a3.l:20:42: note: previous implicit declaration of ‘st_add’ was here
 [a-z]+[a-zA-Z0-9]* {printf("%d %s Identifier\n",lno,yytext);st_add(yytext);}
                                          ^
[amodi@localhost ~]$ ./a.out
Enter file name:main.c
Line No. Lexeme Token
1 # Preprocessor
1 include Keyword
1 < Less than
1 stdio.h Header
1 > Greater than
2 int Data type
2 main Keyword
2 ( Open bracket
2 ) Close bracket
3 { Block start
5 int Data type
5 a Identifier
5 = Assignment
5 1 Number
5 ; Terminator
6 float Data type
6 b Identifier
6 = Assignment
6 0 Number
6 ; Terminator
7 printf Library function
7 ( Open bracket
8 return Keyword
8 0 Number
8 ; Terminator
Number of errors: 3
Line no.:  4 Unrecognized token
Line no.:  7 Unterminated quote
Line no.:  9 Unterminated comment
Symbol Table
a
b

Using Divide and Conquer Strategies design a class for Concurrent Quick Sort using C++

PROGRAM

file name a2.cpp

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<pthread.h>
using namespace std;

struct array
{
 int *arr;
 int first;
 int last;
};
int n;

void* quick(void *in)
{
array* a=(array*)in;
int i,j;
pthread_t id=pthread_self();
if(a->first < a->last)
{
int temp=0;
int i=a->first;
int j=a->last;
int pivot=a->arr[a->first];
while(i<j)
{
 while(a->arr[i] <=pivot && i<j)
 i++;
 while(a->arr[j] > pivot && i<=j)
 j--;
 if(i<=j)
 {
 temp=a->arr[i];
 a->arr[i]=a->arr[j];
 a->arr[j]=temp;
 }
}
 temp=a->arr[j];
 a->arr[j]=a->arr[a->first];
 a->arr[a->first]=temp;

pthread_t threads[2];
cout<<"Thread ID: "<<id<<" for pivot: "<<pivot<<endl;
array a1,a2;
a1.arr=new int[n];
a2.arr=new int[n];
a1.arr=a->arr;
a2.arr=a->arr;
a1.first=a->first;
a1.last=j-1;
a2.first=j+1;
a2.last=a->last;
pthread_create(&threads[0],NULL,&quick,(void *)&a1);
pthread_create(&threads[1],NULL,&quick,(void *)&a2);
pthread_join(threads[0],NULL);
pthread_join(threads[1],NULL);
}
}

int main()
{
array a1;
int n,i;
cout<<"Enter size of array: ";
cin>>n;
a1.arr=new int[n];
a1.first=0;
a1.last=n-1;
cout<<"Enter elements:"<<endl;
for(i=0;i<n;i++)
 cin>>a1.arr[i];
quick(&a1);
cout<<"Sorted array is:"<<endl;
for(i=0;i<n;i++)
 cout<<a1.arr[i]<<" ";
cout<<endl;
return 0;
}


OUTPUT

[amodi@localhost ~]$ g++ a2.cpp -pthread
[amodi@localhost ~]$ ./a.out
Enter size of array: 4
Enter elements:
23
42
73
25
Thread ID: 140425762199424 for pivot: 23
Thread ID: 140425753798400 for pivot: 42
Sorted array is:
23 25 42 73 

Using Divide and Conquer Strategies design a function for Binary Search using C

PROGRAM

file name: a1.scala

import scala.util.control._

object a1
{
def main(args: Array[String])
{
 var n=0
 println("Enter size of array:")
 n=Console.readInt()
 var arr=new Array[Int](n)
 var ch=1
 println("Enter array elements:")
 for(i <- 0 to n-1)
 arr(i)=Console.readInt()
 var temp=0
 for(i <- 0 to n-1)
 {
  for(j <- i+1 to n-1)
  {
   if(arr(i)>arr(j))
   {
    temp=arr(i)
    arr(i)=arr(j)
    arr(j)=temp
   }
  } 
 }
 while(ch!=0)
 {
  var flag=binary(arr,n)
  if(flag== -1)
    println("Number not found")
  else
   println("Number found at index: "+flag)
  println("1. to continue  0. to exit")
  ch=Console.readInt()
 }
}

def binary(arr:Array[Int],n:Int):Int=
{
 println("Sorted array is:")
  for(i <- arr)
 println(i)
 println("Enter number to search")
 var s=Console.readInt()
 var loop= new Breaks;
 var result= -1
 var lb=0
var ub=n-1
var mid=(lb+ub)/2
loop.breakable
{ 
while(lb<=ub)
 {
mid=(lb+ub)/2
 if(s<arr(mid)) 
  ub=mid-1
 else if(s>arr(mid))
  lb=mid+1
 else
  {
   result=mid
   loop.break;
  }
 }
}
return result;
}


}


OUTPUT

Amols-Air:type2 Darwin$ scalac a1.scala
warning: there were four deprecation warnings; re-run with -deprecation for details
one warning found
Amols-Air:type2 Darwin$ scala a1
Enter size of array:
4
Enter array elements:
1
2
4
3
Sorted array is:
1
2
3
4
Enter number to search
3
Number found at index: 2
1. to continue  0. to exit
0