mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Puzzles (https://www.mersenneforum.org/forumdisplay.php?f=18)

 Xyzzy 2021-09-02 11:05

September 2021

[url]https://www.research.ibm.com/haifa/ponderthis/challenges/September2021.html[/url]

 dg211 2021-09-07 14:07

I'd be interested to see what the best values people can find are. My best solutions so far are 40 and 149.

 Dieter 2021-09-13 09:57

[QUOTE=dg211;587442]I'd be interested to see what the best values people can find are. My best solutions so far are 40 and 149.[/QUOTE]

That are very good values. I'm happy to have found a 50-solution this morning - too late for being listed.
It's consoling for me that there are not many solvers until 11/09.
I have no code producing a complete solution, but only codes optimizing versions found with pencil and paper.

 dg211 2021-09-13 10:12

Yeah, I think this is one of the toughest puzzles there has been recently.

I slightly improved the bonus solution to 147, but I'm still on 40 for the first part.

 Kebbaj 2021-09-13 18:10

I'm blocked at 54 damage. Normal pencil and paper cannot give a solution easily.
I only want to abandoned. So Difficult question!!

[8976 "," 4238 "," 8297 "," 4735 "," 3279 "]
31415926535897932384626433832795028841971693993751058209749445923078164
3-2-79-4735897642384735423832793-2798-97-68297473--582-9747354753-89-76
54 damage.

This solution does not spoil the challenge, it's blocked at 54.We have to start at the beginning, if we want another winning solution. But it can help!:smile:

 dg211 2021-09-13 18:36

Remember you can use hyphens in both strings.

I'm impressed people managed to get solutions that good with pen and paper, I didn't even try that approach because I thought it would be too hard.

 Kebbaj 2021-09-13 20:12

[QUOTE=dg211;587822]Remember you can use hyphens in both strings.

I'm impressed people managed to get solutions that good with pen and paper, I didn't even try that approach because I thought it would be too hard.[/QUOTE]

I am also impressed by the strength of formalizing the question and being able to code it. A question not easy to formalize.
But there, I'am obliged to get help with the calculation.
There are 1680 possible permutations from 2 to 9 for each quadruplet. I leave the 0's and 1's, they don't do a lot of damage.

Congrats, for this impressed solution 40 and 147.

 Dieter 2021-09-14 05:39

[QUOTE=Kebbaj;587819]I'm blocked at 54 damage. Normal pencil and paper cannot give a solution easily.
I only want to abandoned. So Difficult question!!

[8976 "," 4238 "," 8297 "," 4735 "," 3279 "]
31415926535897932384626433832795028841971693993751058209749445923078164
3-2-79-4735897642384735423832793-2798-97-68297473--582-9747354753-89-76
54 damage.

This solution does not spoil the challenge, it's blocked at 54.We have to start at the beginning, if we want another winning solution. But it can help!:smile:[/QUOTE]

Your last 4735 has changed to 4753 ("Zahlendreher"), but without consequences for the damage.

 Kebbaj 2021-09-14 09:49

[QUOTE=Dieter;587841]Your last 4735 has changed to 4753 ("Zahlendreher"), but without consequences for the damage.[/QUOTE]

"Unaufmerksamkeitsfehler" "خطء فني"
Well seen this Permutation typing error without consequences for the damage. Thanks Dieter!
Question:
Can we find less than 54 damage without any pulling on the sequance pi?
**
Congrats Dieter, for solving with the manual "to tear out"!

 Kebbaj 2021-09-14 14:48

I'm stubborn as a mule!

Finally, I had score 50, with a lot of damage to my neurons !!
Nice Challenge sept 2021.

I can go to work now!!
Liberation!:smile:

 kruoli 2021-09-14 15:33

[QUOTE=Kebbaj;587845]"Unaufmerksamkeitsfehler"[/QUOTE]

Personally, I never heard that word. But as always with German compound words, it is understandable. I'd suggest "Flüchtigkeitsfehler", which of course is slightly different, literally, but more about what you wanted, I think.
[/PEDANTIC]

 LaurV 2021-09-15 02:55

That's a nice puzzle, actually. Pity I missed it :sad: but the RL[SUP](TM)[/SUP] kept me busy...

 uau 2021-09-16 21:23

I got 40 for the base problem and 144 for bonus.

 uau 2021-09-17 17:26

By the way the 175 limit for the bonus question seems very lax. Can it actually be said to be harder than the main question? Is there any natural way to solve it which would fail to also get 175 for the bonus one?

 Kebbaj 2021-09-22 10:03

[QUOTE=dg211;587822]Remember you can use hyphens in both strings.
.[/QUOTE]

The list of solvers is published. Congrats Dieter!
The remark : "Remember you can use hyphens in both strings". by "dg211" was decisive for me.
Thanks "dg211"!
That allowed me to leave the framework that I was fix it by obstinacy!
I think in my thought I would find it hard to think about two strings at the same time: The "Villain and Heroes" lines. So I persisted to find a solution for the sake of simplicity on a single string "Heroes" , Until I couldn't take anymore less. Since we are blocked at 54. A less than someone found better.

The lesson I learned is "sometimes you have to go out of the box to find a solution".
Thank you,

 Dieter 2021-10-04 10:03

The published bonus solution agrees with my submitted solution (174).
I would like to know the teams for the better solutions (<150).

 uau 2021-10-04 11:24

["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 2021-10-04 12:57

[QUOTE=Dieter;589368]The published bonus solution agrees with my submitted solution (174).[/QUOTE]
The teams in the example solution are ["4809", "5284", "1065", "1382", "3469"]. But the given match strings are not optimal for those teams. I get 160 damage for them. Looking at the given matches, there's for example this (at position 39 in the strings):
4197
5284
with 1+1+1+3=6 damage. But using team 4809 instead of 5284, you get:
419-7
4-809
with 0+1+1+0+2=4 damage.

So you get 160 damage for those teams, and they can be further improved with one-digit changes:
["4809", "5284", "1065", "1382", "3469"]: 160
["4809", "6284", "1065", "1382", "3469"]: 157
["4809", "6284", "1065", "0382", "3469"]: 155

Improving further would require a two-digit change:
["4809", "6284", "1065", "0382", "0459"]: 154

Improving from that requires changing 4 digits:
["4709", "5280", "1065", "0382", "0759"]: 152
["4709", "5280", "9061", "0382", "0154"]: 151

Further improvements would require 5 or more changes, I didn't check for those.

 SmartMersenne 2021-10-04 22:56

It would be great if people who solved it, can share their code.

 uau 2021-10-05 11:43

Well here is a slightly cleaned up version of the code I used. By default it uses a C routine to calculate optimal damage for given teams. You can disable that, and the pure Python code is still easily enough to solve the problem and give something like a 150 solution for the bonus problem, but waiting for the 144 solution might take quite a while. With the C version properly compiled, you should find the 144 solution within a couple of minutes.

[CODE]
#!/usr/bin/python3

import random
import sys

# Calculate best possible damage value for given teams
def calc(seq, teams):
seq = seq + [0]
states = [(i, j) for i in range(len(teams))
for j in range(1, len(teams[i]))] + [None]
this = dict.fromkeys(states, 1e99)
this[None] = 0
for s in seq:
nxt = dict.fromkeys(states, 1e99)
for state in states:
cost = this[state]
nxt[state] = min(nxt[state], cost + s)
if state is None:
for teami2, team in enumerate(teams):
cost2 = cost
for j, tval in enumerate(team):
state2 = (teami2, j+1) if j + 1 < len(team) else None
nxt[state2] = min(nxt[state2], cost2 + abs(s - tval))
cost2 += tval
break
teami, pos = state
team = teams[teami]
tval = team[pos]
state2 = (teami, pos+1) if pos + 1 < len(team) else None
nxt[state2] = min(nxt[state2], cost + abs(s - tval))
this[state2] = min(this[state2], cost + tval)
this = nxt
return this[None]

orig_calc = calc

if 1:
# Import C version for much faster calc() implementation.
# It only works for 5 teams of 4.
import ctypes
clib = ctypes.CDLL("./ibm_ponderthis_202109.so")
from itertools import chain
def calc(seq, teams):
res = clib.calc(bytes(list(chain(*teams))), bytes(seq + [0]), len(seq)+1)
# assert res == orig_calc(seq, teams)
return res

# Print the matching sequences required for puzzle answer. I didn't
# implement the actual format required by the puzzle, this just splits
# the sequence into parts matched by a single team, printing each matching
# part together with the team (or '-' for skip outside team).
#
# To avoid cluttering the calc() code with keeping track of how exactly
# the best solution is formed, this code instead indirectly reconstructs
# a possible best match.

def out(seq, teams):
print('start')
res = calc(seq, teams)
while seq:
for i in range(1, len(seq)+1):
res1 = calc(seq[:i], teams)
res2 = calc(seq[i:], teams)
if res1 + res2 == res:
print(seq[:i])
if sum(seq[:i]) == res1:
print('-')
else:
for team in teams:
if orig_calc(seq[:i], [team]) == res1:
print(team)
break
else:
assert 0
res = res2
seq = seq[i:]
print('diff:', res1)
break
print('end')

def search(seq, teams, offset, maxdepth, bestval, bestteams=None):
for a in range(offset, 20):
t, i = divmod(a, 4)
orig = teams[t]
for k in range(10):
if k in orig:
continue
teams[t] = orig.copy()
teams[t][i] = k
r = calc(seq, teams)
if r < bestval:
print(r, teams)
bestval = r
bestteams = [x.copy() for x in teams]
sys.stdout.flush()
if maxdepth > 1:
bestval, bestteams = search(seq, teams, a + 1, maxdepth - 1,
bestval, bestteams)
teams[t] = orig
return bestval, bestteams

def canon(l):
ll = ['0'*y.count(0)+''.join(str(x) for x in y if x > 0) for y in l]
ll.sort()
return tuple(ll)

seq = [int(x) for x in "314159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196"]

bestval = allbest = 1e99
teams = [random.sample(range(10), 4) for _ in range(5)]
c = None
while 1:
bestval, bestteams = search(seq, teams, 0, 1, bestval)
print('iter done')
if bestteams is None:
c = canon(teams)
allbest = min(allbest, bestval)
print('canonical form:', c, bestval, '/', allbest)
if bestval <= 144:
break
bestteams = [random.sample(range(10), 4) for _ in range(5)]
bestval = 1e99
teams = bestteams

out(seq, teams)
[/CODE]

Here's the C code. You need to compile this into a shared library in the same directory for the Python code to load. On Linux "gcc -O3 -shared thiscode.c -o ibm_ponderthis_202109.so" should work.

[CODE]
#include <assert.h>
#include <stdlib.h>
#include <string.h>

#define MIN(x, y) (((x) < (y)) ? (x) : (y))

int calc(unsigned char *teams, unsigned char *seq, int len) {
assert(seq[len - 1] == 0);
unsigned short best[3*5 + 2];
memset(best, -2, sizeof(best));
best[0] = 0;

for (int seqp = 0; seqp < len; seqp++) {
int s = seq[seqp];
int besti = 2;
for (int teami = 0; teami < 5; teami++) {
int cost1 = best[besti];
best[besti] += s;
int tval = teams[4*teami + 1];
besti++;
int cost2 = MIN(best[besti], cost1 + tval);
best[besti] = MIN(cost1 + abs(s - tval), cost2 + s);
tval = teams[4*teami + 2];
besti++;
int cost3 = MIN(best[besti], cost2 + tval);
best[besti] = MIN(cost2 + abs(s - tval), cost3 + s);
tval = teams[4*teami + 3];
besti++;
best[0] = MIN(best[0], cost3 + tval);
best[1] = MIN(best[1], cost3 + abs(s - tval));
}
besti = 2;
for (int teami = 0; teami < 5; teami++) {
int cost = best[0];
for (int j = 0; j < 3; j++) {
int tval = teams[teami*4 + j];
best[besti] = MIN(best[besti], cost + abs(s - tval));
besti++;
cost += tval;
}
int tval = teams[teami*4 + 3];
best[1] = MIN(best[1], cost + abs(s - tval));
}
best[0] = MIN(best[1], best[0] + s);
best[1] = -1;
}
return best[0];
}
[/CODE]

 SmartMersenne 2021-10-06 00:52

[QUOTE=uau;589521]Well here is a slightly cleaned up version of the code I used. By default it uses a C routine to calculate optimal damage for given teams. You can disable that, and the pure Python code is still easily enough to solve the problem and give something like a 150 solution for the bonus problem, but waiting for the 144 solution might take quite a while. With the C version properly compiled, you should find the 144 solution within a couple of minutes.[/QUOTE]

Are the calc routines in both languages doing exactly the same thing?

 All times are UTC. The time now is 22:31.