Write the smallest possible program that can print the following paragraph (sans quotes):
"Educators, generals, dieticians, psychologists, and parents program. Armies, students, and some societies are programmed. An assault on large problems employs a succession of programs, most of which spring into existence en route. These programs are rife with issues that appear to be particular to the problem at hand. To appreciate programming as an intellectual activity in its own right you must turn to computer programming; you must read and write computer programs -- many of them. It doesn't matter much what the programs are about or what applications they serve. What does matter is how well they perform and how smoothly they fit with other programs in the creation of still greater programs. The programmer must seek both perfection of part and adequacy of collection. In this book the use of ``program'' is focused on the creation, execution, and study of programs written in a dialect of Lisp for execution on a digital computer. Using Lisp we restrict or limit not what we may program, but only the notation for our program descriptions."
The quote must be printed in verbatim. Any language may be used. Programs are rated on the size of their compiled executable form, not the lines of code. Record holder has to draw an ASCII medal for whoever surpasses him.
The following is my entry. It's uncompressed, unoptimized C code, and it compiles to 18475 bytes using the standard GCC settings on Win32. I hope that it will be surpassed shortly.
#include <stdio.h>
int main (void)
{
printf("Educators, generals, dieticians, psychologists, and parents program. Armies, students, and some societies are programmed. An assault on large problems employs a succession of programs, most of which spring into existence en route. These programs are rife with issues that appear to be particular to the problem at hand. To appreciate programming as an intellectual activity in its own right you must turn to computer programming; you must read and write computer programs -- many of them. It doesn't matter much what the programs are about or what applications they serve. What does matter is how well they perform and how smoothly they fit with other programs in the creation of still greater programs. The programmer must seek both perfection of part and adequacy of collection. In this book the use of ``program'' is focused on the creation, execution, and study of programs written in a dialect of Lisp for execution on a digital computer. Using Lisp we restrict or limit not what we may program, but only the notation for our program descriptions.");
return 0;
}
Your move, /prog/.
Name:
342010-01-20 0:00
Looks like I managed to beat my own record at this:
.586
.model flat,stdcall
option casemap:none
include windows.inc
include user32.inc
; include kernel32.inc
;removing this call, even though it's not really proper, but should work on NT and 9x, as long as you're not using some weird PE packers
;invoke ExitProcess,eax
ret
;; Compression function
aP_depack_asm:
; aP_depack_asm(const void *source, void *destination)
_ret$ equ 7*4
_src$ equ 8*4 + 4
_dst$ equ 8*4 + 8
pushad
mov esi, [esp + _src$] ; C calling convention
mov edi, [esp + _dst$]
It should also be possible to save some ~8-16 bytes by moving one of the import strings into the header, but oh well, it's all diminishing returns from here on.
>>41
I think <1024 bytes is possible if you write your own decompressor, but that's probably the lower limit. I could get the string compressed to ~500 bytes with something like 7z, but then your decompressor is larger than your compressed data.
Name:
Anonymous2010-01-21 0:04
#include <stdio.h>
int main (void)
{
FILE *ifp, *ofp;
char[30] temp;
ifp = fopen("x.txt", r);
x.txt contains
"Educators, generals, dieticians, psychologists, and parents program. Armies, students, and some societies are programmed. An assault on large problems employs a succession of programs, most of which spring into existence en route. These programs are rife with issues that appear to be particular to the problem at hand. To appreciate programming as an intellectual activity in its own right you must turn to computer programming; you must read and write computer programs -- many of them. It doesn't matter much what the programs are about or what applications they serve. What does matter is how well they perform and how smoothly they fit with other programs in the creation of still greater programs. The programmer must seek both perfection of part and adequacy of collection. In this book the use of ``program'' is focused on the creation, execution, and study of programs written in a dialect of Lisp for execution on a digital computer. Using Lisp we restrict or limit not what we may program, but only the notation for our program descriptions."
>>48
I (>>41) did include my own decompressor(not made by me, but aPlib which is one of the tiniest decompressors out there). The compressed text is about 0x26B (621)bytes long, I think it may be possible to compress it down to ~5xx bytes, but it will take a better compressor. Decompressor code is 0xA9 (165 bytes). After that you have, some 70 (0x46) bytes worth of imports(table), 0x26(30) bytes actual messagebox display code(and decompressing), and about 0x140 (320) mandatory header/section code. The problem is that you can't reduce the mandatory PE header by much, so this overhead will still exist. You can try to have dual use for the header, but it's tricky and hard to test(getting the PE loader to accept your barely legal PE header). If you used some more primitive format than the PE, without any mandatory fields (like DOS COM format which is raw machine code), you could probably only need: compressed text+decompression code+text display code. In this case, I need 822 bytes for this, not including header and imports, which is less than 1052(total uncompressed text), but is not less than the total file size(mandatory PE header + import).
putStrLn $ permutations " ',-.;AEILTUW`abcdefghiklmnopqrstuvwxy" `genericIndex` i
i is 168232886201243962476554103488494956833083813071404451617331861483496770135280319824397206481339935425217542091944826890841567664615856477281939914194628748826053518654779989872188573470321914206603966168610757082482646167761110781480574840953003387193707815200661636834775960908420997880438552810366267727026110308568591511986533928138190600484062522066300073129689227426828885525871328611743626774765377353506081753997353403529765061111304057653193442878488819145895220286313131130259806761656167832625873787756909654713961481491274753345173203913144902499937173389073981311419124182804089626557437569263141158638922912241732012229583787622611959718346854726953129446000458968815830427769183554439446455988777280214729278121251715134418400992163275089120799687146317104906997375379663829016996303413540063034505596996130294379628111991558453595783331000613924015493511747516824438016482746992254980150235611073431713353751554802928409331527174566000190667835809730617581582361247592823336419213335761910814054075905506528340279605364214572227131344816102209231077194611902166629429428895319818625290589445747236882157654451465634314941493487614078263579306754171172847741932416530131900502250320125033481876679450066327426779830147741229210608426632841223613906658413224401456752072343023635896147194552736674208700020305890612531759294595677161254147736241882120167726147643145869312832676443521755896364532928547247493204335582472612432819109048340358276183239967896430754117027387164820924450995868307183064742787986683772443931656030018903765198063505117111805680088408426029529399160314403871345531437101458502062792733069901043330175067311502526652114926. Determining the shortest representation of this number in program code is left as an exercise to the reader.
Sorry, not permutations. I shouldn't post in the morning. This is what I meant:
putStrLn $ replicateM 1052 " ',-.;AEILTUW`abcdefghiklmnopqrstuvwxy" `genericIndex` i
Name:
Anonymous2010-01-22 15:13
>>59,60
This gives me an idea for an algorithm to produce a tiny program that gives the required output:
shortest <- Infinity;
bestarray <- [];
for all 38! permutations of the character set:
let i be the number representation of the message
factor i into an array, N, of powers, and P, of primes
if length(N+P) < shortest:
shortest = length(N+P)
bestarray <- [N,P]
write a program to compute the integer represented by bestarray and write its message representation to standard output.
OP never said it needed to take a finite amount of time.