Ulam spiral segitiga

21

Kami sudah beberapa dari tantangan tentang spiral Ulam. Tapi itu tidak cukup.

Dalam tantangan ini kita akan memplot spiral Ulam segitiga (sebagai lawan dari spiral Ulam persegi). Berikut ini sketsa bentuk spiral itu.

masukkan deskripsi gambar di sini

Seperti kita ketahui, spiral Ulam mengatur semua bilangan alami dalam spiral luar, dan hanya menandai yang prima. Jadi dalam sketsa di atas hanya angka yang muncul dalam warna hitam (bilangan prima) yang akan ditampilkan.

Tantangan

Terima angka N sebagai input dan tampilkan spiral Ulam segitiga ke angka itu.

  • Input dapat berupa stdin atau argumen fungsi.
  • Spiral harus berputar ke arah positif (yaitu, berlawanan arah jarum jam), seperti pada gambar di atas.
  • Setiap belokan 120 derajat pada gambar di atas akan valid, dan belokan mungkin berbeda untuk input yang berbeda. Tetapi sisi terendah dari segitiga tersirat harus horisontal, karena satu-satunya belokan yang diizinkan adalah (kelipatan) 120 derajat.
  • Kode harus berjalan secara teoritis (diberikan waktu dan memori yang cukup) untuk setiap N hingga apa yang diizinkan oleh perhitungan perantara yang Anda lakukan dengan tipe data default Anda. doublecukup; tidak perlu untuk tipe integer besar.
  • Semua fungsi bawaan diizinkan.
  • Saya tidak akan menerima jawaban saya sendiri (bukan berarti saya pikir itu akan menjadi yang terpendek ...).

Format output

Pilih salah satu dari yang berikut ini.

  1. Tampilkan grafik dengan marker (titik, lingkaran, silang, apa pun yang Anda inginkan) di bilangan prima, dan tidak ada pada bilangan non-prima. Skala tidak harus sama untuk kedua sumbu. Artinya, segitiga tersirat tidak harus sama sisi. Sumbu, garis kisi, dan label sumbu adalah opsional. Hanya penanda di nomor utama yang diperlukan.

    Contoh output untuk N = 12 adalah sebagai berikut (bandingkan dengan sketsa di atas). Plot kedua adalah contoh yang lebih menarik, sesuai dengan N = 10.000.

masukkan deskripsi gambar di sini

masukkan deskripsi gambar di sini

  1. Menghasilkan file gambar dengan di atas, dalam format gambar apa pun yang dikenal (seperti png, tiff, bmp).
  2. Tampilkan spiral sebagai seni ASCII , menggunakan satu karakter pilihan Anda untuk bilangan prima dan ruang kosong untuk non-bilangan prima, dengan ruang kosong untuk memisahkan posisi angka di baris yang sama. Ruang terdepan atau tertinggal atau baris baru diizinkan. Sebagai contoh, kasus N = 12 menggunakan okarakter

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

    di mana tentu saja hanya otanda di bilangan prima yang benar-benar akan ditampilkan. Di ·non-prima ditampilkan di sini hanya untuk referensi.

Kriteria kemenangan

Hadiah yang sebenarnya adalah melihat sendiri pola-pola yang luar biasa itu Kode golf, kode menang paling pendek.

Luis Mendo
sumber
2
Di masa depan saya akan merekomendasikan memilih hanya satu [grafis-output] dan [ascii-art] karena membuat kiriman kurang sebanding. Tapi tantangannya bagus. :)
Alex A.
@AlexA. Terima kasih! Saya akan memperhitungkannya. Jadi ... akankah ada jawaban Julia? ;-)
Luis Mendo
Wow, terima kasih atas hadiahnya, tetapi Anda harus menerima jawaban Anda sendiri. Ini adalah yang terpendek. :)
Martin Ender
Itu memang layak! Sedangkan untuk menerima jawaban, salah satu aturan tantangan adalah "Saya tidak akan menerima jawaban saya sendiri". Ketika saya memikirkan tantangan ini, mau tidak mau saya memiliki MATL dalam pikiran, dengan angka-angka yang kompleks dan fungsi grafis, jadi itu agak seperti menipu :-)
Luis Mendo

Jawaban:

13

CJam, 49 42 byte

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

Input sebagai bilangan bulat tunggal di STDIN. Output sebagai kisi ASCII dengan 0untuk bilangan prima. Rotasi spiral tidak konsisten: jumlah terbesar dari spiral akan selalu berada di baris bawah.

Uji di sini.

Penjelasan

Ide dasarnya adalah merepresentasikan segitiga sebagai array 2D yang acak saat melakukan perhitungan. Anda mendapatkan array ini dengan membalikkan garis dan meluruskan semua baris ke kiri:

   4
  5 3
 6 1 2
7 8 9 A

Akan diwakili sebagai

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

Karena kami telah mencerminkan garis, kami ingin menggulung spiral dengan searah jarum jam . Itu mudah, karena yang perlu kita lakukan adalah memutar segitiga berlawanan arah jarum jam dan menambahkan sublist berikutnya secara berurutan. Kita dapat memutar array yang rusak dengan membalik semua garis dan mentransposnya:

                                                           [[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]]

Jadi ini kodenya. Satu detail yang ingin saya perhatikan adalah bit terakhir yang menciptakan tata letak segitiga. Saya pikir itu agak bagus. :)

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
sumber
1
Saya tahu Anda akan menjadi yang pertama!
Luis Mendo
@LuisMendo Saya sebenarnya akan melewati yang satu ini, karena saya pikir perhitungan indeks kisi akan membosankan, tetapi kemudian saya menyadari bahwa saya bisa memutar seluruh segitiga sambil menambahkan garis.
Martin Ender
1
Saya selalu menyukai penjelasan Anda tentang program CJam karena saya bisa memahaminya , dan saya kagum pada betapa rumitnya, namun singkatnya, program ini bisa.
ETHproduk
10

MATL , 48 36 byte

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

Menggunakan rilis saat ini (9.3.0) .

Cobalah online! Tidak tahu bagaimana kompiler online berhasil menerjemahkan output grafis ke ASCII, tetapi itu menghasilkan perkiraan plot ASCII berkat fitur Octave yang didukung oleh kompiler online!

Edit (4 April 2016): fungsi Y[telah diubah namanya ksejak rilis 13.0.0. Tautan ke kompiler online menyertakan perubahan ini, sehingga kode dapat diuji.

Contoh

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

menghasilkan output grafis (versi MATLAB ditampilkan):

masukkan deskripsi gambar di sini

Penjelasan

Kode menggunakan bilangan kompleks untuk melacak jalur yang diikuti oleh spiral. Seperti yang dapat dilihat dari gambar pertama dalam tantangan, setiap kaki lurus dari spiral adalah segmen dengan peningkatan panjang 1, 2, 3, 4 ... dan secara siklikatif meningkatkan orientasi 120 derajat, 240 derajat, 0 degress, 120 degress. ..

Kode pertama menghasilkan perpindahan kompleks individu dari setiap nomor bilangan bulat ke yang berikutnya. Perpindahan kompleks ini memiliki magnitudo 1 dan sudut 2*pi/3, 4*pi/3atau 0(dalam radian). Dengan demikian mereka dapat dengan mudah dihasilkan sebagai eksponensial imajiner. Untuk itu, urutan bilangan bulat 0,1,2,2,3,3,3,4,4,4,4 ... digunakan terlebih dahulu.

Urutan bilangan bulat ini hampir seperti urutan "n muncul n kali" ( OEIS A002024 ), dan dapat diperoleh di floor(sqrt(2*n)+.5)mana n0,1,2,3, .... Mengalikan dengan 2j*pi/3, di mana junit imajiner, menghasilkan perpindahan kompleks yang diinginkan.

Perpindahan diakumulasikan untuk menghitung posisi yang sesuai dengan bilangan bulat dalam spiral. Angka integer pertama dalam spiral, yaitu 1, secara acak terletak pada posisi 1di bidang kompleks.

Akhirnya, posisi yang berhubungan dengan bilangan non-prima dibuang, dan sisanya diplot pada bidang kompleks.

: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
sumber
Apa Oo saya perlu membaca ini lebih lanjut
Brain Guider
Cobalah secara Online! mendukung output grafis untuk MATL?
Alex A.
Saya pikir TIO tidak mendukung output grafis? Jika ya, saya dapat dengan mudah meminta MATL untuk secara otomatis membuang gambar ke .pngfile yang akan ditampilkan oleh halaman web @AlexA
Luis Mendo
Hei! Saya melakukan tes sederhana ( plot(1:5)) dan menghasilkan output teks-grafis !! matl.tryitonline.net/#code=NTpYRw&input= @AlexA. Bagaimana dengan ini??
Luis Mendo
4
WHOA! Itu luar biasa!
Alex A.
8

Menggambar harus dilakukan dengan

LaTeX / PGF, 527 594 byte

\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 byte adalah dokumen lengkap seperti di atas, yaitu termasuk pembukaan dan parameter (di sini 4000, jadi ~ 523 tanpa parameter). Menghasilkan file PDF.

Ide dasarnya: yah, gambar saja. Menggunakan transformasi matriks untuk kisi segitiga. Satu-satunya masalah adalah bahwa titik-titik juga dipengaruhi (dan direntangkan) oleh transformasi. Jadi saya memilih untuk ellipse spidol :) apa yang saya maksud dengan itu jelas pada gambar kedua (n = 250, 5pt).

Peringatan lain: hanya dapat menangani hingga kurang dari 5000 karena ukuran tumpukan maksimum TeX. Gambar pertama adalah untuk n = 4000. Rupanya mungkin untuk meningkatkan ukuran tumpukan , saya tidak mencobanya.

Menggunakan PGF isprime().

masukkan deskripsi gambar di sini

masukkan deskripsi gambar di sini

Tidak Disatukan:

\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}
Komunitas
sumber
1
Wow. Tidak pernah terpikir oleh saya untuk melakukan ini di LaTeX
Luis Mendo
Menggunakan lualatexatau kompiler pengalokasian dinamis lainnya harus membiarkan Anda memotong ukuran tumpukan, jika saya memahami komentar terkait Anda dengan benar. Jadi itu bukan batasan jawaban Anda, hanya sebagian besar implementasi di mana Anda menjalankannya.
Andras Deak
Maaf, saya sudah memeriksa dan batas ukuran tumpukan input tidak terkait dengan alokasi memori yang saya bahas di komentar saya sebelumnya :(
Andras Deak
@AndrasDeak tidak apa-apa, terima kasih sudah mencarinya. Saya menemukan metode yang tampaknya memang meningkatkan ukuran tumpukan, tetapi tidak mencobanya sendiri (belum).
@CamilStaps terima kasih, saya telah menemukan posting serupa lainnya, tetapi saya tidak mencobanya juga. Bagaimanapun, saya mengambil tulisan Christian Feuersänger sebagai kanon :)
Andras Deak
2

Mathematica, 94 byte

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

Hasil

%[10000]

masukkan deskripsi gambar di sini

njpipeorgan
sumber
2

Python, 263 byte

Menjadi orang baru di Python, pasti ada ruang untuk perbaikan :)

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

Contoh:

f(100000)

masukkan deskripsi gambar di sini

lambruscoAcido
sumber
Anda dapat mempersingkat s=[];X=[];Y=[];i=1;x=0;y=0menjadis=X=Y=[];i=1;x=y=0;
rp.beltran
Abaikan titik koma ekstra di akhir. Seharusnya Anda menghemat 8 byte.
rp.beltran
@ rp.beltran. Ini tidak bekerja. Saya pikir ini terkait dengan fakta bahwa objek memiliki nilai yang sama. Hanya bisa menambahkan x=y=0.
lambruscoAcido
Sayang saya, Anda benar. Saya lupa bahwa Python melewati daftar dengan referensi. Bilangan tidak berubah dan karena itu aman untuk dilakukan dengan bilangan bulat.
rp.beltran
1

R, 137 byte

Hanya menggunakan fungsi bawaan, bahkan untuk bilangan prima. Mengingat pendekatan vektornya alih-alih iteratif, ia cepat, tetapi tidak dapat menangani jumlah yang besar.

Golf:

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])}

Tidak Disatukan:

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
}

Contoh:

g(10000)

masukkan deskripsi gambar di sini

lambruscoAcido
sumber
Bisakah Anda menambahkan contoh hasil?
Luis Mendo
@LuisMendo. Yakin. Saya hanya harus mencari cara untuk menambahkan plot.
lambruscoAcido