Mieliśmy kilka z wyzwań o spirali Ulama. Ale to nie wystarczy.

W tym wyzwaniu narysujemy trójkątną spiralę Ulama (w przeciwieństwie do zwykłej kwadratowej spirali Ulama). Oto szkic tego, jak wygląda spirala.

Jak wiemy, spirala Ulama układa wszystkie liczby naturalne w spiralę zewnętrzną i zaznacza tylko te, które są pierwsze. Na powyższym szkicu pokazane byłyby tylko liczby, które pojawiają się na czarno (liczby pierwsze).

Wyzwanie

Zaakceptuj liczbę N jako dane wejściowe i wyświetl trójkątną spiralę Ulama do tej liczby.

• Dane wejściowe mogą być argumentem standardowym lub funkcyjnym.
• Spirala powinna obrócić się w kierunku dodatnim (to znaczy przeciwnie do ruchu wskazówek zegara), jak na powyższym rysunku.
• Dowolny zwojów o 120 stopni powyższej liczby byłby prawidłowy, a zwrot może być inny dla różnych danych wejściowych. Ale najniższa strona implikowanych trójkątów powinna być pozioma, ponieważ jedynymi dozwolonymi zwojami są (wielokrotności) 120 stopni.
• Kod powinien działać teoretycznie (biorąc pod uwagę wystarczającą ilość czasu i pamięci) dla dowolnego N, aż do poziomu dozwolonego przez jakiekolwiek pośrednie obliczenia wykonane z domyślnym typem danych. doublewystarczy; nie potrzeba dużych typów całkowitych.
• Wszystkie wbudowane funkcje są dozwolone.
• Nie zaakceptuję własnej odpowiedzi (nie sądzę, że i tak byłaby najkrótsza ...).

Formaty wyjściowe

Wybierz jedną z poniższych opcji.

1. Wyświetl wykres ze znacznikiem (kropka, okrąg, krzyż, cokolwiek wolisz) przy liczbach pierwszych i nic przy liczbach innych niż pierwsze. Skala nie musi być taka sama dla dwóch osi. Oznacza to, że implikowane trójkąty nie muszą być równoboczne. Osie, linie siatki i etykiety osi są opcjonalne. Wymagane są tylko znaczniki liczb pierwszych.

   Przykładowy wynik dla N = 12 byłby następujący (porównaj z powyższym szkicem). Drugi wykres jest bardziej interesującym przykładem, odpowiadającym N = 10000.

2. Utwórz plik obrazu z powyższym, w dowolnym dobrze znanym formacie obrazu (takim jak png, tiff, bmp).

3. Wyświetl spiralę jako grafikę ASCII , używając jednego wybranego znaku dla liczb pierwszych i pustego miejsca dla liczb niepierwszych, z pustym miejscem do oddzielenia pozycji liczbowych w tym samym rzędzie. Dopuszczalne są wiodące lub końcowe spacje lub znaki nowej linii. Na przykład przypadek N = 12 użyty ojako znak byłby

                o
               · ·
              · o ·
               o · ·
              · o · o
   

   gdzie oczywiście obyłby wyświetlany tylko znak na liczbach pierwszych. W ·non-primes pokazano tutaj tylko w celach informacyjnych.

Kryterium wygranej

Prawdziwą nagrodą jest przekonanie się o tych niesamowitych wzorach Kod golfa, najkrótszy kod wygrywa.

CJam, 49 42 bajtów

Lri{)mp0S?}%{1$,)/(a@Wf%z+\L*}h;eeSff*W%N*

Wprowadź jako jedną liczbę całkowitą w STDIN. Wyjście jako siatka ASCII 0dla liczb pierwszych. Obrót spirali nie jest spójny: największa liczba spirali będzie zawsze w dolnym rzędzie.

Sprawdź to tutaj.

Wyjaśnienie

Podstawową ideą jest przedstawienie trójkąta jako poszarpanej tablicy 2D podczas wykonywania obliczeń. Tę tablicę uzyskuje się poprzez odwrócenie linii i wyrównanie wszystkich wierszy w lewo:

   4
  5 3
 6 1 2
7 8 9 A

Byłby reprezentowany jako

[[7 8 9 A]
 [6 1 2]
 [5 3]
 [4]]

Ponieważ odbiliśmy lustrzaną linię, chcemy zwinąć spiralę zgodnie z ruchem wskazówek zegara . Jest to wygodne, ponieważ wszystko, co musimy zrobić, to obrócić trójkąt przeciwnie do ruchu wskazówek zegara i przygotować kolejną listę podrzędną w kolejności. Możemy obrócić nierówną tablicę, odwracając wszystkie linie i transponując ją:

                                                           [[B C D E F]
[[7 8 9 A]         [[A 9 8 7]           [[A 2 3 4]          [A 2 3 4]
 [6 1 2]   reverse  [2 1 6]   transpose  [9 1 5]   prepend  [9 1 5]
 [5 3]      ---->   [3 5]      ------>   [8 6]      ---->   [8 6]
 [4]]               [4]]                 [7]]               [7]]

Oto kod. Jednym szczegółem, na który chciałbym zwrócić uwagę, jest ostatni bit, który tworzy układ trójkątny. Myślę, że to raczej fajne. :)

L     e# Push an empty array. This will become the spiral.
ri    e# Read input and convert to integer N.
{     e# Map this block over 0 to N-1...
  )   e#   Increment to get 1 to N.
  mp  e#   Test for primality.
  0S? e#   Select 0 or a space correspondingly.
}%
{     e# While the list we just created is not empty yet...
  1$  e#   Copy the spiral so far.
  ,)  e#   Get the number of lines and increment.
  /   e#   Split the list into chunks of that size.
  (a@ e#   Pull off the first chunk, wrap it in an array, pull up the spiral.
  Wf% e#   Reverse the lines of the spiral.
  z   e#   Transpose the spiral.
  +   e#   Prepend the new line.
  \L* e#   Swap with the remaining chunks and join them back together into a single list.
}h
;     e# Discard the empty list that's left on the stack.
ee    e# Enumerate the spiral. This turns each line into a pair of 0-based index
      e# and the line itself.
Sff*  e# Multiply each element of each pair with a space. For the enumeration index i,
      e# this produces a string of i spaces - the required indentation (keeping in
      e# mind that our spiral is still upside down). For the line itself, this
      e# riffles the cells with spaces, creating the required gaps between the cells.
      e# All of this works because we always end the spiral on the bottom edge.
      e# This ensures that the left edge is always complete, so we don't need
      e# different indentation such as in the N=12 example in the challenge.
W%    e# Reverse the lines to make the spiral point upwards.
N*    e# Join the lines with linefeeds.

MATL , 48 36 bajtów

:1-H*X^.5+Y[2j3/*YP*ZeYsG:Zp)'.'2$XG

Wykorzystuje bieżącą wersję (9.3.0) .

Wypróbuj online! Nie mam pojęcia, w jaki sposób kompilatorowi online udaje się przetłumaczyć dane wyjściowe na ASCII, ale robi to. Powoduje to przybliżony wykres ASCII dzięki funkcji Octave obsługiwanej przez kompilator online!

Edycja (4 kwietnia 2016 r.): Y[Zmieniono nazwę tej funkcji kod wydania 13.0.0. Link do kompilatora online zawiera tę zmianę, dzięki czemu można przetestować kod.

Przykład

>> matl
 > :1-H*X^.5+Y[2j3/*YP*ZeYsG:Zp)'.'2$XG
 > 
> 20000

tworzy wyjście graficzne (pokazana wersja MATLAB):

Wyjaśnienie

Kod wykorzystuje liczby zespolone do śledzenia ścieżki, po której następuje spirala. Jak można zobaczyć na pierwszej figurze w wyzwaniu, każda prosta noga spirali jest segmentem o wzrastającej długości 1, 2, 3, 4 ... i cyklicznie rosnącym ukierunkowaniu 120 stopni, 240 stopni, 0 stopni, 120 stopni. ..

Kod najpierw generuje indywidualne złożone przesunięcia z każdej liczby całkowitej na następny. Te złożone przemieszczenia mają wielkość 1 i kąt 2*pi/3, 4*pi/3lub 0(w radianach). W ten sposób można je łatwo wygenerować jako wyimaginowane wykładnicze. W tym celu najpierw używana jest liczba całkowita 0,1,2,2,3,3,3,3,4,4,4,4 ...

Ta sekwencja liczb całkowitych jest prawie podobna do sekwencji „n pojawia się n razy” ( OEIS A002024 ) i można ją uzyskać jako floor(sqrt(2*n)+.5)gdzie njest 0,1,2,3, ... Mnożenie przez 2j*pi/3, gdzie jjest jednostką urojoną, daje pożądane złożone przemieszczenia.

Przemieszczenia są kumulowane w celu obliczenia pozycji odpowiadających liczbom całkowitym w spirali. Pierwsza liczba całkowita w spirali, która 1jest dowolnie umiejscowiona w miejscu 1w płaszczyźnie zespolonej.

Na koniec pozycje odpowiadające liczbom innym niż pierwotne są odrzucane, a pozostałe wykreślane są w płaszczyźnie zespolonej.

:1-H*X^.5+Y[     % floor(sqrt(2*n)+.5) for n from 0 to N-1, where N is implicit input
2j3/*YP*Ze       % exp(2j*pi/3* ... )
Ys               % cumulative sum. Produces complex positions
G:               % vector 1,2...,N, where N is previous input
Zp               % logical index to select only prime numbers
)                % use that index to keep only complex positions of primes
'.'2$XG          % plot using marker '.'

Rysowanie należy wykonać za pomocą

LaTeX / PGF, 527 594 bajtów

\documentclass{standalone}\usepackage{pgf}\let\z\let\z\e\advance\z\f\ifnum\z\h\the\z\a\newcount\a\i\a\j\a\l\a\x\a\y\a\p\a\q\a\n\i=1\l=1\p=-1\q=1\def\m#1{\e\i by1\e\j by1\e\x by\h\p\e\y by\h\q\pgfmathparse{isprime(\h\i)}\f\pgfmathresult=1\pgfpathcircle{\pgfpoint{\h\x cm}{\h\y cm}}3pt\fi\f\j=\l\e\l by1\j=0\f\p=1\p=-1\q=1\else\f\p=-1\p=0\q=-1\else\p=1\q=0\fi\fi\fi\f#1>0\e#1by-1\m#1\fi}\begin{document}\begin{pgfpicture}\pgftransformcm10{cos(60)}{sin(60)}\pgfpointorigin\n=4000\m\n\pgfusepath{fill}\end{pgfpicture}\end{document}

527 bajtów to pełny dokument jak wyżej, tj. Zawierający preambułę i parametr (tutaj 4000, więc ~ 523 bez parametru). Tworzy plik PDF.

Podstawowy pomysł: po prostu narysuj. Wykorzystuje transformację macierzową dla siatki trójkątnej. Jedynym problemem jest to, że transformacja wpływa również na kropki (i je rozciąga). Wybieram więc znaczniki elipsy :) to, co mam na myśli, jest jasne na drugim obrazku (n = 250, 5pkt).

Kolejne zastrzeżenie: może obsłużyć tylko nieco mniej niż 5000 ze względu na maksymalny rozmiar stosu TeXa. Pierwszy obraz jest dla n = 4000. Najwyraźniej można zwiększyć rozmiar stosu , nie próbowałem tego.

Wykorzystuje PGF isprime().

Nie golfowany:

\documentclass[border=10cm]{standalone}

\usepackage{pgf}

\newcount\ulami
\newcount\ulamj
\newcount\ulamlen

\newcount\ulamx
\newcount\ulamy
\newcount\ulamdx
\newcount\ulamdy

\ulami=1 %
\ulamj=0 %
\ulamlen=1 %
\ulamdx=-1 %
\ulamdy=1 %
\ulamx=0 %
\ulamy=0 %

\def\ulamplot#1{%
  \advance\ulami by 1 %
  \advance\ulamj by 1 %

  \advance\ulamx by \the\ulamdx %
  \advance\ulamy by \the\ulamdy %

  \pgfpathmoveto{\pgfpoint{\the\ulamx cm}{\the\ulamy cm}}

  \pgfmathparse{isprime(\the\ulami)}
  \let\r=\pgfmathresult
  \ifnum\r=1
    \pgfpathcircle{\pgfpoint{\the\ulamx cm}{\the\ulamy cm}}{5pt}
  \fi

  \ifnum\ulamj=\the\ulamlen %
    \advance\ulamlen by 1 %
    \ulamj=0 %
    \ifnum\ulamdx=1 %
      \ulamdx=-1 %
      \ulamdy=1 %
    \else%
      \ifnum\ulamdx=-1 %
        \ulamdx=0 %
        \ulamdy=-1 %
      \else%
        \ulamdx=1 %
        \ulamdy=0 %
      \fi
    \fi
  \fi

  \ifnum#1>0 %
    \advance#1 by -1 %
    \ulamplot{#1}%
  \fi
}

\begin{document}

\begin{pgfpicture}
  \pgfmathsetmacro{\x}{cos(60)}
  \pgfmathsetmacro{\y}{sin(60)}
  \pgftransformcm{1}{0}{\x}{\y}{\pgfpointorigin}

  \pgfpathmoveto{\pgfpointorigin}
  \color{blue}
  \newcount\ulamn
  \ulamn=400
  \ulamplot{\ulamn}
  \pgfusepath{stroke,fill}
\end{pgfpicture}

\end{document}

Mathematica, 94 bajty

ListPlot@Accumulate[Join@@Table[ReIm@Exp[2i Pi/3I],{i,2#^.5},{i}]][[Prime@Range@PrimePi@#-1]]&

Wynik

%[10000]

Python, 263 bajty

Będąc nowym w Pythonie, z pewnością jest miejsce na ulepszenia :)

from matplotlib.pyplot import*
from math import*
def f(m):
 s=[];X=[];Y=[];i=x=y=0
 while len(s)<m:i+=1;s+=[i%3*pi*2/3]*i
 for i in range(m):
  x+=cos(s[i]);y+=sin(s[i]);j=i+2
  if all(map(lambda a:j%a>=1,range(2,int(j**.5+1)))):X+=[x];Y+=[y]
 scatter(X,Y);show()

Przykład:

f(100000)

R, 137 bajtów

Używa tylko wbudowanych funkcji, nawet dla liczb pierwszych. Biorąc pod uwagę wektoryzowane podejście zamiast iteracyjne, jest szybki, ale nie może obsłużyć dużych liczb.

Gra w golfa:

g=function(m){M=1:m;s=rep(M,M)[M]%%3*pi*2/3;k=cumsum;j=sapply(seq(s)+1,function(n)n<4|all(n%%2:n^.5>=1));plot(k(cos(s))[j],k(sin(s))[j])}

Nie golfowany:

g=function(m) {
  M = 1:m
  s = rep(M,M)[M] %% 3 * pi * 2/3
  k=cumsum
  j=sapply(seq(s)+1,function(n)n<4|all(n%%2:n^.5>=1)) # primes
  plot(k(cos(s))[j],k(sin(s))[j])    # cumulated coordinates
}

Przykład:

g(10000)