Skip to content

Instantly share code, notes, and snippets.

@viniru
Created July 28, 2018 18:13
Show Gist options
  • Save viniru/24df0793d51c8e37d2f68602067e2fcd to your computer and use it in GitHub Desktop.
Save viniru/24df0793d51c8e37d2f68602067e2fcd to your computer and use it in GitHub Desktop.
Clustering problem
import java.util.*;
import java.io.File;
public class ClusterB {
int n;
int bitsn;
int clusters ;
HashMap<String,Nodes> cl = new HashMap<>();
void getInput() {
try {
File f = new File("C:\\Users\\vinir_000\\IdeaProjects\\Learn\\src\\input.txt");
Scanner sc = new Scanner(f);
//Scanner sc = new Scanner(System.in);
n = sc.nextInt();
bitsn = sc.nextInt();
clusters = n;
sc.nextLine();
for (int i = 0; i < n; i++) {
String s = sc.nextLine().replaceAll("\\s+", "");
if (!cl.containsKey(s)) {
Nodes n = new Nodes(s);
cl.put(s, n);
}
//else System.out.println("I am present man");
}
clusters = cl.size();
}
catch(Exception e){}
}
void compute()
{
//generate all the nodes at distances 1
for(String s : cl.keySet())
{
for(int i=0;i<bitsn;i++ )
{
StringBuilder x = new StringBuilder(s);
if(x.charAt(i) == '1' )
x.setCharAt(i,'0');
else
x.setCharAt(i,'1');
String y = new String(x.toString());
merge(s,y);
}
}
//generate all the nodes at distances 2
for(String s : cl.keySet())
{
for(int i=0;i<bitsn-1;i++ )
{
for(int j=i+1;j<bitsn;j++)
{
StringBuilder x = new StringBuilder(s);
if (x.charAt(i) == '1')
x.setCharAt(i, '0');
else
x.setCharAt(i, '1');
if (x.charAt(j) == '1')
x.setCharAt(j, '0');
else
x.setCharAt(j, '1');
String y = new String(x.toString());
merge(s, y);
}
}
}
}
void merge(String x,String y)
{
if(cl.containsKey(y))
{
Nodes xp = getParent(x);
Nodes yp = getParent(y);
if(xp != yp) {
int xr = xp.rank;
int yr = yp.rank;
if (xr > yr)
yp.parent = xp;
else if (xr < yr)
xp.parent = yp;
else {
yp.parent = xp;
xp.rank = xp.rank + 1;
}
clusters--;
}
//System.out.println(clusters);
}
}
Nodes getParent(String x)
{
if(cl.get(x).parent == cl.get(x))
return cl.get(x);
cl.get(x).parent = getParent(cl.get(x).parent.s);
return cl.get(x).parent;
}
public static void main(String args[]) {
ClusterB cb = new ClusterB();
cb.getInput();
cb.compute();
System.out.print(cb.clusters);
}
}
class Nodes
{
String s;
Nodes parent ;
int rank = 0;
Nodes(String s)
{
rank = 0;
this.s = s;
parent = this;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment