Arithmetic Golfing

A recent PCG golfing question When do I get my sandwich? asked to find a mapping between seven input strings (sandwich names) and the seven days of the week (indexed by number).

The first answer was made by a user named i cri everytim and utilized a string of characters which uniquely appear at the same position in all seven input strings, enklact, to perform the mapping in Python 2 requiring 29 bytes. After their answer, a lot of answers appeared using the same magic string in different languages to reduce the number of bytes needed. Yet nobody reduced the byte count in Python.

Trying to solve the problem on my own, my first attempt was using only the input strings’ last decimal digit to perform the mapping, though this approach did not save on bytes (read my PCG answer for more on this 30 byte solution).

After a few more hours of working on this problem, however, I achieved to bring down the byte count by one entire byte.

I did so by using a simple brute-force algorithm to check for Python expressions which can be used to perform the sought after mapping. To do so, I use Python’s apostrophes (`...`) to turn the found expression into a string — str(...) is three whole bytes longer — and index that string with the input strings’ lengths. It sure is not very readable, but only takes 28 bytes — and that is all that matters.

lambda S:`6793**164`[len(S)]

After finding the 28 byte function which uses a 9 byte expression (6793**164), I attempted to find an even shorter expression. And even though I did not yet find one, I did write a more general brute-force Python program (source code shown below; can also be downloaded) than the one I linked to in my PCG answer.

Brute-forcing takes exponentially more time the more digits you have to check, so my brute-forcer still requires the user to decide for themselves which expressions should be tried.
There are three parameters that define the search; a regex pattern that should be contained in the expression’s string, an offset that pattern should ideally have and a target length. If an expression is found that takes as many bytes as or less bytes than the target length, an exclamation point is printed.
Though this program did not prove useful in this case, there may come another challenge where an arithmetic expression golfer could come in handy.

My program may not have found shorter expressions, but definitely some impressive ones (the +... at the end refers to an additional offset from the string index which — unsurprisingly — take additional bytes):

  • 2**2**24+800415
  • 2**2**27+5226528
  • 2**7**9+11719750
  • 7954<<850

I also considered using division to generate long strings of digits which may match; the only problem is that Python floating-point numbers only have a certain precision which does not produce long enough strings. Again, using exponentiation (**) and bitshifting (<<) I could not come up with a working expression that takes less bytes.


# Python 2.7 code; 7th, 8th of September 2017

Continue reading

Advertisements

Mandelbrot Set III

I wrote my first ever Mandelbrot Set renderer back in 2015 and used Python to slowly create fractal images. Over a year later, I revisited the project with a Java version which — due to its code being actually compiled — ran much faster, yet had the same clunky interface; a rectangle the user had to draw and a key they had to press to the view change to the selected region.
In this post, over half a year later, I present my newest Mandelbrot Set fractal renderer (download the .jar), written in Java, which both runs fast and allows a much more intuitive and immersive walk through the complex plane by utilizing mouse dragging and scrolling.
The still time demanding task of rendering fractals — even in compiled languages — is split up into a low quality preview rendering, a normal quality display rendering and a high quality 4K (UHD-1 at 3840×2160 pixels to keep a 16:9 image ratio) rendering, all running in seperate threads.

Rainbow spiral
Rainbow spiral

The color schemes where also updated, apart from the usual black-and-white look there are multiple rainbow color schemes which rely on the HSB color space, zebra color schemes which use the iterations taken modulo some constant to define the color and a prime color scheme which tests if the number of iterations taken is prime.

Zebra spiral
Zebra spiral

Apart from the mouse and keyboard control, there is also a menu bar (implemented using Java’s JMenuBar) which allows for more conventional user input through a proper GUI.

Controls

  • Left mouse dragging: pan view
  • Left mouse double click: set cursor’s complex number to image center
  • Mouse scrolling: zoom view
  • Mouse scrolling +CTLR: pan view
  • ‘p’: render high definition fractal
  • ‘r’: reset view to default
  • ‘w’, ‘s’: zoom frame
  • Arrow keys: pan view
  • Arrow keys +CTRL: zoom view
  • Menu bar
    • Fractal: extra info about current fractal rendering
    • Color Scheme: change color scheme and maximum iteration depth
    • HD: controls for high definition rendering
    • Extra: help and about
Blue spiral
Blue spiral

A bit more on how the three threads are implemented.
Whenever the user changes the current view, the main program thread renders a low quality preview and immediately draws it to the screen. In the background, the normal quality thread (its pixel dimensions match the frame’s pixel dimensions) is told to start working. Once this medium quality rendering is finished, it is preferred to the low quality rendering and gets drawn on the screen.
If the user likes a particular frame, they can initiate a high quality rendering (4K UHD-1, 3840×2160 pixels) either by pressing ‘q’ or selecting HD->Render current frame. This high quality rendering obviously takes some time and a lot of processing power, so this thread is throttled by default to allow the user to further explore the fractal. Throttling can be disabled through the menu option HD->Fast rendering. There is also the option to tell the program to exit upon having finished the last queued high definition rendering (HD->Quit when done).
The high definition renderings are saved as .png files and named with their four defining constants. Zim and Zre define the image’s complex center, Zom defines the complex length above the image’s center. Clr defines the number of maximum iterations.

Another blue spiral
Another blue spiral

Just to illustrate how resource intensive fractal rendering really is.
A 4K fractal at 3840×2160 pixels with a iteration depth of 256 would in the worst case scenario (no complex numbers actually escape) require 3840 \cdot 2160 \cdot 256 \cdot 4 = 8493465600 double multiplications. If you had a super-optimized CPU which could do one double multiplication a clock tick (which current CPUs definitely cannot) and ran at 4.00 GHz, it would still take that massively overpowered machine \frac{8493465600}{4 \cdot 10^9} = 2.123 seconds. Larger images and higher maximum iterations would only increase the generated overhead.
The program’s source code is listed below and can also be downloaded (.java), though the compiled .jar can also be downloaded.

Green self-similarity
Green self-similarity

Unrelated to algorithmically generating fractal renderings, I recently found a weed which seemed to be related to the Mandelbrot Set and makes nature’s intertwined relationship with fractals blatently obvious. I call it the Mandel Weed.

Mandel Weed
Mandel Weed
// Java Code; Jonathan Frech; 22nd, 23rd, 24th, 25th, 26th, 27th of July 2017

Continue reading

Tau Day MMXVII

Today it is June the 28th which means that it is \tau day!
The irrational and transcendental constant \tau is what defines \pi = \frac{\tau}{2}, which obviously makes it an important constant. To celebrate this day, I created a C program which calculates \tau by randomly creating 9-dimensional points inside the 9-dimensional hypercube and testing if they are inside the 9-dimensional hypersphere with its center located at (0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5).

Today’s \tau time is 3:18:53 as \tau = 6.2831853 \dots. As one does not know if the time is specified as ante or post meridiem, there are actually two perfectly acceptable \tau times.

            ;b$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$b
        h$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ 
     .$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$+ 
    $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$  
  ,$$$$$$$$$kn}~I"`($$$$$$$x````````````````   
 )$$$m             $$$$$$$$                    
+$$c              q$$$$$$$>                    
$$                $$$$$$$$                     
                 $$$$$$$$.                     
                '$$$$$$$$                      
                $$$$$$$$                       
               ?$$$$$$$a                       
               $$$$$$$$                        
              Q$$$$$$$f                        
              $$$$$$$$                         
             $$$$$$$$i                         
             $$$$$$$$                          
            $$$$$$$$;                          
            $$$$$$$$                           
           J$$$$$$$w                           
           $$$$$$$$;             $$~           
           $$$$$$$$             $$$            
          '$$$$$$$$C          "$$$             
           $$$$$$$$$w       '$$$$              
           $$$$$$$$$$$$$$$$$$$$B               
            $$$$$$$$$$$$$$$$$$.                
             $$$$$$$$$$$$$$$'                  
                8$$$$$$$q                      

The formula used for calculating \tau is derived from a 9-dimensional hypersphere’s hypervolume formula V = \frac{32 \cdot \pi^4}{945} \cdot R^9 (see this Wikipedia article).
V = \frac{2^5 \cdot \tau^4 \cdot R^9}{945 \cdot 2^4} = \frac{2 \cdot R^9}{945} \cdot \tau^4
\tau^4 = \frac{V \cdot 945}{2 \cdot R^9}; R = 0.5
\tau^4 = \frac{V \cdot 945 \cdot 2^9}{2}
\tau = \sqrt[4]{V \cdot 241920}

The constant gets calculated to \tau^* = 6.293700. The real value is approximately \tau = 6.283185 \dots, which makes the percent error \left|\frac{\tau^*-\tau}{\tau}\right| = \left|\frac{6.293700-6.283185}{6.283185}\right| = 0.001673514 = 0.167\%.
Thereby this C program’s approximation is not too far off. The source code is listed below and can also be downloaded here. Instructions on how to compile it using GCC can be seen below or in the source code.

gcc tau.c -o tau -lm; ./tau
tau = 6.293700

Resources worth checking out regarding \tau are The Tau Manifesto and 2 Pi or Not 2 Pi?. I wish everybody a happy \tau day.


// C Code
// Jonathan Frech, 27th of June 2017

Continue reading