# Selectively murder positive integers

Introduction

Arithmetic Gaol is a special facility that incarcerates positive integers. However, recently, the positive integers have been trying to escape. Therefore the wardens have decided to, um, eliminate some of the positive integers to send a message to the other integers. They have hired a software engineer to write a program to figure out which integers to eliminate for maximum effect.

Input Description

Input is given via STDIN, command line arguments, or a user input function (such as raw_input). You can't have it as a function argument or a preinitialized variable (e.g. this program expects input in a variable x).

The first line of input contains a single positive integer n where 8 >= n >= 3. Following that are n lines containing n characters from the set [1,2,3,4,5,6,7,8,9]. Here is an example input:

5
22332
46351
65455
24463
65652


Output Description

The wardens would like to eliminate numbers so that the following conditions are met:

• In each row and column of the resulting grid, no number will appear twice;
• No two eliminated numbers may be adjacent horizontally or vertically;
• The surviving numbers must form an orthogonally contiguous group -- it will be possible to travel from any surviving number to any other surviving number moving only horizontally and vertically and never crossing any eliminated number.

Output the input (minus the first line), with the eliminated numbers replaced with #.

There may be more than one solution. If that is the case, you may output any solution.

There may also be no solution. If that is the case, output the string no answer.

Here is a possible output for the example input:

#2#3#
46351
6#4#5
24#63
#56#2


Example Inputs and Outputs

There are multiple outputs for each input, so these outputs are just examples.

Input:

5
46551
51565
32654
14423
43244


Output:

46#51
#156#
326#4
1#423
#324#


Input:

7
7183625
1681563
5238564
8786268
1545382
3814756
5325345


Output:

71#362#
#6815#3
5238#64
#7#62#8
154#382
3814756
#325#4#


Input:

8
21534768
75196287
68392184
96244853
44865912
76516647
89751326
43698979


Output:

21#34768
#5196287
683#21#4
9#24#853
#4865912
7#51#64#
89751326
436#8#7#


Input:

4
2222
2331
3112
1322


Output:

no answer

• (Also known as Singles.)
– Doorknob
May 19 '15 at 11:53
• This puzzle is excellent. Thank you. Working on a solution May 19 '15 at 19:13
• I like this puzzle, but it cannot be answered "as is" using JavaScript in a browser, as the only user input method prompt does not allow multi line input. May 22 '15 at 13:40

# Ruby - 541..., 394

The basic algorithm is a recursive depth-first search of duplicates to affirmatively select, looking through row 1, then column 1, then row 2, etc, and checking that two neighbors are not killed and that the grid is connected (that's the break if clause in there, and the bit that comes before it).

K=(0...(N=gets.to_i)*N).to_a
J=gets(p).split*''
H=->m{K&[m+1,m-1,m+N,m-N]}
Q=->k{s=[k[j=0]]
(j=s.size
s.map{|x|(s+=H[x]&k).uniq!})while s[j]
break if(K-k).any?{|m|(H[m]-k)[0]}||k!=k&s
$><<K.map{|m|[k.index(m)?J[m]:?#,m%N>N-2?" ":p]}*''|exit if !g=((0...N*2).map{|x|(k.select{|m|m.divmod(N)[x/N]==x%N}.group_by{|m|J[m]}.find{|l,c|c[1]}||[])[1]}-[p]).min g.map{|d|Q[k-g<<d]}} Q[K] puts"no answer"  ### Some neat tricks: if w[1] is much shorter than if !w.one? and if you know there's at least one member, it's the same result. Similarly, [0] is shorter than any? if there's no block, and s[j] is a cute shortcut for j<s.size (technically, it's more like j.abs<s.size) And y%N+(y/N).i is much shorter than Complex(y%N,y/N) Also, when there's two complicated conditionals to generate strings, it might be shorter to do [cond1?str1a:str1b,cond2?str2a:str2b]*'' than to add all the parens or #{}s in. ## Ungolfing and explanation: (This is from the 531 byte version. I've made changes. Most notably, I've since eliminated the call to product - just solve one digit per row/column at a time, and J is now just an array, indexed by integers. All coordinates are just integers.) H calculates neighbors def H m # m, like all indices, is a complex number # where the real part is x and the imaginary is y # so neighbors are just +/-i and +/-1 i='i'.to_c neighborhood = [m+1, m-1, m+i, m-i] # and let's just make sure to eliminate out-of-bounds cells K & neighborhood end  N is the size of the grid N = gets.to_i  K are the keys to the map (complex numbers) # pretty self-explanatory # a range of, e.g., if N=3, (0..8) # mapped to (0+0i),(1+0i),(2+0i),(0+1i),(1+1i),(2+1i),... K = (0..N**2-1).map{|y| (y%N) +(y/N).i }  J is the input map (jail) # so J is [[0+0,"2"],[0+1i,"3"],....].to_h J=K.zip($<.flat_map {|s|
# take each input line, and...
# remove the "\n" and then turn it into an array of chars
s.chomp.chars
}).to_h


k are the non-killed keys

# starts as K


Q is the main recursive method

def Q k
j=0 # j is the size of mass
# the connected mass starts arbitrarily wherever k starts
mass=[k[0]]
while j < s.size # while s hasn't grown
j = mass.size
mass.each{|cell|
# add all neighbors that are in k
(mass+=H[cell] & k).uniq!
}
end
# if mass != k, it's not all orthogonally connected
is_all_connected = k!=k&mass

# (K-k) are the killed cells
two_neighbors_killed = (K-k).any?{|m|
# if any neighbors of killed cells aren't in k,
# it means it was killed, too
(H[m]-k)[0]
}
# fail fast
return if two_neighbors_killed || is_all_connected

def u x
x.group_by{|m|J[m]}.select{|l,c|c[1]}
end

rows_with_dupes = Array.new(N){|r|u[k.select{|m|m.imag==r}]}

cols_with_dupes = Array.new(N){|r|u[k.select{|m|m.real==r}]}

# dupes is an array of hashes
# each hash represents one row or column.  E.g.,
#   {
#     "3"=>[(0+0i),(1+0i),(3+0i)],
#     "2"=>[(2+0i),(4+0i)]
#   }
# means that the 0th, 1st and 3rd cells in row 0
# all are "3", and 2nd and 4th are "2".
# Any digits without a duplicate are rejected.
# Any row/col without any dupes is removed here.
dupes = (rows_with_dupes+cols_with_dupes-[{}])

# we solve one row at a time
first_row = dupes[0]

if !first_row
# no dupes => success!
J.map{|m,v|k.member?(m)?v:?#}.each_slice(N){|s|puts s*''}
exit
else
# the digit doesn't really matter
t=first_row.values

# cross-multiply all arrays in the row to get a
# small search space. We choose one cell from each
# digit grouping and drop the rest.
t.inject(:product).map{ |*e|
# Technically, we drop all cells, and add back the
# chosen cells, but it's all the same.
new_k = k-t.flatten+e.flatten

# and then search that space, recursively
Q[new_k]
}
end
end


The code is executed with:

# run with whole board
Q[K]

# if we get here, we didn't hit an exit, so we fail


## Changelog

394 added @blutorange's suggestion below, and chopped out a lot more manipulation

408 revised output once more. Also use .min instead of .inject(:+) since I'm just taking one row anyway.

417 shorter output calculation

421 dropped complex numbers. Just use integers. Save a bundle

450 more input improvements

456 input improvements

462 incremental improvements - esp. find, not select

475 dropped u and squashed the row/col dupe builder

503 only solve one duplicate digit per row/column at a time.

530 use map &:pop instead of values

531 pull out the lambda that makes the dupes array

552 oops! missed a requirement

536 marginally improved population of dupes array (what was formerly d)

541 initial

• Inside lambdas, break can be used instead of return, might save one more byte. I really lIke this one, lots of tricks and much faster. May 21 '15 at 20:20
• @blutorange Thanks! Applied. Still have a ways to go to hit 344, though. May 21 '15 at 20:35
• A bit longer, yes, but otherwise it looks done well. One more thing I saw: In the second line, as the variable a is used only once, you could make that J=gets(p).split*''. Have you tried cli arguments, see my answer? May 21 '15 at 20:53

# HTML + JavaScript (ES6) 459

Using an HTML textarea to get multiline input.

To test, run the snippet in Firefox. Enlarge the textarea if you like, paste the input inside the textarea (beware: exact input, no extra spaces on any line), and tab away. The result is appended.

Method: a recursive Depth First Serarch. It finds non-optimal solutions for all the test cases in seconds (it's gode golf, but a valid answer should terminate for common test cases)

<textarea onchange="s=this.value,
(R=(s,t,h={},r=[],d=0)=>(
s.map((v,i)=>v>0&&[i%o,~(i/o)].map(p=>h[p+=v]=[...h[p]||[],i])),
[h[i][1]&&h[i].map(p=>r[d=p]=p)for(i in h)],
d?r.some(p=>(
(s[p+o]!=f&s[p-o]!=f&s[p-1]!=f&s[p+1]!=f)&&
(
g=[...s],g[p]=f,e=[...g],n=0,
(F=p=>e[p]>0&&[1,-1,o,-o].map(d=>F(p+d),e[p]=--n))(p<o?p+o:p-o),
t+n==0&&!k[g]&&(k[g]=1,R(g,t-1))
)
)):X=s.join('')
))([...s.slice(2)],z*z-1),this.value+=

+X"></textarea>

First try

Method: a Depth First Serarch, non-recursive, using a user stack.
The function could be easily transformed in a Breadth First Search, chaging l.pop to l.shift, so using a queue instead of a stack, but it's too slow and I'm not sure it can find an optimal solution anyway.

S=s=>{
z=s[0],o=-~z,s=[...s.slice(2)];
k=[];
l=[[z*z,s]];

for(d=1;d&&(t=l.pop());)
{
[t,s]=t,--t,

s.map((v,i)=>v>0&&[i%o,~(i/o)].map(p=>h[p+=v]=[...h[p]||[],i]),h={},r=[])

d=0
for(i in h)h[i][1]&&h[i].map(p=>r[d=p]=p)

r.map(p=>
(s[p+o]!='#'&s[p-o]!='#'&s[p-1]!='#'&s[p+1]!='#')&&
(
g=[...s],g[p]='#',
f=[...g],n=0,
(F=p=>f[p]>0&&[1,-1,o,-o].map(d=>F(p+d),f[p]=--n))(p<o?p+o:p-o),
t+n||k[g]||(k[g]=l.push([t,g]))
)
)
}
}

// TEST
cases=[
['5\n22332\n46351\n65455\n24463\n65652','#2#3#\n46351\n6#4#5\n24#63\n#56#2']
,['5\n46551\n51565\n32654\n14423\n43244','46#51\n#156#\n326#4\n1#423\n#324#']
,['7\n7183625\n1681563\n5238564\n8786268\n1545382\n3814756\n5325345'
,'71#362#\n#6815#3\n5238#64\n#7#62#8\n154#382\n3814756\n#325#4#']
,['8\n21534768\n75196287\n68392184\n96244853\n44865912\n76516647\n89751326\n43698979'
,'21#34768\n#5196287\n683#21#4\n9#24#853\n#4865912\n7#51#64#\n89751326\n436#8#7#']
]

var out = ''
var nt=0
var exec =_=>{
var t=cases[nt++];
if (t) {
var r = S(t[0]).replace(/#/g,'<b>#</b>');
var k = t[1].replace(/#/g,'<b>#</b>');
out += '<tr><th>Input<th>Result<th>Expected</tr>'+
'<tr><td>'+t[0]+'</td><td>'+r+'</td><td>'+k+'</td></tr>';
T.innerHTML = out + 'test ' + nt + ' done';
setTimeout(exec, 100);
}
else
{
T.innerHTML = out;
}
}
T.innerHTML = "...wait ..."
setTimeout(exec, 100);  
table {
font-size: 12px;
}
td {
font-family: monospace;
white-space: pre;
vertical-align: bottom;
margin: 2x 4px;
}

b {
color: #ccc;
}
<table id=T>
</table>

# Ruby, 346344329 316 bytes, sl∞∞∞∞∞∞w

This is code-golf, not code-fast, so...

N=/!/=~G=$*[1..-1]*?! M=N*N g=->i{(!G[i]||G[i]<?*||i<0||A[i])&&break A[i]=0 [1,N+1,-1,-1-N].map{|a|g[i+a]}} f=->w,a{A=[];g[/\d/=~G=a];/#.{#{N}}?#/!~G&&/(\d)([^!]*|.{#{N}}.{#{O=N+1}}*)\1/!~G&&A.count(0)+w==M&&N.times.map{|m|puts G[m*(1+N),N]}&&exit (w...M).map{|j|b=a+'';b[j]=?# w<M&&f[w+1,b]}} f[0,G]$><<"no answer"


Use it like:

mad_gaksha@madlab ~/Applications/Tools \$ ruby -W0 c50442.rb 3 323 312 231
#23
312
231


The flag -W0 is not necessary, but I suggest you either add it to disable warnings or redirect stderr...

Tell me if you had enough patience to run it on the examples for n=6,7,8

# Changelog

• eachmap, thanks to @NotThatCharles
• check for adjacent deletions and same digits by two regexps, similar to what @NotThatCharles suggested
• optimized reading input a little
• smaller & slower
• a few incremental improvements in size: \d is shorter than [^#] in the penultimate line; M.times.to_a is longer than (0..M-1).to_a May 21 '15 at 15:59
• @NotThatCharles Thanks for the tips! But M.times.to_a is 1 byte shorter than (0..M-1).to_a ;) (0...M).to_a works too and is of the same length. May 21 '15 at 16:26
• ...counting is hard May 21 '15 at 16:32
• does it actually complete when n=8? May 21 '15 at 18:07
• @NotthatCharles If you wait loooong enough, or use a super-fast PC, yes, it should. This is a code-golf without any restrictions as to speed, so I prioritized code-length... May 21 '15 at 18:48