Humor Writing for People Who Aren’t Funny:
'via Blog this'
Saturday 28 December 2013
Friday 27 December 2013
Wednesday 25 December 2013
Free Partition Magic alternative, partition manager freeware, partition magic server, partition magic Windows 7 and free Partition Manager software for Windows 7/8/VISTA/XP/2000 and Windows Server 2003/2008/2000.
Tuesday 24 December 2013
Monday 23 December 2013
Sunday 22 December 2013
Friday 20 December 2013
Thursday 19 December 2013
Tuesday 17 December 2013
Tuesday 10 December 2013
Monday 9 December 2013
Sunday 8 December 2013
Friday 6 December 2013
Thursday 5 December 2013
Tuesday 3 December 2013
Monday 2 December 2013
Tuesday 26 November 2013
Monday 25 November 2013
C# Scraping HTML Links
C# Scraping HTML Links: "WebClient w = new WebClient();
string s = w.DownloadString("http://en.wikipedia.org/wiki/Main_Page");
// 2.
foreach (LinkItem i in LinkFinder.Find(s))
{
Debug.WriteLine(i);
}"
'via Blog this'
string s = w.DownloadString("http://en.wikipedia.org/wiki/Main_Page");
// 2.
foreach (LinkItem i in LinkFinder.Find(s))
{
Debug.WriteLine(i);
}"
'via Blog this'
Sunday 24 November 2013
Friday 22 November 2013
Thursday 21 November 2013
Tuesday 19 November 2013
Monday 18 November 2013
Saturday 16 November 2013
Friday 15 November 2013
Wednesday 13 November 2013
Monday 11 November 2013
Sunday 10 November 2013
Saturday 9 November 2013
Friday 8 November 2013
Friday 1 November 2013
Monday 14 October 2013
Saturday 13 July 2013
Thursday 11 July 2013
Wednesday 10 July 2013
Tuesday 9 July 2013
Monday 8 July 2013
Sunday 7 July 2013
Friday 5 July 2013
Thursday 4 July 2013
Tuesday 2 July 2013
Sunday 30 June 2013
Colin Steele's Blog, Against the Grain: How We Built the Next Generation Online Travel Agency using Amazon, Clojure, and a Comically Small Team
Wednesday 26 June 2013
Monday 17 June 2013
Friday 14 June 2013
Friday 31 May 2013
Sunday 26 May 2013
Sunday 19 May 2013
Friday 10 May 2013
Wednesday 17 April 2013
Friday 12 April 2013
Monday 8 April 2013
Eller's Algorithm
Eller's Algorithm:
'via Blog this'
There is very little written about Eller's Algorithm on the internet. The best source I could find (Walter Pullen's excellent Think Labyrinth website) has a single paragraph description which, while very helpful, I found inadequate to implement the algorithm. Additionally, the algorithm described in Mathematics and Physics for Programmers doesn't seem to work. Needless to say, uncovering information about this very interesting algorithm was frustrating. I was able to work out the missing details, and I'm confident that the algorithm I came up with is indeed Eller's algorithm. This page is intended to (hopefully) alleviate the suffering of future searchers interested in this facinating maze generator.
Update:At least one new useful page has appeared on the net since I first wrote this. Check out Jamis Buck'sMaze Generation: Eller's Algorithm blog post. I'll add other useful links as I find them.
Home - Last modified: June 2012
'via Blog this'
Eller's Algorithm
Eller's algorithm creates 'perfect' mazes, having only a single path between any two cells, one row at a time. The algorithm itself is incredibly fast, and far more memory efficient than other popular algorithms (such as Prim's and Kruskal's) requiring storage proportional to only a single row. This makes it possible to create mazes of indefinite length on systems with limited memory.There is very little written about Eller's Algorithm on the internet. The best source I could find (Walter Pullen's excellent Think Labyrinth website) has a single paragraph description which, while very helpful, I found inadequate to implement the algorithm. Additionally, the algorithm described in Mathematics and Physics for Programmers doesn't seem to work. Needless to say, uncovering information about this very interesting algorithm was frustrating. I was able to work out the missing details, and I'm confident that the algorithm I came up with is indeed Eller's algorithm. This page is intended to (hopefully) alleviate the suffering of future searchers interested in this facinating maze generator.
Update:At least one new useful page has appeared on the net since I first wrote this. Check out Jamis Buck'sMaze Generation: Eller's Algorithm blog post. I'll add other useful links as I find them.
The Algorithm
Note: Assume that there all left-most cells have a left-wall and all right-most cells have a right wall.
- Create the first row. No cells will be members of any set
- Join any cells not members of a set to their own unique set
- Create right-walls, moving from left to right:
- Randomly decide to add a wall or not
- If the current cell and the cell to the right are members of the same set, always create a wall between them. (This prevents loops)
- If you decide not to add a wall, union the sets to which the current cell and the cell to the right are members.
- Create bottom-walls, moving from left to right:
- Randomly decide to add a wall or not. Make sure that each set has at least one cell without a bottom-wall (This prevents isolations)
- If a cell is the only member of its set, do not create a bottom-wall
- If a cell is the only member of its set without a bottom-wall, do not create a bottom-wall
- Decide to keep adding rows, or stop and complete the maze
- If you decide to add another row:
- Output the current row
- Remove all right walls
- Remove cells with a bottom-wall from their set
- Remove all bottom walls
- Continue from Step 2
- If you decide to complete the maze
- Add a bottom wall to every cell
- Moving from left to right:
- If the current cell and the cell to the right are members of a different set:
- Remove the right wall
- Union the sets to which the current cell and cell to the right are members.
- Output the final row
A Sample Run
The example here will create a rectangular maze of indefinite length. We'll create the maze one row at a time starting at the top row and moving left to right between cells. Each cell in a row will be assigned to a set. We'll represent that here by enumerating the sets and writing the number of the set that a cell belongs to inside each cell. Each cell can have a wall on the right and on the bottom. We'll assume that a wall exists to the left of the leftmost cell and the the right of the rightmost cell in each row and that a wall exists on the top of all cells in the first row._1_| 4 _4_| 6 6 _6_| <-- 1="" ___="" current="" is="" old="" our="" remove="" right="" row="" u="" walls:="">_1_ _1_| 4 _4_| 6 6 _6_| | 1 _1_ _1_ 4 _4_ 6 6 _6_| If a cell has a bottom wall, remove it from its set: ___ ___ ___ ___ ___ ___ ___ ___ | 1 _1_ _1_| 4 _4_| 6 6 _6_| | 1 ___ ___ 4 ___ 6 6 ___| Remove bottom walls: ___ ___ ___ ___ ___ ___ ___ ___ | 1 _1_ _1_| 4 _4_| 6 6 _6_| | 1 4 6 6 | Continue from Step 2: Step 2: Join cells not members of a set to their own unique set ___ ___ ___ ___ ___ ___ ___ ___ | ___ ___| ___| ___| | 1 2 3 4 5 6 6 7 | Continuing to Step 3: Add Right Walls ___ ___ ___ ___ ___ ___ ___ ___ | ___ ___| ___| ___| |(1 | 2) 3 4 5 6 6 7 | <-- 1="" 2="" 3="" 4="" 5="" 6="" 7="" ___="" a="" add="" added="" and="" didn="" pre="" sets="" t="" union="" wall="">The next two cells are members of the same set, so we MUST add a wall. Failure to do so will create loops in our maze.
Step 1: Create the first row
This will just be an empty row.Step 2:Join any cells not members of a set to their own unique set
___ ___ ___ ___ ___ ___ ___ ___ | |
Step 3:Create right walls___ ___ ___ ___ ___ ___ ___ ___ | 1 2 3 4 5 6 7 8 |
Step 4:Create bottom walls.___ ___ ___ ___ ___ ___ ___ ___ |(1 2) 3 4 5 6 7 8 |If we choose not to add a wall, union the sets
___ ___ ___ ___ ___ ___ ___ ___ | 1 (1 3) 4 5 6 7 8 | ___ ___ ___ ___ ___ ___ ___ ___ | 1 1 (1 | 4) 5 6 7 8 | ... snip ... ___ ___ ___ ___ ___ ___ ___ ___ | 1 1 1 | 4 4 | 6 6 6 |
Ensure that each set has at least one cell with a down passage (i.e. without a bottom wall). Failure to do so will create an isolation.Step 5.A: Create a new row.
___ ___ ___ ___ ___ ___ ___ ___ | 1 _1_ _1_| 4 _4_| 6 6 _6_|
For each cell with a down passage on the previous row, assign the cell below to the same set.
Output the current row: ___ ___ ___ ___ ___ ___ ___ ___ | 1 _1_ _1_| 4 _4_| 6 6 _6_| <-- 1="" etc.="" line="" output="" printer="" something="" to="" u="">_1_
___ ___ ___ ___ ___ ___ ___ ___ | ___ ___| ___| ___| | 1 | 2 2 2 | 5 |(6 | 6) 7 | <-- 1="" 2="" 4:="" 5="" 6="" 7="" ___="" a="" add="" and="" bottom="" continuing="" didn="" must="" pre="" sets="" step="" t="" to="" union="" wall="" walls="">Remember: at least one cell from each set must have a down-passage (i.e. must not have a bottom wall).Step 5.B: Complete the maze___ ___ ___ ___ ___ ___ ___ ___ | ___ ___| ___| ___| | 1 | 2 _2_ _2_| 5 |_6_| 6 _6_|You can add as many rows as you'd like this way___ ___ ___ ___ ___ ___ ___ ___ | ___ ___| ___| ___| | | ___ ___| |___| ___| |_1_ 1 | 3 3 | 7 _7_ _7_| 8 |
The final row differs from a regular row in just two ways: 1) every cell has a bottom wall and 2) every cell must be a member of the same set.
Making each cell part of the same set is simple. Just remove walls between cells that are members of different sets until all the cells are part of the same set. Do not remove a wall if it separates two cells which are members of the same set.
Start by creating a normal row and add a bottom wall to each cell
___ ___ ___ ___ ___ ___ ___ ___ | ___ ___| ___| ___| | | ___ ___| |___| ___| |___ | | ___ ___| | |_1_ _1_|_3_|_3_|_7_ _7_|_8_ _8_|Complete the maze by knocking down walls between cells that are members of different sets and unioning them until all cells are part of the same set.
___ ___ ___ ___ ___ ___ ___ ___ | ___ ___| ___| ___| | | ___ ___| |___| ___| |___ | | ___ ___| | |_1_ (1_|_3)|_3_|_7_ _7_|_8_ _8_| ___ ___ ___ ___ ___ ___ ___ ___ | ___ ___| ___| ___| | | ___ ___| |___| ___| |_ _ | | ___ ___| | |_1_ _1_ _1_|(1_|_7) _7_|_8_ _8_| ___ ___ ___ ___ ___ ___ ___ ___ | ___ ___| ___| ___| | | ___ ___| |___| ___| |___ | | ___ ___| | |_1_ _1_ _1_|_1_ _1_ (1_|_8) _8_| ___ ___ ___ ___ ___ ___ ___ ___ | ___ ___| ___| ___| | | ___ ___| |___| ___| |___ | | ___ ___| | |_1_ _1_ _1_|_1_ _1_ _1_ _1_ _1_|You should now have a "perfect maze". There are no loops (ensuring only a single path exists between any two cells) and no isolations (no cell or group of cells are "blocked off" from the rest of the maze). You can assign any two cells to be the entrance and exit.
___ ___ ___ ___ ___ ___ ___ ___ | ___ ___| ___| ___| | | ___ ___| |___| ___| |___ | | ___ ___| | |___ ___ ___|___ ___ ___ ___ ___|
Example mazes
The following 15 x 15 maze was generated using this algorithm:
__ __ __ __ __ __ __ __ __ __ __ __ __ __ __ |__ |__ __ __|__ | __| | | | | |__ |__ |__| __ __| __ __ | | | | | | | |__ |__| | | | |__|__| | | __| __|__ | __|__| |__| | __| | |__ __ __| | |__| | | | | | | | |__| |__ | | __|__ __| | | | |__ __ __ __ __| | __ | | | | | | | | __| | __| | |__| | | | | | |__ | | | | | |__ __| | | |__|__|__ __| | | | | __| | |__ __| | | |__ |__| __| | __ __| | __| | __|__ |__ |__| |__ __| | | | | | |__| | __ __| __| | __| |__ __|__| __| | | | | | | __ __ | __|__| |__ | | |__| | |__ __ __|__ __|__ __ __ __ __|__|__|__ __ __|You can change the "texture" of your mazes by adding bias to your random number generator so that it becomes more or less likely that you create a right wall than a bottom wall. For example, you can make a maze with more long horizontal passages by creating right-walls less frequently and bottom-walls more frequently.
This is really easy to do. When deciding to add a wall, do something like the following: 1) generate a random number between 1 and 100. 2) if creating a right-wall, check that the resulting number is less than our bias value, if creating a bottom-wall, check than the number is greater than our bias value. In this case, a bias of 50 will create an even texture, like the sample maze above.
The following two sample mazes show how adding bias affects the resulting texture of a maze.
A very vertical maze:
__ __ __ __ __ __ __ __ __ __ __ __ __ __ __ | | | | | __| |__ | | | | | | | | |__| | __|__ | | |__ | | | | | | | | | | | | | __|__ | | | | | | | | | | | | | | | |__| | | | | | | __| | | | | | | | | | |__|__ | | | | | | |__ | | | | | | | | | | | | | | | | | | | | | |__|__| | | |__| | | | | | | |__| | | |__| | | |__ |__|__| |__|__| | | | | |__| | | __ | | | |__ | | | | __|__| |__| | | | | | | |__ __| | | |__ | | | | | | | | | | | | | | | | | | | __| | |__| | | | | | | | | | | | | | |__| |__ | | | | |__ __ __|__ __ __ __ __ __ __|__ __ __ __|__|A more horizontal maze:
__ __ __ __ __ __ __ __ __ __ __ __ __ __ __ | | __ __ __ __| __ __ __ __ __ __ __ __| | | __ __ __ __| __ __ __ __| __ | | | __ __|__ __ __ __ __ __| | |__ __ __ __ __|__ __|__ __ |__|__ |__| | __ __ __| | | |__ __ |__|__ __ __| |__ __ __ __ __ __ __ __|__ __ __ | | |__ __ __ __ __ __ |__|__ __ __ __ __ __ __| |__ __ __ __ __ __ __ __ __| __| |__ | |__ __ __|__ __ __ __|__ __ |__ __| | | | __ __ __| |__ __ __| __|__ | | __ __|__ __ __ __ __ __ __ __ | __| |__ __ |__ __ __ __ __ | __ __ __| __| |__ __ __ __ __| __|__ __ __|__ __ | | |__ __ __|__| __ __ __ __| __ __ __| |__ __ __ __ __| __| __ __| __ __| |__ __ __ __|__ __ __ __ __ __ __ __ __ __ __|
Home - Last modified: June 2012
Thursday 28 March 2013
Monday 18 March 2013
Friday 15 March 2013
Tuesday 12 March 2013
Wednesday 6 March 2013
Monday 4 March 2013
Sunday 3 March 2013
Friday 1 March 2013
Sunday 24 February 2013
Friday 22 February 2013
Thursday 21 February 2013
Wednesday 20 February 2013
Subscribe to:
Posts (Atom)