I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

Sierpinski square curve

From Rosetta Code
Task
Sierpinski square curve
You are encouraged to solve this task according to the task description, using any language you may know.


Task

Produce a graphical or ASCII-art representation of a Sierpinski square curve of at least order 3.

C++[edit]

Output is a file in SVG format.

// See https://en.wikipedia.org/wiki/Sierpi%C5%84ski_curve#Representation_as_Lindenmayer_system
#include <cmath>
#include <fstream>
#include <iostream>
#include <string>
 
class sierpinski_square {
public:
void write(std::ostream& out, int size, int length, int order);
private:
static std::string rewrite(const std::string& s);
void line(std::ostream& out);
void execute(std::ostream& out, const std::string& s);
double x_;
double y_;
int angle_;
int length_;
};
 
void sierpinski_square::write(std::ostream& out, int size, int length, int order) {
length_ = length;
x_ = (size - length)/2;
y_ = length;
angle_ = 0;
out << "<svg xmlns='http://www.w3.org/2000/svg' width='"
<< size << "' height='" << size << "'>\n";
out << "<rect width='100%' height='100%' fill='white'/>\n";
out << "<path stroke-width='1' stroke='black' fill='none' d='";
std::string s = "F+XF+F+XF";
for (int i = 0; i < order; ++i)
s = rewrite(s);
execute(out, s);
out << "'/>\n</svg>\n";
}
 
std::string sierpinski_square::rewrite(const std::string& s) {
std::string t;
for (char c : s) {
if (c == 'X')
t += "XF-F+F-XF+F+XF-F+F-X";
else
t += c;
}
return t;
}
 
void sierpinski_square::line(std::ostream& out) {
double theta = (3.14159265359 * angle_)/180.0;
x_ += length_ * std::cos(theta);
y_ += length_ * std::sin(theta);
out << " L" << x_ << ',' << y_;
}
 
void sierpinski_square::execute(std::ostream& out, const std::string& s) {
out << 'M' << x_ << ',' << y_;
for (char c : s) {
switch (c) {
case 'F':
line(out);
break;
case '+':
angle_ = (angle_ + 90) % 360;
break;
case '-':
angle_ = (angle_ - 90) % 360;
break;
}
}
}
 
int main() {
std::ofstream out("sierpinski_square.svg");
if (!out) {
std::cerr << "Cannot open output file\n";
return 1;
}
sierpinski_square s;
s.write(out, 635, 5, 5);
return 0;
}
Output:

See: sierpinski_square.svg (offsite SVG image)

Factor[edit]

Works with: Factor version 0.99 2020-08-14
USING: accessors kernel L-system sequences ui ;
 
: square-curve ( L-system -- L-system )
L-parser-dialect >>commands
[ 90 >>angle ] >>turtle-values
"F+XF+F+XF" >>axiom
{
{ "X" "XF-F+F-XF+F+XF-F+F-X" }
} >>rules ;
 
[
<L-system> square-curve
"Sierpinski square curve" open-window
] with-ui


When using the L-system visualizer, the following controls apply:

Camera controls
Button Command
a zoom in
z zoom out
left arrow turn left
right arrow turn right
up arrow pitch down
down arrow pitch up
q roll left
w roll right
Other controls
Button Command
x iterate L-system

Go[edit]

Library: Go Graphics

The following uses the Lindenmayer system with the appropriate parameters from the Wikipedia article and produces a similar image (apart from the colors, yellow on blue) to the Sidef and zkl entries.

package main
 
import (
"github.com/fogleman/gg"
"github.com/trubitsyn/go-lindenmayer"
"log"
"math"
)
 
const twoPi = 2 * math.Pi
 
var (
width = 770.0
height = 770.0
dc = gg.NewContext(int(width), int(height))
)
 
var cx, cy, h, theta float64
 
func main() {
dc.SetRGB(0, 0, 1) // blue background
dc.Clear()
cx, cy = 10, height/2+5
h = 6
sys := lindenmayer.Lsystem{
Variables: []rune{'X'},
Constants: []rune{'F', '+', '-'},
Axiom: "F+XF+F+XF",
Rules: []lindenmayer.Rule{
{"X", "XF-F+F-XF+F+XF-F+F-X"},
},
Angle: math.Pi / 2, // 90 degrees in radians
}
result := lindenmayer.Iterate(&sys, 5)
operations := map[rune]func(){
'F': func() {
newX, newY := cx+h*math.Sin(theta), cy-h*math.Cos(theta)
dc.LineTo(newX, newY)
cx, cy = newX, newY
},
'+': func() {
theta = math.Mod(theta+sys.Angle, twoPi)
},
'-': func() {
theta = math.Mod(theta-sys.Angle, twoPi)
},
}
if err := lindenmayer.Process(result, operations); err != nil {
log.Fatal(err)
}
// needed to close the square at the extreme left
operations['+']()
operations['F']()
 
// create the image and save it
dc.SetRGB255(255, 255, 0) // yellow curve
dc.SetLineWidth(2)
dc.Stroke()
dc.SavePNG("sierpinski_square_curve.png")
}

Java[edit]

Translation of: C++
import java.io.*;
 
public class SierpinskiSquareCurve {
public static void main(final String[] args) {
try (Writer writer = new BufferedWriter(new FileWriter("sierpinski_square.svg"))) {
SierpinskiSquareCurve s = new SierpinskiSquareCurve(writer);
int size = 635, length = 5;
s.currentAngle = 0;
s.currentX = (size - length)/2;
s.currentY = length;
s.lineLength = length;
s.begin(size);
s.execute(rewrite(5));
s.end();
} catch (final Exception ex) {
ex.printStackTrace();
}
}
 
private SierpinskiSquareCurve(final Writer writer) {
this.writer = writer;
}
 
private void begin(final int size) throws IOException {
write("<svg xmlns='http://www.w3.org/2000/svg' width='%d' height='%d'>\n", size, size);
write("<rect width='100%%' height='100%%' fill='white'/>\n");
write("<path stroke-width='1' stroke='black' fill='none' d='");
}
 
private void end() throws IOException {
write("'/>\n</svg>\n");
}
 
private void execute(final String s) throws IOException {
write("M%g,%g\n", currentX, currentY);
for (int i = 0, n = s.length(); i < n; ++i) {
switch (s.charAt(i)) {
case 'F':
line(lineLength);
break;
case '+':
turn(ANGLE);
break;
case '-':
turn(-ANGLE);
break;
}
}
}
 
private void line(final double length) throws IOException {
final double theta = (Math.PI * currentAngle) / 180.0;
currentX += length * Math.cos(theta);
currentY += length * Math.sin(theta);
write("L%g,%g\n", currentX, currentY);
}
 
private void turn(final int angle) {
currentAngle = (currentAngle + angle) % 360;
}
 
private void write(final String format, final Object... args) throws IOException {
writer.write(String.format(format, args));
}
 
private static String rewrite(final int order) {
String s = AXIOM;
for (int i = 0; i < order; ++i) {
final StringBuilder sb = new StringBuilder();
for (int j = 0, n = s.length(); j < n; ++j) {
final char ch = s.charAt(j);
if (ch == 'X')
sb.append(PRODUCTION);
else
sb.append(ch);
}
s = sb.toString();
}
return s;
}
 
private final Writer writer;
private double lineLength;
private double currentX;
private double currentY;
private int currentAngle;
 
private static final String AXIOM = "F+XF+F+XF";
private static final String PRODUCTION = "XF-F+F-XF+F+XF-F+F-X";
private static final int ANGLE = 90;
}
Output:

See: sierpinski_square.svg (offsite SVG image)

Julia[edit]

using Lindenmayer # https://github.com/cormullion/Lindenmayer.jl
 
scurve = LSystem(Dict("X" => "XF-F+F-XF+F+XF-F+F-X"), "F+XF+F+XF")
 
drawLSystem(scurve,
forward = 3,
turn = 90,
startingy = -400,
iterations = 6,
filename = "sierpinski_square_curve.png",
showpreview = true
)
 

Mathematica/Wolfram Language[edit]

Graphics[SierpinskiCurve[3]]
Output:

Outputs a graphical version of a 3rd order Sierpinski curve.

Nim[edit]

Translation of: C++

We produce a SVG file.

import math
 
type
 
SierpinskiCurve = object
x, y: float
angle: float
length: int
file: File
 
 
proc line(sc: var SierpinskiCurve) =
let theta = degToRad(sc.angle)
sc.x += sc.length.toFloat * cos(theta)
sc.y += sc.length.toFloat * sin(theta)
sc.file.write " L", sc.x, ',', sc.y
 
 
proc execute(sc: var SierpinskiCurve; s: string) =
sc.file.write 'M', sc.x, ',', sc.y
for c in s:
case c
of 'F': sc.line()
of '+': sc.angle = floorMod(sc.angle + 90, 360)
of '-': sc.angle = floorMod(sc.angle - 90, 360)
else: discard
 
 
func rewrite(s: string): string =
for c in s:
if c == 'X':
result.add "XF-F+F-XF+F+XF-F+F-X"
else:
result.add c
 
 
proc write(sc: var SierpinskiCurve; size, length, order: int) =
sc.length = length
sc.x = (size - length) / 2
sc.y = length.toFloat
sc.angle = 0
sc.file.write "<svg xmlns='http://www.w3.org/2000/svg' width='", size, "' height='", size, "'>\n"
sc.file.write "<rect width='100%' height='100%' fill='white'/>\n"
sc.file.write "<path stroke-width='1' stroke='black' fill='none' d='"
var s = "F+XF+F+XF"
for _ in 1..order: s = s.rewrite()
sc.execute(s)
sc.file.write "'/>\n</svg>\n"
 
 
let outfile = open("sierpinski_square.svg", fmWrite)
var sc = SierpinskiCurve(file: outfile)
sc.write(635, 5, 5)
outfile.close()
Output:

Same as C++ output.

Perl[edit]

use strict;
use warnings;
use SVG;
use List::Util qw(max min);
use constant pi => 2 * atan2(1, 0);
 
my $rule = 'XF-F+F-XF+F+XF-F+F-X';
my $S = 'F+F+XF+F+XF';
$S =~ s/X/$rule/g for 1..5;
 
my (@X, @Y);
my ($x, $y) = (0, 0);
my $theta = pi/4;
my $r = 6;
 
for (split //, $S) {
if (/F/) {
push @X, sprintf "%.0f", $x;
push @Y, sprintf "%.0f", $y;
$x += $r * cos($theta);
$y += $r * sin($theta);
}
elsif (/\+/) { $theta += pi/2; }
elsif (/\-/) { $theta -= pi/2; }
}
 
my ($xrng, $yrng) = ( max(@X) - min(@X), max(@Y) - min(@Y));
my ($xt, $yt) = (-min(@X) + 10, -min(@Y) + 10);
 
my $svg = SVG->new(width=>$xrng+20, height=>$yrng+20);
my $points = $svg->get_path(x=>\@X, y=>\@Y, -type=>'polyline');
$svg->rect(width=>"100%", height=>"100%", style=>{'fill'=>'black'});
$svg->polyline(%$points, style=>{'stroke'=>'orange', 'stroke-width'=>1}, transform=>"translate($xt,$yt)");
 
open my $fh, '>', 'sierpinski-square-curve.svg';
print $fh $svg->xmlify(-namespace=>'svg');
close $fh;

See: sierpinski-square-curve.svg (offsite SVG image)

Phix[edit]

constant rule = "XF-F+F-XF+F+XF-F+F-X"
string s = "F+F+XF+F+XF"
for n=1 to 4 do
string next = ""
for i=1 to length(s) do
integer ch = s[i]
next &= iff(ch='X'?rule:ch)
end for
s = next
end for
 
sequence X = {}, Y= {}
atom x=0, y=0, theta=PI/4, r = 6
string svg = ""
for i=1 to length(s) do
integer ch = s[i]
switch ch do
case 'F': X &= x; x += r*cos(theta)
Y &= y; y += r*sin(theta)
case '+': theta += PI/2
case '-': theta -= PI/2
end switch
end for
constant svgfmt = """
<svg xmlns="http://www.w3.org/2000/svg" height="%d" width="%d">
<rect height="100%%" width="100%%" style="fill:black" />
<polyline points="%s" style="stroke: orange; stroke-width: 1" transform="translate(%d,%d)" />
</svg>"""
string points = ""
for i=1 to length(X) do
points &= sprintf("%.2f,%.2f ",{X[i],Y[i]})
end for
integer fn = open("sierpinski_square_curve.svg","w")
atom xt = -min(X)+10,
yt = -min(Y)+10
printf(fn,svgfmt,{max(X)+xt+10,max(Y)+yt+10,points,xt,yt})
close(fn)

Python[edit]

import matplotlib.pyplot as plt
import math
 
 
def nextPoint(x, y, angle):
a = math.pi * angle / 180
x2 = (int)(round(x + (1 * math.cos(a))))
y2 = (int)(round(y + (1 * math.sin(a))))
return x2, y2
 
 
def expand(axiom, rules, level):
for l in range(0, level):
a2 = ""
for c in axiom:
if c in rules:
a2 += rules[c]
else:
a2 += c
axiom = a2
return axiom
 
 
def draw_lsystem(axiom, rules, angle, iterations):
xp = [1]
yp = [1]
direction = 0
for c in expand(axiom, rules, iterations):
if c == "F":
xn, yn = nextPoint(xp[-1], yp[-1], direction)
xp.append(xn)
yp.append(yn)
elif c == "-":
direction = direction - angle
if direction < 0:
direction = 360 + direction
elif c == "+":
direction = (direction + angle) % 360
 
plt.plot(xp, yp)
plt.show()
 
 
if __name__ == '__main__':
# Sierpinski Square L-System Definition
s_axiom = "F+XF+F+XF"
s_rules = {"X": "XF-F+F-XF+F+XF-F+F-X"}
s_angle = 90
 
draw_lsystem(s_axiom, s_rules, s_angle, 3)

Quackery[edit]

  [ $ "turtleduck.qky" loadfile ] now!
 
[ stack ] is switch.arg ( --> [ )
 
[ switch.arg put ] is switch ( x --> )
 
[ switch.arg release ] is otherwise ( --> )
 
[ switch.arg share
 != iff ]else[ done
otherwise ]'[ do ]done[ ] is case ( x --> )
 
[ $ "" swap witheach
[ nested quackery join ] ] is expand ( $ --> $ )
 
[ $ "L" ] is L ( $ --> $ )
 
[ $ "R" ] is R ( $ --> $ )
 
[ $ "F" ] is F ( $ --> $ )
 
[ $ "AFRFLFRAFLFLAFRFLFRA" ] is A ( $ --> $ )
 
$ "FLAFLFLAF"
 
4 times expand
 
turtle
witheach
[ switch
[ char L case [ -1 4 turn ]
char R case [ 1 4 turn ]
char F case [ 5 1 walk ]
otherwise ( ignore ) ] ]
Output:

https://imgur.com/qEfGTBG

Raku[edit]

(formerly Perl 6)

Works with: Rakudo version 2020.02
use SVG;
 
role Lindenmayer {
has %.rules;
method succ {
self.comb.map( { %!rules{$^c} // $c } ).join but Lindenmayer(%!rules)
}
}
 
my $sierpinski = 'X' but Lindenmayer( { X => 'XF-F+F-XF+F+XF-F+F-X' } );
 
$sierpinski++ xx 5;
 
my $dim = 600;
my $scale = 6;
 
my @points = (-80, 298);
 
for $sierpinski.comb {
state ($x, $y) = @points[0,1];
state $d = $scale + 0i;
when 'F' { @points.append: ($x += $d.re).round(1), ($y += $d.im).round(1) }
when /< + - >/ { $d *= "{$_}1i" }
default { }
}
 
my @t = @points.tail(2).clone;
 
my $out = './sierpinski-square-curve-perl6.svg'.IO;
 
$out.spurt: SVG.serialize(
svg => [
:width($dim), :height($dim),
:rect[:width<100%>, :height<100%>, :fill<black>],
:polyline[
:points((@points, map {(@t »+=» $_).clone}, ($scale,0), (0,$scale), (-$scale,0)).join: ','),
:fill<black>, :transform("rotate(45, 300, 300)"), :style<stroke:#61D4FF>,
],
:polyline[
:points(@points.map( -> $x,$y { $x, $dim - $y + 1 }).join: ','),
:fill<black>, :transform("rotate(45, 300, 300)"), :style<stroke:#61D4FF>,
],
],
);

See: Sierpinski-square-curve-perl6.svg (offsite SVG image)

Rust[edit]

Program output is a file in SVG format.

// [dependencies]
// svg = "0.8.0"
 
use svg::node::element::path::Data;
use svg::node::element::Path;
 
struct SierpinskiSquareCurve {
current_x: f64,
current_y: f64,
current_angle: i32,
line_length: f64,
}
 
impl SierpinskiSquareCurve {
fn new(x: f64, y: f64, length: f64, angle: i32) -> SierpinskiSquareCurve {
SierpinskiSquareCurve {
current_x: x,
current_y: y,
current_angle: angle,
line_length: length,
}
}
fn rewrite(order: usize) -> String {
let mut str = String::from("F+XF+F+XF");
for _ in 0..order {
let mut tmp = String::new();
for ch in str.chars() {
match ch {
'X' => tmp.push_str("XF-F+F-XF+F+XF-F+F-X"),
_ => tmp.push(ch),
}
}
str = tmp;
}
str
}
fn execute(&mut self, order: usize) -> Path {
let mut data = Data::new().move_to((self.current_x, self.current_y));
for ch in SierpinskiSquareCurve::rewrite(order).chars() {
match ch {
'F' => data = self.draw_line(data),
'+' => self.turn(90),
'-' => self.turn(-90),
_ => {}
}
}
Path::new()
.set("fill", "none")
.set("stroke", "black")
.set("stroke-width", "1")
.set("d", data)
}
fn draw_line(&mut self, data: Data) -> Data {
let theta = (self.current_angle as f64).to_radians();
self.current_x += self.line_length * theta.cos();
self.current_y += self.line_length * theta.sin();
data.line_to((self.current_x, self.current_y))
}
fn turn(&mut self, angle: i32) {
self.current_angle = (self.current_angle + angle) % 360;
}
fn save(file: &str, size: usize, length: f64, order: usize) -> std::io::Result<()> {
use svg::node::element::Rectangle;
let x = (size as f64 - length) / 2.0;
let y = length;
let rect = Rectangle::new()
.set("width", "100%")
.set("height", "100%")
.set("fill", "white");
let mut s = SierpinskiSquareCurve::new(x, y, length, 0);
let document = svg::Document::new()
.set("width", size)
.set("height", size)
.add(rect)
.add(s.execute(order));
svg::save(file, &document)
}
}
 
fn main() {
SierpinskiSquareCurve::save("sierpinski_square_curve.svg", 635, 5.0, 5).unwrap();
}
Output:

See: sierpinski_square_curve.svg (offsite SVG image)

Sidef[edit]

Uses the LSystem() class from Hilbert curve.

var rules = Hash(
x => 'xF-F+F-xF+F+xF-F+F-x',
)
 
var lsys = LSystem(
width: 510,
height: 510,
 
xoff: -505,
yoff: -254,
 
len: 4,
angle: 90,
color: 'dark green',
)
 
lsys.execute('F+xF+F+xF', 5, "sierpiński_square_curve.png", rules)

Output image: Sierpiński square curve

Wren[edit]

Translation of: Go
Library: DOME
Library: Wren-lsystem
import "graphics" for Canvas, Color
import "dome" for Window
import "math" for Math
import "./lsystem" for LSystem, Rule
 
var TwoPi = Num.pi * 2
 
class SierpinskiSquareCurve {
construct new(width, height, back, fore) {
Window.title = "Sierpinski Square Curve"
Window.resize(width, height)
Canvas.resize(width, height)
_w = width
_h = height
_bc = back
_fc = fore
}
 
init() {
Canvas.cls(_bc)
var cx = 10
var cy = (_h/2).floor + 5
var theta = 0
var h = 6
var lsys = LSystem.new(
["X"], // variables
["F", "+", "-"], // constants
"F+XF+F+XF", // axiom
[Rule.new("X", "XF-F+F-XF+F+XF-F+F-X")], // rules
Num.pi / 2 // angle (90 degrees in radians)
)
var result = lsys.iterate(5)
var operations = {
"F": Fn.new {
var newX = cx + h*Math.sin(theta)
var newY = cy - h*Math.cos(theta)
Canvas.line(cx, cy, newX, newY, _fc, 2)
cx = newX
cy = newY
},
"+": Fn.new {
theta = (theta + lsys.angle) % TwoPi
},
"-": Fn.new {
theta = (theta - lsys.angle) % TwoPi
}
}
LSystem.execute(result, operations)
}
 
update() {}
 
draw(alpha) {}
}
 
var Game = SierpinskiSquareCurve.new(770, 770, Color.blue, Color.yellow)

zkl[edit]

Uses Image Magick and the PPM class from http://rosettacode.org/wiki/Bitmap/Bresenham%27s_line_algorithm#zkl

sierpinskiSquareCurve(4) : turtle(_);
 
fcn sierpinskiSquareCurve(n){ // Lindenmayer system --> Data of As
var [const] A="AF-F+F-AF+F+AF-F+F-A", B=""; // Production rules
var [const] Axiom="F+AF+F+AF";
buf1,buf2 := Data(Void,Axiom).howza(3), Data().howza(3); // characters
do(n){
buf1.pump(buf2.clear(),fcn(c){ if(c=="A") A else if(c=="B") B else c });
t:=buf1; buf1=buf2; buf2=t; // swap buffers
}
buf1 // n=4 --> 3,239 characters
}
 
fcn turtle(curve){ // a "square" turtle, directions are +-90*
const D=10;
ds,dir := T( T(D,0), T(0,-D), T(-D,0), T(0,D) ), 2; // turtle offsets
dx,dy := ds[dir];
img,color := PPM(650,650), 0x00ff00; // green on black
x,y := img.w/2, 10;
curve.replace("A","").replace("B",""); // A & B are no-op during drawing
foreach c in (curve){
switch(c){
case("F"){ img.line(x,y, (x+=dx),(y+=dy), color) } // draw forward
case("+"){ dir=(dir+1)%4; dx,dy = ds[dir] } // turn right 90*
case("-"){ dir=(dir-1)%4; dx,dy = ds[dir] } // turn left 90*
}
}
img.writeJPGFile("sierpinskiSquareCurve.zkl.jpg");
}
Output:

Offsite image at Sierpinski square curve of order 4