KEYBOARD FOR MONKE!

Flavortext

So...this is awkward. It seems I accidentally turned into a monkey last night after eating one too many banana sundaes. This has made many things inconvenient, especially typing. You see, monkeys only need the following characters: uppercase letters (A-Z), space, comma (,), exclamation mark (!), and question mark (?). For all other purposes, the Stack Overflow keyboard is enough for copy-pasting a.k.a. monkey see, monkey do. Furthermore, since we are superior to humans and do not have opposable thumbs, we can use our thumbs for more than just the space bar. Finally, monkeys absolutely hate typing consecutive characters with the same finger, so typing combos such as "dee" and "un" on a QWERTY keyboard is very annoying.

That's why I've made a new ergonomic keyboard that looks like this, and your task is to assign its keys.

Left paw                        Right paw

Every finger is used for the three keys in one column and only those keys (so the left pinky would be used for the first column and the right thumb for the sixth).

You will be given a string representative of what I usually type, and will design a keyboard according to the following requirements:

• It will be in the shape of the blank keyboard above.
• It will contain the characters ABCDEFGHIJKLMNOPQRSTUVWXYZ ,!? (note the space) and only those characters.
• None of the strings in the input will cause me to type consecutive characters using the same finger.

Here's an example:

Input: 'I LIKE BANANAS! WHERE BANANA?!'


A valid keyboard would be:

ILANR    DFGJM
EK!S?    ZOPQT
BYWHC    ,UVX

An invalid keyboard would be:

IEANR    DFGJM
LK!S?    ZOPQT
B WHC    ,UVXY

This violates the third requirement, because to type LI in I LIKE BANANAS!, I would have to use my left pinky twice for consecutive characters: once for L on the middle row and once for I on the top row. I would also have to use my left ring finger twice while typing KE.

Rules

• The input will always consist only of the characters ABCDEFGHIJKLMNOPQRSTUVWXYZ ,!?, just like the keyboard.
• You may assume that a valid keyboard exists for the input.
• You may input and output in any reasonable format.

Test cases

The output of each test case is formatted the same as the examples above, but without <kbd> and spaces between the two paws' keys. An underscore (_) is used instead of a space for clarity.

'Input'

Keyboard

'I HAVE A TAIL AND YOU DO NOT! WHY?! I PITY YOU!'

I_HAVETLND
Y?OUWPBCF,
!GJKMQRSXZ

'REJECT MODERNITY, RETURN TO MONKE! EAT BANANA!'

RECOD!BQSX
JNKI,FGAV?
TM_YUHLPWZ


Here is a validator kindly provided by tsh.

• Can we use lowercase instead of uppercase? Jul 15 at 15:40
• @pxeger Of course, you can even use numbers to represent each character if you like.
– rues
Jul 15 at 15:41
• Doesn't your valid keyboard violate the "same finger" requirement? " L" requires using the second finger twice. Jul 15 at 17:11
• @Helen You're right, let me find a valid keyboard.
– rues
Jul 15 at 17:31
• I see a problem that the most golfy (brute-force) solutions will be hard to verify because they involve generating all permutations of 30 characters… Jul 15 at 18:31

Perl 5, 134 bytes

sub f{@k=(A..Z,$",',','!','?');splice@k,rand@k,0,pop@k for 1..1e3;@p{@k}=0..29;join('',map$p{$_}%10,split//,$_[0])=~/(.)\1/?f(pop):@k}


Try it online!

sub f{
@k=(A..Z,' ',',','!','?');          #put valid keys in array @k
splice@k,rand@k,0,pop@k for 1..1e3; #shuffle array @k in random order
@p{@k}=0..29;                       #assign a position 0-29 to each key
join('',map$p{$_}%10,split//,$_[0]) #make string of each input char mapped... #to its key position modulus 10 = column number =~ /(.)\1/ #check if two adjacent column numbers exists... #for current input ? f(pop) #if yes, try new keyboard on same input : @k #if no, return current random valid keyboard... #as an array of 30 chars }  This approach tries random keyboards until it hits a valid one for the current input string. In a test of 1000 runs of both the given test strings, a valid keyboard was found at the 20th trial on average. 🐵 • +1 just for 🐵.‎ Jul 16 at 17:03 • 102 bytes Try it online! Jul 19 at 5:36 • or 88 bytes using full program Try it online! Jul 19 at 7:09 • Good golfing, @Nahuel Fouilleul. I suspected more could be done. Jul 19 at 9:18 Jelly, 18 bytes 30Œ!ðiⱮ’:3nƝẠðƇḢs3  Try It Online! -1 byte thanks to caird coinheringaahing This should work in theory. However, it is $$\O(N! \times NM)\$$ where $$\N\$$ is the size of the alphabet and $$\M\$$ is the size of the input. You can try this for a restricted alphabet of "ABCDEF" here. 30Œ!ðiⱮ’:3nƝẠðƇḢs3 Main Link; accept a list of numbers from 1 to 30 on the left 30Œ! Get all permutations of 1..30 ð ðƇ Filter to keep; map over a dyad, which feeds the input to the right iⱮ Get the index of each input in the permutation ’ Decrement to get into the range 0..29 :3 Floor divide by 3 nƝ For each overlapping pair, check if the column indices are inequal Ạ Are all inequal? (Filter will keep these) Ḣ Take the first valid permutation s3 Divide it into non-overlapping chunks of length 3  Borrowing Kjetil's idea to use random permutations (which I actually had, but I wasn't sure if it'd be valid), we get the following solution, which is way faster (as in you can actually run it): Jelly, 18 bytes iⱮ³’:3=ƝẸ 30RẊÇ¿s3  Try It Online! -1 byte thanks to caird coinheringaahing by observing that we can bind the input to the right of the index link to avoid needing a combinator that we would've needed from binding it to the link reference call in the while loop. You can translate test cases from words to numbers here and translate the output back to text here. iⱮ³’:3=ƝẸ Helper Link; check if a permutation is invalid iⱮ³ Get the index of each input in the permutation ’ Decrement to get into the range 0..29 :3 Floor divide by 3 =Ɲ For each overlapping pair, check if the column indices are equal Ẹ Are any equal? 30RẊÇ¿s3 Main Link 30R 1..30 ¿ While Ç The permutation is invalid Ẋ Shuffle it s3 Divide it into non-overlapping chunks of length 3  Unfortunately, I have to explicitly bind the input as the right argument to ç because otherwise the while loop will Fibonacci. • -1 byte Jul 15 at 21:13 • -1 byte from the other one Jul 16 at 9:22 Python 3, 163 bytes s=input() l=k=''.join({}.fromkeys(s).keys()) while any(x+y in l for x,y in zip(k,k[1:])):k=''.join({*k}) print(k+''.join({*'ABCDEFGHIJKLMNOPQRSTUVWXYZ ,!?'}-{*k}))  Try it online! Returns keyboard transposed flat and joined Haskell, 181 bytes import Data.List f[]=[] f(a:b:c:x)=[a,b,c]:f x g(a:b:x)=(a,b):g(b:x) g _=[] q s=head$filter(\x->not$any(\(a,b)->any(\r->aelemr&&belemr)$f x)$g s)$permutations\$['A'..'Z']++"?!, "


Try it online

Goes through all permutations and picks the first one that does not have any adjacent characters on the same column. Output is flattened. It should work in theory with an awful complexity of O(SNS!) where S the size of the alphabet and N the length of input.

JavaScript (ES6), 136 bytes

-16 bytes thanks to @tsh

Expects an array of characters. Returns a random keyboard as an array of 3 strings.

f=a=>a.some(c=>p==(p=k.indexOf(c)%10),p=k=[...'ABCDEFGHIJKLMNOPQRSTUVWXYZ ,!?'].sort(_=>Math.random()-.5))?f(a):k.join.match(/.{10}/g)


Try it online!

• f=a=>a.some(c=>p==(p=k.indexOf(c)%10),p=k=[...'ABCDEFGHIJKLMNOPQRSTUVWXYZ ,!?'].sort(_=>Math.random()-.5))?f(a):k.join.match(/.{10}/g)
– tsh
Jul 19 at 1:51