aocc22

uppgc.c (5038B)

---

 #include "common.h"
 #include <strings.h>
 
 #define DEFAULT_BOARD_SIZE 250000000
 #define MAXJ 1000000000000L
 //#define MAXJ 2022L
 
 typedef struct {
   size_t nalloc;
   long cmax;
   uint8_t *bd;
 } board;
 
 typedef struct {
   size_t height;
   uint8_t bd[4];
 } piece;
 
 static inline int isset(uint8_t row, size_t i) {
   assert(i < 7);
   if ((row & (0x40 >> i)) != 0)
     return 1;
   return 0;
 }
 
 static inline void set(uint8_t *row, size_t i) {
   assert(i < 7);
   *row |= (0x40 >> i);
 }
 
 void init_board(board *b) {
   b->nalloc = DEFAULT_BOARD_SIZE;
   b->cmax = -1;
   b->bd = calloc(b->nalloc, sizeof(*b->bd));
 }
 
 static inline void print_line(uint8_t v) {
   size_t j;
   for (j = 0; j < 7; j++) {
     if (isset(v, j)) {
       printf("#");
     } else {
       printf(".");
     }
   }
 }
 
 void print_piece(piece p) {
   printf("piece> h = %zu\n", p.height);
   size_t i;
   for (i = 0; i < p.height; i++) {
     print_line(p.bd[i]);
     printf("\n");
   }
 }
 
 void print_board(board *b) {
   int i;
   printf("+-------+\n");
   for (i = 0; i < b->cmax + 2; i++) {
     printf("|");
     print_line(b->bd[i]);
     printf("|\n");
   }
 }
 
 void print_board_with_piece(board *b, piece *p, long height) {
   size_t i;
   printf("+-------+\n");
   for (i = 0; i < height + 4; i++) {
     uint8_t d = 0;
     if (i < b->nalloc) {
       d |= b->bd[i];
     }
     if (i >= height && (i - height) < p->height) {
       d |= p->bd[i - height];
     }
     printf("|");
     print_line(d);
     printf("|\n");
   }
 }
 
 #define SWAP(x, y) (x ^= y ^= x ^= y)
 
 void read_pieces(piece *pcs, size_t npcs, char *filename) {
   char **lines;
   size_t nlines = readlines(&lines, filename);
   size_t cp = 0;
   size_t cpi = 0;
   size_t i, j;
 
   for (i = 0; i < npcs; i++)
     memset(pcs[i].bd, 0, 4);
 
   for (i = 0; i < nlines; i++) {
     if (strlen(lines[i]) < 2) {
       pcs[cp].height = cpi;
       cp++;
       cpi = 0;
       continue;
     }
     for (j = 0; j < strlen(lines[i]); j++) {
       if (lines[i][j] == '#') {
         set(&(pcs[cp].bd[cpi]), j);
       }
     }
     cpi++;
   }
   pcs[cp].height = cpi;
 
   for (i = 0; i < npcs; i++) {
     for (j = 0; j < pcs[i].height / 2; j++) {
       SWAP(pcs[i].bd[j], pcs[i].bd[pcs[i].height - 1 - j]);
     }
     for (j = 0; j < pcs[i].height; j++)
       pcs[i].bd[j] >>= 2;
   }
 }
 
 static inline void r_push_piece(piece *p, board *b, long h) {
   size_t i;
   for (i = 0; i < p->height; i++) {
     if ((p->bd[i] & 0x01) != 0)
       return; // cannot push
     if (((p->bd[i] >> 1) & b->bd[h + i]) != 0)
       return;
   }
 
   // pushable
   for (i = 0; i < p->height; i++)
     p->bd[i] >>= 1;
 }
 
 static inline void l_push_piece(piece *p, board *b, long h) {
   size_t i;
   for (i = 0; i < p->height; i++) {
     if ((p->bd[i] & 0x40) != 0)
       return; // cannot
     if (((p->bd[i] << 1) & b->bd[h + i]) != 0)
       return;
   }
 
   // pushable
   for (i = 0; i < p->height; i++)
     p->bd[i] <<= 1;
 }
 
 static inline int can_move_up(piece *p, board *b, long cheight) {
   size_t i;
   if (cheight <= 0)
     return 0;
   for (i = 0; i < p->height; i++) {
     if ((b->bd[i + cheight - 1] & p->bd[i]) != 0)
       return 0;
   }
   return 1;
 }
 
 static inline void draw_piece(piece *p, board *b, long height) {
   size_t i;
   for (i = 0; i < p->height; i++) {
     b->bd[i + height] |= p->bd[i];
   }
   //  printf("> drawing piece of h %zu at h %ld\n", p->height, height);
   long nmax = height + p->height - 1;
   b->cmax = nmax > b->cmax ? nmax : b->cmax;
 }
 
 static inline void try_lr_move(piece *p, board *b, long h, char *moves,
                                size_t nmoves, size_t *i) {
   if (moves[*i % nmoves] == '>') {
     r_push_piece(p, b, h);
   } else {
     l_push_piece(p, b, h);
   }
   (*i)++;
 }
 
 static inline void drop_piece(board *b, piece p, char *moves, size_t nmoves,
                               size_t *i) {
   long cheight = b->cmax + 4;
   try_lr_move(&p, b, cheight, moves, nmoves, i);
   while (can_move_up(&p, b, cheight)) {
     cheight--;
     try_lr_move(&p, b, cheight, moves, nmoves, i);
   }
 
   draw_piece(&p, b, cheight);
 }
 
 static inline long chomp_board(board *b) {
   long chomping = DEFAULT_BOARD_SIZE / 2;
   b->cmax -= chomping;
   memcpy(b->bd, &(b->bd[chomping]), chomping);
   bzero(&(b->bd[chomping]), chomping);
   return chomping;
 }
 
 int main(int argc, char **argv) {
   char **lines;
   size_t nlines = readlines(&lines, "input");
   printf("#lines: %lu\n", nlines);
 
   assert(nlines == 1);
 
   char *moves = lines[0];
   size_t nmoves = strlen(moves);
   if (moves[nmoves - 1] == '\n')
     nmoves--;
 
   printf("#moves: %zu\n", nmoves);
 
   board b;
   init_board(&b);
 
   piece pcs[5];
   read_pieces(pcs, 5, "pieces");
 
   size_t i;
   for (i = 0; i < 5; i++) {
     print_piece(pcs[i]);
   }
 
   i = 0;
   size_t j;
   long chompd = 0;
   for (j = 0; j < MAXJ; j++) {
     drop_piece(&b, pcs[j % 5], moves, nmoves, &i);
     if (b.cmax + 5 > DEFAULT_BOARD_SIZE)
       chompd += chomp_board(&b);
     if ((j % (MAXJ / 1000)) == 0)
       printf("%lu\n", j / (MAXJ / 1000));
   }
   printf("(%zu): %lu\n", j, chompd + b.cmax + 1);
   printf("chompd %lu\n", chompd);
 }