| Andrew Cooke | Contents | Latest | RSS | Twitter | Previous | Next


Welcome to my blog, which was once a mailing list of the same name and is still generated by mail. Please reply via the "comment" links.

Always interested in offers/projects/new ideas. Eclectic experience in fields like: numerical computing; Python web; Java enterprise; functional languages; GPGPU; SQL databases; etc. Based in Santiago, Chile; telecommute worldwide. CV; email.

Personal Projects

Lepl parser for Python.

Colorless Green.

Photography around Santiago.

SVG experiment.

Professional Portfolio

Calibration of seismometers.

Data access via web services.

Cache rewrite.

Extending OpenSSH.

C-ORM: docs, API.

Last 100 entries

M John Harrison; Playing Games on a Cloud GPU; China Gamifies Real Life; Can't Help Thinking It's Thoughtcrime; Mefi Quotes; Spray Painting Bike Frame; Weeks 10 + 11; Change: No Longer Possible To Merge Metadata; Books on Old Age; Health Tree Maps; MRA - Men's Rights Activists; Writing Good C++14; Risk Assessment - Fukushima; The Future of Advertising and Surveillance; Travelling With Betaferon; I think I know what I dislike so much about Metafilter; Weeks 8 + 9; More; Pastamore - Bad Italian in Vitacura; History Books; Iraq + The (UK) Governing Elite; Answering Some Hard Questions; Pinochet: The Dictator's Shadow; An Outsider's Guide To Julia Packages; Nobody gives a shit; Lepton Decay Irregularity; An Easier Way; Julia's BinDeps (aka How To Install Cairo); Good Example Of Good Police Work (And Anonymity Being Hard); Best Santiago Burgers; Also; Michael Emmerich (Vibrator Translator) Interview (Japanese Books); Clarice Lispector (Brazillian Writer); Books On Evolution; Looks like Ara (Modular Phone) is dead; Index - Translations From Chile; More Emotion in Chilean Wines; Week 7; Aeon Magazine (Science-ish); QM, Deutsch, Constructor Theory; Interesting Talk Transcripts; Interesting Suggestion Of Election Fraud; "Hard" Books; Articles or Papers on depolarizing the US; Textbook for "QM as complex probabilities"; SFO Get Libor Trader (14 years); Why Are There Still So Many Jobs?; Navier Stokes Incomplete; More on Benford; FBI Claimed Vandalism; Architectural Tessellation; Also: Go, Blake's 7; Delusions of Gender (book); Crypto AG DID work with NSA / GCHQ; UNUMS (Universal Number Format); MOOCs (Massive Open Online Courses); Interesting Looking Game; Euler's Theorem for Polynomials; Weeks 3-6; Reddit Comment; Differential Cryptanalysis For Dummies; Japanese Graphic Design; Books To Be Re-Read; And Today I Learned Bugs Need Clear Examples; Factoring a 67 bit prime in your head; Islamic Geometric Art; Useful Julia Backtraces from Tasks; Nothing, however, is lost with less discomfort than that which, when lost, cannot be missed; Article on Didion; Cost of Living by City; British Slavery; Derrida on Metaphor; African SciFi; Traits in Julia; Alternative Japanese Lit; Pulic Key as Address (Snow); Why Information Grows; The Blindness Of The Chilean Elite; Some Victoriagate Links; This Is Why I Left StackOverflow; New TLS Implementation; Maths for Physicists; How I Am 8; 1000 Word Philosophy; Cyberpunk Reading List; Detailed Discussion of Message Dispatch in ParserCombinator Library for Julia; FizzBuzz in Julia w Dependent Types; kokko - Design Shop in Osaka; Summary of Greece, Currently; LLVM and GPUs; See Also; Schoolgirl Groyps (Maths); Japanese Lit; Another Example - Modular Arithmetic; Music from United; Python 2 and 3 compatible alternative.; Read Agatha Christie for the Plot; A Constructive Look at TempleOS; Music Thread w Many Recommendations; Fixed Version; A Useful Julia Macro To Define Equality And Hash

© 2006-2015 Andrew Cooke (site) / post authors (content).

Hyperpublic's Challenge

From: andrew cooke <andrew@...>

Date: Fri, 25 Feb 2011 09:07:26 -0300

Since other people have posted solutions and linked to them from HN I thought
I may as well post mine.

First question is based on summing "influences" defined in a matrix.  Given
the form of the input it's simplest to construct a set of delayed functions,
one per input line.  These can then be called, and call each other to
calculate the sum.  Memoization would help, but isn't needed for such a small


# see http://hyperpublic.com/challenge/question1

from itertools import count
from sys import argv

# read test file from command line
filename = argv[1] if len(argv) > 1 else 'challenge2input.txt'

# build tree of functions that terminate in users with no influence
# scorers array allows reference to functions not yet defined
def make_scorer(line):
    def scorer(scorers):
        return sum(1 + scorers[user](scorers)
                   for (user, char) in zip(count(), line)
                   if char == 'X')
    return scorer

scorers = [make_scorer(line) for line in open(filename)]
scores = [scorer(scorers) for scorer in scorers]
print('result', ''.join(str(score) for score in scores[0:3]))

Second question involves plitting the score for a user into groups of points,
so that the minimum number of groups are used.  Apparently this is a ell known
problem called "coin change", which makes sense.  I didn't know that, but did
see that a dynamic solution is going to work (if you start with N points then
the best solution is going to be with group i if the solution with N-P(i) is
smallest; repeat...).

I am pretty sure you can write this directly as a recursive expression with
memoization, but it's easier to just build the anser from the bottom:


# see http://hyperpublic.com/challenge/question2

from operator import mul
from functools import reduce

scores = [2349, 2102, 2001, 1747]
points = [98, 42, 23, 17, 3, 2]

big = 1+max(*scores)
best = [None] * big # either None or (min number, history)

# simple dynamic solution, building from bottom up
for n in range(big):
    for p in points:
        if n == p:
            best[n] = (1, [p])
        elif n > p and best[n-p]:
            (m, h) = best[n-p]
            if not best[n] or best[n][0] > m+1:
                best[n] = (m+1, h+[p])

assert best[20] == (2, [3,17])
assert best[34] == (2, [17,17]) # not greedy

for score in scores:
    (n, history) = best[score]
    print(score, n, history)

print('result', reduce(mul, map(lambda score: best[score][0], scores)))


Comment on this post