10
\$\begingroup\$

Farmer Jack is very poor. He wants to light his whole farm but with minimum of cost. A lamp can illuminate its own cell as well as its eight neighbors . He has arranged the lamps in his field but he needs your help in finding out whether or not he has kept any extra lamps.

Extra lamps : Lamps which on removing from the farm will make no difference to the number of cells lit. Also, the lamps you will point will not be removed one by one, but they will be removed simultaneously.

Note: The only action you can perform is to remove some lamps. You can neither rearrange nor insert lamps. Your final target is to remove maximum number of lamps such that every cell which was lit before is still lit.

Help Farmer Jack in spotting the maximum number of useless lamps so that he can use them elsewhere.

Input

You will be given in the first line dimensions of the field M and N.Next M lines follow containing N characters each representing the field.

'1' represents cell where lamp is kept.

'0' represents an empty cell.

Output

You have to output an integer containing number of useless lamps.

Sample Input:

3 3
100
010
001

Sample Output:

2

Winner:

Since it is code golf, winner will be the one who will successfully complete the task in least number of characters

\$\endgroup\$
12
  • \$\begingroup\$ @PeterTaylor I have edited my post. Do you still have a confusion? \$\endgroup\$ Jan 1, 2014 at 19:24
  • \$\begingroup\$ may we assume the input ends with a newline? \$\endgroup\$ Jan 1, 2014 at 19:51
  • \$\begingroup\$ Yes sure, you can do that \$\endgroup\$ Jan 1, 2014 at 19:53
  • 1
    \$\begingroup\$ This looks like homework. \$\endgroup\$
    – Johannes
    Jan 1, 2014 at 23:34
  • 1
    \$\begingroup\$ Are we guaranteed that the input lamps will light the whole farm? I'm going to guess no... \$\endgroup\$ Jan 2, 2014 at 5:04

9 Answers 9

5
\$\begingroup\$

Mathematica 186 (greedy) and 224 (all combinations)

Greedy Solution

t=MorphologicalTransform;n@w_:=Flatten@w~Count~1
p_~w~q_:=n[p~t~Max]==n[q~t~Max]
g@m_:=Module[{l=m~Position~1,r,d=m},While[l!={},If[w[m,r=ReplacePart[d,#-> 0]&    
[l[[1]]]],d=r];l=Rest@l];n@m-n@d]

This turns off superfluous lights one by one. If the light coverage is not diminished when the light goes off, that light can be eliminated. The greedy approach is very fast and can easily handle matrices of 15x15 and much larger (see below). It returns a single solutions, but it is unknown whether that is optimal or not. Both approaches, in the golfed versions, return the number of unused lights. Un-golfed approaches also display the grids, as below.

Before:

before

After:

after

Optimal Solutions using all combinations of lights (224 chars)

With thanks to @Clément.

Ungolfed version using all combinations of lights

fThe morphological transform function used in sameCoverageQ treats as lit (value = 1 instead of zero) the 3 x3 square in which each light resides.When a light is near the edge of the farm, only the squares (less than 9) within the borders of the farm are counted.There is no overcounting; a square lit by more than one lamp is simply lit.The program turns off each light and checks to see if the overall lighting coverage on the farm is reduced.If it is not, that light is eliminated.

nOnes[w_]:=Count[Flatten@w,1]
sameCoverageQ[m1_,m2_]:=nOnes[MorphologicalTransform[m1,Max]]==
  nOnes[MorphologicalTransform[m2,Max]]

(*draws a grid with light bulbs *)
h[m_]:=Grid[m/.{1-> Style[\[LightBulb],24],0-> ""},Frame-> All,ItemSize->{1,1.5}]

c[m1_]:=GatherBy[Cases[{nOnes[MorphologicalTransform[ReplacePart[Array[0&,Dimensions[m1]],
#/.{{j_Integer,k_}:> {j,k}-> 1}],Max]],#,Length@#}&/@(Rest@Subsets[Position[m1,1]]),
{nOnes[MorphologicalTransform[m1,Max]],_,_}],Last][[1,All,2]]

nOnes[matrix] counts the number of flagged cells. It is used to count the lights and also to count the lit cells

sameCoverageQ[mat1, mat2] tests whether the lit cells in mat1 equals the number of lit cells in mat2.MorphologicalTransform[[mat] takes a matrix of lights and returns a matrix` of the cells they light up.

c[m1] takes all combinations of lights from m1 and tests them for coverage. Among those that have the maximum coverage, it selects those that have the fewest light bulbs. Each of these is an optimal solution.


Example 1:

A 6x6 setup

(*all the lights *)
m=Array[RandomInteger[4]&,{6,6}]/.{2-> 0,3->0,4->0}
h[m]

original

All optimal solutions.

(*subsets of lights that provide full coverage *)
h/@(ReplacePart[Array[0&,Dimensions[m]],#/.{{j_Integer,k_}:> {j,k}-> 1}]&/@(c[m]))

answers


Golfed version using all combinations of lights.

This version calculates the number of unused lights. It does not display the grids.

c returns the number of unused lights.

n@w_:=Flatten@w~Count~1;t=MorphologicalTransform;
c@r_:=n@m-GatherBy[Cases[{n@t[ReplacePart[Array[0 &,Dimensions[r]],#
/.{{j_Integer,k_}:> {j,k}-> 1}],Max],#,Length@#}&/@(Rest@Subsets[r~Position~1]),
{n[r~t~Max],_,_}],Last][[1,1,3]]

n[matrix] counts the number of flagged cells. It is used to count the lights and also to count the lit cells

s[mat1, mat2] tests whether the lit cells in mat1 equals the number of lit cells in mat2.t[[mat] takes a matrix of lights and returns a matrix` of the cells they light up.

c[j] takes all combinations of lights from j and tests them for coverage. Among those that have the maximum coverage, it selects those that have the fewest light bulbs. Each of these is an optimal solution.

Example 2

m=Array[RandomInteger[4]&,{6,6}]/.{2-> 0,3->0,4->0};
m//Grid

grid

Two lights can be saved while having the same lighting coverage. c[m]

2

\$\endgroup\$
7
  • \$\begingroup\$ I don't have Mathematica at hand so I can't test this code, but I think your algorithm is incorrect — unless I misunderstood your explanations. If my understanding is correct, it relies on a greedy strategy that is dependent on the order in which light are processed: for example, starting from the middle lamp in your 3*3 test case would remove it and leave the two side lamps. I don't expect that the particular ordering that you use in the implementation makes it correct, but I don't have a counter-example right now. \$\endgroup\$
    – Clément
    Jan 3, 2014 at 23:10
  • \$\begingroup\$ Your idea seems to be that it may be possible to have 2 superfluous lights, a, b, in the original setup, one of which is more superfluous than the other. So, it may be that there is better economy achieved if one is removed (first). I sense that this could not happen with 3 lights total, but it may indeed be possible with greater numbers of lights. I originally solved the problem by testing all combinations of lights. This is certainly optimal and thus ideal, but I found it impractical with a large set of lights. \$\endgroup\$
    – DavidC
    Jan 3, 2014 at 23:30
  • \$\begingroup\$ @Clément I'm working on a solution that will test all possible combinations. Will take a while... \$\endgroup\$
    – DavidC
    Jan 4, 2014 at 0:34
  • \$\begingroup\$ It sure will ;) But that's to be expected: as it stands this problem is an instance of the minimum set cover — which is NP. Whether the additional assumptions (almost all covering sets, except the lateral ones, have the same cardinality) allow for an efficient implementation is an interesting problem though. \$\endgroup\$
    – Clément
    Jan 4, 2014 at 2:26
  • \$\begingroup\$ I strongly suspect the greedy solution is correct if you go sequentially by rows and columns, but I haven't proven it yet. \$\endgroup\$ Jan 4, 2014 at 6:18
3
\$\begingroup\$

Python, 309 chars

import sys
I=sys.stdin.readlines()[1:]
X=len(I[0])
L=[]
m=p=1
for c in''.join(I):m|=('\n'!=c)*p;L+=('1'==c)*[p<<X+1|p<<X|p<<X-1|p*2|p|p/2|p>>X-1|p>>X|p>>X+1];p*=2
O=lambda a:m&reduce(lambda x,y:x|y,a,0)
print len(L)-min(bin(i).count('1')for i in range(1<<len(L))if O(L)==O(x for j,x in enumerate(L)if i>>j&1))

Works using bitmasks. L is a list of the lights, where each light is represented by an integer with (up to) 9 bits set for its light pattern. Then we exhaustively search for subsets of this list whose bitwise-or is the same as the bitwise-or of the whole list. The shortest subset is the winner.

m is a mask that prevents wraparound of the bits when shifting.

\$\endgroup\$
4
  • \$\begingroup\$ Please try to provide a program which runs correctly.Java/C++ are safe to any kind of indentation or spacing but Python is not.Obfuscating or shortening code is another thing but providing a program which does not run is another. \$\endgroup\$ Jan 2, 2014 at 9:01
  • 3
    \$\begingroup\$ @user2369284 what are you talking about?! It works perfectly fine (with python 2) \$\endgroup\$ Jan 2, 2014 at 9:05
  • \$\begingroup\$ @aditsu I have python 3. \$\endgroup\$ Jan 2, 2014 at 9:08
  • 1
    \$\begingroup\$ @user2369284 well, the print syntax is different so it fails in python 3 \$\endgroup\$ Jan 2, 2014 at 9:47
3
\$\begingroup\$

Java 6 - 509 bytes

I made some assumptions about the limits and solved the problem as stated at this time.

import java.util.*;enum F{X;{Scanner s=new Scanner(System.in);int m=s.nextInt(),n=s.nextInt(),i=m,j,k=0,l=0,r=0,o,c,x[]=new int[30],y[]=x.clone();int[][]a=new
int[99][99],b;while(i-->0){String t=s.next();for(j=n;j-->0;)if(t.charAt(j)>48){x[l]=i;y[l++]=j;}}for(;k<l;++k)for(i=9;i-->0;)a[x[k]+i/3][y[k]+i%3]=1;for(k=1<<l;k-->0;){b=new
int[99][99];for(j=c=l;j-->0;)if((k&1<<j)>0)for(c--,i=9;i-->0;)b[x[j]+i/3][y[j]+i%3]=1;for(o=i=0;i++<m;)for(j=0;j++<n;)o|=a[i][j]^b[i][j];r=c-o*c>r?c:r;}System.out.println(r);}}

Run like this: java F <inputfile 2>/dev/null

\$\endgroup\$
6
  • \$\begingroup\$ Not exactly short, but fits in a disk sector :p I may try a different language later. \$\endgroup\$ Jan 2, 2014 at 2:47
  • \$\begingroup\$ @aditsu How to make this work on windows? \$\endgroup\$ Jan 2, 2014 at 4:06
  • 1
    \$\begingroup\$ @user2369284: I don't see how you can do 0011111100 with only 2 lamps. You need to cover 8 cells with light, and each lamp can do at most 3. \$\endgroup\$ Jan 2, 2014 at 5:07
  • \$\begingroup\$ @user2369284 perhaps java F <inputfile 2>nul, if that fails then java F <inputfile and ignore the exception. Also it won't run with java 7. \$\endgroup\$ Jan 2, 2014 at 6:19
  • \$\begingroup\$ @aditsu I'm really sorry.That was a typo error. Your program works correctly. \$\endgroup\$ Jan 2, 2014 at 9:07
1
\$\begingroup\$

c++ - 477 bytes

#include <iostream>
using namespace std;int main(){
int c,i,j,m,n,p,q=0;cin>>m>>n;
int f[m*n],g[m*n],h[9]={0,-1,1,-m-1,-m,-m+1,m-1,m,m+1};
for(i=0;i<m*n;i++){f[i]=0;g[i]=0;do{c=getchar();f[i]=c-48;}while(c!='0'&&c!='1');}
for(i=0;i<m*n;i++)if(f[i])for(j=0;j<9;j++)if(i+h[j]>=0&&i+h[j]<m*n)g[i+h[j]]++;
for(i=0;i<m*n;i++)if(f[i]){p=0;for(j=0;j<9;j++)if(i+h[j]>=0&&i+h[j]<m*n)if(g[i+h[j]]<2)p++;if(p==0){for(j=0;j<9;j++)if(i+h[j]>=0&&i+h[j]<m*n)g[i+h[j]]--;q++;}}cout<<q<<endl;}
\$\endgroup\$
1
\$\begingroup\$

Ruby, 303

[this was coded to answer a previous version of the question; read note below]

def b(f,m,n,r)b=[!1]*1e6;(n..n+m*n+m).each{|i|b[i-n-2,3]=b[i-1,3]=b[i+n,3]=[1]*3if f[i]};b[r*n+r+n+1,n];end
m,n=gets.split.map(&:to_i)
f=[!1]*n
m.times{(?0+gets).chars{|c|f<<(c==?1)if c>?*}}
f+=[!u=0]*n*n
f.size.times{|i|g=f.dup;g[i]?(g[i]=!1;u+=1if m.times{|r|break !1if b(f,m,n,r)!=b(g,m,n,r)}):0}
p u

Converting to arrays of Booleans and then comparing neighbourhoods for changes.

Limitation(?): Maximum farm field size is 1,000 x 1,000. Problem states "Farmer Jack is very poor" so I'm assuming his farm isn't larger. ;-) Limitation can be removed by adding 2 chars.

NOTE: Since I began coding this, it appears the question requirements changed. The following clarification was added "the lamps you will point will not be removed one by one, but they will be removed simultaneously". The ambiguity of the original question allowed me to save some code by testing individual lamp removals. Thus, my solution will not work for many test cases under the new requirements. If I have time, I will fix this. I may not. Please do not upvote this answer since other answers here may be fully compliant.

\$\endgroup\$
1
\$\begingroup\$

APL, 97 chars/bytes*

Assumes a ⎕IO←1 and ⎕ML←3 APL environment.

m←{s↑⊃∨/,v∘.⊖(v←⍳3)⌽¨⊂0⍪0⍪0,0,s⍴⍵}⋄n-⌊/+/¨t/⍨(⊂m f)≡¨m¨(⊂,f)\¨t←⊂[1](n⍴2)⊤⍳2*n←+/,f←⍎¨⊃{⍞}¨⍳↑s←⍎⍞

Ungolfed version:

s ← ⍎⍞                                         ⍝ read shape of field
f ← ⍎¨ ⊃ {⍞}¨ ⍳↑s                              ⍝ read original field (lamp layout)
n ← +/,f                                       ⍝ original number of lamps
c ← ⊂[1] (n⍴2) ⊤ ⍳2*n                          ⍝ all possible shutdown combinations
m ← {s↑ ⊃ ∨/ ,v ∘.⊖ (v←⍳3) ⌽¨ ⊂ 0⍪0⍪0,0, s⍴⍵}  ⍝ get lighted cells given a ravelled field
l ← m¨ (⊂,f) \¨ c                              ⍝ map of lighted cells for every combination
k ← c /⍨ (⊂ m f) ≡¨ l                          ⍝ list of successful combinations
u ← ⌊/ +/¨ k                                   ⍝ min lamps used by a successful comb.
⎕ ← n-u                                        ⍝ output number of useless lamps

⎕ ← s⍴ ⊃ (⊂,f) \¨ (u= +/¨ k) / k               ⍝ additional: print the layout with min lamps

I agree that more test cases would be better. Here's a random one:

Input:

5 5
10001
01100
00001
11001
00010

Output (useless lamps):

5

Layout with min lamps (not included in golfed version):

0 0 0 0 1
0 1 0 0 0
0 0 0 0 0
0 1 0 0 1
0 0 0 0 0

⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯
*: APL can be written in its own (legacy) single-byte charset that maps APL symbols to the upper 128 byte values. Therefore, for the purpose of scoring, a program of N chars that only uses ASCII characters and APL symbols can be considered to be N bytes long.

\$\endgroup\$
0
\$\begingroup\$

C++ 5.806 Bytes

This is not optimized for size yet. But since there are few contestants i will leave it at that for now.

FarmersField Header:

#pragma once

namespace FarmersLand
{

class FarmersField
{
private:
    unsigned _m_size, _n_size;
    int * _lamp, * _lumination;
    char * _buffer;
    void _illuminate(unsigned m, unsigned n);
    void _deluminate(unsigned m, unsigned n);
    void _removeLamp(unsigned m, unsigned n);
    void _setLamp(unsigned m, unsigned n);
    int _canRemoveLamp(unsigned m, unsigned n);
    int _coordsAreValid(unsigned m, unsigned n);
    int _getLuminationLevel(unsigned m, unsigned n);
    int * _allocIntArray(unsigned m, unsigned n);
    int _coordHelper(unsigned m, unsigned n);
public:
    FarmersField(char * input[]);
    FarmersField(const FarmersField & field);
    ~FarmersField(void);
    int RemoveLamps(void);
    char * Cstr(void);
};

}

FarmersField CPP:

#include "FarmersField.h"
#include <stdio.h>


namespace FarmersLand
{

void FarmersField::_illuminate(unsigned m, unsigned n)
{
    if(this -> _coordsAreValid(m,n))
    {
        ++this -> _lumination[this -> _coordHelper(m,n)];
    }
}

void FarmersField::_deluminate(unsigned m, unsigned n)
{
    if(this -> _coordsAreValid(m,n))
    {
        --this -> _lumination[this -> _coordHelper(m,n)];
    }
}

void FarmersField::_removeLamp(unsigned m, unsigned n)
{
    if(this -> _coordsAreValid(m,n))
    {
        unsigned mi_start = (m == 0) ? 0 : m - 1;
        unsigned mi_end = m + 1;
        unsigned ni_start = (n == 0) ? 0 : n - 1;
        unsigned ni_end = n + 1;

        for(unsigned mi = mi_start; mi <= mi_end; ++mi)
        {
            for(unsigned ni = ni_start; ni <= ni_end; ++ni)
            {
                this -> _deluminate(mi, ni);
            }
        }
        --this -> _lamp[this -> _coordHelper(m,n)];
    }
}

void FarmersField::_setLamp(unsigned m, unsigned n)
{
    if(this -> _coordsAreValid(m,n))
    {
        unsigned mi_start = (m == 0) ? 0 : m - 1;
        unsigned mi_end = m + 1;
        unsigned ni_start = (n == 0) ? 0 : n - 1;
        unsigned ni_end = n + 1;

        for(unsigned mi = mi_start; mi <= mi_end; ++mi)
        {
            for(unsigned ni = ni_start; ni <= ni_end; ++ni)
            {
                this -> _illuminate(mi, ni);
            }
        }
        ++this -> _lamp[this -> _coordHelper(m,n)];
    }
}

int FarmersField::_canRemoveLamp(unsigned m, unsigned n)
{
    unsigned can = 1;
    unsigned mi_start = (m == 0) ? 0 : m - 1;
    unsigned mi_end =   (m == (this->_m_size - 1)) ? m : m + 1;
    unsigned ni_start = (n == 0) ? 0 : n - 1;
    unsigned ni_end =   (n == (this->_n_size - 1)) ? n : n + 1;

    for(unsigned mi = mi_start; mi <= mi_end; ++mi)
    {
        for(unsigned ni = ni_start; ni <= ni_end; ++ni)
        {
            if( 1 >= this -> _getLuminationLevel(mi, ni) )
            {
                can = 0;
            }
        }
    }
    return can;
}

int FarmersField::_coordsAreValid(unsigned m, unsigned n)
{
    return m < this -> _m_size && n < this -> _n_size;
}

int FarmersField::_getLuminationLevel(unsigned m, unsigned n)
{
    if(this -> _coordsAreValid(m,n))
    {
        return this -> _lumination[this -> _coordHelper(m,n)];
    }
    else
    {
        return 0;
    }
}

int * FarmersField::_allocIntArray(unsigned m, unsigned n)
{
    int * a = new int[m * n];
    for(unsigned i = 0; i < m*n; ++i)
    {
        a[i] = 0;
    }
    return a;
}

int FarmersField::_coordHelper(unsigned m, unsigned n)
{
    return m * this -> _n_size + n;
}

int FarmersField::RemoveLamps(void)
{
    int r = 0;
    for(unsigned m = 0 ; m < this -> _m_size; ++m)
    {
        for(unsigned n = 0 ; n < this -> _n_size; ++n)
        {
            if(this -> _canRemoveLamp(m,n))
            {
                ++r;
                this -> _removeLamp(m,n);
            }
        }
    }
    return r;
}

char * FarmersField::Cstr(void)
{
    unsigned size = this -> _m_size * this -> _n_size + _m_size ;
    unsigned target = 0;
    delete(this -> _buffer);
    this -> _buffer = new char[ size ];
    for(unsigned m = 0 ; m < this -> _m_size; ++m)
    {
        for(unsigned n = 0 ; n < this -> _n_size; ++n)
        {
            this -> _buffer[target++] =  (0 == this -> _lamp[this -> _coordHelper(m,n)])? '0' : '1';
        }
        this -> _buffer[target++] = '-'; 
    }
    this -> _buffer[size - 1 ] = 0;
    return this -> _buffer;
}

FarmersField::FarmersField(char * input[])
{
    sscanf_s(input[0], "%u %u", &this -> _m_size, &this -> _n_size);

    this -> _lamp = this -> _allocIntArray(this -> _m_size, this -> _n_size);
    this -> _lumination = this -> _allocIntArray(this -> _m_size, this -> _n_size);
    this -> _buffer = new char[1];

    for(unsigned m = 0 ; m < this -> _m_size; ++m)
    {
        for(unsigned n = 0 ; n < this -> _n_size; ++n)
        {
            if('0' != input[m+1][n])
            {
                this -> _setLamp(m,n);
            }
        }
    }
}

FarmersField::FarmersField(const FarmersField & field)
{
    this -> _m_size = field._m_size;
    this -> _n_size = field._n_size;

    this -> _lamp = this -> _allocIntArray(this -> _m_size, this -> _n_size);
    this -> _lumination = this -> _allocIntArray(this -> _m_size, this -> _n_size);
    this -> _buffer = new char[1];

    for(unsigned m = 0 ; m < this -> _m_size; ++m)
    {
        for(unsigned n = 0 ; n < this -> _n_size; ++n)
        {
            if(0 != field._lamp[this -> _coordHelper(m,n)])
            {
                this -> _setLamp(m,n);
            }
        }
    }

}

FarmersField::~FarmersField(void)
{
    delete(this -> _lamp);
    delete(this -> _lumination);
    delete(this -> _buffer);
}

}

And a set of tests to show that the code does what it was built to do:

#include "../../Utility/GTest/gtest.h"

#include "FarmersField.h"

TEST(FarmersField, Example1) 
{
    using namespace FarmersLand;
    char * input[] = {"3 3", "100", "010", "001"};
    FarmersField f(input);
    EXPECT_STREQ("100-010-001", f.Cstr());
    EXPECT_EQ(2, f.RemoveLamps());
    EXPECT_STREQ("000-010-000", f.Cstr());
}

TEST(FarmersField, Example2) 
{
    using namespace FarmersLand;
    char * input[] = {"3 6", "100000", "010000", "001000"};
    FarmersField f(input);
    EXPECT_STREQ("100000-010000-001000", f.Cstr());
    EXPECT_EQ(1, f.RemoveLamps());
    EXPECT_STREQ("000000-010000-001000", f.Cstr());
 }

TEST(FarmersField, Example3) 
{
    using namespace FarmersLand;
    char * input[] = {"6 3", "100", "010", "001", "000", "000", "000",};
    FarmersField f(input);
    EXPECT_STREQ("100-010-001-000-000-000", f.Cstr());
    EXPECT_EQ(1, f.RemoveLamps());
    EXPECT_STREQ("000-010-001-000-000-000", f.Cstr());
 }

TEST(FarmersField, Example4) 
{
    using namespace FarmersLand;
    char * input[] = {"3 3", "000", "000", "000",};
    FarmersField f(input);
    EXPECT_STREQ("000-000-000", f.Cstr());
    EXPECT_EQ(0, f.RemoveLamps());
    EXPECT_STREQ("000-000-000", f.Cstr());
 }

TEST(FarmersField, Example5) 
{
    using namespace FarmersLand;
    char * input[] = {"3 3", "111", "111", "111",};
    FarmersField f(input);
    EXPECT_STREQ("111-111-111", f.Cstr());
    EXPECT_EQ(8, f.RemoveLamps());
    EXPECT_STREQ("000-010-000", f.Cstr());
 }

TEST(FarmersField, Example6) 
{
    using namespace FarmersLand;
    char * input[] = {"6 6", "100001", "001010", "001001", "001010", "110000", "100001",};
    FarmersField f(input);
    EXPECT_STREQ("100001-001010-001001-001010-110000-100001", f.Cstr());
    EXPECT_EQ(6, f.RemoveLamps());
    EXPECT_STREQ("100011-001010-000000-000010-010000-000001", f.Cstr());
 }
\$\endgroup\$
2
0
\$\begingroup\$

Perl 3420 bytes

Not a golf solution, but I found this problem interesting:

#!/usr/bin/perl
use strict;
use warnings; 

{
   package Farm; 
   use Data::Dumper; 

   # models 8 nearest neighbors to position i,j forall i,j
   my $neighbors = [ [-1, -1],
                     [-1,  0],
                     [-1, +1], 
                     [ 0, -1], 
                     # current pos 
                     [ 0,  1], 
                     [+1, -1], 
                     [+1,  0], 
                     [+1, +1] ];

   sub new { 
      my ($class, %attrs) = @_; 
      bless \%attrs, $class;
   }  

   sub field { 
      my $self = shift;
      return $self->{field};
   }

   sub rows {
      my $self = shift;
      return $self->{rows};
   }

   sub cols {
      my $self = shift;
      return $self->{cols};
   }
   sub adjacents {
      my ($self, $i, $j) = @_;

      my @adjs; 
   NEIGHBORS:
      for my $neighbor ( @$neighbors ) {
         my ($imod, $jmod) = ($neighbor->[0] + $i, $neighbor->[1] + $j); 
         next NEIGHBORS 
            if $imod >= $self->rows || $jmod >= $self->cols;

         # push neighbors
         push @adjs, 
            $self->field->[$imod]->[$jmod];

      }

      return @adjs;
   }

   sub islit { 
      my ($lamp) = @_;

      return defined $lamp && $lamp == 1;
   }

   sub can_remove_lamp { 
      my ($self, $i, $j) = @_; 

      return scalar grep { islit($_) } $self->adjacents($i, $j);
   }

   sub remove_lamp { 
      my ($self, $i, $j) = @_;

      $self->field->[$i]->[$j] = 0;
   }

   sub remove_lamps {
      my ($self) = @_; 

      my $removed = 0;
      for my $i ( 0 .. @{ $self->field } - 1) {
         for my $j ( 0 .. @{ $self->field->[$i] } - 1 ) { 
            next unless islit( $self->field->[$i]->[$j] ); 

            if( $self->can_remove_lamp($i, $j) ) {
               $removed++; 
               $self->remove_lamp($i, $j);
            }
         }
      }

      return $removed;
   }

   1;
}

{ # Tests
   use Data::Dumper;
   use Test::Deep;
   use Test::More; 

   { # 3x3 field
      my $farm = Farm->new( rows  => 3,
                            cols  => 3,
                            field => [ [1,0,0],
                                       [0,1,0],
                                       [0,0,1]
                                     ]
      );

      is( 2, 
          $farm->remove_lamps,
          'Removed 2 overlapping correctly'
      );

      is_deeply( $farm->field, 
                 [ [0,0,0],
                   [0,0,0],
                   [0,0,1],
                 ],
                 'Field after removing lamps matches expected'
      );

   }

   { # 5x5 field
      my $farm = Farm->new( rows  => 5,
                            cols  => 5,
                            field => [ [0,0,0,0,0],
                                       [0,1,0,0,0],
                                       [0,0,1,0,0],
                                       [0,0,0,0,0],
                                       [0,0,0,0,0]
                                     ]
      );

      is( 1, 
          $farm->remove_lamps,
          'Removed 1 overlapping lamp correctly'
      );

      is_deeply( $farm->field,
                 [ [0,0,0,0,0],
                   [0,0,0,0,0],
                   [0,0,1,0,0],
                   [0,0,0,0,0],
                   [0,0,0,0,0],
                 ],
                 'Field after removing lamps matches expected'
      );
   }
}

(I/O was taken out so I could show concrete tests)

\$\endgroup\$
0
\$\begingroup\$

Python - 305 bytes

import sys,itertools
w,h=map(int,input().split());w+=1
l=[i for i,c in enumerate(sys.stdin.read())if c=="1"]
f=lambda l:{i+j for i in l for j in(0,1,-1,w-1,w,w+1,1-w,-w,-w-1)if(i+j+1)%w}&set(range(w*h))
for n in range(1,len(l)):
 for c in itertools.combinations(l,n):
  if f(c)^f(l):print(len(l)-n);exit()
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.