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

C[omp]ute

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

Bicycle Wheels, Inertia, and Energy; Another Tax Fraud; Google's Borg; A Verion That Redirects To Local HTTP Server; Spanish Accents For Idiots; Aluminium Cans; Advice on Spray Painting; Female View of Online Chat From a Male; UX Reading List; S4 Subgroups - Geometric Interpretation; Fucking Email; The SQM Affair For Idiots; Using Kolmogorov Complexity; Oblique Strategies in bash; Curses Tools; Markov Chain Monte Carlo Without all the Bullshit; Email Para Matias Godoy Mercado; The Penta Affair For Idiots; Example Code To Create numpy Array in C; Good Article on Bias in Graphic Design (NYTimes); Do You Backup github?; Data Mining Books; SimpleDateFormat should be synchronized; British Words; Chinese Govt Intercepts External Web To DDOS github; Numbering Permutations; Teenage Engineering - Low Price Synths; GCHQ Can Do Whatever It Wants; Dublinesque; A Cryptographic SAT Solver; Security Challenges; Word Lists for Crosswords; 3D Printing and Speaker Design; Searchable Snowden Archive; XCode Backdoored; Derived Apps Have Malware (CIA); Rowhammer - Hacking Software Via Hardware (DRAM) Bugs; Immutable SQL Database (Kinda); Tor GPS Tracker; That PyCon Dongle Mess...; ASCII Fluid Dynamics; Brandalism; Table of Shifter, Cassette and Derailleur Compatability; Lenovo Demonstrates How Bad HTTPS Is; Telegraph Owned by HSBC; Smaptop - Sunrise (Music); Equation Group (NSA); UK Torture in NI; And - A Natural Extension To Regexps; This Is The Future Of Religion; The Shazam (Music Matching) Algorithm; Tributes To Lesbian Community From AIDS Survivors; Nice Rust Summary; List of Good Fiction Books; Constructing JSON From Postgres (Part 2); Constructing JSON From Postgres (Part 1); Postgres in Docker; Why Poor Places Are More Diverse; Smart Writing on Graceland; Satire in France; Free Speech in France; MTB Cornering - Where Should We Point Our Thrusters?; Secure Secure Shell; Java Generics over Primitives; 2014 (Charlie Brooker); How I am 7; Neural Nets Applied to Go; Programming, Business, Social Contracts; Distributed Systems for Fun and Profit; XML and Scheme; Internet Radio Stations (Curated List); Solid Data About Placebos; Half of Americans Think Climate Change Is a Sign of the Apocalypse; Saturday Surf Sessions With Juvenile Delinquents; Ssh, tty, stdout and stderr; Feathers falling in a vacuum; Santiago 30m Bike Route; Mapa de Ciclovias en Santiago; How Unreliable is UDP?; SE Santiago 20m Bike Route; Cameron's Rap; Configuring libxml with Eclipse; Reducing Combinatorial Complexity With Occam - AI; Sentidos Comunes (Chilean Online Magazine); Hilary Mantel: The Assassination of Margaret Thatcher - August 6th 1983; NSA Interceptng Gmail During Delivery; General IIR Filters; What's happening with Scala?; Interesting (But Largely Illegible) Typeface; Retiring Essentialism; Poorest in UK, Poorest in N Europe; I Want To Be A Redneck!; Reverse Racism; The Lost Art Of Nomography; IBM Data Center (Photo); Interesting Account Of Gamma Hack; The Most Interesting Audiophile In The World; How did the first world war actually end?; Ky - Restaurant Santiago; The Black Dork Lives!; The UN Requires Unaninmous Decisions; LPIR - Steganography in Practice

© 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
problem.

#!/usr/bin/python3

# 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]
scores.sort(reverse=True)
print(scores)
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:

#!/usr/bin/python3

# 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])
            break
        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)))


Andrew

Comment on this post