4 ms·

This makes me think about kolmogorov complexity. The program here looks like gibberish but produces the desired output, would there be even shorter programs tha

by fbodz 3y ago

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?

tysam_and 3y ago
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 :'))))
JayXon 3y ago
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 https://code.golf/12-days-of-christmas#c
- AaronM 3y ago
  Is it broken for anyone else the code prints hello world and then some numbers
  - JayXon 3y ago
    The leaderboard is public but the actual code is private, that hello world is just an example c program.
- Tiberium 3y ago
  To be honest, I understand code.golf's premise, but still, code being public (maybe optionally?) would be nice.
  - hddqsb 3y ago
    I agree. Stack Exchange's Code Golf has public source, but the best there is 644 bytes: https://codegolf.stackexchange.com/a/4198 https://codegolf.stackexchange.com/a/4198
- kolleykibber 3y ago
  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,":"");}}}
  - tgv 3y ago
    Are those consts really necessary? There are also a few character missing after char *d.
    - junon 3y ago
      which characters are missing?
      - huhtenberg 3y ago
        "]=" after "*d["
        junon 3y ago
        It's not necessary in C.
        tgv 3y ago
        You should tell my compiler.
        huhtenberg 3y ago
        const char *d[{"First","Second",...,"Twelf"}; is not a valid C unconditionally.
smallnamespace 3y ago
> 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 3y ago
  > 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/Chaitin_G_J.html https://www.jucs.org/jucs_2_5/the_limits_of_mathematics/Chai...

by fbodz 3y ago

tysam_and 3y ago

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

JayXon 3y ago

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 https://code.golf/12-days-of-christmas#c

AaronM 3y ago
Is it broken for anyone else the code prints hello world and then some numbers
- JayXon 3y ago
  The leaderboard is public but the actual code is private, that hello world is just an example c program.
Tiberium 3y ago
To be honest, I understand code.golf's premise, but still, code being public (maybe optionally?) would be nice.
- hddqsb 3y ago
  I agree. Stack Exchange's Code Golf has public source, but the best there is 644 bytes: https://codegolf.stackexchange.com/a/4198 https://codegolf.stackexchange.com/a/4198
kolleykibber 3y ago
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,":"");}}}
- tgv 3y ago
  Are those consts really necessary? There are also a few character missing after char *d.
  - junon 3y ago
    which characters are missing?
    - huhtenberg 3y ago
      "]=" after "*d["
      - junon 3y ago
        It's not necessary in C.
        tgv 3y ago
        You should tell my compiler.
        huhtenberg 3y ago
        const char *d[{"First","Second",...,"Twelf"}; is not a valid C unconditionally.

smallnamespace 3y ago

> 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 3y ago
> 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/Chaitin_G_J.html https://www.jucs.org/jucs_2_5/the_limits_of_mathematics/Chai...