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,":"");}}}

   const char *d[{"First","Second",...,"Twelf"};

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.

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.

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

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 :'))))