Fractals are just so fascinating. (Click the above image to zoom.)
Below, is the source code of the program used to generate that image*. It uses OpenMP for multithreading and SSE2 SIMD intrinsics for doing parallel mathematics on single core.
On a 4-core CPU, it calculates 8 pixels simultaneously. Language: C++.
I admit that the above source code failed to demonstrate "why".
Why?
Because they're so simple. Here is a version that is rewritten for simplicity and clarity, and all speed optimizations are taken out.
This program outputs an image file in PNM format to stdout.
#include <cmath>
#include <complex>
#include <iostream>
typedef std::complex<double> Value;
/* Define the window of the fractal we want to view. */
static const Value min(-0.370846195, -0.651744395);
static const Value max(-0.369578005, -0.645876205);
/* Define the rendering. */
static const int Width = 512, Height = 384, MaxIter = 1024;
int main()
{
const Value step = (max-min) / Value(Width,Height);
std::cout << "P3\n" << Width << ' ' << Height << "\n100\n";
for(int y=0; y<Height; ++y)
for(int x=0; x<Width; ++x)
{
Value c = min + step*Value(x,y), z = c;
int iter;
for(iter=0; iter<MaxIter; ++iter)
{
if(std::abs(z) >= 2.0) break;
z = z * z + c; /* This is the core of the fractal! */
}
/* The following is just an arbitrary manner of converting the iter value into a colour. */
int Red = 50 + 49 * std::cos(iter/100.0);
int Green = 50 - 49 * std::cos(iter/80.0);
int Blue = 50 - 49 * std::sin(iter/70.0+2);
std::cout << Blue << ' ' << Green << ' ' << Red << '\n';
}
}
The image it produces is:
I call this one the Menorah Fractal. It has got the Mandelbrot set surrounded by four Menorahs.
I actually went ahead and Youtubed the process of writing a Mandelbrot fractal renderer. This one uses the Boundary Tracing Algorithm, which greatly speeds up the rendering process when large regions of same color are present.
http://www.youtube.com/watch?v=rVQMaiz0ydk
P.S. It took about seven hours to produce this video, not counting the time spent designing the program. And I had to redo the recording six times. In the background, it features a couple of AdLib music pieces I created in the 90s.
I created another programming-related Youtube video.
In this video, I create a MOD S3M player from scratch.
Link to video
In order to make it fit in Youtube's 10 minute length limit, I recorded this in the same style we make TASes: by running the emulator slower (in some parts) so I get to type faster. I call this a tool-assisted education video.
I created another programming-related tool-assisted education video.
In this video, I create a tetris clone in GW-BASIC and play three-channel melodies on the special PC speaker of Tandy 1000.
Link to video
Available in HD also for download!
Here's a fun little program that anyone can enjoy!
#include <iostream>
using namespace std;
int main()
{
int day1, day2, day3;
cout << "Hello and welcome to the bar of the future!" << endl;
cout << "Please insert the number of beers you had the day before yesterday: " << endl;
cin >> day1;
cout << "Thank you! Now tell me how many beers you had yesterday: " << endl;
cin >> day2;
cout << "Thank you! Now, please insert the number of beers you have had today: " << endl;
cin >> day3;
cout << "Thank you! You have had an average of " << (day1 + day2 + day3) / 3.0 << " beers per day. You should drink more beer." << endl;
return 0;
}
Written in C++.
EDIT: It also seems I copypasted the wrong text file. Just a sec and I'll update it.
EDIT2: Nach is working on a fix for the code tags, so I'll update this to a form that compiles when he's ready.
EDIT3: Now it should be fixed.
Joined: 3/9/2004
Posts: 4588
Location: In his lab studying psychology to find new ways to torture TASers and forumers
arflech wrote:
the quick fix is to click "Disable HTML in this post"
In fact, it's the only fix.
Warning: Opinions expressed by Nach or others in this post do not necessarily reflect the views, opinions, or position of Nach himself on the matter(s) being discussed therein.
Joined: 3/9/2004
Posts: 4588
Location: In his lab studying psychology to find new ways to torture TASers and forumers
Warp wrote:
Brushy wrote:
cout << "Please insert the number of beers you had the day before yesterday: " <<endl>> day1;
std::cout has no support for operator>>(). Or is this a case of the bbengine botching the code?
It's a case of the HTML engine botching the code. Turn it off!
Warning: Opinions expressed by Nach or others in this post do not necessarily reflect the views, opinions, or position of Nach himself on the matter(s) being discussed therein.
Here is a C++ programming challenge I have been working on lately.
------------------------
There are 13 features. There are thus 213, that is 8192, combinations of these features.
There are 7 classes, each of which implement any number of these features from 1 to 13; there is overlap in these implementations (there may exist more than one class that implements a certain feature). With multiple-inheritance, one can also devise new classes which implement all the ancestors' methods. There are thus 27, that is 128, classes to choose from.
Your task: Write a function, which, given a parameter "bitmask", which is an at least 13-bit integer that denotes the set of features required, returns an instance to the smallest possible class that implements all of the requested features. The class may implement more features, but it must be the smallest implementation to do so. In case of ambiguity, chooses the more fundamental class. You can assume that asking for parameter values outside the range 1..8191 (inclusive) are errors.
Expect the number of features, the number of classes, the size of the classes, and the list of features they each implement to change later. Write your code so that this will not pose a problem.
Design goals: Try to produce optimal code in both speed and size (for example, if possible, no 8192-case switchcases, and no pointers to methods of classes that are never going to be used). And of course, it must be maintainable. As such, no 8192-case hardcoded switchcases.
Example code:
[code c++]enum Feature
{
Feat00 = 0x0001,
Feat01 = 0x0002,
Feat02 = 0x0004,
Feat03 = 0x0008,
Feat04 = 0x0010,
Feat05 = 0x0020,
Feat06 = 0x0040,
Feat07 = 0x0080,
Feat08 = 0x0100,
Feat09 = 0x0200,
Feat10 = 0x0400
};
/* For convenience, here is the base type for all the classes. */
class Base { public: virtual ~Base(); }; /* Base is 0 bytes and implements nothing */
class Class00: public Base
{
char bulk[16];
void DoFeat00();
}; /* Class00 is 16 bytes and implements Feat00 */
class Class01: public Base
{
char bulk[36];
void DoFeat00(); void DoFeat01(); void DoFeat02(); void DoFeat03();
void DoFeat04(); void DoFeat05(); void DoFeat06(); void DoFeat07();
void DoFeat08(); void DoFeat09();
}; /* Class01 is 36 bytes and implements all features EXCEPT Feat10 */
class Class02: public Base
{
char bulk[4];
void DoFeat02();
}; /* Class02 is 4 bytes and implements Feat02 */
class Class03: public Base
{
char bulk[4];
void DoFeat03();
}; /* Class03 is 4 bytes and implements Feat03 */
class Class04: public Base
{
char bulk[8];
void DoFeat04();
}; /* Class04 is 8 bytes and implements Feat04 */
class Class05: public Base
{
char bulk[28];
void DoFeat00(); void DoFeat04(); void DoFeat05(); void DoFeat06(); void DoFeat07();
}; /* Class05 is 28 bytes and implements Feat00, Feat04, Feat05, Feat06 and Feat07 */
class Class06: public Base
{
char bulk[44];
void DoFeat00(); void DoFeat04(); void DoFeat05(); void DoFeat06(); void DoFeat07();
void DoFeat10();
}; /* Class06 is 44 bytes and implements Feat00, Feat04, Feat05, Feat06 and Feat07 AND Feat10 */
/* This is the function that needs an implementation: */
Base* InstantiateSmallestClassWithFeatures(unsigned featureset);[/code]
You are free to add static methods / properties to the classes or even templatize them if required, but do not change their size or their set of features (do not alter the bulk either; it represents the mandatory size). For example, you can add a static const int into each class indicating the set of features implemented.
Examples:
-- When one requests Feat04, gets Class04.
-- When one requests Feat02+Feat04, gets a combination of Class02 and Class04.
-- When one requests Feat04+Feat05, gets Class05.
-- When one requests Feat00+Feat02+Feat03+Feat07, gets Class01 ( the combination of Class05, Class02 and Class03 is the same size, but Class01 is more fundamental ).
------------------------
This programming challenge arised to me in the implementation of animmerger. I solved it. But I think it is an interesting challenge! I would like to see other solutions/attempts.
This programming challenge arised to me in the implementation of animmerger. I solved it. But I think it is an interesting challenge! I would like to see other solutions/attempts.
It seems that nobody was interested about this challenge.
Well, I'll just go ahead and post my solution.
Language: C++
/********************************/
#define DefineFeatures(callback) \
callback(Feat00 , 0x0001) \
callback(Feat01 , 0x0002) \
callback(Feat02 , 0x0004) \
callback(Feat03 , 0x0008) \
callback(Feat04 , 0x0010) \
callback(Feat05 , 0x0020) \
callback(Feat06 , 0x0040) \
callback(Feat07 , 0x0080) \
callback(Feat08 , 0x0100) \
callback(Feat09 , 0x0200) \
callback(Feat10 , 0x0400) \
callback(Feat11 , 0x0800) \
callback(Feat12 , 0x1000)
/* Make an enum out of the feature list */
#define MakeEnum(name, value) name=value,
enum Feature { DefineFeatures(MakeEnum) };
#undef MakeEnum
/* Count the features */
#define SumFeats(name, value) |value
static const unsigned AllFeats = 0 DefineFeatures(SumFeats);
#undef SumFeats
/********************************/
class Base { public: virtual ~Base() {} }; /* Base is 0 bytes and implements nothing */
class Class00
{
char bulk[16];
public:
static const unsigned NumParts = 1, HasFeats = Feat00;
}; /* Class00 is 16 bytes and implements Feat00 */
class Class01
{
char bulk[36];
public:
static const unsigned NumParts = 1, HasFeats = AllFeats &~Feat10;
}; /* Class01 is 36 bytes and implements all features EXCEPT Feat10 */
class Class02
{
char bulk[4];
public:
static const unsigned NumParts = 1, HasFeats = Feat02;
}; /* Class02 is 4 bytes and implements Feat02 */
class Class03
{
char bulk[4];
public:
static const unsigned NumParts = 1, HasFeats = Feat03;
}; /* Class03 is 4 bytes and implements Feat03 */
class Class04
{
char bulk[8];
public:
static const unsigned NumParts = 1, HasFeats = Feat04;
}; /* Class04 is 8 bytes and implements Feat04 */
class Class05
{
char bulk[28];
public:
static const unsigned NumParts = 1, HasFeats = Feat00|Feat04|Feat05|Feat06|Feat07;
}; /* Class05 is 28 bytes and implements Feat00, Feat04, Feat05, Feat06 and Feat07 */
class Class06
{
char bulk[44];
public:
static const unsigned NumParts = 1, HasFeats = Feat00|Feat04|Feat05|Feat06|Feat07|Feat10;
}; /* Class06 is 44 bytes and implements Feat00, Feat04, Feat05, Feat06 and Feat07 AND Feat10 */
/* This is the function that needs an implementation: */
Base* InstantiateSmallestClassWithFeatures(unsigned featureset);
/************************** SOLUTION *************************/
namespace
{
#define DefineClasses(callback) \
callback(Class00) \
callback(Class01) \
callback(Class02) \
callback(Class03) \
callback(Class04) \
callback(Class05) \
callback(Class06)
/* Enumerate the Classes */
#define MakeEnum(name) Class##name,
enum Class { DefineClasses(MakeEnum) };
#undef MakeEnum
/* Count them */
#define CountClasses(name) +1
enum { NClasses = 0 DefineClasses(CountClasses) };
#undef CountClasses
/* Translate Class into a type and information regarding type */
template<unsigned id> struct MetaInfoForClassId { };
template<typename T>
struct MetaInfoForClassType
{
typedef T result;
static const unsigned HasFeats = T::HasFeats;
static const unsigned Cost = sizeof(T);
static const unsigned NumParts = T::NumParts;
};
template<>
struct MetaInfoForClassType<void> /* Fall-back: Non-preferred type information */
{
typedef void result;
static const unsigned HasFeats = 0u;
static const unsigned Cost = 0xffffu;
static const unsigned NumParts = 0xffffu;
};
#define MakeClass(name) \
template<> struct MetaInfoForClassId<Class##name> \
: public MetaInfoForClassType<name> { };
DefineClasses(MakeClass)
#undef MakeClass
/* Utility */
/* Get the index of first 1-bit in the positive integer */
template<unsigned Value, unsigned Basevalue=0, bool found = !Value || (Value&1)>
struct GetLowestBit : public GetLowestBit<Value/2, Basevalue+1> { };
template<unsigned Value, unsigned Basevalue>
struct GetLowestBit<Value, Basevalue, true> { enum { result = Basevalue }; };
/* Choose type 1 or type 2 depending on boolean condition */
template<typename T1, typename T2, bool select1st>
struct ChooseType { typedef T2 result; };
template<typename T1, typename T2>
struct ChooseType<T1,T2,true> { typedef T1 result; };
/* Combine classes into a new class */
template<typename T1,typename T2>
struct And: public T1, public T2
{
static const unsigned HasFeats = T1::HasFeats | T2::HasFeats;
static const unsigned Cost = T1::Cost + T2::Cost;
static const unsigned NumParts = T1::NumParts + T2::NumParts;
};
/* Creates a combination class of classes matching the requested bitmask. */
/* The combination is created through chain-inheritance. */
template<unsigned bitmask=1,
unsigned lowest =GetLowestBit<bitmask>::result,
unsigned remainingbits=bitmask & ~(1u << lowest),
typename lowestInfo =MetaInfoForClassId<lowest> >
struct ClassCombination
/* two classes if remainingbits!=0 */
: public MetaInfoForClassType<And<
typename ClassCombination<remainingbits>::result,
typename lowestInfo::result > >
{
};
template<unsigned bitmask,unsigned lowest,
typename lowestInfo>
struct ClassCombination<bitmask,lowest,0,lowestInfo>
/* one class if remainingbits==0 */
: public lowestInfo
{
};
/* Starting from given bitmask (bm), finds the first
* bitmask whose corresponding ClassCombination produces
* a class that implements at least the given Feats.
*/
template<unsigned ReqFeats,unsigned bm=1>
struct NextClassCombination_WithFeats
{
static const unsigned bitmask =
(ReqFeats & ~ClassCombination<bm>::HasFeats)
? // Escalate
NextClassCombination_WithFeats<ReqFeats, bm+1>::bitmask
: // Found
bm; // bitmask that had matching Feats.
};
template<unsigned ReqFeats>
struct NextClassCombination_WithFeats<ReqFeats, (1u<<NClasses)>
{ // Default case, ensures termination
static const unsigned bitmask = 1u<<NClasses;
};
/* Picks the smallest ClassCombination that fulfills the requested Feats. */
template<unsigned ReqFeats,
typename DType = ClassCombination< (1u<<NClasses)-1 >,
unsigned bitmask = NextClassCombination_WithFeats<ReqFeats>::bitmask
>
struct BestClassCombination_ForFeats
{
typedef ClassCombination<bitmask> CType;
static const bool ChooseC =
((CType::Cost < DType::Cost
|| (CType::Cost == DType::Cost
&& CType::NumParts < DType::NumParts)
));
// Escalate.
typedef typename BestClassCombination_ForFeats<
ReqFeats,
typename ChooseType<CType, DType, ChooseC>::result,
NextClassCombination_WithFeats<ReqFeats, bitmask+1>::bitmask
>::result result;
};
template<unsigned ReqFeats,typename T>
struct BestClassCombination_ForFeats<ReqFeats,T, (1u<<NClasses)>
{
typedef T result;
};
/* BaseAnd makes any chosen implementation to
* have Base as one of the ancestor classes
*/
template<typename T>
class BaseAnd: public Base, public T
{
};
/* Actual framework for constructing stuff */
struct FactoryType
{
Base* (*Constructor)();
unsigned cost;
};
template<typename T>
struct FactoryImpl
{
static Base* Construct() { return new BaseAnd<T>(); }
static const FactoryType data;
};
template<typename T>
const FactoryType FactoryImpl<T>::data =
{ FactoryImpl<T>::Construct, MetaInfoForClassType<T>::Cost };
template<unsigned bitmask=1u>
struct FactoryFinder
{
static inline const FactoryType* FindForFeats
(unsigned req_feats,
unsigned result_cost = 0xffffffu,
const FactoryType* result = 0
)
{
typedef typename BestClassCombination_ForFeats
<ClassCombination<bitmask>::HasFeats>::result imprfinder;
/* Using BestClassCombination_ForFeats here avoids
* having to _instantiate_ all the different types.
* Only those types that end up being returned here, are
* instantiated. If it weren't for this, this duplicate
* functionality would be redundant.
*/
if( ! (req_feats & ~imprfinder::HasFeats))
{
if(imprfinder::Cost < result_cost)
{
result = &FactoryImpl
<typename imprfinder::result>::data;
result_cost = imprfinder::Cost;
}
}
return FactoryFinder<bitmask+1>::
FindForFeats(req_feats, result_cost, result);
}
};
template<>
struct FactoryFinder< (1u<<NClasses) >
{
static inline const FactoryType* FindForFeats
(unsigned,unsigned, const FactoryType* result)
{
return result;
}
};
}
const FactoryType* FindFeatures(unsigned featureset)
{
return FactoryFinder<>::FindForFeats(featureset);
}
Base* InstantiateSmallestClassWithFeatures(unsigned featureset)
{
const FactoryType* fac = FindFeatures(featureset);
return fac->Constructor();
}
/******* TESTING ******/
#include <typeinfo>
#include <iostream>
int main()
{
for(unsigned featureset=1; featureset<= AllFeats; ++featureset)
{
Base* tmp = InstantiateSmallestClassWithFeatures(featureset);
std::cout
<< featureset
<< ": size=" << FindFeatures(featureset)->cost
<< ", impl=" << typeid(*tmp).name()
<< "\n";
delete tmp;
}
}
In retrospect, I think SFINAE could be used to do away with the explicitly coded feature bitmaps in the class declarations...
Maybe I'm missing something obvious, but what exactly is the "problem" here? Simply sort the dimensions of the boxes being compared in descending order, and then see if each dimension in the to-be-inside box is smaller or equal to each corresponding dimension in the container box. "Time limit 3 seconds"? Maximum of 10 dimensions? You could have 10 thousand dimensions and it would still take significantly less than 3 seconds.
Your method for checking if a box nests each other is entirely correct, but you still need to find a way to output the largest nesting sequence. (EDIT: the method is almost correct, it's smaller, not smaller or equal).
And in that problem, the value of n could go as high as 1000, my solution passed with a time of 0.012 sec.
Sort the boxes by their largest dimension. That way you have the order of the longest sequence, you "just" need to find a subset that works.
Instead of checking 2^n subsets for length and validity. try dynamic programming to do it in n^2:
int length[n]; // length of the longest sequence ending on (and including) box number n
int prev[n]; // previous box in said longest sequence, -1 if sequence starts here
for (int i=0;i<n;i++)
{
// initial guess: the sequence containing only this box
length[i] = 1;
prev[i] = -1;
// find a better sequence if one exists
for (int j=0;j<i;j++)
{
if (length[j] + 1 > length[i] && nests(i, j))
{
length[i] = length[j] + 1;
prev[i] = j;
}
}
}
Now find the largest entry in the length array and follow the prev-pointers to get the sequence.
(you might get a speed-up by precalculating nests(i,j) - even though you won't ever need all of these combinations, using transitivity could avoid some nesting checks. I suppose this is only faster when using lots of dimensions.)
@Tub:
I didn't submit your solution, but if I understand correctly, I think it'll receive Wrong Answer.
Try this (the boxes are supposed to be at the sorting method you chose):
If I messed up something, the idea is that knowing the best sequence for k boxes doesn't provide enough information to extend to k+1 boxes.
the secret of dynamic programming is to find a good invariant that can be extended. The "best solution to k boxes" doesn't work, but that's not what I've been doing.
length[ i] contains the best sequence of the boxes 1..i that MUST contain (thus end in) box i!
e.g. length[5] could contain the sequences (5), (1,5) or (1,3,5), but never (1,2,3,4) or (3,5,7) because neither ends with box #5.
Let's try your example, ordered already:
100 50
200 60
300 70
400 10
500 20
600 30
700 40
instead of length / prev, I'll just note the respective sequence.
First box:
only one option
sequence[1] = (1)
Second box:
Either (2) or box 2 appended to a known sequence, which would be (1, 2), which is valid. Keep the longest one.
sequence[2] = (1,2)
Third box:
Either (3), or 3 appended to one of the two already known optimal sequences. The new options are (1, 3) or (1,2,3), both valid, pick the longest.
sequence[3] = (1,2,3)
Fourth box:
Must be (4) because the other combinations are not valid
sequence[4] = (4)
Fifth box:
Either (5) or (4, 5), because (1,5), (1,2,5) and (1,2,3,5) are not valid
sequence[5] = (4,5)
Sixth box:
Either (6) or (4,5) or (4,5,6), because (1,6), (1,2,6) and (1,2,3,6) are not valid
sequence[6] = (4,5,6)
Seventh box:
sequence[7] = (4,5,6,7)
Now we have 7 sequences, each being an optimal solution to a restricted version of the problem. But our globally optimal solution has to end with one of our boxes, so one of our local solutions has to be the global solution. In this case, the longest sequence found is in sequence[7] with length 4: 4,5,6,7
I cannot vouch for the correctness of the pseudo-code above (it's untested), but the general idea does work.
I'm curious, how did you solve it without dynamic programming (or an equal recursion), and what's your upper bound on runtime complexity?
Ah, OK. I didn't understand your idea, it should work. I'll submit it later.
EDIT 2: I got WA, and I know why. The sorting method for the boxes needs to be modified a little. Your method will only work if box i doesn't nest box j for any i>j. To guarantee this, comparing just their largest dimensions won't suffice. If their largest dimension happens to be equal, you must move to the second largest, in case of tying again, to the third and so on.
What I did for this problem was: make a DAG using the nesting relation and finding the longest path in it. It has three phases: one for sorting the dimensional values for each boxes, which takes O(n d log d), making the DAG, which takes O(n^2 d) and finding its longest path (dynamic programming is used here), with O(n^2).
So, the total complexity of the algorithm is O(n d log d + n^2 d), here's the accepted code:
EDIT: The C++ code tag can't handle it very well, http://pastebin.com/bgKgr7MH
So you've actually used the same recursion I've suggested, you just looked at it from a different perspective )
You've implemented it top-down using recursion+memoization, while I implemented it bottom-up. You've also skipped the sorting, thus calling the inner loop n^2 times instead of ~(n^2)/2. But it's basically the same recursion! What I called sequence[i] is exactly your caminho(x), with prev/length being prox/numCaminho!
Your code is indeed O(n^2), which I strongly suspect to be optimal. But there's still plenty of room for minor optimization in your code
- sort the boxes first
- memoization is a good choice when you don't need all values. Since all of them are needed anyway (lines 53f), the bottom-up approach should be easier for the compiler to optimize since it avoids function calls.
- you've precalculated all nestings into a matrix. Since no value is used more than once (but some aren't used at all) and you didn't apply any tricks to speed it up, calculating a nesting when needed should be faster. On line 27, try replacing "if (g[x][i])" with "if (encaixa(i,j))" and remove g[][].
- On that note, you'll test encaixa(i,j) before checking if (caminho(i)>maior). When you remove g[][], the second check should be faster, thus it's better to switch the tests.
- if you've sorted the boxes, it's more efficient to check the highest boxes first. This improves the chances to find the largest sequence early, saving further encaixa() checks. In your code, you'd change the loop in line 27 to "for (int i=x-1; i>0; i--)". (i=x-1, not i=n-1, since the boxes are sorted)
But that's not important unless there are bonus points for speed )
Good catch on your edit2!
So, the total complexity of the algorithm is O(n d log d + n^2 d)
Nitpicking, but "n2 * d" grows asymptotically faster than "n * d * log d", and hence the latter is extraneous in the computational complexity notation, and hence the algorithm is O(n2 * d).
Fractals are just so fascinating. (Click the above image to zoom.)
Below, is the source code of the program used to generate that image*. It uses OpenMP for multithreading and SSE2 SIMD intrinsics for doing parallel mathematics on single core.
On a 4-core CPU, it calculates 8 pixels simultaneously. Language: C++.
I call this one the Menorah Fractal. It has got the Mandelbrot set surrounded by four Menorahs.
