Sp | Lit Wo (R) DS, S (P) горит W | RDS

15

m | Y bR | ain есть We | 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 в h (a) lf wh | En (I) s (e) e Th | em. Я начал это делать, чтобы сделать все возможное - B (U) TI почти не (L) не N (O) T D | O это. N (o) w, я делаю это в затылке, a (n) d вряд ли когда-нибудь не будет | iCe это. Тем не менее, я думал, что это будет большой вызов.

Определения

Для этой задачи каждой букве присваивается балл, исходя из моего суждения о ее ширине шрифтом без засечек. Вы будете использовать эту ширину, чтобы разрезать слово на две половины одинаковой ширины. Символы, которые будут использовать в этом задании, - это алфавит в нижнем и верхнем регистре, апостроф и дефис.

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

Для моих объяснений и контрольных примеров, |обозначает место, в котором слово может быть чисто разделено пополам. (и )по обе стороны от буквы указывают, что эта буква будет разделена пополам, чтобы создать чистое разделение.

вход

Ввод будет состоять из одного «слова» (которое не обязательно должно быть в словаре). Вы можете использовать это слово при любом вводе текста (строка, массив символов и т. Д.). Это слово будет содержать только буквы ', и -(см. Таблицу выше). Из-за того, что вы будете делать с этим словом (см. Ниже), случай ввода оставлен на усмотрение разработчика. Замыкающие переводы допускаются при необходимости.

Задание

Перестановка через все формы ввода (все буквы во всех возможных прописных или строчных буквах). Например, для ввода it'sниже приведены все перестановки:

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

Чтобы разделить перестановку слова пополам, точки на одной стороне слова должны совпадать с точками на другой стороне слова. Однако, если буква застряла между двумя четными секциями, вы также можете аккуратно разрезать букву пополам.

Обратите внимание, что «половина» не означает, что вы перешли на половину строки. «Половина» означает, что точки с обеих сторон равны.

Примеры:

W5 баллов. iэто 1 балл. Расщепление перестановкиWiiiii пополам приведет к тому W | iiiii, что по 5 точек на каждой стороне |.

T3 балла. Разделение перестановки TTTTпополам приведет к TT | TT6 точкам на каждой стороне |.

w4 балла. а 3 балла. Разделение перестановки wawпополам приведет к w (a) w5,5 баллам с каждой стороны. Точки от aраспределяются в обе стороны, так как aделятся пополам.

Выход

Ваш вывод является целым числом числа уникальных перестановок ввода, которые могут быть аккуратно разделены пополам. Замыкающие переводы допускаются при необходимости.

Тестовые случаи

Я буду выводить все действительные перестановки ввода для тестовых случаев. Помните, что это не является частью спецификации для вас.

В моем промежуточном выводе числа указывают значение точки буквы над ними, поэтому вывод немного проще визуализировать.

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

победа

Это код-гольф , поэтому выигрывает самый короткий ответ в байтах. Вы должны быть в состоянии вывести все контрольные примеры (то есть все вводные данные длиной до 10 символов) за разумное время. Не искусственно ограничивайте свой ввод.

премия

Я не знаю, если это возможно. Тем не менее, вы играете в гольф - вы сделаете все для представителя. Я предлагаю вознаграждение в 200 представителей (я начну его, как только это условие будет выполнено, поскольку оно кажется мне в принципе невозможным), для программы, которая выводит правильный вывод antidisestablishmentarianismменее чем за 15 секунд на среднем компьютере (так же, как у меня). Обратите внимание, что этот контрольный пример не должен быть жестко закодирован.

@DigitalTrauma сокрушил мою награду, прибыв намного меньше двух секунд. Проверьте его ответ здесь .

code-golf string Стивен
источник
2
@MackenzieMcClane, за исключением того, что есть пять 'я снимаю его до 2 ^ 23 = 8,388,608.
Джонатан Аллан
2
Мой первый счет antidisestablishmentarianism(не для гольфа) - 83307040(и соответствует всем тестовым случаям), но на моем ноутбуке это занимает ~ 37 секунд (учтите, что это Python). У кого-нибудь также есть счет для этого?
Джонатан Аллан
2
43 секунды в TIO
Джонатан Аллан
8
Мой мозг странный Вы находитесь в правильном месте
Луис Мендо
6
Я не должен пытаться сделать то же самое. Я не должен пытаться сделать то же самое. Я должен n (o) tt (r) yt | od | ot (h) e sa | me. O | ч кр | ар ...
Arnauld

Ответы:

8

Pyth , 75 74 73 70 байт

lfsm} ST-Bysded._Tm.n] д * Fmm к | QD \ I + 4} д "MW" |} д "ил" ч |?} д "fjrt - "+ 2} д" 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

Попробуйте онлайн!

Ради любви к Богу, пожалуйста, даже не пытайтесь antidisestablishmentarianism переводчика. Вы сломаете это.

объяснение

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

Давайте разберем этот код на X частей.

Первая часть: генерация версий и отображение значений

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

Давайте будем здесь ясны. В не части процесса буквы заглавной буквы. Нам просто нужно сопоставить одну букву двум значениям (а знаки пунктуации - одному значению) без необходимости их прописной буквы. Мы будем решать, для каких символов нам понадобятся два значения, а для каких символов нам понадобится одно:

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

Как видите, даже первая часть слишком длинная.

Первое значение для строчной версии, которая включает в себя 'и -. Второе значение для заглавной версии, с 'и -не будет принимать.

Первое значение:

|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.

Первая строка содержит "mw"индекс 0. Она имеет значение 4, что объясняет необходимость логического или. Обратите внимание, что Pyth использует 0-индексирование. Кроме того, пространство перед 4должно отделить его от 1.

Второе значение (в верхнем регистре):

|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

Если dесть "i", то это дает 1на первом шаге. В противном случае это продолжается. Если dесть "m"или "w", то третий шаг дает 1, который добавляется 4к дать 5. Если dнет "m"или "w", то третий шаг дает 0, который добавляется 4к дать 4.

Вторая часть: выполнение работы

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

Это предшествует первой части, которая технически не отделена от второй части (это все еще одна команда). Итак, значение из первой части передается вправо.

Напомним: в первой части мы сопоставили буквы с их возможными значениями (строчные и прописные буквы, только одно значение для двух знаков препинания). За вход "ab"можно получить [[3,4],[3,4]].

Чтобы сгенерировать разные версии в оболочке (что должно было быть сделано в первой части, но это могло бы привести к переполнению), мы неоднократно используем декартово произведение, а затем выравниваем результат. Проблемы возникают, когда есть только одна буква (первый контрольный пример), потому что декартово произведение не даст нам массив, а команда flatten ( .n) переполнена, чтобы дать странные результаты для чисел. Посмотрим, как я обошел эту проблему.

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

Если это раскол в середине | , то в префиксе сумма должна быть удвоена и равна сумме итоговой суммы.

Если он разделен на () , то сумма префикса удваивается, минус значение в скобках будет суммой итога.

Дрянная Монахиня
источник
Да, когда у меня есть время. (Я прошу прощения за мой напряженный график.)
Дрянная Монахиня
11

с 378 байт; около 0,6 сantidisestablishmentarianism

Обновленный ответ . Я прочитал @ комментарий JonathanAllan в о iс, и сначала я не понимал эту оптимизацию, но теперь я вижу , что с тех пор , как iи Iимеют ширину 1, то мы можем считать связанные перестановки дважды только того , чтобы проверить один раз. Ранее мое решение использовало несколько потоков, чтобы распределить нагрузку по нескольким процессорам, и с этим я почти смог выполнить все 28 вариантов на моей машине. Теперь сi оптимизацией нет необходимости связываться с потоками - один поток выполняет работу легко в течение ограниченного времени.

Без лишних слов - игра в гольф c:

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;}

Рекурсивная функция f принимает 3 параметра - указатель на входную строку, длину строки и смещение в строке, чтобы начать обработку (должно быть 0 для вызова верхнего уровня). Функция возвращает количество перестановок.

Попробуйте онлайн . TIO обычно проходит через все тесты (включаяantidisestablishmentarianism менее чем за 2 секунды).

Обратите внимание , что есть некоторые непечатные в строке, bcopy()Эдаm[] . TIO, кажется, справляется с этим правильно.

Ungolfed:

#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;
}

У меня MacBook Pro середины 2015 года под управлением MacOS 10.12.4. Компилятор является Maclan Clang по умолчанию. Я собираю с:

cc splitwords.c -O2 -o splitwords

Запуск всех тестовых примеров, в том числе antidisestablishmentarianismдает:

$ 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
$

Это ни в коем случае не оптимально. Алгоритм просто перебирает все возможности (по модулю i- см. Комментарии выше) и подсчитывает слова, которые могут быть разделены в соответствии с критериями.

Цифровая травма
источник
Хорошая работа, на самом деле я думаю , что это, вероятно , можно оценить результат в O (N), используя фиксированные эффекты 7 классов письма i, -, ', l, mw, fjrt, и abcdeghknopqsuvxyz, но это заняло бы приложение из Полиа перечисления теоремы (или эквивалентный комбинаторный метод перечисления), в котором я не очень хорошо разбираюсь.
Джонатан Аллан
Вы разрушили мои ожидания, как я и ожидал. Вот как вы используете рекурсию :)
Стивен
1

JavaScript (ES6), 199 169 167 байт

Ожидает входную строку в нижнем регистре. Слишком медленно для награды.

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)))

Контрольные примеры

Показать фрагмент кода

Arnauld
источник
1

С, 403 394 байта,

Спасибо, Кевин!

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;}

Попробуйте онлайн

Код Ungolfed:

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;
}
Йохан дю Туа
источник
Вы забыли f(char* w, int l){f(char*w,int l){
поиграть