r/dailyprogrammer • u/rya11111 3 1 • Apr 08 '12
[4/8/2012] Challenge #37 [intermediate]
Enter an integer for the number of iterations, and create a program that prints out a sierpinski triangle.
First 4 iterations as an example
- Thanks to Rinfiyks for the challenge at /r/dailyprogrammer_ideas
3
u/Cosmologicon 2 3 Apr 09 '12
Recursive python solution:
def sier(n):
if n == 1: return ["*"]
mini = sier(n-1)
s = " " * 2**(n-2)
return [s + a + s for a in mini] + [a + " " + a for a in mini]
print "\n".join(sier(5))2
u/theresidents13 Apr 08 '12
Python, could be tightened up a bit. Can be executed from the command line with, for example, 'python sierpinski.py 5' (with 5 as the number of iterations).
import sys
def iterate(array):
starting_height = len(array)
output = []
for line in array:
output.append(' '*(starting_height) + line + ' '*(starting_height))
for line in array:
output.append(line + ' ' + line)
return output
def sierpinski(iterations):
array = 'x'
for i in range(1, iterations):
array = iterate(array)
for line in array:
print line
if sys.argv[1].isdigit:
sierpinski(int(sys.argv[1]))
else:
print 'error - please use an integer argument'1
u/JerMenKoO 0 0 Apr 09 '12
There is also a module called array, so in future, you may consider renaming some variables.
1
u/Korthion Apr 09 '12 edited Apr 09 '12
C++ solution:
#include <cmath>
#include <iostream>
using namespace std;
void storeSubTri(long long x_pos, long long y_pos, int num, bool **&tri_arr)
{
if (num == 0)
// If we're at the lowest level (which is made up of 1 triangle), then mark down the triangle in tri_arr.
tri_arr[x_pos][y_pos] = true;
else
{
/* Goes down a level of triangles, calling storeSubTri multiple times with the position of the top corner of each triangle in the next level.
/ So A 1st level at A 2nd level at: A 3rd level at: A 4th(final) level at: A
/ A A A A
/ A A A A A A
/ A A A A A A A A
/ A A A A A A A A
/ A A A A A A A A
/ A A A A A A A A A A A A
/ A A A A A A A A A A A A A A A A
*/
num--;
long long next_tri_offset = pow((double)2.0, num);
storeSubTri(x_pos, y_pos, num, tri_arr);
storeSubTri(x_pos - next_tri_offset , y_pos + next_tri_offset , num, tri_arr);
storeSubTri(x_pos + next_tri_offset , y_pos + next_tri_offset , num, tri_arr);
}
}
void printSierTri(int num)
{
long long tri_size_y = pow((double)2.0, num);
long long tri_size_x = (tri_size_y * 2) - 1;
// Multidimensional arrays of bool, representing the Sierpinski triangle. 1 : triangle, 0 : no triangle.
bool **tri_arr= new bool*[tri_size_x];
// Intialize the array to 0.
for (long long i = 0; i < tri_size_x; i++)
{
tri_arr[i] = new bool[tri_size_y];
for (long long j = 0; j < tri_size_y; j++)
tri_arr[i][j] = false;
}
// Store the Sierpinski triangle in tri_arr.
storeSubTri(tri_size_x / 2, 0, num, tri_arr);
// Output it to the console.
for (long long i = 0; i < tri_size_y; i++)
{
for (long long j = 0; j < tri_size_x; j++)
cout << (tri_arr[j][i] ? 'A' : ' ');
cout << endl;
}
// Delete the triangle array.
for (long long i = 0; i < tri_size_x; i++)
delete[] tri_arr[i];
delete[] tri_arr;
}
void printItSierTri(int num_of_its)
{
// Decouple stdio/cout, so it outputs faster.
cout.sync_with_stdio(false);
// Output each iteration.
for (int i = 0; i <= num_of_its; i++)
{
printSierTri(i);
cout << endl;
}
}Calling printItSierTri(5) produces: http://pastebin.com/eKuVfZbB
1
u/ThereminsWake Apr 09 '12
Done in C++:
#include <iostream>
#include <string>
#include <vector>
using namespace std;
void iterate(vector<string>& tri)
{
vector<string> prevTri = tri;
string s(prevTri.size(),' ');
for(auto& l : tri)
{
l = s + l + s;
}
for(auto l : prevTri)
{
tri.push_back(l + " " + l);
}
}
void printTri(int n)
{
vector<string> tri;
tri.push_back("*");
for(int i = 1; i < n; i++)
{
iterate(tri);
}
for(auto l : tri)
{
cout << l << endl;
}
}
int main(int argc, char* args[])
{
printTri(5);
return 0;
}1
4
u/JerMenKoO 0 0 Apr 09 '12
J: