← All repositories

crossmate

A collaborative crossword app for iPhone and iPad

git clone https://code.inqk.net/crossmate.git


Crossmake/Scripts/generate_puzzles.sh (11227B)

1#!/usr/bin/env bash
2set -euo pipefail
3
4SCRIPT_DIR="$(cd "$(dirname "${BASH_SOURCE[0]}")" && pwd)"
5CROSSMAKE_DIR="$(cd "${SCRIPT_DIR}/.." && pwd)"
6cd "$CROSSMAKE_DIR"
7
8DATA_DIR="Data"
9GENERATED_DIR="Generated"
10GRID_LIST="Sources/Fillmake/Resources/grid_list.json"
11WORD_LIST="${GENERATED_DIR}/word_list.json"
12COUNTS_FILE="${GENERATED_DIR}/answer_counts.json"
13QUALITY_FILE="${GENERATED_DIR}/word_quality.json"
14BAD_WORDS_FILE="${DATA_DIR}/bad_words.json"
15TIMEOUT_SECONDS="${CROSSMAKE_TIMEOUT_SECONDS:-10}"
16EXAMPLES_PER_GRID="${CROSSMAKE_EXAMPLES_PER_GRID:-4}"
17OUTPUT_PREFIX="Crossmate"
18MIN_FILL_SCORE="${CROSSMAKE_MIN_FILL_SCORE:-7500}"
19BREADTH="${CROSSMAKE_BREADTH:-80}"
20MAX_ANSWER_USAGES="${CROSSMAKE_MAX_ANSWER_USAGES:-1}"
21MAX_PARALLEL_JOBS="${CROSSMAKE_JOBS:-}"
22# Use CROSSMAKE_GRID_SELECTION=ranked to sample from Gridmake's top-ranked grids.
23GRID_SELECTION="${CROSSMAKE_GRID_SELECTION:-random}"
24GRID_RANK_LIMIT="${CROSSMAKE_GRID_RANK_LIMIT:-250}"
25FIXED_GRID_INDEX="${CROSSMAKE_GRID_INDEX:-}"
26FIXED_SEED="${CROSSMAKE_SEED:-}"
27TARGET_PUZZLES="${1:-10}"
28FILLMAKE_EXECUTABLE=".build/release/Fillmake"
29GRIDMAKE_EXECUTABLE=".build/release/Gridmake"
30
31if [[ ! -f "$WORD_LIST" ]]; then
32  echo "Word list not found: $WORD_LIST" >&2
33  exit 1
34fi
35
36if [[ ! -f "$GRID_LIST" ]]; then
37  echo "Grid list not found: $GRID_LIST" >&2
38  exit 1
39fi
40
41if [[ ! -f "$COUNTS_FILE" ]]; then
42  echo "Answer counts not found: $COUNTS_FILE" >&2
43  exit 1
44fi
45
46if [[ ! -f "$QUALITY_FILE" ]]; then
47  echo "Word quality metadata not found: $QUALITY_FILE" >&2
48  exit 1
49fi
50
51if [[ ! -f "$BAD_WORDS_FILE" ]]; then
52  echo "Bad-word list not found: $BAD_WORDS_FILE" >&2
53  exit 1
54fi
55
56if ! command -v jq >/dev/null 2>&1; then
57  echo "jq is required to read $GRID_LIST" >&2
58  exit 1
59fi
60
61if [[ -z "$MAX_PARALLEL_JOBS" ]]; then
62  MAX_PARALLEL_JOBS="$(sysctl -n hw.ncpu 2>/dev/null || getconf _NPROCESSORS_ONLN 2>/dev/null || echo 4)"
63  if ((MAX_PARALLEL_JOBS > 4)); then
64    MAX_PARALLEL_JOBS=4
65  fi
66fi
67
68if ! [[ "$MAX_PARALLEL_JOBS" =~ ^[0-9]+$ ]] || ((10#$MAX_PARALLEL_JOBS < 1)); then
69  echo "CROSSMAKE_JOBS must be a positive integer" >&2
70  exit 1
71fi
72
73if ! [[ "$TIMEOUT_SECONDS" =~ ^[0-9]+([.][0-9]+)?$ ]]; then
74  echo "CROSSMAKE_TIMEOUT_SECONDS must be a positive number" >&2
75  exit 1
76fi
77
78if ! [[ "$EXAMPLES_PER_GRID" =~ ^[0-9]+$ ]] || ((10#$EXAMPLES_PER_GRID < 1)); then
79  echo "CROSSMAKE_EXAMPLES_PER_GRID must be a positive integer" >&2
80  exit 1
81fi
82
83if ! [[ "$MIN_FILL_SCORE" =~ ^-?[0-9]+$ ]]; then
84  echo "CROSSMAKE_MIN_FILL_SCORE must be an integer" >&2
85  exit 1
86fi
87
88if ! [[ "$BREADTH" =~ ^[0-9]+$ ]] || ((10#$BREADTH < 1)); then
89  echo "CROSSMAKE_BREADTH must be a positive integer" >&2
90  exit 1
91fi
92
93if ! [[ "$MAX_ANSWER_USAGES" =~ ^[0-9]+$ ]] || ((10#$MAX_ANSWER_USAGES < 1)); then
94  echo "CROSSMAKE_MAX_ANSWER_USAGES must be a positive integer" >&2
95  exit 1
96fi
97
98if [[ "$GRID_SELECTION" != "ranked" && "$GRID_SELECTION" != "random" ]]; then
99  echo "CROSSMAKE_GRID_SELECTION must be ranked or random" >&2
100  exit 1
101fi
102
103if [[ -n "$FIXED_GRID_INDEX" ]] && ! [[ "$FIXED_GRID_INDEX" =~ ^[0-9]+$ ]]; then
104  echo "CROSSMAKE_GRID_INDEX must be a non-negative integer" >&2
105  exit 1
106fi
107
108if [[ -n "$FIXED_SEED" ]] && ! [[ "$FIXED_SEED" =~ ^[0-9]+$ ]]; then
109  echo "CROSSMAKE_SEED must be a non-negative integer" >&2
110  exit 1
111fi
112
113if ! [[ "$GRID_RANK_LIMIT" =~ ^[0-9]+$ ]] || ((10#$GRID_RANK_LIMIT < 1)); then
114  echo "CROSSMAKE_GRID_RANK_LIMIT must be a positive integer" >&2
115  exit 1
116fi
117
118if ! [[ "$TARGET_PUZZLES" =~ ^[0-9]+$ ]]; then
119  echo "Usage: $0 [positive-puzzle-count]" >&2
120  exit 1
121fi
122
123target_puzzle_count=$((10#$TARGET_PUZZLES))
124if ((target_puzzle_count < 1)); then
125  echo "Usage: $0 [positive-puzzle-count]" >&2
126  exit 1
127fi
128
129next_output_number() {
130  local highest=0
131  local path filename number number_value
132
133  for path in "${GENERATED_DIR}/${OUTPUT_PREFIX}-"*.xd; do
134    [[ -e "$path" ]] || continue
135    filename="${path##*/}"
136    [[ "$filename" =~ ^${OUTPUT_PREFIX}-([0-9]+)\.xd$ ]] || continue
137    number="${BASH_REMATCH[1]}"
138    number_value=$((10#$number))
139    if ((number_value > highest)); then
140      highest="$number_value"
141    fi
142  done
143
144  echo "$((highest + 1))"
145}
146
147output_number="$(next_output_number)"
148mkdir -p "$GENERATED_DIR"
149tmp_dir="$(mktemp -d)"
150trap 'rm -rf "$tmp_dir"' EXIT
151
152echo "Building Fillmake in release mode"
153swift build -c release
154
155if [[ ! -x "$FILLMAKE_EXECUTABLE" ]]; then
156  echo "Fillmake executable not found after build: $FILLMAKE_EXECUTABLE" >&2
157  exit 1
158fi
159
160if [[ ! -x "$GRIDMAKE_EXECUTABLE" ]]; then
161  echo "Gridmake executable not found after build: $GRIDMAKE_EXECUTABLE" >&2
162  exit 1
163fi
164
165available_grid_count="$(jq 'length' "$GRID_LIST")"
166grid_indices="$tmp_dir/grid-indices.txt"
167
168if [[ -n "$FIXED_GRID_INDEX" ]]; then
169  if ((10#$FIXED_GRID_INDEX >= available_grid_count)); then
170    echo "CROSSMAKE_GRID_INDEX ${FIXED_GRID_INDEX} is out of range; found ${available_grid_count} grids" >&2
171    exit 1
172  fi
173  echo "$FIXED_GRID_INDEX" >"$grid_indices"
174elif [[ "$GRID_SELECTION" == "ranked" ]]; then
175  "$GRIDMAKE_EXECUTABLE" --grids "$GRID_LIST" --limit "$GRID_RANK_LIMIT" \
176    | awk 'NR > 1 { print $2 }' >"$grid_indices"
177else
178  for ((grid_index = 0; grid_index < available_grid_count; grid_index++)); do
179    echo "$grid_index"
180  done >"$grid_indices"
181fi
182
183selection_grid_count="$(wc -l <"$grid_indices" | tr -d '[:space:]')"
184if ((10#$selection_grid_count < 1)); then
185  echo "No grids available for selection" >&2
186  exit 1
187fi
188
189selected_indices=()
190while IFS= read -r selected_index; do
191  selected_indices+=("$selected_index")
192done <"$grid_indices"
193
194random_grid_index() {
195  echo "${selected_indices[$((RANDOM % selection_grid_count))]}"
196}
197
198if [[ -n "$FIXED_GRID_INDEX" ]]; then
199  echo "Generating ${target_puzzle_count} puzzle(s) from fixed grid ${FIXED_GRID_INDEX} with ${EXAMPLES_PER_GRID} fill attempt(s) per puzzle, ${MAX_PARALLEL_JOBS} parallel job(s), timeout ${TIMEOUT_SECONDS}s per run, breadth ${BREADTH}, min score ${MIN_FILL_SCORE}, max answer usage ${MAX_ANSWER_USAGES}"
200elif [[ "$GRID_SELECTION" == "ranked" ]]; then
201  echo "Generating ${target_puzzle_count} puzzle(s) from the top ${selection_grid_count} ranked grid(s) with ${EXAMPLES_PER_GRID} fill attempt(s) per puzzle, ${MAX_PARALLEL_JOBS} parallel job(s), timeout ${TIMEOUT_SECONDS}s per run, breadth ${BREADTH}, min score ${MIN_FILL_SCORE}, max answer usage ${MAX_ANSWER_USAGES}"
202else
203  echo "Generating ${target_puzzle_count} puzzle(s) from ${selection_grid_count} random grid(s) with ${EXAMPLES_PER_GRID} fill attempt(s) per puzzle, ${MAX_PARALLEL_JOBS} parallel job(s), timeout ${TIMEOUT_SECONDS}s per run, breadth ${BREADTH}, min score ${MIN_FILL_SCORE}, max answer usage ${MAX_ANSWER_USAGES}"
204fi
205
206running_job_count() {
207  jobs -rp | wc -l | tr -d '[:space:]'
208}
209
210wait_for_job_slot() {
211  while ((10#$(running_job_count) >= 10#$MAX_PARALLEL_JOBS)); do
212    sleep 1
213  done
214}
215
216candidate_index=0
217
218start_candidate() {
219  local group_id="$1"
220  local grid_index="$2"
221  local example="$3"
222  local candidate_id="$4"
223  local seed="$5"
224  local output_path="${tmp_dir}/candidate-${candidate_id}.xd"
225  local log_path="${tmp_dir}/candidate-${candidate_id}.log"
226  local ok_path="${tmp_dir}/candidate-${candidate_id}.ok"
227  local status_path="${tmp_dir}/candidate-${candidate_id}.status"
228  local group_path="${tmp_dir}/candidate-${candidate_id}.group"
229
230  candidate_outputs+=("$output_path")
231  echo "$group_id" >"$group_path"
232  echo "Generating candidate ${candidate_id} from grid index ${grid_index} (${example}/${EXAMPLES_PER_GRID}) with seed ${seed}"
233
234  (
235    set +e
236    "$FILLMAKE_EXECUTABLE" \
237      --words "$WORD_LIST" \
238      --counts "$COUNTS_FILE" \
239      --quality "$QUALITY_FILE" \
240      --bad-words "$BAD_WORDS_FILE" \
241      --grid-index "$grid_index" \
242      --seed "$seed" \
243      --timeout "$TIMEOUT_SECONDS" \
244      --breadth "$BREADTH" \
245      --optimize-fill \
246      --min-fill-score "$MIN_FILL_SCORE" \
247      --max-answer-usages "$MAX_ANSWER_USAGES" \
248      --output "$output_path" >"$log_path" 2>&1
249    status="$?"
250    echo "$status" >"$status_path"
251    if [[ "$status" == "0" ]]; then
252      touch "$ok_path"
253    fi
254  ) &
255}
256
257accepted_count=0
258rejected_count=0
259discarded_count=0
260attempted_group_count=0
261
262fill_score_for_log() {
263  local log_path="$1"
264  local score
265
266  score="$(
267    awk '
268      /kept best fill score/ {
269        value = $(NF)
270        gsub(/\./, "", value)
271        print value
272      }
273      /Selected fill score:/ {
274        print $NF
275      }
276    ' "$log_path" | tail -1
277  )"
278
279  if [[ -n "$score" ]]; then
280    echo "$score"
281  else
282    echo "-999999999"
283  fi
284}
285
286run_grid_group() {
287  local group_id="$1"
288  local grid_index="$2"
289  best_candidate_id=""
290  best_output_path=""
291  best_score="-999999999"
292  candidate_outputs=()
293
294  echo "Starting grid group ${group_id} from grid index ${grid_index}"
295
296  for ((example = 1; example <= EXAMPLES_PER_GRID; example++)); do
297    wait_for_job_slot
298    candidate_index=$((candidate_index + 1))
299    if [[ -n "$FIXED_SEED" ]]; then
300      seed="$FIXED_SEED"
301    else
302      seed="$(($(date +%s) * 1000000 + candidate_index * 1000 + RANDOM))"
303    fi
304    start_candidate "$group_id" "$grid_index" "$example" "$candidate_index" "$seed"
305  done
306
307  wait
308
309  for output_path in "${candidate_outputs[@]}"; do
310    candidate_id="${output_path##*/candidate-}"
311    candidate_id="${candidate_id%.xd}"
312    group_path="${tmp_dir}/candidate-${candidate_id}.group"
313    ok_path="${tmp_dir}/candidate-${candidate_id}.ok"
314    log_path="${tmp_dir}/candidate-${candidate_id}.log"
315
316    [[ -f "$group_path" ]] || continue
317    [[ "$(cat "$group_path")" == "$group_id" ]] || continue
318    [[ -f "$ok_path" ]] || continue
319
320    score="$(fill_score_for_log "$log_path")"
321    if ((score > best_score)); then
322      best_score="$score"
323      best_candidate_id="$candidate_id"
324      best_output_path="$output_path"
325    fi
326  done
327
328  if [[ -n "$best_candidate_id" ]]; then
329    printf -v final_output_path "%s/%s-%04d.xd" "$GENERATED_DIR" "$OUTPUT_PREFIX" "$output_number"
330    mv "$best_output_path" "$final_output_path"
331    echo "Wrote ${final_output_path} from candidate ${best_candidate_id}"
332    grep -E "Searched .* seconds|Selected fill score:" "${tmp_dir}/candidate-${best_candidate_id}.log" || true
333    output_number=$((output_number + 1))
334    accepted_count=$((accepted_count + 1))
335  else
336    echo "No accepted fill for grid group ${group_id}." >&2
337  fi
338
339  for output_path in "${candidate_outputs[@]}"; do
340    candidate_id="${output_path##*/candidate-}"
341    candidate_id="${candidate_id%.xd}"
342    log_path="${tmp_dir}/candidate-${candidate_id}.log"
343    ok_path="${tmp_dir}/candidate-${candidate_id}.ok"
344
345    if [[ -f "$ok_path" ]]; then
346      if [[ -e "$output_path" ]]; then
347        discarded_count=$((discarded_count + 1))
348      fi
349    else
350      rejected_count=$((rejected_count + 1))
351      echo "Rejected candidate ${candidate_id}:" >&2
352      tail -3 "$log_path" >&2 || true
353    fi
354  done
355}
356
357while ((accepted_count < target_puzzle_count)); do
358  attempted_group_count=$((attempted_group_count + 1))
359  run_grid_group "$attempted_group_count" "$(random_grid_index)"
360done
361
362echo "Accepted ${accepted_count} puzzle(s) after ${attempted_group_count} grid group(s); discarded ${discarded_count} lower-scoring accepted fill(s); rejected ${rejected_count}."