Ponder This Challenge - May 2017 - Letter gaps

Ponder This Challenge:

In the string CABACB, each letter appears exactly twice and the number of characters between the "A"s is one, between the "B"s is two, and between the "C"s is three.

The same problem with the letters A-E cannot be solved, but adding a space (in the form of a hyphen) allows it to be solved.

For example, in the string ADAEC-DBCEB, the number of characters between the "A"s is one, between the "B"s is two, between the "C"s is three (counting the space), between the "D"s is four, and between the "E"s is five.

Find a string of letters (A-Z) and "-" whose length is no more than 53 characters, where each of the 26 letters A-Z appears exactly twice, and there is one character between the "A"s, two between the "B"s ... and 26 between the "Z"s.

Solution

• Click here to view the solution

  As David Greer wrote, a string of 52 characters is impossible using parity as follows: The letters A, C, E... have an odd number of spaces between their two appearances, so they must appear in positions of the same parity. Similarly B, D, F... must appear in positions of opposite parity. In a string of 52 letters, there are 26 odd and 26 even positions, of which 13 of each would be taken by the letters B, D, F..., leaving 13 odd and 13 even positions, with no way to divide into pairs of equal parity.

  Todd Will sent us a nice solution:
  IBMPONDERTHIS wasn't possible since the two letter Is are too far apart.
  But here are two other options.
  ORNQVXZWYSB-IBMPONDERQIDTEUVMSXWPZYJCLHKCAFAGTJHUFLKG
  AKAMGJORNYSVGKUXJMWDZPONDERTHISEQLVYUHPIXCW-FCLZTBQFB
  And Florian Fischer sent us an even nicer one:
  KPGOJNWCXVGCKYZJD-PONDERTHISEUWQVXHLIBMYBZRFATASLQFUM

  Matthew Charlap was the first among many who sent us the elegant solution:
  By the nature of the required spacing, all the "even" letters (B, D, F, etc.) can be nested, as can the odds:
  ZXVTRPNLJHFDB--BDFHJLNPRTVXZ (evens - 28 characters)
  YWUSQOMKIGECA-ACEGIKMOQSUWY (odds - 27 characters)
  Concatenating these gives us 55 characters - two characters too long (since three hyphens are used):
  ZXVTRPNLJHFDB--BDFHJLNPRTVXZYWUSQOMKIGECA-ACEGIKMOQSUWY
  Now, all 26 letters are between the hyphens, so if the Ys are removed, we get:
  ZXVTRPNLJHFDB--BDFHJLNPRTVXZWUSQOMKIGECA-ACEGIKMOQSUW,
  which has 25 letters between the hyphens--exactly what we need to put the Ys back in. Note that since Y is the outermost letter in the odds-string, removing it does not cause any other spacings to be broken.
  Putting the Ys around those middle 25 letters (replacing hyphens) results in:
  ZXVTRPNLJHFDB-YBDFHJLNPRTVXZWUSQOMKIGECAYACEGIKMOQSUW.
  This last string has the desired length of 53.
  Note that if we instead remove the Zs, and place them surrounding the other 25 letters and one of the two hyphens, we get another solution:
  XVTRPNLJHFDBZ-BDFHJLNPRTVXYWUSQOMKIGECAZACEGIKMOQSUWY
  This process can easily be generalized for any set of characters separated by 1, 2, 3, ..., n spaces.

Solvers

• Robert Gerbicz (28/04/2017 01:49 AM IDT)
• Rickard Björklund (28/04/2017 02:26 AM IDT)
• Noah Lordi (28/04/2017 05:23 AM IDT)
• Igor Karp (28/04/2017 07:22 AM IDT)
• Kang Jin Cho (28/04/2017 09:08 AM IDT)
• Clive Tong (28/04/2017 10:36 AM IDT)
• Yan-Wu He (28/04/2017 11:35 AM IDT)
• Alex Fleischer (28/04/2017 12:54 PM IDT)
• Matthew Charlap (28/04/2017 05:18 PM IDT)
• Dan Dima (28/04/2017 07:54 PM IDT)
• Steven Langerwerf (28/04/2017 08:22 PM IDT)
• Bert Dobbelaere (28/04/2017 09:06 PM IDT)
• Todd Will (28/04/2017 10:00 PM IDT)
• Evert van Dijken (28/04/2017 11:25 PM IDT)
• Oleg Vlasii (28/04/2017 11:32 PM IDT)
• Leonid Kalmankin (29/04/2017 12:17 AM IDT)
• Roddy MacPhee (29/04/2017 12:31 AM IDT)
• Jesse Rearick (29/04/2017 12:56 AM IDT)
• Pål Hermunn Johansen (29/04/2017 01:33 AM IDT)
• Dmitry Kim (29/04/2017 02:06 AM IDT)
• Paolo Farinelli (29/04/2017 06:44 AM IDT)
• Sean Egan (29/04/2017 07:51 AM IDT)
• Antonio García Astudillo (29/04/2017 02:07 PM IDT)
• Thomas Satzger (29/04/2017 09:05 PM IDT)
• Andreas Knüpfer (29/04/2017 11:53 PM IDT)
• Reiner Martin (30/04/2017 12:01 AM IDT)
• Guy Danielli (30/04/2017 12:41 AM IDT)
• Leo Broukhis (30/04/2017 04:06 AM IDT)
• Shirish Chinchalkar (30/04/2017 05:05 AM IDT)
• Dejan Stakić (30/04/2017 08:49 AM IDT)
• Anatoly Vorobey (30/04/2017 11:40 AM IDT)
• George Barnett (30/04/2017 12:00 PM IDT)
• Aviv Nisgav (30/04/2017 01:00 PM IDT)
• Emir Haleva (30/04/2017 04:38 PM IDT)
• Khalid Saad Alkhorayef (30/04/2017 06:15 PM IDT)
• Andreas Stiller (30/04/2017 06:54 PM IDT)
• Rob Pratt (30/04/2017 08:19 PM IDT)
• Markus Sprecher (30/04/2017 10:51 PM IDT)
• Nyles Heise (01/05/2017 06:28 AM IDT)
• Arjun Ravichandran (01/05/2017 11:05 AM IDT)
• Alexandr Kozlinskiy (01/05/2017 12:34 PM IDT)
• Joseph DeVincentis (01/05/2017 03:52 PM IDT)
• Movin Jain (01/05/2017 04:08 PM IDT)
• Hanlin Ren (01/05/2017 05:18 PM IDT)
• Adrian Orzepowski (01/05/2017 05:26 PM IDT)
• Uoti Urpala (01/05/2017 07:43 PM IDT)
• Mishio Rusterholz (01/05/2017 08:16 PM IDT)
• Kest Che (01/05/2017 08:33 PM IDT)
• Edwin Hall (01/05/2017 09:42 PM IDT)
• Adam Kozdron (01/05/2017 11:44 PM IDT)
• Rashid Naimi (01/05/2017 11:53 PM IDT)
• Tyler Mullen (02/05/2017 12:08 AM IDT)
• Harald Bögeholz (02/05/2017 02:59 AM IDT)
• Aris Nikolaou (02/05/2017 10:43 AM IDT)
• Matej Kollar (02/05/2017 11:36 AM IDT)
• Irina Basieva (02/05/2017 01:23 PM IDT)
• Rohini Kumar Barla (02/05/2017 05:14 PM IDT)
• Liubing Yu (02/05/2017 07:01 PM IDT)
• Boris Rakús (02/05/2017 07:04 PM IDT)
• Károly Csalogány (02/05/2017 07:55 PM IDT)
• David F.H. Dunkley (02/05/2017 08:28 PM IDT)
• JJ Rabeyrin (02/05/2017 09:55 PM IDT)
• Erik Wünstel (02/05/2017 10:45 PM IDT)
• Ali Can Keserel (03/05/2017 12:41 AM IDT)
• Paul Shaw (03/05/2017 10:03 AM IDT)
• Nigel Brumpton (03/05/2017 11:24 AM IDT)
• Sebastian Bohm & Martí Bosch (03/05/2017 11:45 AM IDT)
• Alper Halbutogullari (03/05/2017 01:20 PM IDT)
• Francis Golding (03/05/2017 01:22 PM IDT)
• Rudy Cortembert (03/05/2017 01:41 PM IDT)
• Thomas Egense (03/05/2017 02:07 PM IDT)
• Umut Uludag (03/05/2017 04:11 PM IDT)
• Lei Zhang (03/05/2017 10:18 PM IDT)
• Daniëlle van den Berg (03/05/2017 11:33 PM IDT)
• Yoav Kaempfer (04/05/2017 02:06 AM IDT)
• Radu Haiduc (04/05/2017 02:32 AM IDT)
• Kaifei Chen (04/05/2017 06:06 AM IDT)
• Kandala Srinivas (04/05/2017 06:30 AM IDT)
• Tim Cieplowski (04/05/2017 07:54 AM IDT)
• Chen Yingxiang (04/05/2017 01:19 PM IDT)
• Wu Manchery (04/05/2017 02:08 PM IDT)
• Vasu Venkateshwaran (04/05/2017 03:14 PM IDT)
• Mathias Schenker (04/05/2017 05:04 PM IDT)
• Andreas Eisele (05/05/2017 10:36 AM IDT)
• Tamir Ganor & Shouky Dan (05/05/2017 12:30 PM IDT)
• Soumitra Agarwal (05/05/2017 05:43 PM IDT)
• Andreas Kremmydas (05/05/2017 11:16 PM IDT)
• Florian Fischer (06/05/2017 02:35 AM IDT)
• David Greer (06/05/2017 04:55 AM IDT)
• Soumik Mukhopadhyay (06/05/2017 06:37 AM IDT)
• Michael Liepelt (06/05/2017 10:08 AM IDT)
• Lorenz Reichel (06/05/2017 05:27 PM IDT)
• Ricardo Koller (06/05/2017 07:01 PM IDT)
• Eric Farmer (06/05/2017 09:54 PM IDT)
• Peter Gerritson (06/05/2017 09:57 PM IDT)
• Vladimir Volevich (06/05/2017 10:05 PM IDT)
• Amos Guler (07/05/2017 08:15 AM IDT)
• Luca Pintori (07/05/2017 06:24 PM IDT)
• Tihomir Mescic (07/05/2017 08:24 PM IDT)
• Serge Batalov (08/05/2017 06:55 AM IDT)
• David Friedman (08/05/2017 07:07 PM IDT)
• Rami Pearl (08/05/2017 07:42 PM IDT)
• Alexandru Nicau (09/05/2017 03:03 AM IDT)
• Aleksey Nekrasov (09/05/2017 01:50 PM IDT)
• Wolfgang Kais (10/05/2017 02:19 AM IDT)
• Armin Krauß (10/05/2017 01:53 PM IDT)
• Christian Pfaffenzeller (10/05/2017 03:48 PM IDT)
• Ahmed Khalaf (10/05/2017 05:04 PM IDT)
• Patrick Fussell (10/05/2017 08:44 PM IDT)
• Ismail Farach (11/05/2017 01:15 AM IDT)
• Jérémie Bernier (11/05/2017 02:33 PM IDT)
• Michael Rosola (11/05/2017 05:45 PM IDT)
• Susanne Wienand (12/05/2017 11:00 AM IDT)
• Felix André Huguenin (12/05/2017 04:55 PM IDT)
• Teake Nutma (15/05/2017 11:00 AM IDT)
• Stéphane Higueret (15/05/2017 04:54 PM IDT)
• Ran Sharon (15/05/2017 10:11 PM IDT)
• Adrian Neacsu (15/05/2017 11:01 PM IDT)
• Tero Patana (16/05/17 03:20 AM IDT)
• Michael Pruglo (16/05/17 12:46 PM IDT)
• Erik Lagerstedt (16/05/17 06:39 PM IDT)
• Sergey Koposov (16/05/17 10:03 PM IDT)
• Lingxi Chen (17/05/17 04:17 AM IDT)
• Joehyun Kim (17/05/17 05:02 AM IDT)
• Abhor Gupta (17/05/17 04:05 PM IDT)
• Rahul Upakare (17/05/17 04:39 PM IDT)
• Ahmed Halabya (17/05/17 07:18 PM IDT)
• Rajesh Sathiyanarayanan (17/05/17 09:00 PM IDT)
• Ron Porath (18/05/17 12:26 AM IDT)
• Hui Wang (18/05/17 06:06 AM IDT)
• Jochen Voss (18/05/17 03:52 PM IDT)
• Nathan Bui (18/05/17 05:54 PM IDT)
• Varun Ahluwalia (19/05/17 12:49 AM IDT)
• Merse E. Gáspár (19/05/17 01:43 AM IDT)
• Uma Ramanathan (19/05/17 11:49 AM IDT)
• Vladimir Dorofeev (19/05/17 12:35 PM IDT)
• Joshua Gunderson (19/05/17 11:56 PM IDT)
• Peter Rady (20/05/17 07:21 PM IDT)
• Hugo Pfoertner (20/05/17 10:01 PM IDT)
• Eran Grosbard (21/05/17 05:00 PM IDT)
• Philippe Fondanaiche (21/05/17 09:27 PM IDT)
• Pieter Vandercammen (21/05/17 10:45 PM IDT)
• Ahmed Samir (21/05/17 11:15 PM IDT)
• Fabio Filatrella (22/05/17 07:40 PM IDT)
• Erik Hostens (22/05/17 10:15 PM IDT)
• Vladimir M. Milovanović (22/05/17 10:22 PM IDT)
• Jang Hun Choi (23/05/17 12:06 AM IDT)
• Jake Ellowitz (23/05/17 02:51 AM IDT)
• Yurii Lahodiuk (24/05/17 02:39 AM IDT)
• Greg Janée (24/05/17 05:55 AM IDT)
• Shen Huang (26/05/17 02:31 AM IDT)
• Motty Porat (27/05/17 02:48 AM IDT)
• David Vainapel (28/05/17 09:49 AM IDT)
• Suryaprasad Kareenahalli (28/05/17 01:20 PM IDT)
• Yuval Snappir (29/05/2017 01:35 AM IDT)
• David Stevens (30/05/17 08:48 PM IDT)
• Anders Bisbjerg Madsen (30/05/17 09:50 PM IDT)
• Radu-Alexandru Todor (31/05/17 12:36 AM IDT)
• Stephen Lesko (31/05/17 06:34 AM IDT)
• Alexander Chetverin (01/06/17 04:32 AM IDT)
• Oscar Volpatti (01/06/17 08:29 AM IDT)