La Ligne D'Horizon Problème

Question

Je viens de tomber sur ce petit problème sur les rayons UVA en Ligne du Juge et de la pensée, qu'il peut être un bon candidat pour un peu de code-golf.

Le problème:

Vous êtes à la conception d'un programme pour aider un architecte dans le dessin de la ligne d'horizon d'une ville étant donné l'emplacement des bâtiments de la ville. Pour rendre le problème traitable, tous les édifices sont de forme rectangulaire et ils partagent un fond commun de la ville, ils sont construits dans le est très plat). La ville est également considérée comme deux dimensions. Un bâtiment est spécifié par un ordre triple (Li, Hi, Ri) où Li et Ri sont à gauche et à droite des coordonnées, respectivement, de la construction i et Hi est la hauteur de l'édifice.

Dans le diagramme ci-dessous bâtiments sont indiqués sur la gauche avec des triples

(1,11,5), (2,6,7), (3,13,9), (12,7,16), (14,3,25), (19,18,22), (23,13,29), (24,4,28) 

et la ligne d'horizon, comme illustré sur la droite, est représenté par la séquence:

1, 11, 3, 13, 9, 0, 12, 7, 16, 3, 19, 18, 22, 3, 23, 13, 29, 0 

La sortie doit contenir le vecteur qui décrit la ligne d'horizon, comme illustré dans l'exemple ci-dessus. Dans la ligne d'horizon vecteur (v1, v2, v3, ..., vn) , la vi tels que i est un nombre pair représentent une ligne horizontale (hauteur). Le vi tels que i est un nombre impair représenter une ligne verticale (abscisse). La ligne d'horizon vecteur doit représenter le "chemin", par exemple, par un bug de départ au minimum x-coordonner et de voyager horizontalement et verticalement au-dessus de toutes les lignes qui définissent la ligne d'horizon. Ainsi, la dernière entrée de la ligne d'horizon vecteur sera un 0. Les coordonnées doivent être séparés par un espace vide.

Si je ne compte pas la déclaration prévue (de test) les bâtiments et y compris tous les espaces et les caractères de tabulation, ma solution, en Python, est 223 caractères.

Ici est la version condensée:

B=[[1,11,5],[2,6,7],[3,13,9],[12,7,16],[14,3,25],[19,18,22],[23,13,29],[24,4,28]]

# Solution.

R=range
v=[0 for e in R(max([y[2] for y in B])+1)]
for b in B:
   for x in R(b[0], b[2]):
      if b[1]>v[x]:
         v[x]=b[1]
p=1
k=0
for x in R(len(v)):
   V=v[x]
   if p and V==0:
      continue
   elif V!=k:
      p=0
      print "%s %s" % (str(x), str(V)),
   k=V

Je pense que je n'ai pas fait d'erreur, mais si oui, n'hésitez pas à me critiquer.

Je n'ai pas beaucoup de réputation, donc je vais payer seulement 100 pour un bounty - je suis curieux de savoir, si quelqu'un pouvait essayer de le résoudre en moins de .. disons, de 80 caractères. La Solution posté par cobbal est 101 caractères et actuellement il est le meilleur.

J'ai pensé, que de 80 caractères est un malade limite pour ce genre de problème. cobbal, avec ses 46 caractère solution totalement étonné moi - même si je dois admettre que j'ai passé un certain temps à la lecture de son explication avant que je partiellement compris ce qu'il avait écrit.

Answer 1

Je viens juste de commencer à apprendre J, alors, voici ma première tentative de golf:

103 62 49
46 caractères

   b =: 8 3 $ 1 11 5 2 6 7 3 13 9 12 7 16 14 3 25 19 18 22 23 13 29 24 4 28
   ,(,.{&s)I.s~:_1|.s=:0,~>./(1&{*{.<:[:i.{:)"1 b
1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0

même si je suis sûr que quelqu'un qui connaît la langue bien pourrait raccourcir ce en un peu

Une explication du code:

 NB. liste des numéros de place à droite lié de l'immeuble
 ([: j'. {:) 14 3 25 
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
 NB. comparer à gauche tenus de bâtiment et ensuite multiplier par la hauteur
 (1&{ * {. <: [: j'. {:) 14 3 25 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 3 3 3 3 3 3 3 3 3 3
 NB. s'appliquent à chaque rang de b, note comment entrées plus courtes sont rembourrés avec des 0
 (1&{ * {. <: [: j'. {:)"1 b
0 11 11 11 11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 6 6 6 6 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
...
 NB. l'effondrement de trouver max, ajouter un 0 à la fin pour une rotation plus tard, affecter à s
 ] s =: 0 ,~ >./ (1&{ * {. <: [: j'. {:)"1 b
0 11 11 13 13 13 13 13 13 0 0 0 7 7 7 7 3 3 3 18 18 18 3 13 13 13 13 13 13 0
 NB. faire pivoter le droit de 1 puis de les comparer à s de trouver où la hauteur des changements
 s ~: _1 |. s
0 1 0 1 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 0 1
 NB. trouver des indices de toutes les différences
 I. s ~: _1 |. s
1 3 9 12 16 19 22 23 29
 NB. paire chaque index à la hauteur de l'immeuble,
 (,. {&s) I. s ~: _1 |. s
 1 11
 3 13
 9 0
...
 NB. et enfin aplatir la liste
 , (,. {&s) I. s ~: _1 |. s
1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0

Answer 2

Python, 89 caractères, également à l'aide de Triptyque de 5001 triche:

B=[[1,11,5],[2,6,7],[3,13,9],[12,7,16],[14,3,25],[19,18,22],[23,13,29],[24,4,28]]

x=o=0
while x<5001:
 n=max([H for L,H,R in B if L<=x<R]+[0])
 if n-o:print x,n,
 o=n;x+=1

Remplacement d' 5001 par max(map(max,B))+1 pour permettre à (presque) arbitrairement grandes villes feuilles 102 caractères.

Révision De L'Histoire:

• sauvé deux caractères, comme décrit dans John Pirie commentaire
• enregistré un char comme MahlerFive suggéré

Answer 3

Python: 115 caractères

Comme l'OP, je ne suis pas y compris la déclaration des données, mais je compte les espaces.

D = [(1,11,5), (2,6,7), (3,13,9), (12,7,16), 
 (14,3,25), (19,18,22), (23,13,29), (24,4,28)]

P=[max([0]+[h for s,h,e in D if s<=x<e])for x in range(5001)]
for i,x in enumerate(P[1:]):
   if x!=P[i]:print i+1,x,

Notez que je suis en utilisant le lien fourni par l'OP comme la définition exacte du problème. Par exemple, je triche un peu, en supposant il n'y a pas de construction de coordonner plus de 5000 personnes, et que toutes les coordonnées sont des entiers positifs. Le post original n'est pas soumise à de fortes contraintes assez pour que ce soit amusant, à mon avis.

edit: merci à John Pirie pour l'astuce sur l'effondrement de la construction de liste dans l'impression de boucle. Comment avais-je rater ça?!

edit: j'ai changé d' range(1+max(zip(*D)[2])) de range(5001) après la décision de l'utilisation de l' exacte définition qui en est donnée dans le problème original. La première version serait en mesure de gérer les bâtiments de l'arbitraire des nombres entiers positifs (en supposant que tous les tenir en mémoire).

edit: Réalisé que j'étais de compliquer à l'excès des choses. Vérifier mes révisions.

BTW - j'ai un pressentiment, il y a un beaucoup plus élégante, et éventuellement plus court, moyen pour ce faire. Quelqu'un me battre!

Answer 4

176 octets WinXP .COM exécutable:

vQoAgMYQjsKO2jPAM/+5AIDzq7QLzSE8/751AXQDvoQB6DkAi/noNACL2egvACn5A/87HXYCiR2D xwLi9eviM8mZ9/VSQQvAdfeI+rQCzSG3LFqAwjC0As0h4vbD/9Y8CnP6D7bI/9Y8CnPwtACR9+UD yOvxtAvNITz/dRO0CM0hLDDDtAHNITwadfW+kAHDM/Yz/7cgrTn4dA+L+I1E/tHo6Jr/i8folf8L 9nXozSA=

Base64, j'ai utilisé ce site pour le coder. Décoder pour un .com fichier. Le programme lit l'entrée standard stdin jusqu'à ce qu'une des expressions du FOLKLORE, qui est une combinaison de touches Ctrl-Z lors de la lecture à partir de la console, puis affiche le résultat sur la sortie standard stdout.

EDIT: Le code source:

    mov bp,10
    add dh,10h
    mov es,dx
    mov ds,dx
    xor ax,ax
    xor di,di
    mov cx,8000h
    rep stosw
    mov ah,0bh
    int 21h
    cmp al,255
    mov si,offset l9
    je l1
    mov si,offset l11
l1:
    call l7
    mov di,cx
    call l7
    mov bx,cx
    call l7
    sub cx,di
    add di,di
l2:
    cmp bx,[di]
    jbe l3
    mov [di],bx
l3:
    add di,2
    loop l2
    jmp l1
l4:
    xor cx,cx
l5:
    cwd
    div bp
    push dx
    inc cx
    or ax,ax
    jnz l5
    mov dl,bh
    mov ah,2
    int 21h
    mov bh,44
l6:
    pop dx
    add dl,48
    mov ah,2
    int 21h
    loop l6
    ret
l7:
    call si
    cmp al,10
    jae l7
    db 0fh, 0b6h, 0c8h
l8:
    call si
    cmp al,10
    jae ret
    mov ah,0
    xchg cx,ax
    mul bp
    add cx,ax
    jmp l8
l9:
    mov ah,0bh
    int 21h
    cmp al,255
    jne l12
    mov ah,8
    int 21h
l10:
    sub al,48
    ret
l11:
    mov ah,1
    int 21h
    cmp al,26
    jne l10
    mov si,offset l12
    ret
l12:
    xor si,si
    xor di,di
    mov bh,32
l13:
    lodsw
    cmp ax,di
    je l14
    mov di,ax
    lea ax,[si-2]
    shr ax,1
    call l4
    mov ax,di
    call l4
l14:
    or si,si
    jne l13
    int 20h

Compilé, comme d'habitude pour moi, à l'aide de l'A86.

Answer 5

Python: 133 caractères, de la mémoire et du temps efficace, pas de restrictions sur l'entrée des données

D = [(1,11,5), (2,6,7), (3,13,9), (12,7,16), (14,3,25), (19,18,22), (23,13,29), (24,4,28)]

l,T=0,zip(*D)
for x,h in map(lambda x:(x,max([y for a,y,b in D if a<=x<b]or[0])),sorted(T[0]+T[2])):
    if h!=l: print x,h,
    l=h

explication:

lambda x:(x,max([y for a,y,b in D if a<=x<b]or[0])

renvoie la position et la hauteur à la position x.

Désormais en boucle sur la triées coordonner la liste compilée par sorted(zip(*D)[0]+zip(*D)[2]) et de sortie si la hauteur des changements.

la deuxième version n'est pas aussi efficace que l'un au-dessus et a les coordonnées limite mais ne l'utilise 115 caractères:

for x in range(100):
    E=[max([y for a,y,b in D if a<=(x-i)<b]+[0])for i in(0,1)]
    if E[0]-E[1]:print x,E[0],