# Omnimaga

## Calculator Community => Contests => Community Contests => Topic started by: c4ooo on June 15, 2015, 12:00:02 am

Title: [ENDED] Code Golf - The Reboot #3
Post by: c4ooo on June 15, 2015, 12:00:02 am
Hello ladies, gentleman, and welcome to the third iteration of...
:evillaugh: Code Golf Rebooted! :evillaugh: ™
...not that its evil or anything... But any way, as you can see i am neither @JWinslow23 nor @pimathbrainiac,for my name is c4ooo, and if you are confused as to what is happening, I will explain. Basically, me Pimath and Winslow as well as others, will all be hosting the challenges in succession. If you are confused because you do not know what code golf is, please check out this thread: https://www.omnimaga.org/community-contests/code-golf-the-reboot-1/ (https://www.omnimaga.org/community-contests/code-golf-the-reboot-1/)

So, as to begin, here is this weeks challenge:
Challenge #3: Cellular automation
You must wright a program that infinitely computes Conway's Game of Life. What is this Conway's Game of Life you may be asking? The Game (no not that game, Conway's Game) is "zero person" game in which the board is split into an infinite grid of square cells. Based on four specific rules, cell die or are reborn. These are the four rules, taken from wikipidia:
Quote
• Any live cell with fewer than two live neighbours dies, as if caused by under-population.
• Any live cell with two or three live neighbours lives on to the next generation.
• Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.
• Any live cell with more than three live neighbours dies, as if by overcrowding.

Thus, a every pixel is a cell, and every turn the four rules must be applied to every pixel/cell to generate the new state of the game board. A cell is a "neighbouring cell" if it is adjacent to the cell, diagonals included. To know more about The Game, I highly suggest Wikipedia (It might be necessary for you to read the article, my summery of The Game is very brief): https://en.wikipedia.org/wiki/Conway's_Game_of_Life (https://en.wikipedia.org/wiki/Conway's_Game_of_Life). Mostly to give an advantage to calculators, i will add several rules your program must follow:
• Every pixel on the screen must be an individual cell, white being dead and black being alive or vice verse.
• The game board must consist of every pixel on the screen. eg "full screen"., However, the rule does not apply if there is a significant limitation in your language where this is simply not possible, like in Silver Edition TI-BASIC, or PICO-8.
• The outer pixels do not have to follow the rules,If you want you make make them dead forever. Alternatively, you can make the board wrap around.
• The game must start in a pseudo random configuration, loophole fix, courtesy @Runer112 "every cell's initial state must have a nonzero chance of being in each state and must be independent (barring reasonable PRNG limitations) of every other cell's initial state." No user input / cell manipulation is required.
• Every iteration the program must obviously update the screen.
Ranking
Solutions
Runer112:
Spoiler For Spoiler:

.L
For(ClrDraw)
Pxl-Change(,rand
End
Repeat StorePic DispGraphClrDrawgetKey
For(X,,"
For(9→Z)
-pxl-Test(Z--^3+X-1,Z/3+Xʳʳ-1)ʳ
End
Pxl-On( or pxl-Test(X,Xʳʳ)ʳ=5*X,Xʳʳ
End
End

lirtosiast:
Spoiler For Spoiler:

0
For(F,1,E9
For(X,0,93
Ans/7+49seq(pxl-Test(Y,X+1),Y,0,62
For(Y,1,61
If 2rand<F=pxl-Test(Y,X)+int(3fPart(3cosh(fPart(6-1iPart(sum(Ans,Y,Y+2
Pxl-Change(Y,X
End
End
End

Haobo:
Spoiler For Spoiler:

Copy(rand
While
StorePicDispGraphClrDraw
For(Y,0,63
For(X,0,95
For(Z,0->B,8
pxl-Test(Z^3+X-1,Z/3+Y-1)^^r->A
Z=4?A->C,A+B->B
End
If B=3+(C?B=2
Pxl-On(X,Y
End
End
End
End

ben_g:
Spoiler For Spoiler:

*COMING*

Scipi:
Spoiler For Spoiler:

#include<tonc.h>
#define l for(x=0;++x<239;)for(y=0;++y<159;)
main(){R=1028;*P=32767;u8 x,y,s,m,p;for(;!(S=~K&1023););l M(x,y,Q()&1);for(;u8*v=(u8*)V;){F();l{for(m=-1,p=v[x+y*240],s=-p;++m<9;)s+=v[x+m%3-1+(y+m/3-1)*240];M(x,y,p?s<4&s>1:s==3);}}}

pbfy0:
Spoiler For Spoiler:

.string "PRG"

lcd_ptr .req r4
active_fb .req r5
inactive_fb .req r6
orig_fb .req r7
new_fb .req r8

@ start
push {r4-r8, r12, lr}

ldr lcd_ptr, =0xC0000000
@mov r0, #0x10000
@sub r0, r0, #0x11
ldrh r0, [r9, #6] @ 0xffff is already in the offset table because of -1
str r0, [lcd_ptr, #0x200]

@ldr r2, [lcd_ptr, #0x18]
@bic r2, #14
@orr r2, #6 @ 8 bpp, paletted
ldrh r2, [r9, #18]
str r2, [lcd_ptr, #0x18]

@add lcd_ptr, r1, #0x10 @ to 0xC0000010
ldr orig_fb, [lcd_ptr, #0x10] @ original framebuffer
mov active_fb, orig_fb @ active framebuffer
mov inactive_fb, new_fb

ldr r10, =76800
mov r11, #0
1:   subs r10, r10, #1
strb r11, [active_fb, r10]
@ldrb r3, [inactive_fb, r10]
svc #206 @ rand
and r0, r0, #1
strb r0, [inactive_fb, r10]
bne 1b

mov r2, #320
mov r1, #0
mov r0, inactive_fb
push {r1,r2}
svc #7
pop {r1,r2}
ldr r3, =76480
svc #7

3:   ldr r0, =76480 @ 320 * 239
str inactive_fb, [lcd_ptr, #0x10]
mov inactive_fb, active_fb
ldr active_fb, [lcd_ptr, #0x10]

2:   mov r1, #18 @ 9 * 2
mov r2, #0
sub r0, #1

1:   sub r1, #2
ldrsh r3, [r9, r1] @ won't let me use lsl #1
cmp r3, #76800
ldrltb r3, [active_fb, r3] @ no lt?
teq r1, #0
bne 1b @ at end of loop, r1 and r3 can be discarded

ldrb r1, [active_fb, r0]
teq r2, #3
moveq r1, #1
teqne r2, #4
movne r1, #0
strb r1, [inactive_fb, r0]
teq r0, #320
bne 2b

ldr r0, =0x900E001C
ldr r1, [r0]
tst r1, #0x80
beq 3b

str orig_fb, [lcd_ptr, #0x10]
pop {r4-r8, r12, pc}

offsets:
.hword -321, -320, -319, -1, 1, 319, 320, 321, 0 @ actual offsets
.hword 0x927 @ misc data

Juju:
Spoiler For Spoiler:

function e(i)x=i%128y=i/128n=pget(x,y)z=-n
for j=-3,5 do z+=pget(x+j/3,y+j%3-1) end
if(z<9 or z>21)n=0
if(z==21)n=7
return n
end
for i=0,8191 do poke(i,112*flr(rnd(2))+7*flr(rnd(2)))end
function _update()end
function _draw()memcpy(24576,0,8192)for i=0,8191 do
poke(i,16*e(i*2+1)+e(i*2))end
end

My solution:
Spoiler For Spoiler:

*COMING*

Scoring
All non-calculator programs will be scored through this counter: http://juju2143.ca/golf/
Assembly programs will be scored on binary size (excluding the header), and Basic/Axe programs will be scored based on-calc source size (once again, excluding the header).
Good luck, and may this contest automate you!
Submission:
To submit, ether send me a PM with a the/link to code, or electronically mail me at kuznetsov4000[at]gmail[dot]com.
Want to host to?
Title: Re: Code Golf - The Reboot #3
Post by: lirtosiast on June 15, 2015, 12:13:03 am
I think I know what my approach (in Ti-BASIC) will be. It will be very slow when golfed completely, and I don't think we should expect any of these to be of practical speed.

Do you mean CSE BASIC for the screen limitations?

I think you should specify a minimum screen size, because on any machine without a screen the solution is trivial: since there are no pixels, do nothing.
Title: Re: Code Golf - The Reboot #3
Post by: Juju on June 15, 2015, 12:14:33 am
Hm, another graphic challenge. Gotta try the new PICO-8 0.1.1 out.
Title: Re: Code Golf - The Reboot #3
Post by: c4ooo on June 15, 2015, 12:16:01 am
Hm, another graphic challenge. Gotta try the new PICO-8 0.1.1 out.
This is meant to give advantages to calculators.

I think I know what my approach (in Ti-BASIC) will be. It will be very slow when golfed completely, and I don't think we should expect any of these to be of practical speed.
This is code golf so size > speed :)

Also AOTM i am still tweaking the rules based on some feedback i am getting on IRC so yea...
Title: Re: Code Golf - The Reboot #3
Post by: Scipi on June 15, 2015, 12:18:37 am
I had a feeling Conway's Game Of Life would be one of the challenges. :P Kind of hoping to see Langton's Ant appear, as well
Title: Re: Code Golf - The Reboot #3
Post by: lirtosiast on June 15, 2015, 12:20:34 am
Sorry, stupid question and off-topic but how do I access IRC?

EDIT: -_- I don't want to spam the fora, so I'll wait.

EDIT: That pun was probably the worst in the history of code golf.
Title: Re: Code Golf - The Reboot #3
Post by: c4ooo on June 15, 2015, 12:21:22 am
Sorry, stupid question and off-topic but how do I access IRC?
You get access to it once you get 40 post IIRC :)
Also what @Juju said.
Title: Re: Code Golf - The Reboot #3
Post by: Juju on June 15, 2015, 12:26:44 am
Sorry, stupid question and off-topic but how do I access IRC?
You get access to it once you get 40 post IIRC :)
That's true, but for the OmnomIRC shoutbox. Otherwise, get a IRC client such as Hexchat or mIRC and point it at either irc.efnet.org or irc.omnimaga.org.

Hm, another graphic challenge. Gotta try the new PICO-8 0.1.1 out.
This is meant to give advantages to calculators.
I don't really see why it wouldn't. It's pretty much Lua with a graphics library.
Title: Re: Code Golf - The Reboot #3
Post by: Scipi on June 15, 2015, 04:28:42 am
Down to 287 bytes in GBA C ^_^ I can probably cut it down to somewhere below 250 if I can eliminate a for-loop somewhere.
Title: Re: Code Golf - The Reboot #3
Post by: ben_g on June 15, 2015, 05:27:23 am
I think I know what my approach (in Ti-BASIC) will be. It will be very slow when golfed completely, and I don't think we should expect any of these to be of practical speed.
yeah, Ti-Basic already needs about a minute to update every pixel without doing any logic. I hope you're patient, c4ooo :P

Since Axe is also counted based on source code size now, I think I'm going to try that now.
Title: Re: Code Golf - The Reboot #3
Post by: JWinslow23 on June 15, 2015, 11:43:08 am
EDIT: That pun was probably the worst in the history of code golf.

Well, to be fair, this reboot series doesn't have a lot of "history" :P

I promise you, the next pun will be better ;)
Title: Re: Code Golf - The Reboot #3
Post by: Geekboy1011 on June 15, 2015, 06:03:40 pm
Sorry, stupid question and off-topic but how do I access IRC?

EDIT: -_- I don't want to spam the fora, so I'll wait.

EDIT: That pun was probably the worst in the history of code golf.

Off topic response to an off topic post.  But it's related to forum etiquette.

As long as the posts are constructive and not spam. There is no such thing as spamming the forum. Post away! And to be honest it's actually recommended to post when ever possible. This way the questions,content is available to everyone. Not just the people active at the time!
Title: Re: Code Golf - The Reboot #3
Post by: lirtosiast on June 15, 2015, 11:24:53 pm
It looks like my first attempt will be about 200 bytes, and take over ten minutes per frame. I prefer the short ones, but let's see how this goes.
Title: Re: Code Golf - The Reboot #3
Post by: Runer112 on June 16, 2015, 09:32:27 am
Overall, I'm fairly happy with this question being sufficiently specified. However, I see one rule that should probably be specified further:

• The game must start in a pseudo random configuration, and no user input is required.

As an example of abuse, a single cell placed pseudorandomly is a "pseudo random configuration," but not a very interesting one as every generation after the initial will just be entirely empty. You could fix this by specifying that every cell's initial state must have a nonzero chance of being in each state and must be independent (barring reasonable PRNG limitations) of every other cell's initial state.

Also, you may want to consider adding a minimum bound on FPS. I realize this is a code golf contest, but at a point, one has to say that an extremely slow game of life simulation is no longer an acceptable game of life simulation. I understand that this may make the challenge as currently specified more or less impossible in some languages, in which case you could consider extending the exception to the "full screen" rule. I would suggest something like a minimum of 0.1 FPS and allowing entries that cannot meet this at full screen to run on a square board with a side length of at least 16 and no less than the largest power of two that satisfies the minimum FPS.
Title: Re: Code Golf - The Reboot #3
Post by: c4ooo on June 16, 2015, 11:05:44 am
Overall, I'm fairly happy with this question being sufficiently specified. However, I see one rule that should probably be specified further:

• The game must start in a pseudo random configuration, and no user input is required.

As an example of abuse, a single cell placed pseudorandomly is a "pseudo random configuration," but not a very interesting one as every generation after the initial will just be entirely empty. You could fix this by specifying that every cell's initial state must have a nonzero chance of being in each state and must be independent (barring reasonable PRNG limitations) of every other cell's initial state.
Fixed :D

Also, you may want to consider adding a minimum bound on FPS. I realize this is a code golf contest, but at a point, one has to say that an extremely slow game of life simulation is no longer an acceptable game of life simulation. I understand that this may make the challenge as currently specified more or less impossible in some languages, in which case you could consider extending the exception to the "full screen" rule. I would suggest something like a minimum of 0.1 FPS and allowing entries that cannot meet this at full screen to run on a square board with a side length of at least 16 and no less than the largest power of two that satisfies the minimum FPS.
Nahh, it have plenty of time  ;)

I think you should specify a minimum screen size, because on any machine without a screen the solution is trivial: since there are no pixels, do nothing.
Standard loopholes apply : http://meta.codegolf.stackexchange.com/questions/1061/loopholes-that-are-forbidden-by-default
IMPORTANT
I will be away starting tomorrow afternoon till about Friday afternoon. If you have any important thing to talk to me about, please ask me before then .
Title: Re: Code Golf - The Reboot #3
Post by: Juju on June 16, 2015, 02:53:32 pm
I think I have a nice sub-300 in PICO-8, 293 to be exact. And if you remove a line, you can even draw your own starting pattern in the sprite editor!

Speaking of which, the pseudo-random rule, in layman's terms, you should loop through each and every pixel and randomly set it on or off, right? That's what I did anyway.
Title: Re: Code Golf - The Reboot #3
Post by: lirtosiast on June 16, 2015, 03:20:12 pm
159... I can probably go smaller than that in TI-BASIC, but if ben_g can golf it any more I don't have much more room.

I think I have about 160, but I have yet to test it.
Title: Re: Code Golf - The Reboot #3
Post by: c4ooo on June 16, 2015, 03:45:27 pm
Nice seeming the replies come in! Friday will be the day when I make the next scoreboard update, mostly for you to keep trying harder and to not stop when you know your position is secure  ;)
I also made a solution in axe to this, which I will probably describe in the postmortem section. It is similar to @ben_g 's solution, but only takes up 110 bytes.
And also a small hint to axe golfers: randomizing the screen only takes 3 bytes :P
Title: Re: Code Golf - The Reboot #3
Post by: Scipi on June 16, 2015, 03:53:30 pm
I'm kind of screwed with long function and define names in the library I'm using. I could get mine well below 200 if I went in and renamed a few things, but I don't know if that's considered cheating or not.
Title: Re: Code Golf - The Reboot #3
Post by: lirtosiast on June 17, 2015, 08:22:58 am
It's actually funny how slow my solution is. I'm testing it out now, and it's taken 30 minutes for two-thirds of a frame. It also runs in O(n2) time where n is the number of pixels on the screen, so if you try it on a CSE while changing the numbers around so it takes up the whole graph screen, it'll take about two days per frame-- if it even works, which I suspect it won't for a different reason.

EDIT: Two things.

First, the spec should add that every possible combination of cells should be supported (to disallow TI-BASIC answers that store all live points in a list and thus won't work with more than 999).

Second, my solution seems to work. I've been testing it for about six hours, and I'm starting to get blocks and blinkers, and even one LWSS!

I saved one byte by halving the speed of the program, so now it's an hour and a half per frame (at 15 MHz), or about one pixel per second. This is ridiculous.
Title: Re: Code Golf - The Reboot #3
Post by: pbfy0 on June 17, 2015, 01:38:05 pm
And here I am with my program that runs 10 generations per second
On the other hand, it's 308 296 bytes
Title: Re: Code Golf - The Reboot #3
Post by: lirtosiast on June 18, 2015, 12:24:33 am
@pbfy0 what language are you using? That sounds fast for Axe, especially golfed Axe.

I managed to shave one more byte, but now my code takes two hours per frame. I hope you have the patience to test it, c4ooo...
Title: Re: Code Golf - The Reboot #3
Post by: pbfy0 on June 18, 2015, 09:58:02 am
I'm using nspire assembly. It's mostly so fast just because the calculator is fast. On the other hand, it's hard to golf past a certain point because all arm instructions are 4 bytes.
Title: Re: Code Golf - The Reboot #3
Post by: lirtosiast on June 18, 2015, 12:10:01 pm
A well-golfed solution is entertaining to create and read even if it's in a verbose language.

The shortest version of my code is fast* again! I'll probably never get close to 110 bytes though.

*one frame every 40 minutes
Title: Re: Code Golf - The Reboot #3
Post by: JWinslow23 on June 18, 2015, 12:49:15 pm
@pbfy0 what language are you using? That sounds fast for Axe, especially golfed Axe.

I managed to shave one more byte, but now my code takes two hours per frame. I hope you have the patience to test it, c4ooo...
Well, doesn't the emulator Wabbitemu have an option to run TI-83/84/+/SE code at 1600% speed or something? That would mean about 7.5 minutes per frame :P
Title: Re: Code Golf - The Reboot #3
Post by: lirtosiast on June 18, 2015, 12:59:24 pm
It would only be 3 minutes with my updated code! That's an amazing .005 FPS.

Is anyone else entering the constest in TI-BASIC?
Title: Re: Code Golf - The Reboot #3
Post by: Haobo on June 18, 2015, 11:43:14 pm
And also a small hint to axe golfers: randomizing the screen only takes 3 bytes :P

O_O wanna give a little hint on how you did this?

Smallest I got was 15 the old fashion way...
Title: Re: Code Golf - The Reboot #3
Post by: lirtosiast on June 19, 2015, 08:05:21 pm
I have 93 bytes in TI-BASIC, but I think Runer112 has already beaten me in Axe with 88.

This challenge has been very entertaining; in fact, it's even better than I thought.
Title: Re: Code Golf - The Reboot #3
Post by: TIfanx1999 on June 21, 2015, 04:07:46 am
So, I don't think my entry will be finished today, but I'm still going to post it here when I have it finished.
Title: Re: Code Golf - The Reboot #3
Post by: c4ooo on June 21, 2015, 06:20:56 pm
I have extended the deadline from @pimathbrainiac's "11:59:59 PM ET Saturday" to 11:59:59 PM ET Sunday. From the beginning i believed that  11:59:59 PM ET Sunday was the deadline, and thought pimathbrainiac made a typo when he said Saturday. Although the deadline for this challenge is 11:59:59 PM ET Sunday, following challenges will most likely have the deadline of 11:59:59 PM ET Saturday.
Title: Re: Code Golf - The Reboot #3
Post by: Juju on June 21, 2015, 07:23:58 pm
IMO, 11:59:59 PM ET Sunday would probably be better for those who don't have time through the week.
Title: Re: [ENDED, UPDATED RESULTS MONDAY] Code Golf - The Reboot #3
Post by: Scipi on June 22, 2015, 12:56:03 am
IMO, 11:59:59 PM ET Sunday would probably be better for those who don't have time through the week.

I thought the deadline ended Sundays O.O

I agree, though, it would make more sense for the deadline to be Sunday rather than Saturday.
Title: Re: [ENDED] Code Golf - The Reboot #3
Post by: Runer112 on June 22, 2015, 01:10:42 pm
Not to try to nitpick, but I feel obligated to point out that Haobo's solution does not wholly satisfy rule 4: "... every cell's initial state ... must be independent (barring reasonable PRNG limitations) of every other cell's initial state." The reason I suggested this clause was to prevent simple "randomization" implementations that do not provide at least somewhat convincing randomization. Regrettably, this solution's clever approach of simply using a randomly chosen 768-byte block of memory as the initial state does not satisfy this.

A heuristic proof of this could cite that memory almost always contains meaningful, structured data. As a particuarly apparent example, memory often contains large stretches of zeroes. If one such large stretch were contained in the initial state, then a pixel's probability of starting dead is greatly increased if the byte(s) immediately before it are all zero. This constitutes dependence. And also a pretty boring game of life, which is why the clause was proposed.

Although less apparent on structured data that's not just a stretch of zeroes, the same dependence and insufficient randomness exists in any non-chaotic data. So to extend this heuristic proof to a definitive one, one can prove that non-chaotic data exists in memory. And this can be done by citing the existence of the program itself in memory.

I came down on lirtosiast and pbfy0 earlier about skirting around this clause, so I thought it to only be fair that I come down here as well. I even came down on myself by proposing this clause in the first place, as I was considering using such a "randomization" approach but considered it against the spirit of the prompt.
Title: Re: [ENDED] Code Golf - The Reboot #3
Post by: c4ooo on June 22, 2015, 01:34:10 pm
Not to try to nitpick, but I feel obligated to point out that Haobo's solution does not wholly satisfy rule 4: "... every cell's initial state ... must be independent (barring reasonable PRNG limitations) of every other cell's initial state." The reason I suggested this clause was to prevent simple "randomization" implementations that do not provide at least somewhat convincing randomization. Regrettably, this solution's clever approach of simply using a randomly chosen 768-byte block of memory as the initial state does not satisfy this.

A heuristic proof of this could cite that memory almost always contains meaningful, structured data. As a particuarly apparent example, memory often contains large stretches of zeroes. If one such large stretch were contained in the initial state, then a pixel's probability of starting dead is greatly increased if the byte(s) immediately before it are all zero. This constitutes dependence. And also a pretty boring game of life, which is why the clause was proposed.

Although less apparent on structured data that's not just a stretch of zeroes, the same dependence and insufficient randomness exists in any non-chaotic data. So to extend this heuristic proof to a definitive one, one can prove that non-chaotic data exists in memory. And this can be done by citing the existence of the program itself in memory.
+1 for that proof ( or attempt of)  :thumbsup:

However, I would like to warn you that you are on unsure footing. First you "criticized" @lirtosiast's answer and now you are trying to do the same with @Haobo's I fully trust, being the person you are, that you are doing this for the good and fairness of the game/community However if someone puts two and two together, it may seam to the  that you are trying to discourage completion :P just saying, not trying to attack you or anything. (Reread what I said in bold :P )
Title: Re: [ENDED] Code Golf - The Reboot #3
Post by: TIfanx1999 on June 29, 2015, 02:13:14 am
Well obviously, I didn't have time to finish. I still wanted to finish it (even if it was late) and post my attempt. Unfortunately, I got really sick and haven't been doing much of anything recently. I hope to revisit this in a bit and finish it or at least post an explanation of what i was going to attempt.