API tools faq
paste
Guest User

NYT Pips solver

a guest
Jan 20th, 2026
191
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 25.35 KB | None | 0 0
raw download clone embed print report
  1. # This is a shell archive. Save it in a file, remove anything before
  2. # this line, and then unpack it by entering "sh file". Note, it may
  3. # create directories; files and directories will be owned by you and
  4. # have default permissions.
  5. #
  6. # This archive contains:
  7. #
  8. # 2025-10-26.json
  9. # create-puzzle-header.pl
  10. # get-puzzle-from-json.pl
  11. # Makefile
  12. # pips.c
  13. # README
  14. # remove-fixed.pl
  15. #
  16. echo x - 2025-10-26.json
  17. sed 's/^X//' >2025-10-26.json << 'f236fa34ab2378ed9dd359e6a772e319'
  18. X{"printDate":"2025-10-26","editor":"Ian Livengood","easy":{"id":57,"backendId":"e688601b48895efeb7f2872eeac9c778","constructors":"Heidi Erwin","dominoes":[[6,6],[5,5],[5,2],[6,1]],"regions":[{"indices":[[0,0],[0,1]],"type":"greater","target":7},{"indices":[[0,3],[1,3]],"type":"equals"},{"indices":[[1,0],[1,1],[1,2]],"type":"sum","target":17},{"indices":[[2,2]],"type":"empty"}],"solution":[[[0,1],[1,1]],[[0,3],[1,3]],[[1,0],[0,0]],[[1,2],[2,2]]]},"medium":{"id":51,"backendId":"2340fa8497925b17832d0ae1c3bb5d8e","constructors":"Rodolfo Kurchan","dominoes":[[2,4],[0,4],[4,6],[1,4],[0,0],[1,2],[0,2],[5,6],[5,4],[1,3],[0,5],[5,5],[1,1]],"regions":[{"indices":[[0,3]],"type":"empty"},{"indices":[[1,2],[1,3],[1,4]],"type":"unequal"},{"indices":[[2,2],[2,3]],"type":"sum","target":0},{"indices":[[2,4]],"type":"sum","target":1},{"indices":[[3,3]],"type":"sum","target":2},{"indices":[[4,0],[4,1],[5,1]],"type":"equals"},{"indices":[[4,2]],"type":"sum","target":3},{"indices":[[4,3],[4,4],[4,5],[4,6]],"type":"equals"},{"indices":[[4,7]],"type":"empty"},{"indices":[[5,2],[6,2]],"type":"sum","target":10},{"indices":[[5,3],[5,4],[6,3],[6,4]],"type":"sum","target":22},{"indices":[[5,5],[6,5]],"type":"unequal"},{"indices":[[5,6]],"type":"empty"}],"solution":[[[5,5],[5,6]],[[2,2],[1,2]],[[6,5],[6,4]],[[4,6],[4,7]],[[4,0],[4,1]],[[2,4],[1,4]],[[2,3],[3,3]],[[6,2],[6,3]],[[1,3],[0,3]],[[4,3],[4,2]],[[5,1],[5,2]],[[5,3],[5,4]],[[4,4],[4,5]]]},"hard":{"id":94,"backendId":"02ac54ef6ffe55679572dac5b145d002","constructors":"Heidi Erwin","dominoes":[[5,1],[3,1],[1,1],[4,2],[0,4],[4,4],[5,3],[0,2]],"regions":[{"indices":[[0,0],[0,1],[0,2]],"type":"equals"},{"indices":[[1,0],[1,1],[2,0],[2,1]],"type":"sum","target":5},{"indices":[[1,2],[2,2]],"type":"sum","target":1},{"indices":[[2,3]],"type":"empty"},{"indices":[[3,0],[4,0]],"type":"equals"},{"indices":[[3,1],[3,2]],"type":"sum","target":3},{"indices":[[4,1],[4,2]],"type":"sum","target":5}],"solution":[[[3,0],[2,0]],[[3,1],[2,1]],[[1,1],[1,2]],[[0,0],[1,0]],[[2,2],[2,3]],[[0,1],[0,2]],[[4,0],[4,1]],[[3,2],[4,2]]]}}
  19. X
  20. f236fa34ab2378ed9dd359e6a772e319
  21. echo x - create-puzzle-header.pl
  22. sed 's/^X//' >create-puzzle-header.pl << '462d9a1a9f0c053b0519af07720f78e7'
  23. X#!/usr/bin/env perl
  24. Xuse strict;
  25. Xuse Data::Dumper;
  26. X$Data::Dumper::Sortkeys = 1;
  27. X
  28. Xmy @link; # [square, neighbor]
  29. Xmy @tile; # [faceA, faceB]
  30. Xmy @constraint; # [rule, [sq, ...]]
  31. Xmy %coords; # sq => [row, col]
  32. X
  33. Xmy %constraint_map; # square => constraint
  34. Xmy @constraint_name;
  35. Xmy %constraint_rule; # name => [rule, [squares]]
  36. X
  37. Xmy $num_rows = 0;
  38. Xmy $num_cols = 0;
  39. X
  40. Xmain();
  41. X
  42. Xsub main
  43. X{
  44. X print "/***************************\\\n";
  45. X print "| |\n";
  46. X print "| THIS IS A GENERATED FILE! |\n";
  47. X print "| DO NOT EDIT! |\n";
  48. X print "| |\n";
  49. X print "\\***************************/\n";
  50. X read_spec();
  51. X make_constraints();
  52. X make_board();
  53. X make_tiles();
  54. X}
  55. X
  56. Xsub make_constraints()
  57. X{
  58. X print "int c_none();\n";
  59. X foreach (@constraint) {
  60. X my $rule = $_->[0];
  61. X my @squares = @{$_->[1]};
  62. X my $name = "c_" . join("_", @squares);
  63. X push @constraint_name, $name;
  64. X $constraint_rule{$name} = $_;
  65. X foreach my $sq (@squares) {
  66. X $constraint_map{$sq} = $name;
  67. X }
  68. X print "int $name();\n";
  69. X }
  70. X}
  71. X
  72. Xsub make_tiles()
  73. X{
  74. X my $num_tiles = @tile;
  75. X
  76. X print "Tile tiles[$num_tiles] = {\n";
  77. X foreach (@tile) {
  78. X my($left, $right) = @$_;
  79. X print " {$left, $right, -1, -1},\n";
  80. X }
  81. X print "};\n";
  82. X}
  83. X
  84. Xsub make_board()
  85. X{
  86. X print "Group_Base group_base[] = {\n";
  87. X foreach (@constraint) {
  88. X my($rule, $squares) = @$_;
  89. X my $sq = $squares->[@$squares-1];
  90. X my $r = pad($coords{$sq}[0]);
  91. X my $c = pad($coords{$sq}[1]);
  92. X
  93. X print " {\"$rule\", $r, $c},\n";
  94. X }
  95. X print "};\n";
  96. X
  97. X my %neighbor;
  98. X foreach (@link) {
  99. X my($a, $b) = @$_;
  100. X push @{$neighbor{$a}}, $b;
  101. X push @{$neighbor{$b}}, $a;
  102. X }
  103. X
  104. X my @squares = sort {$a<=>$b} keys %neighbor;
  105. X print "Square board[", scalar(@squares), "] = {\n";
  106. X my $i = 0;
  107. X foreach (@squares) {
  108. X my @adjacent = @{$neighbor{$_}};
  109. X sort {$a<=>$b} @adjacent;
  110. X push @adjacent, -1 while @adjacent < 4;
  111. X my $constraint = $constraint_map{$_} || "c_none";
  112. X my $r = pad($coords{$_}[0]);
  113. X my $c = pad($coords{$_}[1]);
  114. X my $gu = $coords{$_}[2];
  115. X my $g = '"' . $gu . '"';
  116. X my $pi = pad($i, 2);
  117. X my $nl = join(", ", map {pad($_,2)} @adjacent);
  118. X print "/*$pi*/ {$r, $c, -1, $g, {$nl}, $constraint},\n";
  119. X ++$i;
  120. X }
  121. X print "};\n";
  122. X
  123. X print "#define ROWS $num_rows\n";
  124. X print "#define COLS $num_cols\n";
  125. X foreach (@squares) {
  126. X print "#define SQ$_ board[$_].pips\n";
  127. X }
  128. X
  129. X print "int c_none()\n";
  130. X print "{\n";
  131. X print " return 1;\n";
  132. X print "}\n";
  133. X foreach (@constraint_name) {
  134. X my($rule, $sq) = @{$constraint_rule{$_}};
  135. X print "int $_()\n";
  136. X print "{\n";
  137. X
  138. X if ($rule =~ m{(^\d+)}) {
  139. X my $goal = $1;
  140. X my $t = test_not_full($sq);
  141. X print " if ($t) return 1;\n";
  142. X my $t = sum_squares($sq);
  143. X print " if ($t == $goal) return 1;\n";
  144. X print " else return 0;\n"
  145. X } elsif ($rule eq "=") {
  146. X my $t = test_not_full($sq);
  147. X print " if ($t) return 1;\n";
  148. X my $t = test_equal($sq);
  149. X print " if ($t) return 1;\n";
  150. X print " else return 0;\n";
  151. X } elsif ($rule =~ m{^([<>])(\d+)}) {
  152. X my($op,$goal) = ($1, $2);
  153. X my $t = test_not_full($sq);
  154. X print " if ($t) return 1;\n";
  155. X my $t = sum_squares($sq);
  156. X print " if ($t $op $goal) return 1;\n";
  157. X print " else return 0;\n"
  158. X } elsif ($rule eq "<>") {
  159. X print " int mask = 0;\n";
  160. X my $t = test_not_full($sq);
  161. X print " if ($t) return 1;\n";
  162. X foreach (@$sq) {
  163. X print " if (mask & (1<<SQ$_)) return 0;\n";
  164. X print " mask |= 1 << SQ$_;\n";
  165. X }
  166. X print " return 1;\n";
  167. X } else {
  168. X print "$_: <$rule> on ", join(", ", @$sq), "\n";
  169. X }
  170. X print "}\n";
  171. X }
  172. X}
  173. X
  174. Xsub test_not_full
  175. X{
  176. X my($sq) = @_;
  177. X return join(" || ", map{qq{SQ$_ == -1}} @$sq);
  178. X}
  179. X
  180. Xsub sum_squares
  181. X{
  182. X my($sq) = @_;
  183. X return join(" + ", map{qq{SQ$_}} @$sq);
  184. X}
  185. X
  186. Xsub test_equal
  187. X{
  188. X my($sq) = @_;
  189. X my @sq = @$sq;
  190. X my $target = "SQ" . shift @sq;
  191. X
  192. X return join(" && ", map{qq{$target == SQ$_}} @sq);
  193. X}
  194. X
  195. Xsub read_spec
  196. X{
  197. X my @b_lines;
  198. X my @c_lines;
  199. X my @d_lines;
  200. X my $width = 0;
  201. X my %constraints; # name => [rule, [squares]]
  202. X while (<>) {
  203. X chomp;
  204. X #if (m{^[a-zA-Z]\s+}) { push @c_lines, $_; }
  205. X if (m{^[a-zA-Z\[\\\]\^]\s+}) { push @c_lines, $_; }
  206. X elsif (m{^\d+(\s+\d+)*}) { push @d_lines, $_; }
  207. X elsif (m{[-.a-zA-Z]+}) {
  208. X push @b_lines, $_;
  209. X $width = length($_) if length($_) > $width;
  210. X }
  211. X }
  212. X
  213. X # initial constraints table with names and rules
  214. X foreach (@c_lines) {
  215. X my($name, $rule) = $_ =~ m{^([a-zA-Z])\s+(\S+)};
  216. X $constraints{$name} = [$rule, []];
  217. X }
  218. X
  219. X # build map of board and add squares to constraints
  220. X my $next_square = 0;
  221. X my @b_fixed;
  222. X my $r = 0;
  223. X my $c = 0;
  224. X $num_rows = scalar(@b_lines);
  225. X foreach (@b_lines) {
  226. X my @row = split //, $_;
  227. X push @row, '.' while @row < $width;
  228. X foreach my $s (@row) {
  229. X if ($s eq '-') {
  230. X $coords{$next_square} = [$r, $c, ' '];
  231. X $s = $next_square++;
  232. X } elsif ($s =~ /([a-zA-Z])/) {
  233. X push @{$constraints{$1}[1]}, $next_square;
  234. X $coords{$next_square} = [$r, $c, $1];
  235. X $s = $next_square++;
  236. X }
  237. X ++$c;
  238. X $num_cols = $c if $c > $num_cols;
  239. X }
  240. X push @b_fixed, \@row;
  241. X $c = 0;
  242. X ++$r;
  243. X }
  244. X
  245. X # print links
  246. X for (my $r = 0; $r < $num_rows; ++$r) {
  247. X for (my $c = 0; $c < $width; ++$c) {
  248. X my $sq = $b_fixed[$r][$c];
  249. X if ($sq ne '.') {
  250. X my $ad = $c + 1 < $width ? $b_fixed[$r][$c+1] : '.';
  251. X push @link, [$sq, $ad] if $ad != '.';
  252. X $ad = $r + 1 < $num_rows ? $b_fixed[$r+1][$c] : '.';
  253. X push @link, [$sq, $ad] if $ad != '.';
  254. X }
  255. X }
  256. X }
  257. X
  258. X foreach (sort {$a cmp $b} keys %constraints) {
  259. X my($rule, $list) = @{$constraints{$_}};
  260. X #print "$rule: ", join(' ', @$list), "\n";
  261. X push @constraint, [$rule, [@$list]];
  262. X }
  263. X
  264. X foreach (@d_lines) {
  265. X my @d = split /\s+/, $_;
  266. X foreach (@d) {
  267. X my($a, $b) = split //, $_;
  268. X push @tile, [$a, $b];
  269. X }
  270. X }
  271. X
  272. X #foreach (sort {$a<=>$b} keys %coords) {
  273. X # print "$_\t", join(" ", @{$coords{$_}}), "\n";
  274. X #}
  275. X foreach (@b_fixed) {
  276. X print '// ', join(' ', map {pad($_,2)} @$_), "\n\n";
  277. X }
  278. X}
  279. X
  280. Xsub pad
  281. X{
  282. X my($str, $w) = @_;
  283. X $str = ' ' . $str while length($str) < $w;
  284. X return $str;
  285. X}
  286. 462d9a1a9f0c053b0519af07720f78e7
  287. echo x - get-puzzle-from-json.pl
  288. sed 's/^X//' >get-puzzle-from-json.pl << '05c4bfc6519858489c47fcf2e07b8f3e'
  289. X#!/usr/bin/env perl
  290. Xuse strict;
  291. Xuse JSON;
  292. Xuse Data::Dumper;
  293. X$Data::Dumper::Sortkeys = 1;
  294. X
  295. X# You can find the puzzle for YYYY-MM-DD at
  296. X# https://www.nytimes.com/svc/pips/v1/YYYY-MM-DD.json
  297. X
  298. Xmain();
  299. X
  300. Xsub main
  301. X{
  302. X my $which = shift @ARGV || die "Difficulty not given\n";
  303. X my $json_in;
  304. X while (<>) {
  305. X $json_in .= $_;
  306. X }
  307. X my $p = decode_json $json_in;
  308. X #print Dumper($p);
  309. X
  310. X #my $date = $p->{printDate};
  311. X
  312. X my $e = make_encoding($p->{$which});
  313. X}
  314. X
  315. Xsub make_encoding
  316. X{
  317. X my($p) = @_;
  318. X
  319. X my %board;
  320. X my %constraint;
  321. X my $next_label = 'A';
  322. X
  323. X print join(' ', map {join('', @$_)} @{$p->{dominoes}}), "\n\n";
  324. X
  325. X foreach (@{$p->{regions}}) {
  326. X my $type = $_->{type};
  327. X my $target = $_->{target};
  328. X
  329. X my $label;
  330. X if ($type eq 'empty') {
  331. X $label = '-';
  332. X } else {
  333. X if ($next_label eq '[') { $next_label = 'a'; }
  334. X $label = $next_label;
  335. X $next_label = chr(1 + ord($next_label));
  336. X if ($type eq "sum") { $constraint{$label} = $target; }
  337. X elsif ($type eq "less") { $constraint{$label} = "<$target"; }
  338. X elsif ($type eq "greater") { $constraint{$label} = ">$target"; }
  339. X elsif ($type eq "equals") { $constraint{$label} = "="; }
  340. X elsif ($type eq "unequal") { $constraint{$label} = "<>"; }
  341. X else { die "Unrecognize constrain $type:[$target]\n"; }
  342. X }
  343. X
  344. X foreach (@{$_->{indices}}) {
  345. X my($row, $col) = ($_->[0], $_->[1]);
  346. X $board{$row}{$col} = $label;
  347. X }
  348. X }
  349. X
  350. X foreach (sort {$a cmp $b} keys %constraint) {
  351. X print "$_ ", $constraint{$_}, "\n";
  352. X }
  353. X print "\n";
  354. X
  355. X my $write_row = 0;
  356. X foreach my $row (sort {$a<=>$b} keys %board) {
  357. X while ($write_row < $row) {
  358. X print ".\n";
  359. X ++$write_row;
  360. X }
  361. X my $write_col = 0;
  362. X foreach my $col (sort {$a<=>$b} keys %{$board{$row}}) {
  363. X while ($write_col < $col) {
  364. X print '.';
  365. X ++$write_col;
  366. X }
  367. X print $board{$row}{$col};
  368. X ++$write_col;
  369. X }
  370. X print "\n";
  371. X ++$write_row;
  372. X }
  373. X}
  374. 05c4bfc6519858489c47fcf2e07b8f3e
  375. echo x - Makefile
  376. sed 's/^X//' >Makefile << '60f8520832b6f80996c175fbf41f4e55'
  377. X#vim: set tabstop=8 noexpandtab:
  378. Xsolve: pips.c puzzle.h
  379. X cc -O3 pips.c -o solve
  380. X
  381. Xclean:
  382. X rm solve puzzle.h
  383. X
  384. X
  385. 60f8520832b6f80996c175fbf41f4e55
  386. echo x - pips.c
  387. sed 's/^X//' >pips.c << 'e72e2e6d8eef828fea6eb57b7863cb90'
  388. X#include <stdio.h>
  389. X#include <stdlib.h>
  390. X#include <string.h>
  391. X#include <iconv.h>
  392. X#include <wchar.h>
  393. X#include <errno.h>
  394. X
  395. X#define SHOW 1
  396. X#define CLEAR 0
  397. X#define LABELS 0
  398. X
  399. Xint opt_show = SHOW;
  400. Xint opt_clear = CLEAR;
  401. Xint opt_labels = LABELS;
  402. X
  403. Xtypedef struct {
  404. X int y; /* row */
  405. X int x; /* col */
  406. X int pips; /* -1 if empty, # of pips if not empty */
  407. X char * group; /* name of group */
  408. X int neighbors[4];
  409. X int (*constraint)();
  410. X} Square;
  411. X
  412. Xtypedef struct {
  413. X int nA; /* # of pips on A end */
  414. X int nB; /* # of pips on B end */
  415. X int sA; /* where A end is placed (-1 if not placed) */
  416. X int sB; /* where B end is placed (-1 if not placed) */
  417. X} Tile;
  418. X
  419. Xtypedef struct {
  420. X char * group;
  421. X int y;
  422. X int x;
  423. X} Group_Base;
  424. X
  425. Xchar *** rows = 0;
  426. Xint solution_count = 0;
  427. X
  428. X#include "puzzle.h"
  429. X
  430. Xvoid show_tiles_graphic(void);
  431. Xvoid show_tiles_text(void);
  432. Xint place(char * lp, char * cp, int pos);
  433. Xvoid solve(int depth);
  434. Xvoid draw_square(int y, int x, int pips, int up);
  435. Xvoid erase_line(int py, int px, int dy, int dx, int n, char * what);
  436. Xvoid draw_tile(int y, int x, int pips1, int pips2,
  437. X char * g1, char * g2, int dir);
  438. Xvoid label_square(int y, int x, char * label);
  439. X
  440. X
  441. Xint main(int argc, char *argv[]) {
  442. X for (int i = 1; i < argc; ++i) {
  443. X if (strcmp(argv[i], "-c") == 0) { opt_clear = 1; }
  444. X if (strcmp(argv[i], "-l") == 0) { opt_labels = 1; }
  445. X if (strcmp(argv[i], "-q") == 0) { opt_show = 0; }
  446. X }
  447. X solve(0);
  448. X printf("Solutions: %d\n", solution_count);
  449. X return 0;
  450. X}
  451. X
  452. X#define TL "┌"
  453. X#define TR "┐"
  454. X#define BL "└"
  455. X#define BR "┘"
  456. X#define TT "┬"
  457. X#define BT "┴"
  458. X#define LT "├"
  459. X#define RT "┤"
  460. X#define HL "─"
  461. X#define VL "│"
  462. X#define CC "┼"
  463. X#define PIP "◎";
  464. X
  465. X#define SQ_X 7
  466. X#define SQ_Y 3
  467. X
  468. X#define PIX_X ((SQ_X+1)*COLS+1)
  469. X#define PIX_Y ((SQ_Y+1)*ROWS+1)
  470. X
  471. X#define PX 2
  472. X#define PY 1
  473. X
  474. Xvoid show_tiles_text(void)
  475. X{
  476. X char * sep = "";
  477. X for (int t = 0; t < sizeof tiles / sizeof(Tile); ++t) {
  478. X printf("%s%d/%d(%d,%d)", sep, tiles[t].nA, tiles[t].nB,
  479. X tiles[t].sA, tiles[t].sB);
  480. X sep = " ";
  481. X }
  482. X printf("\n");
  483. X}
  484. X
  485. Xvoid show_tiles_graphic(void)
  486. X{
  487. X static int inited = 0;
  488. X printf("board is %d rows x %d cols\n", PIX_Y, PIX_X);
  489. X if (! inited) rows = (char ***)malloc(PIX_Y * sizeof(char *));
  490. X for (int i = 0; i < PIX_Y; ++i) {
  491. X char ** line = inited ? rows[i] : (char **)malloc(PIX_X * sizeof(char *));
  492. X for (int j = 0; j < PIX_X; ++j) {
  493. X line[j] = " ";
  494. X }
  495. X rows[i] = line;
  496. X }
  497. X inited = 1;
  498. X
  499. X for (int t = 0; t < sizeof tiles / sizeof(Tile); ++t) {
  500. X int dir = 0;
  501. X int rA = board[tiles[t].sA].y;
  502. X int cA = board[tiles[t].sA].x;
  503. X int nA = tiles[t].nA;
  504. X char * gA = board[tiles[t].sA].group;
  505. X int rB = board[tiles[t].sB].y;
  506. X int cB = board[tiles[t].sB].x;
  507. X int nB = tiles[t].nB;
  508. X char * gB = board[tiles[t].sB].group;
  509. X
  510. X if (rA > rB) dir = 0;
  511. X else if (rA < rB) dir = 2;
  512. X else if (cA < cB) dir = 3;
  513. X else dir = 1;
  514. X
  515. X draw_tile(rA, cA, nA, nB, gA, gB, dir);
  516. X }
  517. X if (opt_labels) {
  518. X for (int i = 0; i < sizeof group_base / sizeof(group_base[0]); ++i) {
  519. X label_square(group_base[i].y, group_base[i].x, group_base[i].group);
  520. X }
  521. X }
  522. X
  523. X for (int i = 0; i < PIX_Y; ++i) {
  524. X for (int j = 0; j < PIX_X; ++j) {
  525. X printf("%s", rows[i][j]);
  526. X }
  527. X putchar('\n');
  528. X }
  529. X putchar('\n');
  530. X if (opt_clear) {
  531. X exit(0);
  532. X }
  533. X}
  534. X
  535. Xvoid label_square(int y, int x, char * label)
  536. X{
  537. X int px = 1 + x * (SQ_X + 1);
  538. X int py = 1 + y * (SQ_Y + 1);
  539. X int n = strlen(label);
  540. X if (n == 1) {
  541. X rows[py + SQ_Y][px + SQ_X] = label;
  542. X } else {
  543. X for (int i = 0; i < n; ++i) {
  544. X char * one = (char *)malloc(2); //TODO: when does this get freed?
  545. X one[0] = label[i];
  546. X one[1] = '\0';
  547. X rows[py + SQ_Y][px + SQ_X + i] = one;
  548. X }
  549. X }
  550. X}
  551. X
  552. X/* dir: 0 == up, 1 == left, 2 == down, 3 == right */
  553. Xvoid draw_tile(int y, int x, int pips1, int pips2,
  554. X char * g1, char * g2, int dir)
  555. X{
  556. X if (opt_clear) {
  557. X pips1 = pips2 = 0;
  558. X }
  559. X char * what = (strcmp(g1, g2) == 0) ? " " : ".";
  560. X int px = 1 + x * (SQ_X + 1);
  561. X int py = 1 + y * (SQ_Y + 1);
  562. X draw_square(y, x, pips1, (dir == 0 || dir == 2) ? 1 : 0);
  563. X
  564. X switch (dir) {
  565. X case 0: --y; break;
  566. X case 1: --x; break;
  567. X case 2: ++y; break;
  568. X case 3: ++x; break;
  569. X }
  570. X
  571. X int px2 = 1 + x * (SQ_X + 1);
  572. X int py2 = 1 + y * (SQ_Y + 1);
  573. X draw_square(y, x, pips2, (dir == 0 || dir == 2) ? 1 : 0);
  574. X
  575. X switch (dir) {
  576. X case 0:
  577. X erase_line(py-1, px, 0, 1, 7, what);
  578. X break;
  579. X case 1:
  580. X erase_line(py, px-1, 1, 0, 3, what);
  581. X break;
  582. X case 2:
  583. X erase_line(py2-1, px, 0, 1, 7, what);
  584. X break;
  585. X case 3:
  586. X erase_line(py2, px2-1, 1, 0, 3, what);
  587. X break;
  588. X }
  589. X}
  590. X
  591. Xvoid erase_line(int py, int px, int dy, int dx, int n, char * what)
  592. X{
  593. X if (! opt_clear) {
  594. X while (n-- > 0) {
  595. X if (px > 0 && py > 0)
  596. X rows[py][px] = what;
  597. X else {
  598. X printf("Internal error: out of bounds\n");
  599. X exit(1);
  600. X }
  601. X py += dy;
  602. X px += dx;
  603. X }
  604. X }
  605. X}
  606. X
  607. Xvoid draw_square(int y, int x, int pips, int up)
  608. X{
  609. X int i, j;
  610. X x = 1 + x * (SQ_X + 1);
  611. X y = 1 + y * (SQ_Y + 1);
  612. X for (i = y; i < y+SQ_Y; ++i)
  613. X for (j = x; j < x+SQ_X; ++j)
  614. X rows[i][j] = " ";
  615. X
  616. X // frame top and bottom
  617. X for (j = x; j < x+SQ_X; ++j) {
  618. X rows[y-1][j] = HL;
  619. X rows[y+SQ_Y][j] = HL;
  620. X }
  621. X // frame the sides
  622. X for (i = y; i < y+SQ_Y; ++i) {
  623. X rows[i][x-1] = VL;
  624. X rows[i][x+SQ_X] = VL;
  625. X }
  626. X // corners
  627. X rows[y-1][x-1] = TL;
  628. X rows[y+SQ_Y][x-1] = BL;
  629. X rows[y+SQ_Y][x+SQ_X] = BR;
  630. X rows[y-1][x+SQ_X] = TR;
  631. X
  632. X x += 1;
  633. X switch (pips) {
  634. X case 1:
  635. X rows[y+PY][x+PX] = PIP;
  636. X break;
  637. X case 2:
  638. X if (up) {
  639. X rows[y][x] = PIP;
  640. X rows[y+2*PY][x+2*PX] = PIP;
  641. X } else {
  642. X rows[y][x+2*PX] = PIP;
  643. X rows[y+2*PY][x] = PIP;
  644. X }
  645. X break;
  646. X case 3:
  647. X rows[y+PY][x+PX] = PIP;
  648. X if (up) {
  649. X rows[y][x] = PIP;
  650. X rows[y+2*PY][x+2*PX] = PIP;
  651. X } else {
  652. X rows[y][x+2*PX] = PIP;
  653. X rows[y+2*PY][x] = PIP;
  654. X }
  655. X break;
  656. X case 4:
  657. X rows[y][x] = PIP;
  658. X rows[y+2*PY][x] = PIP;
  659. X rows[y][x+2*PX] = PIP;
  660. X rows[y+2*PY][x+2*PX] = PIP;
  661. X break;
  662. X case 5:
  663. X rows[y+PY][x+PX] = PIP;
  664. X rows[y][x] = PIP;
  665. X rows[y+2*PY][x] = PIP;
  666. X rows[y][x+2*PX] = PIP;
  667. X rows[y+2*PY][x+2*PX] = PIP;
  668. X break;
  669. X case 6:
  670. X if (up) {
  671. X rows[y][x] = PIP;
  672. X rows[y+PY][x] = PIP;
  673. X rows[y+2*PY][x] = PIP;
  674. X rows[y][x+2*PX] = PIP;
  675. X rows[y+PY][x+2*PX] = PIP;
  676. X rows[y+2*PY][x+2*PX] = PIP;
  677. X } else {
  678. X rows[y][x] = PIP;
  679. X rows[y][x+PX] = PIP;
  680. X rows[y][x+2*PX] = PIP;
  681. X rows[y+2*PY][x] = PIP;
  682. X rows[y+2*PY][x+PX] = PIP;
  683. X rows[y+2*PY][x+2*PX] = PIP;
  684. X }
  685. X break;
  686. X }
  687. X}
  688. X
  689. Xvoid indent(int depth)
  690. X{
  691. X if (depth > 0) {
  692. X for (int i = 0; i < 2*depth; ++i) putchar('_');
  693. X }
  694. X}
  695. X
  696. Xvoid solve(int depth)
  697. X{
  698. X int sq;
  699. X int i;
  700. X int t;
  701. X
  702. X
  703. X /* find an empty square */
  704. X sq = sizeof board / sizeof(Square);
  705. X while (--sq >= 0) {
  706. X if (board[sq].pips == -1) break;
  707. X }
  708. X if ( sq < 0) {
  709. X ++solution_count;
  710. X if (opt_show) {
  711. X show_tiles_graphic();
  712. X show_tiles_text();
  713. X }
  714. X return;
  715. X }
  716. X
  717. X for (i = 0; i < 4; ++i) {
  718. X int ad = board[sq].neighbors[i];
  719. X if (ad >= 0 && board[ad].pips == -1) {
  720. X for (t = 0; t < sizeof tiles / sizeof(Tile); ++t) {
  721. X if (tiles[t].sA != -1) continue;
  722. X board[sq].pips = tiles[t].nA;
  723. X board[ad].pips = tiles[t].nB;
  724. X tiles[t].sA = sq;
  725. X tiles[t].sB = ad;
  726. X //indent(depth); printf("Try %d%d on %d/%d\n", board[sq].pips, board[ad].pips, sq, ad);
  727. X if ((*board[sq].constraint)() && (*board[ad].constraint)()) {
  728. X solve(depth+1);
  729. X }
  730. X if (tiles[t].nA != tiles[t].nB) {
  731. X board[sq].pips = tiles[t].nB;
  732. X board[ad].pips = tiles[t].nA;
  733. X tiles[t].sB = sq;
  734. X tiles[t].sA = ad;
  735. X //indent(depth); printf("Try %d%d on %d/%d\n", board[sq].pips, board[ad].pips, sq, ad);
  736. X if ((*board[sq].constraint)() && (*board[ad].constraint)()) {
  737. X solve(depth+1);
  738. X }
  739. X }
  740. X board[sq].pips = -1;
  741. X board[ad].pips = -1;
  742. X tiles[t].sA = -1;
  743. X tiles[t].sB = -1;
  744. X }
  745. X }
  746. X }
  747. X}
  748. e72e2e6d8eef828fea6eb57b7863cb90
  749. echo x - README
  750. sed 's/^X//' >README << '0ee3a4adc07a27bcc83b176e68e8893f'
  751. XTo use this Pips solver, first obtain the JSON file from the NYT for
  752. Xthe day the puzzle was published. I've included the file for the
  753. X2025-10-26 puzzles to get you started. There's a comment in
  754. Xget-puzzle-from-json.pl telling where to get other days.
  755. X
  756. XTo solve the puzzle use get-puzzle-from-json.pl to extract the
  757. Xparticular difficulty level you are interested in from the JSON
  758. Xfile, like this:
  759. X
  760. X ./get-puzzle-from-json.pl easy < 2025-10-26.json
  761. X
  762. XThat will extract that particular puzzle and convert it to
  763. Xan intermediate format which will be printed on stdout.
  764. XRedirect stdout to some temp file for use in the next step,
  765. Xor simply pipe the output to the program in the next step.
  766. X
  767. XThe script create-puzzle-header.pl turns that intermediate
  768. Xformat into a C header file the solver can use. Run it on
  769. Xthe output of get-puzzle-from-json.pl and save the output
  770. Xas puzzle.h.
  771. X
  772. XCompile the solver with
  773. X
  774. X cc -O3 pips.c -o solve
  775. X
  776. Xor if you use make a Makefile is included for this.
  777. X
  778. XThen run solve and it will shows you the solutions.
  779. X
  780. XThere are three flags you can give solve.
  781. X
  782. X-l Add the constraint labels. This is pretty useless right now
  783. Xbecause the output doesn't show the region boundaries.
  784. X
  785. X-c Don't show tiles. Just show the shape of the puzzle.
  786. X
  787. X-q Don't show the solutions. It will just show you how many there
  788. Xare.
  789. X
  790. XNOTE! When you change puzzles don't forget to recompile after
  791. Xyou make the new puzzle.h.
  792. X
  793. XThere's one more script included: remove-fixed.pl. When a puzzle
  794. Xhas multiple solutions you can do this:
  795. X
  796. X ./solve | grep / | ./remove-fixed.pl
  797. X
  798. Xand it gives you a list of all the tiles, and for each shows
  799. Xall the different places it can appear. The locations are given
  800. Xusing square numbers. Near the top of puzzle.h is a diagram
  801. Xshowing the square number assignments.
  802. 0ee3a4adc07a27bcc83b176e68e8893f
  803. echo x - remove-fixed.pl
  804. sed 's/^X//' >remove-fixed.pl << 'a58dd082170b431a26ad571650597d60'
  805. X#!/usr/bin/env perl
  806. Xuse strict;
  807. Xuse Data::Dumper;
  808. X$Data::Dumper::Sortkeys = 1;
  809. X
  810. Xmy %cover;
  811. X
  812. Xmain();
  813. X
  814. Xsub main
  815. X{
  816. X while (<>) {
  817. X chomp;
  818. X foreach (split /\s+/, $_) {
  819. X my($tile, $loc) = $_ =~
  820. X m{(\d.\d).(\d+,\d+)};
  821. X $cover{$tile}{"($loc)"} = 1
  822. X }
  823. X }
  824. X foreach my $tile (sort {$a cmp $b} keys %cover) {
  825. X my @squares = sort {$a cmp $b} keys %{$cover{$tile}};
  826. X print "$tile: ", join(" ", @squares), "\n";
  827. X }
  828. X}
  829. a58dd082170b431a26ad571650597d60
  830. chmod +x create-puzzle-header.pl get-puzzle-from-json.pl remove-fixed.pl
  831. exit
  832.  
  833.  
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!