Path: csiph.com!eternal-september.org!feeder.eternal-september.org!nntp.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.lang.c Subject: Re: Cookies in boxes - algorithmic challenge Date: Tue, 21 Apr 2026 18:22:34 -0700 Organization: A noiseless patient Spider Lines: 112 Message-ID: <86tst36b6t.fsf@linuxsc.com> References: <20260401163447.000052de@yahoo.com> <86tstlwjak.fsf@linuxsc.com> <20260408222330.00005cf8@yahoo.com> <865x5zbg10.fsf@linuxsc.com> <20260411225637.0000632e@yahoo.com> <865x5x9kbw.fsf@linuxsc.com> <20260413171129.0000003d@yahoo.com> <86a4v26pup.fsf@linuxsc.com> <20260417144410.00006d46@yahoo.com> <865x5p7ir6.fsf@linuxsc.com> <20260420004318.000007dd@yahoo.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Date: Wed, 22 Apr 2026 01:22:37 +0000 (UTC) Injection-Info: dont-email.me; posting-host="99049ae40d76034458eb7791fd827e8a"; logging-data="2005672"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18QGguVjBZO01MZNME0TYjszRwUjBXSNW4=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:mtswbFGpvjvDTIL5avnmMeNpDAE= sha1:FA41BDHQ4V+Y4hxbSDViclhpFNM= Xref: csiph.com comp.lang.c:397768 Michael S writes: > On Fri, 17 Apr 2026 07:40:13 -0700 > Tim Rentsch wrote: > >> My questions are these. One, could you understand what the code is >> doing and how it works? And two, if given an appropriate choice of >> what permutation is done in best_next_ctype(), does this code do the >> same thing as your code? I was trying to match the behavior of your >> code but I wasn't able to figure out how it decided where to go >> next. > > Here is the simplest form of the algorithm that I can come with. > Essentially, it is a serial non-recursive variant of the code of your > friend with no algorithmic or technical enhancements. > Even in this form it is not slow and hopefully makes the key idea more > obvious. I have difficulty reading code written in the style used below. I might describe it broadly as too many trees and not enough forest. That comment is not meant as criticism but given just for informational value. My hope has been that my explanations, given first in prose and then in code, would let you understand how I approached the problem, so you could see how your approach differs from mine and then explain what the differences are. As things stand I don't know what are the common points of reference, or even whether there are any important ones. Having said that, let me ask this. What is your goal? I find myself wondering if we are talking past each other. > #include > #include > #include "solver.h" > > peek_t > solver( boxes_t boxes ){ > uint8_t box_of_cookie[N_BOXES]; // valid for selected sorts > for (int i = 0; i < N_BOXES; i++) > box_of_cookie[i] = N_BOXES; // value N_BOXES marks unselected sort > > // Selection proceeds in progressive steps. > // At each step we select one new box and one new sort. > // A box and a sort selected at step i are never unselected later > // although association between selected boxes and sorts > // can be changed > for (int step = 0; step < N_BOXES; ++step) { > typedef struct { > uint8_t box, sort; > } trace_t; > trace_t levels[N_BOXES]; > bool seen[N_BOXES] = {0}; > for (int lvl = 0, box = step; ;) { > // look for unseen sort in box > int sort; > for (int ci = 0; ci < BOX_SIZE; ++ci) { > sort = boxes.b[box][ci]; > if (!seen[sort]) > break; > } > if (seen[sort]) { // no unseen sorts in box > box = levels[--lvl].box; // return to previous level > continue; > } > // Unseen sort found > // It will become a new selection for box > int selected_box = box_of_cookie[sort]; > if (selected_box == N_BOXES) { > // sort unselected. > // it means that search at step i succeed > // commit preserved assignments > for (int k = 0; k < lvl; ++k) > box_of_cookie[levels[k].sort] = levels[k].box; > // assign new sort > box_of_cookie[sort] = box; > break; > } > > // sort already selected > // Save new assignment for sort. > // Saved box also serves us if we return > // to the current level from above > levels[lvl++] = (trace_t){ .sort=sort, .box=box}; > // Mark sort as seen. > // That mark guarantees forward progress of the search > seen[sort] = true; > // Continue search. > // At the next level we will look for new selection > // for old box of sort > box = selected_box; > } > } > > // translate result from box_of_cookie[] to index of cookie in box > peek_t res; > for (int c = 0; c < N_BOXES; ++c) { > int b = box_of_cookie[c]; > for (int k = 0; k < BOX_SIZE; ++k) { > if (boxes.b[b][k] == c) { > res.b[b] = k; > break; > } > } > } > return res; > } Another question: is the above typical of how you usually write code, or are you writing it like that for my benefit?