Meurtre sélectivement des nombres entiers positifs

21

introduction

Arithmetic Gaol est une installation spéciale qui incarcère des nombres entiers positifs. Cependant, récemment, les nombres entiers positifs ont tenté de s'échapper. Les gardiens ont donc décidé, euh, d' éliminer certains des entiers positifs pour envoyer un message aux autres entiers. Ils ont embauché un ingénieur logiciel pour écrire un programme afin de déterminer les entiers à éliminer pour un effet maximal.

Description de l'entrée

L'entrée est donnée via STDIN, des arguments de ligne de commande ou une fonction d'entrée utilisateur (telle que raw_input). Vous ne pouvez pas l'avoir comme argument de fonction ou comme variable préinitialisée (par exemple, ce programme attend l'entrée dans une variable x).

La première ligne d'entrée contient un seul entier positif noù 8 >= n >= 3. Les nlignes suivantes contiennent des ncaractères de l'ensemble [1,2,3,4,5,6,7,8,9]. Voici un exemple d'entrée:

5
22332
46351
65455
24463
65652

Description de la sortie

Les gardiens souhaitent supprimer les numéros afin que les conditions suivantes soient remplies:

  • Dans chaque ligne et colonne de la grille résultante, aucun nombre n'apparaîtra deux fois;
  • Aucun nombre éliminé ne peut être adjacent horizontalement ou verticalement;
  • Les nombres survivants doivent former un groupe contigu orthogonalement - il sera possible de voyager de n'importe quel nombre survivant à n'importe quel autre nombre survivant se déplaçant seulement horizontalement et verticalement et ne traversant jamais aucun nombre éliminé.

Sortez l'entrée (moins la première ligne), avec les nombres éliminés remplacés par #.

Il peut y avoir plusieurs solutions. Si tel est le cas, vous pouvez générer n'importe quelle solution.

Il peut également n'y avoir aucune solution. Si tel est le cas, sortez la chaîne no answer.

Voici une sortie possible pour l'exemple d'entrée:

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

Exemples d'entrées et de sorties

Il y a plusieurs sorties pour chaque entrée, donc ces sorties ne sont que des exemples.

Contribution:

5
46551
51565
32654
14423
43244

Sortie:

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

Contribution:

7
7183625
1681563
5238564
8786268
1545382
3814756
5325345

Sortie:

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

Contribution:

8
21534768
75196287
68392184
96244853
44865912
76516647
89751326
43698979

Sortie:

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

Contribution:

4
2222
2331
3112
1322

Sortie:

no answer
code-golf grid Absinthe
la source
4
(Aussi connu sous le nom de célibataires .)
Poignée de porte
Ce puzzle est excellent. Merci. Travailler sur une solution
Pas que Charles
1
J'aime ce casse-tête, mais il ne peut pas être répondu "tel quel" en utilisant JavaScript dans un navigateur, car la seule méthode de saisie utilisateur promptne permet pas la saisie sur plusieurs lignes.
edc65

Réponses:

0

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

C'est du code-golf, pas du code-fast, donc ...

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"

Utilisez-le comme:

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

Le drapeau -W0n'est pas nécessaire, mais je vous suggère de l'ajouter pour désactiver les avertissements ou de rediriger stderr...

Dites-moi si vous avez eu assez de patience pour l'exécuter sur les exemples pour n = 6,7,8

Changelog

  • each⇨ map, grâce à @NotThatCharles
  • vérifier les suppressions adjacentes et les mêmes chiffres par deux regexps, similaire à ce que @NotThatCharles a suggéré
  • entrée de lecture optimisée un peu
  • plus petit et plus lent
blutorange
la source
quelques améliorations incrémentielles de la taille: \dest plus courte que [^#]dans l'avant-dernière ligne; M.times.to_aest plus long que(0..M-1).to_a
Pas que Charles
@NotThatCharles Merci pour les conseils! Mais M.times.to_aest 1 octet plus court que (0..M-1).to_a;) (0...M).to_afonctionne aussi et est de la même longueur.
blutorange
... compter est difficile
pas que Charles
est-il réellement terminé lorsque n = 8?
Pas que Charles
@NotthatCharles Si vous attendez assez longtemps ou utilisez un PC ultra-rapide, oui, cela devrait. C'est un code-golf sans aucune restriction de vitesse, j'ai donc priorisé la longueur du code ...
blutorange
5

Rubis - 541 ..., 394

L'algorithme de base est une recherche récursive en profondeur des doublons à sélectionner de manière affirmative, en parcourant la ligne 1, puis la colonne 1, puis la ligne 2, etc., et en vérifiant que deux voisins ne sont pas tués et que la grille est connectée (c'est la break ifclause de là, et le peu qui le précède).

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"

Quelques astuces intéressantes:

if w[1]est beaucoup plus court que if !w.one?et si vous savez qu'il y a au moins un membre, c'est le même résultat.

De même, [0]est plus court que any?s'il n'y a pas de bloc et s[j]est un raccourci mignon pour j<s.size(techniquement, c'est plus comme j.abs<s.size)

Et y%N+(y/N).iest beaucoup plus court queComplex(y%N,y/N)

De plus, lorsqu'il y a deux conditions compliquées pour générer des chaînes, cela peut être plus court à faire [cond1?str1a:str1b,cond2?str2a:str2b]*''que d'ajouter toutes les parens ou #{}s dans.

Dégoût et explication:

(Cela provient de la version 531 octets. J'ai apporté des modifications. Plus particulièrement, j'ai depuis éliminé l'appel au produit - il suffit de résoudre un chiffre par ligne / colonne à la fois, et J n'est plus qu'un tableau, indexé par entiers. Toutes les coordonnées ne sont que des entiers.)

H calcule les voisins

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 est la taille de la grille

N = gets.to_i

K sont les clés de la carte (nombres complexes)

# 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 est la carte d'entrée (prison)

# 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 sont les clés non tuées

# starts as K

Q est la principale méthode récursive

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

Le code est exécuté avec:

# run with whole board
Q[K]

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

Changelog

394 a ajouté la suggestion de @ blutorange ci-dessous, et a coupé beaucoup plus de manipulation

408 sortie révisée une fois de plus. Utilisez également .minau lieu de .inject(:+)car je ne prends qu'une ligne de toute façon.

Calcul de sortie 417 plus court

421 ont abandonné des nombres complexes. Utilisez simplement des entiers. Enregistrer un bundle

450 améliorations supplémentaires en entrée

456 améliorations d'entrée

462 améliorations incrémentielles - esp. find, ne passelect

475 a chuté uet a écrasé le constructeur de ligne / col dupe

503 ne résout qu'un seul chiffre en double par ligne / colonne à la fois.

530 utiliser map &:popau lieu devalues

531 sortir le lambda qui fait le tableau des dupes

552 oups! manqué une exigence

536 population légèrement améliorée de réseau de dupes (ce qui était auparavant d)

541 initiale

Pas que Charles
la source
À l'intérieur des lambdas, breakpeut être utilisé à la place de return, peut économiser un octet de plus. J'ai vraiment aimé celui-ci, beaucoup de tours et beaucoup plus rapide.
blutorange
@blutorange Merci! Appliqué. Il reste encore du chemin à parcourir pour atteindre le 344.
Pas que Charles
Un peu plus longtemps, oui, mais sinon ça a l'air bien fait. Une dernière chose que j'ai vue: dans la deuxième ligne, comme la variable an'est utilisée qu'une seule fois, vous pouvez le faire J=gets(p).split*''. Avez-vous essayé les arguments cli, voyez ma réponse?
blutorange
3

HTML + JavaScript ( ES6 ) 459

Utilisation d'une zone de texte HTML pour obtenir une entrée multiligne.

Pour tester, exécutez l'extrait dans Firefox. Agrandissez la zone de texte si vous le souhaitez, collez l'entrée à l'intérieur de la zone de texte (attention: entrée exacte, aucun espace supplémentaire sur aucune ligne) et tabulez. Le résultat est ajouté.

Méthode: un premier sérarque récursif en profondeur. Il trouve des solutions non optimales pour tous les cas de test en quelques secondes (c'est gode golf, mais une réponse valide devrait se terminer pour les cas de test courants)

<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>
Développer l'extrait

Premier essai

Méthode: un Depth First Serarch, non récursif, utilisant une pile utilisateur.
La fonction pourrait être facilement transformée en une recherche en largeur, en se connectant l.popà l.shift, donc en utilisant une file d'attente au lieu d'une pile, mais c'est trop lent et je ne suis pas sûr qu'il puisse de toute façon trouver une solution optimale.

Afficher l'extrait de code

edc65
la source