KEYBOARD FOR MONKE!

Question

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.

Task

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.

Answer 1

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. 🐵

Answer 2

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.

Answer 3

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

Answer 4

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->a`elem`r&&b`elem`r)$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.

Answer 5

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!