Thread: September 2021
View Single Post
Old 2021-10-04, 11:24   #17
uau
 
Jan 2017

112 Posts
Default

["0381", "0645", "0896", "0923", "5279"] gives 144 damage for the bonus question.

I found this by writing an exact solver for the best possible damage value for given teams, and then starting from random teams and changing one number at a time until the teams could no longer be improved. It seems that one number at a time is enough in the sense that trying simultaneous multiple-place changes just makes the search slower - it's more efficient to do single-place changes and start from a new random position if the search gets stuck.

My implementation searched for the overall best change and then did that, instead of picking the first one that showed any improvement at all. I'm not sure whether that would matter for how likely it is to converge to a good solution.

The 175 limit seems very easy in the sense that almost all random starting points seem to lead to better solutions than that with single-digit changes (though not literally all). I think finding the 144 one is something around 1 in 1000 to 10000 random starting positions with one-digit changes. My implementation finds that within a couple of minutes (exact time of course varies since it's a random chance to find it at each attempt). I wrote the "best damage with given teams" part in C, and other search logic in Python.

I left a search running for a longer time, and it seems that if there is a solution better than 144, it's vastly harder to find with this kind of search. There are no alternative 144 solutions either (modulo order of teams and placement of '0' values within a team). Best solutions found:

144: 1 solution
('0381', '0645', '0896', '0923', '5279')

145: 9 solutions
('0284', '0379', '0645', '0821', '0896')
('0379', '0384', '0645', '0821', '0896')
('0279', '0384', '0645', '0821', '4896')
('0284', '0415', '0816', '0896', '0938')
('0284', '0415', '0816', '0897', '0938')
('0381', '0645', '0896', '0923', '5269')
('0381', '0645', '0896', '0923', '6279')
('0381', '0645', '0897', '0923', '5279')
('0381', '0645', '0923', '5279', '8196')

146: 29 solutions
('0279', '0284', '0645', '0821', '0896')
('0384', '0479', '0645', '0821', '0896')
('0284', '0379', '0645', '0821', '0897')
('0264', '0347', '0528', '0938', '0964')
('0254', '0347', '0528', '0938', '0964')
('0379', '0384', '0645', '0821', '0897')
('0279', '0384', '0645', '0821', '0896')
('0283', '0435', '0938', '2896', '8645')
('0435', '0916', '0938', '4382', '8649')
('0279', '0384', '0654', '0821', '4896')
('0283', '0514', '0896', '0938', '8645')
('0379', '0384', '0645', '0821', '8196')
('0284', '0514', '0896', '0937', '8645')
('0284', '0514', '0896', '0938', '8645')
('0279', '0384', '0645', '0821', '5896')
('0379', '0384', '0645', '0821', '4896')
('0384', '0479', '0821', '0896', '6415')
('0284', '0415', '0816', '0897', '9318')
('0415', '0694', '0816', '0897', '2843')
('0379', '0384', '0645', '0821', '8197')
('0381', '0645', '0823', '0896', '5279')
('0381', '0645', '0897', '0923', '6279')
('0284', '0379', '0645', '0821', '8196')
('0381', '0645', '0897', '0923', '5269')
('0284', '0379', '0645', '0821', '8197')
('0284', '0415', '0816', '0896', '9318')
('0381', '0645', '0923', '5279', '8197')
('0381', '0645', '0923', '5269', '8196')
('0381', '0645', '0923', '6279', '8196')

One thing to note is that most solutions have '0' in most teams. This helps make the teams effectively 3 in length (you can always pair the 0 with a skip). Shorter teams are more likely to match random patterns.
uau is offline   Reply With Quote