Cartes thermiques

Prenons une pièce rectangulaire, au plafond de laquelle se trouve une caméra thermique pointant vers le bas. Dans la pièce, il existe un certain nombre de sources de chaleur d'intensité 1-9, la température de fond étant 0. La chaleur se dissipe de chaque source, chutant d'une unité par pas (non diagonal). Par exemple, la 20x10pièce

...........1........
....................
...8................
..5...............2.
....................
.1..................
................1...
.................65.
....................
............2.......

contient 9 sources de chaleur, et le gradient de température indiqué par la caméra thermique est

34565432100100000000
45676543210000000000
56787654321000000110
45676543210000001221
34565432100000012321
23454321000000123432
12343210000001234543
01232100000012345654
00121000000011234543
00010000000121123432

Sous forme graphique, cela pourrait ressembler à ceci:

Du gradient, nous pouvons déduire les positions et les intensités de certaines sources de chaleur, mais pas toutes. Par exemple, tous les 9s peuvent toujours être déduits, car ils ont la température maximale, et il en va de même 8dans ce cas, car il produit un maximum local dans le gradient. La 2proximité de la frontière droite peut également être déduite, même si elle n'est pas au maximum local, car elle n'en a pas d'autre 2comme voisin. Les 5s, en revanche, ne sont pas déduits, car leur chaleur pourrait aussi bien être produite par les sources les plus intenses à proximité. Les 0s sont connus pour ne contenir aucune source de chaleur, mais toutes les autres tuiles peuvent potentiellement en contenir une. Notons les tuiles incertaines par des tirets-, certaines sources de chaleur par les chiffres correspondants, et certains espaces vides par périodes .:

---------..1........
----------..........
---8-------......--.
----------......--2-
---------......-----
--------......------
-------......-------
.-----......-----6--
..---.......--------
...-.......-2-------

Votre tâche sera de produire ce modèle inféré à partir du gradient de température.

Règles

L'entrée vous est donnée sous la forme d'une chaîne délimitée par des sauts de ligne ou des tuyaux verticaux |, selon ce qui est le plus pratique, et la sortie doit être de la même forme. Il peut y avoir un délimiteur de fin dans l'entrée et / ou la sortie, mais aucun précédent. La taille de l'entrée peut varier, mais sa largeur et sa hauteur sont toujours au moins 4. Les fonctions et les programmes complets sont acceptables. Le nombre d'octets le plus bas l'emporte et les failles standard sont interdites.

Cas de test supplémentaires

Contribution:

898778765432100
787667654321100
677656543211210
678765432112321
567654321123210

qui ressemble à ceci sous forme graphique:

Sortie:

-9---8-------..
-------------..
--------------.
--8---------3--
-----------3--.

Contribution:

7898
8787
7676
6565

Sortie:

--9-
8---
----
----

Contribution:

00001
00000
00000
10000

Sortie:

....1
.....
.....
1....

CJam, 73 69 62 55 octets

MISE À JOUR : Nouvel algorithme. Des améliorations plus courtes et plus nombreuses

qN/5ff*{{[{_@_@<{I'0t}*\}*]W%}%z}4fI{):X-'-X~X'.??}f%N*

Comment ça marche

La logique est similaire à l'algorithme ci-dessous, mais ici je ne vérifie pas les 4 voisins en une seule itération. Au lieu de cela, j'utilise une approche plus petite pour parcourir toutes les lignes et colonnes dans les deux directions. Voici les étapes à suivre:

• Convertissez chaque personnage en ensembles de 5. Les 4 premiers seront modifiés pour indiquer s'ils sont plus grands que la cellule adjacente de la ligne lors de l'itération. Le dernier est à des fins de comparaison.
• Itérer sur chaque ligne et réduire sur chaque ligne. Tout en réduisant, j'ai deux chaînes de 5 caractères. Je sais quel type d'itération est [0 pour les lignes normales, 1 colonnes inversées, 2 pour les lignes inversées et 3 pour les colonnes normales] Je mets à jour le i ^ème caractère dans la première chaîne de 5 caractères et je fais 0 s'il est plus petit que le second .
• Après les 4 itérations, si les 5 caractères sont identiques et différents de zéro, il s'agit des maxima locaux. Je mappe les cinq chaînes de caractères et les convertis en un seul chiffre .ou -.

Voici un exemple exécuté sur une petite entrée:

7898
8787
7676
6565

Après la première étape:

["77777" "88888" "99999" "88888"
 "88888" "77777" "88888" "77777"
 "77777" "66666" "77777" "66666"
 "66666" "55555" "66666" "55555"]

Après la deuxième étape:

["00777" "08888" "99999" "88088"
 "88888" "07007" "88808" "77007"
 "77707" "06006" "77707" "66006"
 "66606" "05005" "66606" "55005"]

Après le dernier mappage sur un seul caractère, sortie finale:

--9-
8---
----
----

Explication du code :

qN/5ff*                         "Split the input on new line and convert each character";
                                "to string of 5 of those characters.";
{{[{             }*]W%}%z}4fI   "This code block runs 4 times. In each iteration, it";
                                "maps over each row/column and then for each of them,";
                                "It reduce over all elements of the row/column";
                                "Using combination of W% and z ensures that both rows and";
                                "columns are covered and in both directions while reducing";
    _@_@                        "Take a copy of last two elements while reducing over";
        <                       "If the last element is bigger than second last:";
         {I'0t}*\               "Convert the Ith character of the 5 char string of"
                                "second last element to 0";
                                "We don't have to compare Ith character of last two 5 char";
                                "string as the smaller one will be having more leading";
                                "0 anyways. This saves 4 bytes while comparing elements";
{):X-'-X~X'.??}f%N*             "This part of code converts the 5 char back to single char";
 ):X                            "Remove the last character and store in X. This last char";
                                "was not touched in the prev. loop, so is the original char";
    -                           "Subtract X from remaining 4 char. If string is not empty";
                                "then it means that it was not all same characters";
                                "In other words, this character was smaller then neighbors";
     '-      ?                  "If non-empty, then replace with - else ...";
       X~X'.?                   "if int(X) is zero, put . else put X";
               f%N*             "The mapping code block was run for each row and then";
                                "The rows are joined by newline.";

Essayez-le ici

Une approche plus ancienne

qN/~_,):L0s*]0s*:Q_,{QI=:A[W1LL~)]If+Qf=$W=<'-A?A~\'.?I\t}fIL/W<Wf<N*

Comment ça marche

La logique est simple, parcourez la grille et voyez si la valeur actuelle est supérieure ou égale aux quatre voisins restants - haut, bas, gauche et droite. Transformez ensuite la valeur actuelle sur la base de la règle ci-dessus et si la valeur est égale à 0, faites-la "." .

Explication du code

qN/~_,):L0s*]0s*:Q         "This part of code pads the grid with 0s";
qN/~                       "Read the input, split on new lines and unwrap the arrays";
    _,):L                  "Copy the last row, taken length, increment and store in L";
         0s*               "Get L length 0 string";
            ]0s*           "Wrap everything in an array and join the rows by 0";
                :Q         "Store this final single string in Q";

_,{        ...      }fI    "Copy Q and take length. For I in 0..length, execute block";
   QI=:A                   "Get the I'th element from Q and store in A";
   [WiLL~)]If+             "This creates indexes of all 4 neighboring cells to the Ith cell";
              Qf=          "Get all 4 values on the above 4 indexes";
                 $W=       "Sort and get the maximum value";
<'-A?                      "If the current value is not the largest, convert it to -";
     A~\'.?                "If current value is 0, convert it to .";
           I\t             "Update the current value back in the string";
{ ... }fIL/                "After the loop, split the resulting string into chunks of L";
           W<Wf<           "Remove last row and last column";
                N*         "Join by new line and auto print";

Essayez-le en ligne ici

JavaScript (ES6) 99

F=h=>[...h].map((c,i)=>[o=~h.search('\n'),-o,1,-1].some(d=>h[d+i]>c)&c>0?'-':c=='0'?'.':c).join('')

Tester dans la console Firefox / FireBug

console.log(F('\
34565432100100000000\n\
45676543210000000000\n\
56787654321000000110\n\
45676543210000001221\n\
34565432100000012321\n\
23454321000000123432\n\
12343210000001234543\n\
01232100000012345654\n\
00121000000011234543\n\
00010000000121123432\n'),'\n\n',
F('\
898778765432100\n\
787667654321100\n\
677656543211210\n\
678765432112321\n\
567654321123210\n'), '\n\n',
F('7898\n8787\n7676\n6565\n'))

Sortie

---------..1........
----------..........
---8-------......--.
----------......--2-
---------......-----
--------......------
-------......-------
.-----......-----6--
..---.......--------
...-.......-2-------


-9---8-------..
-------------..
--------------.
--8---------3--
-----------3--.


--9-
8---
----
----

Python 2: 154 octets

b=input()
l=b.index('\n')+1
print''.join(('\n.'+('-'+v)[all([v>=b[j]for j in i-l,i-1,i+l,i+1if 0<=j<len(b)])])[('\n0'+v).index(v)]for i,v in enumerate(b))

L'entrée doit être de la forme "00001\n00000\n00000\n10000".

La conversion d'une chaîne en matrice 2D est assez longue en Python. Je garde donc le format de chaîne d'origine. J'énumère sur l'entrée, iest l'index, vest le char (Enfin, énumère les octets enregistrés dans une solution de golf !!). Pour chaque paire, (i,v)je calcule le bon caractère de sortie et je les rejoins. Comment choisir le bon caractère de sortie? Si v == '\n', le caractère de sortie est \n, il v == '0', que le caractère de sortie est '.'. Sinon, je teste les 4 voisins de v, qui sont b[i-b.index('\n')-1](ci-dessus), b[i-1](gauche, b[i+1](droite) et b[i+b.index('\n')+1](dessous), s'ils le sont <= vet choisissez le caractère '-'ouv. Ici, je compare les caractères et non les nombres, mais cela fonctionne très bien, car les valeurs ascii sont dans le bon ordre. Il n'y a pas non plus de problèmes, si b[i-1]ou b[i+1]égaux '\n', car ord('\n') = 10.

Pyth: 61 58

JhxQbVQK@QN~k@++b\.?\-f&&gT0<TlQ<K@QT[tNhN-NJ+NJ)Kx+b\0K)k

Plus ou moins une traduction du script Python. Assez moche ;-)

Essayez-le en ligne: Pyth Compiler / Executor Même format d'entrée que la solution Python.

JhxQb      Q = input()
  xQb      Q.index('\n')
 h         +1
J          store in J

VQK@QN~k.....)k   k is initialized as empty string
VQ           )    for N in [0, 1, 2, ..., len(Q)-1]:
  K@QN                K = Q[n]
      ~k              k += ... (a char, computed in the next paragraph)
             )    end for
              k   print k

@...x+b\0K   ... is a char of len 3 (is constructed below)
     +b\0    the string "\n0"
    x    K   find Q[d] in this string and return index, if not found -1
@...         lookup in string at the computed position (this is done mod 3 automatically!)

++b\.?\-f&&gT0<TlQ<K@QT[tNhN-NJ+NJ)K   not to the string
                       [tNhN-NJ+NJ)    the list [d-1, d+1, d-J, d+j]
        f                              filter the list for indices T which
           gT0                            T >= 0
          &                               and
              <TlQ                        T < len(Q)
         &                                and
                  <K@QT                   Q[d] < Q[T]
     ?\-                           K   use "-" if len(filter) > 0 else Q[d]
                                       this creates the third char
++b\.                                  "\n" + "." + third char

Perl, 77, 75, 72 70

Astuces d'appariement regex 2d standard.

#!perl -p0
/
/;$x="(.{@-})?";y/0/./while s/$.$x\K$"|$"(?=$x$.)/-/s||($"=$.++)<9

Exemple:

$ perl heat.pl <in.txt
---------..1........
----------..........
---8-------......--.
----------......--2-
---------......-----
--------......------
-------......-------
.-----......-----6--
..---.......--------
...-.......-2-------

Essayez-le ici

Java, 307 , 304 , 303 , 299 298

C'est à coup sûr un défi "parfait" pour certains Java Codegolf :)

class M{public static void main(String[]a){int c=a[0].indexOf('|'),i=c,d,v;char[]r=a[0].replace("|","").toCharArray(),m=new char[(v=r.length+c)+c];for(;i<v;){m[i]=r[i++-c];}for(i=c;i<v;i++){a[0]=i%c<1?"\n":"";d=m[i];System.out.print(a[0]+(d<49?'.':m[i-c]>d|m[i+c]>d|m[i-1]>d|m[i+1]>d?'-':m[i]));}}}

Entrée (méthode du tube '|'):

34565432100100000000|45676543210000000000|56787654321000000110|45676543210000001221|34565432100000012321|23454321000000123432|12343210000001234543|01232100000012345654|00121000000011234543|00010000000121123432

Sortie:

---------..1........
----------..........
---8-------......--.
----------......--2-
---------......-----
--------......------
-------......-------
.-----......-----6--
..---.......--------
...-.......-2-------

APL, 92

('.-',⎕D)[1+(M≠0)+M{(1+⍺)×0≠⍺∧M[J/⍨Z∊⍨J←⍵∘+¨(⌽¨,+)(-,+)⊂0 1]∧.≤⍺}¨Z←⍳⍴M←↑{×⍴⍵:(⊂⍎¨⍵),∇⍞⋄⍬}⍞]

Exemple:

       ('.-',⎕D)[1+(M≠0)+M{(1+⍺)×0≠⍺∧M[J/⍨Z∊⍨J←⍵∘+¨(⌽¨,+)(-,+)⊂0 1]∧.≤⍺}¨Z←⍳⍴M←↑{×⍴⍵:(⊂⍎¨⍵),∇⍞⋄⍬}⍞]
34565432100100000000
45676543210000000000
56787654321000000110
45676543210000001221
34565432100000012321
23454321000000123432
12343210000001234543
01232100000012345654
00121000000011234543
00010000000121123432

---------..1........
----------..........
---8-------......--.
----------......--2-
---------......-----
--------......------
-------......-------
.-----......-----6--
..---.......--------
...-.......-2-------

Rubis 140

f=->s{
r=s.dup
l=s.index(?\n)+1
(0...s.size).map{|i|
s[i]<?0||r[i]=r[i]<?1??.:[i-1,i+1,i-l,i+l].map{|n|n<0??0:s[n]||?0}.max>r[i]??-:s[i]}
r}

Rien de spécial; il suffit de parcourir la carte et de comparer la valeur actuelle avec la valeur des quatre voisins.

Exécutez-le en ligne avec des tests: http://ideone.com/AQkOSY

R, 223

À propos du meilleur que je puisse trouver pour le moment. Le traitement de la chaîne coûte assez cher. Je pense qu'il y a place à amélioration, mais je ne le vois pas pour le moment

s=strsplit;a=c(m<-do.call(rbind,s(s(scan(w="c"),'|',T)[[1]],'')));w=(d<-dim(m))[1];n=c(-1,1,-w,w);cat(t(array(sapply(seq(a),function(x)if(a[x]>0)if(any(a[(n+x)[which(n+x>0)]]>a[x]))'-'else a[x]else'.'),d)),fill=d[2],sep='')

Résultat du test

> s=strsplit;a=c(m<-do.call(rbind,s(s(scan(w="c"),'|',T)[[1]],'')));w=(d<-dim(m))[1];n=c(-1,1,-w,w);cat(t(array(sapply(seq(a),function(x)if(a[x]>0)if(any(a[(n+x)[which(n+x>0)]]>a[x]))'-'else a[x]else'.'),d)),fill=d[2],sep='')
1: 898778765432100|787667654321100|677656543211210|678765432112321|567654321123210
2: 
Read 1 item
-9---8-------..
-------------..
--------------.
--8---------3--
-----------3--.
> s=strsplit;a=c(m<-do.call(rbind,s(s(scan(w="c"),'|',T)[[1]],'')));w=(d<-dim(m))[1];n=c(-1,1,-w,w);cat(t(array(sapply(seq(a),function(x)if(a[x]>0)if(any(a[(n+x)[which(n+x>0)]]>a[x]))'-'else a[x]else'.'),d)),fill=d[2],sep='')
1: 34565432100100000000|45676543210000000000|56787654321000000110|45676543210000001221|34565432100000012321|23454321000000123432|12343210000001234543|01232100000012345654|00121000000011234543|00010000000121123432
2: 
Read 1 item
---------..1........
----------..........
---8-------......--.
----------......--2-
---------......-----
--------......------
-------......-------
.-----......-----6--
..---.......--------
...-.......-2-------
> 

J - 69 octets

[:u:45+[:(+2 0 3{~"#1+*)@((]*]=(0,(,-)1 0,:0 1)>./@:|.])-0=])"."0;._2

Exemples:

   ([:u:45+[:(+2 0 3{~"#1+*)@((]*]=(0,(,-)1 0,:0 1)>./@:|.])-0=])"."0;._2) (0 : 0)
34565432100100000000
45676543210000000000
56787654321000000110
45676543210000001221
34565432100000012321
23454321000000123432
12343210000001234543
01232100000012345654
00121000000011234543
00010000000121123432
)
---------..1........
----------..........
---8-------......--.
----------......--2-
---------......-----
--------......------
-------......-------
.-----......-----6--
..---.......--------
...-.......-2-------
   ([:u:45+[:(+2 0 3{~"#1+*)@((]*]=(0,(,-)1 0,:0 1)>./@:|.])-0=])"."0;._2) (0 : 0)
898778765432100
787667654321100
677656543211210
678765432112321
567654321123210
)
-9---8-------..
-------------..
--------------.
--8---------3--
-----------3--.

PS: (0 : 0)c'est la manière J standard de spécifier les chaînes. Vous pourriez aussi bien utiliser des |chaînes délimitées (avec une fin |).

Excel VBA - 426

Ce sera une occasion rare que VBA gagne des jeux de golf à code, mais comme c'est ce que j'utilise le plus, c'est amusant de jouer avec. La première ligne est un boîtier de bord qui a rendu cela plus long qu'il n'y paraît.

Sub m(a)
    b = InStr(a, "|")
    For i = 1 To Len(a)
        t = Mid(a, i, 1)
        Select Case t
            Case "|"
                r = r & "|"
            Case 0
                r = r & "."
            Case Else
                On Error Resume Next
                x = Mid(a, i - 1, 1)
                y = Mid(a, i + 1, 1)
                Z = Mid(a, i + b, 1)
                If i < b Then
                    If t < x Or t < y Or t < Z Then
                        r = r & "-"
                    Else
                        r = r & t
                    End If
                Else
                    If t < x Or t < y Or t < Z Or t < Mid(a, i - b, 1) Then
                        r = r & "-"
                    Else
                        r = r & t
                    End If
                End If
        End Select
    Next
    MsgBox r
End Sub

Le nombre n'inclut pas l'espace blanc de la ligne initiale.

J'ai joué avec l'idée d'envoyer l'entrée sur une feuille et de travailler à partir de là, mais je pense que boucler la chaîne passée caractère par caractère enregistre le code.

Appel depuis la fenêtre immédiate:

m "34565432100100000000|45676543210000000000|56787654321000000110|45676543210000001221|34565432100000012321|23454321000000123432|12343210000001234543|01232100000012345654|00121000000011234543|00010000000121123432"

Sortie (dans une fenêtre):

---------..1........|----------..........|---8-------......--.|----------......--2-|---------......-----|--------......------|-------......-------|.-----......-----6--|..---.......--------|...-.......-2-------

Perl - 226

sub f{for(split'
',$_[0]){chomp;push@r,r($_);}for(t(@r)){push@y,r($_)=~s/0/./gr}$,=$/;say t(@y);}sub r{$_[0]=~s/(?<=(.))?(.)(?=(.))?/$1<=$2&&$3<=$2?$2:$2eq'0'?0:"-"/ger;}sub t{@q=();for(@_){for(split//){$q[$i++].=$_;}$i=0;}@q}

Vous pouvez l'essayer sur ideone . Si quelqu'un est intéressé par une explication, faites-le moi savoir.

Haskell - 193

z='0'
r=repeat z
g s=zipWith3(\u t d->zip3(zip(z:t)u)t$zip(tail t++[z])d)(r:s)s$tail s++[r]
f=unlines.map(map(\((l,u),t,(r,d))->case()of _|t==z->'.'|maximum[u,l,t,r,d]==t->t|0<1->'-')).g.lines

fest une fonction qui prend une chaîne sous la forme 0001\n0000\n0000\n1000et renvoie la chaîne requise.

g est une fonction qui prend une liste de listes de caractères et retourne une liste de listes de ((gauche, haut), ceci, (droite, bas)).