Zaimplementuj skrót o zmiennej długości

10

Mój przyjaciel i ja mamy tę grę, w którą gramy słowami. To jest fajna rozrywka i polega na „anulowaniu” liter w słowie, dopóki nic nie zostanie. Jestem naprawdę zmęczony tym, że jest o wiele szybszy ode mnie, więc Twoim zadaniem jest go wdrożyć i pozwolić mi w końcu go pokonać. Oczywiście, ponieważ muszę sprawić, by program był jak najłatwiejszy do ukrycia, musi być jak najmniejszy.

Jak działa ta gra?

Gra jest dość prostym algorytmem. Redukuje ciąg alfabetyczny, dopóki nie będzie można go dalej zmniejszać, co czyni go rodzajem skrótu. Rzeczywista gra, którą my, ludzie, jest bardzo trudna do wdrożenia, ale można ją uprościć w następującym algorytmie:

Zaczynasz od złożenia alfabetu na pół i ułożenia dwóch elementów w taki sposób:

a b c d e f g h i j k l m
z y x w v u t s r p q o n

Następnie, zaczynając od środka, przypisujesz dodatnie liczby całkowite do górnej połowy, a ujemne do dolnej:

a  b  c  d  e f g h i j k l m
13 12 11 10 9 8 7 6 5 4 3 2 1

z   y   x   w   v  u  t  s  r  p  q  o  n
-13 -12 -11 -10 -9 -8 -7 -6 -5 -4 -3 -2 -1

Następnie weź swój ciąg (będziemy używać hello world) i ignorując wszelkie znaki niealfabetyczne, przetłumacz go:

h e l l  o w   o  r  l d
6 9 2 2 -2 -10 -2 -5 2 10

Następnie sumujesz wartości literowe. Te, które znalazły się na wcześniejszym schemacie (np. dI w, li o), anulują się, a pozostałe sumują się.

sum(6 9 2 2 -2 -10 -2 -5 2 10 )=12

12 jest liczbą b, więc skrót hello worldjestb

Za słowa, które całkowicie niweluje (np love), to wyjście „0 znak”: -. Zauważ, że w danych wejściowych -nadal będą ignorowane. Ma to znaczenie tylko w wyniku.

Jeśli wielkość liczby jest większa niż 13, wtedy zaczynasz podwajać liczby ai. zZasadniczo bierzesz tyle samo alub więcej z, ile pasuje do liczby i bierzesz wszystko, co pozostało do ostatniej litery, w ten sposób:

code golf: 43.

Pasuje do 3 ai zostało 4:

aaa 4: j
result: aaaj

Wskazówka: Ta część jest w zasadzie divmodz tym wyjątkiem, że zaokrągla się w kierunku zera, a nie -infinity(np. -43 zamieniłby się na 3 z, a a tak -4jest ).pzzzp

Uwaga: kreska nie przyjdzie, jeśli a„s lub z” s pasuje idealnie, tylko jeśli jest to dokładnie 0.

Wyjaśnienia:

  • Hash jest przypadek w czuły
  • Standardowe luki są niedozwolone
  • I / O może być w dowolnym formacie, który nie jest zbyt dziwaczny, stdin, stdout, arg wiersza poleceń, funkcja itp.
  • To jest więc wygrywa najmniejszy rozmiar w bajtach .

Przykłady:

hello world  -->  b

love  -->  -

this is an example -->  aak

hello *&*(&(*&%& world  -->  b

good bye --> ae

root users --> zzs
Maltysen
źródło
3
lovejest pusty ...
Justin

Odpowiedzi:

4

CJam, 46 bajtów

Wypróbuj online lub wypróbuj pakiet testowy online .

lel{'n-_W>+_zE<*}%:+{_De<C~e>___0>-'n+'-?o-}h;

Wyjaśnienie

Algorytm działa tak, jak można się spodziewać: odczytuje dane wejściowe, konwertuje na małe litery, mapuje każdy znak na wartość, sumuje wartości i drukuje znaki oraz odpowiednio dostosowuje sumę, aż suma wyniesie zero. Prawdopodobnie najciekawszą optymalizacją (chociaż oszczędza tylko dwa bajty) jest to, że zamiast tego używane są negowane odwzorowania znaków, ponieważ pozwala to uniknąć zamiany argumentów odejmowania w celu poprawienia znaku podczas obliczania odwzorowanej wartości i pozwala uniknąć zamiany ponownie podczas odwzorowywania z powrotem na literę z powodu odejmowanie zanegowanej wartości jest zastępowalne przez dodanie.

lel             "Read a line of input and convert all letters to lowercase.";
{               "Map each character:";
  'n-_W>+         "Map each character to its negated value by subtracting 'n'
                   and incrementing if the result is nonnegative.";
  _zE<*           "If the value is out of the letter range, use 0 instead.";
}%
:+              "Compute the sum of the mapped character values.";
{               "Do...";
  _De<C~e>        "Compute the sum clamped to the letter range.";
  __              "If the clamped sum is nonzero, ...";
  _0>-'n+         "... then produce the clamped sum mapped back to a letter by
                     decrementing if it is positive and adding 'n', ...";
  '-              "... else produce '-'.";
  ?
  o               "Output the character produced above.";
  -               "Subtract the clamped sum out of the sum.";
}h              "... while the sum is nonzero.";
;               "Clean up.";
Runer112
źródło
4

Pyth, 79 78 77 65 61 58

J+\-GK+0fTr13_14=ZsX@JzJKMe,pk*G/H13%H13@JxK?g\aZ>Z0_g\z_Z
orlp
źródło
Możesz użyć @Jzzamiast f}YJzJest prawdopodobnie więcej, ale muszę teraz spać. Powodzenia;)
FryAmTheEggman
@FryAmTheEggman Cool, nie wiedziałem o skrzyżowaniu @!
orlp
2

Klip 10 , 87

Fr+`m[y?cAyg#Ay-v,-RRZ]0]}m.U`[Fx?x?<x0,:-/xR'z*m'm%xR!!%xR],:/xR'a*m'n%xR!!%xR]]'-[R13
Ypnypn
źródło
1

R, 258 bajtów

function(s){a=13;r=data.frame;z=strsplit(gsub("[^a-z]","",tolower(s)),"")[[1]];d=r(l=rev(letters),h=c(-1*a:1,1:a));m=merge(r(l=z),d);n=sum(m$h);q=abs(n);v=rep(ifelse(n>0,"a","z"),q%/%a);paste0(paste(v,collapse=""),d$l[d$h==sign(n)*q%%a],ifelse(n==0,"-",""))}

To musi być najobrzydliwszy kod R. Uznałem, że R może być dobrym wyborem, ponieważ ma wektor wszystkich liter od „a” do „z” jako wbudowaną zmienną globalną. Ale okazuje się, że reszta to bałagan.

Niegolfowane + wyjaśnienie:

function(s) {
    a <- 13              # Store the value associated with a
    r <- data.frame      # Store the `data.frame` function

    # Split the input into a vector, ignoring case and non-letters
    z <- strsplit(gsub("[^a-z]", "", tolower(s)), "")[[1]]

    # Create a data frame where the first column is the letters
    # z through a and the second is the associated scores
    d <- data.frame(l=reverse(letters), h=c(-1*a:1, 1:a))

    # Merge the split vector with the data frame of scores
    m <- merge(data.frame(l=z), d)

    # Get the total score for the input
    n <- sum(m$h)
    q <- abs(n)

    # Pad the output with a or z as necessary
    v <- rep(ifelse(n > 0, "a", "z"), q %/% a)

    # Collapse the vector of a's or z's into a string
    out1 <- paste(v, collapse="")

    # Look up the letter associated with remainder
    out2 <- d$l[d$h == sign(n)*q%%a]

    # If n = 0, we still want a dash
    out3 <- ifelse(n == 0, "-", "")

    # Return the concatenation of all pieces of the output
    paste0(out1, out2, out3)
}

Spowoduje to utworzenie nienazwanego obiektu funkcji, który przyjmuje ciąg znaków jako dane wejściowe i zwraca powiązaną wartość skrótu. Aby to nazwać, nadaj mu nazwę, npf=function(s){...} .

Przykłady:

> f("this is an example")
[1] "aak"

> f("root users")
[1] "zzs"

> f("love")
[1] "-"

> f("People like grapes.")
[1] "aaag"

Wypróbuj online!

Pytania? Z przyjemnością udzielę dalszych wyjaśnień. Propozycje? Sugestie są mile widziane!

Alex A.
źródło
1

Haskell, 171 bajtów

import Data.Char
m=13
l=zip['a'..'z'][-i|i<-[-m..m],i/=0]
p 0="-"
p n|n>m='a':p(n-m)|n<(-m)='z':p(n+m)|1<2=[c|(c,i)<-l,i==n]
f n=p$sum[y|Just y<-[lookup(toLower x)l|x<-n]]

Testowe uruchomienie:

> map f ["hello world", "love", "this is an example", "hello *&*(&(*&%& world", "good bye", "root users"]
["b","-","aak","b","ae","zzs"]

Jak to działa: lto tablica odnośników od liter do odpowiedniej wartości. Wyszukaj wszystkie znaki z ciągu wejściowego i odrzuć te, których nie znaleziono. Zsumuj wynikową listę. W zależności od sumy pwydruków, -a może najpierw kilka as lub zsi wreszcie (od tyłu) wyszukuje literę l.

nimi
źródło
1

R - 200

function(s){l=letters
N=setNames
x=strsplit(tolower(s),'')[[1]]
n=(13:-13)[-14]
v=sum(N(n,l)[x[x%in%l]])
o=''
while(v){d=min(max(v,-13),13)
o=paste0(o,N(l,n)[as.character(d)])
v=v-d}
if(o=='')o='-'
o}
flodel
źródło
+1, zdecydowanie lepiej niż moja odpowiedź R. Dobra robota!
Alex A.