Bantu anak saya menemukan surat-suratnya

17

Latar Belakang

Berdasarkan permainan, anak saya yang berumur empat tahun dapatkan dari rabinya.

"Tujuan" adalah untuk "menemukan" surat-surat dalam urutan tertentu, misalnya aecdb. Anda diberi setumpuk kartu surat, mis daceb. Anda hanya dapat mencari melalui tumpukan dalam urutan yang diberikan, meskipun secara siklis. Ketika Anda memenuhi surat yang Anda butuhkan, Anda mengeluarkannya dari tumpukan.

Objektif

Diberi perintah dan tumpukan (permutasi duplikat bebas satu sama lain), temukan urutan huruf tumpukan teratas (semuanya dapat dicetak ASCII) yang Anda lihat saat bermain game.

Contoh langkah demi langkah

Kami perlu menemukan pesanan aecdb, mengingat tumpukan daceb:

Atas tumpukan d: Tidak apa yang kita cari ( a), jadi kami menambahkannya ke urutan: ddan memutar untuk mendapatkan stack: acebd.

Top of stack a: Ya! jadi kami menambahkannya ke urutan: dadan menghapusnya dari stack: cebd.

Atas tumpukan c: Tidak apa yang kita cari ( e), jadi kami menambahkannya ke urutan: dacdan memutar untuk mendapatkan stack: ebdc.

Top of stack e: Ya! jadi kami menambahkannya ke urutan: dacedan menghapusnya dari stack: bdc.

Atas tumpukan b: Tidak apa yang kita cari ( c), jadi kami menambahkannya ke urutan: dacebdan memutar untuk mendapatkan stack: dcb.

Atas tumpukan d: Tidak apa yang kita cari ( c), jadi kami menambahkannya ke urutan: dacebddan memutar untuk mendapatkan stack: cbd.

Top of stack c: Ya! jadi kami menambahkannya ke urutan: dacebdcdan menghapusnya dari stack: bd.

Atas tumpukan b: Tidak apa yang kita cari ( d), jadi kami menambahkannya ke urutan: dacebdcbdan memutar untuk mendapatkan stack: db.

Top of stack d: Ya! jadi kami menambahkannya ke urutan: dacebdcbddan menghapusnya dari stack: b.

Top of stack b: Ya! jadi kami menambahkannya ke urutan: dacebdcbdbdan menghapusnya dari stack: .

Dan kita selesai. Hasilnya adalah dacebdcbdb.

Implementasi referensi

def letters(target, stack):
    string = ''
    while stack:
        string += stack[0]
        if stack[0] == target[0]:
            stack.pop(0)
            target = target[1:]
        else:
            stack.append(stack.pop(0))
    return string

print letters('aecdb', list('daceb'))

Cobalah online!

Uji kasus

try, yrtyrtyry

1234, 43214321432434

ABCDEFGHIJKLMNOPQRSTUVWXYZ, RUAHYKCLQZXEMPBWGDIOTVJNSFRUAHYKCLQZXEMPBWGDIOTVJNSFRUHYKCLQZXEMPWGDIOTVJNSFRUHYKLQZXEMPWGIOTVJNSFRUHYKLQZXMPWGIOTVJNSRUHYKLQZXMPWIOTVJNSRUYKLQZXMPWOTVNSRUYQZXPWOTVSRUYQZXPWTVSRUYQZXWTVSRUYZXWTVSUYZXWTVUYZXWVYZXWYZXYZ

?, ??

a, a a a

abcd, abcdabcd

Adm
sumber

Jawaban:

5

Tiga metode yang cukup berbeda memberikan jumlah byte yang sama.

Python 2 , 59 byte

s,t=input()
for c in s*99:
 if c in t:print c;t=t.lstrip(c)

Cobalah online!

Mencetak setiap karakter di barisnya masing-masing.


Python 2 , 59 byte

lambda s,t:[c==t[0]and t.pop(0)or c for c in s*99if c in t]

Cobalah online!

Mengambil daftar sebagai input, dan menampilkan daftar.


Python 3 , 59 byte

def f(s,t):
 for c in t:p,q=s.split(c);s=q+p;print(end=p+c)

Cobalah online!

Tidak
sumber
1
Hm, saya curiga pada dua versi pertama ... mengapa 99khusus?
Erik the Outgolfer
@EriktheOutgolger Ini setidaknya jumlah karakter ASCII yang dapat dicetak, dan setidaknya panjang dari setiap input.
xnor
5

APL (Dyalog Classic) , 21 byte

∊⊢,⊢∘⊂~¨(,\⊣⊂⍨1,2>/⍋)

Cobalah online!

Ini setara dengan kereta api {∊⍵,(⊂⍵)~¨(,\⍺⊂⍨1,2>/⍺⍋⍵)}

memberikan permutasi argumen kanan dalam argumen kiri

1,2>/bandingkan pasangan berturut-turut dengan >dan tambahkan 1

⍺⊂⍨gunakan topeng boolean di atas untuk dipecah menjadi beberapa kelompok; 1s di mask menandai awal grup baru

,\ gabungan kelompok secara kumulatif

(⊂⍵)~¨ melengkapi masing-masing sehubungan dengan

⍵, lebih dulu

ratakan sebagai string tunggal

ngn
sumber
4

Batch, 155 byte

@set/pt=
@set/ps=
@set r=
:l
@set c=%s:~,1%
@set r=%r%%c%
@if %c%==%t:~,1% set t=%t:~1%&set c=
@set s=%s:~1%%c%
@if not "%t%"=="" goto l
@echo %r%

Mengambil target dan menumpuk sebagai input pada STDIN.

Neil
sumber
4

JavaScript (ES6), 54 byte

Mengambil target sebagai string dan tumpukan sebagai array karakter. Mengembalikan string.

f=(t,[c,...s])=>t&&c+f(t.slice(c==t[0]||!s.push(c)),s)

Uji kasus

Bagaimana?

Pada setiap iterasi, kami mengekstrak karakter cdi bagian atas tumpukan dan menambahkannya ke hasil akhir. Kami kemudian melakukan panggilan rekursif yang parameternya bergantung pada hasil c == t[0], di mana t[0]karakter yang diharapkan berikutnya.

Jika ccocok t[0]:

  • kami menghapus cdari string target dengan melewatit.slice(1)
  • kami menghapus cdari tumpukan dengan melewati stidak berubah

Jika ctidak cocok t[0]:

  • kami membiarkan string target tidak berubah dengan melewati t.slice(0)
  • kami mendorong ckembali di ujung tumpukan
Arnauld
sumber
3

Python 2 , 73 byte

f=lambda o,s,S='':s and f(o[s[0]==o[0]:],s[1:]+s[:s[0]!=o[0]],S+s[0])or S

Cobalah online!

Saya menduga ini sangat golf.

Erik the Outgolfer
sumber
3

Python 2 , 65 byte

f=lambda o,s:o and s[0]+f(o[s[0]==o[0]:],s[1:]+s[0]*(s[0]!=o[0]))

Cobalah online!

ovs
sumber
3

Haskell , 49 46 byte

q@(a:b)#(c:d)|a==c=a:b#d|e<-d++[c]=c:q#e
a#_=a

Cobalah online!

Cukup sederhana. Argumen kiri adalah "tujuan" dan kanan adalah tumpukan. Jika kepala sasaran cocok dengan bagian atas tumpukan, kami akan menambahkannya di awal, dan berulang dengan sisa tujuan dan tumpukan (tanpa menambahkan kembali item di atas). Jika tidak, kami akan menambahkan item teratas dan berulang dengan tujuan yang sama, membaca item teratas hingga akhir tumpukan. Ketika tujuan kosong, pencocokan pola memilih baris kedua dan daftar kosong dikembalikan.

EDIT: -3 byte terima kasih kepada @GolfWolf dan @Laikoni!

pengguna1472751
sumber
1
47 chars
Cristian Lupascu
Juga 47
Cristian Lupascu
1
46 byte
Laikoni
1
@GolfWolf solusi kedua Anda (dan Laikoni) tidak berfungsi. Ini menghasilkan "ytrty" bukan "yrtyry" karena diutamakan operator dengan (:) dan (#)
user1472751
1

Bersih , 85 byte

import StdEnv
g l[u:v][a:b]|a==u=g[a:l]v b=g[a:l][u:v](b++[a])
g l[]_=reverse l
f=g[]

Cobalah online!

Menentukan fpengambilan fungsi parsial [Char]dan[Char] , di mana argumen pertama adalah target dan yang kedua adalah tumpukan.

Suram
sumber
1

Java 8, 88 byte

a->b->{for(int c:a)for(char t=0;c!=t;System.out.print(t)){t=b.poll();if(c!=t)b.add(t);}}

Input sebagai char[]danjava.util.LinkedList<Character> ( java.util.Queueimplementasi)

Penjelasan:

Cobalah online.

a->b->{                        // Method with two parameters and no return-type
  for(int c:a)                 //  Loop over the characters of the char-array
    for(char t=0;c!=t;         //   Inner loop until we've found the character in the queue
        System.out.print(t)){  //     After every iteration: print the char `t`
      t=b.poll();              //    Remove the top of the queue, and save it in `t`
      if(c!=t)                 //    If this is not the character we're looking for:
        b.add(t);}}            //     Add it at the end of the queue again
Kevin Cruijssen
sumber
1

> <> , 38 32 byte

Edit: Teal pelican memiliki lebih banyak ><>pendekatan disini bahwa swap metode masukan

0[i:0(1$.
\~~l]1+{$[&
/?=&:&:o:{

Cobalah online!

Mengambil urutan huruf melalui -sbendera, dan tumpukan melalui input.

Bagaimana itu bekerja:

0[.... Creates a new empty stack
...... This puts the order of the letters safely away
......

..i:0(1$. Takes input until EOF (-1). This means input is in reverse
..~...    And then teleports to the ~ on this line
......

......      Gets the first character from the beginning of the order
\.~l]1+{$[& And stores it in the register before going to the next line
/.....

......     Output the bottom of the stack
......     Checks if the bottom of the stack is equal to the current character
/?=&:&:o:{ If so, go to the second line, else cycle the stack and repeat

0.....      Pop the extra 0 we collected
\~~l]1+{$[& Pop the value that was equal and get the next character from the order
/.....      And go down to the last line. This will end with an error (which could be avoid with a mere 4 extra bytes
Jo King
sumber
1

> <> , 21 16 byte

i$\~~
=?\$:{::o@

Cobalah online!

Flow diubah untuk memanfaatkan ruang kosong dan menghapus rerouting kode tambahan. (-5 byte) - Terima kasih kepada @ JoKing

> <> , 21 byte

i:{:@=?v:o$!
o~i00. >

Cobalah online!

Jawaban lain> <> dapat ditemukan di sini.

Penjelasan

Tumpukan dimulai dengan set karakter awal menggunakan flag -s. Input adalah urutan karakter yang diberikan pengguna. Penjelasan ini akan mengikuti alur kode.

i$\        : Take input, swap the top 2 stack items then move to line 2;
             [1,2,3] -> [1,2,4,3]
  \$:      : Swap the top 2 stack items then duplicate the top item;
             [1,2,4,3] -> [1,2,3,4,4]
     {::o  : Move the stack items 1 left then duplicate the stack top twice and print one;
             [1,2,3,4,4] -> [2,3,4,4,1,1]
=?\      @ : Swap the top three stack items left 1 then do an equal comparison, if equality move to line 1 else continue;
             [2,3,4,4,1,1] -> [2,3,4,1,1,4] -> [2,3,4,1]
  \~~      : Remove the top 2 stack items;
             [2,3,4,1] -> [2,3]
Pelican teal
sumber
Oh ya, memasukkannya dengan cara itu lebih masuk akal lol
Jo King
Bagaimana dengan 17 byte ?
Jo King
1
@JoKing - Perubahan yang sangat bagus untuk membuat perutean yang berlebihan itu hilang, saya tidak bisa menahan untuk mengambil byte tambahan off: P
Teal pelican
0

Perl, 62 byte

sub{$_=$_[1];for$x(@{$_[0]}){/\Q$x\E/;$z.="$`$&";$_="$'$`"}$z}

Mengambil argumen pertama, urutan, sebagai daftar karakter dan yang kedua, tumpukan, sebagai string.

Tidak Disatukan:

sub {
    $_ = $_[1];
    for $x (@{$_[0]}) {
        /\Q$_\E/;
        $z.="$`$&";
        $_ = "$'$`"
    }
    $z
}

Anda pernah bertanya-tanya untuk apa semua variabel regex yang tidak jelas itu? Jelas, mereka dirancang untuk tantangan yang tepat ini. Kami cocok dengan karakter saat ini $x(yang sayangnya harus melarikan diri kalau-kalau itu adalah karakter khusus regex). Ini dengan mudah membagi string menjadi "sebelum pertandingan" $`, "pertandingan" $&, dan "setelah pertandingan" $'. Dalam pencarian siklik, kami melihat dengan jelas setiap karakter sebelum pertandingan dan memasukkannya kembali ke tumpukan. Kami juga melihat karakter saat ini tetapi tidak mengembalikannya. Jadi kami menambahkan "sebelum pertandingan" ke daftar "terlihat" $zdan menyusun tumpukan dari "setelah pertandingan" diikuti oleh "sebelum pertandingan".

Silvio Mayolo
sumber
0

SNOBOL4 (CSNOBOL4) , 98 byte

	S =INPUT
	L =INPUT
R	S LEN(1) . X REM . S	:F(END)
	OUTPUT =X
	L POS(0) X =	:S(R)
	S =S X	:(R)
END

Cobalah online!

Mencetak setiap huruf pada baris baru. Gunakan versi ini untuk mendapatkan semuanya untuk dicetak pada baris yang sama. Mengambil input sebagai tumpukan, lalu menargetkan, dipisahkan oleh baris baru.

	S =INPUT			;*read stack
	L =INPUT			;*read letters
R	S LEN(1) . X REM . S	:F(END)	;*set X to the first letter of S and S to the remainder. If S is empty, goto END.
	OUTPUT =X			;*output X
	L POS(0) X =	:S(R)		;*if the first character of L matches X, remove it and goto R
	S =S X	:(R)			;*else put X at the end of S and goto R
END
Giuseppe
sumber
0

Perl, 44 byte

Termasuk +4untuk-lF

Berikan input seperti pada STDIN sebagai target kemudian susun (ini adalah urutan terbalik dari contoh):

(echo daceb; echo aecdb) | perl -lF -E '$a=<>;say,$a=~s/^\Q$_//||push@F,$_ for@F'

Jika Anda tidak keberatan dengan trailing newline ini 40berfungsi:

(echo daceb; echo aecdb) | perl -plE '$_=<>=~s%.%s/(.*)\Q$&//s;$_.=$1;$&%reg'
Ton Hospel
sumber