Programming

So the other night I was a bit bored and decided to do something to pass the time. I first came across Project Euler a while ago, but had never gone further than problem #1. Boredom is a great motivator and I went through problems #2 thru #9 last night and I decided to post my solutions in search of better ones. Feel free to comment with your suggestions.

Project Euler’s Problem #8 statement is —

Find the greatest product of thirteen consecutive digits in the 1000-digit number.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

A sliding window avoids multiplying the same twelve digits again for every position. Zeroes need a little care because they cannot be divided back out of the running product, so the window tracks how many it contains.

number = """\
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450
"""

digits = [int(digit) for digit in "".join(number.split())]
window_size = 13
product = 1
zeroes = 0
largest = 0

for index, digit in enumerate(digits):
    if digit == 0:
        zeroes += 1
    else:
        product *= digit

    if index >= window_size:
        outgoing = digits[index - window_size]
        if outgoing == 0:
            zeroes -= 1
        else:
            product //= outgoing

    if index >= window_size - 1 and zeroes == 0:
        largest = max(largest, product)

print(largest)

Each digit enters and leaves the product once, making this linear-time. It prints 23514624000.

So the other night I was a bit bored and decided to do something to pass the time. I first came across Project Euler a while ago, but had never gone further than problem #1. Boredom is a great motivator and I went through problems #2 thru #9 last night and I decided to post my solutions in search of better ones. Feel free to comment with your suggestions.

Project Euler’s Problem #7 statement is —

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10001st prime number?

A sieve finds all the primes up to a limit in one pass. For the nth prime, $n(\log n + \log\log n)$ is an upper bound when $n \ge 6$, so the sieve can be sized without guessing or repeatedly growing it.

from math import ceil, isqrt, log

n = 10_001
limit = ceil(n * (log(n) + log(log(n))))
sieve = bytearray(b"\x01") * (limit + 1)
sieve[:2] = b"\x00\x00"

for prime in range(2, isqrt(limit) + 1):
    if not sieve[prime]:
        continue

    start = prime * prime
    count = (limit - start) // prime + 1
    sieve[start : limit + 1 : prime] = b"\x00" * count

primes = (number for number, is_prime in enumerate(sieve) if is_prime)
for _ in range(n - 1):
    next(primes)

print(next(primes))

Multiples below prime * prime were already crossed out by smaller primes. The answer is 104743; for sieve limit $L$, it runs in $O(L\log\log L)$ time and $O(L)$ space.

I needed to pass structured measurements between two copies of a test program. Text was easy to inspect but tedious to parse, and writing a private binary format felt like volunteering to maintain archaeology.

The experimental Go library includes gob, which encodes typed values as a stream. In my current snapshot the package is imported simply as gob; its location and API may change before the language settles.

The sender is pleasantly small:

type Sample struct {
    Host  string
    Load  int
    Times []int64
}

enc := gob.NewEncoder(conn)
err := enc.Encode(Sample{"buildbox", 7, times})
if err != nil {
    return err
}

The receiver creates a decoder and supplies a destination value. Gob sends type information, then values using those types. Repeated values do not need to describe the complete structure each time, which makes a long-lived stream a better fit than many one-value connections.

Exported fields are the useful ones here. Private implementation details stay private, and fields are matched by name rather than by their physical offset in memory. That gives the decoder room to tolerate some structural evolution. It is not permission to change everything and hope.

I tried adding a field to the sender while leaving the old receiver alone. The old side ignored what it did not know. I then removed a field the receiver expected and got its zero value. That behavior is convenient for rolling experiments, provided zero has a sensible meaning.

Gob is Go-specific. I would not choose it for a public protocol consumed by C, Python, or an unknown implementation five years from now. Nor would I treat bytes emitted by today’s weekly snapshot as an archival format without tests against future toolchains.

For two cooperating Go programs built from a recorded snapshot, it removes a great deal of dull code. The mechanism is type description plus streamed values, not a dump of process memory, so pointers and machine layout are not being smuggled onto the wire. That is the right abstraction for this tool. The candid caveat is in the title: I am using it now, while keeping the protocol boundary small enough to replace later.

I have too much useful C code to pretend a new language arrives on an empty disk. My first serious Go experiment therefore needed an old image-processing library. That led directly to cgo, then to several hours learning that a foreign-function interface is a border crossing, not a transparent bridge.

The smallest call is almost suspiciously simple. In the snapshot I used, a preamble before import "C" declares the C side:

package scale

/*
#include <stdint.h>

static uint32_t clamp(uint32_t v, uint32_t limit) {
    return v < limit ? v : limit;
}
*/
import "C"

func clamp(v, limit uint32) uint32 {
    return uint32(C.clamp(C.uint32_t(v), C.uint32_t(limit)))
}

The exact generated names and build steps are tied to this weekly release. cgo is changing quickly, so this is a field note rather than a durable manual. I run cgo as part of the package build, compile its generated C, then let the normal architecture-specific tools finish the package.

Scalar conversion is the easy part. Buffers force the real questions: who owns the memory, how long does an address remain valid, and may either runtime retain it after the call? I settled on a strict rule for this experiment: Go calls C synchronously, C consumes the supplied bytes before returning, and C stores no pointer into Go-managed memory.

For output allocated by the C library, I expose a C release function and call it with defer immediately after checking the returned pointer. That keeps allocation and release in the same ownership domain. Wrapping a C allocation in a Go slice may avoid a copy, but it also makes lifetime assumptions much easier to hide. I copy unless profiling proves the copy matters.

Strings are another ownership test disguised as convenience. A Go string is not a NUL-terminated C string. Conversion may allocate. Embedded zero bytes have C semantics whether I find them philosophically agreeable or not. Passing length explicitly is better whenever the C API permits it.

Then I measured the crossing. I called a trivial C function in a loop and compared it with the same arithmetic written in Go. The absolute figures are not worth publishing because both cgo and the compiler are moving, but the shape was obvious: crossing for every pixel was disastrous; crossing once per image was lost in the actual work.

That changed my wrapper. The first version exposed the C library nearly function for function:

Go pixel loop -> cgo -> C operation -> return

The revised version sends a whole row or image:

Go request -> cgo -> C loop over image -> return

The second interface is less “complete” and much more useful. It minimizes transitions and expresses the operation at the level where ownership is clear.

Callbacks in the other direction are harder. They combine scheduler state, foreign threads, and object lifetime. I avoided them by collecting results in C and returning a batch. That is not always possible, but it is a better starting point than assuming a C callback can enter arbitrary Go code safely. The runtime is young and its constraints deserve respect, not exploratory production outages.

Failures need translation too. The C library reports integer status codes and sometimes leaves detail in a structure. My wrapper converts those into a small Go value implementing the snapshot’s os.Error convention. I do not leak C constants throughout callers. If the library returns a partial result, the wrapper states whether that result remains valid and who frees it.

The build is the least elegant part. Header search paths, linker flags, and platform differences have not vanished; they have merely moved to the package boundary. This is still better than spreading them through the program, but cgo does not make a C dependency portable by blessing it with a comment.

I keep one integration test that allocates, calls, copies, releases, and repeats. It catches ownership regressions more reliably than staring harder at the wrapper.

My conclusion is deliberately conservative. cgo is excellent for preserving a tested, substantial C implementation. It is poor as a shortcut for tiny functions that cross the boundary constantly. Design a coarse interface, keep ownership explicit, translate failures once, and benchmark the complete operation. A border can support trade. It should not run through the middle of the kitchen.

The new goinstall tool removes some Makefile work from small Go packages. Given an import path on a host it recognizes, it fetches the source, builds dependencies, and installs the package in the Go tree under GOROOT. This predates the workspace layout I keep wishing into existence.

For a package hosted on GitHub I can run:

$ goinstall github.com/rselbach/lines.git

GitHub is one of the repository hosts this version knows how to fetch, provided the repository name includes the .git suffix it expects. The import path is also the package identity: source lands below $GOROOT/src/pkg/github.com/rselbach/lines.git, and the installed archive goes into the corresponding package tree below $GOROOT/pkg. There is no GOPATH here yet.

This is early machinery. Repository conventions, supported fetch methods, command flags, and even package locations are changing between weekly snapshots. I would not encode today’s behavior into a company-wide build system without pinning the toolchain and keeping the escape hatch labeled.

It also does not solve version selection. Installing the latest source from a remote location is convenient for experiments and rather less comforting for reproducing a build six months later. For serious work I still record the exact revisions of the compiler and imported code.

Even with those caveats, goinstall saves the old fetching, directory arranging, dependency chasing, and archive copying dance. The machine can have that ritual; it will invent another soon enough.