Measly Mazes

I wanted to create a maze generator for quite some while now and recently picked up the project again, using a naive approach consisting of applying a randomized depth-first search algorithm on a given rectangle. Thus, the resulting maze’s internal path structure is quite shallow, with most path forks having one degenerated short section.
Nevertheless, mazes are generated:

jt maze --ppm 32 32 | convert - -sample 1000% maze.png

You can generate your own mazes either by building maze.c natively or by using my newly developed package manager jt.

Sudoku Generation

Over two years ago, I wrote a basic 3×3-sudoku solver which uses both fundamental rule-based elimination and guessing to arrive at the solution. Revisiting the topic of computer-aided sudoku manipulation, I wrote a generalized sudoku generator (sudoku.hs).

    | 4  
  3 |    
---------
  2 | 1  
  4 |    

./sudoku 5 2

Continue reading

Pi Day MMXVII

Every year on March the 14th, for one day the world gets irrationally excited about the famous constant \pi. As is tradition, you try to calculate \pi in unusual ways, demonstrating the constant’s ubiquity as it crops up in the most unexpected circumstances.

                        lnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn       
                    nJ$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$w       
                 `v$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$        
                n$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$z        
               u$$mnn:       Y$$$i        .@$$$$$,                    
              $$n           )$$$*         W$$$$$m                     
             -n[            $$$$.        ]$$$$$$                      
                           h$$$w         $$$$$$Y                      
                          [$$$$         X$$$$$$                       
                         "$$$$n        '$$$$$${                       
                        .$$$$$         8$$$$$$                        
                        *$$$$}        :$$$$$$+                        
                       #$$$$u         $$$$$$%                         
                     t$$$$$$         ;$$$$$$`                         
                    u$$$$$$!         $$$$$$W                          
                   Y$$$$$$M         .$$$$$$,                          
                 f$$$$$$$$.         Z$$$$$Z          nn               
               `w$$$$$$$$|          $$$$$$(         v$z               
              n$$$$$$$$$W           $$$$$$$1      'X$8                
             Y$$$$$$$$$$            *$$$$$$$8nnnn$$$p                 
             $$$$$$$$$@.             W$$$$$$$$$$$$$n                  
             _$$$$$$${                x$$$$$$$$$0>                    
                -n{.                     !|nt_.                       

A fairly well-known way to approximate pi is to randomly choose points in a square (often thought of as throwing darts at a square piece of cardboard), determine their distance to a circle’s center and do a division, as I did in my π Generator post.

However, \pi does not only appear in the formula for a circle’s area, A=\pi \cdot r^2, yet also in the formula for a sphere’s volume, V=\frac{4}{3} \cdot \pi \cdot r^3, and for all the infinite hyperspheres above dimension three (view this Wikipedia article for more about volumes of higher-dimensional spheres).

In particular, the formula for the hypervolume of a hypersphere in four dimensions is defined as being V=\frac{\pi^2}{2} \cdot r^4. Using this formula, my Python script randomly chooses four-dimensional points (each in the interval \left[0, 1\right)), calculates their distance to the point \left(0.5, 0.5, 0.5, 0.5\right) and determines if they are in the hypersphere around that point with radius 0.5.
By dividing the number of random points which lie in the hypersphere by the number of iterations used (10^6 in the example below), the script approximates the hypersphere’s hypervolume. By then rearranging the equation V=\frac{\pi^2}{2} \cdot r^4 with r=0.5 to \pi=\sqrt{V\cdot 32}, the desired constant can be approximated.

$ python pi.py
3.14196371717

# Python 2.7.7 Code
# Jonathan Frech, 13th of March 2017

Continue reading