Odzyskiwanie ciągów

33

Wprowadzenie

Zobaczmy następujący ciąg:

AABBCCDDEFFGG

Widać, że każda litera została zduplikowana , z wyjątkiem litery E. Oznacza to, że list Ezostał zduplikowany . Więc jedyne co musimy zrobić tutaj to, aby odwrócić ten proces, co daje nam następujące ONZ deduplikowane ciąg:

AABBCCDDEEFFGG

Weźmy trudniejszy przykład:

AAAABBBCCCCDD

Widać, że liczba kolejnych jest nieparzysta B, co oznacza, że ​​jeden z nich BBzostał zduplikowany z oryginalnego ciągu. Musimy tylko cofnąć kopię tego listu, co daje nam:

AAAABBBBCCCCDD


Wyzwanie

Biorąc pod uwagę niepusty ciąg zduplikowany , składający się tylko z znaków alfabetu (tylko wielkie lub tylko małe litery), zwróć ciąg nie zduplikowany . Możesz założyć, że w ciągu zawsze będzie co najmniej jeden zduplikowany znak.


Przypadki testowe

AAABBBCCCCDDDD    -->    AAAABBBBCCCCDDDD
HEY               -->    HHEEYY
AAAAAAA           -->    AAAAAAAA
N                 -->    NN
OOQQO             -->    OOQQOO
ABBB              -->    AABBBB
ABBA              -->    AABBAA

To jest , więc wygrywa najkrótsza ważna przesyłka w bajtach!

Adnan
źródło
@ mbomb007 Tak, to spowodowałoby AABBBB.
Adnan
1
Nie jestem pewien, czy rozumiem wyzwanie. Dlaczego ABBBmapowania AABBBB, nie AABBBBBB?
Dennis
2
@Dennis Jeśli oddzielić każdą grupę znaków na grupy 2, co można uzyskać z następujących powodów: A BB B. Znaki, które nie są sparowane (a zatem nie powielone) muszą zostać zduplikowane, w wyniku AA BB BBczego powstaje ciąg niezduplikowany.
Adnan
8
Więc: Upewnij się, że każdy ciąg znaków ma parzystą liczbę elementów, dodając co najwyżej jeden element do biegu?
Szalony fizyk
1
@MadPhysicist Tak, to prawda
Adnan

Odpowiedzi:

20

MATL , 7 bajtów

Y'to+Y"

Wypróbuj online! Lub sprawdź wszystkie przypadki testowe .

Weźmy 'ABBA'jako przykładowe dane wejściowe.

Y'   % Implicit input. Run-length decoding
     % STACK: 'ABA', [1 2 1]
t    % Duplicate top of the stack
     % STACK: 'ABA', [1 2 1], [1 2 1]
o    % Modulo 2
     % STACK: 'ABA', [1 2 1], [1 0 1]
+    % Add, element-wise
     % STACK: 'ABA', [2 2 2]
Y"   % Run-length encoding. Implicit display
     % STACK: 'AABBAA'
Luis Mendo
źródło
11

Siatkówka , 11 bajtów

(.)\1?
$1$1

Wypróbuj online - zawiera wszystkie przypadki testowe

mbomb007
źródło
1
Spodziewałem się, że Retina wygra.
Adám
@ Adám Tak, jest dość krótki, ale ta odpowiedź MATL jest świetna. Wszystkie języki gry w golfa zakończyły się krótszymi rozwiązaniami.
mbomb007
8

Perl, 16 bajtów

15 bajtów kodu + -pflaga.

s/(.)\1?/$1$1/g

Aby uruchomić:

perl -pe 's/(.)\1?/$1$1/g' <<< 'HEY'
Dada
źródło
7

Haskell, 36 bajtów

u(a:b:c)=a:a:u([b|a/=b]++c)
u x=x++x

Przykład użycia: u "OOQQO"-> "OOQQOO".

Jeśli ciąg ma co najmniej 2 elementy, weź dwie kopie pierwszego i dołącz odwołanie rekurencyjne za pomocą

  • drugi element i reszta, jeśli pierwsze dwa elementy różnią się lub
  • tylko reszta

Jeśli jest mniej niż dwa elementy (jeden lub zero), weź dwie kopie listy.

nimi
źródło
6

Brachylog , 17 bajtów

@b:{~b#=.l#e,|}ac

Wypróbuj online!

Wyjaśnienie

Example input: "ABBB"

@b                  Blocks: Split into ["A", "BBB"]
  :{          }a    Apply the predicate below to each element of the list: ["AA", "BBBB"]
                c   Concatenate: "AABBBB"

    ~b#=.             Output is the input with an additional element at the beginning, and
                        all elements of the output are the same (e.g. append a leading "B")
        .l#e,         The length of the Output is an even number
             |        Or: Input = Output (i.e. do nothing)
Fatalizować
źródło
4

Ruby, 21 bajtów

20 bajtów plus -pflaga.

gsub(/(.)\1?/){$1*2}
Wartość tuszu
źródło
4

JavaScript (ES6), 37 30 bajtów

Zapisane 7 bajtów przy użyciu znacznie bardziej wydajne „$ 1 $ 1” jak [inne] [odpowiedzi] zrobił

s=>s.replace(/(.)\1?/g,'$1$1')

Przypadki testowe

Arnauld
źródło
4

Mathematica, 41 bajtów

s=StringReplace;s[s[#,a_~~a_->a],b_->b~~b]&

Nienazwana funkcja, która wprowadza ciąg i wyprowadza ciąg. Całkowicie deduplikuj, a następnie całkowicie nieeduplikuj. Niezbyt krótko, ale na razie nie mogłem nic lepszego.

Greg Martin
źródło
4

Befunge 98 , 24 bajtów

#@~#;:::#@,~-:!j;$,;-\,;

Wypróbuj online!

$można łatwo zastąpić -, a drugi za @pomocą ;.

Myślę, że można to pograć w golfa ze względu -na początek zarówno -,(lub $,powyżej), jak i -\,.

W jaki sposób?

Stack notation:  bottom [A, B, C, D] top

#@~     Pushes the first character onto the stack (C henceforth) and ends if EOF
#;      No-op to be used later
:::     Now stack is [C, C, C, C]

#@,~    Prints C, and if EOF is next (odd consecutive Cs), prints again and ends
        Lets call the next character D

-       Now stack is [C, C, C-D]
:!j;    If C == D, go to "$," Else, go to "-\,"

===(C == D)===

$,      C == D (i.e. a pair of Cs) so we discard top and print C (Stack is now [C])
;-\,;   Skipped, IP wraps, and loop starts again

===(C != D)===

-       Stack is [C, C-(C-D)]  By expanding: [C, C - C + D] or just [C, D]
\,      Prints C (Stack is now [D])

;#@~#;  This is skipped, because we already read the first character of a set of Ds,
        and this algorithm works by checking the odd character in a set of
        consecutive similar characters. We already read D, so we don't
        need to read another character.
Łagodnie Milquetoast
źródło
3

Java 7, 58 bajtów

String c(String s){return s.replaceAll("(.)\\1?","$1$1");}

Nie golfowany:

String c(String s){
  return s.replaceAll("(.)\\1?", "$1$1");
}

Kod testowy:

Wypróbuj tutaj.

class M{
  static String c(String s){return s.replaceAll("(.)\\1?","$1$1");}

  public static void main(String[] a){
    System.out.println(c("AABBCCDDEFFGG"));
    System.out.println(c("AAAABBBCCCCDD"));
    System.out.println(c("AAABBBCCCCDDDD"));
    System.out.println(c("HEY"));
    System.out.println(c("AAAAAAA"));
    System.out.println(c("N"));
    System.out.println(c("OOQQO"));
    System.out.println(c("ABBB"));
    System.out.println(c("ABBA"));
  }
}

Wydajność:

AABBCCDDEEFFGG
AAAABBBBCCCCDD
AAAABBBBCCCCDDDD
HHEEYY
AAAAAAAA
NN
OOQQOO
AABBBB
AABBAA
Kevin Cruijssen
źródło
2

PHP, 65 bajtów, bez wyrażenia regularnego

while(""<$c=($s=$argv[1])[$i])if($c!=$s[++$i]||!$k=!$k)echo$c.$c;

pobiera dane wejściowe z argumentu wiersza poleceń. Uruchom z -r.

regex? W PHP wyrażenie regularne używane przez większość odpowiedzi powiela każdy znak. byłoby 44 bajtów:

<?=preg_replace("#(.)\1?#","$1$1",$argv[1]);
Tytus
źródło
2

Brain-Flak 69 bajtów

Obejmuje +3 za -c

{((({}<>))<>[({})]<(())>){((<{}{}>))}{}{(<{}{}>)}{}}<>{({}<>)<>}<>

Wypróbuj online!

Wyjaśnienie:

Part 1:
{((({}<>))<>[({})]<(())>){((<{}{}>))}{}{(<{}{}>)}{}}<>

{                                                  }   # loop through all letters
 (   {}     [ {} ]<(())>){((<{}{}>))}{}                # equals from the wiki   
                                                       # but first:
  ((  <>))<>                                           # push the top letter on the other 
                                                       # stack twice  
             (  )                                      # push the second letter back on
                                       {        }      # if they were equal:
                                        (<    >)       # push a 0 to exit this loop
                                          {}{}         # after popping the 1 from the 
                                                       # comparison and the next letter
                                                       # (the duplicate)
                                                 {}    # pop the extra 0
                                                    <> # switch stacks

Part 2 (at this point, everything is duplicated in reverse order):
{({}<>)<>}<>

{        }   # for every letter:
 ({}<>)      # move the top letter to the other stack
       <>    # and switch back
          <> # Finally switch stacks and implicitly print
Riley
źródło
1

V 10 bajtów

ͨ.©±½/±±

TryItOnline

Po prostu znajdź i zamień wyrażenie regularne jak wszystkie pozostałe w wątku. Jedyną różnicą jest to, że mogę zastąpić wszystko, co wymagałoby \przed nim, postacią o tej samej wartości ascii, ale z wysokim zestawem bitów. ( (00001000 staje się ¨10101000)

nmjcman101
źródło
1

Perl 6 , 17 bajtów

s:g/(.)$0?/$0$0/

z przełącznikiem wiersza polecenia -p

Przykład:

$ perl6 -pe 's:g/(.)$0?/$0$0/' <<< 'AAABBBCCCCDDDD
> HEY
> AAAAAAA
> N
> OOQQO
> ABBB
> ABBA'
AAAABBBBCCCCDDDD
HHEEYY
AAAAAAAA
NN
OOQQOO
AABBBB
AABBAA
Brad Gilbert b2gills
źródło
1

Rakieta 261 bajtów

(let((l(string->list s))(r reverse)(c cons)(e even?)(t rest)(i first))(let p((l(t l))(ol(c(i l)'())))
(cond[(empty? l)(list->string(if(e(length ol))(r ol)(r(c(i ol)ol))))][(or(equal?(i ol)(i l))(e(length ol)))
(p(t l)(c(i l)ol))][(p(t l)(c(i l)(c(i ol)ol)))])))

Nie golfowany:

(define (f s)
  (let ((l (string->list s)))
    (let loop ((l (rest l))
               (ol (cons (first l) '())))
      (cond
        [(empty? l)
         (list->string(if (even? (length ol))
                          (reverse ol)
                          (reverse (cons (first ol) ol))))]
        [(or (equal? (first ol) (first l)) 
             (even? (length ol)))
         (loop (rest l) (cons (first l) ol))]
        [else
         (loop (rest l) (cons (first l) (cons (first ol) ol)))] ))))

Testowanie:

(f "ABBBCDDEFFGGG")

Wydajność:

"AABBBBCCDDEEFFGGGG"
rnso
źródło
1

05AB1E , 10 bajtów

.¡vy¬ygÉ×J

Wypróbuj online!

Wyjaśnienie

.¡           # split string into groups of the same char
  v          # for each group
   y         # push the group
    ¬        # push the char the group consists of
     yg      # push the length of the group
       É     # check if the length of the group is odd
        ×    # repeat the char is-odd times (0 or 1)
         J   # join to string
Emigna
źródło
1

Python3, 102 94 bajty

from collections import*
lambda s:"".join(c*(s.count(c)+1&-2)for c in OrderedDict.fromkeys(s))

Dzięki xnor za oszczędność 8 bajtów! -> bithack.

Yytsi
źródło
To nie utrzymuje liter we właściwej kolejności.
xnor
@xnor Dziękujemy za wzmiankę! Naprawiony.
Yytsi
Wygląda dobrze. Możesz zapisać wyrażenie x+x%2jako x&-2.
xnor
@ xnor Próbowałem s.count(c)&-2i zwrócił pusty ciąg ...: / Jakieś myśli?
Yytsi
1
Masz rację i popełniłem błąd. Myślę, że x+1&-2powinienem to zrobić. Dziwki idą do siebie, a szanse zaokrąglają się do nich.
xnor
1

R, 81 bajtów

r=rle(el(strsplit(scan(,""),"")));cat(do.call("rep",list(r$v,r$l+r$l%%2)),sep="")

Odczytuje ciąg ze standardowego wejścia, splajnuje na wektor znaków i wykonuje kodowanie długości przebiegu (rle). Następnie powtórz każdą wartość z rle, sumę długości i mod długości2 .

Jeśli możemy odczytać dane wejściowe oddzielone spacją (domyślnie jako wektor / tablica znaków), możemy pominąć część dzielącą, a program zmniejsza się do 64 bajtów:

r=rle(scan(,""));cat(do.call("rep",list(r$v,r$l+r$l%%2)),sep="")
Billywob
źródło
1

> <> (Fish) 39 bajtów

0v ;oo:~/:@@:@=?!voo
 >i:1+?!\|o !:  !<

Jestem całkiem pewien, że można w nią grać w golfa przy użyciu innej techniki.

Pobiera dane wejściowe i porównuje z bieżącym elementem stosu, jeśli jest inny, wydrukuje pierwszy element stosu dwa razy, jeśli to samo, wydrukuje je oba.

Do pustego stosu dostarczana jest wartość 0, która nic nie drukuje, dzięki czemu można go dołączyć w dowolnym momencie.

Pelikan turkusowy
źródło
1

Pyth, 15 bajtów

Vrz8p*+hN%hN2eN

Sprawdź tutaj wszystkie przypadki testowe.

Podziękowania dla Luisa Mendo za metodologię.

Wyjaśnienie

Vrz8p*+hN%hN2eN    z autoinitializes to the input
 rz8               run-length encode the input, returned as list of tuples (A -> [[1,"A"]])
V                  for every element N in this list
      +hN          add the head element of N (the number in the tuple)
         %hN2      to the head element of N mod 2
     *       eN    repeat the tail element of N that many times (the letter in the tuple)
    p              print repeated character without trailing newline

Jak to często bywa, wydaje mi się, że może to być krótsze. Myślę, że powinien istnieć lepszy sposób na wyodrębnienie elementów z listy niż to, czego używam tutaj.

Mike Bufardeci
źródło
1

PowerShell , 28 bajtów

$args-replace'(.)\1?','$1$1'

Wypróbuj online!(obejmuje wszystkie przypadki testowe)

Odpowiedź portu Retina . Jedyne, na co warto zwrócić uwagę, to to, że mamy $argszamiast zwykłego $args[0](ponieważ -replacebędą iterować po każdym elemencie w tablicy wejściowej, możemy zagrać poza indeksem), i '$1$1'muszą być pojedynczymi cudzysłowami, aby zostały zastąpione wyrażeniem regularnym zmienne zamiast traktowane jak zmienne PowerShell (co by się stało, gdyby były podwójnymi cudzysłowami).

AdmBorkBork
źródło
1

C, 67 bajtów

i;f(char*s,char*d){i=*s++;*d++=i;*d++=i;*s?f(i-*s?s:++s,d):(*d=0);}

Zadzwoń z:

int main()
{
    char *in="AAABBBCCCCDDDD";
    char out[128];
    f(in,out);
    puts(out);
}
Steadybox
źródło
1

pieprzenie mózgu, 22 bajty

,
[
  [>->+<<-]
  >[>..<<]
  >,
]

Wypróbuj online.

Drukuje bieżący znak dwa razy, chyba że jest on równy znakowi, który został właśnie wydrukowany dwa razy.

Mitch Schwartz
źródło