Trouver la capacité des objets imprimés 2D

23

Dans un monde 2D fictif, un ensemble d'instructions d'impression 2D pour un objet peut être représenté par une liste d'entiers comme suit:

1 4 2 1 1 2 5 3 4

Chaque nombre représente la hauteur de l'objet à ce point particulier. La liste ci-dessus se traduit par l'objet suivant lors de l'impression:

      #
 #    # #
 #    ###
 ##  ####
#########

Nous le remplissons ensuite avec autant d'eau que possible, ce qui se traduit par:

      #
 #~~~~#~#
 #~~~~###
 ##~~####
#########

Nous définissons la capacité de l'objet à être les unités d'eau que l'objet peut contenir lorsqu'il est complètement rempli; dans ce cas, 11.

À strictement parler, une unité d'eau ( ~) peut exister à un endroit si et seulement si elle est entourée de deux blocs solides ( #) dans la même rangée.

Défi

Prenez une liste d'entiers positifs en entrée (dans n'importe quel format) et affichez la capacité de l'objet imprimé lorsque la liste est utilisée comme instructions.

Vous pouvez supposer que la liste contient au moins un élément et que tous les éléments sont compris entre 1 et 255.

Cas de test

+-----------------+--------+
|      Input      | Output |
+-----------------+--------+
| 1               |      0 |
| 1 3 255 1       |      0 |
| 6 2 1 1 2 6     |     18 |
| 2 1 3 1 5 1 7 1 |      7 |
| 2 1 3 1 7 1 7 1 |      9 |
| 5 2 1 3 1 2 5   |     16 |
| 80 80 67 71     |      4 |
+-----------------+--------+
code-golf sequence array-manipulation Sisyphe
la source
5
Conceptuellement lié
Alex A.

Réponses:

15

Haskell, 54 octets

f l=(sum$zipWith min(scanl1 max l)$scanr1 max l)-sum l

Les expressions scanl1 max let scanr1 max lcalculent le maximum courant de la liste en lisant vers l'avant et vers l'arrière, c'est-à-dire le profil de l'eau plus la terre si l'eau allait couler dans une direction.

Orig:

      #
 #    # #
 #    ###
 ##  ####
#########

La gauche:

      #~~
 #~~~~#~#
 #~~~~###
 ##~~####
#########

Droite:

~~~~~~#
~#~~~~#~#
~#~~~~###
~##~~####
#########

Ensuite, le profil de l'image globale est le minimum de ceux-ci, ce qui correspond à l'endroit où l'eau ne fuit dans aucune direction.

Le minimum:

      #
 #~~~~#~#
 #~~~~###
 ##~~####
#########

Enfin, la quantité d'eau est la somme de cette liste, qui contient à la fois l'eau et la terre, moins la somme de la liste d'origine, qui ne contient que la terre.

xnor
la source
9

Gelée, 10 octets

U»\U«»\S_S

Alors qu'APL nécessite plusieurs parenthèses et J symboles à deux caractères, l'algorithme est beau dans Jelly.

     »\          Scan maximums left to right
U»\U             Scan maximums right to left
    «            Vectorized minimum
       S_S       Sum, subtract sum of input.

Essayez-le ici .

lirtosiast
la source
4

MATL , 14

Ma réponse Matlab a été traduite en MATL. algorithme de xnor.

Y>GPY>P2$X<G-s

Explication

Y>: cummax()(l'entrée est implicitement poussée sur la pile)

G: pousser l'entrée (à nouveau)

P: flip()

Y>: cummax()

P: flip()

2$X<: min([],[])(minimum de deux arguments)

G: pousser l'entrée (à nouveau)

-: -

s: sum()

Rainer P.
la source
MATL est-il un langage de substitution de Matlab? Pouvez-vous fournir un lien dans l'en-tête?
Addison Crump
1
@FlagAsSpam Je pense que c'est un peu plus que ça: esolangs.org/wiki/MATL
Martin Ender
@ MartinBüttner Le pseudocode pour cela serait-il identique au pseudocode Matlab? Je me demande si c'est une chose de traduction directe plutôt qu'une chose basée sur quelque chose.
Addison Crump
1
@FlagAsSpam MATL est basé sur la pile, ce n'est donc certainement pas une substitution simple.
Martin Ender
Oui, c'est une traduction directe. MATL est basé sur la pile (notation polonaise inversée) avec des raccourcis de un à trois caractères pour les opérateurs et fonctions MATLAB . Voir [ github.com/lmendo/MATL/blob/master/doc/MATL_spec.pdf] .
Rainer P.
3

Dyalog APL, 17 octets

+/⊢-⍨⌈\⌊⌽∘(⌈\⌽)

Il s'agit d'un train monadique qui prend le tableau d'entrée sur la droite.

L'algorithme est à peu près le même que xnor, bien que je l'ai trouvé indépendamment. Il recherche le maximum dans les deux directions (en arrière en inversant la matrice, en balayant et en inversant à nouveau), et trouve le minimum vectorisé de celles-ci. Ensuite, il soustrait le tableau et les sommes d'origine.

L'autre façon de procéder serait de diviser le tableau à chaque emplacement, mais c'est plus long.

Essayez-le ici .

lirtosiast
la source
1
Exactement le même que je suis venu ici pour écrire. :-) Lorsque nous obtenons l'opérateur dual (aka under), vous pouvez économiser 3 octets avec +/⊢-⍨⌈\⌊⌈\⍢⌽.
Adám
2

Matlab, 47

Utilisant également l'algorithme de xnor.

@(x)sum(min(cummax(x),flip(cummax(flip(x))))-x)
Rainer P.
la source
1

MATLAB, 116 113 109 106 Octets

n=input('');s=0;v=0;l=nnz(n);for i=1:l-1;a=n(i);w=min([s max(n(i+1:l))]);if a<w;v=v+w-a;else s=a;end;end;v

Cela fonctionne en stockant le point haut à gauche et, tout en parcourant chaque point suivant, trouve le point le plus haut à droite. Si le point actuel est inférieur aux deux points hauts, il ajoute la différence minimale au volume cumulé.

Code non golfé:

inputArray = input('');
leftHighPoint = inputArray(1);
volume = 0;
numPoints = nnz(inputArray);

for i = 1:numPoints-1
    currentPoint = inputArray(i); % Current value
    lowestHigh = min([max(inputArray(i+1:numPoints)) leftHighPoint]);

    if currentPoint < lowestHigh
        volume = volume + lowestHigh - currentPoint;
    else 
        leftHighPoint = currentPoint;
    end
end
volume

La première fois que j'ai essayé de jouer au golf, MATLAB ne semble pas le meilleur pour le faire en ....

Lui
la source
0

ES6, 101 octets

a=>(b=[],a.reduceRight((m,x,i)=>b[i]=m>x?m:x,0),r=m=0,a.map((x,i)=>r+=((m=x>m?x:m)<b[i]?m:b[i])-x),r)

Un autre port de l'alghorithme de @ xnor.

Neil
la source
0

Pip -l , 19 octets

$+J(ST0XgZD1`0.*0`)

Prend les nombres d'entrée comme arguments de ligne de commande. Ou ajoutez le -rdrapeau pour les prendre comme lignes de stdin: Essayez-le en ligne!

Explication

Contrairement à toutes les autres réponses, dans Pip, il était en fait plus court de construire (une version modifiée de) l'art ASCII et de compter les unités d'eau.

Commençons par gla liste des arguments.

[1 4 2 1 5 2 3]

0Xgproduit une liste de chaînes de n zéros pour chaque n dans g.

[0 0000 00 0 00000 00 000]

ZD1puis zippe ces chaînes ensemble, en utilisant 1pour combler les lacunes dans la liste imbriquée rectangulaire résultante:

[[0 0 0 0 0 0 0] [1 0 0 1 0 0 0] [1 0 1 1 0 1 0] [1 0 1 1 0 1 1] [1 1 1 1 0 1 1]]

STconvertit cette liste en chaîne. L' -lindicateur spécifie que les listes sont formatées comme suit: chaque liste imbriquée est jointe sans séparateur et, au niveau supérieur, le séparateur est une nouvelle ligne. Nous obtenons donc cette chaîne multiligne - essentiellement, le diagramme de l'objet, mais à l'envers:

0000000
1001000
1011010
1011011
1111011

On retrouve alors toutes les correspondances de l'expression régulière `0.*0`. Cela correspond aux deux murs les plus externes et tout ce qui les sépare sur chaque ligne.

[0000000 001000 011010 0110]

Jjoint ces cordes en une seule grosse chaîne, et la $+somme, donnant le nombre de 1s - qui est égal à la quantité d'eau que l'objet peut contenir.

6
DLosc
la source