int-e

/*
Cf. https://adventofcode.com/2021/day/11

This program looks for configurations that take long before synchronizing.

Times reflecting speedup from using SSE3:

without sse3 (g++):
real    0m54.995s

int-e

Comparison of prompt and free monads.

Summary

The prompt monad is a free monad but with a more convenient programming interface in the context of designing EDSLs. It also predates free monads as far as the Haskell community is concerned.

Context

Type names refer to the MonadPrompt and free packages on Hackage.

Usage

For Prompt, one defines an API GADT API r where each constructor takes the parameters of an API function as arguments, and specifies its result type in r.

int-e

{-# LANGUAGE MagicHash, BangPatterns #-}

module Main where

import Foreign.Ptr
import Foreign.C
import Control.Monad

foreign import ccall "wrapper" foo :: (CInt -> CInt) -> IO (FunPtr (CInt -> CInt))
foreign import ccall bar :: FunPtr (CInt -> CInt) -> CInt -> IO CInt

int-e

{-

Ragnarok puzzle, combinatorics edition:

Count Eulerian paths in

     /\/\/\/\
    /\/\/\/\/
    \/\/\/\/\
     \/\/\/\/

int-e

Update functions for May 2020 Ponder This

The challenge is about a Game of Life variant with a von Neumann neighborhood on an 11x11 toroidal grid. We need a fast update function because a starting configuration can take billions of generations before reaching a cycle.

High level approach

On the high level, we use a bit-based approach where the grid is stored in a 128 bit integer. We proceed in three stages.

1. Find neighbors. This amounts to shifting the grid in each of the four cardinal directions.
2. Count the neighbors. We do this by sorting the 4 neighbors per cell using a sorting network. This is attractive because only 5 comparators are required for a 4 bit sorting network, and each comparator can be implemented using a bit-wise and (for the lower output) and a bit-wise or (for the upper output).

int-e

-- `beforeSeq` implements `xs <* ys`
beforeSeq :: Seq a -> Seq b -> Seq a
beforeSeq xs ys = replicateEach (length ys) xs

-- a wide tree with two extra nodes to its left and right
data Wide a = Wide a (FingerTree a) a

-- replicate each element of a sequence a fixed number of times
replicateEach :: Int -> Seq a -> Seq a
replicateEach n xs

int-e

#include <cinttypes>
#include <cstdlib>
#include <iostream>

typedef uint64_t M;

// 9*5^26 overflows, so m is only guaranteed to be correct modulo 2^(D-d).
#define D (64+25)

static char trail[D];

int-e

{-# LANGUAGE RecursiveDo #-}
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE BlockArguments #-}

import Control.Monad
import Control.Monad.RWS
import Data.Monoid
import Data.List

------------------------------------------------------------------------------

int-e

-- Wagon implementation.
--
-- Wagon is a second-order concatenative language by Chris Pressey.
-- See https://esolangs.org/wiki/Wagon for further information.
--
-- Author: Bertram Felgenhauer <int-e@gmx.de>

module List where

import Data.Char

int-e

-- ghc -O2 -hide-package containers IntMapFAL.hs && ./IntMapFAL --small | tee IntMapFAL.out

{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE RankNTypes #-}

import Control.DeepSeq (rnf)
import Control.Exception (evaluate)
import Gauge (bench, bgroup, env, defaultMain, whnf)
import Data.List (foldl')
import qualified Data.IntMap as M