 (This is a snapshot of my old weblog. New posts and selected republished essays can be found at raganwald.com.)

Wednesday, May 02, 2007

Information wants to be free

—One of the lessons from The Media Lab: Inventing the Future at M. I. T. by Stuart Brand

Here’s a programming challenge:

Write a program that produces 128 specific bits of output. In the simplest case, output those 128 bits in a standard numeric form such as sixteen pairs of hexadecimal digits. Your program may not contain the 128 bits in literal form, it must manufacture them in some way.  Why settle for third- and fourth- hand explanations and retelling of the most important work ever conducted in Computer Science and Cryptography? The Essential Turing presents Alan Turing’s original writings, lectures, and correspondence on the subjects of Computability, Logic, Philosophy, Artificial Intelligence, and Artificial Life (his last work), in an easily readable form.

Furthermore:
• Novelty counts. Try to think of a really unique way to generate the bits.

Imagine you are determined to protect our freedom to program. Once the Monopolistic Overloards detect that a particular program produces illegal codes, they will send cease-and-desist letters to anyone distributing that program. Therefore, the greater good is served by collecting many different ways to generate the 128 bits of information.

Or if you prefer a less weighty objective, imagine this is a job interview question. If the interviewers have seen your solution before, you won’t stand out from the crowd.

• You may express the 128 bits of output in any other form you like, however more complex or obscure formulations—such as steganographic images—should be accompanied by a method or program to recover the output into numeric form.

• Oh yes, the bits. Your program must produce 00001001 11111001 00010001 00000010 10011101 01110100 11100011 01011011 11011000 01000001 01010110 11000101 01100011 01010110 10001000 11000000, or any equivalent representation such as 09 F9 11 02 9D 74 E3 5B D8 41 56 C5 63 56 88 C0, as its output.

Come on folks, we’re programmers. We probably blew millions of person-hours writing programs that counted from one to one hundred. Let’s stand up and prove that when the chips are down, we can invest a few minutes and write something that’s both interesting to code and meaningful.

What’s the smallest program that produces the 128 bits? Can it be done in pure lambda calculus? Is there a self-modifying program that turns itself into the 128 bits? Can it be done with an Enterprisey Servive-Oriented Architecture? Haskell? C#? Let’s really do this right!!

Follow-up: Quality.

Comments on “The 128-bit programming challenge:
PHP:

foreach(array(9,6,10,8,0,15,2,7,4,10,13,10,5,2,6,2,11,12,13,4,1,6,9,1,13,2,1,2,0,4,4,0) as \$y) {
print(dechex(\$x %= 16));
\$x += \$y;
}

My submission:
http://pastie.textmate.org/58276

It's in the spirit, if not the letter of what you describe. The first time you run it, it encrypts a string, given a password. Thereafter it's simply a program for decrypting whatever it originally encrypted.

(regrettably it needs the crypt gem to run, so it isn't as self-contained as I'd like)

/* replace ? with angle brackets */
#include ?stdio.h?

int main
(
void
)
{
int returnStatus = 0;

int data[] = {+9, +240, -232, -15, +155, -41, +111, -136, +125, -151, +21, +111, -98, -13, +50, +56 };

int sum = 0;

int z;
for (z = 0; z < sizeof(data) / sizeof(int); z++)
{
sum += data[z];

printf("%02X ", sum);
}

printf("\n");

return returnStatus;
}

Cool stuff folks, keep 'em coming!

FWIW, I'm currently daydreaming about a byte-code interpreter where the supplied string is a Quine.

Of course, we can't supply the program as is, but we can compile a program in a higher-level language down to the Quine.

When you see that I need an interpreter AND a compiler, we understand why I fear to start this program :-)

messing with python and primes

hex(int(str(2*2*3*11046899)+str(2*2*2*2*3*3*3*3*11*11*31*181)+str(5*10203773)+str(2*2*2*7*911*17669)+str(2*2*2*2*2*2*2*5)))

I wrote a flex program that takes written text, adds up the value of the letters in each word, discarding the words past the 16th, xors those values against a mask, and then prints out the resulting text in hexadecimal format.

A certain very important paragraph of text is nicely translated into the 128 bits you desire.

Application here: http://www.undefined.com/Hexr.swf

Source code:
http://www.undefined.com/Hexr.mxml

Sample text might be found at: http://www.law.cornell.edu/constitution/constitution.billofrights.html

Sorry, it ate my sample text url:
http://www.law.cornell.edu/constitution/constitution.billofrights.html

hmm formatting on this blog is a touch narrow, will try again.

hex(int(str(2*2*3*11046899)+
str(2*2*2*2*3*3*3*3*11*11*31*181)+
str(5*10203773)+
str(2*2*2*7*911*17669)+
str(2*2*2*2*2*2*2*5)))

Someone write a program that uses 68 74 74 70 3a 2f 2f 72 69 61 61 2e 63 6f 6d 2f as a master key and then deliver some cease-and-desist letters.

And find out what strings give the incriminated sequence as md5 checksum. 'DRM sucks' doesn't. :-(

http://pastie.textmate.org/58306
but output is dependent on compiler/platform

#!/usr/bin/bfi
++++++++++
[>++++++++++>+++++>+++>+<<<<-]
>>--.
+++++++++.
>++.
<<++.
>.
>.
<--------.
.
>.
<-.
++.
>.
<+++++++.
<--.
>>.
<--.
---.
>.
<<+.
>-.
>.
<++.
<---.
>>.
<<++.
>+++.
>.
<----.
---.
>.
<++++.
+.
>.
<<-.
>-.
>.
<+.
---.
>.
<++.
+.
>.
<++.
.
>.
<<.
>--------.

That should do it. Interpreter.

Alex

Here's a Perl version http://www.urth.org/~autarch/hex.

I'd post it here but the formatting would be horked.

It's not exactly safe. Have fun.

Here's my contribution in Python (it does need the latest version: 2.5). I even managed to avoid using any indentation so it will show up correctly as a comment (not an easy feat in Python!).

import re

primality_regex = re.compile(r"^1?\$|^(11+?)\1+\$")
is_prime = (lambda n: primality_regex.match(n * '1') == None)

(primes, i) = ([], [])
while len(primes) < 256: i.append((primes.append(len(i)) if is_prime(len(i)) else None))

innocent_data = [29, 1583, 61, 5, 929, 643, 1439, 479, 1327, 317, 449, 1213, 541, 449, 773, 1171]
for d in innocent_data: print hex(primes.index(d)),

The innocent data is a list of prime numbers. The program looks at the prime number given, determines which prime it is (0th, 1st, 2nd, etc) and outputs that number in hex. For example, 29 is the 9th prime number (if you consider 2 to be the 0th) and so the program outputs a hex 9.

print(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF * rand());

print(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF * rand());

I'm sure that works for a suitable implementation of rand.

Another possibility is that it eventually works, much like the million monkeys and million typewriters!

void code()
{
__asm__(
"stc\n"
"stc\n"
"popf\n"
"test %bl,%ah\n"
"pop %ebx\n"
"lds 86(%ebx),%esp\n"
"mov %dh,(%eax)"
);
}

int main()
{
int i;
unsigned char *c=(unsigned char *)code+3;
for (i=0;i<16;i++,c++)
printf("%02x%c",(i%5)?*c:(*c^0xf0),(i-15)?' ':'\n');
}

Of course, it only works on x86.

s = true
b = [4,1,2,6,2,1,3,1,3,1,6,1,1,1,2,3,1,1,1,3,1,1,2,3,3,2,1,1,1,2,1,4,1,2,4,1,
5,1,1,1,1,1,1,2,1,2,3,1,1,1,1,2,3,2,1,1,1,1,1,2,1,1,3,1,3,2,6]

i = b.inject("") { |r, c| s = !s; s ? r + "1" * c : r + "0" * c }
(0..(i.length/8)-1).each { |x| print i[(x * 8)..((x * 8) + 7)].to_i(2).to_s(16).rjust(2, "0") + " "}
puts

public class Generator {
/*
* Start with zero for steps bits,
* then 1 for steps bits etc. If the number
* is negative, switch bits for abs(number) steps.
*/
public static void main(String[] args) {
boolean key[] = new boolean;

int[] steps =
{4, -1, 2, 6, 2, -1, 3, -1, 3, -1, 6, -3, 2,
3, -3, 3,-2, 2, 3, 3, 2, -3, 2, -1, 4,
-1, 2, 4, -1, 5, -6, 2, -1, 2, 3, -4, 2,
3, 2, -5, 2, -2, 3, -1, 3, 2};

int counter = 0;
boolean current = false;
for (int i = 0; i < steps.length; i++) {
int repeats = steps[i];
if (repeats > 0 && current == true) {
for (int j = 0; j < repeats; j++) {
key[counter++] = current;
}
current = false;
} else if (repeats > 0) {
counter += repeats;
current = true;
} else {
while (repeats++ < 0) {
key[counter++] = current;
current = !current;
}
}

}

//output
String out = new String();
for (int i = 0; i < key.length; i++) {
out += key[i] ? '1' : '0';

//easier on the eyes
if ((i+1) % 8 == 0) {
out += ' ';
}
if ((i+1) % 64 == 0) {
out += "\n";
}
}
System.out.println(out);
}

}

Obscurity counts! Here's a Haskell version that encodes the sequence as the coefficients of a polynomial that gives special values on inputs -1, 0, 1, 2:

import Text.Printf

polynomial :: [Integer] -> Integer -> Integer
polynomial coeffs x = sum . zipWith (*) coeffs . map (x^) \$ [0..]

cs = [15850099746,11842663369,-4463664333,-1460134528]
f = flip div 6 . polynomial cs
hex = [-1..2] >>= printf "%08x" . f

main = putStrLn hex

(format t "~2,'0x"
(reduce #'(lambda (m n)
(format t "~2,'0x " m)
(+ m n))
'(#x09  #xF0  #x-E8 #x-0F
#x9B  #x-29 #x6F  #x-88
#x7D  #x-97 #x15  #x6F
#x-62 #x-0D #x32  #x38)))

I've got a good one, it takes input to produce the correct output, so the data isn't actually in the program itself. However, the input is common knowledge:
first, split the 128 bit string into 2 chunks.

09F911029D74E35B and D84156C5635688C0

Then derive questions from it, like a text adventure. Like so:

718624318471595000's factors are 2 2 2 5 5 5 5 101 3373 421885103
15582831591453800000's factors are 2 2 2 2 2 2 5 5 5 5 5 163 3229 148033747

Maybe the big numbers can be embedded in the program, but the smaller numbers can be a series of questions like "number of eyes a human has", "number of digits a human has", "numeric value of the first class to be tought in university".

Really, it's just a form of steganorgraphy.

In any case, I find it not interesting enough to write up such a program.

rot13:

09 S9 11 02 9Q 74 R3 5O Q8 41 56 P5 63 56 88 P0

I win.

I'm certain there's a better way to do this in Scheme, but here's my 15 minute attempt:

(define bits 6231311211111232111132121111115142141211123321131113211161313126214)

(define (decode-bits bits)
(define (decode-bits-onoff bits on)
(cond
((= bits 0))
((= (modulo bits 10) 0) (decode-bits-onoff (/ bits 10) (abs (- on 1))))
(else
(print on)
(decode-bits-onoff (- bits 1) on))))
(decode-bits-onoff bits 0))

(decode-bits bits)

Oooo, I really like the run-length encoding idea. A rough equivalent, in Haskell:

runs = [4,1,2,6,2,1,3,1,3,1,6,1,1,1,2,3,1,1,1,3,1,1,2,3,3,2,1,1,1,2,1,4,1,2,4,1,5,1,1,1,1,1,1,2,1,2,3,1,1,1,1,2,3,2,1,1,1,1,1,2,1,1,3,1,3,2,6]
bits = concat . zipWith replicate runs . cycle \$ [0,1]
main = putStrLn (bits >>= show)

Someone already used assembly for this, but here's my shot with pure asm. Have fun figuring out, why this works ;)

;; print128.asm
;;
;; compile with:
;; yasm -f elf -m amd64 print128.asm -o print128.o
;; ld print128.o --omagic -o print128
;;
;; Public domain. No warranty given. Works for me...
;; Platform: Linux on amd64

BITS 64
global _start
section .text

_start:
mov ecx, 16
mov rdx, London
.pants movzx eax, byte [rdx]
shr eax, 4
and eax, 0x0f
cmp ecx, 5
je .briefs
.undies call on_me
movzx eax, byte [rdx]
and eax, 0x0f
call on_me
mov eax, 0x20
call suzie
inc rdx
dec ecx
jnz .pants
mov eax, 10
mov eax, 60
xor edi,edi
syscall
.briefs times 2 dec eax
jmp .undies

some times 22 db 0x90

London or ecx,edi
popf
jz some
pop rbx
in eax, 0x63
push rsi
.al_al mov al,al

on_me mov ebx, 7
xor edi, edi
cmp eax, 10
cmovge edi, ebx
suzie push rcx
push rdx
mov [some], ax
xor eax, eax
inc eax
mov edi, eax
mov rsi, some
mov edx, eax
syscall
pop rdx
pop rcx
ret

Okay, this isn't very clever, but it makes up for it in simplicity:

"0C 88 65 36 5C 65 14 8D B5 3E 47 D9 20 11 9F 90".reverse()

damn, Anonymous already beat me to it, here's my fully assembly version:

section .text
global _start
_start:
mov ecx,10h
mov ebp,hex
mov edx,buffer
mov ebx,h
lp: movzx eax,byte [ebp]
mov ah,al
and al,0fh
xlat
mov [edx+1],al
shr ax,12
xlat
mov [edx],al
mov [edx+2],byte 20h
inc ebp
loop lp
mov [edx],byte 0ah
mov ecx,buffer
mov eax,4
lp2: xor ebx,ebx
inc ebx
mov edx,16*3+1
int 80h
mov eax,1
mov ebx,0
int 80h
hex: or ecx,edi
popfd
jz lp2
pop ebx
lds esp,[ebx+56h]
mov al,al
h db '0123456789abcdef'
section .bss
buffer resb 16*3+1

Under 32bit linux:
\$ nasm -f elf hex.asm
\$ ld hex.o

the resulting stripped program is exactly 512 bytes

Poetry is better than programming...

http://thunderfist-podium.blogspot.com/2007/05/ode-to-drm.html

;; Print a list of numbers which are *close to* the ilicit bits. This
;; is an approximate method, and will never guarantee precise values
;; for all the bits. However, if you round the numbers (code not
;; given, please don't sue me), you will almost certainly get the
;; right values.
;;
;; This is based on the traditional method of getting around a
;; competing patent or copyright: tweak what you're copying just
;; enough that it does not infringe on the intellectual property in
;; question. If this were to suddenly become invalid, it would be a
;; huge change in precedent.
;;
;; I'm not going to lie to you: this program could be
;; reverse-engineered by someone properly determined and
;; intelligent. However, the AACSLA's approval of AACS decoding
;; devices which can be reverse-engineered is widely known. I fail to
;; see how this is much different. ;-)

(defun random-double-float-between (lower-bound upper-bound)
"Given a LOWER-BOUND and an UPPER-BOUND, both of which are
double-floats, return a random double-float between those
bounds."
(declare (double-float lower-bound upper-bound)
(optimize (speed 3) (safety 0) (debug 1)))
(+ lower-bound (random upper-bound)))

(defun monte-carlo-integrate (contained-in-region-p &key min-x min-y max-x max-y (iterations 1000))
"Perform Monte Carlo integration on a region contained in the
rectangle defined by MIN-X, MIN-Y, MAX-X, and MAX-Y. The
function CONTAINED-IN-REGION-P should take x and y coordinates
and return true iff the point given lies in the region. This is
an approximate procedure and will run ITERATIONS times."
(declare (double-float min-x min-y max-x max-y)
(function contained-in-region-p)
(type (integer 0) iterations)
(optimize (speed 3) (safety 0) (debug 1)))
(let ((hits 0d0)
(misses 0d0))
(loop repeat iterations
do (let ((x (random-double-float-between min-x max-x))
(y (random-double-float-between min-y max-y)))
(if (funcall contained-in-region-p x y)
(incf hits 1d0)
(incf misses 1d0))))
;; At this point, we know roughly how much of the rectangle's area
;; lies inside the region. Let's compute the region's area:
(* (* (- max-x min-x)
(- max-y min-y))
(/ hits (+ hits misses)))))

(defun make-triangle-region (a)
"A triangle defined by x > 0, y > 0, y < a*x, where a is a
convenient constant. The first two conditions can be assumed,
since the driver code will confine itself to a reasonable
region."
#'(lambda (x y)
(< y (* a x))))

(defun approximate-key (&optional (iterations 3000000))
"Return an approximation of some illicit bits, as a list of double-floats."
(let ((region-defining-slopes '(1.0204081632653062d-4 0.0028231292517006804d0 1.927437641723356d-4
2.2675736961451248d-5 0.001780045351473923d0 0.0013151927437641724d0
0.0025736961451247164d0 0.0010317460317460319d0 0.0024489795918367346d0
7.369614512471656d-4 9.750566893424037d-4 0.0022335600907029476d0
0.0011224489795918367d0 9.750566893424037d-4 0.0015419501133786847d0
0.0021768707482993197d0)))
(mapcar #'(lambda (slope)
(monte-carlo-integrate (make-triangle-region slope)
:min-x 0d0
:min-y 0d0
:max-x 420d0
:max-y 1.2d0
:iterations iterations))
region-defining-slopes)))

from md5 import md5

words = """
greedy censoring maniacs deceivers cretins hypocritical maniacal
senseless unwanted meaningless lucrative barbarians shady lucrative
corrupted psychopathic
""".split()

print " ".join([md5(word).hexdigest()[:2] for word in words]).upper()

The same rle compression, but different seed and in scheme to obscure.

(define (generate)
(define init '(11 -2 240 -232 -15 155 -41 111 -136 125 -151 21 111 -98 -13 50 56))
(define (iter list prev)
(if (eq? list '())
'()
(let ((x (+ (car list) prev)))
(append (cons x '()) (iter (cdr list) x)))))
(iter (cdr init) (car init)))

(generate)

# in Io, http://www.iolanguage.com/

s1 := Sequence clone
list(93,145,116,34,172,70,219,118,186,40,34,229,19,36,231,167) foreach(n, s1 append(n))
s1 bitwiseXor("The 128-bit programming challenge") foreach(n, write(n, ","))

We can do it with two numbers.

One is an integer, I.

One is a transcendental number, T.

Take any transcendental number (pi, e, ln(any rational number not 1), etc) and define T, the full expansion of its binary digits.

Then find I, the place in the expansion where the 128-bit number in question first occurs.

program then becomes, in Haskell:

take 128 (drop I T)

...I think...

I cut my assembly version down even further, eliminating the hex table. It's here

It's formatted better there too.

So here is a C program I wrote which prints the parity of the count of the non-whitespace characters on each line of a text file.

http://malsyned.net/lineparity.c.txt

The real fun comes when you run it on its own source code.

doesn't count as the bits are there:

map(lambda x: int((13256278887989457651018865901401704640 & (0xFF << x)) >> x), range(120,-1,-8))

Shame on you guys! No Bash script solution so far. Here is one that use rot13 ;)

#!/bin/bash

wget http://www.rot13.com/index.php?text=09%20S9%2011%2002%209Q%2074%20R3%205O%20Q8%2041%2056%20P5%2063%2056%2088%20P0
cat index.php\@text\=09\ S9\ 11\ 02\ 9Q\ 74\ R3\ 5O\ Q8\ 41\ 56\ P5\ 63\ 56\ 88\ P0 | grep textarea | sed s/\<[^\<]*\>//g

wget -O- http://weblog.raganwald.com/2007/05/128-bit-programming-challenge.html |grep "such as" | sed "s/.*such as //g" | sed "s/, as.*//g" | sed "s/<code>//g" | sed "s/<\/code>//g"

This python script modifies itself every time it's run, it'll start printing the right answer after it's run 6 times

import sys, re
l = [64,5,19,12043,216493,836256503069278983442067L, 0]
print '0'+hex(sum(l))[2:-1]
open(sys.argv,'w').write(re.sub(r'\[.*7L, 0\]',str([l*l]+l[2:]),t))

http://pastebin.ca/468181

that brainfuck submission just rocks.

"you patented ------? drat!"

All these people writing all this code... that know how that code works.

Wouldn't the true form for this project be and endless supply of programs that print the number you want, but nobody has any idea how?

I'm thinking some form of genetically-evolved bytecode with fitness based on 1. Closeness to the right output (major weighting) 2. Cyclomatic complexity 3. Source code DOESN'T contain fragments of the output.

New idea:

A program to generate programs which output the 128 bits. Each generated program would be different from all previous ones.

Take any number of random 128 bit numbers, and xor all of them with the original. Store all of them and the result, just don't store the original. The original will be the result of xoring these together.

The 128 bits will be in the original program-generating program, but the random strings can be generated without repetition, therefore each generated program will be completely original.

This way we can have as many programs that generate the answer as we like. Everyone can have a different one!

Here is my submission. Sort of obfuscated Javascript; it could be said to paint the bits on. Bonus: although it contains a block of data (not the verboten bits, a different set of floats) it would work equally well with an infinitely large set of other blocks, so it's Google-proof.

This post has been removed by the author.

My Ruby one-liner:

http://pastie.caboo.se/58465

I think it's better to just ask Microsoft on the matter.

Here's my TCL version. Sorry for the long line length! You'd better write down the result after the first run of the proc, you never know what might happen to code once it's in memory ;)

package require rc4
proc innocent {} {
set ct "467EBE2B5E8383662D8D6BFB6E48A6F1E05B6B389DC4F5BF8CF7C0278C38D9BCD31EF2D1B42B8C7F160B3C6F8399FEF3A0A56C1CD21EBEF50BC0BCF7055906C114DD6B1E29F422DE1D10F5"
set keytext [lrange [split [info body innocent] \xa] 2 end]
eval [rc4::rc4 -key \$keytext [binary format H* \$ct]]
}
innocent

A certain polynomial has interesting values for x=0,1...15.

Yeah, I know it's wasteful to call pow() so many times. Eat me.

#include ?math.h?
#include ?stdio.h?

int main(void)
{
double a = {9.00000000000000000000,
-228661.18157025575055740774,
724683.57943269179668277502,
-968118.22122667043004184961,
735913.64518094679806381464,
-360093.45301621430553495884,
121087.63338343235955107957,
-29059.62251475052835303359,
5084.38570988967330777086,
-654.67652075689773027989,
61.96920291867959917909,
-4.25825901474738177654,
0.20654766581869227204,
-0.00670111913070791255,
0.00013043366442119572,
-0.00000115128173188207 };

int x;
for (x = 0; x < 16; x++)
{
double sum = 0.0;
int i;
for (i = 0; i < 16; i++)
{
sum += a[i] * pow(x, i);
}
printf("%02x ", (int)round(sum));
}
return 0;
}

x=' ';j=q='';b=0;
z = ' ;for(i=0; i+2<z.split(x). length-1; i ) {; document; j=j+j+z.split (x)[i++ +0]; j=00+j.length+ 1-1 ;j=j. toString(16 -x.length+1); document ;b+= ( (((z. split( x+q+q)[(i++) -00]. length ))) );b=b ;b=(b. toString (16))+x; 11+document. write (j+b); j="";b=0;}';
eval(z);

It's a little bit messy but it works, printing the code in formatted hex. To make it work outside the context of a webpage, you would need to declare a dummy object document with a write() function.

(replce ampersand-lt-semicolon above with less-than sign)

Here is, in Haskell, the LaGrange interpolation polynomial.

module Main (main) where

import Text.Printf
import Data.Ratio

type NType = Ratio Integer

eval :: [NType] -> NType -> NType
eval cs x = sum \$ zipWith (\ c e -> c * x ^^ e) cs [0 ..]

code =
[ (9%1)
, ((-82400361437)%360360)
, (281235315869%388080)
, ((-2930518882811389)%3027024000)
, (293753425355%399168)
, ((-64682072698547)%179625600)
, (1318210170059%10886400)
, ((-5423231598623)%186624000)
, (309964247987%60963840)
, ((-598675176131)%914457600)
, (299832497%4838400)
, ((-15297886481)%3592512000)
, (19787389%95800320)
, ((-125184413)%18681062400)
, (437347%3353011200)
, ((-1505507)%1307674368000)
]

main :: IO ()
main =
mapM_ putStr \$ fmap (\ i -> (printf "%02x" ((round (eval code i)) :: Int)) ++ " ") (take 16 [0 ..])

A simple, stupid way to generate the number in question.

Save the instructions in a file (say number.bc)
\$ bc number.bc

obase=16
ibase=16
3^2
.+F0
.-E8
.-F
.+9B
.-29
.+6F
.-88
.+7D
.-97
.+15
.+6F
.-62
.-D
.+32
.+38

I'd suspect the shortest program would be much, much slower than the ones submitted here.

I was thinking of something like this:

i = 0
while (!property(i)) ++i;

For a well chosen property of those 128 bits...

This reminds me of some of Gregory Chaitins work on Omega. http://en.wikipedia.org/wiki/Gregory_Chaitin

One way to really get this down to a small amount of code is to think of scripting languages that can do lookups and retrieve data over the Internet, to munge into the needed bits.

Here's my attempt:
#include <stdio.h>

char msg[] = "information wants to be free";
char key[] = "PMiM]mN62nB\\^PCiDLSidZ";

int main() {
int i, n = 0, bits = 0;
for (i = 0; i < 22; ++i) {
bits |= (key[i] - 48) << n;
if ((n += 6) >= 8)
printf("%02x ", msg[i*6/8] ^ (bits & 255)),
bits >>= 8, n -= 8;
}
putchar('\n');
return 0;
}

a='';for(var i=0;i<16;i++){a+=\$\$('.Post ul li code')[i].innerHTML}

Javascript: 62 cars

import Numeric;import List;main=putStrLn.('0':).(`showHex`"").sum.map(2^).scanl(-)123.map(length).filter(/=" ").group\$"aaa a a a a a aaa aaaa aaaa aaaaaaa aa aaa a a aa aa a a aa aaa a a aaaa a aa aa a aa a a a aa a aaaaa aaaaaa aa aa aa a aa a aaaa aa aa a aaaa a aa aa aa a aa aaaa aaaa a"

Yes, yes. Stupid entry. But you get a bonus flag with it for free :)
(Hint: rgb colors)

A perl one:
#!/usr/bin/perl
for (\$o=\$i=0 ; \$i<16 ; \$i++)
{
printf("%2.2X ", \$o = (\$o+hex(substr("09F018F19BD76F787D69156F9EF33238", 2*\$i, 2))) % 256) ;
}

Two simple programs in C that perform some calculations on the comments inside the code.

I (now) see that somebody else beat me to it with a parity counter.

This post has been removed by the author.

> One way to really get this down to > a small amount of code is to think > of scripting languages that can

import urllib, re
print re.findall('representation such as (.*?),',urllib.urlopen('http://weblog.raganwald.com/2007/05/128-bit-programming-challenge.html').read())

Since the hex representation of the number has become the iconic representation, I hacked on my previous solution a little bit and now have it outputting in hex.

lineparit2.c

Once again, to get it to output the requested number, simply run the program on its own source code.

Here:
0#**+!fzaa!bx!#*z=!=-z+zoaxmoxd!mabx=!xaboab*#

Of course, this is rather useless without the interpreter here:
http://pastebin.ca/470831

Neither of the parts contains anything traceable back to the original number without the other part. The interpreter can output any hexadecimal number, not necessarily even 128 bits wide. The code above is just gibberish without the knowledge about interpreter commands.

scanl1 (+) [9,240,-232,-15,155,-41,111,-136,125,-151,21,111,-98,-13,50,56]

More with less :)

This batch files doesn't exactly outputs the bits, but you can see them in your head anyway. =)

@echo off
:a
echo 0000_00_______00__000_000__000000_0__00___0__0___0_00____000___0_0__0_____0__000_0_00000__0_0_0__0___000_0__0__000___0_0_0__0__000_000___000000
echo ____1__1_11111__1____1___1_______1__1__111_1__111_1___111___11__1_11_11_11_11_____1_____1__1_1_11__11___1_1__11___11__1_1_11__1___1____11______
goto a

Lotus Notes solution here.

My php version outputs random numbers.

\$offsets=array(
0x679e,0x1b31,0xcb6,0x7a57,
0xace9,0x5b08,0x255e,0x5f33
);
srand(0x27);
for (\$i=0;\$i<8;\$i++)
{
while (\$offsets[\$i]--) rand();
\$k=rand(0,0x10000);
printf("%02x %02x ",\$k&0xff,\$k>>8);
}
printf("\n");

#!/usr/bin/python

def f1(x):
return 114.83333*x**3-925*x**2+2211.1667*x-1391.9
def f2(x):
return -66.5*x**3+1273*x**2-7992.5*x+16607

def f3(x):
return -13.666667*x**3+496*x**2-5871.3333*x+22845.1
def f4(x):
return -9.5*x**3+430.5*x**2-6440*x+31936

def tohex(x):
return '%02X'%x

key = map(f1, range(1,5)) + map(f2, range(5,9)) + map(f3, range(9,13)) + map(f4, range(13,17))

print map(tohex,map(int,key))

Here's my way; I think it's pretty clever =)
http://me22.fuphyl.org/magic.cpp

Here's the internal representation:
{0,25,1,2,38,1,1,4,31,2,2,1,1,2,40,2,1,3,7,2,
237,124,1,5,2,1,1,2,1,1,1,5,1,2,4,1,2,20,1,4,
9,1,1,1,3,4,1,8,1,18,1,2,3,1,2,1,12,1,1,1,
2,2,1,1,1,3,8,2,1,1,1,1,23,2};

( If you recognized from all those ones that it's a continued fraction, give yourself a pat on the back )

And here's a version modifies to use (64-bit mantissa) long doubles, so you can run it without gmpxx:
#include <math.h>
#include <stdio.h>

long double eval_cf(int *b, int const * const e) {
long double ret = *b++;
if ( b == e ) return ret;
return ret + 1 / eval_cf(b, e);
}

int main() {

int a[] = {0,25,1,2,38,1,1,4,31,2,2,1,1,2,40,3,4,3,17,1,
7,3,1,1,1,12,3,2,3,11,2,1,1,13};
int b[] = {0,18,1,15,1,4,1,7,1,1,4,1,2,6,2,2,3,2,5,1,
4,6,1,9,3,5,1,928,1,1,2,3,1,1,1,6,2};

unsigned long long am = eval_cf(a,a+sizeof(a)/sizeof(*a)) * pow(2.,64);
unsigned long long bm = eval_cf(b,b+sizeof(b)/sizeof(*b)) * pow(2.,64);
printf( "%016llX%016llX\n", am, bm<<4 );
return 0;
}
( or get it from http://me22.fuphyl.org/magic.c )

Here's a relevant article on the whole "provenance matters" issue in copyright:
http://ansuz.sooke.bc.ca/lawpoli/colour/2004061001.php

Someone mentioned genetic programming, here it is:

http://www.kontextfrei.de/~arnie/evolve.html

Done in perl.
Well documented, so it is really readable despite being written in perl ;-)

For the uninitiated:
Genetic programming works roughly like this:
You have a grammar that generates legal programs, in this case programs that are just expressions returning an integer. Random legal programs are generated by starting at the starting symbol (;-), and choosing rules at random. There is a maximum program size to ensure termination.
Then the program is evaluated, and assigned a fitness corresponding to how near it got to the value we want. This is done with a population of a few hundred to thousand programs. Then the programs are mutated and combined (crossover), simulating natural reproduction (with possible dna damage). Unfit programs produce less offspring, fit programs more.
After some thousand generations, the programs converge to returning the right number.

<< Home