Overkill III: Permutations of Overkill (Perl6)

Long-time readers remember my previous code with the Magic Box. In short, given the numbers [ 3, 4, 5, 6, 7, 8, 9, 10, 11 ] , arrange them in a 3x3 square such that every row, column and diagonal adds up to 21.

My first pass, on a very old computer, had the C version taking a second and a half, the Perl5 version taking a minute and a half, and the Perl6 version taking an hour and a half. But I no longer use that computer, and am now using a much newer one, so I took the opportunity to try again.

I have Nvidia cards in my box, so I could eventually write Overkill IV about that, but I don't have the knowledge or time right now. I did install rakudobrew and the newest version of Perl6, but otherwise, everything was unchanged.

C dropped to 0.6 seconds. Perl5 now takes 16 seconds. Perl6 now takes 10 minutes. So, the newer computer brought substantial speed gains for each, but the most dramatic is with Perl6, which tells us that the Perl6 developers have not only worked on correctness and completeness, but speed. Good for them! Good for us!

But wait! There's more!

@loltimo saw the post and suggested that I use permutations.

"What are permutations?", you ask? That's what basically happens in recursive_magic_box(), where all the possible variations are created. Given A, B and C, there are six possible orderings: ABC ACB BAC BCA CAB CBA. If I was given all possible orderings of an array, rather than (mis)handling it on my own and having to check that I got it right, would that make things faster?

As it turns out, yes. 47 seconds, rather than 10 minutes. More than 10x faster. But still, not as fast as Perl5. I now want to implement permutations for Perl5 and see if it makes that one faster.

And, it makes me feel much better about Perl6.

Code Samples Below

Hacking NTP into an Alarm Clock - Talking Through A Problem

Photo by  Douglas Heriot. Thanks.

In my life, there are very few clocks I rely on, and few of them need me to manually set them. The ones in my computers are connected to the network and use NTP to stay correct. My phone syncs to the phone network, which isn't quite as accurate as NTP, which can cause problems for flashmobs but is within tolerances for my daily life. The clocks with my cable boxes similarly connect outside of themselves to keep correct time.

There are three that I can think of that need manual maintenance: my watch, my car and my alarm clock.

My watch is an analog self-winding Seiko watch and I really don't think it is hackable. I have never really trusted in-car timepieces, so while driving, I'll check my watch or my phone. This leaves my alarm clock.

For me, I don't set the alarm, so that's almost a wash. But I might want to set it up for one. So, an alarm clock has 

• An LED display
• A speaker
• A snooze button
• Other buttons for different purposes
• Stuff to be cleared out to make room for my stuff.

It strikes me that, if there was something that could do NTP within the case, the only issue is knowing where it is, and you could use IP Location lookup (like IPLocation.net ) to figure out where you are, and determine time zones from there. That is, if all the smarts are within your alarm clock, which doesn't have to be true.

The snooze button is a switch like any other, so you could easily connect them to whatever electronics project you put together, and we're talking just a few LEDs and four seven-segment displays, so driving the display itself should be easy enough. One alarm clock hack I saw went to 24-hour time rather than learning how to drive the AM/PM light, which is fair enough.

If this ends up being an Arduino project, you could write your alarm to the speaker output yourself, but if you use an MP3 shield or go Raspberry Pi, it would be just as easy to use an audio file for your alarm. And, once you factor in the $80 for a WIFI shield vs the $10-20 or so for one that plugs into your Raspberry Pi, the Pi solution seems less and less overkill.

So, this seems like a doable thing. Is there anything I'm missing?

Look At My Pretty Pictures

The red parts of this image are a hypocycloid.
The blue parts of this image are an epicycloid.
The gap on the right side is an unsolved problem.

Perl blogger Gabor Szabo of Perl Maven asked me to show off my SVG Spirograph code, and so, here it, released as a Github Gist. I'm not quite to the point where I'm happy with it.

Years ago, as a child, I knew people with Spirographs, and I loved playing with them, making these crazy patterns with just pen, paper and geared plastic circles.

Years later, when I heard that Canvas support was being added to browsers, I developed tools in Javascript to draw these things. Nobody I knew had really any practical use for that skill, and so I kinda left it.

Until I started looking into laser cutters. Essentially, they're high-contrast printers, and they love vector graphics, using a thin red vector as an indication to cut rather than etch. So, when I saw Gabor write about the SVG module on Perl Maven, I knew what I must do.

Right now, I have three functions that generate these images, corresponding to epicycloid, hypocycloid and hypotrochoid curves, with two functions each providing the X and Y coordinates. In each, take a circle, rotate another circle around it (outside for epicycloids, inside for the others). If the point you're using is along the circumference, it's a cycloid, and if it's beyond that, it's an hypotrochoid, which, strictly speaking, could not be done with a Spirograph because the rings would get in the way. With math, Perl and SVG, this is not a problem.

SVG has the capability of drawing curves, but I assure you that the number of curves in the SVGs that created the images here are zero. If you draw lines between points, and those points are close enough, the lines look like curves, and the file sizes explode. On the other end, if you have the distance between points long enough, they are clearly lines, and it takes a large number of loops over to disguise the straight lines and get a thick curve. My code currently cycles through at 1/400ths of a degree at a time, which is fine for epicycloids and hypocycloids, but overkill for hypotrochoids.

Getting this code to handle Bézier curves and the like requires more math than I currently know, and might not actually be possible, but would certainly be good for reducing file sizes.

This is a number of  hypotrochoids stacked on top of each other,
cut into balsa wood. I love the 21st century.

The other problem my code has goes back to ensuring an end. Circles and ellipses are special cases of these things, and it is also the case that, with irrational numbers, that the thing will never complete, but instead look like a big black (or red, or blue) circle. So, we need to ensure that, eventually, it'll halt. If it goes over the same part twice, it makes the line thicker, which I don't want, but the problem is we're dealing with floating point, and 0.0000000000000000014 isn't mathematically equal to 0.0000000000000000015, but if we have several x and y coordinates in a row that are within 0.0000000000000000001 of previous pairs, we're probably looping over again. Eventually, I'll poke at that idea. As is, it loops 50,000 times, which is why the "both" image above isn't complete.

And, having an offset, to rotate these things as desired, would also be good. Code below, and also on Github.

Why I Wish I Was A Hardware Hacker

In our lab, we have a device that we call the Minus 80. We call it that because it is a freezer that is meant to store our samples at -80°C, or -112°F. For our purposes, as I understand them, this is not as much overkill as you might think, and there are people who get very concerned when it drops below, or rather, when it pops above -70°C. Drag out from the wall and point the big fan at the coils concerned. Conversations with HVAC guys are so loud you can hear them on the other side of a closed door concerned. Last summer, environmental issues surrounding this and other instruments (here meaning "not a computer") were a primary concern that affected use every day.

The unit in question has a digital readout of the current temperature, on a glowing LED mounted at about shin-height, which is not optimal if you're hoping to monitor the temperature. Which leads me to something that I am very sure I saw on the Ben Heck Show, or else on Make. An LED takes a current to light but also four signals to show the number. At least I think so; it's been over a decade since I last tried working with a breadboard. So, given the signal feeding the digital readout, we could run that into something like an Arduino, and from there through more normal means into our database, where we could do alerting should the thing get too warm when nobody is looking.

Anyone who knows me knows that I love taking data in one form and turning it into another. Web to RSS. RSS to JSON. CSV to PNG. If I can get the temperature out of the freezer — the temperature data, that is — I am sure I can do with it whatever I need to. It is that physical step that befuddles me. Yes, I have been annoyed for a good long time about the Minus 80's lack of serial or USB interface. Now, I have a sense of how to I could actually get there myself.

Not that the boss would let me take a soldering iron to his Minus 80. Which is a little more frustrating....

Overkill: Using the Awesome Power of Modern Computing to Solve Middle School Math Problems

I was helping my son with his math the other night and we hit a question called The Magic Box. You are given a 3x3 square and the digits 3,4,5,6,7,8,9,10,11, and are expected to find a way of placing them such that each row, each column, and each diagonal adds up to 21.

I'm a programmer, so my first thought was, hey, I'll make a recursive algorithm to do this. The previous question, measuring 4 quarts when you have a 3 quart measure and a 5 quart measure, was solved due to insights remembered from Die Hard With A Vengeance, so clearly, I'm not coming at these questions from the textbook.

With a little more insight, I solved it. 7 is a third of 21, and it the center of an odd-numbered sequence of numbers, so clearly, it is meant to be the center. There is only one way you can use 11 on a side, with 4 and 6, so that a center column or row will be 3 7 11. If you know that column and the 4 11 6 row, you know at least this:

.  3  .
.  7  .
4 11  6

And because you know the diagonals, you know that it'll be

8  3 10 
.  7  .
4 11  6

And you only have 5 and 9 left, and they're easy to just plug in

8  3 10
9  7  5
4 11  6

So, that's the logical way to to solve it. Clearly, order isn't important; it could be reversed on the x and y axis and still be a solution. But, once the thought of solving with a recursive algorithm came into my head, I could not leave well enough alone. So, here's a recursive program that finds all possible solutions for this problem.

Overkill II: The Quickening

Previously on /var/log/rant, I talked about using recursion to brute-force a middle-school math problem. Because I learned a little bit about using Xeon Phi co-processor (the part formerly called video cards), I thought I'd try C++. And found that, while the Perl version ran for about a minute and a half, the C++ version took about a second and a half.

I then tried a Python version, using the same workflow as with the C++. I backed off on the clever for the testing because I am not as sure about using multidimensional arrays in C++ and Python as I am in Perl. When you only code in a language about once every 15 years, you begin to forget the finer points.

Anyway. the code follows. I don't believe I'm doing a particularly stupid thing with my Perl here, but it's hard to ID particularly stupid things in languages sometimes. Here's the code, now with your USDA requirement of Node.js.

Considering Code Documentation

I was procrastinating about a work project, thinking about magnets, thinking about crushers, thinking about thermite, when I thought about my status tracker.

It goes by the name status.pl because status is already a DBus utility. I made some other decisions relating to command-line interface, moving away from a cool idea I had a few years ago that hasn't aged well. I changed it to record.pl, which isn't similarly overloaded on my system, at least, and wrote a few flags for it, mostly for overkill. I mean, at core, it's because Len Budney convinced me my scripts needed manners, especially it not doing anything when just called.

So, I wrote this. All the details are tucked in Status.pm, which I am not sharing and which needs an overhaul too. All in all, I am reasonably happy with this; If there was a useless use of sub signatures award, I think this'd be a contender, but both that and postderef are used in get_records.pl,  so it's okay. (I put no warnings because I'm running 5.26 on my desktop, but it is likely that I'll copy this to cluster machines running our 5.20 or the system 5.10 Perls, which would need the warnings.) I could and probably should go without IO::Interactive, but still.

So, my question is, beyond the user documentation that gets passed through Pod::Usage, what documentation does this program need? I'm always at a loss for examples of what is needed. In general, programmers discount documentation; most editor themes I see make comments gray and muted, which has always angered me, but looking at this (and yes, it's a slight case) I'm at a loss to decide what would be important to add.

So, what comments would you add? What do you find wanting?

(If desired, to add to this conversation, I can add the display section and the module.)

Net::Twitter Cookbook: Favorites and Followers

Favorites.

Also known as "Likes", they're an indication in Twitter that you approve of a status update. Most of the time, they're paired with retweets as signs by the audience to the author that the post is agreeable. Like digital applause.

This is all well and good, but it could be used for so much more, if you had more access and control over them.

So I did.

The first step is to collect them. There's an API to get them, and collecting them in bulk is easy. A problem is avoiding grabbing the same tweet twice.

# as before, the "boilerplate" can be found elsewhere in my blog.
use IO::Interactive qw{ interactive } ;
my $config ;
$config->{start} = 0 ;
$config->{end}   = 200 ;

for ( my $page = $config->{start}; $page <= $config->{end}; ++$page ) {
        say {interactive} qq{\tPAGE $page} ;
        my $r = $twit->favorites( { 
            page => $page ,
            count => 200 ,
            } ) ;
        last unless @$r ;

        # push @favs , @$r ;
        for my $fav (@$r) {
            if ( $config->{verbose} ) { 
                 say {interactive} handle_date( $fav->{created_at} ) 
                 }
            store_tweet( $config->{user}, $fav ) ;
            }
        sleep 60 * 3 ;    # five minutes
        }

Once I had a list of my tweets, one of the first things I did was use them to do "Follow Friday". If you know who you favorited over the last week, it's an easy thing to get a list of the usernames, count them and add them until you have reached the end of the list or 140 characters.

Then, as I started playing with APIs and wanted to write my own ones, I created an API to find ones containing a substring, like json or pizza or sleep. This way, I could begin to use a "favorite" as a bookmark.

(I won't show demo code, because I'm not happy or proud of the the code, which lives in a trailing-edge environment, and because it's more database-related than Twitter-focused.)

As an aside, I do not follow back. There are people who follow me who I have no interest in reading, and there are people I follow who care nothing about my output. In general, I treat Twitter as something between a large IRC client and an RSS reader, and I never expected nor wanted RSS feeds to track me.

But this can be a thing worth tracking, which you can do, without any storage, with the help of a list. Start with getting a list of those following you, those you follow, and the list of accounts (I almost wrote "people", but that isn't guaranteed) in your follows-me list. If they follow you and aren't in your list, add them. If they're in the list and you have started following them, take them out. If they're on the list and aren't following you, drop them. As long as you're not big-time (Twitter limits lists to 500 accounts), that should be enough to keep a Twitter list of accounts you're not following.

use List::Compare ;

    my $list = 'id num of your Twitter list';

    my $followers = $twit->followers_ids() ;
    my @followers = @{ $followers->{ids} } ;

    my $friends = $twit->friends_ids() ;
    my @friends = @{ $friends->{ids} } ;

    my @list = get_list_members( $twit, $list ) ;
    my %list = map { $_ => 1 } @list ;


    my $lc1 = List::Compare->new( \@friends,   \@followers ) ;
    my $lc2 = List::Compare->new( \@friends,   \@list ) ;
    my $lc3 = List::Compare->new( \@followers, \@list ) ;

    # if follows me and I don't follow, put in the list
    say {interactive} 'FOLLOWING ME' ;
    for my $id ( $lc1->get_complement ) {
        next if $list{$id} ;
        add_to_list( $twit, $list, $id ) ;
        }

    # if I follow, take off the list
    say {interactive} 'I FOLLOW' ;
    for my $id ( $lc2->get_intersection ) {
        drop_from_list( $twit, $list, $id ) ;
        }

    # if no longer following me, take off the list
    say {interactive} 'NOT FOLLOWING' ;
    for my $id ( $lc3->get_complement ) {
        drop_from_list( $twit, $list, $id ) ;
        }

#========= ========= ========= ========= ========= ========= =========
sub add_to_list {
    my ( $twit, $list, $id ) = @_ ;
    say STDERR qq{ADDING $id} ;
    eval { $twit->add_list_member(
            { list_id => $list, user_id => $id, } ) ; } ;
    if ($@) {
        warn $@->error ;
        }
    }

#========= ========= ========= ========= ========= ========= =========
sub drop_from_list {
    my ( $twit, $list, $id ) = @_ ;
    say STDERR qq{REMOVING $id} ;
    eval {
        $twit->delete_list_member( { list_id => $list, user_id => $id, } ) ;
        } ;
    if ($@) {
        warn $@->error ;
        }
    }

But are there any you should follow? Are there any posts in the the feed that you might "like"? What do you "like" anyway?

There's a way for us to get an idea of what you would like, which is your past likes. First, we must get, for comparison, a collection of what your Twitter feed is like normally. (I grab 200 posts an hour and store them. This looks and works exactly like my "grab favorites code", except I don't loop it.

    my $timeline = $twit->home_timeline( { count => 200 } ) ;

    for my $tweet (@$timeline) {
        my $id          = $tweet->{id} ;                          # twitter_id
        my $text        = $tweet->{text} ;                        # text
        my $created     = handle_date( $tweet->{created_at} ) ;   # created
        my $screen_name = $tweet->{user}->{screen_name} ;         # user id
        if ( $config->{verbose} ) {
            say {interactive} handle_date( $tweet->{created_at} );
            say {interactive} $text ;
            say {interactive} $created ;
            say {interactive} $screen_name ;
            say {interactive} '' ;
            }
        store_tweet( $config->{user}, $tweet ) ;
        # exit ;
        }

So, we have a body of tweets that you like, and a body of tweets that are a representative sample of what Twitter looks like to you. On to Algorithm::NaiveBayes!

use Algorithm::NaiveBayes ;
use IO::Interactive qw{ interactive } ;
use String::Tokenizer ;

my $list   = 'ID of your list';
my $nb     = train() ;
my @top    = read_list( $config, $nb , $list ) ;

say join ' ' , (scalar @top ), 'tweets' ;

for my $tweet (
    sort { $a->{analysis}->{fave} <=> $b->{analysis}->{fave} } @top ) {
    my $fav = int $tweet->{analysis}->{fave} * 100 ;
    say $tweet->{text} ;
    say $tweet->{user}->{screen_name} ;
    say $tweet->{gen_url} ;
    say $fav ;
    say '' ;
    }

exit ;

#========= ========= ========= ========= ========= ========= =========
# gets the first page of your Twitter timeline.
#
# avoids checking a tweet if it's 1) from you (you like yourself;
#   we get it) and 2) if it doesn't give enough tokens to make a
#   prediction.
sub read_list {
    my $config = shift ;
    my $nb     = shift ;
    my $list   = shift ;

    ...

    my @favorites ;
    my $timeline =     $twit->list_statuses({list_id => $list});

    for my $tweet (@$timeline) {
        my $id          = $tweet->{id} ;                          # twitter_id
        my $text        = $tweet->{text} ;                        # text
        my $created     = handle_date( $tweet->{created_at} ) ;   # created
        my $screen_name = $tweet->{user}->{screen_name} ;         # user id
        my $check       = toke( lc $text ) ;
        next if lc $screen_name eq lc $config->{user} ;
        next if !scalar keys %{ $check->{attributes} } ;
        my $r = $nb->predict( attributes => $check->{attributes} ) ;
        my $fav = int $r->{fave} * 100 ;
        next if $fav < $config->{limit} ;
        my $url = join '/', 'http:', '', 'twitter.com', $screen_name,
            'status', $id ;
        $tweet->{analysis} = $r ;
        $tweet->{gen_url}  = $url ;
        push @favorites, $tweet ;
        }

    return @favorites ;
    }

#========= ========= ========= ========= ========= ========= =========
sub train {

    my $nb = Algorithm::NaiveBayes->new( purge => 1 ) ;
    my $path = '/home/jacoby/.nb_twitter' ;

    # adapted on suggestion from Ken to

    # gets all tweets in your baseline table
    my $baseline = get_all() ;
    for my $entry (@$baseline) {
        my ( $tweet, $month, $year ) = (@$entry) ;
        my $label = join '', $year, ( sprintf '%02d', $month ) ;
        my $ham = toke(lc $tweet) ;
        next unless scalar keys %$ham ;
        $nb->add_instance(
            attributes => $ham->{attributes},
            label      => ['base'],
            ) ;
        }

    gets all tweets in your favorites table
    my $favorites = get_favorites() ;
    for my $entry (@$favorites) {
        my ( $tweet, $month, $year ) = (@$entry) ;
        my $label = join '', $year, ( sprintf '%02d', $month ) ;
        my $ham = toke(lc $tweet) ;
        next unless scalar keys %$ham ;
        $nb->add_instance(
            attributes => $ham->{attributes},
            label      => ['fave'],
            ) ;
        }

    $nb->train() ;
    return $nb ;
    }

#========= ========= ========= ========= ========= ========= =========
# tokenizes a tweet by breaking it into characters, removing URLs
# and short words
sub toke {
    my $tweet = shift ;
    my $ham ;
    my $tokenizer = String::Tokenizer->new() ;
    $tweet =~ s{https?://\S+}{}g ;
    $tokenizer->tokenize($tweet) ;

    for my $t ( $tokenizer->getTokens() ) {
        $t =~ s{\W}{}g ;
        next if length $t < 4 ;
        next if $t !~ /\D/ ;
        my @x = $tweet =~ m{($t)}gmix ;
        $ham->{attributes}{$t} = scalar @x ;
        }
    return $ham ;
    }

Honestly, String::Tokenizer is probably a bit too overkill for this, but I'll go with it for now. It might be better to get a list of the 100 or 500 most common words and exclude them from the tweets, instead of limiting by size. As is, strings like ada and sql would be excluded. But it's good for now.

We get a list of tweets including a number between 0 and 1, representing the likelihood, by Bayes, that I would like the tweet. In the end, it's turned into an integer between 0 and 100. You can also run this against your normal timeline to pull out tweets you would've liked but missed. I often do this

I run the follows_me version on occasion. So far, it is clear to me that the people I don't follow, I don't follow for a reason, and that remains valid.

If you use this and find value in it, please tell me below. Thanks and good coding.