hp
jblog
toc

Sorting w. r. t. a partial ordering

2022-09-03, post № 263

programming, #haskell, #order-theory

Task. Given a type T, a finite array v=(n,\varphi) with n\in\mathbb{N}_0 and \varphi:\{1..n\}\to T together with a finite set of pairs K\subset T^2, compute a permutation \pi\in\mathbb{S}_n such that v':=(n,\varphi\circ\pi) respects the strict partial ordering induced by K, provided K is loop-free.
Furthermore choose \pi to respect relative ordering of equal elements, that is

\forall\,i<j\in\{1..n\}:\Big(v_i=v_j\implies\pi(i)<\pi(j)\Big).

An application of late is computing the execution order of inter-dependent transformers.

Possibly due to the seeming banality of the application, my many first presumptuous attempts were both of questionable algorithmic complexity as well as failing in subtle ways, fostering bugs which only seldom showed their ugly faces. Fed up with hotfixed bypasses and manual pre-ordering, I badly longed after an implementation which indeed took some time to get right:

Heart of my approach I will herein present is computing a total ordering on all order-participating values L:=\bigcup\{\{x,y\};(x,y)\in K\} that is compatible with K and thus an apt choice for a sorting key to attain \pi by arbitrary extension to v.
For this consider the digraph D:=(L,K) and inductively deconstruct it to form a K-conforming array (\#L,\varphi_L:\{1..\#L\}\to L). Care must be taken, however, to correctly position elements left of a node of minimal degree three as e. g. greedily seeking chains may disregard local element relations. As such, iteratively pluck an arbitrarily chosen minimal element, laying these out from left to right via \varphi_L. Their minimality ensures that no element can contradict K going down.
When using a stable sorting algorithm which sorts under \varphi_L, relative ordering is naturally respected as desired.

I wrote quadratic implementation in Haskell that only stipulates Eq a: sort-via.hs. To achieve the complexity typically sought after for sorting tasks, I suspect an underlying total order on the elements is required for data management. Avoiding Haskell’s non-ADT containers and disappointing standard library support for random number generation, I wrote a C++ implementation and test suite testing both: sort-via.cpp, Makefile.

Decoupled fizzbuzz

2022-08-06, post № 262

programming, #haskell, #vim

Cogniscent of the baggage associated with this timeless kids-game-turned-into-interview-question, sparing its hiring efficacy and undeniable tedium when implemented again and again in yet another C imitation, I believe that the lack of its demise is in parts due to it being just shy of trivial with regards to all three pillars of imperative computing (control flow, i/o and data).
Contrasting a functional pearl — which is a dazzling S-Expression found out there in conceptual cosmos —, I want to describe fizzbuzz as an imperative nut: effortlessly consumable when bought already cracked and put into a bag on a store shelf, yet unexpectedly hard to crack into two clean halves by oneself. I feel its implementation often beckoning me, enticing me with forthcoming elegance, only to turn around and show its ugly face of cumbersomely construed i/o calls and disconcertingly intertwined execution paths.

Following an over-engineered approach in Haskell utilizing overlapping instances to not discriminate against index or periodicity (decoupled-fizzbuzz_overlapping-instances.hs), I chose to try the other extreme of thinking about both streams of different origins and only splicing them appropriately (decoupled-fizzbuzz_decoupled.hs). To further decrease apparent coupling, I finally hid the branching away inside a sort (decoupled-fizzbuzz_decoupled-ifless.hs):

main = mapM_ putStrLn . take 100
    $ zipWith3 (\n s z -> head . reverse . sort $ [show n, s ++ z])
               [1..] (cycle ["","","fizz"]) (cycle ["","","","","buzz"])

Fascinatingly, the often seen approach of leeching periodicity of off the indices’ arithmetic properties has vanished completely to the point of having two mutually oblivious data streams being merged based on their intrinsic willingness to provide non-empty data.

Thus born was the basis for a vim implementation of fizzbuzz. Not a vimscript implementation — which would presumably not bring anything new to the table — but in non-branching, linearily typed vim keystrokes (decoupled-fizzbuzz_decoupled.vim):

i1<Esc> qiyyp<C-A>q98@i
qfkAfizz<Esc>kkq32@f qb4jAbuzz<Esc>jq19@b
:%s/^\d*\ze[fb]<Enter>

It is not yet clear to me how to transform arbitrary branching decisions into decoupled blind text manipulation tasks, where every branch has somehow become an effect of a textual arbiter introduced for a niche action. However, I currently entertain hopes of coaxing vim-y edits into a scripting language more attuned to editing tasks and with less translational friction than traditional tools including regexp+ and fully-fledged Turing complete programs can offer. The Kolmogorov problem of fizzbuzz is in my view a convincing demonstration of the presence of untapped potential in this domain.

The Great GitHub Escape

2022-07-09, post № 261

version-control, freedom, #git, #proprietary, #seeking-refuge

As so many naturally grown things, my tiny corner of the IT space I inhabit is, too, a local state. A maximum of sorts, it is a snapshot in time of my path meandering this young, unexplored constructed world. Steps are often taken on a whim and thus not pondered on for long, the juicy sign on button all too elusive.

When I first signed on to the then independant Octocat service, it was with little care nor need: my fellow students flocked there out of habit, yet to convincing them of an alternative there was no barrier errected: our project a clean slate, and our university offering a Git server indeed. Now, nigh four years later, my public projects released and shared, the feline bought by one Big Brother and me having taken on a job centered around a repository hosted yonder, a fence has risen.
For long I dreamt escaping, yet where to? Another bloated webby clone with all the same deceptive ties just in a different coat of paint? No; Git’s bible [1] rightfully proclaims in its fourth chapter this proper unixy task’s ease, yet assumes a healthy management of keys; focussing on one sole project — not managing a few dozens. Coupled with the aformentioned trapping ties, leaving stayed mere a distant dream for months.

Yet dreams come true when acted upon and action ought to be sparked. It was a fortnight past when I first read Drew DeVault’s GitHub Copilot and open source laundering [2], a text which threw me into an action frenzy: I could no longer bear to take a part in this monopolistic pile of vigilantes, not bear to help their efforts further. Though sprinting off is only half the story: all my repositories now seeking refuge, the question where to grew louder.

With revitalized spirits, one needn’t fret: I coded up a thin SSH-Git authentication layer together with a Dumb HTTP Git protocol layer for public projects around a thousand lines of Go strong. It is called gruau and publicly served by itself [3], free for anyone to use or inspect and try to break into.

I was pleasently surprised what profound impact the reclaiming of my Git repositories had on my connection with my data. I will surely try to never open a new repository on any of the lock-in services out there again. On the technical side, I found my own shallow plumbing solution to be around twice as fast when it comes to small exchanges which are most likely dominated by handshake overhead. Aside from the moralistic reasons, this increase in remote Git snappiness alone would make me take on this journey again.

I wholeheartedly thank Drew DeVault for sparking the cinder.

One is invited to interpret my account of seeking refuge as a call to action. Yet, a shallow glance of introspection later, I sincerly do not aim to deflect anyone’s life’s trajectory. As such, this post should be understood as an outlet for my wretched digital encounters.

Status quo

2022-06-11, post № 260

poetry, #nonfree, #digitalism

Jealousy — a vicious might,
yet aimlessly benign.
A sheet, of sorts, to masquerade
the unknown — touched in parts.
Relentlessly, though glossily,
evading contra thought.
And if remarked upon it buckles
for those who see it through
a lens already worked to capture
its sheen of irresistible serenity.
One a lone one wanting out,
a place of cobbled past transcriptions.
‘But where to then?’ the aching soul exclaims,
dreading present future’s glance.
‘Untangle me; do not let madness fetch its reign!’
it echoes — ownerlessly — to itself.

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 \pi^{3\to2}_{\bullet\bullet\circ}(\left]-\varepsilon,\varepsilon\right[\ \cap\ \mathrm{graph}\,f) 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.jpg
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 \infty\times n-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

Extra assets: tche-inefficient.hs
Jonathan Frech's blog; built 2024/05/27 06:43:58 CEST