Chris Jester-Young

[Lisp] On Generalised composition

2010-10-17T16:29:40-07:00

Just for fun, I decided to make a pure define-only version, just to be slightly easier on the eyes. :-P Not really a serious entry compared to the above, but you get to see defines nested 4 deep!

## Generalised composition, define-only [scheme]
(define (compose . fns)
  (define (make-chain fn chain)
    (define (call-chain . args)
      (define (call) (apply fn args))
      (call-with-values call chain))
    call-chain)
  (reduce make-chain values fns))

[C] On argv iteration

2009-04-30T21:40:43-07:00

Your method is mostly good, but, it will fail if your argc is 0 (i.e., argv[0] is null, and other elements after it are invalid). On some operating systems (e.g., Linux), if you call execve with an empty argument array (without even the program name as the 0th argument), this will in fact cause the above-mentioned condition.

Mind you, I once sent a patch to Boost.Program_options because it didn't catch the argc == 0 case either, so I guess it's not a corner case that many people think about. :-)

int
main(int argc, char **argv)
{
    while (--argc >= 0)
        printf("%s\n", *++argv);
    return 0;
}

[Java] On Stats

2009-04-23T01:18:28-07:00

Seriously, a better solution is to make an enum type containing all the keys (HP, STR, etc), then look each attribute up using an EnumMap.

import java.util.EnumMap;
import java.util.Map;

public class Stats {
    public enum Type {
        HP, STR, MAG, SPEED, SKILL, DEF, RES, LUCK, WEIGHT, MOV;
    }

    private Map<Type, Integer> attrs = new EnumMap<Type, Integer>(Type.class);

    public int getStat(Type type) {
        if (attrs.containsKey(type))
            return attrs.get(type);
        throw new IllegalArgumentException(type);
    }

    public int getStat(String type) {
        return getStat(Type.valueOf(type.toUpperCase()));
    }
}

[Java] On Stats

2009-04-23T01:14:32-07:00

Use reflection! :-P

public int getStat(String stat) {
    try {
        Field field = Stats.class.getField(stat.toUpperCase());
        return field.getInt(this);
    } catch (NoSuchFieldException exc) {
        throw new IllegalArgumentException(exc);
    } catch (IllegalAccessException exc) {
        throw new IllegalArgumentException(exc);
    }
}

[Lisp] On Generalised composition

2009-04-22T05:07:17-07:00

zbigniew from freenode #scheme suggests that "fold" be replaced with "reduce"; this would then strip out the (redundant) "values" call at the start of the function chain. Thanks!

## Generalised composition [scheme]
(define (compose . fns)
  (define (make-chain fn chain)
    (lambda args
      (call-with-values (lambda () (apply fn args)) chain)))
  (reduce make-chain values fns))

[Lisp] Generalised composition

2009-04-22T04:24:55-07:00

Most people have worked with a simple kind of function composition: one that is essentially (lambda (f g) (lambda (x) (f (g x)))). SRFI 41 (http://srfi.schemers.org/srfi-41/srfi-41.html) describes a more general composition, that takes an arbitrary number of functions, and that allows each function to return multiple values. Here's my version of the same idea, but using "reduce" from SRFI 1 (http://srfi.schemers.org/srfi-1/srfi-1.html), which I think is much cleaner from a functional programming point of view. Feel free to refactor this to make it even more functional. :-)

(Original version used "fold"; thanks to zbigniew on freenode #scheme for suggesting to use "reduce", to remove the redundant "values" call; plus, as Riastradh points out, that makes it tail-recursive also.)

## Generalised composition [scheme]
(define (compose . fns)
  (define (make-chain fn chain)
    (lambda args
      (call-with-values (lambda () (apply fn args)) chain)))
  (reduce make-chain values fns))

[C] Writing characters to stdout at a specified rate

2008-10-28T11:32:59-07:00

See http://stackoverflow.com/questions/242697/do-stdout-output-with-specific-speed for context. The OP has asked me to post my code somewhere public so people can play with it, so here it is. :-)

My use of sleeptill is designed to get around the problem of "time slippage", where, because the time to write and do various other calculations is not necessarily trivial, using a simple constant quantity to nanosleep could cause the time to keep drifting out.

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>

int
sleeptill(const struct timespec *when)
{
    struct timespec now, diff;

    clock_gettime(CLOCK_REALTIME, &now);
    diff.tv_sec = when->tv_sec - now.tv_sec;
    diff.tv_nsec = when->tv_nsec - now.tv_nsec;
    while (diff.tv_nsec < 0) {
        diff.tv_nsec += 1000000000;
        --diff.tv_sec;
    }
    if (diff.tv_sec < 0)
        return 0;
    return nanosleep(&diff, 0);
}

int
main(int argc, char **argv)
{
    double rate = 0.0;
    char *endp;
    struct timespec start;
    double offset;

    if (argc >= 2) {
        rate = strtod(argv[1], &endp);
        if (endp == argv[1] || *endp)
            rate = 0.0;
        else
            rate = 1 / rate;

        if (!argv[2])
            argv[2] = ".";
    }

    if (!rate) {
        fprintf(stderr, "usage: %s rate [char]\n", argv[0]);
        return 1;
    }

    clock_gettime(CLOCK_REALTIME, &start);
    offset = start.tv_nsec / 1000000000.0;

    while (1) {
        struct timespec till = start;
        double frac;
        double whole;

        frac = modf(offset += rate, &whole);
        till.tv_sec += whole;
        till.tv_nsec = frac * 1000000000.0;
        sleeptill(&till);
        write(STDOUT_FILENO, argv[2], 1);
    }
}

[C] On Fastest way to get value of pi

2008-08-31T22:34:10-07:00

@evilteach: Thanks for that. My question was going for the fastest double-precision method applicable, however, your approach of going for more precision is nice too.

I noticed that your final answer has a sqrt in it. Do you have an arbitrary-precision sqrt function? Does Erlang provide one, or would you have to do an iterative approximation by hand?

I've taken the liberty of taking your code and marking it as Erlang, so that the syntax highlighting works better for it. Hope you don't mind! :-)

## evilteach's code formatted as Erlang [erlang]
%
%   A simple test program to calculate pi, using an easy, slow converging formula
%

-module(pi).
-export([main/0]).

% The formual we use
% pi^2 = 6*(1/(1^2) + 1/(2^2) + 1/(3^2) ...)




% When we reach the 0th term, we are done.
pi_engine(0, Sum) -> 
    io:format("~20w ~30.25f ~n", [0, Sum]),
    io:format("The value of Pi is about ~30.25f ~n", [math:sqrt(Sum * 6)]);

% Calculate the Nth term
pi_engine(N, Sum) when N > 0 -> 
    %io:format("~20w ~30.25f ~n", [N, Sum]),
    pi_engine(N - 1, Sum + (1 / (N * N)));

pi_engine(N, _Sum) when N < 0 ->
    io:format("A negative number of terms does not make sense~w ~n", [N]).


% provide an interface into the engine, as we must pass the sum along in order to 
% be able to accumulate the running total
pi(TermsToCalculate) -> 
    InitialValue = 0.0,
    pi_engine(TermsToCalculate, InitialValue).


main() ->
    io:format("main begins ~n", []),

    
    % Decide how many terms should be used for this run
    TermsToCalculate = 100000,
    
    % Perform the calculation, and display the result
    pi(TermsToCalculate),

    io:format("main ends ~n", []).

[Perl] Bencode decoder

2008-08-22T01:19:59-07:00

The BitTorrent .torrent file format uses Bencode, so this program allows you to unpack .torrent files into something more intelligible. Note that the hashes are in binary, so be sure to escape the output before writing it to your terminal!

## Bdecode.pm
#!/usr/bin/perl -w
package Bdecode;
use strict;
use Carp;

our %bdecode_funcs = (
    list => sub {return [bdecode_list($_[0])]},
    dict => sub {return {bdecode_list($_[0])}},
    int => sub {return 0 + $_[1]},
    string => sub {return substr ${$_[0]}, 0, $_[1], ''},
);

# on return, contains unparsed text
sub bdecode(\$) {
    my ($str) = @_;
    my $key =
        $$str =~ /^l/ ? 'list' :
        $$str =~ /^d/ ? 'dict' :
        $$str =~ /^i(0|-?[1-9]\d*)e/ ? 'int' :
        $$str =~ /^(0|[1-9]\d*):/ ? 'string' :
        undef;
    $key or croak 'invalid sequence';
    $$str =~ s///;
    return $bdecode_funcs{$key}->($str, $+);
}

sub bdecode_list($) {
    my ($str) = @_;
    my @result;
    push @result, bdecode($$str) while $$str !~ /^e/;
    $$str =~ s///;
    return @result;
}

1;
## bdecode
#!/usr/bin/perl -w0777
use strict;
use Bdecode;
use Data::Dumper;

my $input = <STDIN>;
my $obj = Bdecode::bdecode($input);
push @ARGV, '' unless @ARGV;
for my $path (@ARGV) {
    my $cur = $obj;
    for my $item (split '/', $path) {
        my ($name, @indices) = split /:/, $item;
        $name =~ s/%([[:xdigit:]]{2})/chr hex $1/eg;
        $cur = $cur->{$name} if length $name;
        $cur = $cur->[$_] for @indices;
    }
    my $dumper = new Data::Dumper([$cur], [$path]);
    print $dumper->Dump;
}

[C] Fastest way to get value of pi

2008-07-30T03:50:29-07:00

Solutions welcome in any language. :-) I'm looking for the fastest way to obtain the value of pi, as a personal challenge. More specifically I'm using ways that don't involve using #defined constants like M_PI, or hardcoding the number in.

The program below tests the various ways I know of. The inline assembly version is, in theory, the fastest option, though clearly not portable; I've included it as a baseline to compare the other versions against. In my tests, with builtins, the 4 * atan(1) version is fastest on GCC 4.2, because it auto-folds the atan(1) into a constant. With -fno-builtin specified, the atan2(0, -1) version is fastest.

Apart from testing between various compiler flags (I've compared 32-bit against 64-bit too, because the optimisations are different), I've also tried switching the order of the tests around. The atan2(0, -1) version still comes out top every time, though.

I'm keen to hear what results you have, as well as improvements to the testing process. :-)

ETA: I noticed that the inline assembly was treated as a constant and hoisted out of the loop. Thus, I've included the fldpi in a separate file, so that it gets treated like a function call. As a bonus, now the frame setup times get counted too, just like all the other function calls.

## pitimes.c
#include <math.h>
#include <stdio.h>
#include <time.h>

#define ITERS 10000000
#define TESTWITH(x) {                                                       \
    diff = 0.0;                                                             \
    time1 = clock();                                                        \
    for (i = 0; i < ITERS; ++i)                                             \
        diff += (x) - M_PI;                                                 \
    time2 = clock();                                                        \
    printf("%s\t=> %e, time => %f\n", #x, diff, diffclock(time2, time1));   \
}

static inline double
diffclock(clock_t time1, clock_t time0)
{
    return (double) (time1 - time0) / CLOCKS_PER_SEC;
}

int
main()
{
    int i;
    clock_t time1, time2;
    double diff;

    /* Warmup. The atan2 case catches GCC's atan folding (which would
     * optimise the ``4 * atan(1) - M_PI'' to a no-op), if -fno-builtin
     * is not used. */
    TESTWITH(4 * atan(1))
    TESTWITH(4 * atan2(1, 1))

#if defined(__GNUC__) && (defined(__i386__) || defined(__amd64__))
    extern double fldpi();
    TESTWITH(fldpi())
#endif

    /* Actual tests start here. */
    TESTWITH(atan2(0, -1))
    TESTWITH(acos(-1))
    TESTWITH(2 * asin(1))
    TESTWITH(4 * atan2(1, 1))
    TESTWITH(4 * atan(1))

    return 0;
}
## fldpi.c
double
fldpi()
{
    double pi;
    asm("fldpi" : "=t" (pi));
    return pi;
}
## build.sh [shell-unix-generic]
#!/bin/sh
gcc -O3 -Wall -c           -m32 -o fldpi-32.o fldpi.c
gcc -O3 -Wall -c           -m64 -o fldpi-64.o fldpi.c

gcc -O3 -Wall -ffast-math  -m32 -o pitimes1-32 pitimes.c fldpi-32.o
gcc -O3 -Wall              -m32 -o pitimes2-32 pitimes.c fldpi-32.o -lm
gcc -O3 -Wall -fno-builtin -m32 -o pitimes3-32 pitimes.c fldpi-32.o -lm
gcc -O3 -Wall -ffast-math  -m64 -o pitimes1-64 pitimes.c fldpi-64.o -lm
gcc -O3 -Wall              -m64 -o pitimes2-64 pitimes.c fldpi-64.o -lm
gcc -O3 -Wall -fno-builtin -m64 -o pitimes3-64 pitimes.c fldpi-64.o -lm

[C#] On I hate to do this, but...

2008-07-18T01:45:34-07:00

@Wolfbyte: Haha, nice. Very enterprisey, probably suitable for the next OMGWTF contest. :-P (That's http://omg.thedailywtf.com/ for the lurkers.)

[C#] On I hate to do this, but...

2008-07-16T10:20:26-07:00

Implementation in Perl. :-P

(Le sigh, some people just have no sense of humour. Marking my submission as spam? You've got to be kidding me, it's a valid FizzBuzz program after all.)

## FizzBuzz in Perl [perl]
my %fbmap = (3 => 'Fizz', 5 => 'Buzz');
my $fizzbuzz = sub {
    my $num = $_;
    join('', map {$num % $_ ? '' : $fbmap{$_}} keys %fbmap) || $num;
};

print "@{[map &$fizzbuzz, 1..100]}\n";

[PHP] On Adding seconds to a MySQL timestamp

2008-07-14T21:50:58-07:00

My fixes below are really tiny things:
1. Using a bracket expression for matching single characters, rather than using full-blown branches.
2. Using single quotes where double quotes are unnecessary.
3. Not doing case-insensitive matching where it doesn't make a difference at all.
4. Not updating $seconds, but rather passing $seconds + $_amount as an argument to mktime.
5. Spelling ``list'' correctly in the destructuring assignment. :-P

<?php
function addSecondsToTimestamp ($_timestamp, $_amount) {
    list($year, $month, $day, $hours, $minutes, $seconds) = preg_split('/[- :]/', $_timestamp);
    return date('Y-m-d H:i:s', mktime($hours, $minutes, $seconds + $_amount, $month, $day, $year));
}
?>

[C#] On Balance HTML Tags

2008-07-14T11:52:12-07:00

@Konrad: on your suggestion of using a Stack, it's impossible to iterate through the stack (looking for the opening tag) without popping all the items in between. If we _do_ find the opening tag, then yes, we do want to pop all the items in between (adding them to the discard list), but if we don't find it, we are supposed to keep the opening tag stack intact, and just place the closing tag in the discard list. RemoveAt is O(1) if the back element is being removed (see the .NET Framework reference source if you want to verify), which Corbin's code does, consistently.

WRT string searching (this is more a diversion of curiosity than anything else): I'm given to believe that there are some optimised string-searching algorithms out there. The ones I've heard of (Knuth-Morris-Pratt and Boyer-Moore) require pre-studying of the â€œneedleâ€, and thus isn't suitable for the current application. However, I've also chanced to look at a few different strstr() implementations, to see how they do their stuff:

1. Find first character of the needle in the haystack (using strchr() or equivalent), then (if found) use the result as a starting point to compare the rest of the needle (using memcmp() or equivalent). If comparison fails, advance the pointer and start again. This approach is used in: String.indexOf() in OpenJDK, strstr() in BSD libc, std::basic_string::find in {GNU libstdc++, STLport, and Microsoft's C++ library}, and (from what I can gather) String.IndexOf() in .NET Framework.

2. Find the first two characters of the needle in the haystack (using a custom-written loop), then (if found) use the result as a starting point to compare the rest of the needle (again, using a custom-written loop). This approach is used in: strstr() in Microsoft's libc, strstr() in procmail, and strstr() in GNU libc (which uses the procmail implementation).

[C#] On Balance HTML Tags

2008-07-14T10:45:58-07:00

Hats off to Corbin for an excellent implementation. I would add a few suggestions:

1. Because <li>, , and the like are put on the ignore list, people who type in â€œcorrect XHTMLâ€ with closer tags are going to get those stripped off. This is not strictly a problem, however for people writing lots of list items and/or paragraphs, this search-back through the ignore list is O(nÂ²) on the number of such closer tags. Although malicious users are going to be able to cause this O(nÂ²) case no matter what, it'd be nice for the more typical XHTML case to actually not impose that sort of performance penalty. I'll post a possible solution once I come up with one, it's just a thought I have at the moment.

2. I would suggest downcasing all the incoming tags like Jeff's version does, just to reduce the amount of case-insensitive comparisons that have to be done. If this is not done, then the ignoredtags.Contains() test has to be modified to be a case-insensitive one, too, in order for , <LI>, and the like to work correctly.

3. (This applies to Jeff's version too.) For consistency, <hr /> should get added to the no-closer-needed list.

[Bash] On store string from terminal into file w/timestamp

2008-07-08T11:36:19-07:00

Here's a one-liner (excluding the shell-bang line) for your enjoyment. :-) The main thing is the use of "$*", which joins all arguments into a single string. The use of printf means you don't have to use "echo -e", which can help readability.

#!/bin/bash
printf '%s\t%s\n' "$(date)" "$*" >> ~/progress/progress.txt

[Ruby] On Tracking error in numbers

2008-06-30T00:08:38-07:00

I don't know whether your specific problem domain can be solved using interval arithmetic, but if so, a search for "ruby interval arithmetic" came up with http://intervals.rubyforge.org/. Hope it helps. :-)

[JavaScript] On countdown timer (minutes & seconds) javascript

2008-06-29T22:23:32-07:00

@Ryan: Yes, it seems backwards to me---why would a "prototype" function refer to a specific instance of _TDisplay? Is it meant to model the singleton pattern? A not-so-singleton approach would be to assign the closure to "TDisplay.tick", not "_TDisplay.prototype.tick". (I can understand the use of "TDisplay._tick.call(TDisplay)", because the callback from "setInterval" loses the "this" reference.)

Of course, a not-so-singleton approach would also assign the "tick" property in the constructor, rather than assigning the "tick" property in "global" code. :-) Something like the code box below.

(ETA: My original version didn't take into account that the "this" reference might not be saved as part of the closure's environment. This will sort that out. Also, calling self._tick() will automatically set the "this" reference correctly, no need to use call().)

function _TDisplay() {
    var self = this;
    this.tick = function () {
        self._tick();
    };
}

[Lisp] On Group-by

2008-06-29T09:33:16-07:00

The function can be made even shorter by using the cut functionality in SRFI 26. :-)

## Even more succinct, with SRFI 1 and SRFI 26 [scheme]
(define (group-by x n)
  (unfold
    (lambda (l) (<= (length l) n))
    (cut take <> n)
    (cut drop <> n) 
    x
    list))

[Lisp] On Group-by

2008-06-25T17:36:50-07:00

Here is a demonstration of the kinds of madness one can get up to in the name of "performance". Of course, I personally prefer the shorter, simpler, and clearer code listed in my previous submission.

This implementation uses a variant of "split-at!" (returning the results as a dotted pair instead of multiple values, as well as allowing the list to be shorter than the split point). It's faster in two ways: for long lists, because there are no calls to "length"; and for large group size, because the use of "split-at!" (or variant) means only one traversal, rather than one for each of "take" and "drop". Oh, and it also mutates the incoming list, to avoid making any copies.

## This way lies madness [scheme]
(define (split-at-or-earlier! x i)
  (let 
      ((dummy (cons #f x)))
    (let loop
        ((cur dummy) (rem i))
      (if
        (or (zero? rem) (null? (cdr cur)))
        (let 
            ((tail (cdr cur)))
          (set-cdr! cur '())
          (cons (cdr dummy) tail))
        (loop (cdr cur) (- rem 1))))))

(define (group-by x n)
  (let
      ((split! 
        (lambda (l) 
          (split-at-or-earlier! l n))))
    (unfold
      (lambda (p) (null? (car p)))
      car
      (lambda (p) (split! (cdr p)))
      (split! x))))

[C#] On Sanitize HTML

2008-06-25T01:22:30-07:00

@Mike: That sounds like a good idea. However, not being a .NET person myself, I can't help but think: surely there is a way to make a reverse iterator from a collection, and be able to use the "for (Type x in foo)"-type loop. e.g., rbegin/rend in the C++ STL, or descendingIterator in the Java Collections Framework. (I've had a cursory look at the .NET Framework documentation and couldn't find anything suitable....)

[C#] On Sanitize HTML

2008-06-25T00:50:42-07:00

@Rob, @mmp1: (Re use of a DOM)

Technically, using a DOM is possible. Just not the HTML DOM. You write out a restricted DTD, containing only the elements and attributes you want (start with the XHTML DTD, and strip it down) and ask the XML processing system to validate against that. The restricted DTD can use a root tag of, say, rhtml ("restricted" HTML), and you wrap <rhtml>...</rhtml> around the string to validate. Then, strip off inappropriate URI schemes (i.e., anything but http/https for images, or http/https/ftp for links) via the DOM, write the tree back out to a string, strip off the rhtml tags, and you're done.

But, that is a lot of work. Also, it rejects any invalid input, rather than just stripping it off or escaping it, which is what Jeff was going for.

[C#] On Sanitize HTML

2008-06-25T00:41:19-07:00

@Stefan: The result of cleaning is for the version of the code Jeff last posted. It matches the first-pass regex twice: , and <. The second-pass regex accepts the , but rejects the <.

Also, there are cases where linking to images is actually quite appropriate, such as showing screenshots. Also, because not every site bans image links, you would have to guard against people putting image links on those sites that point to your webapp anyway. So, your webapp must have the kinds of defences mentioned in my earlier post, no matter what.

i.e., the server can only "automatically react" for POST requests, and only if the timestamp/hash thing checks out. (Referring to that last post, LiveJournal has even more defences than that...I will have to post a summary of it sometime, once I look at the code further.)

[Lisp] On Group-by

2008-06-23T10:59:22-07:00

Here's a very cheap answer that uses SRFI 1. :-P

About the predicate ensuring that the list has more than n elements left:

1. The "take"/"drop" functions fail if there aren't at least n elements in the list being processed. Unfortunately, all the "length" calls do not make the code particularly fast, especially if the list is long.

2. It's safe to change the (<= (length l) n) into (< (length l) n), so that the loop continues one last time when (length l) is n. However, the tail-generator code would then append an empty list, which is outside the spec. Solving it in that case would require complicating the tail generator, and I was going for simplest answer here.

I'll see if I can code up a faster version. But meanwhile, here's a very concise version. :-)

## SRFI 1-based implementation [scheme]
;; To activate SRFI 1:
;; MzScheme 372: (require (lib "1.ss" "srfi"))
;; MzScheme 4.0: (require srfi/1)
;; Guile: (use-modules (srfi srfi-1))

(define (group-by x n)
  (unfold
    (lambda (l) (<= (length l) n))
    (lambda (l) (take l n))
    (lambda (l) (drop l n))
    x
    list))

[Java] On Simple interpreter

2008-06-23T09:18:31-07:00

I don't have a code refactoring for you at the moment, however, it looks like you're trying to do your own language parsing, which is not easy to do by hand. A much easier way to do parsing is to use a parser generator, such as JavaCC (https://javacc.dev.java.net/), to make a parser for you.

Given the amount of time you have (surely) spent on it, I would suggest spending just a little more time on how to turn your language into a grammar that JavaCC can use. The JavaCC site has extensive documentation on how you can write this grammar. All the best!