[fbodz]

This makes me think about kolmogorov complexity. The program here looks like gibberish but produces the desired output, would there be even shorter programs that don't look like they make sense but produce the same output? How would you search for these programs?

[JayXon]

The current world record for the shortest C program that prints 12 Days of Christmas lyrics is 431 bytes: https://code.golf/12-days-of-christmas#c

[kolleykibber]

Well that post just cost me a couple of hours.

And still 136 bytes off 431:

  #define p printf 
  int main(){const char *g[]={"A Partridge in a Pear 
  Tree.\n","Two Turtle Doves, and","Three French Hens,","Four 
  Calling Birds,","Five Gold Rings,"," Geese-a-Lay"," Swans- 
  a-Swimm","t Maids-a-Milk","e Ladies Danc"," Lords-a-Leap"," 
  Pipers Pip","Twelve Drummers Drumm"};
  const char *d[{"First","Second","Third","Four","Fif","Six","Seven","Eigh","Nin","Ten","Eleven","Twelf"};for(int i=0,j;i<12;i++){p("On 
  the %s%s day of Christmas\nMy true love sent to 
  me\n",d[i],i>2?("th"):"");
  for(j=i;j>=0;j--){p("%s%s%s\n",j>4&&j<11? 
  d[j]:"",g[j],j>4?"ing,":"");}}}

[huhtenberg]

You can shave 25 more by using printf as is, removing "const", removing spaces between char and *, and removing parenthesis around "th".

[tgv]

Are those consts really necessary? There are also a few character missing after char *d.

[mananaysiempre]

> Are those consts really necessary?

Technically yes, initializing a plain char * from a const char * (from array decay) is a constraint violation (an error the standard requires the compiler to detect and complain about) even in C89. Many compilers will let you off with a warning though.

[junon]

which characters are missing?

[huhtenberg]

"]=" after "*d["

[junon]

It's not necessary in C.

[Tiberium]

To be honest, I understand code.golf's premise, but still, code being public (maybe optionally?) would be nice.

[hddqsb]

I agree. Stack Exchange's Code Golf has public source, but the best there is 644 bytes: https://codegolf.stackexchange.com/a/4198

[AaronM]

Is it broken for anyone else the code prints hello world and then some numbers

[JayXon]

The leaderboard is public but the actual code is private, that hello world is just an example c program.

[smallnamespace]

> would there be even shorter programs that don't look like they make sense but produce the same output

Yes, mostly likely

> How would you search for these programs?

Brute force search is very inefficient so the real answer generally is "be clever" in the mathematical sense.

In general, KC is not computable so there is no program that can take a string and return the shortest program that computes that string.

However it's always in principle possible for someone to prove that the KC of some particular string is X.

[tromp]

> However it's always in principle possible for someone to prove that the KC of some particular string is X.

Only for a bounded number of strings. I.e. there is a finite set of string X such that for strings outside of X, you can not prove their KC, even in principle.

This result by Chaitin [1] can be paraphrased as: you cannot prove a 2 kilo theorem with a 1 kilo theory.

[1] https://www.jucs.org/jucs_2_5/the_limits_of_mathematics/Chai...

[tysam_and]

I think it's honestly quite hard to know, as it's really (generally speaking, AFAIPK) impossible to directly compute the KC in most cases, only really from the feasibility standpoint we can check that it's slower than some other version/value.

Which is quite exciting, it sets us up nicely for long-running competitions and the like due to the logarithmic-like growth curve (with sometimes some very fun discoveries on the ultra-tail-end of things! <3 :D)

Am currently running a mini-competition with a current prize bounty of $100 (distributed proportionally by % contribution in logspace) for an LLM that can memorize the most digits of Pi by March of next year. Pi is nice as it actually is quite compressible in theory and seeing if a model is able to learn a sufficiently-close-to-the-MDL set of weights that recovers a highly-compressed algorithm from the data would be extremely nice, indeedy!

However, whether this is feasible or not with off-the-shelf models and such is not entirely easy to know, so for now, it's just a digits-memorizing competition, and we shall see where it goes from there!!! <3 :'))))