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 解答：
2 个赞
挺好玩，贴一个 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).()
1 个赞
不清楚为什么很慢，我的代码并没有什么「交互」。此外要注意每个人的输入都不同。
用 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
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();
}
执行时间依赖于一开始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
我觉得1-2应该增加点难度
找出发生重复 所在 的 行
你 这 人 说 话 怎 么 带 空 格
风 评 被 害 不 可 避
2 个赞
ん？（察觉）
1 个赞
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);
}
aabbbaab
^
这种算沒有 2 个同時出現字符而且沒有 3 个同時出现。而是两组 4 个同時出現。很明顯如果到 ^ 的位置就停下得到的就是錯誤的答案。
这个算我错了
即使能够在余下的字符中搜索，效率也会很低
那就看看 1-2 的吧
为了解決 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
第一个 所对应的行
重复了几遍输入
最后停止的行
&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
只不过 时间翻了2倍多 而已
你要说用 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
对于 day 3
现在想到了3个方法
1 遍历2次 先找最大的x y 再用数组计算重复
2 遍历1次 用类似vector的结构计算重复
3 遍历1次 生成所有的 (x . y) 然后排序并计算重复
觉得第一个最容易实现 效率也最高
原来 2-2 比 3-1 要难
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