Wymagane są minimalne naciśnięcia klawiszy, aby wpisać dany tekst

45

Wszyscy wiemy, że programiści są zwykle leniwi. Aby zmaksymalizować czas wolny, decydujesz się napisać program, który generuje minimalną liczbę naciśnięć klawiszy dla wprowadzanego do niego tekstu.

Wejście : tekst, który należy przekonwertować na naciśnięcia klawiszy. Możesz zdecydować, jak wprowadzić tekst (STDIN / odczyt z pliku podanego w argumentach)

Dane wyjściowe : Niezbędne działania w następującym formacie:

  • Muszą być ponumerowane
  • Hit: Naciśnięcie klawisza i natychmiastowe zwolnienie go
  • Press: Naciśnięcie klawisza i nie zwolnienie go (nigdy nie będzie to optymalne, gdy klawisz zostanie Rzwolniony jako kolejne naciśnięcie klawisza)
  • Release: Zwolnienie Pklucza ressed

Przykład :

Wejście:

Hello!

Wynik:

Naiwnym rozwiązaniem byłoby:

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

Byłoby to bardziej wydajne:

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

Środowisko:

  • Edytor używa czcionki o stałej szerokości
  • Tekst jest miękko zawijany do 80 znaków
  • Strzałki w górę i Strzałka w dół zachowują kolumnę, nawet jeśli pomiędzy nimi są krótsze linie
  • Zakłada się, że schowek jest pusty
  • Zakłada się, że Num Lock jest włączony
  • Zakłada się, że Caps Lock jest wyłączony
  • Caps Lock działa tylko na litery (tj. Bez Shift Lock)

Skróty klawiszowe / skróty :

  • Home: Przejdź na początek bieżącej linii
  • End: Przejdź do końca bieżącej linii
  • Ctrl+ A: Zaznacz wszystko
  • Ctrl+ C: Kopiuj
  • Ctrl+ X: Wytnij
  • Ctrl+ V: Wklej
  • Shift+ Przesunięcie kursora: znakowanie
  • Ctrl+ F: Otwiera okno wyszukiwania.
    • Głupie dopasowanie tekstu, brak wyrażeń regularnych
    • Wielkość liter ma znaczenie
    • Wyszukiwania się zawijają
    • Jednowierszowy tekst do wyszukiwania
    • Dane wejściowe są wstępnie wypełnione bieżącym wyborem, chyba że pomiędzy nimi znajduje się nowa linia, wybierane jest pełne wejście
    • Kopiowanie / wklejanie działa jak zwykle
    • Naciśnięcie powoduje Enterwyszukiwanie, wybranie pierwszego dopasowania po bieżącej pozycji kursora
  • F3: Powtórz ostatnie wyszukiwanie
  • Ctrl+ H: Otwiera okno dialogowe zamiany
    • Głupie dopasowanie tekstu, brak wyrażeń regularnych
    • Wielkość liter ma znaczenie
    • Zamień wszystko z zawijaniem
    • Wprowadzanie tekstu w jednym wierszu
    • Dane wejściowe wyszukiwania są wstępnie wypełnione bieżącym wyborem, chyba że pomiędzy nimi znajduje się nowa linia, wybierane jest pełne wejście
    • Zamień wejście jest puste
    • Kopiowanie / wklejanie działa jak zwykle
    • Tab przeskakuje do wejścia zamiany
    • Naciśnięcie powoduje Enterzastąpienie wszystkich. Kursor zostanie umieszczony po ostatniej zamianie

Zasady :

  • Rozwiązania muszą być kompletnym programem, który kompiluje / analizuje i wykonuje bez żadnych dalszych modyfikacji
  • Klawiatura wyświetlana powyżej to klawiatura, z której należy korzystać
    • Nie jest wymagana obsługa znaków, których nie można wpisać za jej pomocą
  • Każdy klucz musi zostać zwolniony na końcu
  • Kursor nie musi znajdować się na końcu pliku na końcu

Punktacja :

Twój wynik to suma działań wymaganych do wpisania następujących tekstów. Zwycięzcą jest rozwiązanie o najniższym wyniku. Używam mojego naiwnego rozwiązania 1371 + 833 + 2006 = 4210. Pokonaj to! Wybiorę zwycięzcę za dwa tygodnie.

1 Moje naiwne rozwiązanie

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 Łatwe powtórzenie

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

3 Bardziej złożone powtórzenie

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

Możesz użyć napisanego przeze mnie programu do odtwarzania , aby przetestować swoje rozwiązania (uwaga: nie obsługuje jeszcze wyszukiwania / zamiany, wszystko inne powinno działać).

code-challenge optimization keyboard TimWolla
źródło
6
Bardzo chciałbym zobaczyć taki program dla vima.
Braden Best
4
Zwykle używam myszy do części tych rzeczy.
Victor Stafusa,
1
Bardzo interesujące. Pójdę rano; 3
cjfaure
2
Naprawdę nie musiałeś nas Rick Roll, prawda? :)
Filip Haglund,
1
Jestem trochę z @ B1KMusic. Dla mnie bardziej interesujące byłoby generowanie rozwiązań dla vimgolfa. (Co jest odpowiednikiem tego, co próbujesz tutaj zrobić, używając tylko poleceń vim.) To brzmi jednak jak zabawny pomysł, zmniejszanie liczby naciśnięć klawiszy jest bardzo trudne (a przynajmniej tak mi się wydaje), ponieważ trudny jest precyzyjny ruch wyboru. To sprawia, że ​​kopiowanie i wklejanie jest naprawdę trudnym zadaniem i zajmuje prawie tyle samo naciśnięć klawiszy, co próbujesz skopiować. (A przynajmniej tak czytam, jak działa kopiowanie i wklejanie). I nie widzę wielu innych sposobów ograniczenia uderzeń klawiszy.
FDinoff,

Odpowiedzi:

11

Haskell 1309 + 457 + 1618 = 3384

Wreszcie odpowiedź (wynik znacznie się poprawił, gdy zdałem sobie sprawę, że w pierwszym teście są zakładki - musiałem edytować pytanie, aby je zobaczyć). Kompiluj z ghc, dostarcz wejście na standardowe wejście. Przykład:

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

Próbowałem oczywistych rzeczy, takich jak Dijkstra, ale było to o wiele za wolno, nawet po zredukowaniu rozgałęzienia do jedynych użytecznych ruchów, którymi są: wypisz następny klucz lub skopiuj od początku linii (Shift + Home, Ctrl + C, End) lub wklej.

Podejście to wykorzystuje schowek o stałej długości, kopiuje, gdy prefiks linii stanie się „użyteczny”, i używa tego prefiksu, o ile można go wkleić na większej liczbie linii niż prefiksy linii, które osiągnie w następnej kolejności. Kiedy nie może korzystać ze schowka, opiera się na naiwnym rozwiązaniu, więc na pewno go pobije, gdy wybrana długość przekroczy koszt kopii.

Minimalny wynik jest osiągany, gdy długość prefiksu jest dopasowana do „Nigdy nie będę”. Są sposoby, aby to poprawić, ale mam już dość czytania Ricka Astleya.

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
źródło
Bardzo fajne rozwiązanie :) Btw: Możesz ogolić więcej postaci, łącząc Pasty (jeśli to możliwe).
TimWolla,
To naprawdę wpływa tylko na przykład 2 - miałem wersję algorytmu Dijkstry, która to znalazła, ale jest to możliwe tylko w przypadku pierwszych 3 linii. Możesz ulepszyć moje rozwiązanie dla wszystkich testów, wypróbowując różne rozmiary prefiksów; rozwiązanie jest na tyle szybkie, że można to zrobić brutalną siłą, wymagane jest tylko około 10 przebiegów. Jednak niewygodne jest refaktoryzowanie tego w haskell.
bazzargh