Pressões mínimas necessárias para digitar um determinado texto

45

Todos sabemos que os programadores tendem a ser preguiçosos. Para maximizar seu tempo livre, você decide escrever um programa que produz um número mínimo de pressionamentos de tecla para o texto inserido nele.

Entrada : texto que precisa ser convertido em pressionamentos de tecla. Você pode decidir como inserir o texto (STDIN / leitura de um arquivo fornecido nos argumentos)

Saída : as ações necessárias no seguinte formato:

  • Eles devem ser numerados
  • H: Pressionando uma tecla e liberando-a imediatamente
  • Press: Pressionar uma tecla e não soltá-la (isso nunca será o ideal quando a tecla for Rpressionada como o próximo pressionamento de tecla)
  • Release: Liberando uma Pchave ressed

Exemplo :

Entrada:

Hello!

Resultado:

Uma solução ingênua seria:

1 P Shift
2 H h
3 R Shift
4 H e
5 H l
6 H l
7 H o
8 P Shift
9 H 1
10 R Shift

Isso seria mais eficiente:

1 P Shift
2 H h
3 H 1
4 R Shift
5 H Left
6 H e
7 H l
8 H l
9 H o

Meio Ambiente:

  • O editor usa uma fonte monoespaçada
  • O texto é encapsulado com 80 caracteres
  • Seta para cima e Seta para baixo preservam a coluna, mesmo se houver linhas mais curtas entre
  • Presume-se que a área de transferência esteja vazia
  • Presume-se que o bloqueio numérico esteja ativado
  • Presume-se que o caps lock esteja desativado
  • Caps lock funciona apenas para as letras (ou seja, sem Shift Lock)

Teclas de atalho / atalhos :

  • Home: Salta para o início da linha atual
  • End: Pula para o final da linha atual
  • Ctrl+ A: Marcar tudo
  • Ctrl+ C: Copiar
  • Ctrl+ X: Cortar
  • Ctrl+ V: Colar
  • Shift+ Cursor em movimento: Marcação
  • Ctrl+ F: Abre uma caixa de diálogo de pesquisa.
    • Correspondência de texto estúpida, sem expressões regulares
    • Maiúsculas e Minúsculas
    • Pesquisas envolvem
    • Entrada de texto de linha única para a pesquisa
    • A entrada é pré-preenchida com a seleção atual, a menos que haja uma nova linha no meio, a entrada completa é selecionada
    • Copiar / colar funciona normalmente
    • Pressionar Enterrealiza a pesquisa, selecionando a primeira correspondência após a posição atual do cursor
  • F3: Repetir a última pesquisa
  • Ctrl+ H: Abre uma caixa de diálogo de substituição
    • Correspondência de texto estúpida, sem expressões regulares
    • Maiúsculas e Minúsculas
    • Substitua Tudo, com a envolvente
    • Entradas de texto de linha única
    • A entrada de pesquisa é pré-preenchida com a seleção atual, a menos que haja uma nova linha no meio, a entrada completa é selecionada
    • A entrada de substituição está vazia
    • Copiar / colar funciona normalmente
    • Tab pula para a entrada de substituição
    • Pressionar Enterexecuta a substituição de todos. O cursor é colocado após a última substituição

Regras :

  • As soluções devem ser um programa completo que compile / analise e execute sem nenhuma modificação adicional
  • O teclado exibido acima é o teclado a ser usado
    • Não é necessário manipular caracteres que não podem ser digitados com ele
  • Cada chave deve ser liberada no final
  • O cursor não precisa estar no final do arquivo no final

Pontuação :

Sua pontuação é a soma da quantidade de ações necessárias para digitar os seguintes textos. O vencedor é a solução com a menor pontuação. Usando minha solução ingênua, recebo 1371 + 833 + 2006 = 4210. Cai fora! Eu vou escolher um vencedor em duas semanas.

1 Minha solução ingênua

number = 1

H = (char) -> console.log "#{number++} H #{char}"
P = (char) -> console.log "#{number++} P #{char}"
R = (char) -> console.log "#{number++} R #{char}"

strokes = (text) ->
    shiftActive = no

    for char in text
        if /^[a-z]$/.test char
            if shiftActive
                R "Shift"
                shiftActive = no

            H char
        else if /^[A-Z]$/.test char
            unless shiftActive
                P "Shift"
                shiftActive = yes

            H char.toLowerCase()
        else
            table =
                '~': '`'
                '!': 1
                '@': 2
                '#': 3
                '$': 4
                '%': 5
                '^': 6
                '&': 7
                '*': 8
                '(': 9
                ')': 0
                '_': '-'
                '+': '='
                '|': '\\'
                '<': ','
                '>': '.'
                '?': '/'
                ':': ';'
                '"': "'"
                '{': '['
                '}': ']'

            if table[char]?
                unless shiftActive
                    P "Shift"
                    shiftActive = yes

                H table[char]
            else
                H switch char
                    when " " then "Space"
                    when "\n" then "Enter"
                    when "\t" then "Tab"
                    else
                        if shiftActive
                            R "Shift"
                            shiftActive = no

                        char
    R "Shift" if shiftActive

input = ""

process.stdin.on 'data', (chunk) -> input += chunk
process.stdin.on 'end', -> strokes input

2 Fácil repetição

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD
EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
GGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJ
KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK
LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM

3 Repetição mais complexa

We're no strangers to love
You know the rules and so do I
A full commitment's what I'm thinking of
You wouldn't get this from any other guy
I just wanna tell you how I'm feeling
Gotta make you understand

Never gonna give you up
Never gonna let you down
Never gonna run around and desert you
Never gonna make you cry
Never gonna say goodbye
Never gonna tell a lie and hurt you

We've known each other for so long
Your heart's been aching but
You're too shy to say it
Inside we both know what's been going on
We know the game and we're gonna play it
And if you ask me how I'm feeling
Don't tell me you're too blind to see

Never gonna give you up
Never gonna let you down
Never gonna run around and desert you
Never gonna make you cry
Never gonna say goodbye
Never gonna tell a lie and hurt you

Never gonna give you up
Never gonna let you down
Never gonna run around and desert you
Never gonna make you cry
Never gonna say goodbye
Never gonna tell a lie and hurt you

(Ooh, give you up)
(Ooh, give you up)
(Ooh)
Never gonna give, never gonna give
(Give you up)
(Ooh)
Never gonna give, never gonna give
(Give you up)

We've know each other for so long
Your heart's been aching but
You're too shy to say it
Inside we both know what's been going on
We know the game and we're gonna play it

I just wanna tell you how I'm feeling
Gotta make you understand

Never gonna give you up
Never gonna let you down
Never gonna run around and desert you
Never gonna make you cry
Never gonna say goodbye
Never gonna tell a lie and hurt you

Never gonna give you up
Never gonna let you down
Never gonna run around and desert you
Never gonna make you cry
Never gonna say goodbye
Never gonna tell a lie and hurt you

Never gonna give you up
Never gonna let you down
Never gonna run around and desert you
Never gonna make you cry
Never gonna say goodbye
Never gonna tell a lie and hurt you

Você pode usar o programa de repetição criado por mim para testar suas soluções (Nota: ele ainda não suporta Pesquisa / Substituição, todo o resto deve funcionar).

code-challenge optimization keyboard TimWolla
fonte
6
Eu adoraria ver um programa como este para o vim.
Braden Best
4
Normalmente eu uso o mouse para parte dessas coisas.
Victor Stafusa
1
Muito interessante. Vou tentar de manhã; 3
cjfaure
2
Você realmente não tinha que nos rolar com Rick, tinha? :)
Filip Haglund
1
Estou meio com @ B1KMusic. Para mim, seria mais interessante gerar soluções para o vimgolf. (O que é o equivalente ao que você está tentando fazer aqui, apenas usando os comandos vim.) Isso, no entanto, embora pareça uma ideia divertida, reduzir as teclas é muito difícil (ou pelo menos eu acho que é), pois é difícil um movimento preciso para a seleção. Isso faz com que copiar e colar seja uma tarefa muito difícil e exige quase o número de pressionamentos de tecla que você estava tentando copiar. (Ou pelo menos é assim que estou lendo como funciona copiar e colar). E não vejo muitas outras maneiras de reduzir os pressionamentos de tecla.
FDinoff

Respostas:

11

Haskell 1309 + 457 + 1618 = 3384

Finalmente, uma resposta (a pontuação melhorou muito quando percebi que há guias no seu primeiro teste - era necessário editar a pergunta para vê-las). Compilar com ghc, fornecer entrada no stdin. Exemplo:

$ ghc keyboard.hs && echo hello|./keyboard
1 H h
2 H e
3 H l
4 H l
5 H o
6 H Enter

Tentei as coisas óbvias como Dijkstra, mas era muito lento, mesmo depois de reduzir a ramificação para os únicos movimentos úteis, que são: enviar a próxima chave ou copiar desde o início da linha (Shift + Home, Ctrl + C, Fim) ou cole.

Portanto, essa abordagem usa uma área de transferência de comprimento fixo, copia quando um prefixo de linha está prestes a se tornar 'útil' e continua usando esse prefixo desde que seja possível de ser colado em mais linhas do que os prefixos de linhas que alcançar a seguir. Quando não pode usar a área de transferência, ela recorre à solução ingênua, por isso é garantida que será vencida assim que a duração escolhida for superior ao custo de uma cópia.

A pontuação mínima é alcançada quando o tamanho do prefixo é escolhido para caber em "Never going". Existem maneiras de melhorar isso, mas eu já tive o bastante de ler Rick Astley.

import Data.List (isPrefixOf,isInfixOf)
import Control.Monad (foldM)
plen=12
softlines text=sl 0 [] text
  where
    sl n [] [] = []
    sl n acc [] = [(n,reverse acc)]
    sl n acc (x:xs)
      |x=='\n'||length acc==79=(n,reverse (x:acc)):(sl (n+1) [] xs)
      |otherwise=sl n (x:acc) xs
pasteable (a,b) (c,d)=(c>a && b`isInfixOf`d)
                      || (c==a && b`isInfixOf`(drop (length b) d))
findprefixes l=filter (\(a,b,c)->c/=[])
               $ map (\(a,b)->(a, b, map fst $ filter (pasteable (a,b)) l))
               $ filter (\(a,b)->length b==plen && last b/='\n')
               $ map (\(a,b)->(a, take plen b)) l
mergePrefixes [] = []
mergePrefixes (p:ps) = mergePrefixes' p ps
 where mergePrefixes' p [] = [p]
       mergePrefixes' (a,x,b) ((c,y,d):qs) =
         if length (filter (>=c) b) >= length d then
           mergePrefixes' (a,x,b) qs
         else
           (a, x, (filter (<c) b)):(mergePrefixes' (c,y,d) qs)
uc = ("~!@#$%^&*()_+<>?:{}|\""++['A'..'Z'])
lc = ("`1234567890-=,./;[]\\'"++['a'..'z'])
down c = case [[lo]|(lo,hi)<-zip lc uc,c==hi] of []->error [c];p->head p
applyPrefixToLine prefix [] s=return s
applyPrefixToLine [] line s=emit line s
applyPrefixToLine prefix line@(ch:rest) s=
 if prefix`isPrefixOf`line then
   do { s<-emitPaste s; applyPrefixToLine prefix (drop (length prefix) line) s}
 else
   do { s<-emitch s ch; applyPrefixToLine prefix rest s}
type Keystroke = (Char, [Char])
key action k (n, shift) = do
  putStrLn ((show n)++" "++[action]++" "++k)
  if k=="Shift" then return (n+1, (not shift))
  else return (n+1, shift)
emitch (m, shift) ch=
  case ch of
    '\t'->key 'H' "Tab" (m,shift)
    '\n'->key 'H' "Enter" (m,shift)
    ' '->key 'H' "Space" (m,shift)
    _->
      if shift && ch`elem`lc then
        do { key 'R' "Shift" (m, True); key 'H' [ch] (m+1, False) }
      else if not shift && ch`elem`uc then
             do { key 'P' "Shift" (m, False); key 'H' (down ch) (m+1, True) }
           else if ch`elem`lc
                then key 'H' [ch] (m, shift)
                else key 'H' (down ch) (m, shift)
emit line s = foldM emitch s line
emitPaste s = do
  s<-key 'P'"Ctrl" s
  s<-key 'H' "v" s
  key 'R' "Ctrl" s
emitCopy s = do
  s<-key 'H' "Home" s
  s<-key 'P'"Ctrl" s
  s<-key 'H' "c" s
  s<-key 'R' "Ctrl" s
  s<-key 'R' "Shift" s
  key 'H' "End" s
applyPrefix pf ((a,b):xs) p@((c,y,d):ps) s=
  if (c==a) then
    do
      s@(n, shift) <- emit y s
      s <- if shift then return s else key 'P' "Shift" s
      s <- emitCopy s
      s <- applyPrefixToLine y (drop (length y) b) s
      applyPrefix y xs ps s
  else
    do
      s<-applyPrefixToLine pf b s
      applyPrefix pf xs p s
applyPrefix "" ((a,b):xs) [] s=
  do
    s <- emit b s
    applyPrefix "" xs [] s
applyPrefix pf ((a,b):xs) [] s=
  do
    s<-applyPrefixToLine pf b s
    applyPrefix pf xs [] s
applyPrefix _ [] _ s=return s

main=do
  input <- getContents
  let lines = softlines input
  let prefixes = mergePrefixes (findprefixes lines)
  (n,shift) <- applyPrefix "" lines prefixes (1, False)
  if shift then
    key 'R' "Shift" (n, shift)
  else
    return(n,shift)
bazzargh
fonte
Solução muito boa :) Btw: você pode raspar mais alguns personagens combinando as pastas (se possível).
TimWolla
Isso realmente afeta o exemplo 2 - eu tinha uma versão do algoritmo Dijkstra que acha isso, mas é apenas utilizável nas 3 primeiras linhas. Você pode melhorar minha solução para todos os testes tentando diferentes tamanhos de prefixo; a solução é rápida o suficiente para que você possa fazer isso com força bruta, são necessárias apenas 10 execuções. É estranho refatorar isso em haskell.
bazzargh