This is a post regarding the solution to a substring problem which follows a
pattern that is quite common among substring problems: it is solvable with a
pair of fast and slow iterators.

If this is not possible, we will return the empty string.

Problem Statement

Given two strings, S and T, find the minimum window in S which will contain all
the characters in T (with their frequencies) in linear time.

S

T

Answer

""

""

""

""

"A"

""

"A"

""

""

"A"

"A"

"A"

"A"

"AB"

"A"

"ADOBECODEBANC"

"ABC"

"BANC"

"ADOBECODECABANC"

"ABC"

"CAB"

C++ Solution

stringminimum_window_substring(strings,stringt){if(t.empty()){return"";}// Frequency in the token.
unordered_map<char,size_t>tf;for(charc:t){tf[c]++;}// Frequency in the string.
unordered_map<char,size_t>sf;// How many characters we have to match.
constautotarget=t.size();constauton=s.size();size_tbest_i=0;constautono_size=numeric_limits<size_t>::max();size_tbest_size=no_size;size_tslow=0;size_tfast=0;size_tmatched=0;// Advance fast until we met the target.
// Then shrink with slow until we no longer meet the conditions.
// As this advances each pointer at most N times, this is O(n).
while(slow<n&&fast<n){sf[s[fast]]++;if(sf[s[fast]]<=tf[s[fast]]){matched++;}fast++;// Here, the range is [slow, fast).
while(matched==target&&slow<fast){constsize_tmatch_size=fast-slow;if(match_size<best_size){best_i=slow;best_size=match_size;}sf[s[slow]]--;if(sf[s[slow]]<tf[s[slow]]){matched--;}slow++;}}if(best_size==no_size){return"";}returns.substr(best_i,best_size);}

This is an update on what I have recently done to Hellish Bricks.

Progression Curves

The game got progression curves for running speed and initial jump speed.

These are important so that the character evolves, creating more gameplay
possibilities as the game progresses.

Colored Lights

I’ve also enabled lantern and ambient light commands so that the player can
change the lantern and the ambient light colors during the game or during
initialization, through the boot script.

Default Boot Script

# Set lantern to a light yellow.
lantern #EEEEBB
# Set ambient to a dark red.
ambient #443322

This is the first of what may end up being a series of posts regarding the
development of my closed-source game Hellish Bricks.

The game is heavily inspired on Devil Daggers (2016), but intends to focus on
low-poly and minimalist graphics instead of retro ones.

Hellish Bricks is written using modern C++ and requires at least OpenGL 3.3 and
just about 128 MiB of free memory for now.

I intend to write better and more visually appealing shaders in the future and
start working on some fancier graphical effects, such as particles and shadows.

Gameplay Video

Playable Demo

You need at least Windows Vista to run the game and you may also need to
download and install the Microsoft Visual C++ Redistributable for Visual Studio
2017 before being able to execute the game.

Recently I had to solve a problem which asked you to determine the bitwise and
of a range of nonnegative numbers. There is an obvious linear solution to this
problem which simply computes the bitwise and of the range.

Bitwise and of [4, 10] = 4 & 5 & 6 & 7 & 8 & 9 & 10

However, after thinking about how the anding ends up “erasing” bits permanently
I figured out the following logarithmic solution:

Essentially, if you have at least two numbers in the range, the last bit will be
zero, so you can compute the bitwise and of the prefixes and append a zero to
the result (by shifting it to the left).

In this post I will present a simple and somewhat generic solution for the
sliding maximum problem.

Find the maximum element for every K consecutive elements.

Note that the sliding minimum can be seen as a negated sliding maximum problem,
just like the maximum spanning tree can be seen as the minimum spanning tree of
the negated graph.

Implementation

Below is a generic C++ sliding window I implemented that takes a comparator as a
template parameter. This allows it to be instantiated for both the sliding
maximum and the sliding minimum.

template<typenameT,typenameComparator>classSlidingWindow{structBlock{Block(Tv,size_tw):value(v),width(w){}Tvalue;size_twidth;};Comparatorcomp;deque<Block>data;public:voidpush(constTt){size_twidth=1;while(!data.empty()&&comp(data.back().value,t)){data.pop_back();width++;}data.emplace_back(t,width);}Tget()const{returndata.front().value;}voidpop(){// Either reduce the width of the best block (front), or drop it.
if(data.empty()){return;}if(data.front().width>1){data.front().width--;}else{data.pop_front();}}};

This solution is amortized O(1) for all operations, making it O(N) for N
elements. By using STL trees we cannot do better than O(N log N).

Sliding Maximum Example

Using 20 terms and a window of width 4, we have the following table: