Инкрементный шифр

19

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


Шифр Объяснение

Шифр прост, вы используете операции увеличения и уменьшения, чтобы перейти от буквы 1 к конечной букве, с *вашей функцией «отправки». Оператор для «увеличения» будет >и «уменьшения» будет <.

Пример использования слова adbc:

  • Начните с первой буквы слова, выведите эту букву. a
  • Затем используйте >и <(например, brainfuck), чтобы «перейти» от текущей буквы к следующей. a>приведет к «поднятию» aна 1 к букве b. a<может привести к тому, zчто вы уменьшаете букву (она переносится, вы всегда должны выбирать направление, в результате которого происходит НАИМЕНЕЕ число операций).
  • После вывода правильной минимизированной комбинации <и >выведите a, *чтобы обозначить, что мы достигли следующей буквы.

Шаги для кодирования adbcбудут:

a          # a
a>>>*      # ad
a>>>*<<*   # adb
a>>>*<<*>* # adbc

Примеры

Шаги для кодирования azaбудут:

a       # a
a<*     # az
a<*>*   # aza

Больше примеров:

"abcdef"    =  "a>*>*>*>*>*"
"zyaf"      =  "z<*>>*>>>>>*"
"zzzzzz"    =  "z*****"
"z"         =  "z"
"zm"        =  "z<<<<<<<<<<<<<*" or "z>>>>>>>>>>>>>*" (equidistant)
"zl"        =  "z>>>>>>>>>>>>*"
"alphabet"  =  "a>>>>>>>>>>>*>>>>*<<<<<<<<*<<<<<<<*>*>>>*<<<<<<<<<<<*"
"banana"    =  "b<*>>>>>>>>>>>>>*<<<<<<<<<<<<<*>>>>>>>>>>>>>*<<<<<<<<<<<<<*" OR "b<*<<<<<<<<<<<<<*>>>>>>>>>>>>>*<<<<<<<<<<<<<*>>>>>>>>>>>>>*"
"abcdefghijklmnopqrstuvwxyz" = "a>*>*>*>*>*>*>*>*>*>*>*>*>*>*>*>*>*>*>*>*>*>*>*>*>*"
"abcdefz"   =  "a>*>*>*>*>*<<<<<<*"

правила

  • Мы кодируем, а не декодируем, так что не путайте это.
  • Вы можете предположить, что сообщение будет содержать буквы [A-Z]или [a-z], по вашему выбору.
  • Вы можете использовать любой не буквенный / цифровой / зарезервированный символ для обозначения *(EG $).
  • У вас должно быть окончание *, оно не подразумевается в повторах.
  • Вы можете предполагать, что пустых строк нет, но возможен один символ.
  • Если он находится на одинаковом расстоянии до следующей буквы, вы можете выбрать направление.
  • Это , выигрывает наименьшее количество байт.

Пожалуйста, объясните свой ответ, это помогает другим учиться таким образом.

Урна волшебного осьминога
источник
Просто чтобы прояснить, последний контрольный пример представляет собой, abcdefghijklmnopqrstuvwxyzа не его собственный ввод?
Ник Клиффорд
1
@ Ник Клиффорд, да.
Волшебная урна осьминога
Я думаю, что zlследует использовать >.
xnor
4
Не могли бы вы проверить примеры? alphabetна мой взгляд , a>>>>>>>>>>>*>>>>*<<<<<<<<*<<<<<<<*>*>>>*<<<<<<<<<<<*и zlдолжно быть z>>>>>>>>>>>>*и bananaдолжно второе решение существуетb<*<<<<<<<<<<<<<*>>>>>>>>>>>>>*<<<<<<<<<<<<<*>>>>>>>>>>>>>*
Йорг Hülsermann
@xnor правильно, была ручная опечатка от zm. @jorg хорошие уловы, исправил все это, было ручным трудом.
Волшебная Урна Осьминога

Ответы:

2

Желе , 17 байт

OIżN$ẋ"@€⁾><;€⁶ṭḢ

Вместо символа используется пробел *(пробел или символ новой строки сохраняет один байт ”*).

Работает с любым прописными только или строчным только входом.

Попробуйте онлайн! или посмотрите набор тестов (где эти пробелы пост-заменены на*для удобства чтения).

Как?

OIżN$ẋ"@€⁾><;€⁶ṭḢ - Main link: string s          e.g. "adbc"
O                 - cast s to ordinals                [97,100,98,99]
 I                - incremental differences           [3,-2,1]
    $             - last two links as a monad:
   N              -     negate                        [-3,2,-1]
  ż               -     zip together                  [[3,-3],[-2,2],[1,-1]]
         ⁾><      - literal ['>','<']                 "><"
      "@€         - using reversed @arguments for €ach zip with("):
     ẋ            -     repeat (-n are like zeros)    [[">>>",""],["","<<"],[">",""]]
            ;€    - concatenate €ach with:
              ⁶   -     literal ' '                   [[">>>","",' '],["","<<",' '],[">","",' ']]
               ṭ  - tack to:
                Ḣ -     head of s (1st char)          [['a'],[">>>","",' '],["","<<",' '],[">","",' ']]
                  - implicit print   (" not printed:) "a>>> << > "
Джонатан Аллан
источник
11

8086 машинный код, 70 68 67 байт

00000000  be 82 00 bf 43 01 57 31  d2 ac 3c 0d 74 2c 89 d1  |....C.W1..<.t,..|
00000010  88 c2 aa e3 f4 4f 28 c1  9f 88 e7 79 02 f6 d9 83  |.....O(....y....|
00000020  f9 0d 9f 76 05 83 e9 1a  f6 d9 30 fc 9e b0 3c 78  |...v......0...<x|
00000030  02 b0 3e f3 aa b0 2a aa  eb cf c6 05 24 b4 09 5a  |..>...*.....$..Z|
00000040  cd 21 c3                                          |.!.|
00000043

Как это устроено:

            |   org 0x100
            |   use16
be 82 00    |       mov si, 0x82        ; source = command line arguments
bf 43 01    |       mov di, result      ; destination = result
57          |       push di
31 d2       |       xor dx, dx          ; clear dx
ac          |   n:  lodsb               ; al = *si++
3c 0d       |       cmp al, 0x0d        ; end of input reached? (newline)
74 2c       |       je q                ; jump to exit in that case
89 d1       |   @@: mov cx, dx          ; store last char in cl
88 c2       |       mov dl, al          ; and store the current char in dl
aa          |       stosb               ; *di++ = al
e3 f4       |       jcxz n              ; skip encoding this char if cx == 0 (only happens for the first char)
4f          |       dec di              ; move di pointer back
28 c1       |       sub cl, al          ; take the difference between this char and the last one
9f          |       lahf                ; store flags from last subtraction in bh
88 e7       |       mov bh, ah
79 02       |       jns @f
f6 d9       |       neg cl              ; make sure cl is positive
83 f9 0d    |   @@: cmp cl, 13          ; which way is shorter?
9f          |       lahf                ; also store these flags
76 05       |       jbe @f
83 e9 1a    |       sub cl, 26          ; invert cl if we're going backwards
f6 d9       |       neg cl
30 fc       |   @@: xor ah, bh          ; xor saved flags together
9e          |       sahf                ; load flags register with the result
b0 3c       |       mov al, '<'
78 02       |       js @f               ; now the sign flag tells us which operator to use
b0 3e       |       mov al, '>'
f3 aa       |   @@: rep stosb           ; while (cx--) *di++ = al
b0 2a       |       mov al, '*'         ; mark the end with an asterisk
aa          |       stosb
eb cf       |       jmp n               ; repeat
c6 05 24    |   q:  mov byte [di], '$'  ; mark end of string
b4 09       |       mov ah, 0x09        ; dos function: print string
5a          |       pop dx              ; dx = string pointer
cd 21       |       int 0x21            ; syscall
c3          |       ret
            |   result rb 0
user5434231
источник
Эта. Это не круто. Ты сделал это очень быстро, черт возьми.
Волшебная урна осьминога
Благодарю. Это в значительной степени тривиальное решение, хотя. Просто получилось довольно коротким в
8086 году.
10

Python 3 , 87 байт

r,*s=input();p=r
for c in s:d=(ord(p)-ord(c)-13)%26-13;r+='<'*d+'>'*-d+'*';p=c
print(r)

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

Работает как в нижнем, так и в верхнем регистре.

Программа создает выходную строку, rпоскольку она перебирает символы во входной строке. Он сохраняет предыдущий символ как pи вычисляет инкрементную операцию для перехода pк новому символу c.

Интервал между символами равен ord(c)-ord(p), и (ord(c)-ord(p)-13)%26-13принимает его по модулю 26 к интервалу [-13..12]. Отрицательный результат означает, что уйти короче, а положительный результат означает уйти. Это должно быть преобразовано в строку >или в <зависимости от знака. Вместо использования absили условного выражения мы используем преимущество умножения строк в Python, которое s*nдает пустую строку, когда nона отрицательна. В выражении '<'*-d+'>'*dнеправильно подписанная часть не вносит свой вклад.

Начальное состояние обрабатывается путем разбиения ввода на его первый символ, а остальные с распаковкой Python 3 r,*s=input(). Начальный символ используется для начала построения строки, а также начальный «предыдущий» символ.

Спасибо ovs за предложение перейти на Python 3 для распаковки.

XNOR
источник
6

Python 3 , 110 93 байта

r,*s=input()
b=r
for a in s:d=(ord(a)-ord(b))%26;r+=['>'*d,'<'*(26-d)][d>13]+'*';b=a
print(r)

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

овс
источник
Ооо ... Работает как в нижнем, так и в верхнем регистре, хороший (но я думаю, что вы можете сбрить байты, предполагая, один или другой).
Волшебная Урна Осьминога
Пояснения пожалуйста?
Товарищ SparklePony
3

JavaScript (ES6), 118 109 107 байт

Входная строка не чувствительна к регистру.

s=>s.replace(/./g,(c,i)=>(d=~~s-(s=parseInt(c,36)),i)?'<><>'[k=d/13+2|0].repeat([d+26,-d,d,26-d][k])+'*':c)

Как это устроено

В отличие от Python, оператор JS по модулю возвращает число, имеющее тот же знак, что и дивиденд, а не делитель. Кроме того, repeat()метод JS выдает ошибку при задании отрицательного числа, а не возвращает пустую строку (и она в *любом случае значительно длиннее простой ).

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

Ниже приведена таблица, описывающая 4 возможных случая, где dрасстояние между текущим и предыдущим символами со знаком:

d           | floor(d / 13) + 2 | direction | repeat
------------+-------------------+-----------+-------
-25 ... -14 |         0         |     <     | d + 26
-13 ... -1  |         1         |     >     | -d  
 +0 ... +12 |         2         |     <     | +d  
+13 ... +25 |         3         |     >     | 26 - d

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

Arnauld
источник
2

PHP, 127 байт

for($l=ord($r=($s=$argn)[0]);$x=ord($s[++$i]);$l=$x)$r.=str_pad("",($a=abs($n=$l-$x))<14?$a:26-$a,"><"[$n>0^$a>13])."*";echo$r;

Testcases

PHP, 137 байт

for($l=$r=($s=$argn)[0];$s[++$i];$l=$s[$i])$r.=str_pad("",$d=min($a=abs(ord($l)-ord($s[$i])),$b=26-$a),"><"[$d<$b^$l<$s[$i]])."*";echo$r;

Testcases

Йорг Хюльсерманн
источник
2

JavaScript (ES6), 111 103 байт

f=
s=>s.replace(/./g,(c,i)=>(p=(n+26-(n=parseInt(c,36)))%26,i?'<>'[p+3>>4].repeat(p>13?26-p:p)+'*':c),n=0)
<input oninput=o.textContent=f(this.value)><pre id=o>

s=>[...s].map(c=>(n=parseInt(c,36),p&&(p=(n+26-p)%26,s+='><'[p+3>>4].repeat(p>13?26-p:p)+'*'),p=n),s=s[p=0])&&s

Первоначально версия, которая занимала 111 байт, прежде чем я адаптировал трюк @ Arnauld по настройке nво время вычислений p, я думаю, что sвместо этого есть другой трюк, nно уже поздно, поэтому я не буду беспокоиться.

Нил
источник
2

Haskell (lambdabot), 161 153 байта

w(s:n)=s:(join.snd$mapAccumL(ap(,).g)s n);g c n|q<-[c..'z']++['a'..c],(Just l,s)<-minimum$first(elemIndex n)<$>[(q,'>'),(reverse q,'<')]=(s<$[1..l])++"*"

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


Объяснение:

-- Encode a single letter
g c n | q          <- [c..'z']++['a'..c]        -- The alphabet starting from letter c, looping around
      , (Just l,s) <- minimum                   -- Choose the smallest of ..
                    $ first(elemIndex n)        -- the index of the letter n ..
                  <$> [(q,'>'),(reverse q,'<')] -- from the alphabet q and its reverse

      = (s<$[1..l]) -- Repeat < or > the same number of times as the index of n ..
     ++ "*"         -- and append *

-- Encode the whole string
w (s:n) = s                                -- Yield the first char of the input
        : ( join . snd                     -- Concatinate the result of ..
          $ mapAccumL (\a b->(b,g a b))s n -- executing the g function on each letter of the input string ..
                                           -- except the first, passing the previous letter as the 'c' ..
                                           -- argument on each iteration
          )
судейская шапочка
источник
2

EXCEL VBA 130 байт

s="":p=Mid(s,1,1):For i=1 To Len(s)-1:b=Asc(Mid(s,i+1,1)):a=Asc(Mid(s,i,1)):p=p &String(abs(b-a),IIf(b>a,">","<"))&"*":Next:[a1]=p

Запустите его из окна Excel VBA Immediate.

Объяснение:

Простой цикл for с функцией String для повторения «>» или «<» n раз, где n - разница ascii между символьной строкой i и i + 1.

Рохан
источник
2

Java 7-, 232 байта

class C{static void main(String[]a)throws Exception{int i=System.in.read(),j,d,c;p(i);while((j=System.in.read())>10){d=(j-i+26)%26;c=d>13?-1:1;while(d%26>0){d-=c;p(61+c);}p(42);i=j;}}static void p(int k){System.out.print((char)k);}}

Довольно тривиальное решение. Развернулся и прокомментировал:

class C {
    static void main(String[] a) throws Exception {
        int i = System.in.read(), j, d, c; // i is the last character. j is the current character. d is the difference. c is the direction (-1 is left, 1 is right)
        p(i); // print the starting character first
        while ((j = System.in.read()) > 10) { // keep going until a newline is hit (or an EOF/EOL for -1)
            d = (j - i + 26) % 26; // get the difference (always positive) by wrapping around
            c = d > 13 ? -1 : 1; // get the direction by finding which way is shorter, going right when it's a tie
            while (d % 26 > 0) { // keep going until the current character is reached
                d -= c; // reduce d in the right direction
                p(61 + c); // < is 60 = 61 + (-1), > is 62 = 61 - (-1)
            }
            p(42); // print an asterisk
            i = j; // set the current character to the new reference point
        }
    }

    static void p(int k) {
        System.out.print((char) k);
    }
}
HyperNeutrino
источник
2

C 170 байт

e(c){putchar(c);}i;m(a,b){i=b-a?a>b?b-a<14?b-a:-(a+26-b):a-b<14?-(a-b):b+26-a:0;while(i>0)e(62),i--;while(i<0)e(60),i++;}f(char*l){e(*l);while(l[1])m(*l,l[1]),e(42),l++;}

Подробный Live

e(c){ putchar(c); } // encode

g(a,b) // obtain required transition
{
    return (b-a) // calculate distance

         ? (a > b // distance is non-zero

             // if b comes after a
             ? (b-a < 14 // if forward is a shorter path
                 ? b-a // go forward
                 : -(a+26-b)) // otherwise go backward

             // if b comes before a
             : (a-b < 14 // if backward is a shorter path
                 ? -(a-b) // go backward
                 : b+26-a)) // otherwise go forward

         : 0; // if distance is 0
}

// transition
i;m(a,b)
{
    // obtain required transition
    i=g(a,b);

    // encode forward transition
    while(i>0)e('>'), i--;

    // encode backward transition
    while(i<0)e('<'),i++;
}

// incremental cipher function
f(char*l)
{
    e(*l); // encode first character

    while(*(l+1)) // while next character is not END-OF-STRING
        m(*l,*(l+1)), // do transition from current to next character
        e('*'), // encode
        l++; // next
}
Khaled.K
источник
Классное решение. Следующее, вероятно, легче понять, но на 1 байт длиннее:#define x q<14?q:q+26 e(c){putchar(c);}i,q;m(a,b){q=b-a;i=q?(a>b?x:-x):0;while(i>0)e('>'),i--;while(i<0)e('<'),i++;}f(char*l){e(*l);while(*(l+1))m(*l,*(l+1)),e('*'),l++;}
Moreaki
1
@Moreaki Спасибо, но это код-гольф, поэтому мы всегда стремимся уменьшить количество байтов, в любом случае я добавил подробное объяснение того, как работает мой код.
Khaled.K
2

JavaScript (ES6), 140 128 129 111 113 байтов

Я пошел другим путем к другим решениям JS, но это не сработало - вот что у меня получилось:

f=

([x,...s])=>x+s.map(y=>`<><>`[r=(d=y[c=`charCodeAt`]()-x[c](x=y))/13+2|0].repeat([d+26,-d,d,26-d][r])+`*`).join``

i.addEventListener("input",()=>o.innerText=i.value&&f(i.value))
console.log(f("adbc"))
console.log(f("aza"))
console.log(f("abcdef"))
console.log(f("zyaf"))
console.log(f("zzzzzz"))
console.log(f("z"))
console.log(f("zm"))
console.log(f("zl"))
console.log(f("alphabet"))
console.log(f("banana"))
console.log(f("abcdefghijklmnopqrstuvwxyz"))
console.log(f("abcdefz"))
<input id=i>
<pre id=o>

  • Сохранено 12 байтов благодаря предложению от Люка по уничтожению строки.
  • Добавлен 1 байт, исправляющий неправильное прочтение задачи, которое, как мне показалось, допускает неявный финальный печатный символ.
  • Сохранено еще 18 байт благодаря обширной перезаписи Люка.
  • Добавлены 2 байта, так как цифры не являются допустимыми печатными символами.

Оригинал, 131 байт

мохнатый
источник
1
([x,...s])=>x+s.map(...)сохраняет 12 байтов. Обратите внимание, что вы должны добавить символ печати в конце. Я предлагаю использовать число, которое будет стоить только 2 байта `1`+1вместо `*`.
Люк
Спасибо Люк; Я забыл, что могу разрушить строковый ввод таким образом. Должно быть, я неправильно понял вызов прошлой ночью; Я мог бы поклясться, что последний печатный символ был неявным. К сожалению, простое включение после joinпривело бы к неправильному выводу для однобуквенных вводов. Однако перемещение символа печати в mapметоде стоит всего 1 байт.
Лохматый
1
([x,...s])=>x+s.map(y=>'<><>'[r=(d=y[c='charCodeAt']()-x[c](x=y))/13+2|0].repeat([d+26,-d,d,26-d][r])+0).join``для 111 байтов
Люк
Спасибо еще раз, @Luke. Прежде чем я отредактирую это, вы бы предпочли опубликовать вышесказанное в качестве собственного ответа? Я чувствую, что он достаточно отличается от моего (почти гибрид этого и Арно), чтобы все было в порядке.
Лохматый
Нет, вы можете отредактировать его. Я попытался найти reduceрешение для игры в гольф , но оказалось, что это 115 байт.
Люк
2

C ++, 210 190 байтов

Моя первая попытка игры в гольф!

#include<iostream>
int g(char*a){char k,j,d;std::cout<<*a;a++;for(;*a;a++){for(j=*(a-1),d=j-*a,k=d>0?d>13?62:60:d<-13?60:62;j!=*a;j+=k-61,j=j<97?122:j>122?97:j)std::cout<<k;std::cout<<'*';}}

k сохраняет, какой из <,> или * печатать. Сначала он просто печатает первый элемент массива, затем запускает цикл от первого до последнего элемента массива. j сохраняет предыдущий элемент, а затем сравнивает, если j ближе к * a, с помощью <или> установите k на <,> соответственно, а затем выведите k, затем запустите этот цикл, пока j не станет равным p. Затем после каждого окончания второго цикла выведите *.

0x81915
источник
2
Добро пожаловать на сайт! Если я правильно помню, *p!=0можно заменить на *p. Я почти уверен, что место в нем char *aтоже не нужно. Вам также нужно будет #include <iostream>и using namespace std;(хотя я думаю, что это может быть дешевле просто добавить std::), чтобы сделать это полный ответ.
Wheat Wizard
2
Добро пожаловать на сайт! Я думаю, что вам нужно включить, std::или using namespace std;вам, вероятно, также потребуется #include <iostream>подсчет байтов.
DJMcMayhem
+1, но исправьте две вышеупомянутые вещи, добро пожаловать в PPCG;). Ознакомьтесь с некоторыми языками в TIO Nexus ( tio.run/nexus ), когда у вас будет возможность! Возможно представьтесь Деннису, он ключевой чувак, плавающий здесь.
Волшебная урна осьминога
Спасибо всем за предложения и указание на ошибки. Я обновлю код в ближайшее время.
0x81915
1

05AB1E , 17 байт

¬sÇ¥v„<>y0›èyÄ×ðJ

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

объяснение

Использует >, <и <space>для обозначения прироста , убывания , отправки

¬                  # get the first letter of the input string
 sǥ               # push a list of delta's of the character codes in the input string
    v              # for each delta
     „<>           # push the string "<>"
        y0›        # check if the delta is positive
           è       # use this to index into the string
            yÄ×    # repeat it abs(delta) times
               ðJ  # join to string with a space
Emigna
источник
И потерял этот на 3 часа 😉.
Волшебная Урна Осьминога
1

Haskell , 167 168 126 байт

f=fromEnum
r=replicate
a?b=mod(f a-f b-13)26-13
c#x=r(c?x)'<'++r(-c?x)'>'
s(c,s)x=(x,s++c#x++"*")
e(x:y)=x:snd(foldl s(x,[])y)

Теперь используем арифметическое решение xnor. Вызов с e strгде str :: Stringстрока для кодирования.

Юлианский волк
источник