text:
• 13
• 18
• 19
• 27
• 10

How to design a framework?

This topic is 2517 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

I'm working with C++ and the SFML library.
I made basic games but VERY unorganized, pretty much all in the one header file. No OOP, no classes, well, very few.

I wanted to make a "game engine" or something similar, just a framework. Well organized, not sure how to go about doing it, this is the problem i ran into.

 int main() { myGameEngine myGame; while(1) { myGame.MasterLoop(); } }
I would have code like this, and the "masterloop()" would be located elsewhere obviously. Let's say I wanted to have an "entity" class that controls monsters/items/etc. How would I store these "ents" and there data, so that the "myGameEngine" class can reach them? (assuming there in a differnt class). Example:

 class Entity { public: void GetEntityType() private: sf::Sprite EntSprite; };

I understand I can have the "gameengine" class inherit the class, but this doesn't seem "organized". I'm sorry if im to vague. Nothing feels right,
What's the best way to break up parts of a game (2D - SFML)?
Thanks!

Share on other sites
First of all I would like to say hello, it's my first post .
Now for the framework. You could implement the MasterLoop inside the MyGameEngine class, and store classes like entites in some kind of data structure (ie. List). My approach would be very XNA like - The MyGameEngine could have a method called Update witch would be bassicaly a MasterLoop and calls to Update methods for the entities. This Update methods would handle the game/entites logic. As for Drawing it could be pretty much the same, the main class calls Draw methods from all entities it has. That way in the main function you have something like: myGame.Update() and it handles all the basic nessesary stuff. So the entity class should have some basic fields, like a model/sprite. Then you could create ie. a monster class witch would inherit from entity and implement it's logic (AI, collisions etc.).
As for the data structure a good approach is a scene graph (http://en.wikipedia.org/wiki/Scene_graph) that by its construction gives you quite nice order and logic.

I hope this helps a little, sorry for my English btw

Share on other sites
Hi.

While I am not a big fan of XNA, I do however like their "GameComponent" and "GameService" approach alot. Might I suggest you look into this? I am not sure if you're familiar with C#. If so, you could download Reflector (which enables you to disassemble managed code, and step into its sourcecode). The game/component/service architecture in XNA could be an excellent starting point for you.

One way to look at it (certainly not the only way....):

An example could be a manager that manages monsters. Make it a class. With several methods like: Initialize(), Uninitialize(), Update(), Draw(). Those update an draw methods get called by the game every single frame. The manager then starts updating and drawing all monsters that it is managing. Monster would be a class. The manager would hold a list of Monster-objects. You see how the game doesn't necesarrily have to know about monsters? The game just "provides" something for the monsters to be able to exist. You will need to think of what your game needs to provide. Make managers for most stuff. Feed those managers stuff to manage.

Then, looking at another side. Your framework could define a basic class for Monster. You could subclass that for example: FlyingMonster, SwimmingMonster, etc. Within each subclass you would handle the specific movement rules for that subclass. Your manager doesn't really need to know how to move the monsters. They know it themselves. The manager might just tell them that they can move from there to there but no further than that. It gives them some rules. Instead of subclassing all your game objects, like monsters, bullets, I could advise you too look into object composition, instead of object subclassing. This could be a vital design decision in your framework.

One of the dangers of writing a framework is that often you might find yourself wanting too much. What purpose does this framework fulfull? Keep asking yourself this. Is this a framework for just this game, or would you like to make more games with it? Would it serve as a general framework, allowing for alot of things you dont always use, or does it just, and only just that, provide what this one game requires? Usually one speaks of a framework when you intend to deliver a flexibile component structure. When you're talking of just getting your game object oriented, you're not necesarilly speaking of a framework, merely an OO-paradigm.

Share on other sites
Thanks for the information. I've tried alittle more using the ideas above. But getting to the techincal side of it. I have this for example:

 #ifndef _INCLUDE_ENGINE_H #define _INCLUDE_ENGINE_H #include "INIReader.h" #include "AudioManager.h" namespace NNEngine { class CNNGameEngine { public: CNNGameEngine( void ); ~CNNGameEngine( void ); void Load( void ); void Unload( void ); void RunLoop( void ); // Interfaces AudioManager *audioManager; private: }; } #endif

I'd have quite a few "interfaces" that are loaded onto the heap in the "load()" and deleted on the "unload()". I would use this class like so:

 #include "../Engine/includes/Engine.h" #include <iostream> int main() { std::cout << "Trying to add a sound file...\n"; NNEngine::CNNGameEngine MyTestGame; MyTestGame.audioManager->AddSoundEffectToList( "derp","derp.wav" ); std::cout << "Added derp.wav labeled as derp to the precache/ram\n"; system( "pause" ); return 0; }

Does this seem like a probable way of doing this?

Share on other sites
Hidden
To me, an engine is a collection of classes that work together. The way you have it there, your Engine is the main class, which contains links to all your other classes (through interfaces).

Personally, I would probably have NNEngine as a namespace that all these classes belong to.

Then in your Game/Logic/Controller class you have a way to register an AudioManager class.

That way you end up with something like

 #include "some/path/to/engine/include.h" using namespace NNEngine; int main() { CNNGameEngine MyTestGame; AudioManager MyAudioManager; MyTestGame.LoadAudioManager(&MyAudioManager); MyAudioManager.LoadSoundEffect("blah", "path.wav"); MyAudioManager.Play("blah); }

Obviously not a full example, but this is how I tend to do things in my engine (passing pointers around for classes for interaction).


text:
## RS Aggarwal Class 10 Solutions Chapter 3 Linear equations in two variables Ex 3A

These Solutions are part of RS Aggarwal Solutions Class 10. Here we have given RS Aggarwal Solutions Class 10 Chapter 3 Linear equations in two variables Ex 3A.

### RS Aggarwal Solutions Class 10 Chapter 3

Solve each of the following systems of equations graphically.
Question 1.
Solution:
2x + 3y = 2 …..(i)
x – 2y = 8 …(ii)
From Eq. (i),
⇒ 2x = 2 – 3y
⇒x = $$\frac { 2 – 3y }{ 2 }$$
Giving some different values to y, we get corresponding values of x as given below:

Now, plot the points (1, 0), (-2, 2) and (4, -2) on the graph and join them to get a line.
Similarly x – 2y = 8 ⇒ x = 8 + 2y

Now plot the points (6, -1), (4, -2) and (2, -3) on the graph and join them to get another line.
We see that these two lines intersect each other at point(4, -2).
x = 4, y = -2

Question 2.
Solution:
3x + 2y = 4
⇒ 3x = 4 – 2y
⇒ x = $$\frac { 4 – 2y }{ 3 }$$
Giving some different values to y, we get corresponding values of x as given below:

Now plot the points (0, 2), (2, -1) and (4, -4) on the graph and join them to get a line. Similarly,
2x – 3y = 7
2x = 3y+ 7
x = $$\frac { 3y+ 7 }{ 2 }$$

Now plot the points on the graph and join them to get another line.
We see that these two lines intersect each other at point (2, -1).
x = 2, y = -1

Question 3.
Solution:
2x + 3y = 8
⇒ 2x = 8 – 3y
x = $$\frac { 8 – 3y }{ 2 }$$
Now, giving some different values to y, we get corresponding values of x as given below

Now, we plot the points (4,0), (2,3) and (0, 6) on the graph and join them to get a line.
Similarly,
x – 2y + 3 = 0
x = 2y – 3

Now, plot the points (-3, 0), (-1, 1) and (1, 2) on the graph and join them to get another line.
We see that these two lines intersect each other at the point (1, 2).
x = 1, y = 2

Question 4.
Solution:
2x – 5y + 4 = 0
⇒ 2x = 5y – 4
x = $$\frac { 5y – 4 }{ 2 }$$
Giving some different values to y, we get corresponding values of x as given below:

Now, plot the points (-2, 0) (3, 2) and (8,4) on the graph and join them to get a line.
Similarly,
2x + y – 8 = 0
⇒ y = 8 – 2x

Plot the points (1, 6), (2, 1) and (3, 2) on the graph and join them to get another line.
We see that these two lines intersect each other at the point (3, 2).
x = 3, y = 2

Question 5.
Solution:
3x + 2y = 12
⇒ 3x = 12 – 2y
x = $$\frac { 12 – 2y }{ 2 }$$
Giving some different values to y, we get corresponding the values of x as given below:

Now, we plot the points (4,0), (2,3) and (0, 6) on the graph and join them to get a line.
Similarly,
5x – 2y = 4
⇒ 5x = 4 + 2 y
⇒ x = $$\frac { 4 + 2 y }{ 5 }$$

Plot the points (0, -2), (2, 3) and (4, 8) on the graph and join them to get another line.
We see that these two lines intersect each other at the point (2, 3).
x = 2, y = 3

Question 6.
Solution:
3x + y + 1 = 0 ⇒y = -3x – 1
Giving some different values to x, we get corresponding values of y as given below:

Now, plot the points (0, -1), (-1, 2) and (-2, 5) on the graph and join them to get a line.
Similarly,
2x – 3y + 8 = 0
2x = 3y – 8
x = $$\frac { 3y – 8 }{ 2 }$$

Now, plot the points (-4, 0), (-1, 2) and (2, 4) on the graph and join them to get another line.
We see that these two lines intersect each other at the points (-1, 2).
x = -1, y = 2

Question 7.
Solution:
2x + 3y + 5 = 0
2x = -3y – 5
x = $$\frac { -3y – 5 }{ 2 }$$
Giving some different values to y, we get corresponding values of x as given below:

Now, plot the points (-4, 1), (-1, -1) and (2, -3) on the graph and join them to get a line. Similarly,
3x – 2y – 12 = 0
⇒ 3x = 2y + 12
x = $$\frac { 2y + 12 }{ 3 }$$

Plot the points (4, 0), (0, -6) and (2, -3) on the graph and join them to get another line.
We see that these two lines intersect each other at the point (2, -3).
x = 2, y = -3

Question 8.
Solution:
2x – 3y + 13 = 0
⇒ 2x = 3y – 13
⇒ x = $$\frac { 3y – 13 }{ 2 }$$
Giving some different values to y, we get corresponding values of x as given below:

Now, plot the points (-5, 1), (-2, 3) and (1, 5) on the graph and join them to get a line.
Similarly,
3x – 2y + 12 = 0
3x = 2y – 12
x = $$\frac { 2y – 12 }{ 3 }$$

Now, plot the points (-4, 0), (-2, 3) and (0, 6) on the graph and join them to get another line.
We see that these lines intersect each other at the point (-2, 3).
x = -2, y = 3

Question 9.
Solution:
2x + 3y – 4 = 0
⇒ 2x = 4 – 3y
⇒ x = $$\frac { 4 – 3y }{ 2 }$$
Giving some different values to y, we get corresponding values of x as given below:

Plot the points (2, 0) (-1, 2) and (5, -2) on the graph and join them to get a line.
Similarly,
3x – y + 5 = 0
⇒ -y = -5 – 3x
⇒ y = 5 + 3x

Plot the points (0, 5), (-1, 2) and (-2, -1) on the graph and join them to get another line.
We see that these two lines intersect each other at the point (-1, 2).
x = -1, y = 2

Question 10.
Solution:
x + 2y + 2 = 0
⇒ x = – (2y + 2)
Giving some different values to y, we get corresponding the values of x as given below:

Plot the points (-2,0), (0, -1) and (2, -2) on the graph and join them to get a line.
Similarly,
3x + 2y – 2 = 0
⇒ 3x = 2 – 2y
x = $$\frac { 2 – 2y }{ 3 }$$

Plot the points (0, 1), (2, -2) and (-2, 4) on the graph and join them to get another line.
We see that these two lines intersect each other at the point (2, -2).
x = 2, y = -2

Solve each of the following given systems of equations graphically and find the vertices and area of the triangle formed by these lines and the x-axis:
Question 11.
Solution:
x – y + 3 = 0
⇒ x = y – 3
Giving some different value to y, we get corresponding values of x as given below:

Plot the points (-3, 0), (-1, 2) and (0, 3) on the graph and join them to get a line.
Similarly,
2x + 3y – 4 = 0
⇒ 2x = 4 – 3y
x = $$\frac { 4 – 3y }{ 2 }$$

Plot the points (2, 0), (-1, 2) and (5, -2) on the graph and join them to get another line.
We see that these line intersect each other at (-1, 2) and x-axis at A (-3, 0) and D (2, 0).

Area of ∆BAD = $$\frac { 1 }{ 2 }$$ x base x altitude
= $$\frac { 1 }{ 2 }$$ x AD x BL
= $$\frac { 1 }{ 2 }$$ x 5 x 2 = 5 sq.units

Question 12.
Solution:
2x – 3y + 4 = 0
⇒ 2x = 3y – 4
x = $$\frac { 3y – 4 }{ 2 }$$
Giving some different values to y, we get corresponding value of x as given below:

Plot the points (-2, 0), (1, 2) and (4, 4) on the graph and join them to get a line.
Similarly,
x + 2y – 5 = 0
x = 5 – 2y

Now, plot the points (5, 0), (3, 1) and (1, 2) on the graph and join them to get another line.
We see that there two lines intersect each other at the point B (1, 2) and intersect x- axis at A (-2, 0) and D (5, 0) respectively.

Now, area of ∆BAD = $$\frac { 1 }{ 2 }$$ x base x altitude
= $$\frac { 1 }{ 2 }$$ x AD x BL
= $$\frac { 1 }{ 2 }$$ x 7 x 2
= 7 sq. units

Question 13.
Solution:
4x – 3y + 4 = 0
⇒ 4x = 3y – 4
x = $$\frac { 3y – 4 }{ 4 }$$
Giving some different values to y, we get corresponding value of x as given below:

Plot the points (-1, 0), (2, 4) and (-4, -4) on the graph and join them, to get a line.
Similarly,
4x + 3y – 20 = 0
4x = 20 – 3y
x = $$\frac { 20 – 3y }{ 4 }$$

Plot the points (5, 0), (2, 4) and (-1, 8) on the graph and join them to get a line.

We see that these two lines intersect each other at the point B (2, 4) and intersect x-axis at A (-1, 0) and D (5, 0).
Area ∆BAD = $$\frac { 1 }{ 2 }$$ x base x altitude
= $$\frac { 1 }{ 2 }$$ x AD x BL
= $$\frac { 1 }{ 2 }$$ x 6 x 4 = 12 sq. units

Question 14.
Solution:
x – y + 1 = 0 ⇒ x = y – 1
Giving some different values toy, we get the values of x as given below:

Plot the points (-1, 0), (0, 1) and (1, 2) on the graph and join them to get a line.
Similarly,
3x + 2y – 12 = 0
⇒ 3x = 12 – 2y
x = $$\frac { 12 – 2y }{ 3 }$$

Plot the points (4, 0), (2, 3) and (0, 6) on the graph and join them to get another line.

We see that these two lines intersect each ohter at the point E (2, 3) and intersect x- axis at A (-1, 0) and D (4, 0).
Area of ∆EAD = $$\frac { 1 }{ 2 }$$ x base x altitude 1
= $$\frac { 1 }{ 2 }$$ x AD x EL
= $$\frac { 1 }{ 2 }$$ x 5 x 3
= $$\frac { 15 }{ 2 }$$
= 7.5 sq. units

Question 15.
Solution:
x – 2y + 2 = 0 ⇒ x = 2y – 2
Giving some different values to y, we get corresponding values of x as given below:

Plot the points (-2, 0), (0, 1), (2, 2) on the graph and join them to get a line.
Similarly,
2x + y – 6 = 0
⇒ y = 6 – 2x

Plot the points on the graph and join them to get a line.

We see that these two lines intersect each other at the point C (2, 2) and intersect the x-axis at A (-2, 0) and F (3, 0).
Now, area of ∆CAF = $$\frac { 1 }{ 2 }$$ x base x altitude
= $$\frac { 1 }{ 2 }$$ x AF x CL
= $$\frac { 1 }{ 2 }$$ x 5 x 2 = 5 sq. units

Solve each of the following given systems of equations graphically and find the vertices and area of the triangle formed by these lines and the y-axis:
Question 16.
Solution:
2x – 3y + 6 = 0
⇒ 2x = 3y – 6
x = $$\frac { 3y – 6 }{ 2 }$$
Giving some different values to y, we get corresponding values of x, as given below:

Now, plot the points (-3, 0), (0, 2), (3, 4) on the graph and join them to get a line.
Similarly,
2x + 3y – 18 = 0
2x = 18 – 3y
x = $$\frac { 18 – 3y }{ 2 }$$

Plot the points (0, 6), (3, 4) and (6, 2) on the graph and join them to get a line.
We see that these two lines intersect each other at C (3, 4) and intersect y-axis at B (0, 2) and D (0, 6).

Now, area of ∆CBD = $$\frac { 1 }{ 2 }$$ x base x altitude
= $$\frac { 1 }{ 2 }$$ x BD x CL
= $$\frac { 1 }{ 2 }$$ x 4 x 3 sq. units = 6 sq. units

Question 17.
Solution:
4x – y – 4 = 0
⇒ 4x = y + 4
x = $$\frac { y + 4 }{ 2 }$$
Giving some different values to y, we get corresponding values of x as given below:

Plot the points (1, 0), (0, -4) and (2, 4) on the graph and join them to get a line.
Similarly,
3x + 2y – 14 = 0
2y = 14 – 3x
y = $$\frac { 14 – 3x }{ 2 }$$

Now, plot the points (0, 7), (2, 4) and (4, 1) on the graph and join them to get another line.
We see that these two lines intersect each other at C (2, 4) and y-axis at B (0, -4) and D (0, 7) respectively.

Area of ∆CBD = $$\frac { 1 }{ 2 }$$ x base x altitude
= $$\frac { 1 }{ 2 }$$ x BD x CL
= $$\frac { 1 }{ 2 }$$ x 11 x 2 sq. units = 11 sq. units

Question 18.
Solution:
x – y – 5 = 0 ⇒ x = y + 5
Giving some different values to y, we get corresponding values of x as given below:

Plot the points (5, 0), (0, -5) and (1, -4) on the graph and join these to get a line.
Similarly,
3x + 5y – 15 = 0
3x = 15 – 5y
x = $$\frac { 15 – 5y }{ 3 }$$

Plot the points (5, 0), (0, 3) and (-5, 6) on the graph and join them to get a line.
We see that these two lines intersect each other at A (5, 0) and y-axis at B (0, -5) and E (0, 3) respectively.

Now area of ∆ABE = $$\frac { 1 }{ 2 }$$ x base x altitude
= $$\frac { 1 }{ 2 }$$ x BE x AL
= $$\frac { 1 }{ 2 }$$ x 8 x 5 sq. units = 20 sq. units

Question 19.
Solution:
2x – 5y + 4 = 0
⇒ 2x = 5y – 4
x = $$\frac { 5y – 4 }{ 2 }$$
Giving some different values to y, we get corresponding values of x as given below:

Plot the points (-2, 0), (3, 2) and (-7, -2) on the graph and join them to get a line.
Similarly,
2x + y – 8 = 0
2x = 8 – y
x = $$\frac { 8 – y }{ 2 }$$

Plot the points (4, 0), (3, 2) and (2, 4) on the graph and join them to get a line.
We see that these two lines intersect each other at B (3, 2) and y-axis at G (0, 1) and H (0, 8) respectively.

Now area of ∆EGH = $$\frac { 1 }{ 2 }$$ x base x altitude
= $$\frac { 1 }{ 2 }$$ x GH x EL
= $$\frac { 1 }{ 2 }$$ x 7 x 3 sq. units
= $$\frac { 21 }{ 2 }$$ = 10.5 sq. units

Question 20.
Solution:
5x – y – 7 = 0 ⇒ y = 5x – 7
Giving some different values to x, we get corresponding values of y as given below:

Plot the points (0, -7), (1, -2), (2, 3) on the graph and join them to get a line.
Similarly,
x – y + 1 = 0 ⇒ x = y – 1

Plot the points (-1, 0), (1, 2) and (2, 3) on the graph and join them to get a line.

We see that these two lines intersect each other at C (2, 3) and intersect y-axis at A (0, -7) and F (0, 1) respectively.
Now, area of ∆CAF = $$\frac { 1 }{ 2 }$$ x base x altitude
= $$\frac { 1 }{ 2 }$$ x AF x CL
= $$\frac { 1 }{ 2 }$$ x 8 x 2 = 8 sq.units

Question 21.
Solution:
2x – 3y – 12 ⇒ 2x = 12 + 3y
x = $$\frac { 12 + 3y }{ 2 }$$
Giving some different values to y, we get corresponding values of x as given below:

Plot the points (6, 0), (3, -2) and (0, -4) on the graph and join them to get a line.
Similarly,
x + 3y = 6 ⇒ x = 6 – 3y

Plot the points (6, 0), (0, 2) and (-6, 4) on the graph and join them to get a line.
We see that these two lines intersect each other at the points A (6, 0) and intersect the y-axis at C (0, -4) and E (0, 2) respectively.

Now area of ∆ACE = $$\frac { 1 }{ 2 }$$ x base x altitude
= $$\frac { 1 }{ 2 }$$ x CE x AO
= $$\frac { 1 }{ 2 }$$ x 6 x 6 sq. units = 18 sq.units

Show graphically that each of the following given systems of equations has infinitely many solutions:
Question 22.
Solution:
2x + 3y = 6
2x = 6 – 3y
x = $$\frac { 6 – 3y }{ 2 }$$
Giving some different values to y, we get the corresponding val ues of x as given below:

Plot the points (3, 0), (0, 2) and (-3, 4) on the graph and join them to get a line.
Similarly,
4x + 6y = 12
4x = 12 – 6y
x = $$\frac { 12 – 6y }{ 2 }$$

on the graph and join them to get a line.
We see that all the points lie on the same straight line.
This system has infinite many solutions.

Question 23.
Solution:
3x – y = 5
⇒ y = 3x – 5
Giving some different values to x, we get corresponding values of y as shown below:

Now, plot the points (0, -5), (1, -2), (2, 1) on the graph and join them to get a line:
Similarly,
6x – 2y = 10
⇒ 6x = 10 + 2y
x = $$\frac { 10 + 2y }{ 6 }$$

Plot the points (2, 1), (4, 7), (3, 4) on the graph and join them to get another line.
We see that these lines coincide each other.
This system has infinite many solutions.

Question 24.
Solution:
2x + y = 6
y = 6 – 2x
Giving some different values to x, we get corresponding values of y as given below:

Plot the points (0, 6), (2, 2), (4, -2) on the graph and join them to get a line.
Similarly,
6x + 3y = 18
⇒ 6x = 18 – 3y
⇒ x = $$\frac { 18 – 3y }{ 2 }$$

Now, plot the points (3, 0), (1, 4) and (5, -4) on the graph and join them to get another line.
We see that these two lines coincide each other.
This system has infinitely many solutions

Question 25.
Solution:
x – 2y = 5 ⇒ x = 5 + 2y
Giving some different values to y, we get corresponding values of x as shown below:

Plot the points (5, 0), (3, -1), (1, -2) on the graph and join them to get a line.
similarly,
3x – 6y = 15
⇒ 3x = 15 + 6y
x = $$\frac { 15 + 6y }{ 3 }$$

Plot the points (7, 1), (-1, -3) and (-3, -4) on the graph and join them to get another line.
We see that all the points lie on the same line.
Lines coincide each other.
Hence, the system has infinite many solutions.

Show graphically that each of the following given systems of equations is inconsistent, i.e., has no solution:
Question 26.
Solution:
x – 2y = 6 ⇒ x = 6 + 2y
Giving some different values to y, we get corresponding values of x as given below:

Plot the points (6, 0), (4, -1) and (0, -3) on the graph and join them to get a line.
Similarly,
3x – 6y = 0
⇒ 3x = 6y
⇒ x = 2y

Plot the points (0, 0), (2, 1), (4, 2) on the graph and join them to get a line.

We see that these two lines are parallel i.e., do not intersect each other.
This system has no solution.

Question 27.
Solution:
2x + 3y = 4
⇒ 2x = 4 – 3y
⇒ x = $$\frac { 4 – 3y }{ 2 }$$
Giving some different values to y, we get corresponding values of x as given below:

Plot the points (2, 0), (-1, 2) and (5, -2) on the graph and join them to get a line.
Similarly,
4x + 6y = 12 ⇒ 4x = 12 – 6y
x = $$\frac { 12 – 6y }{ 4 }$$

Plot the points (3, 0), (0, 2) and (-3, 4) on the graph and join them to get another line.
We see that two lines are parallel i.e., these do not intersect each other at any point.
Therefore the system has no solution.

Question 28.
Solution:
2x + y = 6, y = 6 – 2x
Giving some different values to x, we get corresponding values ofy as given below:

Plot the points (0, 6), (1, 4) and (3, 0) on the graph and join them to get a line.
Similarly,
6x + 3y = 20 ⇒ 6x = 20 – 3y

We see that these two lines are parallel and do not intersect each other.
Therefore this system has no solution.

Question 29.
Solution:
2x + y = 2 ⇒ y = 2 – 2x
Giving some different values to x, we get corresponding values of y as given below:

Plot the points (0, 2), (1, 0) and (-2, 6) on the graph and join them to get a line.
Similarly,
2x + y = 6 ⇒ y = 6 – 2x

Plot the points (0, 6), (2, 2) and (3, 0) on the graph and join them to get another line.
ABFD is the trapezium whose vertices are A (0, 2), B (1, 0), F (3, 0), D (0, 6).

Area of trapezium ABFD = Area ∆DOF – Area ∆AOB
= $$\frac { 1 }{ 2 }$$ (DO x OF) – $$\frac { 1 }{ 2 }$$ (AO x OB)
= $$\frac { 1 }{ 2 }$$ (6 x 3) – $$\frac { 1 }{ 2 }$$ (2 x 1) sq.units
= 9 – 1 = 8 sq.units

Hope given RS Aggarwal Solutions Class 10 Chapter 3 Linear equations in two variables Ex 3A are helpful to complete your math homework.

If you have any doubts, please comment below. Learn Insta try to provide online math tutoring for you.

format: plain


text:
# Developing PETSc Documentation#

## General Guidelines#

• Good documentation should be like a bonsai tree: alive, on display, frequently tended, and as small as possible (adapted from these best practices).

• Wrong, irrelevant, or confusing documentation is worse than no documentation.

## Documentation with Sphinx#

We use Sphinx to build our web page and documentation. Most content is written using reStructuredText, a simple markup language.

These slides contain an overview of Sphinx and how we use(d) it, as of October, 2020.

### Building the HTML docs locally#

Note

The documentation build with Sphinx involves configuring a minimal build of PETSc and building some of the classic docs, which requires local working flex, gcc, and g++ before you follow the instructions below.

We suggest using a Python 3 virtual environment 1.

$cd$PETSC_DIR
$python3 -m venv petsc-doc-env$ . petsc-doc-env/bin/activate
$python3 -m pip install -r doc/requirements.txt  Then, $ cd doc
$make html # may take several minutes$ browse _build/html/index.html  # or otherwise open in browser

to turn off the Python virtual environment once you have built the documentation use

$deactivate  ### Building the manual locally as a PDF via LaTeX# Note Before following these instructions, you should have a working local LaTeX installation and the ability to install additional packages, if need be, to resolve LaTeX errors. Set up your local Python environment (e.g. as above), then $ cd doc
$make latexpdf$ open _build/latex/manual.pdf  # or otherwise open in PDF viewer

### Sphinx Documentation Guidelines#

Refer to Sphinx’s own documentation for general information on how to use Sphinx, and note the following additional guidelines.

• Use the literalinclude directive to directly include pieces of source code. Use an “absolute” path, beginning with /, which means relative to the root for the Sphinx docs (where conf.py is found).

.. literalinclude:: /../src/sys/error/err.c
:start-at: PetscErrorCode PetscError(
:end-at: PetscFunctionReturn(0)
:append: }

For robustness to changes in the source files, Use :start-at: and related options when possible, noting that you can also use (positive) values of :lines: relative to this. For languages other than C, use the :language: option to appropriately highlight.

• Any invocable command line statements longer than a few words should be in .. code-block:: sections. Any such statements not in code-block statements must be enclosed by double backticks “”. For example make all is acceptable but

$make PETSC_DIR=/my/path/to/petsc PETSC_ARCH=my-petsc-arch all  should be in a block. • All code blocks showing invocation of command line must use the “console” block directive. E.g. .. code-block:: console$ cd $PETSC_DIR/src/snes/interface$ ./someprog
output1
output2

The only exception of this is when displaying raw output, i.e. with no preceding commands. Then one may use just the “::” directive to improve visibility E.g.

::

output1
output2

• Any code blocks that show command line invocations must be preceded by $, e.g. .. code-block:: console$ ./configure --some-args
$make libs$ make ./ex1
$./ex1 --some-args  • Environment variables such as $PETSC_DIR or $PATH must be preceded by $ and be enclosed in double backticks, e.g.

Set $PETSC_DIR and $PETSC_ARCH

• For internal links, use explicit labels, e.g

.. _sec_short_name:

Section name
============

and elsewhere (in any document),

See :ref:link text <sec_short_name>

• For internal links in the manual with targets outside the manual, always provide alt text so that the text will be properly formatted in the standalone PDF manual, e.g.

PETSc has :doc:mailing lists </community/mailing>.

• We use the sphinxcontrib-bibtex extension to include citations from BibTeX files. You must include .. bibliography:: blocks at the bottom of a page including citations (example). To cite the same reference in more than one page, use this workaround on one of them (example) 2.

• See special instructions on Images.

• Prefer formatting styles that are easy to modify and maintain. In particular, use of list-table is recommended.

• When using external links with inline URLs, prefer to use anonymous hyperlink references with two trailing underscores, e.g.

link text <https://external.org>__

• To pluralize something with inline markup, e.g. DMs, escape the trailing character to avoid WARNING: Inline literal start-string without end-string.

DM\s

• Use restraint in adding new Sphinx extensions, in particular those which aren’t widely-used and well-supported, or those with hidden system dependencies.

## Images#

PETSc’s documentation is tightly coupled to the source code and tests, and is tracked in the primary PETSc Git repository. However, image files are too large to directly track this way (especially because they persist in the integration branches’ histories).

Therefore, we store image files in a separate git repository and clone it when needed. Any new images required must be added to the currently-used branch of this repository.

### Image Guidelines#

• Whenever possible, use SVG files. SVG is a web-friendly vector format and will be automatically converted to PDF using rsvg-convert 3

• Avoid large files and large numbers of images.

• Do not add movies or other non-image files.

• Note the URL and currently-used branch (after -b) for the upstream images repository, as used by the documentation build:

	git clone https://gitlab.com/petsc/images.git -b main-1 --depth=1 images

• Decide where in doc/images a new image should go. Use the structure of the doc/ tree itself as a guide.

• Create a Merge Request to the currently-used branch of the upstream images repository, adding this image 4.

• Once this Merge Request is merged, you may make a Merge Request to the primary PETSc repository, relying on the new image(s).

It may be helpful to place working copies of new image(s) in your local doc/images while iterating on documentation; just don’t forget to update the upstream images repository.

### Removing, renaming, moving or updating images#

Do not directly move, rename, or update images in the images repository. Simply add a logically-numbered new version of the image.

If an image is not used in any integration branch (main or release), add it to the the top-level list of files to delete, in the images repository.

### Cleaning up the images repository (maintainers only)#

If the size of the image repository grows too large,

• Create a new branch main-X, where X increments the current value

• Create a new commit deleting all files in the to-delete list and clearing the list

• Reset the new main-X to a single commit with this new, cleaned-up state

• Set main-X as the “default” branch on GitLab (or wherever it is hosted).

• Update both release and main in the primary PETSc repository to clone this new branch

## Building Classic Documentation#

Some of the documentation is built by a “classic” process as described below.

The documentation tools listed below can be automatically downloaded and installed by configure.

Note that Sowing and C2html are build tools that do not use the compilers specified to PETSc’s configure, as they need to work in cross-compilation environments. Thus, they default to using gcc, g++, and flex from the user’s environment (or configure options like --download-sowing-cxx). Microsoft Windows users should install gcc etc. from Cygwin as these tools don’t build with MS compilers.

One can run this process in-tree with

$make alldoc12 LOC=${PETSC_DIR}

For debugging, a quick preview of manual pages from a single source directory can be obtained, e.g.

$cd$PETSC_DIR/src/snes/interface
$make LOC=$PETSC_DIR manualpages_buildcite
$browse$PETSC_DIR/docs/manualpages/SNES/SNESCreate.html  # or otherwise open in browser

Footnotes

1

This requires Python 3.3 or later, and you maybe need to install a package like python3-venv.

2

The extensions’s development branch supports our use case better (:footcite:), which can be investigated if a release is ever made.

3

rsvg-convert is installable with your package manager, e.g., librsvg2-bin on Debian/Ubuntu systems).

4

Maintainers may directly push commits.


text:
# Text based fight game

I learned code about a week ago and I wanna hear some recommendations and stuff I could add to my code. This is a fight system I made for my text based game. Please tell me what I could do better.

import random
import time
import sys
def fight_snake():
fdmg1 = int(random.randint(1,7))
edmg1 = int(random.randint(1,6))
print("You hit a", fdmg1)
print("The Snake hits a", edmg1)
time.sleep(1)
if edmg1 > fdmg1:
print("You died")
elif edmg1 < fdmg1:
print("You killed the Snake")
else:
print("You didnt kill the Snake but you managed to escape")

def fight_enemy_a():
fdmg1 = int(random.randint(1,7))
edmg_a = int(random.randint(4,10))
print("You hit a", fdmg1)
print("The Enemy hits a", edmg_a)
time.sleep(1)
if edmg_a > fdmg1:
print("You died")
elif edmg_a < fdmg1:
print("You killed the Enemy")
else:
print("You didnt kill the Enemy but you managed to escape")

def fight_enemy_b():
fdmg1 = int(random.randint(1,7))
edmg_b = int(random.randint(4,9))
print("You hit a", fdmg1)
print("The Enemy hits a", edmg_b)
time.sleep(1)
if edmg_b > fdmg1:
print("You died")
elif edmg_b < fdmg1:
print("You killed the Enemy")
else:
print("You didnt kill the Enemy but you managed to escape")

def fight_enemy_c():
fdmg1 = int(random.randint(1,7))
edmg_c = int(random.randint(1,7))
print("You hit a", fdmg1)
print("The Enemy hits a", edmg_c)
time.sleep(1)
if edmg_c > fdmg1:
print("You died")
elif edmg_c < fdmg1:
print("You killed the Enemy")
else:
print("You didnt kill the Enemy but you managed to escape")

# Design

As it stands, your current design is very rigid, and not extensible in any way. The best approach for a situation like this could be to use Object Oriented Programming, but in accordance with the Python talk, Stop Writing Classes, all of your code can be shortened to one function.

def fight_enemy(enemy_name, min_enemy_damage, max_enemy_damage, min_player_damage, max_player_damage):
enemy_damage_dealt = random.randint(min_enemy_damage, max_enemy_damage)
player_damage_dealt = random.randint(min_player_damage, max_player_damage)

if enemy_damage_dealt > player_damage_dealt:
print("Uh-oh! You died!")
elif enemy_damage_dealt < player_damage_dealt:
print("You killed the {enemy_name}".format(enemy_name=enemy_name))
else:
print("You walk away unscathed, but the {enemy_name} still lives.".format(enemy_name=enemy_name))

Here's an example function call:

fight_enemy("Enemy", 1, 10, 1, 10)

# Naming

Many of your variable names are so cryptic that it's understand what they're doing, even in the context of other code. Here's a small list of some of your bad variable names.

• fdmg1
• edmg_c

While identifying bad names is important, fixing them is even better. Here's a small list of tips to follow when naming variables.

• Don't make the name too short. (Unless you're doing stuff like coordinates, with x, and y.)
• Don't include abbreviations unless the name is long, and the abbreviations are still readable.
• Use underscores _ to separate words.

# Nitpicks

When getting an value from random.randint(), there's no need to convert to an integer using int. random.randint() already returns an integer value.

You should also be using string formatting with str.format, rather than passing multiple arguments to print(). For example, the following line:

print("The Enemy hits a", edmg_b)

Would become:

print("The Enemy hits a {damage}".format(damage=edmg_b))

For more on str.format, see the docs.

You also have to useless imports:

import time
import sys

If you don't use the contents of these modules, the imports can be removed.

In short, I've refactored your code down to this:

import random

def fight_enemy(enemy_name, min_enemy_damage, max_enemy_damage, min_player_damage, max_player_damage):
enemy_damage_dealt = random.randint(min_enemy_damage, max_enemy_damage)
player_damage_dealt = random.randint(min_player_damage, max_player_damage)

if enemy_damage_dealt > player_damage_dealt:
print("Uh-oh! You died!")
elif enemy_damage_dealt < player_damage_dealt:
print("You killed the {enemy_name}".format(enemy_name=enemy_name))
else:
print("You walk away unscathed, but the {enemy_name} still lives.".format(enemy_name=enemy_name))

Hope this helps! Enjoy!

• @KeanuJones No problem. Always love to help out! :) – Ethan Bierlein Aug 11 '15 at 0:29

# DRY

You are repeating yourself in a lot of places in your code. In fact, I'd say most all of your code is just a giant repeat.

You have 4 functions in your code. These functions are almost exactly identical, except for a few tiny points.

Each function is doing the same thing: getting two random numbers, logging them out with a message, and then running some conditionals on these numbers to determine what other message should be sent.

Therefore, why don't you stick these all into one function?

To fix your code, let's start by taking one of the functions and working our way towards having non-repeating code.

The function we will work from will be fight_snake:

def fight_snake():
fdmg1 = int(random.randint(1,7))
edmg1 = int(random.randint(1,6))
print("You hit a", fdmg1)
print("The Snake hits a", edmg1)
time.sleep(1)
if edmg1 > fdmg1:
print("You died")
elif edmg1 < fdmg1:
print("You killed the Snake")
else:
print("You didnt kill the Snake but you managed to escape")

I have one main problem with this function: you are hard-coding the enemy to be a "snake".

What if you want to have another enemy? Are you going to create another practically identical function just to print out a word that is not "snake"? Of course not; that would not be very effective.

To make this function more flexible, let's add a parameter to the function that is the enemy that the user is fighting.

That is done simply like this:

def fight_enemy(enemy):

Note: I changed the function name to fight_enemy because the function is no longer specific to a snake.

Now, instead of using the string "snake", we can use the parameter that was passed in to the function.

def fight_enemy(enemy):
fdmg1 = int(random.randint(1,7))
edmg1 = int(random.randint(1,6))
print("You hit a", fdmg1)
print("The " + enemy + " hits a", edmg1) # <== Changed
time.sleep(1)
if edmg1 > fdmg1:
print("You died")
elif edmg1 < fdmg1:
print("You killed the " + enemy) # <== Changed
else:
print("You didnt kill the " + enemy + " but you managed to escape") # <=== Changed

Now our function is looking pretty good, but there is still one problem: the random numbers. For each of your 4 functions, you generated different random numbers.

Now you mentioned that you are very new to this, so this next section may be very confusing.

To be able to implement different random numbers, let's create a dictionary that maps a single value to a tuple of two values for creating random numbers.

That could be done like this:

random_numbers = {
'a': ((1,7),(1,6)),
'b': ((1,7),(4,10)),
...
}

Note: random_numbers and 'a','b',... are bad variable names. I used these because I was unsure of their original use in the code. You should think of better ones.

Great, we have a dictionary, but that still doesn't help us not have to repeat code. That means it's time to create more parameters!

This parameter will be one of the keys of the random_numbers dictionary so the function knows which random number to grab.

def fight_enemy(enemy, type):
fdmg1 = int(random.randint(1, 7))
edmg1 = int(random.randint(random_numbers[type][0], random_numbers[type][1]))
print("You hit a", fdmg1)
print("The " + enemy + " hits a", edmg1)
time.sleep(1)
if edmg1 > fdmg1:
print("You died")
elif edmg1 < fdmg1:
print("You killed the " + enemy)
else:
print("You didnt kill the " + enemy + " but you managed to escape")

There! Now, when calling this function, the code simply has to pass in the type of the fight and the enemy name. (I called it "type" because I figured it determined the strength).

Now, you can delete those other 3 functions: all you have to use is this now!

However, there are still a few things I'd like to point out.

fdmg1 = int(random.randint(1,7))
edmg1 = int(random.randint(1,6))

This function has it's own scope, so you don't need to worry about other functions using the variables fdmg and edmg and messing up your code. These should be renamed to fdmg and edmg respectively.

The function:

random.randint

already returns an int, so there is no point in calling int on the return.


text:
# TTP08-06 Charged-Higgs effects in a new B -> D tau nu differential decay distribution

TTP08-06 Charged-Higgs effects in a new B -

TTP08-06 Charged-Higgs effects in a new B -

D tau nu differential decay distribution > We present a detailed analysis of charged-Higgs effects in the decay B → D tau nu. Updating the relevant formfactors, we find this decay mode competitive with and complementary to B → tau nu. The differential distribution in the decay chain B → D nu tau[→ pi nu] excellently discriminates between Standard-Model and charged-Higgs contributions. By measuring the D and pi energies and the angle between the D and pi tracks one can determine the magnitude and phase of the effective charged-Higgs coupling g_S.

 Ulrich Nierste, Stephanie Trine, Susanne Westhoff Phys. Rev. D 78 015006 2008 PDF PostScript arXiv


text:
# Truncated pyramid

How many cubic meters is volume of a regular four-side truncated pyramid with edges one meter and 60 cm and high 250 mm?

Correct result:

V =  0.163 m3

#### Solution:

$a_{1}=1 \ \text{m} \ \\ a_{2}=60/100=\dfrac{ 3 }{ 5 }=0.6 \ \text{m} \ \\ h=250/1000=\dfrac{ 1 }{ 4 }=0.25 \ \text{m} \ \\ \ \\ S_{1}=a_{1}^{ 2 }=1^{ 2 }=1 \ \text{m}^2 \ \\ S_{2}=a_{2}^{ 2 }=0.6^{ 2 }=\dfrac{ 9 }{ 25 }=0.36 \ \text{m}^2 \ \\ \ \\ V=h/3 \cdot \ (S_{1}+\sqrt{ S_{1} \cdot \ S_{2} }+S_{2})=0.25/3 \cdot \ (1+\sqrt{ 1 \cdot \ 0.36 }+0.36)=\dfrac{ 49 }{ 300 }=0.163 \ \text{m}^3$

We would be very happy if you find an error in the example, spelling mistakes, or inaccuracies, and please send it to us. We thank you!

Showing 0 comments:

Tips to related online calculators
Do you want to convert length units?
Do you know the volume and unit volume, and want to convert volume units?

#### You need to know the following knowledge to solve this word math problem:

We encourage you to watch this tutorial video on this math problem:

## Next similar math problems:

• Runcated pyramid teapot
The 35 cm high teapot has the shape of a truncated pyramid with the length of the edge of the lower square base a=50 cm and with the edges of the rectangular base b: 20 cm and c: 30 cm. How many liters of water will fit in the teapot?
• A square base
A solid right pyramid has a square base. The length of the base edge is 4 centimeters and the height of the pyramid is 3 centimeters. What is the volume of the pyramid?
• Pyramid a+h
Calculate the volume and surface area of the pyramid on the edge and height a = 26 cm. h = 3 dm.
• Water well
Drilled well has a depth 20 meters and 0.1 meters radius. How many liters of water can fit into the well?
• Conserving water
Calculate how many euros are spent annually on unnecessary domestic hot water, which cools during the night in pipeline. Residential house has 129 m of hot water pipelines 5/8" and the hot water has a price of 7 Eur/m3.
• Permille of alcohol
I have 2 per mille of alcohol in my blood. How many milliliters is it when I have 5 liters of blood?
• Gasholder
The gasholder has spherical shape with a diameter 23 m. How many m3 can hold in?
• Tiles
How many square tiles with the content 121 cm2 has to be ordered for the paving of the square room with a side length of 2.75 meters?
• Tray
Wjat height reach water level in the tray shaped a cuboid, if it is 420 liters of water and bottom dimensions are 120 cm and 70 cm.
• An oil
An oil drum is cut in half. One half is used as a water trough. Use the dimensions; length 82cm, width 56cm to estimate the capacity of the water trough in liters.
• Ice cream in cone
In the ice cream cone with a diameter of 5.7 cm is 0.8 dl of ice cream. Calculate the depth of the cone.
• Aquarium volume
The aquarium has a cuboid shape and dimensions a = 0.3 m, b = 0.85 m, c =? , V = ?. What volume has a body, if after dipping into the aquarium water level rises by 28 mm?
• Digging
A pit is dug in the shape of a cuboid with dimensions 10mX8mX3m. The earth taken out is spread evenly on a rectangular plot of land with dimensions 40m X 30m. What is the increase in the level of the plot ?
• Resistance
A resistor having an electrical resistance of 1.5 k ohms passes an electrical current of 0.1 A. Calculate what voltage is between the terminals of the resistor.
• Folded square
ABCD is a square. The square is folded on the midpoint of AB and A is folded onto the fold, creating a shaded region. The perimiter of the shaded figure is 75. Find the area of square ABCD
• Newtonmeters
The driver loosened the nut on the car wheel with a wrench that held 20 cm from the axis of the bolt. He acted on the key with a force of 320N. At what moment did he act on the bolt?
• Quatrefoil
Calculate area of the quatrefoil which is inscribed in a square with side 6 cm.


text:
# What is the molar mass of hexanol?

$102.18 \cdot g \cdot m o {l}^{-} 1$.
i.e. $\left(6 \times 12.011 + 14 \times 1.00794 + 15.999\right) \cdot g \cdot m o {l}^{-} 1$ =??
$\text{Hexanol}$, ${C}_{6} {H}_{13} O H$, has many isomers. Which isomer do you think would give the highest boiling point? See here.


text:
# Benny Brodda - dblp

Optimal Control of Markov Processes with Incomplete State

For every stationary Markov process in the first sense, there is a corresponding stationary Markov process in the second sense. The chapter reviews equivalent Markov processes, and proves an important theorem that enables one to judge whether some class of equivalent non-cut-off Markov processes contains a process whose trajectories possess certain previously assigned properties. Hidden Markov models - Traffic modeling and subspace methods Andersson, Sofia LU ( 2002 ) Mark Faculty of Engineering, LTH (1) Faculty of Science (1) 2021-04-24 A Markov process is a random process in which the future is independent of the past, given the present. Thus, Markov processes are the natural stochastic analogs of the deterministic processes described by differential and difference equations.

for Mathematical SciencesLund University2 Department of Mathematical SciencesNorwegian  Title: Lum 8 2016, Author: Lund University, Name: Lum 8 2016, Length: en smärtsam process att lyfta denna problematik på arbetsplatsen, men pollen data: Gaussian Markov random field models for compositional data”. Numerical discretisation of stochastic (partial) differential equations. David Cohen Atomic-scale modelling and simulation of charge transfer process and photodegradation in Organic Photovoltaics Mikael Lund, Lunds universitet Fredrik Ronquist. Introduction to statistical inference. Bayesian phylogenetic inference and Markov chain Monte Carlo simulation.

## CV Jennifer Alvén

The following is an example of a process which is not a Markov process. Consider again a switch that has two states and is on at the beginning of the experiment. We again throw a dice every minute. However, this time we ip the switch only if the dice shows a 6 but didn’t show MIT 6.262 Discrete Stochastic Processes, Spring 2011View the complete course: http://ocw.mit.edu/6-262S11Instructor: Robert GallagerLicense: Creative Commons The prototypical Markov random field is the Ising model; indeed, the Markov random field was introduced as the general setting for the Ising model.

### CV Jennifer Alvén

Thus, Markov processes are the natural stochastic analogs of the deterministic processes described by differential and difference equations. They form one of the most important classes of random processes. Any (Ft) Markov process is also a Markov process w.r.t. the ﬁltration (FX t) generated by the process. Hence an (FX t) Markov process will be called simply a Markov process. We will see other equivalent forms of the Markov property below. For the moment we just note that (0.1.1) Deﬂnition of a Markov Process † Let (›; F) be a measurable space and T an ordered set.

Lund SLE Research Group Markov Decision Processes. The Markov Decision Process (MDP) provides a mathematical framework for solving the RL problem. Almost all RL problems can be modeled as an MDP. MDPs are widely used for solving various optimization problems.
Talldungens gårdshotell restaurang

A countably infinite sequence, in which the chain moves state at discrete time steps, gives a discrete-time Markov chain (DTMC). A continuous-time process is called a continuous-time Markov chain (CTMC). In mathematics, a Markov decision process (MDP) is a discrete-time stochastic control process. It provides a mathematical framework for modeling decision making in situations where outcomes are partly random and partly under the control of a decision maker. MDPs are useful for studying optimization problems solved via dynamic programming.MDPs were known at least as early as the 1950s; a core 6. Linear continuous Markov processes 7.

Remark on Hull, p. 259: \present value" in the rst line of Abstract Let Φ t, t ≥ 0 be a Markov process on the state space [ 0, ∞) that is stochastically ordered in its initial state. Examples of such processes include server workloads in queues, birth-and-death processes, storage and insurance risk processes and reflected diffusions. Markov process whose initial distribution is a stationary distribution. 55 2 Related work Lund, Meyn, and Tweedie ([9]) establish convergence rates for nonnegative Markov pro-cesses that are stochastically ordered in their initial state, starting from a xed initial state. Examples of such Markov processes include: M/G/1 queues, birth-and-death A Markov process is a stochastic process that satisfies the Markov property (sometimes characterized as " memorylessness ").
Jobb fastighetsförvaltning

Thus, Markov processes are the natural stochastic analogs of the deterministic processes described by differential and difference equations. They form one of the most important classes of random processes 2014-04-20 2005-10-25 2019-02-03 Textbooks: https://amzn.to/2VgimyJhttps://amzn.to/2CHalvxhttps://amzn.to/2Svk11kIn this video, I'll introduce some basic concepts of stochastic processes and Markov Processes And Related Fields. The Journal focuses on mathematical modelling of today's enormous wealth of problems from modern technology, like artificial intelligence, large scale networks, data bases, parallel simulation, computer architectures, etc. For every stationary Markov process in the first sense, there is a corresponding stationary Markov process in the second sense.

A Markov chain is a discrete-time process for which the future behaviour, given the past and the present, only depends on the present and not on the past. A Markov process is the continuous-time version of a Markov chain. Clear, rigorous, and intuitive, Markov Processes provides a bridge from an undergraduate probability course to a course in stochastic processes and also as a reference for those that want to see detailed proofs of the theorems of Markov processes. It contains copious computational examples that motivate and illustrate the theorems.
Akassa kommunal

listen and love color street
socioekonomiskt utsatta områden
rakna ut graviditetspenning
smålandsgatan 7 värnamo
beräkna skattereduktion bolån

### Kemister jobb i Lund Lund lediga jobb

Since the characterizing functions of a temporally homogeneous birth-death Markov process are completely determined by the three functions a(n), w + (n) and w-(n), and since if either w + (n) or w-(n) is specified then the other will be completely determined by the normalization condition (6.1-3), then it is clear that a temporally homogeneous birth-death Markov process X(t) is completely Research Portal. Find researchers, research outputs (e.g. publications), projects, infrastructures and units at Lund University For this reason, the initial distribution is often unspecified in the study of Markov processes—if the process is in state $$x \in S$$ at a particular time $$s \in T$$, then it doesn't really matter how the process got to state $$x$$; the process essentially starts over, independently of the past. 2021-04-24 · Markov process, sequence of possibly dependent random variables (x1, x2, x3, …)—identified by increasing values of a parameter, commonly time—with the property that any prediction of the next value of the sequence (xn), knowing the preceding states (x1, x2, …, xn − 1), may be based on the last Lindgren, Georg och Ulla Holst. "Recursive estimation of parameters in Markov-modulated Poisson processes". IEEE Transactions on Communications.

## Efficient Monte Carlo simulation of stochastic hybrid systems

† Let K be a collection of subsets of ›. Thus decision-theoretic n-armed bandit problem can be formalised as a Markov decision process. Christos Dimitrakakis (Chalmers) Experiment design, Markov Decision Processes and Reinforcement LearningNovember 10, 2013 6 / 41. Introduction Bernoulli bandits a t r t+1 Figure: The basic bandit process CONTINUOUS-TIME MARKOV CHAINS Problems: •regularity of paths t7→X t. One can show: If Sis locally compact and p s,tFeller, then X t has cadl` ag modiﬁcation (cf.

Almost all RL problems can be modeled as an MDP. MDPs are widely used for solving various optimization problems. In this section, we will understand what an … De nition 2.1 (Markov process). The stochastic process X is a Markov process w.r.t.


text:
# The integers and the rationals are homeomorphic?

We know since $\mathbb{Q}$ is countable that there exist a bijection $f : \mathbb{Z} \to \mathbb{Q}$. If we view $\mathbb{Q}$ and $\mathbb{Z}$ are topological subspaces of $\mathbb{R}$, are theo homeomorphic??

-
Which topology do you consider? Subsets of $\mathbb{R}$ or another? –  Duronman Oct 29 '13 at 10:24
the induced topology –  Chasky Oct 29 '13 at 10:26
Is $\{17\}$ an open subset of $\mathbb{Q}$, under the induced topology? –  André Nicolas Oct 29 '13 at 10:28
It’s true that it’s not open, but that has nothing to do with its being closed: a set can be both open and closed. For example, $\{q\in\Bbb Q:q^2<2\}$ is clopen (both open and closed) in $\Bbb Q$. –  Brian M. Scott Oct 29 '13 at 10:34
In the induced topology on $\mathbb{Q}$, they are not open. Under the induced topology on $\mathbb{Z}$, they are open. –  André Nicolas Oct 29 '13 at 10:36
show 1 more comment

Solution 1: Is $\mathbb{Q}$ a discrete topological space?

Solution 2: When does a sequence in $\mathbb{Z}$ converge?

Solution 3: Is $\mathbb{Q}$ locally compact?

-
First pick a topology. So in this case I assume its the induced topology. Now any topological invariant will give an obstruction to a homeomorphism. For example, $\mathbb{Q}$ is everywhere dense in $\mathbb{R}$, but $\mathbb{Z}$ is not. So the answer is no, they are not homeomorphic.
“$\mathbb{Q}$ is everywhere dense in $\mathbb{R}$” does not give an obstruction to a homeomorphism! It’s not an intrinsic topological property of $\mathbb{Q}$, but rather a property of the embedding of $\mathbb{Q}$ into $\mathbb{R}$. For instance, $\mathbb{Q} \setminus [0,1]$, with its induced topology from $\mathbb{R}$, is not dense in $\mathbb{R}$ but is homeomorphic to $\mathbb{Q}$. –  Peter LeFanu Lumsdaine Oct 29 '13 at 16:03


text:
# Baby twins deep learning classification with Inception-ResNetV1

A photo of my two girls with annotations. It will be used for building the face recognition dataset. In the blog post, their faces have been blurred for anonymization.

Deeplearning techniques have proven to be the most efficient AI tools for computer vision. In this blog post we use a deeplearning convolutional neural network to build a classifier on my baby twins pictures.

When it comes to machine learning practical experiments, the first thing anybody needs are some data. When experimenting for hobby, we often rely on some open and popular dataset such as MNIST or the IMDB reviews. However, it is useful for improving to be confronted with challenges on fresh and unworked data.

Since July 2019 (9-months at the time of the writing), I am the happy father of two lovely twin baby girls: L and J. If I have free private data at scale, it is definitely photos of my kids. Indeed, all our families have been taking pictures of them and, thanks to Whatsapp and other communications means, I have been able to collect a great part of them.

Deeplearning and Convnet neural networks are now the state-of-the-art methods for computer vision. Here are Convnet visualizations on a L. photo.

In this post, we will use a state-of-the-art deep learning architecture: Inception ResNetV1 to build a classifier for photo portraits of my girls. We also take benefit of some pretrained weights from facenet dataset. Before that, we will make a detour by tricking a little bit the problem: this will allow us to check our code snippets and review some nice visualization techniques. Then, the InceptionResNetV1 based model will allow us to achieve some interesting accuracy results. We will experiment using Keras backed by Tensorflow. We conducted the computing intensive tasks on a GPU machine hosted on Microsoft Azure.

The code source is available here: on Github. The dataset is obviously composed of personal pictures of my family that I do not want to let openly accessible. In this blog post, the faces of my babies have been intentionally blured to preserve their privacy. Of course, the algorithms whose results are presented here were run with non obfuscated data.

In this post and in the associated source code we reuse some of the models and snippets from the (excellent) book Deep Learning with Python by François Chollet. We also leverage the InceptionResNetv1 implementation from Sefik Ilkin Serengil.

Let us start this post by explaining the problem and why it is not as easy as it may seems to be.

## A more complex topic that it seems

While my baby girls L and J are not identical twins, they definitely are sisters, they do look alike a lot! In addition, the photos were taken since their first days in this world to their 8 months. It is no secret that babies change a lot during their first months. They were born weighing around 2.5 kgs, now they are close to 9 kgs. Even family members whom saw them in their first days have difficult times distinguish them now.

In addition, following their grandmother’s home country tradition L and J were shaved at the age of 4 months. Their haircut is not a way to distinguish them: we have photos before the shaving, during hair regrowth and now with middle to long hairs. Also, many photos were taken with a woolen hat or anything else. Consequently, we will be pushing a little the limits of face recognition.

Our objective in this series of experimentation is to build a photo classifier. Precisely, given a photo we would like to make a 2-class prediction: “Is this photo is the one of L or J?”. We assume then that each picture contains one and only one portrait of one of my two baby girls.

I have collected 1000 raw photos that will be used to create the dataset.

## Building the dataset

### Photo tagging

In the raw datasets, some photos contain only L, others only J, some both and some none of them. We exploit these photos to extract face pictures for each girl. To do so, we need to locate precisely the faces in the photos first.

For efficient annotation, I have used an opensource tagging software: VoTT which is supported by Microsoft. The tagging is pretty straightforward and you can quickly annotate the photos with a very intuitive interface. It took me between one and two hours to tag the full dataset.

Efficient photo annotation with the VoTT software. Note also the FC Nantes outfits…

One of the worries of twins parents, is the fear to favor one child over the other. Well, I am not concerned and data speak for me. Here are the results: after the tagging we have a very well balanced tags repartition with a little more than 600 tags for each of the girls.

The tag repartitions of L and J.

Now we will build the picture dataset: where each picture contains the portrait of one of the kid. VoTT provides the tag location within the picture as a JSON format. Therefore, it is easy to crop all files to produce a dataset where each image contains only one kid’s face, see this code snippet.

The extraction process from tagged photos to square cropped images.

### Splitting the dataset: train, validation, test

As always for any machine learning training procedure, one must separate the original dataset between: 1) training data that will be used to fit the model and 2) validation data that will be used to measure performance of the tuned algorithms. Here we go further by keeping also a third untouched test dataset.

It is always easier to work with an equally balanced dataset. Luckily this is almost the case with the original data. Consequently after processing (mainly shuffling and splitting) we obtain the following repartition in our file system:

├── train
│ ├── J => 396 JPG files
│ └── L => 396 JPG files
├── validation
│ ├── J => 150 JPG files
│ └── L => 150 JPG files
└── test
│ ├── J => 100 JPG files
│ └── L => 100 JPG files

The code snippets for splitting and shuffling the dataset is available here.

## Machine setup – GPU Powered VM

The experiments are conducted with Python 3.6 and Tensorflow GPU 1.15. We use the high level deeplearning library Keras 2.2.4.

We have setup an Ubuntu 18.04 NC6 GPU VM on Microsoft Azure. The NC-series VM use Nvidia Tesla K80 graphic card and Interl Xecon E5-2690 for CPU. With the NC6 version we benefit from 1 GPU and 6 vCPU, this setup maked the following computations perfectly acceptable: all experiments lasted less than few minutes.

This is the second time I do the setup of an Ubuntu machine with Cuda/cudNN and Tensorflow, same as before this was a real pain. The official documentation from Tensorflow is totally incorrect and guides you in the wrong direction. Finally, I managed to have a successful setup with the following Tensorflow-gpu 1.15.0, Keras 2.2.4 and Cuda 10.0 thanks to this StackOverflow post.

For efficient development, I use VSCode with the new SSH Remote extensions which make remote development completely seamless. The experiments are also conducted with IPython Jupyter notebook. And once again VSCode provides out-of-the-shelf SSH tunneling to simplify everything.

Tensorflow outputs confirm that its primary computing device is our Tesla K80 GPU.

The nvidia-smi command shows load on the GPU from the Python process

## First, a simplified problem with tricked data to get started

The experiments provided in this section can be found in this notebook.

Here we will make a small detour by simplifying tricking the challenge. We will add easily detectable geometrical shapes in the images.

### Drawing obvious shapes on image classes

When tackling a datascience project, I always think it is great to start really simple. Here, I wanted to make sure that my code snippets were ok so I decided to trick (temporarily) the problem. Indeed, I drawed geometrical shapes on image classes. Precisely, for any J photo, a rectangle is drawn and, for any L photo, an ellipse is inserted. The size, the shape ratio and the filling color are left random. You can see with the two following examples what this looks like:

An ellipse is drawn on all L photos, for train, validation and test sets.

A rectangle with random filling color on all J images.

Of course this completely workarounds and tricks the face recognition problem. Anyway that’s a good starting point to test our setup and code experimentation snippets.

### A simple Convnet trained from scratch

For this simplified task we use the basic Convnet architecture introduced by Francois Chollet in his book (see the beginning of the post). Basically, it consists of 4 2D-convolutional layers followed by MaxPooling layers. This constitutes the convolutional base of the model. Then the tensors are flatten and a series of Dense and Dropout layers are added to perform the final classification parts.

_________________________________________________________________
Layer (type) Output Shape Param #
=================================================================
conv2d_1 (Conv2D) (None, 198, 198, 32) 896
_________________________________________________________________
max_pooling2d_1 (MaxPooling2 (None, 99, 99, 32) 0
_________________________________________________________________
conv2d_2 (Conv2D) (None, 97, 97, 64) 18496
_________________________________________________________________
max_pooling2d_2 (MaxPooling2 (None, 48, 48, 64) 0
_________________________________________________________________
conv2d_3 (Conv2D) (None, 46, 46, 128) 73856
_________________________________________________________________
max_pooling2d_3 (MaxPooling2 (None, 23, 23, 128) 0
_________________________________________________________________
conv2d_4 (Conv2D) (None, 21, 21, 128) 147584
_________________________________________________________________
max_pooling2d_4 (MaxPooling2 (None, 10, 10, 128) 0
_________________________________________________________________
flatten_1 (Flatten) (None, 12800) 0
_________________________________________________________________
dropout_1 (Dropout) (None, 12800) 0
_________________________________________________________________
dense_1 (Dense) (None, 512) 6554112
_________________________________________________________________
dense_2 (Dense) (None, 1) 513
=================================================================
Total params: 6,795,457
Trainable params: 6,795,457
Non-trainable params: 0

### 97%+ accuracy

Actually this is no surprise that we are able to achieve great classification performance. The algorithms performs without difficulty. To do so we used the standard Data-augmentation techniques. Note that for this task we skipped the rotations.

## Define TRAINING SET
train_datagen = ImageDataGenerator(rescale=1./255, rotation_range=0,
width_shift_range=0.2,
height_shift_range=0.2,
shear_range=0.2,
zoom_range=0.2,
horizontal_flip=True, fill_mode='nearest')

train_generator = train_datagen.flow_from_directory(TRAIN_DIR,
target_size=(TARGET_SIZE, TARGET_SIZE),
batch_size = BATCH_SIZE,
class_mode='binary')

## Define VALIDATION SET
validation_datagen = ImageDataGenerator(rescale=1./255)
validation_generator = validation_datagen.flow_from_directory(VAL_DIR,
target_size=(TARGET_SIZE, TARGET_SIZE),
batch_size = BATCH_SIZE,
class_mode='binary')

After running the training on 30 epochs we observe the following learning curves.

model.compile(loss='binary_crossentropy', optimizer=optimizers.RMSprop(lr=1e-3), metrics=['acc'])
history = model.fit_generator(train_generator, steps_per_epoch=steps_per_epoch, epochs=30, validation_data=validation_generator, validation_steps=50)

Training and validation accuracy on tricked data. We achieve strong accuracy without surprise.

Now that the results seem satisfactory without sign of overfitting (the validation accuracy grows and stalls). It is time to measure performance on the test sets composed of the 200 pictures left aside.

Accuracy is a key indicator but even with a 2-class classification problem, it is a common error to ignore more subtle information such as the confusion matrix. Using the following snippet and the scikit learn library. We are able to collect a full classification report along a confusion matrix. Again, here all signals are green, and we see the results of a very efficient classifier. Yet, let us not forget that the game has been tricked!

from sklearn.metrics import classification_report, confusion_matrix

TEST_SIZE=200
target_names = ['J', 'L']
Y_pred = Y_pred.flatten()
y_pred_class = np.where(Y_pred > 0.5, 1, 0)

print('Classification Report')
print(classification_report(test_generator.classes, y_pred_class, target_names=target_names))

print('Confusion Matrix')
plot_confusion_matrix(confusion_matrix(test_generator.classes, y_pred_class),target_names)

The confusion matrix with tricked data. We see excellent accuracy, precision and recall.

### Going beyond and observe Conv2d learnings with an activation model

Again, we use a technique well exposed in the François Chollet’s book.

The idea is to build a multi output model based on the successive outputs of the base convolutional layers. Thanks to the successive ReLu layers, we can plot the activation maps from the outputs of these layers. The following visuals illustrate well that our Convnet base model has successfully learned the geometrical shape: the curved stroke of ellipses and the squared edges of rectangles.

layer_outputs = [layer.output for layer in model.layers[:depth]]
activation_model = models.Model(inputs=model.input, outputs=layer_outputs)
predictions = models.predict(input_img_tensor)

One the extracted feature on the bottom layer from the L picture with ellipse. We see in green the activated regions. The ellipsis is strongly activated but also the pacifier.

From the bottom layers of our neural network model, the ellipsis are obviously the most activated regions of the input picture.

With upper layers, it is visible that the patterns that is captured for the classification is the curve of the stroke path of our ellipsis. Similarly, the square corners of the rectangles are captured.

## Back to the real face recognition problem

Now it is time to get back to our original problem: classification of my baby girls without relying on any trick, just with face recognition on the original images. The simple Convnet in the previous section will not be sufficient to build a classifier with significant accuracy. We will need bigger artillery.

The experiments provided in this section can be found in this notebook.

### Using the InceptionResNetV1 as a base model

InceptionResNetV1 is a deep learning model that has proven to be one of the state-of-the-art very deep architecture for convolutional networks. It also uses the concept Residual Neural Networks.

We use its implementation provided originally by Sefik Ilkin Serengil whom was also reusing parts of the implementation provided by David Sandberg.

For our classification problem, we use InceptionResNetV1 as the base (then very deep) network. On top of it we flatten the tensors and bring Dense and Dropout layers to serve as classification.

Layer (type) Output Shape Param #
=================================================================
inception_resnet_v1 (Model) (None, 128) 22808144
_________________________________________________________________
dense_1 (Dense) (None, 256) 33024
_________________________________________________________________
dropout_1 (Dropout) (None, 256) 0
_________________________________________________________________
dense_2 (Dense) (None, 64) 16448
_________________________________________________________________
dropout_2 (Dropout) (None, 64) 0
_________________________________________________________________
dense_3 (Dense) (None, 16) 1040
_________________________________________________________________
dense_4 (Dense) (None, 1) 17
=================================================================
Total params: 22,858,673
Trainable params: 22,829,841
Non-trainable params: 28,832

### Achieving nearly 0.80 accuracy

We conducted some experiments when trying to make InceptionResNetV1 without any prior weights tuning, which means without using pre-trained experimentations (sometimes called Transfer Learning). Without any surprise, the model could not reach significant validation accuracy (i.e. significantly above 0.6 in accuracy). Our dataset, even with data augmentation, is too small to let a deep architecture “learn” what are the key elements that constitute the characteristics of a human face.

Therefore, we reuse pretrained weights from facenet database, provided by David Sandberg and Sefik Ilkin Serengil in his blog post.

from inception_resnet_v1 import *

def model_with_inception_resnet_base(pretrained_weights):
model = InceptionResNetV1()

if pretrained_weights == True:

new_model = models.Sequential()

return new_model

Thanks to our GPU we were able to retrain the full model composed of a InceptionResNetV1 base with our top layers classifiers. We did not even have to recourse to fine-tuning techniques where the first layers weights need to be frozen.

After a dozen of minutes of training, I was happy to see the following training and validation accuracy curves.

The training and validation accuracy over the epochs. We see that the validation accuracy reaches 0.80 accuracy.

This shows all the positive signs of a successfully trained ML algorithm. Therefore, let us examine the performance on the test dataset, i.e. the one that has not been fed to the algorithm before.

The final classification report and confusion matrix. We achieves nearly 0.80 of accuracy.

The classification reports and confusion matrix on the test dataset confirm the measure on the validation set. We achieve nearly 80% of accuracy. One interesting thing is, from the report, J. looks to be a little be more difficult for our model to classify than L. Honestly, I have no assumption on what could cause this. A deeper analysis by examining layers in the spirit of what has been presented above could be conducted.

## Conclusion

I did not spend time trying to tune so much the InceptionResNetV1 hyperparameters. I also tweaked but only a little the top layers. No doubt that there is room for great improvements here. This can constitute a follow up blog post.

Also, I did not confront other algorithms and deeplearning architectures. I quickly gave a try to the Deepface Keras implementation but without significant results. I did not spend time investigating why this was not working. Once again this could be part of an interesting follow up. Ideally, I would also benchmark this DLib implementation.

By conducting these experiments, I confirm that it is nearly impossible to perform “real” recognition on faces without some kind of pretrained models if you have at hands this small amount of face data.

Finally, I learnt a lot. It is always a good thing to try things on your own data. This is how you learn to tackle real-life problems in datascience.

Our classifier works: it is now able at 80% accuracy to recognize between my two baby girls.

# An unexpected quadratic cost in Excel Interop

My current task at work is the development of an excel addin. This addin is developed in C# .NET and is based on the Excel Interop assemblies, we also use Excel DNA for the packaging and the User Defined functions. While developing a new feature I stumbled upon a technical oddity of Excel Interop which I will describe to you in this post.

Let me start this post by reminding you that a range in Excel is not necessarily a block of contiguous cells. Indeed, try it yourself by starting excel right now. Then you can select a range, keep the Ctrl button of your keyboard press on and select an other block of contiguous cell. Then, you have several cells selected that you can name (as shown in the screenshot). Finally, you have created a named range with non-contiguous cells.

Having said that, let us assume that for our addin we need to reference programmatically the range of all lines of the form, with usual excel notations, Ax:Cx where x describes a set of row indices.

Then we need to use the method Application.Union of Micorsoft.Office.Interop.Excel and finally produce few lines of code that  looks like that.

In the chart above we have monitored the time execution of the BuildUnionAll method for different values of the parameter count.

Remark: in the case of BuildUnionAll there is no need to use a loop and the Union method, we could have just ask for the range “A1:Ccount”. Note also that for small unions you may also use a syntax with semicolon to separate contiguous cells blocks e.g. worsheet.Range[“A1:C3;A8:C12”]. However, this does not work for large ranges made of multiple non-adjacent cells blocks.

So far so good, we see an almost linear curve, which is natural regarding to what we were expecting.

Now, change a little bit our expectation to something quite different and more realistic where we would truly need the Application.Union method. Then let us say that we would like to have the union Ax:Cx mentioned above but for x odd index only. We want the IEnumerable<int> to have the same size than before, so let us use the method in the code below.

Similarly, we monitor the performance curve.

Argghhh!!! we get an awful quadratic cost which makes our approach completely broken for large unions. This quadratic cost was unexpected. Actually I did not found documentation on this (the msdn doc on Excel.Interop is really minimalist). However, it seems that the rule is that the Union method has a linear cost depending on the number of Areas in the input ranges. The Areas member of a Range is the collection containing the blocks of contiguous cells of the range.

This experimental rule, leads us to review our algorithm in a different way. If the cost of an Union is important (linear) when there are many areas in a range. Then we will try to minimize this situation: we will let our algorithm perform the union preferably on ranges having fewer areas. Once again, the basic techniques from school bring a good solution and we will design a very simple recursive algorithm based on the divide and conquer approach, inspired for the merge sort algorithm.

To the end, we recover an almost linear curve. The asymptotic complexity here (if the rows to pick are not adjacent to each other) equals the merge sort one which is O(n.ln(n)).

# F#-ception, wtf ?!?

Hi, its middle of summer so let us relax with a “coding for fun” post. The subject presented here came from a kind of “wtf contest” that we had with a colleague of mine on our free time. The objective was to write a unit test to tackle an existing code base using the weirdest approach. My contestant Gabriel is a brilliant developer, so in order to compete with him I had to bring something really absurd rather than technically sophisticated. So I came with the idea of executing F# code inlined in a powershell script invoked from F# code. Obviously, this is absolutely useless. However, it fitted well for the thematic of the  contest. In this post we will skip the “existing code base” part and focus on how to achieve this with a very simple example .

The first part of the job is to write some F# code that builds the powershell script with inlined F#. We will have to reference the F# code dom provider which can be downloaded here. Remark that for the sake of simplicity of this post we did not add any extra assemblies (see referencedAssemblies in script below).

Then let us try the FsToPs function with very simple case

Thus, the powershell code in simpleExample.ps1 looks like

You should be able to run this script in a powershell session. However, it is not finished for us, we have to invoke this script in F# and retrieve the returned value. The following snippet will do the job for us.

Then executed within MsTest framework….

…it works!

I’d like to thank Gabriel for being fair play by helping me to debug the first version of F#-ception.

# Rewriting a tree algorithm with purely functional data structures: the “zippers”.

This is my first post, it follows a question that I have posted few weeks ago here. A really interesting link provided by a stackoverflow user made me review my question and lead me to write this post. The objective here is to describe the modification of an existing algorithm implementation, from a first try which uses intensively mutability of the underlying data structure to a purely immutable functional implementation. We will show that this can be achieved quite easily when using the appropriate data structures which in our case are the so-called “zippers”.

I discovered the F# programming language recently. While implementing some stuff for the discovery of the language I came confronted with the next problem. Given a sequence of branches coming from a tree but accessible one by one in a random order, how to reconstruct (efficiently) a labeled tree. For example, imagine to retrieve your disk paths in a random order e.g. “C:\Foo”, “C:\”, “C:\Foobar”, “C:\Foo1\bar2” etc. and you would like to rebuild your filesystem.

The branches are supposed to be represented by a linked list of string labels. We also assume that the sequence does not contain twice the same branch and it is in valid, in the sense that a labeled n-ary tree can be created with it. There may be many trees that can be built but we will accept any of them, in other words, we do not care about the order of the children of a given node. The n-ary tree data structure is the usual one where the children of a node are represented by a linked list.

I have no doubt that there may exit better solutions but let us focus at the first implementation that came to my mind as a seasoned imperative and an inexperienced functional programmer. The algorithm is recursive and works as follows.

The branch is inserted in the tree using the recursive procedure:
If the current tree is empty then it is replaced by the branch (as a tree). Except the previous corner case, the invariant loop states that “the label of the current tree node is equal to head of the current branch”.
Having said that we explore a step below:
If the tail of the current branch is empty list then there is nothing to do. Indeed, following the invariant loop, the current branch is actually a sub-branch of the existing tree.
Else, we search the children of the given node and try to find a match with the next value of the current branch.
If such a match exists we are not done yet, we have to go deeper and apply our procedure on the subtree of the matched child with the tail of current branch.
If there is no match, we are arrived to an end so we append the current branch (transformed as a tree) to the children list.

Implementing this in F# leads to the following code (provided some help from Leaf Garland). The function that builds the tree is the mergeInto that performs side effects on its first parameter.

Now apply this with a simple example.

However, this implementation is quite frustrating because we have hacked our functional data structure with F# ref cells to enable mutability just for this particular construction. We needed such mutability to perform our “append” operation on the tree. We were focused on a subtree and we could not return a new tree with the branch attached correctly.  Because of the recursion, we did not know where we were exactly.

This is were the zippers come into play. The zippers were introduced by Gerard Huet in this paper. The authors says that they have probably been “invented at numerous occasions by creative programmers” but never published. I recommend you to have a look on the first fourth pages of this paper, it is very accessible for an academic publication and may help you for the following.

A zipper is a practical implementation of a given data structure, this is why we can say that what follows is a labeled n-ary tree implemented using the zipper pattern. To sum up, the zipper enables you to focus on a subtree but the structure keeps the path that lead you there granting you to return a new immutable instance of the complete tree.

The translation of zippers implementation of Huet’s paper from OCAML to F# is straightforward. In the implementation below I reused the good idea from this post where the author changed the order of the function arguments to enable F# pipe-forward. The go functions are used for tree traversal while the insert returns a new data structure with the input tree inserted. Most of the implementation of the zippers provided on the web are designed for leaf-labeled trees, so for our case we need to extend the types to support labeled trees. In the code below, we have removed the go_left and insert_left because they were not of any use for the following.

The power of the zippers comes from the Path and Location discriminated unions, even if the focus is on a subtree we know where we are because we kept track of what is on our left, above and on our right. If you want to visualize some zipper I suggest you to read this post.
You can see that the difference with Huet’s implementation on leaf-labeled trees is that the Path type contains the label of the currentPosition (that can be retrieved with the getLabel method). I was in difficulty to implement the go_up method without it (to build the parent node), though I am not completely satisfied with this…

Now, it is time to review our algorithm and we will see that it will become more elegant and less imperative:
The main difference comes from the fact that we do not have to look for a “matched child” while keeping the focus on the current node. We can go down directly and move right.
Precisely, the first corner case with the Empty tree stays similar. The invariant loop states “that the parent label of the current node equals the head of the current branch”.
Then, if the label of the node matches the head of the branch, we have to go deeper. If there is no right simbling then this is our destination and we have to append the branch here. Finally, if there is a younger simbling (a node at the right) reapply the procedure but put the focus on him.

In this new implementation, we can append the branch to the good location because we have an insert_right operation. In the previous implementation we could not do this (without modifying once again the tree structure) because we would have gone too deep to append the tree to the list kept by the parent of our node.

Remark that we have not speak the word “zipper” in the description, the zippers are only wrappers that provides efficient and useful operations on our immutable data structure.
So the core algorithm looks now

We introduce the getZipper function that creates a zipper around a tree and the appendToTree which is the method that we will call effectively (abstracting the zipper). Here how it works with the same branch sequence.

So now we have a competitor to our mergeInto method which uses only purely functional and immutable datastructure and which does not require any modification on the exposed tree data structure. Remark that provided the same input sequence of branches the two algorithms do not build the same tree. However, I would not said that the zipper is without default for our case. The zipper structure is quite complex , that is non negligible. We have also added an extra complexity cost, not in the appendToTreeZipper function but in appendToTree, it comes from the root function. After a quick examination of the go_up method an upper bound for the root function complexity can be found, it is the height of the tree multiplied by the number of individuals in the largest sibship.