Nine marching rectangles

2022-05-14, post № 259

graphics, #text-graphics

Rasterizing the continuous most often proves to be a delicate enterprise. Going from the unfathomable depths of the reals to a mere finite amount of toggled bits already zaps both completeness as well as dense ordering. Adding to that, the miniscule amount of pixels contemporary displays have to offer makes sharp jumps a frequent occurrence, breaking the illusion of continuity entirely.

With a queasy feeling about the meaning of continuous perception lurking in the back of my mind, at a recent Bill Frisell concert I was inspired to try myself at more organically conducive discrete productions. Layered in between a mighty bass and a whisked drum, both innately transferring their pristinely real movement for me to hear, Mr. Frisell — illuminated by slowly wafting curvy patches — tuned some knobs of digital effects and managed not to break the fake.
A fan of monospaced 2:1 text, I decided to try and imitate the patches’ feel in a more blatently discrete manner. As such, I wrote a marching-squares-based character-targeting renderer for graph slabs which uses only the symbols \._+| @^/.

       ..                .\_.                                                   
     ..                   .^\.                                                  
    ./.                     ||                                                  
    ||                      .\.                                                 
    ||                       ||                                                 
    ..                      .+|                                                 
     ..                     |@|                                                 
     .\_.                  .++.                                                 
      .^\.                .+@|                                                  
        ..._.           ._+@+.                                                  
          .^\___________+@@+.                                                   
            .^^^+@@@@@@@@@+.            .______________.                        
                .^^^^^^^^^.       ._____/^^^^^^^^^^^^^^. ._.                    
                            ._____+@@+^^.                .^...                  
                       .____+@@@@@+^^.                      ....                
                   .___+@@@@@@@@+^.                           .\.               
                .__+@@@@@@@@@+^^.                              .\.              
             .__+@@+^^^^^^^^^.                                  .\.             
          .__/^^^^^.                                             ||             
        ._/^^.                                                   ||             
      ._/^.                                                      ||             
     ./^.                                                       ./.             
   ._/.                                                        ./.              
   |+.                                                        ./.               
  ./.                                                       ....                
  ||                                                     ._...                  
  ||                                  .________________. .^.                    
  ||                               .__++^^^^^^^^^^^^^^^.                        
  ||                             ._++^^.                                        
  .\.                           .++^.                                           
   .\.                        ._/^.                                             
    .\_.                    ._/^.                                               
     .^...               ._..^.                                                 
        .. .__.     .__. .^.                                                    
           .^^.     .^^.                                                        
                                                                                
                                                                                
                                                                                
                                                                                
                                                                                

Source: nine-marching-rectangles.cpp

Brutally approaching blocky arrangements

2022-04-30, post № 258

programming, discrete-optimization, #sokoban, #brute-force, #baba, #c++

Arvi Teikari’s discrete self-referencing puzzler has fascinated with its non-formulaic take on box pushing since its early days as a contest entry in April of 2017^[1]. Whilst its vanilla level set is vast, conceptually coupled as well as thematically aligned, one cannot expect it to exhaustively cover the gargantuan space of world scenarios, even after filtration by solvability and playfulness.

As such, in line with the ever increasing shift in gaming away from the ROM-baked whollistic experiences towards providing loose game-inducing boundaries on internet-driven platforms — dually tending to the consuming player as well as the niche creator in one —, of particular note being Roblox, LittleBigPlanet, Super Mario Maker, its sequel and Dreams, it was a natural step for Teikari to open up their game to become a puzzler engine in late 2020^[2], allowing anyone to tinker with the shifting ways of their visually dissonant purely property-induced worlds.

A stumped Baba.

Seven years

2022-03-28, post № 257

anniversary, #retrospection

For approaching a third of my time on this earth, I have been blogging about my projects, my findings, my poetry, my systems. Looking back on it, reminiscing in distaste about the humble beginnings of graphically oriented slow snake scripting to dubious groking of Unix and numerics, meandering through games neither played nor parodied and taking my first swings at golfing. Dabbling in pixel painting, moving away from imprisoned evaluating. Graduating. Experiencing symbolicism, doubting the physicist’s model’s realism. Writing compilers, construeing languages, calculating Laplacians. Discovering sequences and trails of old — in thought and *ware. Hopping by the GNUs of new, making sense of the legacy that is Berners-Lee’s. Wrestling with what once was freedom. Writing a Bachelor’s thesis. Tasting concurrency, rediscovering simplicity. Loathing light in captured form. Lonely for the depths are known.

Looking back, I am unsure if it was worth it. I sometimes dream to have been born a Unix pioneer, not hindered by the mischief caused by modern datum’s drought for thought. Yet then again — romantically —, glorifying the past immensely, doubt creeps in if in all honesty, life’s discretization is after all not robbery. For should I not be content pondering what is constructed and then wondering why I am yearning for the improbable that is acceptance of the unloggable?

I detest conducted computing. I believe in free software. I think open source is an unjust blanket. I wish to seek asylum in the analogue. I am writing this on my Thinkpad X250 running proprietary WiFi drivers in an editor whose benevolent license I despise. The birds are tweeting.

Tchoukaillon hooks

2022-03-19, post № 256

mathematics, #discrete, #haskell, #functional-pearl

Ever since watching D. Knuth’s talk “Tchoukaillon numbers”^[1] in the Rutgers experimental mathematics seminar back in January of 2022, I was intrigued by the algorithm he presented to iteratively generate the Tchoukaillon arrays ꚓ⁽ⁿ⁾. Their discrete pointwise limit defines a two-dimensional permutation of the natural numbers, whereby pointwise exactly one value is attained more than once. These properties make calculating the discrete limit expressible as a lazy computation:

tcheInf i j = discreteLimit $ \n -> tche n i j

Despite the seeming simplicity of iteratively taking hooks from an -matrix, two-dimensional problems seem to require extra scrutiny when approached with a linear data model, even more so without arbitrary jumps. To not transpose too often — thereby invalidating the previous computations’ linearity — I took the approach of linearly evaluating a micro-DSL to express each finitely wide tche n as finite chunks of tcheFlat n :: [Int]:

tcheFlat 1 = [1..]
tcheFlat n = eval (cycle actions) $ tcheFlat (n-1) where
    actions = concat [[flat (n-m), grab (n-m-1,m)] | m <- [1..n-1]]

tche n i j | j <= n    = (chunksOf n $ tcheFlat n) ## i ## j
           | otherwise = -n

Of course left in the dust by the closed-form formula, D. Knuth’s table’s corner element is computationally viably accessible using this method:

*Main> tcheInf 32 32
2093

Source: tche.hs

The naïve’s shackles cannot be undone.

2022-02-19, post № 255

web, #security, #hsts

Without the intend to trivialize the world of material possessions, possibly the novelty alone makes the many quirks and unseen effects which occur in the presence of information-centric conduct hard to grasp in its entirety. Most bizarrely, the concept of ownership admits only to a loose analogy: expected algorithmic runtimes to reproduce bit patterns. Yet if these expections are broken or systems otherwise circumvented, stolen goods are merely accurately replicated hunks of data; nothing ever gets moved or removed, only copied against the origin’s will. Still, the sig­nif­i­cance is akin to theft, only securing bits requires more than not losing them.

As such, it is no wonder that a tender technology like the web took a long and winded path before reaching present-day hardened cryptographic ubiquity. But the tolls of time and progress are plentiful: from the fundamentally inextensible to the obsolete and the undying facets kept alive through compatibility shims, one of such shims being HTTP-talking sockets whose only assignment is to appeal to the client’s senses and never to talk with them again, referring to their HTTPS comrades which are in control of the sought after pages.
Yet cannot the clients remember? Should the clients even seek port 80? What does it mean to support SSL? To enforce it? Answers to these questions are given by HSTS, yet it too has morphed over the years; and a server’s adherence is not certain.

Vanishing members

2022-01-22, post № 254

programming, #c++, #template-metaprogramming

Inheritance is all about keeping material possessions in the familly. Thus, a child may access non-private parent members:

#include <iostream>
struct A { int v{5}; };
struct B : A {
    void f() { std::cout << v << std::endl; } };
int main() { B{}.f(); }

Even though v has not been declared inside struct B’s declaration, it accesses it through its inheritance ties to struct A. Feeling the need to be polymorphic with regards to the numerical representation, struct A may be changed to a struct template:

#include <iostream>
template<typename T> struct A { T v{5}; };
struct B : A<int> {
    void f() { std::cout << v << std::endl; } };
int main() { B{}.f(); }

Yet hard-baking in the numerical type for the derived struct feels overly restrictive. As such, one might want to build a templated class hierarchy:

#include <iostream>
template<typename T> struct A { T v{5}; };
template<typename T> struct B : A<T> {
    void f() { std::cout << v << std::endl; } };
int main() { B<int>{}.f(); }

What surprised me nearly two weeks ago — when a templated class hierarchy naturally arose — is that the above does not compile.

$ clang++ 2.cpp
2.cpp:4:29: error: use of undeclared identifier 'v'
    void f() { std::cout << v << std::endl; } };
                            ^
1 error generated.

Winter MMXXI

2021-12-25, post № 253

ascii-art, esolangs, #language-brainfuck, #winter, #tree

                      >                      
                     [-]                     
                    +++++                    
                   >[-]>[-                   
                  ]<<[->+>+                  
                 <<]>>[-<<+>                 
                >]<[->[-]>[-]                
               <<<[->>+>+<<<]>               
              >>[-<<<+>>>][-]>[              
             -]<<<[->>+>+<<<]>>>             
            [-<<<+>>>]<[-<->][-]>            
           [-]<<[->+>+<<]>>[-<<+>>           
          ]<<[->+<]>->[-]>[-]<<<<[-          
         >>>+>+<<<<]>>>>[-<<<<+>>>>]         
        [-]>[-]<<<[->>+>+<<<]>>>[-<<<        
       +>>>]<<[>>[-]++++++++++++++++++       
      ++++++++++++++.<<-]>[>[-]++++++++      
     ++++++++++++++++++++++++++++++++++.     
    <-]>[-]++++++++++.<<<<<]<+>[-]<[-->+<    
   ]>>[-]>[-]<<[->+>+<<]>>[-<<+>>][-]>[-]<   
  <<[->>+>+<<<]>>>[-<<<+>>>]<<[>>[-]+++++++  
 +++++++++++++++++++++++++.<<-]>[>[-]+++++++ 
+++++++++++++++++++++++++++++++++++.<-]>[-]++
                  ++++++++.                  

Try it online!

Finite Life’s long trajectories

2021-11-27, post № 252

simulation, #cellular-automata

Conway’s Game of Life is classicly played on the infinite two-state grid with only a finite number of cells lit in the starting configuration. Due to its particular rules, Turing machines can be embedded within it, making it equivalently powerful computationally. Paired with the non-existence of a uniform distribution on countably infinite discrete sets, homogenously reasoning about trajetories of all Games of Life is hindered by both an unclear enumeration and fundamental limits of computation.
More tractably, Life can be played on a discrete torus with finitely many states. Because of this global size limitation, Turing completeness is lost since only finitely many world states exist. For host architecture’s compatibility’s sake, I chose to play in an 𝟪 ⨉ 𝟪-sized toric world represented as an uint64_t; with Life’s rules implemented by bit-fiddling. C++20 kindly offers std::pop_count which, paired with bit-wise neighbourhood masks, allows for a clean rule encoding:

const int pc{std::popcount(w & neighbourhood_masks[j])};
if (pc == 3 || (w & (1ULL << j) && pc == 2))
    v |= 1ULL << j;

The corresponding masks are compile-time generated using a constexpr-evaluated lambda returning a std::array<world_t, 64>. Source: fgol-traj.cpp

With finite Life defined and implemented, the question I set out to ask can be posed:

In the finite directed graph of all states with edges representing one time step of evolution according to Life’s rules, one seeks to find world states which either take a long time to fall into a cycle or ones which lead into large cycles. In that regard, this maximum time is an indicator of the ‘entropic depth’ of this simulation.

Since the search space is too vast to be exhaustively searched, the 64 bits which make up a state are pseudo-randomly uniformly chosen and evolved. Keeping track of previously simulated initial state’s times, a record is kept. As of now, the longest trajectory length has been 401, achieved by the following starting configuration:

$ ./fgol-traj 0558cdc8400d3b35
world 0558cdc8400d3b35:
[]  []  [][]    
[][]  [][][]    
[]  [][]        
            []  
      []    [][]
[]  [][]    [][]
      [][]  []  
[]  []          

trajectory length until first self-colision: 401
periodicity: 132
first point of periodicity: 0000c0b070000000

Before this trajetory length, two states were found with a score of 375: 8e423847408ec519 and 94c0f9892ad05be8.

Yet this method only achieves lower bounds. Starting states which take longer than 300 steps to repeat already seem to be quite rare; finding the above state took multiple hours of searching. And because of this problem’s highly non-continuous nature, a rogue state could be lurking out there in the vastness of thought, waiting to be discovered by someone.