Advent of Code 2018


#1

https://adventofcode.com/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

我的 Emacs Lisp 解答:


#3

挺好玩,贴一个 day 1 的 Clojure 解答。有空再跟进整理

;; 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")
  |> IO.read(:all)
  |> 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).()

#4

不清楚为什么很慢,我的代码并没有什么「交互」。此外要注意每个人的输入都不同。


#5

用 SNOBOL4 写的。

         &anchor  = 1
         digits   = '0123456789'
         freq     = 0
         pat      = (any('+-') . sign) (span(digits) . val)
loop     input pat                   :f(fin)
         sign '+'                    :s(add)f(min)
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)
         sign '+'                    :s(add)f(min)
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

#6

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();
}

执行时间依赖于一开始hash的大小


$ 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


#7

我觉得1-2应该增加点难度

找出发生重复 所在 的 行


#8

你 这 人 说 话 怎 么 带 空 格

风 评 被 害 不 可 避


#9

ん?(察觉)


#10

2

谁能在一行的中间中断呢?也就是说找到一个2和一个3之后就不继续查找当前行的剩余部分了。

%{
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);
}

#11
aabbbaab
     ^

这种算沒有 2 个同時出現字符而且沒有 3 个同時出现。而是两组 4 个同時出現。很明顯如果到 ^ 的位置就停下得到的就是錯誤的答案。


#12

这个算我错了

即使能够在余下的字符中搜索,效率也会很低

那就看看 1-2 的吧


#13

为了解決 IO 的问題我把 day1-2 改成了个编译器:

         &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

#14

第一个 所对应的行

重复了几遍输入

最后停止的行


#15
         &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

注:p -> pass l -> line c -> current


#16

只不过 时间翻了2倍多 而已


#17

你要说用 C 和个解释运行还经常 GC 的语言比,那当然没法比

另外我把 hash 调大到 100000 后,看來是我谦虛了,还能把 C 吊起來打。

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

#18

对于 day 3

现在想到了3个方法

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

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

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

觉得第一个最容易实现 效率也最高

原来 2-2 比 3-1 要难


#19

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

#20

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