Trójkątna spirala Ulam

21

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.

wprowadź opis zdjęcia tutaj

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.

wprowadź opis zdjęcia tutaj

wprowadź opis zdjęcia tutaj

  1. Utwórz plik obrazu z powyższym, w dowolnym dobrze znanym formacie obrazu (takim jak png, tiff, bmp).
  2. 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.

Luis Mendo
źródło
2
W przyszłości polecam wybranie tylko jednego z [graficznych wyników] i [ascii-art], ponieważ powoduje to, że zgłoszenia są mniej porównywalne. Ale i tak fajne wyzwanie. :)
Alex A.,
@AlexA. Dzięki! Wezmę to pod uwagę. Więc ... czy będzie odpowiedź Julii? ;-)
Luis Mendo
Wow, dzięki za nagrodę, ale powinieneś zaakceptować własną odpowiedź. To jest najkrótsze. :)
Martin Ender
Zasługuje na to! Jeśli chodzi o akceptację odpowiedzi, jedną z zasad wyzwania było „Nie zaakceptuję własnej odpowiedzi”. Kiedy pomyślałem o tym wyzwaniu, nieuchronnie miałem na myśli MATL, z jego liczbą zespoloną i funkcjami graficznymi, więc to było trochę jak oszustwo :-)
Luis Mendo

Odpowiedzi:

13

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.
Martin Ender
źródło
1
Wiedziałem, że będziesz pierwszy!
Luis Mendo,
@LuisMendo Chciałem pominąć ten, ponieważ myślałem, że obliczanie indeksów siatki byłoby uciążliwe, ale potem zdałem sobie sprawę, że mogę obrócić cały trójkąt podczas dodawania linii.
Martin Ender
1
Zawsze podoba mi się twoje wyjaśnienie programów CJam, ponieważ mogę je zrozumieć i jestem zdumiony, jak skomplikowane, choć krótkie, mogą być te programy.
ETHprodukcje
10

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):

wprowadź opis zdjęcia tutaj

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 '.'
Luis Mendo
źródło
O co muszę przeczytać dalej
Brain Guider
Próbuje online! obsługiwać wyjście graficzne dla MATL?
Alex A.
Myślałem, że TIO nie obsługuje wyjścia graficznego? Jeśli tak się stanie, mogę łatwo MATL automatycznie zrzucić zdjęcia do .pngpliku, który będzie wyświetlany na stronie internetowej @AlexA
Luis Mendo
Hej! Zrobiłem prosty test ( plot(1:5)) i generuje on tekst-grafikę !! matl.tryitonline.net/#code=NTpYRw&input= @AlexA. Jak to jest ??
Luis Mendo,
4
WHOA! To cudownie!
Alex A.
8

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().

wprowadź opis zdjęcia tutaj

wprowadź opis zdjęcia tutaj

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}
Społeczność
źródło
1
Łał. Nigdy nie przyszło mi do głowy, aby zrobić to w LaTeX
Luis Mendo
Użycie lualatexlub inny dynamicznie alokujący kompilator powinien pozwolić ci ominąć rozmiar stosu, jeśli dobrze rozumiem odpowiedni komentarz. Więc to nie jest ograniczenie twojej odpowiedzi, tylko większość implementacji, w których ją uruchomisz.
Andras Deak,
Przepraszam, sprawdziłem, a limit wielkości stosu wejściowego nie jest związany z przydziałem pamięci, o którym wspomniałem w poprzednim komentarzu :(
Andras Deak
@AndrasDeak jest w porządku, dziękuję za sprawdzenie. Znalazłem metodę, która najwyraźniej zwiększa rozmiar stosu, ale nie próbowałem jej (jeszcze).
@CamilStaps dzięki, znalazłem inne podobne posty, ale też ich nie próbowałem. W każdym razie traktuję posty Christiana Feuersängera jako kanon :)
Andras Deak
2

Mathematica, 94 bajty

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

Wynik

%[10000]

wprowadź opis zdjęcia tutaj

njpipeorgan
źródło
2

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)

wprowadź opis zdjęcia tutaj

lambruscoAcido
źródło
Możesz skrócić s=[];X=[];Y=[];i=1;x=0;y=0dos=X=Y=[];i=1;x=y=0;
rp.beltran
Zignoruj ​​ten dodatkowy średnik na końcu. Powinno ci oszczędzić 8 bajtów.
rp.beltran
@ rp.beltran. To nie działa. Myślę, że jest to związane z faktem, że obiekty mają te same wartości. Można tylko dodać x=y=0.
lambruscoAcido
Mój zły, masz rację. Zapomniałem, że Python przekazuje listy przez referencje. Liczby są niezmienne, więc bezpiecznie jest robić liczby całkowite.
rp.beltran
1

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)

wprowadź opis zdjęcia tutaj

lambruscoAcido
źródło
Czy możesz dodać przykładowy wynik?
Luis Mendo,
@LuisMendo. Pewnie. Musiałem tylko wymyślić, jak dodać fabułę.
lambruscoAcido