Implementing two Graph traversal algorithms in Python: Depth First Search and Breadth First Search

Posted on in Learning • Tagged with Programming, Learning, University

Depth First Search and Breadth First Search

I am right in front of a ton of exams and I need to learn about algorithms and data structures. When I read about pseudocode of Graph traversal algorithms, I thought:
Why not actually implement them in a real programming language? So I did so and now you can study my code now here. I guess this problem was solved a thousand times before, but I learnt something and I hope my approach has some uniqueness to it.

Additionlay, you can also generate a topological order after you traversed the whole Graph, which is a nice little extra.

If you want the most recent version of the code, you can visit its own Github repo here.

Well, here's the code. Just download and run it like this: python graph_traversal.py

# -*- coding: utf-8 -*-

__author__ = 'Nikolai Tschacher'
__version__ = '0.1'
__contact__ = 'admin@incolumitas.com'


import time
from collections import deque

"""
This is just a little representation of two basic graph traversal methods.

    - Depth-First-Search
    - Breadth-First-Search

It's by no means meant to be fast or performant. Rather it is for educational
purposes and to understand it better for myself.
"""


class Node(object):
    """Represents a node."""

    def …

Continue reading

Create your own font the hard way!

Posted on in Learning • Tagged with Captcha, Programming, Design, Glyphs, Learning, Font

Last major update on 23.10.2013

Preface

As promised previously in my last article, I will guide you through the creation process of a rudimentary font. I will use the glyphs of my font to draw captchas and incorportate the implementation in my brand new captcha plugin for wordpress. There are already quite a few captcha plugins out there, some of them are better than mine (RECAPTCHAfor instance translates books and thus solves two problems at the same time), others are worse, because the math equations can simply be parsed (As far as I can judge without inspecting the code further).

In this article however, I will center the focus entirely on the font and abstract from it's future usage in the captcha.

Technical background of fonts

A logical start of font creation is to answer the question what type of font we are going to create. But lets first introduce some concepts that are of importance when it comes to font design.

In short: A font is a collection of glyphs. Each glyph has a shape and there are various ways of describing that shape. You can imagine a glyph as a instanteation of a character. Whereas …


Continue reading

Plotting Bézier curves directly and with De Casteljau's algorithm

Posted on in Learning • Tagged with Font, Captcha, Programming, Mathematics, Learning, Bézier

Last major Update: 21.10.2013

Github repo that contains the presented code in this post.

Introduction

In this article I will present you a very simple and in no sense optimized algorithm written in Python 3 that plots quadratic and cubic Bézier curves. I'll implement several variants of Bézier rasterization algorithms. Let's call the first version the direct approach, since it computes the corresponding x and y coordinates directly by evaluation of the equation that describes such Bézier curvatures.

The other possibility is De Casteljau's algorithm, a recursive implementation. The general principle is illustrated here. But the summarize the idea very briefly: In order to compute the points of the Bézier curve, you subdivide the lines of the outer hull that are given from the n+1 control points [Where n denotes the dimension of the Bézier curve) at a ratio t (t goes from 0 to 1 in a loop). If you connect the interpolation points, you'll obtain n-1 connected lines. Then you apply the exactly same principle to these newly obtained lines as before (recursive step), until you finally get one line remaining. Consider again the point at the ratio t on this single line left and …


Continue reading

Major Redesign of incolumitas.com

Posted on in Learning • Tagged with Themeprojectsnewredesigncsshtml, Meta, Learning, Uncategorized

Hello everybody!

I finally found some motivation and time to give my blog a design upgrade - Basically an endavour that was overdue since this blog has seen the light of the day ;)

On the technical side, this theme is a complete redevelopment. It's not finished yet, on the contrary, it's the very first version and there remain a lot of issues that need to be resolved. For instance: The majority of the CSS code is still rather dirty and of experimental nature. Additionally, I want to include an image slideshow based on unslider.js. Your template function in the your theme would then look something like the following:

if ( ! function_exists( 'clearcontent_header_slider' )):
/*
 * This function includes a minimal jquery slideshow into the header of the site. It uses unslider.js in 
 * order to achieve this objective. Link to github site: https://github.com/idiot/unslider
 */
function clearcontent_header_slider() {
    ?>

    <div class="header-slideshow">
        <ul>
            <li style="background-image: url('<?php echo get_template_directory_uri() . '/pics/slideshow/1.png' ?>');"></li>
            <li style="background-image: url('<?php echo get_template_directory_uri() . '/pics/slideshow/2.png' ?>');"></li>
            <li style="background-image: url('<?php echo get_template_directory_uri() . '/pics/slideshow/3.png' ?>');"></li>
        </ul>
    </div>
    <script type="text/javascript">
        var $j = jQuery.noConflict();

        // Use jQuery via $j(...) instead …

Continue reading

Python and curses - A small textbox selection example.

Posted on in Learning • Tagged with Programming, Learning

Hey dear readership :)

What.

I recently was in a need of a handy  and nice way (not just pragmatic) to chose between different entities in the command line, each of them constituting an option. Surely, you can craft a simple menu with standard I/O functions, but I wanted to explore something different and more beautiful.

Therefore I found curses, a simple wrapper around ncurses, the famous BSD/UNIX library for portable advanced terminal handling.

So, I dived into this library, I'd recommend this tutorial for everyone who wants to deal with this old school stuff...

How.

You can check out the recent script on my github site. Here is a copy, for everyone to lazy to look it up:

import curses

# Author: Nikolai Tschacher
# Date: 02.06.2013

class BoxSelector:
    """ Originally designed for accman.py.
        Display options build from a list of strings in a (unix) terminal.
        The user can browser though the textboxes and select one with enter.
    """

    def __init__(self, L):
        """ Create a BoxSelector object. 
            L is a list of strings. Each string is used to build 
            a textbox.
        """
        self.L = L
        # Element parameters. Change them here.
        self.TEXTBOX_WIDTH = 50
        self.TEXTBOX_HEIGHT = 6

        self.PAD_WIDTH = 400
        self …

Continue reading

Another wordpress catpcha implementation

Posted on in Learning • Tagged with Programming, Learning, Security

Hey dear readership and dudelmatz :)

I'm kinda overworked and planned quite a while ago to release my own little captcha implementation to prevent this massive bulk of spam comments I receive on a daily base: It's obnoxious to scroll through this sheer amount of spam comments and delete them. You can't just masstrash them, because you might miss a legit comment and therefore you need to check every single one. I assume the spammer embrace this expected behaviour of a blogger, and therefore exploit it.

So I needed to put a stop to this violation of my spare time and I created my own captcha. Of course, I first searched for a working and already existing solution (and I am sure there are many which are better then what I came up with), but the one I used is basically crap

Its plugin description states:

Captcha plugin allows you to protect your website from spam using math logic which can be used for login, registration, reseting password, comments forms.

And yeah as I feared this simple elegant captcha is worthless, because math logic is a joke to parse and solve by computers (=>spamscripts). I was pissed and in a mood …


Continue reading