^{C'est le premier d'une série de défis Island Golf. Prochain challenge}

Avec un îlot en ASCII-art, affiche un chemin optimal pour le contourner.

Contribution

Votre entrée sera une grille rectangulaire composée de deux caractères, représentant la terre et l’eau. Dans les exemples ci-dessous, la terre est #et l'eau est ., mais vous pouvez substituer deux caractères distincts de votre choix.

...........
...##......
..#####....
..#######..
.#########.
...#######.
...#####.#.
....####...
...........

Il y aura toujours au moins une tuile de terre. Les tuiles de terrain seront toutes contiguës (c'est-à-dire qu'il n'y a qu'une seule île). Les dalles d’eau seront également contiguës (c’est-à-dire qu’il n’ya pas de lacs). La bordure extérieure de la grille sera constituée de carreaux d’eau. Les tuiles de terrain ne seront pas reliées en diagonale: vous ne verrez jamais quelque chose comme

....
.#..
..#.
....

Sortie

Votre code doit sortir la même grille, avec une circumnavigation la plus courte dessinée. Dans les exemples ci-dessous, le chemin de circumnavigation est dessiné avec o, mais vous pouvez remplacer n'importe quel caractère tant qu'il est distinct de vos personnages de terre et d'eau.

Une circumnavigation est une simple courbe fermée, entièrement dessinée sur des tuiles d'eau, qui entoure complètement toutes les tuiles de terrain de la grille. Les connexions diagonales sont autorisées. Par exemple, ceci est une circumnavigation de l'île ci-dessus (mais pas la plus courte):

.ooooo.....
o..##.oo...
o.#####.o..
o.#######o.
o#########o
ooo#######o
..o#####.#o
..oo####..o
....oooooo.

La longueur d'une circumnavigation est calculée comme suit: pour chaque paire de tuiles adjacentes sur le chemin, si elles sont connectées horizontalement ou verticalement, ajoutez 1; s'ils sont connectés en diagonale, ajoutez √2. La longueur du chemin ci-dessus est de 22 + 7√2 (31.9).

Une circumnavigation la plus courte est une circumnavigation dont la longueur est la plus courte possible. Votre programme doit générer tout chemin répondant à cette condition. Pour la plupart des îles, les solutions possibles seront multiples. Voici une solution pour l’île ci-dessus, de longueur 10 + 13√2 (28.4):

...oo......
..o##oo....
.o#####oo..
.o#######o.
o#########o
.o.#######o
..o#####.#o
...o####.o.
....ooooo..

Détails

Votre solution peut être un programme complet ou une fonction . Toutes les méthodes d'entrée et de sortie par défaut sont acceptables.

Votre entrée et votre sortie peuvent être une chaîne multiligne ou une liste de chaînes. Si votre langue a un type de caractère distinct des chaînes à caractère unique, vous pouvez remplacer "liste de caractères" par "chaîne" dans la phrase précédente. Si votre langue doit entrer la hauteur et / ou la largeur de la grille, vous pouvez le faire. Votre sortie peut (éventuellement) avoir une nouvelle ligne de fin. Comme mentionné ci-dessus, vous pouvez utiliser trois caractères distincts à la place de #.o(veuillez spécifier dans votre soumission les caractères que vous utilisez).

Cas de test

A. Îles avec les plus courtes circumnavigations uniques:

...
.#.
...

.o.
o#o
.o.

......
.####.
......

.oooo.
o####o
.oooo.

......
......
..##..
...#..
......
......

......
..oo..
.o##o.
..o#o.
...o..
......

.......
.#####.
...#...
...#...
.#####.
.......

.ooooo.
o#####o
o..#..o
o..#..o
o#####o
.ooooo.

.......
...#...
...#...
.#####.
...#...
...#...
.......

...o...
..o#o..
.o.#.o.
o#####o
.o.#.o.
..o#o..
...o...

.......
.#####.
.##..#.
..#..#.
.......

.ooooo.
o#####o
o##..#o
.o#..#o
..oooo.

B. Exemple d'îlot avec plusieurs solutions possibles:

........
....##..
...####.
..###...
.#####..
.#####..
..##....
........

Sorties possibles:

....oo..
...o##o.
..o####o
.o###.o.
o#####o.
o#####o.
.o##oo..
..oo....

....oo..
...o##o.
..o####o
.o###.o.
o#####o.
o#####o.
.o##.o..
..ooo...

....oo..
...o##o.
..o####o
.o###..o
o#####.o
o#####o.
.o##oo..
..oo....

....oo..
...o##o.
..o####o
.o###..o
o#####.o
o#####o.
.o##.o..
..ooo...

C. Grand test en tant que Gist

C'est du code-golf : c'est le code le plus court dans chaque langue qui gagne.

Mathematica (version 9), 165 octets

La ConvexHullMeshfonction courte et agréable utilisée par Greg Martin n'a été introduite que dans la version 10 de Mathematica. J'ai donc pensé essayer de m'en passer, en utilisant mon ancienne version 9 de Mathematica. J'ai toutefois réussi à la raccourcir un peu! Il est une fonction qui prend et retourne une liste de chaînes (avec ., #et ocomme les symboles).

""<>#&/@("o"MorphologicalTransform[MorphologicalComponents[#,Method->"ConvexHull"],Max[#(1-#[[2,2]])CrossMatrix@1]&]+"#"#/.{0->"."})&[Characters@#/.{"."->0,"#"->1}]&

Explication:

• Tout d'abord, Characters@# /. {"."->0, "#"->1}transforme l'entrée en une matrice de 0s et de 1s.
• "o"MorphologicalTransform[MorphologicalComponents[#,Method->"ConvexHull"],Max[#(1-#[[2,2]])CrossMatrix@1]&]+"#"#utilise ensuite les puissantes capacités de traitement d'images de Mathematica (mais extrêmement lourdes en octets…) pour remplir d'abord la coque convexe de l'île (qui est la forme que vous obtiendriez si vous étiriez une ficelle autour de celle-ci), puis définissez ses limites. Nous multiplions ensuite cette matrice par la chaîne "o"pour obtenir une matrice de 0s et "o"s (grâce à l'adaptabilité impressionnante de Mathematica à propos des types), et ajoutons cela à "#"la matrice de l'île.
• Enfin, ""<>#& /@ (... /. {0->"."})transforme cette matrice de "o"s, "#"s et 0s en une matrice de "o"s, "#"s et "."s et joint chaque ligne à une chaîne.

Lorsque nous testons cela sur l'exemple B , nous obtenons la sortie

{"....oo..",
 "...o##o.",
 "..o####o",
 ".o###..o",
 "o#####o.",
 "o#####o.",
 ".o##oo..",
 "..oo...."}

[Edit, grâce à Greg Martin:] Si nous sommes autorisés à utiliser des tableaux de caractères au lieu de listes de chaînes, nous pouvons réduire ce nombre à 144 octets:

"o"MorphologicalTransform[MorphologicalComponents[#,Method->"ConvexHull"],Max[#(1-#[[2,2]])CrossMatrix@1]&]+"#"#/.{0->"."}&[#/.{"."->0,"#"->1}]&

(Mais votez pour la solution de Notatree , c'est mieux!)

Mathematica, 168 octets

(x_~n~y_:=Min[Norm[x-#]&/@y];i=#;p=i~Position~#&;t=p["#"|"."]~Select~#&;(i~Part~##="o")&@@@t[#~n~t[ConvexHullMesh[Join[s=p@"#",#+{.1,.1}&/@s]]~RegionMember~#&]==1&];i)&

Fonction pure prenant un tableau 2D de caractères en entrée et renvoyant un tableau 2D de caractères. Une version plus facile à lire:

1  (x_~n~y_ := Min[Norm[x - #] & /@ y];
2  i = #; p = i~Position~# &; 
3  t = p["#" | "."]~Select~# &;
4  (i~Part~## = "o") & @@@ 
5    t[#~n~
6      t[ConvexHullMesh[
7        Join[s = p@"#", # + {.1, .1} & /@ s]]
8      ~RegionMember~# &] == 1 &];
9  i) &

La ligne 1 définit une fonction nqui produit la distance (la plus petite) entre un point xdu plan et un ensemble yd’autres points. La ligne 2 initialise la variable ià l'entrée, à la fois pour résoudre une ambiguïté de curry et pour pouvoir la modifier afin de produire la sortie éventuelle; La ligne 2 définit également une fonction pqui renvoie les coordonnées de toutes les occurrences de son entrée dans i.

Sur la ligne 3, p["#" | "."]représente chaque coordonnée de la carte en entrée (puisque tous ses caractères sont un "#"ou "."), ainsi test une fonction qui sélectionne uniquement les coordonnées qui satisfont une propriété encore non spécifiée. Sur la ligne 4, i~Part~## = "o"va changer un tas d'entrées du ipersonnage "o"; ces caractères seront sélectionnés dans l'ensemble des coordonnées possibles en fonction des éléments des lignes 5 à 8. Et la ligne 9 ne fait que renvoyer la réponse une fois qu'elle est calculée.

Ok, l'infrastructure est faite, maintenant au calcul réel. ConvexHullMeshest intégré à Mathematica pour calculer la coque convexe d’un ensemble de points (le plus petit polygone convexe contenant ces points). Moralement, cela devrait "remplir" les criques et les fjords de l'île (ce qui est s = p@"#"), pour les écarter de notre cicrumnavigation. Il y a un petit problème avec le ConvexHullMeshmoment où tout cet ensemble de points est dans une ligne (merci, cas de test n ° 2), que nous résolvons en ajoutant une version légèrement décalée de slui-même à la ligne 7. Cette sortie est un polygone, donc les lignes 7 -9 (t[...~RegionMember~# &]) produit une liste des points avec des coordonnées entières dans ce polygone. Enfin, la ligne 5 et la fin de la ligne 9 calculent tous les points qui se trouvent à une distance exactement égale à 1 (et non pas 0) à partir de cet ensemble de points entiers; cet ensemble devient le chemin circumnavigating.

Vous trouverez ci-dessous la sortie du grand cas de test sur le lien de l'OP. Remarquez en haut à gauche, les choix inhabituels de quand aller par rapport à l'ouest par rapport au sud-ouest suggèrent le fait que cela trace une ligne invisible de pente -2/3 entre deux péninsules (ledit segment de ligne faisant partie de la limite de la coque convexe).

........................
.............o..........
...........oo#ooooooo...
..........o#.#.##...#o..
........oo.#.#.###.##o..
.......o..########.##o..
.....oo...############o.
...oo#....############o.
..o#.###.##############o
.o##.##################o
.o####################o.
.o.##################.o.
.o##################..o.
.o..################..o.
o###################..o.
o#####################o.
o.##################.o..
o####################o..
o#...##############.o...
o##...#############o....
o#.....###....#oooo.....
.oooooo#ooooooo.........
.......o................

Python 3, 779 octets (mise en retrait avec des onglets)

Ceci est l'ensemble du programme. Il lit les entrées de stdin et les affiche sur stdout. Stdin doit se terminer par EOF. Exemple exécuté avec la grande entrée: https://ideone.com/XIfYY0

import itertools,sys
L=list
C=itertools.count
d=L(map(L,filter(None,sys.stdin.read().split('\n'))))
X=len(d[0])
Y=len(d)
R=range
def P(r):return all(d[y][x]=='.'for x,y in r)
def S(f):
    for n in C(0):
        if P(f(n)):l=n
        else:break
    for n in C(l+1):
        if P(f(n)):return l,n
def f(V,a,*b):return L(eval('lambda '+a+':('+i+')',V)for i in b)
V=locals()
def D(n):
    y=min(n,Y-1);x=n-y
    while y>=0and x<X:yield(x,y);x+=1;y-=1
def E(n):
    x=max(0,n-Y);y=x+Y-n
    while y<Y and x<X:yield(x,y);x+=1;y+=1
F=f(V,'p','(p,y)for y in R(0,Y)','(x,p)for x in R(0,X)')+[D,E]
r=f(V,'x,y','x','y','x+y','x-y+Y')
B=L(map(S,F))
for x in R(0,X):
    for y in R(0,Y):
        z=L(zip(r,B))
        if all(g(x,y)in R(a,b+1)for g,(a,b)in z)and any(g(x,y)in e for g,e in z):d[y][x]='o'
print('\n'.join(''.join(x)for x in d))

L'idée est simple: elle calcule les plus petites limites octogonales et dessine les cellules situées à l'intérieur de toutes les limites calculées et coupant au moins l'une des arêtes.

JavaScript (ES6), 369 343 octets

f=s=>(a=s.split`
`.map(s=>[...s]),m=Array(8),a.map((b,i)=>b.map((c,j)=>c>'#'||[i-j,i,j+i,j,j-i,-i,-i-j,-j].map((d,k)=>d>m[k]||(m[k]=d-1)))),[o,p,q,r,t,u,v,w]=m,g=(i,j,k,l,...p)=>i-k|j-l?a[i][j]=g(i+(k>i)-(k<i),j+(l>j)-(l<j),k,l,...p):1/p[0]?g(k,l,...p):'o',g(p,p-o,p,q-p,q-r,r,r-t,r,-u,t-u,-u,u-v,w-v,-w,o-w,-w,p,p-o),a.map(b=>b.join``).join`
`)

Explication: La chaîne est divisée en un tableau de caractères (je ne sais pas si l'entrée en tableau de caractères est acceptable). Le tableau est ensuite itéré et les positions de tous les carrés sont localisées. Les lignes de délimitation données par les équations x - y = o, x = p, x + y = q, y = r, y - x = t, -x = u, -x - y = v, -y = wsont déterminées de telle sorte que le paramètre maximal possible est choisi où toutes les terre se trouve au - delà de la ligne. Cela a pour effet de renfermer l'île dans un octogone. Les coordonnées des coins de l'octogone sont facilement calculées à partir des paramètres et les cellules de son bord sont remplies. La matrice est ensuite reliée dans une chaîne. La raison pour laquelle un octogone suffit est la suivante:

   /o#     /o#     /o#
 |/o #   |/o #   |/ o#
 *o###   * o #   *  o#
/|o #   /|o #   /| o#
 |o#     |o#     |o#

Considérons un coin de l'octogone. À un moment donné le long des deux bords, le chemin sera limité par la terre car nous avons construit l’octogone pour toucher la terre aussi près que possible. S'il n'y a pas de terrain au coin lui-même, le chemin pourrait emprunter les itinéraires alternatifs, comme indiqué à droite, mais le nombre de marches orthogonales et diagonales est identique, de sorte que la distance est inchangée.

Python 3.5, 224, 263, 234 218 octets

Mettez 16 autres octets au golf en supprimant la fonction imbriquée et en en faisant un one-liner.

def h(s,k=0,i=0):w=s.find('\n')+1;x=s.find('X')-w;k=k or x;d=[1,w+1,w,w-1,-1,-w-1,-w,-w+1]*2;u=s[:k]+'o'+s[k+1:];return['X'>s[k]and i<8and(h(u,k+d[i+2],i+2)or h(u,k+d[i+1],i+1)or h(u,k+d[i],i))or'',s][s[k]>'X'and k==x]

Golfé 29 octets:

def f(s):
 w=s.find('\n')+1;x=s.find('X')-w;d=[1,w+1,w,w-1,-1,-w-1,-w,-w+1]*2
 def h(s,k,i):u=s[:k]+'o'+s[k+1:];return['X'>s[k]and i<8and(h(u,k+d[i+2],i+2)or h(u,k+d[i+1],i+1)or h(u,k+d[i],i))or'',s][s[k]>'X'and k==x]
 return h(s,x,0)

L'entrée est une chaîne unique utilisant "~" pour l'océan, "X" pour la terre et "o" pour la limite. (Utiliser 'X' enregistre un octet pour '>' au lieu de '==')

Version moins golfée avec commentaires:

def f(s):
    w=s.find('\n')+1                         # width of one row
    x=s.find('X')-w                          # starting point
    d=[1,w+1,w,w-1,-1,-w-1,-w,-w+1]*2        # delta to add to current index to move in 
                                             # the 8 directions: E, SE, S, SW, W, NW, 
                                             # N, NE. Make it long to avoid
                                             # lots of modulo operations in 
                                             #    the recursive calls

    def h(s,k,i):                            # s is the island string, k the current
                                             # position, i the direction index
        if s[k]>'X'and k==x:                 # if back at the begining,
            return s                         #   return the map

        elif 'X'>s[k] and i<8:               # if there is water here, and haven't
                                             #  looped around,
            u=s[:k]+'o'+s[k+1:]              #  make a new map with an 'o' in the 
                                             #  current spot

            r = h(u,k+d[i+2],i+2)            # try a 90 degree right turn
            if r: return r

            r = h(u,k+d[i+1],i+1)            # try a 45 degree turn
            if r: return r

            r= h(u,k+d[i],i)                 # try straight ahead
            if r: return r

        return ''                            # this path failed

    return h(s,x,0)

C # 7 - 414 369 327 octets

Edit : passage en boucle 1D, informatique iet jà la volée

Édition : modification de la méthode de saisie, de la table de consultation réduite et passage aux limites initiales bien définies ... et suppression de l'espace inutile dans la dernière boucle for externe

using C=System.Console;class P{static void Main(){var D=C.In.ReadToEnd().Replace("\r","");int W=D.IndexOf('\n')+1,H=D.Length,z=H,k,q,c;int P()=>z%W*(k%3-1)+z/W*(k/3-1)+H;var B=new int[9];for(;z-->0;)for(k=9;k-->0&D[z]%7<1;)if(B[k]<=P())B[k]=P()+1;for(;++z<H;C.Write(q>9?'o':D[z]))for(q=k=9;k-->0;)q*=(c=P()-B[k])>0?0:c<0?1:2;}}

Essayez-le en ligne

Programme complet, prend entrée dans la norme, il imprime à des normes, usages #, .et o. Pour chaque cellule, il calcule un "profil" (qui correspond à la distance sur 8 directions (il semble en calculer un neuvième par souci de commodité, mais c'est toujours le cas 0), et enregistre un maximum de chacune d'entre elles. Il écrit ensuite la totalité de la carte. Encore une fois, et remplace toute cellule qui est à la fois sur une limite et pas en dehors de toute avec un "0". Le code commenté ci-dessous explique comment tout cela fonctionne.

Selon ma réponse à Sauver les oies de l'extinction , cela produit le plus petit octogone (circumnavigation valide avec la plus grande surface) qui délimite l'île.

Remarque : pour une fois dans ma vie, j'utilise quelque chose de la décennie actuelle et ce code nécessite la compilation de C # 7. Si vous n'avez pas C # 7, il y a une ligne à remplacer, qui est clairement indiquée dans le code.

Exemple d'utilisation et de sortie:

type t7.txt | IslandGolf1.exe

.........ooooooooooo....
........o....#......o...
.......o...#.#.##...#o..
......o....#.#.###.##.o.
.....o....########.##..o
....o.....############.o
...o.#....############.o
..o#.###.##############o
.o##.##################o
o.####################.o
o..##################..o
o.##################...o
o...################...o
o###################...o
o#####################.o
o.##################..o.
o####################o..
o#...##############.o...
o##...#############o....
o#.....###....#...o.....
.o.....#.........o......
..ooooooooooooooo.......

Code formaté et commenté:

using C=System.Console;

class P
{
    static void Main()
    {
        // \n 10
        // # 35
        // . 46
        // o 111


        var D=C.In.ReadToEnd().Replace("\r",""); // map

        int W=D.IndexOf('\n')+1, // width
            H=D.Length, // length
            z=H, // position in map (decomposed into i and j by and for P)
            k, // bound index
            q, // bound distance, and later cell condition (0 -> outside, 8 -> inside, >8 -> on boudary)
            c; // (free), comparison store

        // 'indexes' into a profile for the point z at index k
        // effectively {i=z%W,j=z/W,-i,-j,i+j,j-i,-i-j,i-j,0}[k] (inside order is a bit different) (0 const is always treated as 'inside bounds')
        // each non-zero-const entry describes the distance in one of the 8 directions: we want to maximise these to find the 'outer bounds'
        // the non-zero-const bounds describe 8 lines, together an octogen
        int P()=>z%W*(k%3-1)+z/W*(k/3-1)+H; // new C#7 local method syntax (if you don't have C#7, you can test this code with the line below instead)
        //k=0;System.Func<int>P=()=>z%W*(k%3-1)+z/W*(k/3-1)+H; // old lambda syntax (must pre-assign k to make static checker happy)

        var B=new int[9]; // our current bounds, each is initially null (must only call P() when on a #)
        // B[k] starts off a 0, P() has a +H term, and W+(H/W)<H for W >= 3, so B[k] is assigned the first time we compare it (H-i-j always > 0)

        for(;z-->0;) // for each cell
            for(k=9;k-->0& // for each bound
                D[z]%7<1;) // if this cell is #
                if(B[k]<=P())B[k]=P()+1; // update bound if necessary (add one so that we define the bound _outside_ the hashes)
        // z=-1
        for(;++z<H; // for each cell
                C.Write(q>9?'o':D[z])) // print the cell (if q > 9, then we are on the bounds, otherwise, spit out whatever we were before)
            // check we are not 'outside' any of the bounds, and that we are 'on' atleast one of them
            for(q=k=9;k-->0;) // for each bound
                q*=(c=P()-B[k])>0?0: // outside bound (q=0)    (??0 is cheaper than (int) or .Value)
                    c<0?1: // inside (preserve q)
                    2; // on bound (if q != 0, then q becomes > 9)
    }
}