Random ASCII Art of the Day # 5: Diamond Tilings

21

Czas na mash!

Jest to część nr 5 zarówno mojej Random Golf of the Day, jak i serii ASCII Art of the Day firmy Optimizer . Zgłoszenia w tym wyzwaniu zostaną uwzględnione w obu tabelach wyników (w których można znaleźć powiązane posty). Oczywiście możesz traktować to jak każde inne wyzwanie związane z golfem i odpowiedzieć na nie, nie martwiąc się o żadną z serii.

Otwór 5: Diamentowe tilings

Zwykły sześciokąt można zawsze wyłożyć kafelkami z takimi diamentami:

Użyjemy artystycznej reprezentacji tych tafli ASCII. W przypadku sześciokąta o długości boku 2 istnieje 20 takich nachyleń:

   ____     ____     ____     ____     ____     ____     ____     ____     ____     ____  
  /\_\_\   /\_\_\   /\_\_\   /\_\_\   /_/\_\   /_/\_\   /\_\_\   /_/\_\   /_/\_\   /_/\_\ 
 /\/\_\_\ /\/_/\_\ /\/_/_/\ /\/_/\_\ /\_\/\_\ /\_\/_/\ /\/_/_/\ /\_\/\_\ /\_\/_/\ /_/\/\_\
 \/\/_/_/ \/\_\/_/ \/\_\_\/ \/_/\/_/ \/\_\/_/ \/\_\_\/ \/_/\_\/ \/_/\/_/ \/_/\_\/ \_\/\/_/
  \/_/_/   \/_/_/   \/_/_/   \_\/_/   \/_/_/   \/_/_/   \_\/_/   \_\/_/   \_\/_/   \_\/_/ 
   ____     ____     ____     ____     ____     ____     ____     ____     ____     ____  
  /_/_/\   /\_\_\   /_/\_\   /_/_/\   /_/\_\   /_/\_\   /_/_/\   /_/_/\   /_/_/\   /_/_/\ 
 /\_\_\/\ /\/_/_/\ /_/\/_/\ /\_\_\/\ /\_\/_/\ /_/\/_/\ /_/\_\/\ /\_\_\/\ /_/\_\/\ /_/_/\/\
 \/\_\_\/ \/_/_/\/ \_\/\_\/ \/_/\_\/ \/_/_/\/ \_\/_/\/ \_\/\_\/ \/_/_/\/ \_\/_/\/ \_\_\/\/
  \/_/_/   \_\_\/   \_\/_/   \_\/_/   \_\_\/   \_\_\/   \_\/_/   \_\_\/   \_\_\/   \_\_\/ 

Biorąc pod uwagę długość boku N, należy wygenerować takie kafelki Nlosowo dla sześciokąta o długości boku . Dokładny rozkład nie ma znaczenia, ale każde kafelkowanie musi zostać zwrócone z niezerowym prawdopodobieństwem.

Ponieważ N ≤ 4zgłoszenie musi wygenerować kafelkowanie w ciągu 1 minuty co najmniej 80% czasu, a co najmniej 80% kafelków musi zostać wygenerowane w ciągu 1 minuty. Większość podejść nie będzie musiała się martwić tą zasadą (jest bardzo łagodna) - ma to na celu wykluczenie bardzo naiwnych algorytmów opartych na odrzucaniu, które generują dowolne ciągi znaków, dopóki nie pojawi się kafelkowanie.

Być może chcesz wiedzieć, że całkowitą liczbę możliwych przechyleń dla danego N można znaleźć w OEIS A008793 .

Możesz napisać pełny program lub funkcję i pobrać dane wejściowe za pomocą STDIN (lub najbliższej alternatywy), argumentu wiersza poleceń lub argumentu funkcji i wygenerować wynik za pomocą STDOUT (lub najbliższej alternatywy), wartości zwracanej funkcji lub parametru funkcji (wyjściowej).

Nie możesz wyprowadzać więcej spacji wiodących niż jest to konieczne do wyrównania sześciokąta (to znaczy lewy róg sześciokąta nie powinien mieć spacji przed nim). Każda linia może zawierać maksymalnie Nspacje (niekoniecznie spójne, więc możesz np. Mieć prostokątny wydruk, drukujący obwiednię sześciokąta).

To jest kod golfowy, więc wygrywa najkrótsze przesłanie (w bajtach). I oczywiście najkrótsze zgłoszenie na użytkownika wejdzie również do ogólnej tabeli liderów serii.

Liderów

Pierwszy post z każdej serii generuje tabelę wyników.

Aby upewnić się, że Twoje odpowiedzi się pojawią, zacznij każdą odpowiedź od nagłówka, używając następującego szablonu Markdown:

# Language Name, N bytes

gdzie Njest rozmiar twojego zgłoszenia. Jeśli poprawić swój wynik, to może zachować stare porachunki w nagłówku, uderzając je przez. Na przykład:

# Ruby, <s>104</s> <s>101</s> 96 bytes

(Język nie jest obecnie wyświetlany, ale fragment go wymaga i analizuje, a w przyszłości mogę dodać tabelę wyników według języków).

Martin Ender
źródło
3
Czy to tylko ja widzę przykładowy obraz w 3D?
LegionMammal978
3
@ LegionMammal978 Nie, to zupełnie normalne. ;) (I prawdopodobnie jest to również dobry sposób na podejście do wyzwania.)
Martin Ender
For N ≤ 4, your submission must produce a tiling within 1 minute at least 80% of the time.zbyt łatwe: 80% czasu to samo, podstawowe kafelki, w przeciwnym razie znajdę kolejne kafelki w dowolnym momencie
edc65
@ edc65 Dobra uwaga, pozwól mi to przeformułować.
Martin Ender

Odpowiedzi:

10

CJam, 105 bajtów

ri:A" __"e*A,2f*:B,[W1]{J+B:):B,{N1$S*"\/"J%A2*4$-:D*
0{;B{_1&!2mr+J*m1e>D(2*e<}%__:)&}g:B{'_t}/+@J+}*}fJ;

Dodano nową linię, aby uniknąć przewijania. Wypróbuj online

Wyjaśnienie:

To rozwiązanie rozpoczyna każdą linię jako zygzak, a następnie umieszcza na niej N znaków podkreślenia na podstawie ich pozycji w poprzedniej linii i kilku zasad. Otrzymałem to z serii obserwacji, patrząc na wynik jako zwykłą matrycę 2D znaków:

  • każda linia ma dokładnie N znaków podkreślenia
  • podkreślenia można zastąpić symbolem / lub \, aby uzyskać idealnie powtarzalny wzór zygzakowaty ( /\w górnej połowie, \/w dolnej połowie)
  • podkreślenia nie mogą dotykać boków i nie mogą przylegać do innego podkreślenia
  • podczas przechodzenia do następnego wiersza pozycja każdego podkreślenia zmienia się o -1, 0 lub 1
  • więcej, /_/może zmienić się tylko o -1 lub 0 i \_\może zmienić się tylko o 0 lub 1
  • dla początkowych pozycji podkreślenia możemy użyć "_ "wzorca lub " _"wzorca, oba są w porządku
  • powyższe zasady są wystarczające do uzyskania wszystkich przechyleń

Postanowiłem go zatem wdrożyć, zachowując poprzednie pozycje podkreślenia, modyfikując je losowo (2 opcje dla każdego podkreślenia) i powtarzając, aż reguły będą spełnione. W trakcie optymalizacji przełączyłem się na pozycje podkreślenia względem lewej strony sześciokąta (bez spacji).

ri:A" __"e*       read the input (A) and generate the top line
A,2f*:B           make an array [0 2 4 ... 2A-2] and store in B
                  these are the initial positions for the underscores
,                 B's length = A, used as the initial number of leading spaces
                  let's call it C
[W1]{…}fJ         for J in [-1 1] (top half, bottom half)
  J+              add J to C
  B:):B           increment the underscore positions (adjustment before each half)
  ,{…}*           repeat A times
    N1$S*         add a newline and C spaces
    "\/"J%        take "\/" and reverse it if J=-1 (zigzag pattern)
    A2*4$-:D*     calculate D=A*2-C and repeat the pattern
    0             dummy value (for the next loop)
    {…}g          do-while
      ;B          pop last value and push B
      {…}%        apply block to each item (say x)
        _1&!      duplicate x and calculate !(x&1) (for /_/ vs \_\)
        2mr+      randomly add 0 or 1
        J*m       multiply by J and subtract from x
        1e>       limit the minimum value to 1
        D(2*e<    and the maximum value to 2*(D-1)
      __:)&       check if the modified array has any adjacent values
    :B            store the new positions in B
    {'_t}/        place underscores over the zigzag pattern
    +@J+          bring C to the top and add J to it
;                 pop C

Stara wersja „3D”, 189 bajtów:

ri:A" __"e*aA4*S*aA2**+[0-2XXW1]:C;"/\_\\\/_/":D;A3m*{{C2/.f*:.+~
A(2*+:V;A+:U;2{UI+1$1$=4{_V+D4/I=@=t}/t}fI}:F~}/[0Y1WWW]:C;
"/_/\\\_\/":D;AaA*:B;A{A[_{_BI=e<)mr}fI]:B;{BQ={[PQR]F}fR}fQ}fPN*

Wypróbuj online

aditsu
źródło
+1 za świetną pracę, a także dlatego, że jeden głos dałby ci 10 000 powtórzeń, ale głównie za wspaniałą pracę. (Och, hej, spójrz na to. Gratulacje na 10 000 :))
Alex A.
Świetna analiza wzorów! Użyję tego do mojej odpowiedzi.
anatolyg
6

Python 2, 337 335 324 318 311 300 296 bajtów

from random import*
n=input()
R=range(n*2)
b=[]
l=[]
for i in R:o=abs(i-n)-(i<n);b+=[o];l+=[list(' '*o+'\//\\'[i<n::2]*(n*2-o))]
for i in R[:n]:
 o=1;p=n+i*2
 for j in R:r=randint(0,p<n*3+i*2-j);p+=(r or-1)*(o==r);q=p<=b[j];o=r|q;p+=q;l[j][p]='_';b[j]=p+1
for s in[' '*n+'__'*n]+l:print''.join(s)

Chodzi o to, aby najpierw utworzyć sześciokąt diamentów, taki jak ten:

  ____
 /\/\/\
/\/\/\/\
\/\/\/\/
 \/\/\/

A następnie wypełnij go ścieżkami podkreślenia w dół, takimi jak to:

  ____                          ____
 /_/\/\                        /\_\/\
/_/\/\/\    or maybe this:    /\/_/\/\
\_\/\/\/                      \/_/\/\/
 \_\/\/                        \_\/\/

Ostateczny wynik z dodanymi wszystkimi ścieżkami wyglądałby mniej więcej tak:

  ____                          ____  
 /_/\_\                        /\_\_\ 
/_/\/_/\    or maybe this:    /\/_/\_\
\_\/_/\/                      \/_/\/_/
 \_\_\/                        \_\/_/ 

Spora część kodu wymaga upewnienia się, że ścieżki te nie wykraczają poza granice ani się nie krzyżują.

Nieskluczony kod:

# Initialize l with all diamonds
blocked = []
l = [[] for _ in range(n*2)]
for i in range(n*2):
    offset = n-i-1 if i<n else i-n
    blocked.append(offset)
    l[i] += ' '*offset + ('/\\' if i<n else '\/')*(2*n - offset)

# Generate the random _'s
for i in range(n):
    oldright = True
    pos = n + i*2
    for j in range(n*2):
        # Go randomly right (true) or left (false), except when you out of bounds on the right side
        right = randint(0, 1) and pos < n*3 + i*2 - j
        if right == oldright:
            pos += 1 if right else -1
        if pos <= blocked[j]:
            right = True
            pos += 1
        l[j][pos] = '_'
        blocked[j] = pos + 1
        oldright = right

# Print the result
print ' '*n + '__'*n
for s in l:
    print ''.join(s)
Matty
źródło
1
Właśnie zauważyłem, że twój wynik wydaje się nieprawidłowy. W swoich dwóch przykładowych wynikach masz trójkąty (prawy górny i prawy dolny).
Martin Ender
1
@MartinEnder Przykłady pokazały tylko jedną „ścieżkę podkreślenia”, aby pokazać ideę algorytmu. Ostateczne wyjście ma wszystkie ścieżki (w tym przypadku 2), co eliminuje trójkąty. Dodałem także w przykładach ostatecznego wyniku.
Matty,
Och, rozumiem, to ma sens. Dziękuję za wyjaśnienie.
Martin Ender
2
Myślę, że można skrócić randint(0,1)*(p<n*3+i*2-j)do randint(0,p<n*3+i*2-j).
maja 21
O tak, dzięki!
Matty
4

Perl, 174 168 166 161

#!perl -n
for$l(-$_..$_){$t=/_/?join'',map'/_'x($%=rand
1+(@z=/__?/g)).'/\\'.'_\\'x(@z-$%),split/\/\\/:__
x$_;$l>0&&$t!~s!^.(\\.*/).$!$1!?redo:print$"x abs$l-.5,$_=$t.$/}

Spróbuj mnie .

nutki
źródło
Zawsze wydaje się generować ten sam kafelek (przynajmniej na ideone)
aditsu
@aditsu, Ideone pokazuje wynik w pamięci podręcznej po kliknięciu linku. Musisz uruchomić widelec, aby uruchomić go ponownie.
nutki
2

JavaScript ( ES6 ), 376 416 494

Po prostu być tam ...

Zbuduj wszystkie tilings, a następnie wybierz losowy. Czas na tilings 232848 dla N = 4 to ~ 45 sekund na moim laptopie. Nie próbowałem N = 5.

Jako EcmaScript 6 działa tylko w przeglądarce Firefox.

F=n=>{
  for(i=s=r=b='';i<n;i++)
    s='\n'+b+'/\\'[R='repeat'](n-i)+'_\\'[R](n)+s,
    r+='\n'+b+'\\/'[R](n-i)+'_/'[R](n),
    b+=' ';
  for(h=[t=0],x=[s+r];s=x[t];t++)
    for(d='';!d[n*3];d+='.')
      if(l=s.match(r=RegExp("(\n"+d+"/)\\\\_(.*\n"+d+"\\\\)/_","g")))
        for(j=2<<l.length;j-=2;h[z]||(h[z]=x.push(z)))
          z=s.replace(r,(r,g,h)=>(k+=k)&j?g+'_/'+h+'_\\':r,k=1);
  return b+'__'[R](n)+x[Math.random()*t|0]
}


function go()
{
  var n = N.value | 0,
  t0 = performance.now(),
  r = F(n),
  t1 = performance.now();
  
  O.innerHTML = r+'\n\nTime (msec): '+(t1-t0)
}
N: <input id=N value=3><button onclick="go()">GO</button>
<pre id=O></pre>

edc65
źródło
W Chromium 42 otrzymuję „Uncaught SyntaxError: U nieoczekiwany token =>” i „Uncaught ReferenceError: go nie jest zdefiniowany”
aditsu
1
@aditsu to ES6, Chrome: nie Firefox: tak. Czy to nie jest dobrze znany fakt?
edc65
Nie miałem pojęcia, spodziewałem się, że Chromium użyje najnowszego i największego, jak to się nazywa, pozornie nie javascript. Dziękuję za wyjaśnienie.
aditsu
Uruchomiłem go teraz w Firefoksie (31.5.3) i działa dla N = 1, 2 lub 3, ale dla N = 4 działa przez około 10 sekund, kończy i nic nie pokazuje (i nie ma błędu w konsoli )
aditsu
@aditsu nie jestem pewien ... może javascript w piaskownicy zostanie cicho zabity, gdy przekroczy limit czasu dom.max_script_run_time. Jest to globalna preferencja w około: config, moja jest ustawiona na 30.
edc65
1

SmileBASIC, 241 bajtów

INPUT N
T=N*2CLS?" "*N;"__"*N
DIM B[T]FOR I=-1TO N-1O=1P=N+I*2FOR J=0TO T-1IF I<0THEN O=ABS(J0N+.5)<<0B[J]=O?" "*O;MID$("\/\",J<N,2)*(T-O)ELSE R=P<N*3+I*2-J&&RND(2)P=P+(R*2-1)*(O==R)A=P<=B[J]R=R||A:P=P+A:LOCATE P,J+1?"_"B[J]=P+1O=R
NEXT
NEXT

Mocno oparty na odpowiedzi Matty'ego

12Me21
źródło