started at ; stage 2 at ; ended at
I like 2D decision problems now, so let's find trax wins. submissions may be written in any language.
trax is an abstract strategy game invented in new zealand (!) in 1980, the goal of which is to build either a loop or a long line in one's own colour out of tiles. this is done by taking turns placing either of the two kinds of tile, which each have both colours of line on them:
these tiles can be rotated arbitrarily, so there are 6 total orientations:
the goal is to make either a loop, which is fairly self-explanatory:
or a line, which connects one side of the board to the other (vertically or horizontally), provided it spans at least 8 rows/columns:
note that this is not a line, because the ends are bent away instead of touching the sides:
and this is also not a line, because a separate outcropping means the line is not spanning the full width of the board:
your goal will be to recognize whether or not a trax position represents a finished game, by way of containing either a loop or a line. you do not have to determine which player won, which means that the colours of any board can be switched to get an equivalent position:
accordingly, the input format does not specify the colour of the tiles. using only the characters +, /, \, space, and newline, a grid with lines of equal length is formed in the customary manner.
these inputs describe exactly 2 equivalent trax positions with opposite colours.
the + character represents one of the cross-shaped tiles, while / and \ are both orientations of the curved tiles. for example, the shapes shown side-by-side above would be described like so:
/\+
\
if you need further examples, you may simply copy any of the diagrams in this spec to get their textual representations.
your challenge, given a string representing a valid trax position as described above, is to decide whether the game is still continuing, or if there is a loop or line on the board (thus meaning it has ended). as any language is allowed, there is no fixed API.
the rules of trax place some constraints on which positions are reachable. as you may assume that your input is a valid position, these rules may be of some interest to you.
firstly, the board must always remain connected. tiles must be placed next to an existing tile and mismatching colours may not touch, so this is invalid:
secondly, the board can never be left in a state where there are two or more edges of the same colour entering into the same empty space, like this:
if this happened during a game, the player would be forced to play an additional tile in the same move that fills the gap:
as such, your input will never have situations like this. (not that it matters very much...)
note that it is possible for multiple loops/lines to be created in one move, even for both players at once! (if you're curious, this always makes the person making the move win)
victory by loop.
victory by line.
game ongoing.
you can download all the entries
written by Olivia
submitted at
1 like
written by Dolphy
submitted at
1 like
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 | import antigravity # :O from copy import deepcopy as shallow_copy # >:D MALE = 0 ASEXUAL = 1 FEMALE = 2 POLYGENDER = 3 CIS = 0 TRANS = 1 HE_HIM = 0 SHE_HER = 1 THEY_THEM = 2 def transition(gender): return (gender + 2) % 4 class Queer: def __init__(self, femininity, masculinity, t) -> None: self.femininity = femininity self.masculinity = masculinity self.down_gender_identity = int(POLYGENDER in femininity) self.up_gender_identity = int(ASEXUAL in femininity) self.left_gender_identity = int(FEMALE in femininity) self.right_gender_identity = int(MALE in femininity) self.pronouns = t plus_1 = Queer([POLYGENDER, ASEXUAL], [FEMALE, MALE], HE_HIM) plus_2 = Queer([FEMALE, MALE], [POLYGENDER, ASEXUAL], HE_HIM) forward_1 = Queer([FEMALE, ASEXUAL], [MALE, POLYGENDER], SHE_HER) forward_2 = Queer([MALE, POLYGENDER], [FEMALE, ASEXUAL], SHE_HER) backward_1 = Queer([MALE, ASEXUAL], [FEMALE, POLYGENDER], THEY_THEM) backward_2 = Queer([FEMALE, POLYGENDER], [MALE, ASEXUAL], THEY_THEM) # Wave function collapse! class Tile: def __init__(self, grid) -> None: self.possible_genders = [] self.gender = None self.grid = grid self.x = 0 self.y = 0 self.gay_checks = [False, False] def collapse(self, abusive_parents=False): if self.gender: return if len(self.possible_genders) == 0: return genders = self.possible_genders right = None if self.x == len(self.grid[0]) - 1 else self.grid[self.y][self.x + 1] down = None if self.y == len(self.grid) - 1 else self.grid[self.y + 1][self.x] left = None if self.x == 0 else self.grid[self.y][self.x - 1] up = None if self.y == 0 else self.grid[self.y - 1][self.x] if abusive_parents: self.gender = self.possible_genders[0] if left: left.collapse() if right: right.collapse() if up: up.collapse() if down: down.collapse() return if left and left.gender: genders = [gender for gender in genders if gender.left_gender_identity == left.gender.right_gender_identity] if right and right.gender: genders = [gender for gender in genders if gender.right_gender_identity == right.gender.left_gender_identity] if up and up.gender: genders = [gender for gender in genders if gender.up_gender_identity == up.gender.down_gender_identity] if down and down.gender: genders = [gender for gender in genders if gender.down_gender_identity == down.gender.up_gender_identity] self.possible_genders = genders if len(genders) == 0: raise Exception("B-but y-you said t-that all entries w-would be va-valid :(") if len(genders) == 1: self.gender = genders[0] if left: left.collapse() if right: right.collapse() if up: up.collapse() if down: down.collapse() def make_possible_genders(self, strgrid, x, y): self.x = x self.y = y if strgrid[y][x] == '+': self.possible_genders.append(plus_1) self.possible_genders.append(plus_2) elif strgrid[y][x] == '/': self.possible_genders.append(forward_1) self.possible_genders.append(forward_2) elif strgrid[y][x] == '\\': self.possible_genders.append(backward_1) self.possible_genders.append(backward_2) def get_next_direction_to_move(tile, current_dir, color): inv_dir = transition(current_dir) dirs = [] if color == TRANS: dirs = shallow_copy(tile.gender.femininity) else: dirs = shallow_copy(tile.gender.masculinity) dirs = [d for d in dirs if d != inv_dir] return dirs[0] def get_wall_hit(grid, current_dir, color, x, y, w, h): i_cant_find_name_for_this_variable = False while True: tile = grid[y][x] if not tile.gender: return None if i_cant_find_name_for_this_variable: current_dir = get_next_direction_to_move(tile, current_dir, color) if current_dir == MALE and x == w - 1: return current_dir elif current_dir == FEMALE and x == 0: return current_dir elif current_dir == ASEXUAL and y == 0: return current_dir elif current_dir == POLYGENDER and y == h - 1: return current_dir if current_dir == MALE: x += 1 elif current_dir == FEMALE: x -= 1 elif current_dir == ASEXUAL: y -= 1 elif current_dir == POLYGENDER: y += 1 i_cant_find_name_for_this_variable = True def check_for_straight_wins(grid): height = len(grid) width = len(grid[0]) for i in range(height): tile = grid[i][0] if not tile.gender: continue x = 0 y = i start_dir = None if tile.gender.pronouns == HE_HIM: start_dir = MALE elif tile.gender.pronouns == SHE_HER: start_dir = ASEXUAL elif tile.gender.pronouns == THEY_THEM: start_dir = POLYGENDER color = int(start_dir in tile.gender.femininity) if start_dir is not None: wall_dir = get_wall_hit(grid, start_dir, color, x, y, width, height) if wall_dir == MALE: return True for i in range(width): tile = grid[0][i] if not tile.gender: continue x = i y = 0 start_dir = None if tile.gender.pronouns == HE_HIM: start_dir = POLYGENDER elif tile.gender.pronouns == SHE_HER: start_dir = FEMALE elif tile.gender.pronouns == THEY_THEM: start_dir = MALE color = int(start_dir in tile.gender.femininity) if start_dir is not None: wall_dir = get_wall_hit(grid, start_dir, color, x, y, width, height) if wall_dir == POLYGENDER: return True return False def check_gay(grid, w, h, x, y, color): tile = grid[y][x] if not tile.gender: return False if tile.gay_checks[color]: return False dirs = None if color == TRANS: dirs = tile.gender.femininity else: dirs = tile.gender.masculinity def trans(_grid, _x, _y, _startdir): _tile = _grid[_y][_x] if not _tile.gender: return False if _tile.gay_checks[color]: return False _dir = _startdir i_cant_find_name_for_this_variable = False while not _tile.gay_checks[color]: _tile.gay_checks[color] = True if i_cant_find_name_for_this_variable: _dir = get_next_direction_to_move(_tile, _dir, color) if _dir == MALE and _x == w - 1: return False elif _dir == FEMALE and _x == 0: return False elif _dir == ASEXUAL and _y == 0: return False elif _dir == POLYGENDER and _y == h - 1: return False if _dir == MALE: _x += 1 elif _dir == FEMALE: _x -= 1 elif _dir == ASEXUAL: _y -= 1 elif _dir == POLYGENDER: _y += 1 i_cant_find_name_for_this_variable = True _tile = _grid[_y][_x] if not _tile.gender: return False return True if trans(grid, x, y, dirs[0]): return True tile.gay_checks[color] = False return trans(grid, x, y, dirs[1]) def check_for_gay_wins(grid): height = len(grid) width = len(grid[0]) for y in range(height): for x in range(width): if check_gay(grid, width, height, x, y, TRANS) or check_gay(grid, width, height, x, y, CIS): return True return False def parse(input_grid): input_grid = input_grid.split('\n') height = len(input_grid) width = max([len(line) for line in input_grid]) for y in range(height): input_grid[y] += (width - len(input_grid[y])) * ' ' grid = [] for y in range(height): grid.append([]) for x in range(width): grid[-1].append(Tile(grid)) grid[-1][-1].make_possible_genders(input_grid, x, y) for y in range(height): for x in range(width): if len(grid[y][x].possible_genders) != 0: grid[y][x].collapse(True) return grid def are_ya_winnin_son(board): board = parse(board) return check_for_straight_wins(board) or check_for_gay_wins(board) |
written by luatic
submitted at
0 likes
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | from sys import stdin M = { '+' : ((1, 0), (0, 1)), '/' : ((0,-1), (-1,0)), '\\': ((0, 1), (1, 0)), } L = tuple(map(str.rstrip, stdin.readlines())) W, H = S = max(map(len, L)), len(L) def I(p): x, y = p return y in range(H) and x in range(len(L[y])) and L[y][x] in M def D(v, w): return sum(x * y for x, y in zip(v, w)) def F(p, v): x, y = p m = M[L[y][x]] w = tuple(map(lambda r: D(r, v), m)) return (x + w[0], y + w[1]), w def P(p, v): o = p while I(p): p, v = F(p, v) if abs(D(o, v) - D(p, v)) >= abs(D(S, v)) >= 8: exit(1) for x in range(W): P((x, 0), (0, 1)) P((x, H-1), (0, -1)) for y in range(H): P((0, y), (1, 0)) P((W-1, y), (-1, 0)) def C(p): for v in ((0, 1), (0, -1), (1, 0), (-1, 0)): q = set() while I(p): q.add(p) p, v = F(p, v) if p in q: exit(1) for y, l in enumerate(L): for x in range(len(l)): C((x, y)) |
written by olus2000
submitted at
1 like
written by moshikoi
submitted at
1 like
1 2 3 4 5 6 | add_executable(main)
target_sources(main
PUBLIC
FILE_SET modules TYPE CXX_MODULES
FILES main.cpp tile.cpp traveler.cpp)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 | module; #include <format> #include <fstream> #include <generator> #include <iostream> #include <print> #include <string> export module main; import tile; import traveler; std::generator<std::string const &> lines(std::istream &is) { std::string line; while (std::getline(is, line)) { co_yield line; } co_return; } bool has_victory(std::vector<std::vector<Tile>> &grid) { auto const width = std::ranges::max(grid | std::views::transform([](auto const &row) { return row.size(); })); auto const height = grid.size(); for (int row = 0; row < grid.size(); ++row) { for (int col = 0; col < grid[row].size(); ++col) { Tile &tile = grid[row][col]; if (tile.connection(Direction::North) != Direction::North) { Traveler traveler{row, col, Direction::South}; traveler.travel(grid); if (traveler.row == row && traveler.col == col) { return true; } if (traveler.direction == Direction::South && height > 7 && traveler.row - row == height) { return true; } } if (tile.connection(Direction::West) != Direction::West) { Traveler traveler{row, col, Direction::East}; traveler.travel(grid); if (traveler.row == row && traveler.col == col) { return true; } if (traveler.direction == Direction::East && width > 7 && traveler.col - col == width) { return true; } } } } return false; } int entry(std::istream &is) { std::vector<std::vector<Tile>> grid; for (auto const &line : lines(is)) { std::vector<Tile> row; for (char ch : line) { switch (ch) { case ' ': row.push_back(Tile::Blank); break; case '+': row.push_back(Tile::Cross); break; case '/': row.push_back(Tile::Slash); break; case '\\': row.push_back(Tile::Backslash); break; default: throw std::runtime_error{std::format("Invalid character '{}'", ch)}; } } grid.push_back(row); } if (has_victory(grid)) { std::println("Victory"); } else { std::println("No victory"); } return 0; } int main(int argc, char const **argv) { try { if (argc < 2) { entry(std::cin); } else { std::ifstream is(argv[1]); entry(is); } } catch (std::exception ex) { std::println(std::cerr, "{}", ex.what()); return 1; } } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 | module; #include <cstdint> #include <utility> export module tile; export enum class Direction : std::uint8_t { East = 0b00, North = 0b01, West = 0b10, South = 0b11, }; export Direction opposite(Direction direction) { switch (direction) { case Direction::East: return Direction::West; case Direction::North: return Direction::South; case Direction::West: return Direction::East; case Direction::South: return Direction::North; default: std::unreachable(); } } export class Tile { public: static Tile const Blank; static Tile const Cross; static Tile const Slash; static Tile const Backslash; Direction connection(Direction entry) const; void remove_connection(Direction entry); bool empty() const { return good != 0b00; } private: std::underlying_type_t<Direction> direction : 2; std::uint8_t good : 2; Tile(Direction east) : direction{std::to_underlying(east)}, good{0b11} {} }; Tile const Tile::Blank{Direction::East}; Tile const Tile::Cross{Direction::West}; Tile const Tile::Slash{Direction::South}; Tile const Tile::Backslash{Direction::North}; Direction Tile::connection(Direction entry) const { Direction const exit = static_cast<Direction>(direction ^ std::to_underlying(entry)); bool const is_good = (good >> (entry == Direction::East || exit == Direction::East)) & 1; return is_good ? exit : entry; } void Tile::remove_connection(Direction entry) { Direction const exit = static_cast<Direction>(direction ^ std::to_underlying(entry)); good &= ~(1 << (entry == Direction::East || exit == Direction::East)); } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | module; #include <vector> export module traveler; import tile; export class Traveler { public: int row; int col; Direction direction; Traveler(int row, int col, Direction direction) : row{row}, col{col}, direction{direction} {} void travel(std::vector<std::vector<Tile>> &grid); private: bool step(std::vector<std::vector<Tile>> &grid); }; void Traveler::travel(std::vector<std::vector<Tile>> &grid) { while (0 <= row && row < grid.size() && 0 <= col && col < grid[row].size()) { if (!step(grid)) { break; } } } bool Traveler::step(std::vector<std::vector<Tile>> &grid) { Tile ¤t_tile = grid[row][col]; Direction entry = opposite(direction); Direction const next = current_tile.connection(entry); if (entry == next) { return false; } current_tile.remove_connection(entry); direction = next; switch (direction) { case Direction::East: col += 1; break; case Direction::North: row -= 1; break; case Direction::West: col -= 1; break; case Direction::South: row += 1; break; default: std::unreachable(); } return true; } |
written by kimapr
submitted at
1 like
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 | ( // Code by olus2000 (UID: 339009650592710656) FALSE VALUE ENABLE-BUG BEGIN-STRUCTURE grid FIELD: grid.addr FIELD: grid.width FIELD: grid.height END-STRUCTURE BEGIN-STRUCTURE grid-cell CFIELD: grid-cell.type CFIELD: grid-cell.wseen CFIELD: grid-cell.rseen CFIELD: grid-cell.invert END-STRUCTURE 0 CONSTANT GRID-0 1 CONSTANT GRID-/ 2 CONSTANT GRID-\ 3 CONSTANT GRID-+ CREATE NULL-GRID-CELL grid-cell ALLOT GRID-0 NULL-GRID-CELL grid-cell.type C! FALSE NULL-GRID-CELL grid-cell.wseen C! FALSE NULL-GRID-CELL grid-cell.rseen C! : grid[] ( n n grid -- grid-cell ) >R 2DUP 2DUP 0< 0= SWAP 0< 0= AND SWAP R@ grid.height @ < AND SWAP R@ grid.width @ < AND 0= R> SWAP IF DROP 2DROP NULL-GRID-CELL EXIT THEN >R R@ grid.width @ * + grid-cell * R> grid.addr @ + ; 10 CONSTANT CHAR-LF 0 VALUE PARSED-GRID 0 VALUE PARSED-STR-ADDR 0 VALUE PARSED-STR-LEN 0 VALUE PARSED-WIDTH 0 VALUE PARSED-HEIGHT 0 VALUE PARSED-MINX 0 VALUE PARSED-MINY : PARSED-GRID-CELL-TYPE! ( char -- ) PARSED-WIDTH PARSED-MINX - PARSED-HEIGHT PARSED-MINY - PARSED-GRID grid[] DUP NULL-GRID-CELL = IF 1 ABORT" BONDAGE" THEN grid-cell.type C! ; : ENSURE-UNCHARA ( char -- char ) DUP CASE CHAR-LF OF ENDOF [CHAR] / OF ENDOF [CHAR] \ OF ENDOF [CHAR] + OF ENDOF BL OF ENDOF 1 ABORT" CHARA" ENDCASE ; : PARSE-GRID ( c-addr u grid -- ) TO PARSED-GRID TO PARSED-STR-LEN TO PARSED-STR-ADDR 0 PARSED-GRID grid.height ! 0 PARSED-GRID grid.width ! 0 TO PARSED-WIDTH 0 TO PARSED-HEIGHT PARSED-STR-LEN 0 ?DO PARSED-STR-ADDR I CHARS + C@ ENSURE-UNCHARA CASE CHAR-LF OF 0 TO PARSED-WIDTH PARSED-HEIGHT 1+ TO PARSED-HEIGHT ENDOF BL OF PARSED-WIDTH 1+ TO PARSED-WIDTH ENDOF PARSED-WIDTH 1+ DUP TO PARSED-WIDTH PARSED-GRID grid.width @ MAX PARSED-GRID grid.width ! PARSED-HEIGHT 1+ PARSED-GRID grid.height @ MAX PARSED-GRID grid.height ! ENDCASE LOOP PARSED-WIDTH TO PARSED-MINX PARSED-HEIGHT TO PARSED-MINY PARSED-GRID grid.width @ PARSED-GRID grid.height @ 2DROP 0 TO PARSED-WIDTH 0 TO PARSED-HEIGHT PARSED-STR-LEN 0 ?DO PARSED-STR-ADDR I CHARS + C@ CASE CHAR-LF OF 0 TO PARSED-WIDTH PARSED-HEIGHT 1+ TO PARSED-HEIGHT ENDOF BL OF PARSED-WIDTH 1+ TO PARSED-WIDTH ENDOF PARSED-WIDTH PARSED-HEIGHT PARSED-MINX PARSED-MINY 2DROP 2DROP PARSED-WIDTH PARSED-MINX MIN TO PARSED-MINX PARSED-HEIGHT PARSED-MINY MIN TO PARSED-MINY PARSED-WIDTH 1+ TO PARSED-WIDTH ENDCASE LOOP PARSED-MINX NEGATE PARSED-GRID grid.width +! PARSED-MINY NEGATE PARSED-GRID grid.height +! 0 TO PARSED-WIDTH 0 TO PARSED-HEIGHT ALIGN HERE PARSED-GRID grid.height @ PARSED-GRID grid.width @ * >R R@ grid-cell * ALLOT PARSED-GRID grid.addr ! R> 0 ?DO PARSED-GRID grid.addr @ I grid-cell * + >R GRID-0 R@ grid-cell.type C! FALSE R@ grid-cell.wseen C! FALSE R@ grid-cell.rseen C! 2 R> grid-cell.invert C! LOOP PARSED-STR-LEN 0 ?DO PARSED-STR-ADDR I CHARS + C@ ENSURE-UNCHARA CASE CHAR-LF OF 0 TO PARSED-WIDTH PARSED-HEIGHT 1+ TO PARSED-HEIGHT FALSE ENDOF [CHAR] / OF GRID-/ PARSED-GRID-CELL-TYPE! TRUE ENDOF [CHAR] \ OF GRID-\ PARSED-GRID-CELL-TYPE! TRUE ENDOF [CHAR] + OF GRID-+ PARSED-GRID-CELL-TYPE! TRUE ENDOF TRUE ENDCASE IF PARSED-WIDTH 1+ TO PARSED-WIDTH THEN LOOP ; BEGIN-STRUCTURE point FIELD: point.x FIELD: point.y END-STRUCTURE CREATE POINT-ZERO point ALLOT 0 0 POINT-ZERO 2! BEGIN-STRUCTURE grid-cell-def point +FIELD grid-cell-def.begin-white-up point +FIELD grid-cell-def.begin-white-down point +FIELD grid-cell-def.begin-red-up point +FIELD grid-cell-def.begin-red-down point +FIELD grid-cell-def[0,1] point +FIELD grid-cell-def[1,0] point +FIELD grid-cell-def[0,-1] point +FIELD grid-cell-def[-1,0] END-STRUCTURE BEGIN-STRUCTURE grid-cell-defs-t grid-cell-def +FIELD grid-cell-defs./ grid-cell-def +FIELD grid-cell-defs.\ grid-cell-def +FIELD grid-cell-defs.+ END-STRUCTURE CREATE GRID-CELL-DEFS grid-cell-defs-t ALLOT : DIR-FLAT ( n n -- u ) 1+ 3 * SWAP 1+ + ; : grid-cell-def[] ( n n grid-cell-def -- point ) >R DIR-FLAT CASE 0 0 DIR-FLAT OF 0 ENDOF 0 1 DIR-FLAT OF 4 ENDOF 1 0 DIR-FLAT OF 5 ENDOF 0 -1 DIR-FLAT OF 6 ENDOF -1 0 DIR-FLAT OF 7 ENDOF 1 THROW ENDCASE point * R> + ; : 4DUP 2>R 2>R 2R@ 2R> 2R@ 2SWAP 2R> ; : DEFINE-CELL-CONNECTION ( n n n n grid-cell-def -- ) >R 4DUP NEGATE SWAP NEGATE SWAP 2SWAP R@ grid-cell-def[] 2! 2SWAP NEGATE SWAP NEGATE SWAP 2SWAP R> grid-cell-def[] 2! ; 0 1 1 0 GRID-CELL-DEFS grid-cell-defs./ DEFINE-CELL-CONNECTION 0 -1 -1 0 GRID-CELL-DEFS grid-cell-defs./ DEFINE-CELL-CONNECTION 0 -1 SWAP GRID-CELL-DEFS grid-cell-defs./ grid-cell-def.begin-white-up 2! -1 0 SWAP GRID-CELL-DEFS grid-cell-defs./ grid-cell-def.begin-white-down 2! 0 1 SWAP GRID-CELL-DEFS grid-cell-defs./ grid-cell-def.begin-red-up 2! 1 0 SWAP GRID-CELL-DEFS grid-cell-defs./ grid-cell-def.begin-red-down 2! 0 1 -1 0 GRID-CELL-DEFS grid-cell-defs.\ DEFINE-CELL-CONNECTION 0 -1 1 0 GRID-CELL-DEFS grid-cell-defs.\ DEFINE-CELL-CONNECTION 0 -1 SWAP GRID-CELL-DEFS grid-cell-defs.\ grid-cell-def.begin-white-up 2! 1 0 SWAP GRID-CELL-DEFS grid-cell-defs.\ grid-cell-def.begin-white-down 2! 0 1 SWAP GRID-CELL-DEFS grid-cell-defs.\ grid-cell-def.begin-red-up 2! -1 0 SWAP GRID-CELL-DEFS grid-cell-defs.\ grid-cell-def.begin-red-down 2! 0 1 0 -1 GRID-CELL-DEFS grid-cell-defs.+ DEFINE-CELL-CONNECTION 1 0 -1 0 GRID-CELL-DEFS grid-cell-defs.+ DEFINE-CELL-CONNECTION 0 -1 SWAP GRID-CELL-DEFS grid-cell-defs.+ grid-cell-def.begin-white-up 2! 0 1 SWAP GRID-CELL-DEFS grid-cell-defs.+ grid-cell-def.begin-white-down 2! -1 0 SWAP GRID-CELL-DEFS grid-cell-defs.+ grid-cell-def.begin-red-up 2! 1 0 SWAP GRID-CELL-DEFS grid-cell-defs.+ grid-cell-def.begin-red-down 2! : GRID-CELL-DEF-BEGINS ( u grid-cell -- point[2] grid-cell-def ) >R R@ grid-cell.invert C@ 1 = IF 1 SWAP - THEN GRID-CELL-DEFS R> grid-cell.type C@ 1- grid-cell-def * + >R point 2* * R@ + R> ; BEGIN-STRUCTURE traxer-state point +FIELD traxer-state.pos point +FIELD traxer-state.prev-pos CFIELD: traxer-state.go? CFIELD: traxer-state.first CFIELD: traxer-state.colour CFIELD: traxer-state.dir CFIELD: traxer-state.bump ALIGNED END-STRUCTURE CREATE TRAXER-STATES traxer-state 4 * ALLOT 0 TRAXER-STATES traxer-state 0 * + traxer-state.colour C! 0 TRAXER-STATES traxer-state 1 * + traxer-state.colour C! 1 TRAXER-STATES traxer-state 2 * + traxer-state.colour C! 1 TRAXER-STATES traxer-state 3 * + traxer-state.colour C! 0 TRAXER-STATES traxer-state 0 * + traxer-state.dir C! 1 TRAXER-STATES traxer-state 1 * + traxer-state.dir C! 0 TRAXER-STATES traxer-state 2 * + traxer-state.dir C! 1 TRAXER-STATES traxer-state 3 * + traxer-state.dir C! 0 VALUE CURRENT-TRAXER CREATE TRAXER-OLDPOS point ALLOT 0 VALUE CURRENT-GRID-CELL 0 VALUE CURRENT-GRID-CELL-DEF 0 VALUE CURRENT-GRID-CELL-BEGINS 0 VALUE NEXT-GRID-CELL 0 VALUE NEXT-GRID-CELL-DEF 0 VALUE NEXT-GRID-CELL-BEGINS 0 VALUE FOUND-LOOP : COLOUR-MISMATCH ( n n -- flag ) ENABLE-BUG IF ." diff " 2DUP SWAP . . CR THEN DIR-FLAT 2 0 DO DUP NEXT-GRID-CELL-BEGINS I point * + DUP point.x @ SWAP point.y @ DIR-FLAT = IF DROP FALSE UNLOOP EXIT THEN LOOP DROP TRUE ; : FIND-DIRECTION ( -- ) 2 0 DO CURRENT-GRID-CELL-BEGINS I CURRENT-TRAXER traxer-state.dir C@ 1 = IF 1 SWAP - THEN point * + >R CURRENT-TRAXER traxer-state.pos point.x @ R@ point.x @ + CURRENT-TRAXER traxer-state.pos point.y @ R> point.y @ + 2DUP TRAXER-OLDPOS point.y @ = SWAP TRAXER-OLDPOS point.x @ = AND 0= IF CURRENT-TRAXER traxer-state.pos point.y ! CURRENT-TRAXER traxer-state.pos point.x ! UNLOOP EXIT THEN 2DROP LOOP ; : FORWARD-TRAXER ( traxer-state -- flag ) TO CURRENT-TRAXER CURRENT-TRAXER traxer-state.go? C@ 0= IF FALSE EXIT THEN ENABLE-BUG IF CR ." >> color " CURRENT-TRAXER traxer-state.colour C@ . CR ." dir " CURRENT-TRAXER traxer-state.dir C@ . CR ." from " CURRENT-TRAXER traxer-state.prev-pos DUP point.y @ SWAP point.x @ . . CR ." at " CURRENT-TRAXER traxer-state.pos DUP point.y @ SWAP point.x @ . . CR THEN CURRENT-TRAXER traxer-state.prev-pos TRAXER-OLDPOS point MOVE CURRENT-TRAXER traxer-state.pos CURRENT-TRAXER traxer-state.prev-pos point MOVE CURRENT-TRAXER traxer-state.pos DUP point.x @ SWAP point.y @ PARSED-GRID grid[] TO CURRENT-GRID-CELL ENABLE-BUG IF ." ( type " CURRENT-GRID-CELL grid-cell.type C@ . ." inv " CURRENT-GRID-CELL grid-cell.invert C@ . ." )" CR THEN CURRENT-GRID-CELL grid-cell.type C@ GRID-0 = IF ENABLE-BUG IF ." reject null source " CR THEN FALSE EXIT THEN CURRENT-GRID-CELL grid-cell.invert C@ 2 = IF 0 CURRENT-GRID-CELL grid-cell.invert C! THEN CURRENT-TRAXER traxer-state.colour C@ CURRENT-GRID-CELL GRID-CELL-DEF-BEGINS TO CURRENT-GRID-CELL-DEF TO CURRENT-GRID-CELL-BEGINS CURRENT-GRID-CELL-DEF CURRENT-GRID-CELL-BEGINS CURRENT-TRAXER DROP 2DROP FIND-DIRECTION CURRENT-TRAXER traxer-state.pos DUP point.x @ SWAP point.y @ PARSED-GRID grid[] TO NEXT-GRID-CELL ENABLE-BUG IF ." to " CURRENT-TRAXER traxer-state.pos DUP point.y @ SWAP point.x @ . . CR ." ( type " NEXT-GRID-CELL grid-cell.type C@ . ." inv " NEXT-GRID-CELL grid-cell.invert C@ . ." )" CR THEN CURRENT-GRID-CELL grid-cell.wseen CURRENT-TRAXER traxer-state.colour C@ CHARS + C@ IF ENABLE-BUG IF ." reject seen source " CR THEN FALSE EXIT THEN CURRENT-TRAXER traxer-state.first C@ 0= IF TRUE CURRENT-GRID-CELL grid-cell.wseen CURRENT-TRAXER traxer-state.colour C@ CHARS + C! THEN FALSE CURRENT-TRAXER traxer-state.first C! NEXT-GRID-CELL NULL-GRID-CELL = IF TRUE CURRENT-TRAXER traxer-state.bump C! THEN NEXT-GRID-CELL grid-cell.type C@ GRID-0 = IF ENABLE-BUG IF ." reject null target " CR THEN FALSE EXIT THEN CURRENT-TRAXER traxer-state.colour C@ NEXT-GRID-CELL GRID-CELL-DEF-BEGINS TO NEXT-GRID-CELL-DEF TO NEXT-GRID-CELL-BEGINS NEXT-GRID-CELL grid-cell.wseen CURRENT-TRAXER traxer-state.colour C@ CHARS + C@ IF ENABLE-BUG IF ." found loop" CR THEN TRUE TO FOUND-LOOP THEN TRUE ; BEGIN-STRUCTURE vstack FIELD: vstack.addr FIELD: vstack.len END-STRUCTURE 0 VALUE VSTACK-ITEM : VSTACK-PUSH ( addr vstack -- ) >R R@ vstack.addr @ R@ vstack.len @ VSTACK-ITEM * + VSTACK-ITEM MOVE 1 R> vstack.len +! ; : VSTACK-POP ( addr vstack -- flag ) DUP vstack.len @ 0> 0= IF 2DROP FALSE EXIT THEN >R -1 R@ vstack.len +! R@ vstack.addr @ R> vstack.len @ VSTACK-ITEM * + SWAP VSTACK-ITEM MOVE TRUE ; CREATE QUEUE vstack ALLOT : IMPLODE-POS ( u u -- u ) PARSED-GRID grid.width @ * + ; : EXPLODE-POS ( u -- u u ) PARSED-GRID grid.width @ /MOD ; BEGIN-STRUCTURE queue-elem-t FIELD: queue-elem.pos END-STRUCTURE CREATE QUEUE-ELEM queue-elem-t ALLOT : NORM-PUSH ( n n -- FLAG ) 2DUP IMPLODE-POS QUEUE-ELEM ! PARSED-GRID grid[] >R R@ grid-cell.type C@ GRID-0 = R@ grid-cell.wseen C@ 0= 0= OR 0= R> SWAP IF grid-cell.wseen TRUE SWAP C! QUEUE-ELEM QUEUE VSTACK-PUSH ELSE DROP THEN ; : NORMALIZE ( -- ) PARSED-GRID DUP grid.height @ SWAP grid.width @ * DUP point * ALIGN HERE QUEUE vstack.addr ! queue-elem-t * ALLOT 0 QUEUE vstack.len ! queue-elem-t TO VSTACK-ITEM DUP 0 ?DO I PARSED-GRID grid.width @ /MOD 2DUP TO PARSED-HEIGHT TO PARSED-WIDTH NORM-PUSH ENABLE-BUG IF CR ." [ flood fill at " PARSED-WIDTH . PARSED-HEIGHT . ." ]" CR THEN BEGIN QUEUE-ELEM QUEUE VSTACK-POP WHILE QUEUE-ELEM @ EXPLODE-POS 2DUP TO PARSED-HEIGHT TO PARSED-WIDTH PARSED-GRID grid[] DUP TO CURRENT-GRID-CELL CURRENT-GRID-CELL grid-cell.invert C@ 2 = IF 0 CURRENT-GRID-CELL grid-cell.invert C! THEN ENABLE-BUG IF CR ." >> pos " PARSED-WIDTH PARSED-HEIGHT SWAP . . CR THEN ENABLE-BUG IF ." ( type " CURRENT-GRID-CELL grid-cell.type C@ . ." inv " CURRENT-GRID-CELL grid-cell.invert C@ . ." )" CR THEN DUP grid-cell.type C@ GRID-0 = IF 0 ELSE 2 THEN 0 ?DO ENABLE-BUG IF ." color " I . CR THEN DUP I SWAP GRID-CELL-DEF-BEGINS TO CURRENT-GRID-CELL-DEF TO CURRENT-GRID-CELL-BEGINS 2 0 DO CURRENT-GRID-CELL-BEGINS I point * + DUP point.x @ SWAP point.y @ ENABLE-BUG IF ." dir " 2DUP SWAP . . CR THEN 2DUP PARSED-WIDTH PARSED-HEIGHT ROT + ROT ROT + SWAP 2DUP ENABLE-BUG IF ." to " 2DUP SWAP . . CR THEN NORM-PUSH PARSED-GRID grid[] DUP TO NEXT-GRID-CELL DUP grid-cell.type C@ ENABLE-BUG IF ." to " QUEUE-ELEM @ EXPLODE-POS SWAP . . CR THEN GRID-0 = IF ENABLE-BUG IF ." reject null target " CR THEN DROP 2DROP ELSE J SWAP GRID-CELL-DEF-BEGINS TO NEXT-GRID-CELL-DEF TO NEXT-GRID-CELL-BEGINS NEGATE SWAP NEGATE SWAP COLOUR-MISMATCH IF ENABLE-BUG IF ." inverting " CR THEN NEXT-GRID-CELL grid-cell.invert C@ 2 = 0= IF 1 ABORT" VERTIGO" THEN 1 NEXT-GRID-CELL grid-cell.invert C! ELSE NEXT-GRID-CELL grid-cell.invert C@ 2 = IF ENABLE-BUG IF ." default " CR THEN 0 NEXT-GRID-CELL grid-cell.invert C! THEN THEN THEN LOOP LOOP DROP REPEAT LOOP DUP 0 ?DO I PARSED-GRID grid.width @ /MOD PARSED-GRID grid[] grid-cell.wseen FALSE SWAP C! LOOP DROP ; : ANALYZE-GRID ( -- flag ) PARSED-GRID grid.width @ PARSED-GRID grid.height @ * 0 ?DO I PARSED-GRID grid.height @ /MOD TO PARSED-HEIGHT TO PARSED-WIDTH ENABLE-BUG IF CR CR ." [ #" I . ." scanning at " PARSED-WIDTH . PARSED-HEIGHT . ." ]" CR THEN 4 0 DO TRAXER-STATES I traxer-state * + >R PARSED-HEIGHT PARSED-WIDTH R@ traxer-state.pos 2! R@ traxer-state.pos R@ traxer-state.prev-pos point MOVE TRUE R@ traxer-state.go? C! TRUE R@ traxer-state.first C! FALSE R> traxer-state.bump C! LOOP FALSE TO FOUND-LOOP 4 0 DO TRAXER-STATES I traxer-state * + FORWARD-TRAXER TRAXER-STATES I traxer-state * + traxer-state.go? C! LOOP TRUE CURRENT-GRID-CELL grid-cell.wseen C! TRUE CURRENT-GRID-CELL grid-cell.rseen C! BEGIN FOUND-LOOP 0= FALSE 4 0 DO TRAXER-STATES I traxer-state * + traxer-state.go? C@ OR LOOP AND WHILE ENABLE-BUG IF CR ." ..." CR THEN 4 0 DO TRAXER-STATES I traxer-state * + FORWARD-TRAXER TRAXER-STATES I traxer-state * + traxer-state.go? C! LOOP REPEAT FOUND-LOOP IF ENABLE-BUG IF ." loop!" CR THEN FALSE UNLOOP EXIT THEN 2 0 DO TRAXER-STATES I 2* 0 + traxer-state * + traxer-state.bump C@ TRAXER-STATES I 2* 1 + traxer-state * + traxer-state.bump C@ AND IF TRAXER-STATES I 2* 0 + traxer-state * + traxer-state.pos point.x @ TRAXER-STATES I 2* 1 + traxer-state * + traxer-state.pos point.x @ - ABS TRAXER-STATES I 2* 0 + traxer-state * + traxer-state.pos point.y @ TRAXER-STATES I 2* 1 + traxer-state * + traxer-state.pos point.y @ - ABS MAX 8 < 0= IF ENABLE-BUG IF ." line!" CR THEN FALSE UNLOOP UNLOOP EXIT THEN THEN LOOP LOOP TRUE ; : ENTRY ( c-addr u -- flag ) HERE >R ALIGN HERE grid ALLOT PARSE-GRID NORMALIZE ANALYZE-GRID R> HERE - ENABLE-BUG IF CR DUP NEGATE . ." bytes used" CR THEN ALLOT ; |
written by LyricLy
submitted at
1 like
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 | #include <string.h> #include <stddef.h> #include <stdbool.h> #include <stdio.h> #include <stdlib.h> typedef ptrdiff_t Int; typedef struct { bool main; bool off; } parts; typedef struct { char *s; parts *consumed; Int width; Int height; } grid; grid parsegrid(char *s) { grid g; g.s = s; g.width = strcspn(s, "\n"); g.height = strlen(s) / g.width; // freed when the program dies g.consumed = calloc(g.width * g.height, sizeof * g.consumed); return g; } char indexgrid(grid g, Int x, Int y) { // width + 1 for the newlines return g.s[y*(g.width+1)+x]; } parts *indexconsumed(grid g, Int x, Int y) { return &g.consumed[y*g.width+x]; } bool inbounds(grid g, Int x, Int y) { return x >= 0 && y >= 0 && x < g.width && y < g.height; } bool followline(grid g, Int x, Int y, Int dx, Int dy) { Int ox = x; Int oy = y; while (inbounds(g, x, y)) { Int mainaltx = 0; Int mainalty = -1; switch (indexgrid(g, x, y)) { case '/': { Int olddy = dy; dy = -dx; dx = -olddy; mainaltx = 1; mainalty = 0; } case '\\': { Int olddy = dy; dy = dx; dx = olddy; mainaltx = -1; mainalty = 0; } } parts *p = indexconsumed(g, x, y); if (dy == 1 || (dx == mainaltx && dy == mainalty)) p->main = true; else p->off = true; x += dx; y += dy; } return ((ox == 0 || ox == g.width-1) && (x == -1 || x == g.width) && llabs(ox-x) >= 8) || ((oy == 0 || oy == g.height-1) && (y == -1 || y == g.height) && llabs(oy-y) >= 8); } bool hasconcluded(char *s) { grid g = parsegrid(s); #define follow(g, x, y, dx, dy) do { if (followline(g, x, y, dx, dy)) return true; } while (0) for (Int x = 0; x < g.width; x++) { follow(g, x, 0, 0, 1); follow(g, x, g.height-1, 0, -1); } for (Int y = 0; y < g.width; y++) { follow(g, 0, y, 1, 0); follow(g, g.width-1, y, -1, 0); } // loops are that left over for (Int y = 0; y < g.height; y++) { for (Int x = 0; x < g.width; x++) { parts p = *indexconsumed(g, x, y); if (!p.main || !p.off) return true; } } return false; } |
post a comment