# Minimizing number of field lamps

This program attempts to solve the following challenge:

There is a 2D grid of cells containing N lamps. Each lamp illuminates its own cell as well as its eight neighbours. How many lamps can you possibly remove such that each cell that was originally illuminated remains illuminated?

My code:

import java.util.*;

class test
{
public static void main(String[] ar)
{
int use = 0;
Scanner sc = new Scanner(System.in);
System.out.print("Enter the dimensions: ");
int a = sc.nextInt();
int b = sc.nextInt();
int[][] f = new int[a][b];
System.out.print("Enter the no. of lamps: ");
int n = sc.nextInt();
int[][] l = new int[n][2];
//System.out.print("Enter the coordinates : ");
for(int i = 0; i < n; i++)
{
int t1,t2;
do
{
t1 = l[i][0] = (int)(Math.random()*a);
t2 = l[i][1] = (int)(Math.random()*b);
f[t1][t2] = 1;
}while(f[t1][t2] == 0);
}
print(f);
light(f);
for(int i = 0; i < l.length; i++)
{
int[][] f1 = new int[a][b];
for(int j = 0; j < l.length; j++)
{
if(i == j)
continue;
int x = l[j][0];
int y = l[j][1];
if(x < 0)
continue;
f1[x][y] = 1;
}
light(f1);
if(!same(f,f1))
use++;
else
{
l[i][0] = -1;
l[i][1] = -1;
}
}
System.out.println("Usefull : " + use);

}

public static boolean same(int[][] a, int[][] b)
{
for(int i = 0; i < a.length; i++)
{
for(int j = 0; j < a[i].length ; j++)
{
if(a[i][j] != b[i][j])
return false;
}
}
return true;
}

public static void print(int[][] a)
{
for(int i = 0; i < a.length ; i++)
{
for(int j = 0; j < a[i].length; j++)
System.out.print(a[i][j] + " ");
System.out.println();
}
System.out.println();
}

public static void light(int[][] a)
{
for(int i = 0;i < a.length; i++)
{
for(int j = 0; j < a[i].length; j++)
{
if(a[i][j] == 1)
light(a,i,j);
}
}
convert(a);
}

public static void light(int[][] a, int i, int j)
{
for(int p = i - 1; p <= i + 1; p++)
{
for(int q = j - 1; q <= j + 1; q++)
{
try
{
if(a[p][q] != 1)
a[p][q] = 2;
}catch(Exception e){}
}
}
}

public static void convert(int[][] a)
{
for(int i = 0; i < a.length; i++)
{
for(int j = 0; j < a[i].length; j++)
{
if(a[i][j] == 2)
a[i][j] = 1;
}
}
}
}


Your algorithm is faulty, because it only tries to eliminate redundant lamps in the order in which they were installed.

Consider a 1 × 9 array with 7 initial lamps L0 … L6 at positions 2 … 8.

Your algorithm would first eliminate L0 at position 5, then L1 at position 4. It would consider L2 and L3 essential. Then it would eliminate L4 at position 7. L5 and L6 would be essential. Total lamps eliminated: three.

An optimal solution would eliminate four lamps at positions 3, 4, 6, 7.

• @200_sucess A lamp also illuminates its own cell. – user2369284 Dec 31 '13 at 2:51
• Please advise how to solve this problem – user2369284 Dec 31 '13 at 2:53
• I know, a lamp also illuminates its own cell. – 200_success Dec 31 '13 at 2:56
• I believe this problem is equivalent to finding a minimum vertex cover of a graph whose vertices are lamps and their neighbouring cells, and whose edges link lamps to their illuminated neighbours. Guess what — it's an NP-hard problem! – 200_success Dec 31 '13 at 3:25
• That's not how this site works. Asking for code to be written is off-topic (see help center). – 200_success Dec 31 '13 at 8:32
import java.util.*;


Importing whole packages is not a very good idea, especially of there are multiple identical named classes in the imported packages. You should only import what is needed.

class test
{


Classnames in Java are UpperCamelCase. Additionally Java normally uses a modified K&R style with the opening braces on the same line.

function style() {
if (true) {
// code
} else {
// code
}
}


public static void main(String[] ar)
{
int use = 0;
Scanner sc = new Scanner(System.in);
System.out.print("Enter the dimensions: ");
int a = sc.nextInt();
int b = sc.nextInt();
int[][] f = new int[a][b];


Do you have an illness that makes typing hurt? There is zero reason to shorten variable names and there is no excuse to only use one-letter variables (only exception are dimensions, x y z and mathematical formulas). Your code is hard to read and reads more like it was obfuscated.

Whenever you have the urge to give a variable a one-letter-name, stop, take a deep breath, and then you name the variable according to what it does.

for(int i = 0; i < n; i++)
{
// snip
do
{
// snip
}while(f[t1][t2] == 0);
}


Your brace and indentation style is a mess, to be honest. This is very hard to read, f.e. while quick scanning the code I thought it would be such a construct:

for (loop-stuff)
{

} while (loop stuff)


A "one-line-for-loop" with an embedded while...and my next thought was "wait, that's legal in Java?". It would be easier to read like this:

for(int i = 0; i < n; i++) {
// snip
do {
// snip
}while(f[t1][t2] == 0);
}


public static boolean same(int[][] a, int[][] b)


Not bad, but a better name would be areEqual or equal.

public static void light(...)


This is a bad function name, it tells me nothing about what the function does.

if(a[p][q] != 1)
a[p][q] = 2;


And see, this is why one-letter-names are bad. Quick! Tell me what it does?!

Also, you should avoid magic numbers at all costs. Java has Enums, use them.

To be honest, I can't really comment anything else on your code, with the one-letter-variables, odd brace-style and the not really well named functions, I can't tell what's going on.

• Re: Additionally Java normally uses a modified K&R style with the opening braces on the same line.- even so, who cares? Use whatever style you feel comfortable with as long as it's readable. – MrLore Dec 30 '13 at 21:27
• Actually, do { …; f[t1][t2] = 1; } while (f[t1][t2] == 0); is not a loop at all! It will always execute exactly once. – 200_success Dec 30 '13 at 22:21
• @MrLore: I always mention it because that's what is defined in the Java Documentation as default style. It's a good move to try to unify that, and if you don't have a compelling reason not to follow these guidelines, you should stick to them. It's like premature optimization, if you don't have a compelling reason to strive from it, you shouldn't. "I prefer that other style for clarity because ..." is a compelling reason, "I don't care" or "I did use that other style in that other language, I'm used to it" is not. – Bobby Dec 30 '13 at 22:42