Asesinar selectivamente enteros positivos

21

Introducción

Arithmetic Gaol es una instalación especial que encarcela números enteros positivos. Sin embargo, recientemente, los enteros positivos han estado tratando de escapar. Por lo tanto, los guardianes han decidido, um, eliminar algunos de los enteros positivos para enviar un mensaje a los otros enteros. Han contratado a un ingeniero de software para escribir un programa para averiguar qué enteros eliminar para obtener el máximo efecto.

Descripción de entrada

La entrada se proporciona a través de STDIN, argumentos de línea de comando o una función de entrada de usuario (como raw_input). No puede tenerlo como un argumento de función o una variable preinicializada (por ejemplo, este programa espera entrada en una variable x).

La primera línea de entrada contiene un solo entero positivo ndonde 8 >= n >= 3. A continuación hay nlíneas que contienen ncaracteres del conjunto [1,2,3,4,5,6,7,8,9]. Aquí hay un ejemplo de entrada:

5
22332
46351
65455
24463
65652

Descripción de salida

Los guardias desean eliminar los números para que se cumplan las siguientes condiciones:

  • En cada fila y columna de la cuadrícula resultante, ningún número aparecerá dos veces;
  • No hay dos números eliminados que puedan ser adyacentes horizontal o verticalmente;
  • Los números supervivientes deben formar un grupo contiguo ortogonalmente: será posible viajar de cualquier número superviviente a cualquier otro número superviviente que se mueva solo horizontal y verticalmente y nunca cruce ningún número eliminado.

Salida de la entrada (menos la primera línea), con los números eliminados reemplazados por # .

Puede haber más de una solución. Si ese es el caso, puede generar cualquier solución.

También puede no haber solución. Si ese es el caso, envíe la cadenano answer .

Aquí hay una salida posible para la entrada de ejemplo:

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

Ejemplo de entradas y salidas

Hay múltiples salidas para cada entrada, por lo que estas salidas son solo ejemplos.

Entrada:

5
46551
51565
32654
14423
43244

Salida:

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

Entrada:

7
7183625
1681563
5238564
8786268
1545382
3814756
5325345

Salida:

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

Entrada:

8
21534768
75196287
68392184
96244853
44865912
76516647
89751326
43698979

Salida:

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

Entrada:

4
2222
2331
3112
1322

Salida:

no answer
code-golf grid Ajenjo
fuente
44
(También conocido como Singles .)
Pomo de la puerta
Este rompecabezas es excelente. Gracias. Trabajando en una solución
No es que Charles
1
Me gusta este rompecabezas, pero no se puede responder "tal cual" usando JavaScript en un navegador, ya que el único método de entrada del usuario promptno permite la entrada de varias líneas.
edc65

Respuestas:

0

Ruby, 346 344 329 316 bytes, sl∞∞∞∞∞∞w

Esto es código golf, no código rápido, así que ...

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"

Úselo como:

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

El indicador -W0no es necesario, pero le sugiero que lo agregue para desactivar las advertencias o redirigir stderr...

Dime si tuviste suficiente paciencia para ejecutarlo en los ejemplos para n = 6,7,8

Registro de cambios

  • each⇨ map, gracias a @NotThatCharles
  • verifique las eliminaciones adyacentes y los mismos dígitos por dos regexps, similar a lo que sugirió @NotThatCharles
  • entrada de lectura optimizada un poco
  • más pequeño y más lento
blutorange
fuente
algunas mejoras incrementales en tamaño: \des más corto que [^#]en la penúltima línea; M.times.to_aes más largo que(0..M-1).to_a
No es que Charles
@NotThatCharles ¡Gracias por los consejos! Pero M.times.to_aes 1 byte más corto que (0..M-1).to_a;) (0...M).to_atambién funciona y tiene la misma longitud.
blutorange
... contar es difícil
No es que Charles
¿se completa realmente cuando n = 8?
No es que Charles
@NotthatCharles Si espera lo suficiente o usa una PC súper rápida, sí, debería. Este es un código de golf sin restricción alguna en cuanto a la velocidad, por lo que priorizado código de longitud ...
Blutorange
5

Rubí - 541 ..., 394

El algoritmo básico es una búsqueda recursiva de duplicados en profundidad para seleccionar afirmativamente, mirando a través de la fila 1, luego la columna 1, luego la fila 2, etc., y verificando que dos vecinos no se eliminen y que la cuadrícula esté conectada (esa es la break ifcláusula en allí, y lo que viene antes).

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"

Algunos buenos trucos:

if w[1]es mucho más corto que if !w.one?y si sabes que hay al menos un miembro, es el mismo resultado.

Del mismo modo, [0]es más corto que any?si no hay bloque, y s[j]es un lindo atajo para j<s.size(técnicamente, es más comoj.abs<s.size )

Y y%N+(y/N).ies mucho más corto queComplex(y%N,y/N)

Además, cuando hay dos condicionales complicados para generar cadenas, puede ser más corto [cond1?str1a:str1b,cond2?str2a:str2b]*''que agregar todos los parens o #{}s.

Sin pretensiones y explicación:

(Esto es de la versión de 531 bytes. He realizado cambios. En particular, he eliminado la llamada al producto: solo resuelva un dígito por fila / columna a la vez, y J ahora es solo una matriz, indexada por enteros. Todas las coordenadas son solo enteros.)

H calcula vecinos

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 es el tamaño de la cuadrícula

N = gets.to_i

K son las claves del mapa (números complejos)

# 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 es el mapa de entrada (cárcel)

# 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 son las llaves no asesinadas

# starts as K

Q es el principal método recursivo

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

El código se ejecuta con:

# run with whole board
Q[K]

# if we get here, we didn't hit an exit, so we fail
puts"no answer"

Registro de cambios

394 agregó la sugerencia de @ blutorange a continuación, y cortó mucha más manipulación

408 salida revisada una vez más. También use en .minlugar de.inject(:+) ya que solo estoy tomando una fila de todos modos.

417Cálculo de salida más corto

421 descartaron números complejos. Solo usa números enteros. Guardar un paquete

450 mejoras de entrada más

456 mejoras de entrada

462 mejoras incrementales - esp. findnoselect

475 caídosu y aplastó al constructor de fila / col dupe

503 solo resuelve un dígito duplicado por fila / columna a la vez.

530 uso en map &:poplugar devalues

531 saca la lambda que hace que los dupes se arreglen

552 ¡Uy! se perdió un requisito

536 población marginalmente mejorada de dupes array (lo que era antes d)

541 inicial

No es que Charles
fuente
Dentro de las lambdas, breakse puede usar en lugar de return, puede guardar un byte más. Realmente me gusta este, muchos trucos y mucho más rápido.
blutorange
@blutorange ¡Gracias! Aplicado. Sin embargo, todavía tengo mucho camino por recorrer para alcanzar 344.
No es que Charles
Un poco más, sí, pero por lo demás parece estar bien hecho. Una cosa más que vi: en la segunda línea, como la variable ase usa solo una vez, podría hacer eso J=gets(p).split*''. ¿Has probado argumentos cli, ves mi respuesta?
blutorange
3

HTML + JavaScript ( ES6 ) 459

Usar un área de texto HTML para obtener entradas de varias líneas.

Para probar, ejecuta el fragmento en Firefox. Si lo desea, amplíe el área de texto, pegue la entrada dentro del área de texto (cuidado: entrada exacta, sin espacios adicionales en ninguna línea) y retírela. Se adjunta el resultado.

Método: una profundidad recursiva First Serarch. Encuentra soluciones no óptimas para todos los casos de prueba en segundos (es un buen juego de golf, pero una respuesta válida debería terminar para los casos de prueba comunes)

<textarea onchange="s=this.value,
  z=s[0],o=-~z,k=[],X='no answer',f='#',
  (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>
Expandir fragmento

Primer intento

Método: un primer Serarch de profundidad, no recursivo, utilizando una pila de usuarios.
La función podría transformarse fácilmente en Breadth First Search, cambiar l.popa l.shift, por lo tanto, usar una cola en lugar de una pila, pero es demasiado lenta y no estoy seguro de que pueda encontrar una solución óptima de todos modos.

Mostrar fragmento de código

edc65
fuente