A Solution Algorithm for Dudley’s Hat Problem
An algorithmic experiment for Dudley's Hat that dynamically tracks subset-sum constraints to reduce search work; the historical project record reached a value of 27.
This project explored an alternative search strategy for the combinatorial problem I recorded as Dudley's Hat.
Under the surviving project definition, integers are placed in three increasing arrays. A new value can be added only when it does not conflict with subset sums already possible in that array and when it is larger than the previously added value.
The Expensive Part: Subset Sums
Testing a candidate requires knowledge of sums that can already be formed from earlier elements. Recomputing those combinations from scratch for every candidate quickly increases the search cost.
The approach I implemented tried to reuse the current state and validate candidates dynamically, reducing repeated work compared with a straightforward exhaustive search.
Experimental Result
The archived project record reports a largest value of 21 for the manual/comparison approaches and 27 for my implementation.
The surviving project record states that the implementation reached 27 instead of 21. Because the complete historical experiment specification is unavailable, the supported statement is narrower: the implementation reached 27 under the problem definition and conditions used in the project.
Search-Space Reduction vs Parallelism
Splitting a search across more threads and reducing the number of states that need to be searched are different optimizations. Parallelism can evaluate the same state space faster, while a better state representation or pruning rule can remove work entirely.
That distinction became one of the useful lessons of this project.
A related exponential-search experiment appears in my Subset Sum Optimization project, while Data Structures and Algorithm Analysis provides the broader complexity context.
