1 // This file is part of Freecell Solver. It is subject to the license terms in
2 // the COPYING.txt file found in the top-level directory of this distribution
3 // and at http://fc-solve.shlomifish.org/docs/distro/COPYING.html . No part of
4 // Freecell Solver, including this file, may be copied, modified, propagated,
5 // or distributed except according to the terms contained in the COPYING file.
6 //
7 // Copyright (c) 2000 Shlomi Fish
8 // simpsim.c - a module that contains Simple Simon moves.
9 #include "simpsim.h"
10 #include "scans.h"
11
12 // This is a fallback in case this module is still compiled with
13 // FCS_DISABLE_SIMPLE_SIMON.
14 #ifdef FCS_DISABLE_SIMPLE_SIMON
15 char fc_solve_simple_simon_nothing;
16 #else
17
18 #include "meta_move_funcs_helpers.h"
19
fcs_is_ss_false_parent(const fcs_card parent,const fcs_card child)20 static inline bool fcs_is_ss_false_parent(
21 const fcs_card parent, const fcs_card child)
22 {
23 return (fcs_card_rank(parent) == fcs_card_rank(child) + 1);
24 }
25
fcs_is_ss_suit_true(const fcs_card parent,const fcs_card child)26 static inline bool fcs_is_ss_suit_true(
27 const fcs_card parent, const fcs_card child)
28 {
29 return (fcs_card_suit(parent) == fcs_card_suit(child));
30 }
31
32 #include "fcs_is_ss_true_parent.h"
33 #define fcs_is_ss_true_parent(parent, child) \
34 fc_solve_is_ss_true_parent[parent][child]
35
36 #define STACK_SOURCE_LOOP_START(min_num_cards) \
37 for (stack_i source_stack_idx = 0; source_stack_idx < LOCAL_STACKS_NUM; \
38 ++source_stack_idx) \
39 { \
40 const_AUTO(col, fcs_state_get_col(state_key, source_stack_idx)); \
41 const int col_len = fcs_col_len(col); \
42 if (col_len < min_num_cards) \
43 { \
44 continue; \
45 }
46
47 #define STACK_SOURCE_LOOP_END() }
48
49 #define STACK_DEST_LOOP_START(min_num_cards) \
50 for (stack_i dest_stack_idx = 0; dest_stack_idx < LOCAL_STACKS_NUM; \
51 ++dest_stack_idx) \
52 { \
53 if (dest_stack_idx == source_stack_idx) \
54 { \
55 continue; \
56 } \
57 \
58 const_AUTO(dest_col, fcs_state_get_col(state_key, dest_stack_idx)); \
59 const int dest_col_len = fcs_col_len(dest_col); \
60 \
61 if (dest_col_len < min_num_cards) \
62 { \
63 continue; \
64 }
65
66 #define STACK_DEST_LOOP_END() }
67
68 #ifndef HARD_CODED_NUM_STACKS
69 #define SIMPS_SET_GAME_PARAMS() SET_GAME_PARAMS()
70 #else
71 #define SIMPS_SET_GAME_PARAMS()
72 #endif
73
74 #define SIMPS_define_accessors() \
75 tests_define_accessors(); \
76 SIMPS_SET_GAME_PARAMS()
77
78 #define SIMPS_define_vacant_stacks_accessors() \
79 SIMPS_define_accessors(); \
80 const fcs_game_limit num_vacant_stacks = soft_thread->num_vacant_stacks
81
82 #define CALC_POSITIONS_BY_RANK() \
83 const fcs_pos_by_rank *const positions_by_rank = \
84 (const fcs_pos_by_rank *)fc_solve_calc_positions_by_rank_location( \
85 soft_thread)
86
87 #define STACKS_MAP_LEN MAX_NUM_STACKS
88
init_stacks_map(bool * const stacks_map,const stack_i source_stack_idx,const stack_i dest_stack_idx)89 static inline void init_stacks_map(bool *const stacks_map,
90 const stack_i source_stack_idx, const stack_i dest_stack_idx)
91 {
92 for (stack_i i = 0; i < STACKS_MAP_LEN; i++)
93 {
94 stacks_map[i] = false;
95 }
96 stacks_map[source_stack_idx] = stacks_map[dest_stack_idx] = true;
97 }
98
99 typedef struct
100 {
101 size_t num_separate_false_seqs;
102 int seq_points[MAX_NUM_CARDS_IN_A_STACK];
103 // the stacks to move each false sequence of the junk to.
104 size_t junk_move_to_stacks[MAX_NUM_STACKS];
105 // The number of stacks that are left unoccupied during and after the
106 // process of moving the junk sequences to different stacks.
107 int after_junk_num_freestacks;
108 // above_num_true_seqs[] - the number of true sequences in each false
109 // sequence
110 size_t above_num_true_seqs[MAX_NUM_CARDS_IN_A_STACK];
111 } sequences_analysis;
112
113 #include "simple_simon_rank_seqs.h"
114
fcs_col_pop_seq(fcs_cards_column src_col,const size_t cards_num)115 static inline void fcs_col_pop_seq(
116 fcs_cards_column src_col, const size_t cards_num)
117 {
118 fcs_card *const src_cards_ptr =
119 &fcs_col_get_card(src_col, (fcs_col_len(src_col) -= cards_num));
120 const size_t cards_size = (((size_t)cards_num) * sizeof(fcs_card));
121 memset(src_cards_ptr, 0, cards_size);
122 }
123
DECLARE_MOVE_FUNCTION(fc_solve_sfs_simple_simon_move_sequence_to_founds)124 DECLARE_MOVE_FUNCTION(fc_solve_sfs_simple_simon_move_sequence_to_founds)
125 {
126 SIMPS_define_accessors();
127
128 STACK_SOURCE_LOOP_START(13)
129 fcs_card *start_card_ptr = &fcs_col_get_card(col, col_len - FCS_MAX_RANK);
130 size_t suit = 0;
131 // Check if the top 13 cards are a sequence
132 for (; suit < FCS_NUM_SUITS; ++suit)
133 {
134 if (!memcmp(start_card_ptr, simple_simon_rank_seqs[suit],
135 sizeof(simple_simon_rank_seqs[suit])))
136 {
137 break;
138 }
139 }
140 if (suit < FCS_NUM_SUITS)
141 {
142 // We can move this sequence up there
143 sfs_check_state_begin();
144
145 my_copy_stack(source_stack_idx);
146
147 var_AUTO(
148 new_src_col, fcs_state_get_col(new_state_key, source_stack_idx));
149 fcs_col_pop_seq(new_src_col, FCS_MAX_RANK);
150 fcs_set_foundation(new_state_key, suit, FCS_MAX_RANK);
151
152 fcs_move_stack_non_seq_push(
153 moves, FCS_MOVE_TYPE_SEQ_TO_FOUNDATION, source_stack_idx, suit);
154
155 sfs_check_state_end();
156 }
157 STACK_SOURCE_LOOP_END()
158 }
159
160 #define LOOK_FOR_TRUE_PARENT_with_ds_dc__START(card) \
161 if (!fcs_card_is_king(card)) \
162 { \
163 const fcs_pos_by_rank pos = positions_by_rank[FCS_POS_IDX( \
164 fcs_card_rank(card) + 1, fcs_card_suit(card))]; \
165 if (pos.col < 0) \
166 { \
167 continue; \
168 } \
169 const stack_i dest_stack_idx = (stack_i)pos.col; \
170 \
171 if (dest_stack_idx != source_stack_idx) \
172 { \
173 const int dest_card_height = pos.height; \
174 const_AUTO( \
175 dest_col, fcs_state_get_col(state_key, dest_stack_idx)); \
176 const int dest_col_len = fcs_col_len(dest_col);
177
178 #define LOOK_FOR_TRUE_PARENT_with_ds_dc__END() \
179 } \
180 }
181
182 #define LOOK_FOR_TRUE_PARENT_AT_TOP__START(card) \
183 LOOK_FOR_TRUE_PARENT_with_ds_dc__START( \
184 card) if (dest_card_height == dest_col_len - 1) \
185 {
186 #define LOOK_FOR_TRUE_PARENT_AT_TOP__END() \
187 } \
188 LOOK_FOR_TRUE_PARENT_with_ds_dc__END()
189
190 // TODO:
191 //
192 // Convert to fc_solve_get_the_positions_by_rank_data.
DECLARE_MOVE_FUNCTION(fc_solve_sfs_simple_simon_move_sequence_to_true_parent)193 DECLARE_MOVE_FUNCTION(fc_solve_sfs_simple_simon_move_sequence_to_true_parent)
194 {
195 // card - the current card (at height height)
196 // num_true_seqs - the number of true sequences (i.e: sequences of a
197 // unified suit) in the source sequence.
198 SIMPS_define_vacant_stacks_accessors();
199
200 CALC_POSITIONS_BY_RANK();
201
202 STACK_SOURCE_LOOP_START(1)
203 // Loop on the cards in the stack and try to look for a true
204 // parent on top one of the stacks
205 fcs_card card = fcs_col_get_card(col, col_len - 1);
206 size_t num_true_seqs = 1;
207
208 for (int height = col_len - 2;; --height)
209 {
210 LOOK_FOR_TRUE_PARENT_AT_TOP__START(card)
211 // This is a suitable parent - let's check if we have enough empty
212 // stacks to make the move feasible We can do it - so let's move
213
214 sfs_check_state_begin();
215 copy_two_stacks(source_stack_idx, dest_stack_idx);
216 fcs_move_sequence((size_t)(dest_stack_idx), source_stack_idx,
217 (size_t)(col_len - height - 1));
218 sfs_check_state_end();
219 LOOK_FOR_TRUE_PARENT_AT_TOP__END()
220 // Stop if we reached the bottom of the stack
221 if (height == -1)
222 {
223 break;
224 }
225
226 const fcs_card prev_card = card;
227 card = fcs_col_get_card(col, height);
228 // If this is no longer a sequence - move to the next stack
229 if (!fcs_is_ss_false_parent(card, prev_card))
230 {
231 break;
232 }
233 if (!fcs_is_ss_suit_true(card, prev_card))
234 {
235 ++num_true_seqs;
236 // We can no longer perform the move so go to the next stack.
237 if (calc_max_simple_simon_seq_move(num_vacant_stacks) <
238 num_true_seqs)
239 {
240 break;
241 }
242 }
243 }
244 STACK_SOURCE_LOOP_END()
245 }
246
get_seq_h(const fcs_const_cards_column col,size_t * const num_true_seqs_out_ptr)247 static inline int get_seq_h(
248 const fcs_const_cards_column col, size_t *const num_true_seqs_out_ptr)
249 {
250 const int col_len = fcs_col_len(col);
251
252 fcs_card card = fcs_col_get_card(col, col_len - 1);
253 size_t num_true_seqs = 1;
254
255 int height;
256 // Stop if we reached the bottom of the stack
257 for (height = col_len - 2; height > -1; --height)
258 {
259 const fcs_card next_card = fcs_col_get_card(col, height);
260 // If this is no longer a sequence - move to the next stack
261 if (!fcs_is_ss_false_parent(next_card, card))
262 {
263 break;
264 }
265
266 if (!fcs_is_ss_suit_true(next_card, card))
267 {
268 ++num_true_seqs;
269 }
270
271 card = next_card;
272 }
273
274 *num_true_seqs_out_ptr = num_true_seqs;
275
276 return height + 1;
277 }
278
DECLARE_MOVE_FUNCTION(fc_solve_sfs_simple_simon_move_whole_stack_sequence_to_false_parent)279 DECLARE_MOVE_FUNCTION(
280 fc_solve_sfs_simple_simon_move_whole_stack_sequence_to_false_parent)
281 {
282 // card - the current card
283 // dest_card - the card at the top of "dest_stack_idx".
284 // num_true_seqs - the number of true sequences on the current
285 // false sequence
286 SIMPS_define_vacant_stacks_accessors();
287
288 const size_t max_seq_move =
289 calc_max_simple_simon_seq_move(num_vacant_stacks);
290
291 STACK_SOURCE_LOOP_START(1)
292 {
293 size_t num_true_seqs;
294 // This means that the loop exited prematurely and the stack does not
295 // contain a sequence
296 if ((get_seq_h(col, &num_true_seqs) > 0) ||
297 (max_seq_move < num_true_seqs))
298 {
299 continue;
300 }
301 }
302
303 const size_t height = 0;
304 const fcs_card card = fcs_col_get_card(col, height);
305
306 STACK_DEST_LOOP_START(1)
307 const fcs_card dest_card = fcs_col_get_card(dest_col, dest_col_len - 1);
308 if (!(fcs_is_ss_false_parent(dest_card, card)))
309 {
310 continue;
311 }
312 sfs_check_state_begin();
313 copy_two_stacks(source_stack_idx, dest_stack_idx);
314 fcs_move_sequence(
315 (size_t)(dest_stack_idx), source_stack_idx, (size_t)(col_len));
316 sfs_check_state_end();
317 STACK_DEST_LOOP_END()
318 STACK_SOURCE_LOOP_END()
319 }
320
generic_populate_seq_points(const fcs_cards_column dest_col,const int dest_card_height,sequences_analysis * const seqs,const int dest_col_len)321 static inline void generic_populate_seq_points(const fcs_cards_column dest_col,
322 const int dest_card_height, sequences_analysis *const seqs,
323 const int dest_col_len)
324 {
325 size_t num_separate_false_seqs = seqs->num_separate_false_seqs;
326 seqs->above_num_true_seqs[num_separate_false_seqs] = 1;
327 fcs_card above_card = fcs_col_get_card(dest_col, dest_col_len - 1);
328 for (int card_height = dest_col_len - 2; card_height > dest_card_height;
329 --card_height)
330 {
331 const fcs_card up_above_card = fcs_col_get_card(dest_col, card_height);
332 if (!fcs_is_ss_false_parent(up_above_card, above_card))
333 {
334 seqs->seq_points[num_separate_false_seqs++] = card_height + 1;
335 seqs->above_num_true_seqs[num_separate_false_seqs] = 1;
336 }
337 seqs->above_num_true_seqs[num_separate_false_seqs] +=
338 !fcs_is_ss_suit_true(up_above_card, above_card);
339 above_card = up_above_card;
340 }
341
342 if (dest_card_height <= dest_col_len - 2)
343 {
344 seqs->seq_points[num_separate_false_seqs++] = dest_card_height + 1;
345 }
346
347 seqs->num_separate_false_seqs = num_separate_false_seqs;
348 }
349
populate_seq_points(const fcs_cards_column dest_col,const int dest_card_height,sequences_analysis * const seqs)350 static inline void populate_seq_points(const fcs_cards_column dest_col,
351 const int dest_card_height, sequences_analysis *const seqs)
352 {
353 seqs->num_separate_false_seqs = 0;
354 generic_populate_seq_points(
355 dest_col, dest_card_height, seqs, fcs_col_len(dest_col));
356 }
357
generic_false_seq_index_loop(const int stacks_num,fcs_kv_state raw_state_raw,const int num_vacant_stacks,const fcs_cards_column col,sequences_analysis * const seqs,const stack_i source_stack_idx,const stack_i dest_stack_idx,const bool behavior_flag,const bool should_src_col,const fcs_card src_card,const size_t num_src_junk_true_seqs)358 static inline bool generic_false_seq_index_loop(const int stacks_num,
359 fcs_kv_state raw_state_raw, const int num_vacant_stacks,
360 const fcs_cards_column col, sequences_analysis *const seqs,
361 const stack_i source_stack_idx, const stack_i dest_stack_idx,
362 const bool behavior_flag, const bool should_src_col,
363 const fcs_card src_card, const size_t num_src_junk_true_seqs)
364 {
365 const size_t num_separate_false_seqs = seqs->num_separate_false_seqs;
366 bool stacks_map[STACKS_MAP_LEN];
367 init_stacks_map(stacks_map, source_stack_idx, dest_stack_idx);
368
369 int after_junk_num_freestacks = num_vacant_stacks;
370
371 const size_t false_seq_index_limit =
372 num_separate_false_seqs + (should_src_col ? 1 : 0);
373
374 size_t false_seq_idx;
375
376 for (false_seq_idx = 0; false_seq_idx < false_seq_index_limit;
377 false_seq_idx++)
378 {
379 const bool is_ultimate_iter =
380 (false_seq_idx == num_separate_false_seqs);
381
382 // Find a suitable place to put it
383 const fcs_card the_card =
384 is_ultimate_iter
385 ? src_card
386 : fcs_col_get_card(col, seqs->seq_points[false_seq_idx]);
387
388 const size_t the_num_true_seqs =
389 is_ultimate_iter ? num_src_junk_true_seqs
390 : seqs->above_num_true_seqs[false_seq_idx];
391
392 // Let's try to find a suitable parent on top one of the stacks
393 int clear_junk_dest_stack;
394 for (clear_junk_dest_stack = 0; clear_junk_dest_stack < stacks_num;
395 ++clear_junk_dest_stack)
396 {
397 const fcs_const_cards_column clear_junk_dest_col =
398 fcs_state_get_col(state_key, clear_junk_dest_stack);
399 const int clear_junk_stack_len = fcs_col_len(clear_junk_dest_col);
400
401 if (!((clear_junk_stack_len > 0) &&
402 (!stacks_map[clear_junk_dest_stack])))
403 {
404 continue;
405 }
406
407 if (fcs_is_ss_false_parent(fcs_col_get_card(clear_junk_dest_col,
408 clear_junk_stack_len - 1),
409 the_card))
410 {
411 if (calc_max_simple_simon_seq_move(after_junk_num_freestacks) >=
412 the_num_true_seqs)
413 {
414 goto found;
415 }
416 }
417 }
418
419 // Check if there is a vacant stack
420 if (behavior_flag ||
421 (!((num_vacant_stacks > 0) &&
422 (calc_max_simple_simon_seq_move(
423 after_junk_num_freestacks - 1) >= the_num_true_seqs))))
424 {
425 break;
426 }
427 --after_junk_num_freestacks;
428 // Find an empty stack and designate it as the destination for the junk
429 for (clear_junk_dest_stack = 0;; ++clear_junk_dest_stack)
430 {
431 if (fcs_state_col_is_empty(state_key, clear_junk_dest_stack) &&
432 (!stacks_map[clear_junk_dest_stack]))
433 {
434 break;
435 }
436 }
437
438 found:
439 stacks_map[clear_junk_dest_stack] = true;
440 seqs->junk_move_to_stacks[false_seq_idx] =
441 (size_t)clear_junk_dest_stack;
442 }
443
444 seqs->after_junk_num_freestacks = after_junk_num_freestacks;
445 return (false_seq_idx == false_seq_index_limit);
446 }
447
false_seq_index_loop(const int stacks_num,fcs_kv_state raw_state_raw,const int num_vacant_stacks,const fcs_cards_column col,sequences_analysis * const seqs,const stack_i source_stack_idx,const stack_i dest_stack_idx,const bool behavior_flag)448 static inline bool false_seq_index_loop(const int stacks_num,
449 fcs_kv_state raw_state_raw, const int num_vacant_stacks,
450 const fcs_cards_column col, sequences_analysis *const seqs,
451 const stack_i source_stack_idx, const stack_i dest_stack_idx,
452 const bool behavior_flag)
453 {
454 return generic_false_seq_index_loop(stacks_num, raw_state_raw,
455 num_vacant_stacks, col, seqs, source_stack_idx, dest_stack_idx,
456 behavior_flag,
457 // Params that should be ignored in this case.
458 false, fc_solve_empty_card, 0);
459 }
460
461 #define IS_false_seq_index_loop( \
462 col, behavior_flag, source_stack_idx, dest_stack_idx) \
463 false_seq_index_loop(LOCAL_STACKS_NUM, raw_state_raw, num_vacant_stacks, \
464 col, &seqs, source_stack_idx, dest_stack_idx, behavior_flag)
465
466 #define POPULATE_AND_CHECK_IF_FALSE_SEQ( \
467 col, height, source_stack_idx, dest_stack_idx, behavior_flag) \
468 ({ \
469 populate_seq_points(col, height, &seqs); \
470 IS_false_seq_index_loop( \
471 col, behavior_flag, source_stack_idx, dest_stack_idx); \
472 })
473
move_sequences_analysis_seqs_loop(fcs_kv_state * const ptr_to_pass_new_state SFS__PASS_MOVE_STACK (fcs_move_stack * const moves),const sequences_analysis * const seqs_ptr,const stack_i source_col_idx,const int source_col_cards_num IND_BUF_T_PARAM (indirect_stacks_buffer))474 static inline void move_sequences_analysis_seqs_loop(
475 fcs_kv_state *const ptr_to_pass_new_state SFS__PASS_MOVE_STACK(
476 fcs_move_stack *const moves),
477 const sequences_analysis *const seqs_ptr, const stack_i source_col_idx,
478 const int source_col_cards_num IND_BUF_T_PARAM(indirect_stacks_buffer))
479 {
480 #define pass_new_state (*ptr_to_pass_new_state)
481 for (size_t seq_index = 0; seq_index < seqs_ptr->num_separate_false_seqs;
482 seq_index++)
483 {
484 const_AUTO(dest_col_i, seqs_ptr->junk_move_to_stacks[seq_index]);
485 my_copy_stack(dest_col_i);
486
487 fcs_move_sequence(dest_col_i, (size_t)source_col_idx,
488 ((seq_index == 0) ? (size_t)source_col_cards_num
489 : (size_t)seqs_ptr->seq_points[seq_index - 1]) -
490 (size_t)seqs_ptr->seq_points[seq_index]);
491 }
492 #undef pass_new_state
493 }
494
DECLARE_MOVE_FUNCTION(fc_solve_sfs_simple_simon_move_sequence_to_true_parent_with_some_cards_above)495 DECLARE_MOVE_FUNCTION(
496 fc_solve_sfs_simple_simon_move_sequence_to_true_parent_with_some_cards_above)
497 {
498 // card - the card in height "height"
499 // num_separate_false_seqs - this variable tells how many distinct false
500 // sequences exist above the true parent
501 // seq_points[] - the separation points of the false sequences (i.e: where
502 // they begin and end)
503
504 SIMPS_define_vacant_stacks_accessors();
505 CALC_POSITIONS_BY_RANK();
506
507 STACK_SOURCE_LOOP_START(1)
508 size_t num_true_seqs = 1;
509
510 for (int height = col_len - 2;; --height)
511 {
512 const fcs_card card = fcs_col_get_card(col, height + 1);
513 bool should_search = true;
514 size_t increment_num_true_seqs = 0;
515 bool should_break;
516 // Stop if we reached the bottom of the stack
517 if (!((should_break = (height == -1))))
518 {
519 const fcs_card h_above_card = fcs_col_get_card(col, height);
520 // If this is no longer a sequence - move to the next stack
521 if (!fcs_is_ss_false_parent(h_above_card, card))
522 {
523 should_break = true;
524 }
525 else if ((should_search =
526 (!fcs_is_ss_suit_true(h_above_card, card))))
527 {
528 increment_num_true_seqs = 1;
529 }
530 }
531 if (should_search)
532 {
533 LOOK_FOR_TRUE_PARENT_with_ds_dc__START(card)
534 // This is a suitable parent - let's check if there's a sequence
535 // above it.
536 sequences_analysis seqs;
537
538 if ((POPULATE_AND_CHECK_IF_FALSE_SEQ(dest_col, dest_card_height,
539 source_stack_idx, dest_stack_idx, false) &&
540 (calc_max_simple_simon_seq_move(
541 seqs.after_junk_num_freestacks) >= num_true_seqs)))
542 {
543 // We can do it - so let's move everything.
544 // Notice that we only put the child in a different stack
545 // than the parent and let it move to the parent in the
546 // next iteration of the program
547 sfs_check_state_begin();
548 copy_two_stacks(source_stack_idx, dest_stack_idx);
549 // Move the junk cards to their place
550 move_sequences_analysis_seqs_loop(
551 &pass_new_state SFS__PASS_MOVE_STACK(moves), &seqs,
552 dest_stack_idx,
553 dest_col_len PASS_IND_BUF_T(indirect_stacks_buffer));
554
555 // Move the source seq on top of the dest seq
556 fcs_move_sequence(dest_stack_idx, source_stack_idx,
557 (size_t)(col_len - height - 1));
558
559 sfs_check_state_end();
560 }
561 LOOK_FOR_TRUE_PARENT_with_ds_dc__END()
562 }
563
564 if (should_break)
565 {
566 break;
567 }
568 num_true_seqs += increment_num_true_seqs;
569 }
570 STACK_SOURCE_LOOP_END()
571 }
572
DECLARE_MOVE_FUNCTION(fc_solve_sfs_simple_simon_move_sequence_with_some_cards_above_to_true_parent)573 DECLARE_MOVE_FUNCTION(
574 fc_solve_sfs_simple_simon_move_sequence_with_some_cards_above_to_true_parent)
575 {
576 SIMPS_define_vacant_stacks_accessors();
577 CALC_POSITIONS_BY_RANK();
578
579 STACK_SOURCE_LOOP_START(1)
580 for (ssize_t src_card_height = col_len - 1; src_card_height >= 0;
581 src_card_height--)
582 {
583 const fcs_card h_card = fcs_col_get_card(col, src_card_height);
584 fcs_card card = h_card;
585
586 size_t num_true_seqs = 1;
587
588 for (size_t end_of_src_seq = (size_t)(src_card_height) + 1;
589 end_of_src_seq < (size_t)col_len; ++end_of_src_seq)
590 {
591 const fcs_card above_card = fcs_col_get_card(col, end_of_src_seq);
592 if (!fcs_is_ss_false_parent(card, above_card))
593 {
594 // Split the cards above it into false sequences
595 LOOK_FOR_TRUE_PARENT_AT_TOP__START(h_card)
596 // This is a suitable parent - let's check if we
597 // have enough empty stacks to make the move feasible
598 sequences_analysis seqs;
599
600 if ((POPULATE_AND_CHECK_IF_FALSE_SEQ(col,
601 (int)end_of_src_seq - 1, source_stack_idx,
602 dest_stack_idx, false) &&
603 (calc_max_simple_simon_seq_move(
604 seqs.after_junk_num_freestacks) > num_true_seqs)))
605 {
606 sfs_check_state_begin();
607 copy_two_stacks(source_stack_idx, dest_stack_idx);
608
609 // Move the junk cards to their place
610 move_sequences_analysis_seqs_loop(
611 &pass_new_state SFS__PASS_MOVE_STACK(moves), &seqs,
612 source_stack_idx,
613 col_len PASS_IND_BUF_T(indirect_stacks_buffer));
614
615 fcs_move_sequence(dest_stack_idx, source_stack_idx,
616 end_of_src_seq - (size_t)src_card_height);
617
618 sfs_check_state_end();
619 }
620 LOOK_FOR_TRUE_PARENT_AT_TOP__END()
621 break;
622 }
623 if (!fcs_is_ss_suit_true(card, above_card))
624 {
625 ++num_true_seqs;
626 }
627 card = above_card;
628 }
629 }
630 STACK_SOURCE_LOOP_END()
631 }
632
633 // start, end, src_stack.
634 typedef struct
635 {
636 int seq_len;
637 stack_i src_stack;
638 } s_e_src_type;
639
calc_start_end_src_stack(const int seq_index,const sequences_analysis * const seqs,const int after_end_of_junk,const int col_len,const stack_i source_stack_idx,const stack_i dest_stack_idx,const int dest_col_len)640 static inline s_e_src_type calc_start_end_src_stack(const int seq_index,
641 const sequences_analysis *const seqs, const int after_end_of_junk,
642 const int col_len, const stack_i source_stack_idx,
643 const stack_i dest_stack_idx, const int dest_col_len)
644 {
645 if ((size_t)seq_index == seqs->num_separate_false_seqs)
646 {
647 return (const s_e_src_type){.seq_len = col_len - after_end_of_junk,
648 .src_stack = source_stack_idx};
649 }
650 else
651 {
652 return (const s_e_src_type){
653 .seq_len = (((seq_index == 0) ? dest_col_len
654 : seqs->seq_points[seq_index - 1]) -
655 seqs->seq_points[seq_index]),
656 .src_stack = dest_stack_idx};
657 }
658 }
659
DECLARE_MOVE_FUNCTION(fc_solve_sfs_simple_simon_move_sequence_with_junk_seq_above_to_true_parent_with_some_cards_above)660 DECLARE_MOVE_FUNCTION(
661 fc_solve_sfs_simple_simon_move_sequence_with_junk_seq_above_to_true_parent_with_some_cards_above)
662 {
663 // card - the current card in "stack"
664 // num_separate_false_seqs - the number of false sequences
665 // seq_points[] - the places in which the false sequences of the junk begin
666 // and end
667 // num_src_junk_true_seqs - the number of true seqs in the false seq above
668 // the source card.
669 // num_true_seqs - the number of true sequences in the false seq which we
670 // wish to move.
671 SIMPS_define_vacant_stacks_accessors();
672 CALC_POSITIONS_BY_RANK();
673
674 STACK_SOURCE_LOOP_START(1)
675 size_t num_src_junk_true_seqs;
676
677 const int after_end_of_junk = get_seq_h(col, &num_src_junk_true_seqs);
678 if (!after_end_of_junk)
679 {
680 continue;
681 }
682 int height = after_end_of_junk;
683
684 fcs_card card = fcs_col_get_card(col, height);
685
686 size_t num_true_seqs = 1;
687
688 for (--height; height > -1; --height)
689 {
690 const fcs_card next_card = fcs_col_get_card(col, height);
691 if (!fcs_is_ss_false_parent(next_card, card))
692 {
693 card = next_card;
694 break;
695 }
696 if (!fcs_is_ss_suit_true(next_card, card))
697 {
698 ++num_true_seqs;
699 }
700 card = next_card;
701 }
702
703 // Start at the card below the top one, so we know there's some junk above
704 LOOK_FOR_TRUE_PARENT_with_ds_dc__START(
705 card) if (dest_card_height <= dest_col_len - 2)
706 {
707 // This is a suitable parent - let's check if there's a sequence above
708 // it.
709 sequences_analysis seqs;
710
711 populate_seq_points(dest_col, dest_card_height, &seqs);
712
713 if (generic_false_seq_index_loop(LOCAL_STACKS_NUM, raw_state_raw,
714 num_vacant_stacks, dest_col, &seqs, source_stack_idx,
715 dest_stack_idx, false, true,
716 fcs_col_get_card(col, after_end_of_junk),
717 num_src_junk_true_seqs) &&
718 (calc_max_simple_simon_seq_move(seqs.after_junk_num_freestacks) >=
719 num_true_seqs))
720 {
721 sfs_check_state_begin();
722 copy_two_stacks(source_stack_idx, dest_stack_idx);
723 // Move the junk cards to their place
724
725 for (size_t seq_index = 0;
726 seq_index < seqs.num_separate_false_seqs + 1; seq_index++)
727 {
728 const s_e_src_type s_e = calc_start_end_src_stack(
729 (int)seq_index, &seqs, after_end_of_junk, col_len,
730 source_stack_idx, dest_stack_idx, dest_col_len);
731 const_AUTO(dest_col_i, seqs.junk_move_to_stacks[seq_index]);
732 copy_two_stacks(s_e.src_stack, dest_col_i);
733 fcs_move_sequence(
734 dest_col_i, (size_t)s_e.src_stack, (size_t)s_e.seq_len);
735 }
736
737 // Move the source seq on top of the dest seq
738 fcs_move_sequence(dest_stack_idx, source_stack_idx,
739 (size_t)(after_end_of_junk - height));
740
741 sfs_check_state_end();
742 }
743 }
744 LOOK_FOR_TRUE_PARENT_with_ds_dc__END() STACK_SOURCE_LOOP_END()
745
746 return;
747 }
748
749 typedef fcs_pos_by_rank ds_dc_type;
750
sort_ds_dcs(ds_dc_type * const ds_dcs,const int len)751 static inline void sort_ds_dcs(ds_dc_type *const ds_dcs, const int len)
752 {
753 #define start ds_dcs
754 ds_dc_type *const end = start + len;
755
756 for (ds_dc_type *b = start + 1; b < end; b++)
757 {
758 for (ds_dc_type *c = b;
759 (c > start) &&
760 (c[0].col < c[-1].col ||
761 (c[0].col == c[-1].col && c[0].height > c[-1].height));
762 c--)
763 {
764 const_AUTO(swap_temp, c[-1]);
765 c[-1] = c[0];
766 c[0] = swap_temp;
767 }
768 }
769 #undef start
770 }
771
DECLARE_MOVE_FUNCTION(fc_solve_sfs_simple_simon_move_whole_stack_sequence_to_false_parent_with_some_cards_above)772 DECLARE_MOVE_FUNCTION(
773 fc_solve_sfs_simple_simon_move_whole_stack_sequence_to_false_parent_with_some_cards_above)
774 {
775 // card - the current card
776 SIMPS_define_vacant_stacks_accessors();
777 CALC_POSITIONS_BY_RANK();
778
779 // We never fill empty stacks with junk cards in this move function,
780 // so as a result, after_junk_num_freestacks == num_vacant_stacks and
781 // is constant here.
782 const size_t max_seq_move =
783 calc_max_simple_simon_seq_move(num_vacant_stacks);
784
785 STACK_SOURCE_LOOP_START(1)
786 {
787 size_t num_true_seqs;
788 if (get_seq_h(col, &num_true_seqs) || (max_seq_move < num_true_seqs))
789 {
790 continue;
791 }
792 }
793 const size_t height = 0;
794 const fcs_card card = fcs_col_get_card(col, height);
795
796 if (fcs_card_is_king(card))
797 {
798 continue;
799 }
800 ds_dc_type ds_dcs[4];
801 size_t len = 0;
802 for (size_t parent_suit = 0; parent_suit < 4; parent_suit++)
803 {
804 const fcs_pos_by_rank pos = positions_by_rank[FCS_POS_IDX(
805 fcs_card_rank(card) + 1, parent_suit)];
806
807 if ((pos.col < 0) || ((stack_i)pos.col == source_stack_idx))
808 {
809 continue;
810 }
811
812 ds_dcs[len++] = pos;
813 }
814
815 // This is done to preserve the original order in the solutions.
816 sort_ds_dcs(ds_dcs, (int)len);
817
818 for (size_t i = 0; i < len; i++)
819 {
820 const stack_i dest_stack_idx = (stack_i)ds_dcs[i].col;
821 const size_t dest_card_height = (size_t)ds_dcs[i].height;
822 const_AUTO(dest_col, fcs_state_get_col(state_key, dest_stack_idx));
823
824 // This is a suitable parent - let's check if there's a sequence above
825 // it.
826 sequences_analysis seqs;
827
828 if (POPULATE_AND_CHECK_IF_FALSE_SEQ(dest_col, (int)dest_card_height,
829 source_stack_idx, dest_stack_idx, true))
830 {
831 sfs_check_state_begin();
832 copy_two_stacks(source_stack_idx, dest_stack_idx);
833 // Move the junk cards to their place
834 move_sequences_analysis_seqs_loop(
835 &pass_new_state SFS__PASS_MOVE_STACK(moves), &seqs,
836 dest_stack_idx,
837 fcs_col_len(dest_col) PASS_IND_BUF_T(indirect_stacks_buffer));
838
839 fcs_move_sequence(
840 dest_stack_idx, source_stack_idx, (size_t)(col_len));
841
842 sfs_check_state_end();
843 }
844 }
845 STACK_SOURCE_LOOP_END()
846 }
847
DECLARE_MOVE_FUNCTION(fc_solve_sfs_simple_simon_move_sequence_to_parent_on_the_same_stack)848 DECLARE_MOVE_FUNCTION(
849 fc_solve_sfs_simple_simon_move_sequence_to_parent_on_the_same_stack)
850 {
851 SIMPS_define_vacant_stacks_accessors();
852
853 STACK_SOURCE_LOOP_START(3)
854 // Search for a parent card
855 for (int parent_card_height = 0; parent_card_height < col_len - 2;
856 parent_card_height++)
857 {
858 const fcs_card parent_card = fcs_col_get_card(col, parent_card_height);
859 if (fcs_is_ss_true_parent(
860 parent_card, fcs_col_get_card(col, parent_card_height + 1)))
861 {
862 continue;
863 }
864
865 for (int child_card_height = parent_card_height + 2;
866 child_card_height < col_len; child_card_height++)
867 {
868 if (!fcs_is_ss_true_parent(
869 parent_card, fcs_col_get_card(col, child_card_height)))
870 {
871 continue;
872 }
873 // We have a matching parent and child cards
874 // Now let's try to find stacks to place the cards above the child
875 // card.
876
877 int end_of_child_seq = child_card_height;
878 size_t child_num_true_seqs = 1;
879 while (
880 (end_of_child_seq + 1 < col_len) &&
881 fcs_is_ss_false_parent(fcs_col_get_card(col, end_of_child_seq),
882 fcs_col_get_card(col, end_of_child_seq + 1)))
883 {
884 child_num_true_seqs += (!fcs_is_ss_true_parent(
885 fcs_col_get_card(col, end_of_child_seq),
886 fcs_col_get_card(col, end_of_child_seq + 1)));
887 ++end_of_child_seq;
888 }
889
890 sequences_analysis seqs;
891 populate_seq_points(col, end_of_child_seq, &seqs);
892
893 // Add the child to the seq_points
894 const_AUTO(child_seq_index, seqs.num_separate_false_seqs);
895 seqs.above_num_true_seqs[seqs.num_separate_false_seqs] =
896 child_num_true_seqs;
897 seqs.seq_points[seqs.num_separate_false_seqs++] = child_card_height;
898
899 // Add the cards between the parent and the child to the seq_points
900 generic_populate_seq_points(
901 col, parent_card_height, &seqs, child_card_height);
902
903 // Let's check if we can move the child after we are done moving all
904 // the junk cards
905 if (!(IS_false_seq_index_loop(
906 col, false, source_stack_idx, source_stack_idx) &&
907 (calc_max_simple_simon_seq_move(
908 seqs.after_junk_num_freestacks) >=
909 child_num_true_seqs)))
910 {
911 continue;
912 }
913 sfs_check_state_begin();
914
915 // Move the junk cards to their place
916
917 my_copy_stack(source_stack_idx);
918 move_sequences_analysis_seqs_loop(
919 &pass_new_state SFS__PASS_MOVE_STACK(moves), &seqs,
920 source_stack_idx,
921 col_len PASS_IND_BUF_T(indirect_stacks_buffer));
922 const_AUTO(src_col_i, seqs.junk_move_to_stacks[child_seq_index]);
923 my_copy_stack(src_col_i);
924 fcs_move_sequence(source_stack_idx, src_col_i,
925 (size_t)(end_of_child_seq - child_card_height + 1));
926
927 sfs_check_state_end();
928 }
929 }
930 STACK_SOURCE_LOOP_END()
931 }
932
DECLARE_MOVE_FUNCTION(fc_solve_sfs_simple_simon_move_sequence_to_false_parent)933 DECLARE_MOVE_FUNCTION(fc_solve_sfs_simple_simon_move_sequence_to_false_parent)
934 {
935 // num_true_seqs - the number of true sequences on the current
936 // false sequence
937 SIMPS_define_vacant_stacks_accessors();
938
939 const size_t max_seq_move =
940 calc_max_simple_simon_seq_move(num_vacant_stacks);
941
942 STACK_SOURCE_LOOP_START(1)
943 size_t num_true_seqs;
944 const int height = get_seq_h(col, &num_true_seqs);
945 // Let's check if we have enough empty stacks to make the move
946 // feasible.
947 if (max_seq_move < num_true_seqs)
948 {
949 continue;
950 }
951 const fcs_card src_card = fcs_col_get_card(col, height);
952
953 // take the sequence and try and put it on another stack
954 STACK_DEST_LOOP_START(1)
955 if (!fcs_is_ss_false_parent(
956 fcs_col_get_card(dest_col, dest_col_len - 1), src_card))
957 {
958 continue;
959 }
960
961 sfs_check_state_begin();
962 copy_two_stacks(source_stack_idx, dest_stack_idx);
963 fcs_move_sequence(
964 dest_stack_idx, source_stack_idx, (size_t)(col_len - height));
965 sfs_check_state_end();
966 STACK_DEST_LOOP_END()
967 STACK_SOURCE_LOOP_END()
968 }
969
970 #endif // #ifdef FCS_DISABLE_SIMPLE_SIMON
971