m | Y bR | ain adalah Kita | iRd. F (o) RT (h) E La | sT fi (v) e YE | ars O | R s | o, (I) ha | ve C (u) T wO | rds in h (a) lf wh | En (I) s (e) e Th | em. Ketika saya mulai Melakukannya, itu untuk | usaha | TaL - B (u) TI hampir bisa (l) tidak N (o) T d | o itu. N (o) w, aku d | o itu di belakang kepalaku, a (n) d hampir tidak | | | | Namun, saya pikir ini akan membuat tantangan besar.

Definisi

Untuk tantangan ini, setiap huruf diberi skor poin, berdasarkan penilaian saya tentang lebarnya dalam font sans-serif. Anda akan menggunakan lebar ini untuk memotong kata menjadi dua bagian dengan lebar yang sama. Karakter yang akan digunakan tantangan ini adalah alfabet dalam huruf besar dan kecil, apostrof, dan tanda hubung.

Width  Characters
1      i l I '
2      f j r t -
3      a b c d e g h k n o p q s u v x y z
4      m w A B C D E F G H J K L N O P Q R S T U V X Y Z
5      M W

Untuk penjelasan dan kasus pengujian saya, |menunjukkan lokasi di mana sebuah kata dapat dibagi menjadi dua. (dan )di kedua sisi surat menunjukkan bahwa surat itu akan dibagi dua untuk membuat pemisahan bersih.

Memasukkan

Input akan terdiri dari satu "kata" (yang tidak harus ada dalam kamus). Anda dapat mengambil kata ini dalam input teks apa pun yang Anda inginkan (String, array char, dll.). Kata ini hanya akan berisi huruf ',, dan -(lihat tabel di atas). Karena apa yang akan Anda lakukan dengan kata ini (lihat di bawah), kasus input diserahkan kepada kebijaksanaan pengembang. Mengejar baris baru diizinkan jika perlu.

Tugas

Permutasi melalui semua bentuk input (semua huruf pada semua posisi huruf besar atau kecil yang mungkin). Misalnya, untuk input it's, di bawah ini semua permutasi:

it's
it'S
iT's
iT'S
It's
It'S
IT's
IT'S

Untuk membagi permutasi kata menjadi dua, titik di satu sisi kata harus sama dengan titik di sisi lain kata. Namun, jika sebuah huruf tersangkut di antara dua bagian genap, Anda juga dapat memotong satu huruf menjadi dua.

Harap dicatat bahwa "setengah" tidak berarti bahwa Anda telah pindah ke tengah-tengah string. "Setengah" berarti bahwa poin di kedua sisi sama.

Contoh:

Wadalah 5 poin. iadalah 1 poin. Membagi permutasi menjadi Wiiiiisetengah akan menghasilkan W | iiiii, dengan 5 poin di setiap sisi |.

Tadalah 3 poin. Membagi permutasi menjadi TTTTsetengah akan menghasilkan TT | TT, dengan 6 poin di setiap sisi |.

wadalah 4 poin. a adalah 3 poin. Membagi permutasi menjadi wawsetengah akan menghasilkan w (a) w, dengan 5,5 poin di setiap sisi. Poin dari adidistribusikan ke kedua sisi, seperti ayang terbelah dua.

Keluaran

Output Anda adalah bilangan bulat dari jumlah permutasi unik dari input yang dapat dibagi menjadi dua. Mengejar baris baru diizinkan jika perlu.

Uji Kasus

Saya akan mengeluarkan semua permutasi yang valid dari input untuk kasus uji. Ingatlah bahwa itu bukan bagian dari spesifikasi untuk Anda.

Dalam output antara saya, angka-angka menunjukkan nilai poin dari huruf di atas mereka, sehingga outputnya sedikit lebih mudah untuk divisualisasikan.

Input: a
( a ) 
  3   
( A ) 
  4   
Output: 2

Input: in
Output: 0

Input: ab
A | B 
4   4 
a | b 
3   3 
Output: 2

Input: abc
A ( B ) C 
4   4   4 
A ( b ) C 
4   3   4 
a ( B ) c 
3   4   3 
a ( b ) c 
3   3   3 
Output: 4

Input: will
W ( I ) L l 
5   1   4 1 
W ( I ) l L 
5   1   1 4 
W ( i ) L l 
5   1   4 1 
W ( i ) l L 
5   1   1 4 
w I | L l 
4 1   4 1 
w I | l L 
4 1   1 4 
w i | L l 
4 1   4 1 
w i | l L 
4 1   1 4 
Output: 8

Input: stephen
S T E ( P ) H E N 
4 4 4   4   4 4 4 
S T E ( p ) H E N 
4 4 4   3   4 4 4 
S T E | p h e n 
4 4 4   3 3 3 3 
S T e ( P ) H E n 
4 4 3   4   4 4 3 
S T e ( P ) H e N 
4 4 3   4   4 3 4 
S T e ( P ) h E N 
4 4 3   4   3 4 4 
S T e ( p ) H E n 
4 4 3   3   4 4 3 
S T e ( p ) H e N 
4 4 3   3   4 3 4 
S T e ( p ) h E N 
4 4 3   3   3 4 4 
S t E ( P ) H e n 
4 2 4   4   4 3 3 
S t E ( P ) h E n 
4 2 4   4   3 4 3 
S t E ( P ) h e N 
4 2 4   4   3 3 4 
S t E ( p ) H e n 
4 2 4   3   4 3 3 
S t E ( p ) h E n 
4 2 4   3   3 4 3 
S t E ( p ) h e N 
4 2 4   3   3 3 4 
S t e ( P ) h e n 
4 2 3   4   3 3 3 
S t e p | H E N 
4 2 3 3   4 4 4 
S t e ( p ) h e n 
4 2 3   3   3 3 3 
s T E ( P ) H E n 
3 4 4   4   4 4 3 
s T E ( P ) H e N 
3 4 4   4   4 3 4 
s T E ( P ) h E N 
3 4 4   4   3 4 4 
s T E ( p ) H E n 
3 4 4   3   4 4 3 
s T E ( p ) H e N 
3 4 4   3   4 3 4 
s T E ( p ) h E N 
3 4 4   3   3 4 4 
s T e ( P ) H e n 
3 4 3   4   4 3 3 
s T e ( P ) h E n 
3 4 3   4   3 4 3 
s T e ( P ) h e N 
3 4 3   4   3 3 4 
s T e ( p ) H e n 
3 4 3   3   4 3 3 
s T e ( p ) h E n 
3 4 3   3   3 4 3 
s T e ( p ) h e N 
3 4 3   3   3 3 4 
s t E ( P ) h e n 
3 2 4   4   3 3 3 
s t E p | H E N 
3 2 4 3   4 4 4 
s t E ( p ) h e n 
3 2 4   3   3 3 3 
s t e P | H E N 
3 2 3 4   4 4 4 
s t e p | H E n 
3 2 3 3   4 4 3 
s t e p | H e N 
3 2 3 3   4 3 4 
s t e p | h E N 
3 2 3 3   3 4 4 
Output: 37

Input: splitwords
S P L I T | W O r d s 
4 4 4 1 4   5 4 2 3 3 
<snip>
s p l i t w | o R d S 
3 3 1 1 2 4   3 4 3 4 
Output: 228

Input: 'a-r
' a ( - ) R 
1 3   2   4 
' a | - r 
1 3   2 2 
Output: 2

Input: '''''-
' ' ' ( ' ) ' - 
1 1 1   1   1 2 
Output: 1

Kemenangan

Ini adalah kode-golf , jadi jawaban tersingkat dalam byte menang. Anda harus dapat mengeluarkan semua kotak uji (jadi, semua masukan hingga 10 karakter) dalam jumlah waktu yang wajar. Jangan membatasi input Anda secara artifisial.

Karunia

Saya tidak tahu apakah ini ada kemungkinan. Namun, Anda adalah pegolf - Anda akan melakukan apa saja untuk perwakilan. Saya menawarkan 200 rep bounty (saya akan memulainya setelah kondisi bounty ini terpenuhi, karena tampaknya pada dasarnya tidak mungkin bagi saya) untuk sebuah program yang menghasilkan output yang benar antidisestablishmentarianismdalam waktu kurang dari 15 detik pada komputer rata-rata (alias milik saya). Harap dicatat bahwa test case ini tidak boleh dikodekan dengan cara apa pun.

@DigitalTrauma menghancurkan karunia saya, datang di bawah dua detik. Lihatlah jawabannya di sini .

Pyth , 75 74 73 70 byte

lfsm} sT-Bysded._Tm.n] d * Fmm? k | qd \ i + 4} d "mw" |} d "il '" h |} d "fjrt -" + 2} d "mw" -2 } d "'- 
lfsm} sT-Bysded._Tm.n] d * Fmm? k | qd \ i + 4} d" mw "| x} Ld + c" mw il' fjrt - ") G1 4-2} d "'- 
lfsm} sT-Bysded._Tm.n] d * Fm <, | x} Ld + c" mw il' fjrt - ") G1 4 | qd \ i + 4} d" mw "-2} d "-
lfsm} sT-Bysded._Tm.n] d * Fm <, | x} Ld + c "mw il 'fjrt -") G1 4 | qd \ i + 4} d "mw" h} dG

Cobalah online!

Demi kasih Tuhan, tolong jangan coba-coba antidisestablishmentarianismdalam bahasa penerjemah. Anda akan menabraknya.

Penjelasan

lfsm}sT-Bysded._Tm.n]d*Fm<,|x}Ld+c"mw il' fjrt-")G1 4|qd\i+4}d"mw"h}dG

Biarkan kami memecah kode ini menjadi X bagian.

Bagian pertama: menghasilkan versi cased dan memetakan ke nilai-nilai

m<,|x}Ld+c"mw il' fjrt-")G1 4|qd\i+4}d"mw"h}dG

Mari kita perjelas di sini. Dalam tidak ada bagian dari proses adalah huruf dikapitalisasi. Kita hanya perlu memetakan satu huruf menjadi dua nilai (dan tanda baca menjadi satu nilai), tanpa perlu menggunakan huruf kapital. Kami akan memutuskan karakter mana yang kami perlukan dua nilai, dan untuk karakter mana kami akan membutuhkan satu:

m<,|x}Ld+c"mw il' fjrt-")G1 4|qd\i+4}d"mw"h}dGQ  Q implicitly appended
m                                             Q  for d in Q:
                                           }dG       d in alphabet?
                                          h          +1 (T/F as 1/0)
 <   take the first ^ elements of the following array
     for d in alphabet, it will take 2 elements;
     for d being ' or -, it will take 1 element.
  ,          pair up the following two values
   |x}Ld+c"mw il' fjrt-")G1 4                  this is the first value
                             |qd\i+4}d"mw"    this is the second value

Seperti yang Anda lihat, bahkan bagian pertama terlalu panjang.

Nilai pertama adalah untuk versi huruf kecil, yang mencakup 'dan -. Nilai kedua adalah untuk versi huruf besar, dengan 'dan -tidak akan mengambil.

Nilai pertama:

|x}Ld+c"mw il' fjrt-")G1 4
       "mw il' fjrt-"        does what it says on the tin
      c              )       split on spaces, creating an
                             array with three elements
     +                G      append another element, which
                             is the alphabet, as a fail-safe;
                             now the array has 4 elements
  }Ld                        check if d is in each array
                             as with above, True becomes 1
                             and False becomes 0 (T/F as 1/0)
 x                     1     find the first occurrence of 1
|                        4   logical or with 4. If it was 0,
                             it would become 4 now.

String pertama berisi "mw"pada indeks 0. Ini memiliki nilai 4, yang menjelaskan kebutuhan logis atau. Perhatikan bahwa Pyth menggunakan pengindeksan 0. Juga, ruang sebelum 4adalah untuk memisahkannya 1.

Nilai kedua (huruf besar):

|qd\i+4}d"mw"
 qd\i          d=="i"
|              logical OR
       }d"mw"  is d in "mw"? That is, is d "m" or "w"?
     +4        +4

Jika dadalah "i", kemudian memberikan1 pada langkah pertama. Kalau tidak, itu berlanjut. Jika dini "m"atau "w", maka langkah ketiga memberikan 1, yang ditambahkan ke 4memberi 5. Jika dtidak "m"atau "w", maka langkah ketiga memberi 0, yang ditambahkan 4untuk memberi 4.

Bagian kedua: menyelesaikan pekerjaan

lfsm}sT-Bysded._Tm.n]d*F

Ini diawali dengan bagian pertama, yang secara teknis tidak dipisahkan dari bagian kedua (masih satu perintah). Jadi, nilai dari bagian pertama diteruskan ke kanan.

Rekap: pada bagian pertama, kami memetakan huruf ke nilai yang mungkin (huruf kecil dan huruf besar untuk huruf, hanya satu nilai untuk dua tanda baca). Untuk input "ab", orang akan mendapatkannya [[3,4],[3,4]].

Untuk menghasilkan versi cased berbeda (yang seharusnya dilakukan di bagian pertama, tetapi itu akan melimpah), kami menggunakan produk Cartesian berulang kali, dan kemudian meratakan hasilnya. Masalah muncul ketika hanya ada satu huruf (testcase pertama), karena produk Cartesian tidak akan memberi kita sebuah array, dan perintah rata ( .n) diluap untuk memberikan hasil yang aneh ke angka. Kita akan melihat bagaimana saya menghindari masalah ini.

lfsm}sT-Bysded._Tm.n]d*F
                      *F  reduce by Cartesian product
                 m   d    for d in each unflattened version:
                    ]         [d] (wrap in array)
                  .n          flatten
 f                filter for resulting arrays as T
              ._T all prefixes of T
   m              for d in each prefix:
          sd          find the sum of d
         y            double
       -B   ed        [above, above - last element of d]
    }sT               is the sum of T in the above array of 2 elements?
  s               sum the 1/0 generated in each prefix
                  any non-zero value is regarded as truthy
l                 length

Jika itu adalah perpecahan di tengah |, maka awalan akan memiliki jumlah yang digandakan menjadi jumlah dari total.

Jika itu dibagi () , maka jumlah awalan menjadi dua kali lipat dikurangi nilai dalam tanda kurung akan menjadi jumlah dari total.

c, 378 byte; sekitar 0,6 untukantidisestablishmentarianism

Jawaban yang diperbarui . Saya membaca @ komentar JonathanAllan tentang is, dan pada saya pertama tidak mengerti optimasi ini, tapi sekarang saya melihat bahwa sejak kedua idan Imemiliki lebar 1, maka kita dapat menghitung permutasi terkait dua kali dengan hanya harus memvalidasi sekali. Sebelumnya solusi saya menggunakan banyak utas untuk menyebarkan beban ke banyak CPU dan dengan itu saya hampir bisa melewati semua kemungkinan ²⁸ pada mesin saya. Sekarang dengan ioptimasi tidak perlu mengacaukan utas - utas tunggal melakukan pekerjaan dengan mudah dalam batasan waktu.

Tanpa fungsi c - golf lanjut:

char m[128]={[39]=10,[45]=20};f(s,l,p)char *s;{m[65]?:bcopy("PPPPPPPPPPPdPPPPPPPPPdPPP      <<<<<(<<(<P<<<<(<(<<P<<<",m+65,58);int g,h,u=0,v=0,x=0,y=0,c=0;if(p<l){g=s[p];if(g>64&&g-'i'){s[p]-=32;c+=f(s,l,p+1);}s[p]=g;c+=((g=='i')+1)*f(s,l,p+1);}else{for(l--,p=0,g=m[s[p]],h=m[s[l]];p<=l;){y=v;x=u;if(u+g>v+h){v+=h;h=m[s[--l]];}else{u+=g;g=m[s[++p]];}}c=u==v||y==x;}return c;}

Fungsi rekursif f mengambil 3 parameter - pointer ke string input, panjang string dan offset dalam string untuk memulai pemrosesan (harus 0 untuk panggilan tingkat atas). Fungsi mengembalikan jumlah permutasi.

Cobalah online . TIO tampaknya biasanya dijalankan melalui semua testcases (termasuk antidisestablishmentarianismdi bawah 2 detik.

Perhatikan bahwa ada beberapa unsintables dalam string tersebut bcopy() diedit m[]. TIO tampaknya menangani ini dengan benar.

Tidak Disatukan:

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <unistd.h>
#include <stdlib.h>
#include <assert.h>

int width_tbl[] = {
    ['\''] = 1,
    ['-'] = 2,
    ['A'] = 4,4,4,4,4,4,4,4,1,4,4,4,5,4,4,4,4,4,4,4,4,4,5,4,4,4,
    ['a'] = 3,3,3,3,3,2,3,3,1,2,3,1,4,3,3,3,3,2,3,2,3,3,4,3,3,3
};

int
f (char *str, int len, int pos) {
    int lidx, ridx;
    int tot_width = 0;
    int lwidth, rwidth;
    int tot_lwidth = 0, tot_rwidth = 0;
    int prev_tot_lwidth = 0, prev_tot_rwidth = 0;
    char tmp;
    int perm_cnt = 0;

    if (pos < len) {
        tmp = str[pos];
        if (isalpha(tmp) && (tmp != 'i')) {
            str[pos] = toupper(str[pos]);
            perm_cnt += f(str, len, pos+1);
        }
        str[pos] = tmp;
        perm_cnt += ((tmp == 'i') + 1) * f(str, len, pos+1);
    } else {
        //puts(str);
        lidx = 0;
        ridx = len - 1;
        lwidth = width_tbl[str[lidx]];
        rwidth = width_tbl[str[ridx]];
        while (lidx <= ridx) {
            prev_tot_rwidth = tot_rwidth;
            prev_tot_lwidth = tot_lwidth;
            if (tot_lwidth + lwidth > tot_rwidth + rwidth) {
                tot_rwidth += rwidth;
                rwidth = width_tbl[str[--ridx]];
            } else {
                tot_lwidth += lwidth;
                lwidth = width_tbl[str[++lidx]];
            }
        }
        if (tot_lwidth == tot_rwidth) {
            perm_cnt = 1;
        } else if (prev_tot_rwidth == prev_tot_lwidth) {
            perm_cnt = 1;
        }
    }
    return perm_cnt;
}


int main (int argc, char **argv) {
    int i;
    int perm_cnt;

    if (argc > 0) {
        char *str = strdup(argv[1]);
        assert(str);

        perm_cnt = f(str, strlen(str), 0);

        printf("n = %d\n", perm_cnt);
    }

    return 0;
}

Saya memiliki MacBook Pro pertengahan 2015 yang menjalankan MacOS 10.12.4. Compiler adalah dentang MacOS default. Saya mengkompilasi dengan:

cc splitwords.c -O2 -o splitwords

Menjalankan semua testcases, termasuk antidisestablishmentarianismmemberi:

$ time ./splitwords
Testcase "a": n = 2
Testcase "in": n = 0
Testcase "ab": n = 2
Testcase "abc": n = 4
Testcase "will": n = 8
Testcase "stephen": n = 37
Testcase "splitwords": n = 228
Testcase "'a-r": n = 2
Testcase "'''''-": n = 1
Testcase "antidisestablishmentarianism": n = 83307040

real    0m0.573s
user    0m0.564s
sys 0m0.003s
$

Ini tidak berarti optimal. Algoritme hanya memaksa secara kasar melalui semua kemungkinan (modulo i- lihat komentar di atas), dan menghitung kata-kata yang dapat dibagi sesuai dengan kriteria.

JavaScript (ES6), 199 169 167 byte

Mengharapkan string input dalam huruf kecil. Terlalu lambat untuk hadiah.

f=(s,r=[],t=R=0,i=3,x=parseInt("k1048cccctt"["i'l-fjrtmw".search(c=s[0])+1],36)+8>>i&7)=>x&&(c?(i&&f(s,r,t,0),f(s.slice(1),[x,...r],t+x)):R+=r.some(x=>t==x|!(t-=2*x)))

Uji kasus

f=(s,r=[],t=R=0,i=3,x=parseInt("k1048cccctt"["i'l-fjrtmw".search(c=s[0])+1],36)+8>>i&7)=>x&&(c?(i&&f(s,r,t,0),f(s.slice(1),[x,...r],t+x)):R+=r.some(x=>t==x|!(t-=2*x)))

;[ "a", "in", "ab", "abc", "will", "stephen", "splitwords", "'a-r", "'''''-" ]
.map(
  s => console.log(s, '->', f(s))
)

C, 403 394 byte,

Kevin terima kasih!

r;char*g[]={"","ilI'","fjrt-","","mw","MW",0},**p,b[99];q(c){for(p=g;*p;p++)if(strchr(*p,c))return p-g;return c>='a'&&c<='z'?3:4;}f(char*w,int l){int i,n,c,t,x,y;if(*w){for(i=0;i<2;i++)x=tolower(*w),y=toupper(*w),!i||x!=y?b[l]=i%2?x:y,b[l+1]=0,f(w+1,l+1):0;}else{t=0;for(c=0;c<2;c++)for(i=0;i<l;i++){x=y=0;for(n=0;n<l;n++)c==0||n!=i?((n<i)?(x+=q(b[n])):(y+=q(b[n]))):0;t|=x==y;}r+=t;}return r;}

Cobalah online

Kode tidak dikunci:

int getwidth(int c)
{
    char **p, *g[] = { "", "ilI'", "fjrt-", "", "mw", "MW", 0};
    for (p=g; *p; p++)
    {
        if (strchr(*p,c))
            return p-g;
    }
    return c >= 'a' && c <= 'z' ? 3 : 4;
}

int test(char* w, int l)
{
    int i, n, c, t, x, y;

    if (*w)
    {
        for (i=0;i<2; i++)
        {
            x = tolower(*w);
            y = toupper(*w);
            if (!i || x != y)
            {
                b[l] = i % 2 ? x : y;
                b[l + 1] = 0;
                test(w + 1, l+1);
            }
        }
    }
    else
    {
        t = 0;
        for (c=0; c<2; c++)
        {
            for (i=0; i<l; i++)
            {
                x = 0;
                y = 0;
                for (n=0; n<l; n++)
                {
                    if (c == 0 || n != i)
                    {
                        if (n < i)
                            x += getwidth(b[n]);
                        else
                            y += getwidth(b[n]);
                    }
                }
                t |= x == y;
            }
        }
        r += t;
    }
    return r;
}