Ponder This

Welcome to our monthly puzzles.
You are cordially invited to match wits with some of the best minds in IBM Research.

Septmeber 2021 - Challenge

<< August


A group of superheroes is dispatched to deal with menacing supervillains in the following manner: The superheroes are denoted by the numbers 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 and the supervillains are also denoted by the same numbers.

When superhero number i is dispatched to deal with supervillain j, the collateral damage caused as result is represented as the number |i-j|. If the supervillain j is not dealt with, the damage is j and if for some reason the superhero i is dispatched without an enemy, it will result in i damage as well (superheroes always find something to do).

We can describe a sequence of supervillain incidents as a string of numbers. For example, the string

271828

means supervillain 2 causes an incident, afterwards supervillain 7 causes one, then 1, and 8 and then 2 returns to cause another incident, and then 8 returns to cause yet another incident.

Superheroes are dispatched via a similar string. The two strings are then compared and the total damage is computed. In our example, if the heroes are dispatched via the string 254828 then the total damage is 5 (|5-7| + |4-1|).

By adding hyphens, we can indicate an empty part of the string, as compared to the other string. If we compare the strings

271828
25-828

Then the damage is 3 instead of 5, since comparing "1" and "-" results only in 1 point of damage.

To further complicate matters, superheroes agree to be dispatched only as part of a group. Such a group is a string of four digits, all distinct. There can be only a limited number of possible groups, every group can be dispatched more than once, and a superhero can be part of many groups.

Given a string of supervillain activities, groups are dispatched to create a similar string of superheroes, hyphens can be freely added to both strings, and then the damage is computed.
As an example, given the supervillain sequence "271828182846" and the superhero groups "3945", "0278", and "9583", we dispatch the group "0278", then "0278" again and then "3945" and obtain "027802783945". We then add hyphens and get:

-2718-28182846
027-8027-83945

Which results in a damage of 6.

Your goal: For the supervillain sequence
"31415926535897932384626433832795028841971693993751058209749445923078164"
(first 71 digits of pi), find five superhero teams (of four distinct digits each) and a way to dispatch the teams such that the total damage is at most 50.

Give your result in the following format:
["3945", "0278", "9583"]
-2718-28182846
027-8027-83945

In which the first line gives the teams, the second line describes the supervillain sequence with hyphens, and the third line gives the superhero sequence with hyphens.



A bonus "*" Same as above, but for the sequence
"314159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196"

(first 201 digits of pi). Again, with five teams of four digits each, and damage at most of 175.




We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

 

Challenge: 30/08/2021 @ 12:00 PM EST
Solution: 04/10/2021 @ 12:00 PM EST
List Updated: 11/09/2021 @ 12:00 PM EST

People who answered correctly:

*Bert Dobbelaere (2/9/2021 2:06 AM IDT)
*Lorenz Reichel (2/9/2021 10:40 PM IDT)
Bertram Felgenhauer (3/9/2021 11:37 AM IDT)
*Oleg Vlasii (3/9/2021 7:14 PM IDT)
Daniel Chong Jyh Tar (4/9/2021 6:40 AM IDT)
*Dominik Reichl (6/9/2021 12:44 AM IDT)
Paul Revenant (7/9/2021 12:22 AM IDT)
*Andreas Stiller (7/9/2021 1:42 PM IDT)
*David Greer (7/9/2021 5:21 PM IDT)
Alex Fleischer (8/9/2021 7:21 PM IDT)
*Liubing Yu (8/9/2021 7:15 AM IDT)
Alper Halbutogullari (11/9/2021 2:47 AM IDT)
*Sean Egan (11/9/2021 10:11 AM IDT)
*Clive Tong (11/9/2021 7:16 PM IDT)
Eran Vered (11/9/2021 7:43 PM IDT)