this will be tough to explain. we're doing-- I mean, your task is to do gijswijt's sequence. submissions may not be written in languages in ∅.
this sequence (OEIS A090822)! is an odd one. let's get it started, like any good sequence, with a 1. now, to get each of the next numbers in the sequence, we're going to take
the entire sequence so far (so far, just 1) and look at the length of the longest run of repeated blocks we can see anchored to the end of the sequence.
all that doesn't make a ton of sense right now, but because all we have is this 1 it should be pretty clear that the only "run of repeated blocks" we're gonna
get is just this (1) on its own. that's only 1 block, so the next item in the sequence is gonna be 1. now we have 1 1, and it gets a little more interesting.
we can see that as two repeated short blocks (1) (1), so we can write a 2 next. we've reached 1 1 2, and things are getting VERY exciting.
you might think we can write another 2 because we still have the (1) (1) 2 trick up our sleeves, but remember what I said before? "anchored to the end of the sequence"? yeah.
that means our "run of repeated blocks" has gotta end at the end. we can't go taking 'em from the middle all willy-nilly now. that means the best we can get is a 1 1 (2) run, so we gotta write another 1.
let's skip ahead a bit, because I think you get the idea now.
1 1 2 1
1 1 2 1 1
1 1 2 1 1 2
boom, now something new can go down. we've got our first run with blocks of size greater than 1! look here: (1 1 2) (1 1 2)! last time we were in this spot, we could only write a 1, but because we've
retraced our steps and repeated the 1 1 2 part twice, we now have a run of 2 and can write a 2! we're saved from writing down 1 1 2 forever and can get to the rest of the sequence.
I think you get the idea now, so I'll just write out a few more terms for you. all in all, the sequence goes like this: 1 1 2 1 1 2 2 2 3 1 1 2 1 1 2 2 2 3 2 1...
your challenge is to print the is to output write the fucking thing you know what it is. as the only banned languages are in the empty set, there is no fixed API. I wish you good luck just kidding I actually
want you to lose so I score more points.
#!/usr/bin/sed -nrf:_Problem# Gijswijt's sequence# https://cg.esolangs.gay/66/:_Restrictions# can only generate the first 219 terms:main2Q1s:.*: 1:h;vb seq_loop:seq_loop/^( [0-9]+){219}$/{s:^ ::pQ0}s:(( [0-9]+)+)\1\1$:@3:s:(( [0-9]+)+)\1$:@2:s:^.*@::s:^ .*$:1:H;xs:\n::hb seq_loop
#include<stdio.h>#include<stdlib.h>chargijswijt_next(constchar*sequence,unsignedlen){// [ ] this is dynamic programming// [ ] this is tabulation// [ ] this is memoization// [x] this is quadratic but pretty much instant up to like 10000charmax_repeat_count=1;for(unsignedsubseq_len=1;subseq_len<=len/2;subseq_len++){charrepeat_count=1;unsignedcurrent_count=0;for(unsignedi=len-1;i>=subseq_len;i--){if(sequence[i]!=sequence[i-subseq_len]){break;}current_count++;if(current_count==subseq_len){repeat_count++;current_count=0;}}if(max_repeat_count<repeat_count){max_repeat_count=repeat_count;}}returnmax_repeat_count;}intmain(intargc,char*argv[]){unsignedmax_iter=220;if(argc>=2){if(sscanf(argv[1],"%u",&max_iter)!=1){fprintf(stderr,"USAGE: %s [max iterations (default %u)]\n",argv[0],max_iter);}}char*sequence=malloc((max_iter+1)*sizeof(*sequence));unsignedsequence_len=1;sequence[0]='1';// no wait ouch oof this is cubic helpwhile(max_iter-->1){charnext=gijswijt_next(sequence,sequence_len);sequence[sequence_len++]=next+'0';}sequence[sequence_len]='\0';puts(sequence);/* ^^^^^^^^ the fucking thing you know what it is ^^^^ print the is to output write */free(sequence);}
#include<errno.h>#include<fcntl.h>#include<stdint.h>#include<stdio.h>#include<stdlib.h>#include<string.h>#include<sys/mman.h>#include<sys/time.h>#include<sys/wait.h>#include<time.h>#include<unistd.h>#define THE_SIZE 0x20000000000// also known as 2 TiBvoidsin(constchar*err){fprintf(stderr,"fatal: sinful system%s%s\n",err?": ":"",err?err:"");exit(1);}typedefstruct{uint8_ta:4,b:4;}bitbyte_t;typedefstruct{uint64_ttotal;uint64_toff_8;uint64_toff_16;uint64_toff_32;uint64_toff_64;uint64_tdata;}data_t;staticdata_t*data;void*align(void*ptr,intligma){return(void*)(((size_t)ptr+(ligma-1))&-ligma);}uint64_tget(uint64_ti){if(i>=data->total){sin("sinful memory access");}char*ptr=(char*)&data->data;uint64_toff=0;if((data->off_8-1)<=i){ptr+=(data->off_8-1-off)/2+(data->off_8-1-off)%2;ptr=align(ptr,1);off+=data->off_8-1;}else{bitbyte_t*v=&((bitbyte_t*)ptr)[(i-off)/2];return(i-off)%2?v->b+1:v->a+1;}if((data->off_16-1)<=i){ptr+=1*(data->off_16-1-off);ptr=align(ptr,2);off+=data->off_16-1;}else{return((uint8_t*)ptr)[i-off]+1;}if((data->off_32-1)<=i){ptr+=2*(data->off_32-1-off);ptr=align(ptr,4);off+=data->off_32-1;}else{return((uint16_t*)ptr)[i-off]+1;}if((data->off_64-1)<=i){ptr+=4*(data->off_64-1-off);ptr=align(ptr,8);off+=data->off_64-1;}else{return((uint32_t*)ptr)[i-off]+1;}return((uint64_t*)ptr)[i-off]+1;}voidappend(uint64_tval){uint64_ti=data->total++;if(val<1){sin("sinful data");}val--;if(val>=(1ULL<<4)&&!data->off_8){data->off_8=i+1;}if(val>=(1ULL<<8)&&!data->off_16){data->off_16=i+1;}if(val>=(1ULL<<16)&&!data->off_32){data->off_32=i+1;}if(val>=(1ULL<<32)&&!data->off_64){data->off_64=i+1;}char*ptr=(char*)&data->data;uint64_toff=0;if((data->off_8-1)<=i){ptr+=(data->off_8-1-off)/2+(data->off_8-1-off)%2;ptr=align(ptr,1);off+=data->off_8-1;}else{bitbyte_t*v=&((bitbyte_t*)ptr)[(i-off)/2];(i-off)%2?(v->b=val):(v->a=val);return;}if((data->off_16-1)<=i){ptr+=1*(data->off_16-1-off);ptr=align(ptr,2);off+=data->off_16-1;}else{((uint8_t*)ptr)[i-off]=val;return;}if((data->off_32-1)<=i){ptr+=2*(data->off_32-1-off);ptr=align(ptr,4);off+=data->off_32-1;}else{((uint16_t*)ptr)[i-off]=val;return;}if((data->off_64-1)<=i){ptr+=4*(data->off_64-1-off);ptr=align(ptr,8);off+=data->off_64-1;}else{((uint32_t*)ptr)[i-off]=val;return;}((uint64_t*)ptr)[i-off]=val;}intgenerator(constchar*path){intfd=open(path,O_RDWR|O_CREAT,0644);if(fd==-1)sin(strerror(errno));if(truncate(path,THE_SIZE))sin(strerror(errno));data=mmap(NULL,THE_SIZE,PROT_READ|PROT_WRITE,MAP_SHARED,fd,0);if(data==MAP_FAILED)sin(strerror(errno));intcolumn=0;inthuman_readable=isatty(fileno(stdout));for(uint64_ti=0;i<data->total;i++){column+=printf("%llu",(unsignedlonglong)get(i));if(!human_readable){column=100;}if(column>72){printf("\n");column=0;}else{column+=printf(" ");}}structtimespects_begin;clock_gettime(CLOCK_MONOTONIC,&ts_begin);for(;;){uint64_tmax_rep=1;for(uint64_tstride=1;stride<=data->total/(max_rep+1);stride++){uint64_trep;for(rep=1;(rep+1)<=data->total/stride;rep++){for(uint64_ti=0;i<stride;i++){if(get(data->total-1-i-rep*stride)!=get(data->total-1-i-(rep-1)*stride)){gotorepeat_out;}}}repeat_out:if(max_rep<rep){max_rep=rep;}}column+=printf("%llu",(unsignedlonglong)max_rep);if(!human_readable){column=100;}if(column>72){printf("\n");column=0;}else{column+=printf(" ");}structtimespects_end;clock_gettime(CLOCK_MONOTONIC,&ts_end);if((ts_end.tv_sec*1000+ts_end.tv_nsec/1000000)-(ts_begin.tv_sec*1000+ts_end.tv_nsec/1000000)>50){fflush(stdout);clock_gettime(CLOCK_MONOTONIC,&ts_begin);}append(max_rep);}return0;}intmain(){constchar*cfg_home=getenv("XDG_CONFIG_HOME");if(!cfg_home){constchar*home=getenv("HOME");if(!home){returngenerator("/tmp/cg666.bin");}charpath[strlen(home)+sizeof("/.config/cg666/data.bin")];path[0]='\0';strcat(path,home);strcat(path,"/.config/cg666");pid_tpid;if(!fork()){if(execl("/usr/bin/env","/usr/bin/env","mkdir","-p","--",path,NULL))sin(strerror(errno));return0;}intstatus;if(waitpid(pid,&status,0)==-1){sin(strerror(errno));}elseif(status!=0){sin("mkdir is a sinner");}strcat(path,"/data.bin");returngenerator(path);}else{charpath[strlen(cfg_home)+sizeof("/cg666/data.bin")];path[0]='\0';strcat(path,cfg_home);strcat(path,"/cg666");pid_tpid;if(!fork()){if(execl("/usr/bin/env","/usr/bin/env","mkdir","-p","--",path,NULL))sin(strerror(errno));return0;}intstatus;if(waitpid(pid,&status,0)==-1){sin(strerror(errno));}elseif(status!=0){sin("mkdir is a sinner");}strcat(path,"/data.bin");returngenerator(path);}}
len(entry(26))
completes in only 7 seconds, which is par for the course. I'm reluctant to go further, seeing as 30 had run out my memory.I was not closely enough to count how long it took, but block 27 contains a total of 233988391 elements.
post a comment