Ponder This

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

January 2023 - Challenge

<< December February >>


A "gene" of length n is a string of n letters from the character set {‘G’, ‘A’, ‘C’, ‘T’}.

The gene can be transformed into another gene in a sequence of steps. Each step changes exactly one letter in the gene.

In one step, the leftmost letter in the gene can be changed to any character in the set {‘G’, ‘A’, ‘C’, ‘T’}. Changing the remaining letters is subject to additional constraints:

  1. ‘T’ can be changed to ‘C’ if all the letters to its left are ‘C’.
  2. ‘T’ can be changed to ‘G’ if the letter to its immediate left is ‘C’, and the remaining letters to its left are ‘A’.
  3. ‘C’ can be changed to ‘T’ if all the letters to its left are ‘T’.
  4. ‘C’ can be changed to ‘A’ if the letter to its immediate left is ‘C’, and the remaining letters to its left are ‘A’.
  5. ‘A’ can be changed to ‘C’ if the letter to its immediate left is ‘C’, and the remaining letters to its left are ‘A’.
  6. ‘G’ can be changed to ‘T’ if all the letters to its left are ‘T’.

Given any gene, we wish to find a way to convert it to the gene "GGG...G" in the minimal number of steps.

For example, starting with the gene [‘C’, ‘T’, ‘T’, ‘G’, ‘G’], we can convert it to [‘G’, ‘G’, ‘G’, ‘G’, ‘G’] in the following eight steps:

[‘C’, ‘T’, ‘T’, ‘G’, ‘G’]
[‘C’, ‘C’, ‘T’, ‘G’, ‘G’]
[‘A’, ‘C’, ‘T’, ‘G’, ‘G’]
[‘A’, ‘C’, ‘G’, ‘G’, ‘G’]
[‘T’, ‘C’, ‘G’, ‘G’, ‘G’]
[‘T’, ‘T’, ‘G’, ‘G’, ‘G’]
[‘C’, ‘T’, ‘G’, ‘G’, ‘G’]
[‘C’, ‘G’, ‘G’, ‘G’, ‘G’]
[‘G’, ‘G’, ‘G’, ‘G’, ‘G’]

The solution can be written in the following manner, indicating sequentially in each step which letter position to convert (starting from 1), and to which letter to convert it:

[(2, ‘C’), (1, ‘A’), (3, ‘G’), (1, ‘T’), (2, ‘T’), (1, ‘C’), (2, ‘G’), (1, ‘G’)]

For the starting position [‘A’, ‘C’, ‘A’, ‘C’], the minimum number of steps to reach [‘G’, ‘G’, ‘G’, ‘G’] is 25.

Your goal: Find a starting position of 20 letters using only the characters ‘A’ and ‘C’ such that the minimal number of steps to reach a gene of all ‘G’ characters is between 880,000 and 890,000.

Provide your solution in two lines, the first containing the starting position in the same format as [‘A’, ‘C’, ‘A’, ‘C’], and the second line containing the minimal number of steps.

A Bonus "*" will be given for finding the minimal number of steps required for reaching the all-‘G’ state from an all-‘T’ state, for n=100 letters.


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: 04/01/2023 @ 10:00 AM EST
Solution: 04/02/2023 @ 12:00 PM EST
List Updated: 08/02/2023 @ 11:30 AM EST

People who answered correctly:

*Martin Bisson (5/1/2023 10:55 AM IDT)
*Lazar Ilic (5/1/2023 3:16 PM IDT)
Paul Shaw (5/1/2023 3:39 PM IDT)
*Paul Revenant (5/1/2023 4:05 PM IDT)
*Alper Halbutogullari (5/1/2023 8:15 PM IDT)
*Hakan Summakoğlu (5/1/2023 10:02 PM IDT)
*Richard T Liu (6/1/2023 1:01 AM IDT)
*Victor Chang (6/1/2023 6:45 AM IDT)
*Bertram Felgenhauer (6/1/2023 3:08 PM IDT)
*Daniel Chong Jyh Tar (6/1/2023 8:01 PM IDT)
Johannes Antonio Wolfgan Losert (6/1/2023 10:07 PM IDT)
*Bert Dobbelaere (7/1/2023 10:52 AM IDT)
*Daniel Bitin (7/1/2023 5:44 PM IDT)
*Stephen Herbert Jr (8/1/2023 10:07 AM IDT)
*Lorenzo Gianferrari Pini (8/1/2023 12:05 PM IDT)
Caleb (8/1/2023 12:16 PM IDT)
*Stéphane Higueret (8/1/2023 11:19 PM IDT)
*Amos Guler (9/1/2023 10:25 PM IDT)
*Martin Thorne (10/1/2023 4:08 AM IDT)
*Gary M. Gerken (10/1/2023 6:43 AM IDT)
*Vladimir Volevich (10/1/2023 12:19 PM IDT)
*Dominik Reichl (10/1/2023 5:19 PM IDT)
*Seth Cohen (11/1/2023 5:55 AM IDT)
Kennedy (11/1/2023 10:40 PM IDT)
Michael Liepelt (12/1/2023 9:50 AM IDT)
Guillaume Escamocher (13/1/2023 4:37 PM IDT)
*Lorenz Reichel (13/1/2023 6:00 PM IDT)
*Harald Bögeholz (14/1/2023 6:24 AM IDT)
Fire H24d (14/1/2023 9:03 AM IDT)
*Sanandan Swaminathan (14/1/2023 11:25 AM IDT)
Julian Bayerl (15/1/2023 9:57 AM IDT)
*Dieter Beckerle (16/1/2023 5:46 PM IDT)
David Greer (16/1/2023 7:43 PM IDT)
Abu Said Manap (17/1/2023 2:50 PM IDT)
*David Tucker (17/1/2023 3:33 PM IDT)
*Phil Proudman (17/1/2023 6:22 PM IDT)
*Latchezar Christov (18/1/2023 3:16 PM IDT)
*K S(19/1/2023 2:25 AM IDT)
*Nyles Heise(19/1/2023 8:32 AM IDT)
*Kevin Bauer(19/1/2023 8:49 PM IDT)
*Karl Mahlburg(21/1/2023 6:28 AM IDT)
stan(21/1/2023 1:19 PM IDT)
*Motty Porat(21/1/2023 5:15 PM IDT)
*Dan Dima(21/1/2023 6:17 PM IDT)
*Tim Walters(24/1/2023 10:47 AM IDT)
*Joaquim Neves Carrapa(26/1/2023 5:07 PM IDT)
*Matt Cristina(28/1/2023 5:46 AM IDT)
*Kang Jin Cho(28/1/2023 6:57 PM IDT)
*Todd Will(28/1/2023 7:48 PM IDT)
*David F.H. Dunkley(29/1/2023 3:55 AM IDT)
Meron(30/1/2023 2:54 PM IDT)
*Andreas Stiller(30/1/2023 8:24 PM IDT)
Wilder Boyden(30/1/2023 9:54 PM IDT)
Oscar Volpatti(1/2/2023 10:31 AM IDT)
Fabio Michele Negroni(1/2/2023 11:01 AM IDT)
*Karl D’Souza(2/2/2023 12:24 AM IDT)
*Reiner Martin(2/2/2023 4:32 PM IDT)
*Marco Bellocchi(4/2/2023 8:58 PM IDT)
*Radu-Alexandru Todor(4/2/2023 11:59 PM IDT)
*Li Li(5/2/2023 7:12 AM IDT)