January 2023 - Challenge
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:
- ‘T’ can be changed to ‘C’ if all the letters to its left are ‘C’.
- ‘T’ can be changed to ‘G’ if the letter to its immediate left is ‘C’, and the remaining letters to its left are ‘A’.
- ‘C’ can be changed to ‘T’ if all the letters to its left are ‘T’.
- ‘C’ can be changed to ‘A’ if the letter to its immediate left is ‘C’, and the remaining letters to its left are ‘A’.
- ‘A’ can be changed to ‘C’ if the letter to its immediate left is ‘C’, and the remaining letters to its left are ‘A’.
- ‘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)