# Advent of Code 2018

Advent of Code is an Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like.

2 个赞

2 个赞

``````;; language: clojure
;;;; helpers
(defn to-i [s] (Integer/parseInt s))
(def my-input-list (map to-i (line-seq (clojure.java.io/reader "input.txt"))))

;;;; day one
;; part 1
(apply + my-input-list)

;; part 2
(defn f [sets sum list]
(let [head (first list),
tail (rest list),
now-sum (+ head sum),
now-sets (conj sets now-sum)]
(cond
(sets now-sum) now-sum
(empty? tail) (recur now-sets now-sum my-input-list)
true (recur now-sets now-sum tail))))

(f #{} 0 my-input-list)
;; 楼主花了将近 50 秒，我这就用了 1 秒。。。是都花在花哨的交互上了么 XD
``````

Day2

``````# language: elixir
# Unit
input =
File.open!("input.txt")
|> String.split()

# Day Two Part One
input
|> Enum.reduce({0, 0}, fn(str, {s, t}) ->
freqs =
String.graphemes(str)
|> Enum.group_by(&(&1))
|> Enum.map(fn({_, v}) -> length(v) end)

fun = &(if Enum.member?(freqs, &1), do: 1, else: 0)

{s + fun.(2), t + fun.(3)}
end)
|> (fn({s, t}) -> s * t end).()

# Day Two Part Two
input
|> Enum.find_value(fn(now_str) ->
Enum.find_value(input, fn(s) ->
diff = String.myers_difference(now_str, s)
if 4 == length(diff) do
del = Keyword.get(diff, :del) || ""
ins = Keyword.get(diff, :ins) || ""

if String.length(del) == 1 && String.length(ins) == 1, do: diff
end
end)
end)
|> Keyword.take([:eq])
|> (fn([{_, x}, {_, y}]) -> x <> y end).()
``````
1 个赞

``````         &anchor  = 1
digits   = '0123456789'
freq     = 0
pat      = (any('+-') . sign) (span(digits) . val)
loop     input pat                   :f(fin)
add      freq     = freq + val       :(loop)
min      freq     = freq - val       :(loop)
fin      output   = freq
end
``````
``````>> 0:~ \$ time cat Downloads/input.txt  | spitbol day1.snb                                 << 19:57 <]
0.00 real         0.00 user         0.00 sys
``````

Part 2 要用到 IO，稍有一點麻煩。

``````         &anchor  = 1
digits   = '0123456789'
freq     = 0
sat      = table(1000,500)
sat<0>   = 1
pat      = (any('+-') . sign) (span(digits) . val)
open     input('data',1)
loop     data pat                    :f(endf)
endf     endfile(1)                  :(open)
add      freq     = freq + val       :(hash)
min      freq     = freq - val
hash     sat<freq>  = sat<freq> + 1
eq(sat<freq>, 2)            :f(loop)
fin      output   = freq
end
``````
``````>> 0:~ \$ time spitbol -1=input.txt day1-2.snb                                             << 20:45 <]
0.39 real         0.38 user         0.00 sys
>> 0:~ \$ wc -l input.txt                                                                  << 21:00 <]
1025 input.txt
``````

Day2 part1

``````>> 0:~ \$ cat day2.snb                                                                     << 23:38 <]
&anchor = 1
three   = 0
two     = 0
pat     = len(1) . char
loop    line = input            :f(fin)
stat = table(30)
in      line pat =              :f(set)
gt(stat<char>, 3)       :s(in)
eq(stat<char>, 3)       :f(nt)
accu3 = accu3 - 1       :(inc)
nt      eq(stat<char>, 2)       :f(nxt)
accu2 = accu2 - 1
accu3 = accu3 + 1       :(inc)
nxt     eq(stat<char>, 1)       :f(inc)
accu2 = accu2 + 1
inc     stat<char> = stat<char> + 1 :(in)
set     gt(accu3, 0)            :f(nn)
three = three + 1
nn      gt(accu2, 0)            :f(cl)
two = two + 1
cl      accu3   = 0
accu2   = 0             :(loop)
fin     res = two * three
output = 'res:' two '*' three '=' res
end
>> 0:~ \$ time cat input.txt | spitbol day2.snb                                            << 23:38 <]
0.00 real         0.00 user         0.00 sys
res:249*23=5727
``````
1 个赞

1-1

``````%{
#include <math.h>
long sum = 0;
%}

%%

[+-]?[0-9]+   { sum += atoi( yytext ) ;}
[ \t\n]+     /* eat up whitespace */
.           printf( "Unrecognized character: %s\n", yytext );

%%

int main( int argc, char **argv ){

++argv, --argc;  /* skip over program name */

if ( argc > 0 )
yyin = fopen( argv[0], "r" );
else
yyin = stdin;
yylex();
printf("the sum:%ld",sum);
}
``````

1-2

``````%{

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <search.h>

long sum = 0;
int line = 1;
int page = 0;
ENTRY e, *ep;
char str[255];

%}

%%

[+-]?[0-9]+   { sum += atoi( yytext ) ;
sprintf(str, "%d", sum);
e.key = str;
e.data = (void *) line;
ep = hsearch(e, ENTER);

if (ep == NULL) {
printf("hash table two small : %d",line);
exit(1);
}else{
if((int)(ep->data) != line){
printf("found sum:%s, first-line:%d, current-line:%d, page:%d",str, (int)(ep->data) ,line,page);
exit(0);
}
}
}
[ \t]+       /* eat up whitespace */
\n         {line++;}
.          printf( "Unrecognized character: %s\n", yytext );

<<EOF>>    {  yyterminate(); }

%%

int main( int argc, char **argv ){

hcreate(900000);

++argv, --argc;  /* skip over program name */
while(1){
if ( argc > 0 )
yyin = fopen( argv[0], "r" );
else
yyin = stdin;
yylex();
page ++;
line = 1;
// printf("page :%d\n",page);
}
hdestroy();
}

``````

``````
\$ time ./a.out  test.txt
found sum:563, first-line:529, current-line:561, page:139
real    0m0.209s
user    0m0.160s
sys     0m0.050s

``````

2 个赞

ん？（察觉）

1 个赞

2

``````%{
char letter[26];
int  two_flag = 0;
int  three_flag = 0;
int two_count = 0;
int three_count = 0;

void init(){
two_flag = 0;    three_flag = 0;
for(int i = 0; i< 26 ; i++){
if(letter[i] ==2 && two_flag == 0){      two_count++; two_flag = 1; }
if(letter[i] ==3 && three_flag == 0){      three_count++; three_flag = 1;  }
}
for(int i = 0; i< 26 ; i++)letter[i] = 0;
}
%}

%%

[a-z]   { int i = *yytext -'a' ; letter[i]++; }
[ \t]+       /* eat up whitespace */
\n         {init();}
.          printf( "Unrecognized character: %s\n", yytext );

%%

int main( int argc, char **argv ){
++argv, --argc;  /* skip over program name */
if ( argc > 0 )
yyin = fopen( argv[0], "r" );
else
yyin = stdin;
init();
yylex();
printf("result:%ld" ,two_count * three_count);
}
``````
``````aabbbaab
^
``````

``````         &anchor  = 1
digits   = '0123456789'
pat      = (any('+-') . sign) (span(digits) . val)
output   = '         freq     = 0'
output   = '         sat      = table(1000,500)'
output   = '         sat<0>   = 1'
output   = "         define('hash(val)')    :(beg)"
output   = 'hash     freq     = freq + val'
output   = '         sat<freq> = sat<freq> + 1'
output   = '         eq(sat<freq>, 2)   :s(fin)f(return)'
output   = 'beg'

loop     input pat                   :f(fin)
sign '+'                    :s(out)f(min)
min      val      = -val
out      output   = '         hash(' val ')'       :(loop)
fin      output   = '                    :(beg)'
output   = 'fin      output = freq'
output   = 'end'
end
``````
``````>> 0:~ \$ cat input.txt | spitbol day2-com.snb > prog.snb
``````

``````         freq     = 0
sat      = table(1000,500)
sat<0>   = 1
define('hash(val)')    :(beg)
hash     freq     = freq + val
sat<freq> = sat<freq> + 1
eq(sat<freq>, 2)   :s(fin)f(return)
beg
hash(-14)
hash(15)
hash(9)
hash(19)
.........
hash(-114806)
:(beg)
fin      output = freq
end
``````

``````>> 0:~ \$ time spitbol prog.snb                                       << 02:27 <]
57538
0.33 real         0.32 user         0.00 sys
``````

``````         &anchor  = 1
digits   = '0123456789'
pat      = (any('+-') . sign) (span(digits) . val)
output   = '         lit      = table(1000,100)'
output   = '         sat      = table(1000,300)'
output   = '         sat<0>   = 1'
output   = '         lit<0>   = 0'
output   = "         define('hash(val,line)')    :(beg)"
output   = 'hash     freq     = freq + val'
output   = '         sat<freq> = sat<freq> + 1'
output   = '         eq(sat<freq>, 2)   :s(n)'
output   = '         lit<freq> = line   :(return)'
output   = 'n        cur = line    :(fin)'
output   = 'beg'

loop     input pat                   :f(fin)
line     = line + 1
sign '+'                    :s(out)f(min)
min      val      = -val
out      output   = '         hash(' val ', ' line ')'  :(loop)
fin      output   = '         pass = pass + 1      :(beg)'
output   = "fin      output = freq 'p' (pass + 1) 'l' lit<freq> 'c' cur "
output   = 'end'
end
``````

``````>> 0:~ \$ time spitbol prog.snb                                       << 03:00 <]
57538p136l426c301
0.83 real         0.83 user         0.00 sys
``````

``````>> 0:~ \$ time spitbol prog.snb                                       << 03:44 <]
57538p136l426c301
0.16 real         0.15 user         0.00 sys
``````

``````>> 0:~ \$ time spitbol prog.snb                                       << 03:49 <]
57538
0.05 real         0.04 user         0.00 sys
``````

1 遍历2次 先找最大的x y 再用数组计算重复

2 遍历1次 用类似vector的结构计算重复

3 遍历1次 生成所有的 (x . y) 然后排序并计算重复

3-1

``````
%{
#include <math.h>

int left,top,width,height;

int max_x = 0 ,max_y = 0 ,result = 0 ,stage = 1;

void update_max(){
int x = left + width;
int y = top + height;
if(x > max_x) max_x = x;
if(y > max_y) max_y = y;
}
char* count_array;

void update_count(){
for(int i = 0 ; i< height ; i++){
for(int j = 0; j < width ; j++){
int index = (top+i)*max_x + left+j;
if(count_array[index] <=2) count_array[index]++;
}
}
left=top=width=height=0;
}

%}

%x FIRST FIRST_ID FIRST_LEFT FIRST_TOP FIRST_WIDTH FIRST_HEIGHT

%x SECOND SECOND_ID SECOND_LEFT SECOND_TOP SECOND_WIDTH SECOND_HEIGHT

%%

if ( stage ==1 ) BEGIN(FIRST);
else BEGIN(SECOND);

<FIRST>{

#[0-9]+  {}
@        {BEGIN(FIRST_LEFT);}

<FIRST_LEFT>[0-9]+  {left = atoi(yytext);}
<FIRST_LEFT>,  {BEGIN(FIRST_TOP);}

<FIRST_TOP>[0-9]+  {top = atoi(yytext);}
<FIRST_TOP>:  {BEGIN(FIRST_WIDTH);}

<FIRST_WIDTH>[0-9]+  {width = atoi(yytext);}
<FIRST_WIDTH>x  {BEGIN(FIRST_HEIGHT);}

<FIRST_HEIGHT>[0-9]+  {height = atoi(yytext);}

<*>[ \t]+   /* eat up whitespace */

<FIRST_HEIGHT>\n       { update_max(); BEGIN(FIRST);}
.        printf( "Unrecognized character: %s\n", yytext );
<<EOF>>   {yyterminate();}
}

<SECOND>{

#[0-9]+  {}
@        {BEGIN(SECOND_LEFT);}

<SECOND_LEFT>[0-9]+  {left = atoi(yytext);}
<SECOND_LEFT>,  {BEGIN(SECOND_TOP);}

<SECOND_TOP>[0-9]+  {top = atoi(yytext);}
<SECOND_TOP>:  {BEGIN(SECOND_WIDTH);}

<SECOND_WIDTH>[0-9]+  {width = atoi(yytext);}
<SECOND_WIDTH>x  {BEGIN(SECOND_HEIGHT);}

<SECOND_HEIGHT>[0-9]+  {height = atoi(yytext);}

<*>[ \t]+   /* eat up whitespace */

<SECOND_HEIGHT>\n       { update_count(); BEGIN(SECOND);}
.        printf( "Unrecognized character: %s\n", yytext );
<<EOF>>   {yyterminate();}
}

%%

int main( int argc, char **argv ){

++argv, --argc;  /* skip over program name */
stage = 1;
while(stage < 3){
if ( argc > 0 )
yyin = fopen( argv[0], "r" );
else
yyin = stdin;

yylex();
if(stage == 1){
count_array = (char*)malloc(max_x* max_y);
if( ! count_array ){
printf("malloc error \n"); exit(1);
}
for (int i = 0; i < max_y; i++)
for (int j = 0; j < max_x; j++) count_array[ i*max_x + j] = 0;

}else{
for (int i = 0; i < max_y; i++)
for (int j = 0; j < max_x; j++) if(count_array[i*max_x + j] >=2) result++;
}
stage++;
}
free(count_array);
printf("max_x:%d  max_y:%d result:%d" ,max_x,max_y,result);
}

``````
``````\$ time ./a.out test.txt
max_x:999  max_y:999 result:119572
real    0m0.083s
user    0m0.080s
sys     0m0.000s
``````

3-2

``````
%{
#include <math.h>

int MAX = 0xFFFFFFFF;

int left,top,width,height , id = 0;

int max_x = 0 ,max_y = 0 ,result = 0 ,stage = 1,lines = 0;

void update_max(){
int x = left + width;
int y = top + height;
if(x > max_x) max_x = x;
if(y > max_y) max_y = y;
}
int* count_array;
int* id_and_sum ;
int* id_and_count ;

void update_count(){

id_and_sum[id] = height * width;

for(int i = 0 ; i< height ; i++){
for(int j = 0; j < width ; j++){
int index = (top+i)*max_x + left+j;
if(count_array[index] == 0) {
count_array[index] = id;
}else{
count_array[index] = MAX;
}
}
}
left=top=width=height=id=0;
}

%}

%x FIRST FIRST_ID FIRST_LEFT FIRST_TOP FIRST_WIDTH FIRST_HEIGHT

%x SECOND SECOND_ID SECOND_LEFT SECOND_TOP SECOND_WIDTH SECOND_HEIGHT

%%

if ( stage ==1 ) BEGIN(FIRST);
else BEGIN(SECOND);

<FIRST>{

#  {BEGIN(FIRST_ID);}
<FIRST_ID>[0-9]+   {id=atoi(yytext);lines=id; }
<FIRST_ID>@        {BEGIN(FIRST_LEFT);}

<FIRST_LEFT>[0-9]+  {left = atoi(yytext);}
<FIRST_LEFT>,  {BEGIN(FIRST_TOP);}

<FIRST_TOP>[0-9]+  {top = atoi(yytext);}
<FIRST_TOP>:  {BEGIN(FIRST_WIDTH);}

<FIRST_WIDTH>[0-9]+  {width = atoi(yytext);}
<FIRST_WIDTH>x  {BEGIN(FIRST_HEIGHT);}

<FIRST_HEIGHT>[0-9]+  {height = atoi(yytext);}

<*>[ \t]+   /* eat up whitespace */

<FIRST_HEIGHT>\n       { update_max(); BEGIN(FIRST);}
.        printf( "Unrecognized character: %s\n", yytext );
<<EOF>>   {yyterminate();}
}

<SECOND>{

#  {BEGIN(SECOND_ID);}
<SECOND_ID>[0-9]+   {id=atoi(yytext); }
<SECOND_ID>@        {BEGIN(SECOND_LEFT);}

<SECOND_LEFT>[0-9]+  {left = atoi(yytext);}
<SECOND_LEFT>,  {BEGIN(SECOND_TOP);}

<SECOND_TOP>[0-9]+  {top = atoi(yytext);}
<SECOND_TOP>:  {BEGIN(SECOND_WIDTH);}

<SECOND_WIDTH>[0-9]+  {width = atoi(yytext);}
<SECOND_WIDTH>x  {BEGIN(SECOND_HEIGHT);}

<SECOND_HEIGHT>[0-9]+  {height = atoi(yytext);}

<*>[ \t]+   /* eat up whitespace */

<SECOND_HEIGHT>\n       { update_count(); BEGIN(SECOND);}
.        printf( "Unrecognized character: %s\n", yytext );
<<EOF>>   {yyterminate();}

}

%%

int main( int argc, char **argv ){

++argv, --argc;  /* skip over program name */
int i = 1;
while(i < 3){
if ( argc > 0 )
yyin = fopen( argv[0], "r" );
else
yyin = stdin;
stage = i;
yylex();
if(stage == 1){

id_and_sum = (int*)malloc(sizeof(int)*(lines+1));
if( ! id_and_sum ){
printf("malloc error \n"); exit(1);
}
for (int i = 0; i < lines+1; i++)id_and_sum[i] = 0;

id_and_count = (int*)malloc(sizeof(int)*(lines+1));
if( ! id_and_count ){
printf("malloc error \n"); exit(1);
}
for (int i = 0; i < lines+1; i++)id_and_count[i] = 0;

count_array = (int*)malloc(sizeof(int)*max_x* max_y);
if( ! count_array ){
printf("malloc error \n"); exit(1);
}
for (int i = 0; i < max_y; i++)
for (int j = 0; j < max_x; j++) count_array[ i*max_x + j] = 0;

}else{
for (int i = 0; i < max_y; i++)
for (int j = 0; j < max_x; j++){
int index = i*max_x + j;
int id = count_array[index];
if( id> 0 && id != MAX) id_and_count[id]++;
}
for(int i = 1;i<lines+1 ;i++){
// printf("%d:%d %d\n",i, id_and_sum[i],id_and_count[i]);
if(id_and_count[i] == id_and_sum[i]){
printf("found id:%d\n",i);
}
}
}
i++;
}
free(count_array);free(id_and_sum); free(id_and_count);
}

``````
``````\$ time ./a.out test.txt
found id:775

real    0m0.099s
user    0m0.090s
sys     0m0.000s
``````

2-2

``````%{
#include <math.h>
#include <string.h>

int lines = 0, length = 0;
int stage = 1;
char* source;
char* temp ;
char* comp ;

void calc(){

for(int i = 0; i< lines -1 ;i++){
prep_data(i+1);
calc_data(i);

}
}

void prep_data(int line){
for( int i = line ; i < lines;i++ ){
strcpy(temp+(length+1)*i, source+(length+1)*i);
comp[i] = 0;
}
}

void calc_data(int start_line){

for(int cur_line = start_line + 1 ; cur_line < lines ; cur_line ++){

int int_rep = length /8;
int rem = length - 8 * int_rep;
for(int i = 0; i< int_rep ; i++){

if(i!=0 && comp[cur_line] < i*8 -1)continue;
int s_add = start_line*(length+1)+i*8;
int t_add = cur_line*(length+1)+i*8;
long* ps = (long*)(source + s_add);
long* ts = (long*)(temp + t_add);
char* tcs = (char*)ts;
*ts = *ps ^ *ts;

int t_count = 0;
for(int ii = 0;ii<8;ii++){
if(*(tcs+ii) == 0) t_count++;
}
comp[cur_line] += t_count;
}

for(int i = 0; i< rem ; i++){
if(comp[cur_line] < int_rep*8+i-1)continue;
int p_add = start_line*(length+1)+int_rep*8 + i;
int t_add = cur_line*(length+1)+int_rep*8 + i;
char* ps = source + p_add;
char* ts = temp + t_add;
*ts = *ps ^ *ts;
if(*ts == 0)comp[cur_line]++;
}

if(comp[cur_line] == length -1){
printf("start:%d  current:%d start_s:%s",start_line,cur_line,source+(length+1)*start_line);
}
}
}

%}

%x  FIRST  SECOND

%%

if ( stage ==1 ) BEGIN(FIRST);
else BEGIN(SECOND);

<FIRST>{

\n       { lines ++ ; }
[a-z]+   {
int len = strlen(yytext);

if(length == 0)  length = len;
else if(length != len){
printf("line length error:%d  %s",lines,yytext);
}
}
<<EOF>>   {yyterminate();}
}

<SECOND>{
\n       { lines ++ ; }
[a-z]+   {
strcpy(source+(length+1)*lines,yytext );

}
}

%%

int main( int argc, char **argv ){

++argv, --argc;  /* skip over program name */
int i = 1;
while(i < 3){
if ( argc > 0 )
yyin = fopen( argv[0], "r" );
else
yyin = stdin;
stage = i;
yylex();
if(stage == 1){
source = (char*)malloc(lines * (length +1));
temp = (char*)malloc(lines * (length +1));
comp = (char*)malloc(lines);
lines = 0;
}else{
calc();
}
i++;
}
free(source); free(temp); free(comp);
}

``````
``````\$ time ./a.out test.txt
start:96  current:204 start_s:cnjxoritwzhvbosyewrmqhgkul
real    0m0.032s
user    0m0.030s
sys     0m0.000s

``````