Thursday, August 2, 2018

Simplest Quick Sort Algorithm

A lot of quicksort implementations are hard to follow, because the indexes are shifted around slightly (+1 or -1).  Here's the most intuitive implementation I could write:



# split an array into 3 groups around an arbitrary pivot value (last element):
# [ less than pivot ... equal to pivot ... greater than or equal to pivot ]
def partition(arr, low, high):
    # consolidate any elements smaller than pivot (last element)
    i = low 
    for j in range(low, high):
        if arr[j] < arr[high]:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1 
    # drop pivot into position at middle 
    arr[i], arr[high] = arr[high], arr[i]
    return i

# main function
def quickSort(arr, low, high): 
    if low < high:
        pi = partition(arr, low, high)
        # now, resort new regions around pivot
        quickSort(arr, low, pi-1)
        quickSort(arr, pi+1, high)



Friday, February 5, 2016

Ubuntu Mate

I've been testing out Ubuntu Mate 15.10, and it may be my new favorite Linux distro for the desktop.   :-)

It's very simple and clean, and comes with various themes, such as Redmond (below), Cupertino (with a bottom dock), or Gnome (classic top/bottom panels).  It also includes a more advance menu that includes a search and favorites.





Wednesday, December 2, 2015

Edge/Collision Detection in ASCII character templates - Part 2

I experimenting with edge detection in ASCII characters, to use for manipulating text data (for example, creating mazes).

Here was Part I:  http://sevkeifert.blogspot.com/2015/11/i-wrote-that-turns-ascii-tessellation.html

Then I noticed that a lot of character patterns have implied white space, such as a pattern with pipes and underscores.  This pattern contains visual whitespace, but no actual whitespace character data:


So, here's an experiment to generalize the parser to handle cases like this.  The simplest approach I found was to add an option to  translate all characters into an exploded map of the data.  One character can translate to a block of 9 characters that represent the solid and non-solid properties of the font shape.  For example:



Then, the edge detection code works as usual, just in an exploded view of the ASCII data.


For example:

1. First transform text to exploded view
2. Parse as usual
3. Then apply an inverse transform to collapse back to normal.

The transform looks like:

Load template:

Apply Transform:


Apply pre-processing filters (sharpen edges)


Parse and apply post-processing filters


Apply inverse transform:



Then I added some code to detect the "outside" of a shape.  Also, I added pre and post image filtering rules, so loose edges like /_ can be automatically detected and closed.

Here's another example parsing implied whitespace in a template:



Parser Hints


Now, the parser can automatically detect inside/outside of closed shapes.

Also, I added a special character ~ that flags a region as closed within another shape (such as holes in the template).   The special character ` acts as non-useable whitespace.

summary:
    ~ means outside of shape
    ` means don't use whitespace

For example, to protect the closed shape of the eye, add a ~ inside of it:



Updated code at:

Python2: https://github.com/sevkeifert/text-utils/blob/master/maze-ify-ascii.py
Python3: https://github.com/sevkeifert/text-utils/blob/master/maze-ify-ascii-v3.py

Saturday, November 28, 2015

Irregular maze generator (from ASCII tessellation) - Part 1

I wanted to write a generalized ASCII maze generator which could create a unlimited variety of tessellations.  

So I first created a parser that could detect "edges" in an ASCII "image"


Then the script will knock out wall in the ASCII image to create a maze.


This can generate irregularly shaped mazes, based on the ASCII template.  

Source code is at:


Python2: https://github.com/sevkeifert/text-utils/blob/master/maze-ify-ascii.py

Python3: https://github.com/sevkeifert/text-utils/blob/master/maze-ify-ascii-v3.py




USAGE:


   maze-ify-ascii.py -f YOUR_TEMPLATE_FILE  



For example, here's a basic grid:






Grid with holes:



Oblique


Hexagonal tessellation:




Complex Features
Irregular shape, with holes, multiple regions, text, and protected whitespace



Now for Part II: parsing the space *inside* font characters:

Wednesday, November 25, 2015

Command line tool to create and parse text outlines - revisited


A while back I posted a quick script for creating text outlines on the command line (for example, in Vim).  I like keeping all my documentation as plain text.  I updated it so that it can now parse and repair outlines if you edit them.

Source code is here:

        https://github.com/sevkeifert/text-utils/blob/master/outline


Description of the `outline` utility:

This is a command line tool for creating text outlines from space-delimited
markup.  This program transforms a stream of data, either rendering markup or
decoding an already rendered outline back into markup.

                                                    Kevin Seifert - 2015 GPLv2
USAGE

    Pipe space-delimited (or space-delimited) text into this script to create a
    text outline.  For example:

        cat your_markup_file | $0

OPTIONS

    -d    decode outline
    -e    encode outline (default)
    -h    help
    -n    use numeric style: 1  1.1  1.2 ...
    -r    re-encode existing outline (repair)
    -w   set word wrap width
    -0    mix single/double space (add break after continued lines)
    -1    single space
    -2    double space

EXAMPLE USAGE

    cat yourfile | outline       # for roman numeral format
    cat yourfile | outline -n    # for decimal format
    cat yourfile | outline -d    # decode rendered outline back into markup
    cat yourfile | outline -r    # repair (re-encode) rendered outline

    Or in vim, visually select text and run selection markup through pipe

        :'<,'> ! outline
        :'<,'> ! outline -d
        :'<,'> ! outline -r

MARKUP EXAMPLE

    INPUT EXAMPLE (WHITESPACE DETERMINES LEVEL)

        some heading
            more text
                a sub point
                another sub point
            more text
                a sub point
                another sub point

    OUTPUT EXAMPLE (RENDERED INTO OUTLINE)

        I. some heading
            A. more text
                1. a sub point
                2. another sub point
            B. more text
                1. a sub point
                2. another sub point

    ALSO, YOU CAN USE DECIMAL FORMAT USING THE -n FLAG

        1. some heading
            1.1 more text
                1.1.1 a sub point
                1.1.2 another sub point
            1.2 more text
                1.2.1 a sub point
                1.2.2 another sub point

Sunday, November 22, 2015

Word Ladder Puzzle Game (and Puzzle Solver)

Here's a word ladder puzzle game (and solver) I wrote a while back. A word ladder is a string of words that change one letter at a time. For example: "cat", "cot", "dot", "dog" is a word ladder that connects "cat" and "dog". I tweaked the game to run as a standalone application (instead of a java applet). The source code is on github:

https://github.com/sevkeifert/wordladder-game-solver

The game:


The puzzle solver:






How to Increase Website Traffic


I generally haven't put a lot of time into maintaining this blog, and mostly forgot about it for a couple years.   :-)

I've never really blogged frequently, and I took a break from posting any articles around 2011 and started posting again in 2014 (was busy).  Although I noticed the vacation created an interesting sociological experiment with the overall web traffic:




Traffic is fairly steady (and gradually falls) when the site is not updated at all -- from September 2011 to August 2014.

So, basically if you want more web traffic, increase both the number of articles on your website, and the number of "new" articles.    Overall, the increase in traffic is largely correlated with adding new articles.

Also, the posts that have gotten the most traffic are about things where I spent more than an hour "Googling" for something, and couldn't find a good answer or solution.  If you can't find it, there's a vacuum in the available information and you'll end up higher in Google's search result.   Even though the topic might be only interesting to a smaller demographic, anything on these topics will get a lot of  hits from Google searches.

I also notice "fuzzy" topics may do better that pure information, as readers will discuss the topic further with others.  My most popular articles are opinion articles regarding Linux.

This information is probably commonsensical, though what I thought what was interesting, was to actually see a confirmation of SEO principles with real web statistics.  After all, who else is going to let their website languish for years, for the benefit of science?  ;-)