Генерация цепочки целых чисел, используя наименьшее количество уникальных символов (в C ++)

13

Я новичок в спорте кода гольф. Я пытаюсь создать лестницу целых чисел, используя наименьшее количество уникальных символов в C ++.

Допустим, нам дано целое число 4.

Мы сгенерируем следующую лестницу:

1
1 2
1 2 3
1 2 3 4

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

Моя программа выглядит следующим образом:

#include<iostream>

int i;
int ii;
int iii;
int iiii;

main() {
    std::cin >> i;
    for(ii++; ii <= i; ii++) {
        int iii = iiii;
        for(iii++; iii <= ii; iii++) {
            std::cout << iii << " ";
        }
        std::cout << std::endl;
    }
}

Вот проверка, которую я использовал для проверки количества уникальных символов в моей программе:

#include <cstdio>
#include <cstring>
using namespace std;
int check[300],diffcnt=0,cnt=0,t;
char c;
double score;
int main(){

    memset(check,0,sizeof(check));
    FILE *in=fopen("ans.cpp","r");
    while(fscanf(in,"%c",&c)!=EOF){
        cnt++;
        if(!check[c]){
            check[c]=1;
            if(c=='\r'||c=='\n') continue;
            diffcnt++;
        }
    }
    if(diffcnt<25) printf("100\n");
    else if(diffcnt<30){
        printf("%.3lf\n",20.0*100.0/cnt+20.0*(29-diffcnt));
    }
    else{
        score=20.0;
        for(int x=95;x<cnt;x++) score*=0.9;
        printf("%.3lf\n",score);
    }
    printf("Unique Characters: %d\n", diffcnt);
    printf("Total Characters: %d\n", cnt);
    return 0;
}

Желательно использовать менее 25 уникальных символов для завершения этой программы (исключая символы новой строки, но включая пробелы). В настоящее время моя программа использует 27. Я не уверен, как оптимизировать его дальше.

Может ли кто-нибудь посоветовать мне, как его оптимизировать (с точки зрения количества используемых уникальных символов)? Обратите внимание, что можно использовать только C ++.

code-challenge tips c++ LanceHAOH
источник
5
Конечно , новы просить советы относительно каких-либо других критериев оценки, кроме кода-гольфа , но на самом деле это тема, поскольку на страницах советов написано, что это лучший ответ на проблему программирования, которая обсуждается .
Адам
8
@ LuisMendo Я действительно не думаю, что это так в этом случае, так как многие языки полностью упрощают эту схему оценки. Если этот пользователь хочет помочь в изучении «уникального гольфа», это действительно имеет смысл только в подмножестве языков, поэтому я думаю, что это гораздо лучше в качестве подсказки, чем в качестве общей задачи. Тем не менее, основная проблема может быть проблемой, если кто-то захочет опубликовать ее.
FryAmTheEggman
3
Я думаю, что вы можете использовать орграфы <% и%> вместо фигурных скобок, и я думаю, что я пропустил некоторые.
мое местоимение monicareinstate
2
Я определенно пропустил некоторые. # is% :, так что вы можете избавиться от трех символов и ввести один ({=> <%,} =>%>, # =>% :) и перейти к 25. Если вы объедините это с ответом ниже, я думаю, вы можете получить 24.
мое местоимение monicareinstate
2
@LanceHAOH Триграфы чрезвычайно распространены в [закулисных] вопросах, и орграфы появляются также при чтении о триграфах.
мое местоимение monicareinstate

Ответы:

12

Я считаю, что мне удалось удалить символ = из вашего кода, хотя теперь он значительно медленнее

#include<iostream>

int i;
int ii;
int iii;
int iiii;

int main() {
    std::cin >> i;
    i++;
    for(ii++; ii < i;) {
    for(;iii>iiii;iii++);
    for(;iii<iiii;iii++);
    ii++;
        for(iii++; iii < ii; iii++) {
            std::cout << iii << " ";
        }
        std::cout << std::endl;
    }
}

Это не очень красиво, но злоупотребляя целочисленным переполнением, мы можем вернуться к 0 без использования =

Также нам пришлось немного сменить охрану. К сожалению, из-за включения я не смог избавиться от всех символов новой строки (хотя и близко), так что это может быть следующим путем для расследования.

Изменить: пока не хватает времени, но если вы включите и используете strstream и различные другие библиотеки, я думаю, что вы можете удалить символ «тоже», снова используя целые числа, чтобы получить правильный символ для пробела и передать его в strstream

Истек срок действия данных
источник
2
Вы могли бы #include<std>и устранить все :с. Не очень хорошая практика кодирования, но это не относится к делу.
Даррел Хоффман
3
@DarrelHoffman Я не могу заставить это работать, вам не нужно делать, using namespace std;что бы использовать дополнительный p для: так что net 0
Expired Data
Хм. Может быть, мой C ++ немного ржавый. Кроме того, это добавляет g, так что чистый убыток, я думаю. Если бы это было золото код, мы могли бы уменьшить количество байтов путем переименования ii, iiiи iiiiдругие имена одного письма (выбрать любые другие уже используемые буквы), но это не то , что эта проблема о, так что я думаю , нет. Мне интересно, будет ли какая-то польза от использования, getcи putcвместо cin/ cout, придется попробовать.
Даррел Хоффман
1
Виноват. Я просто снова прочитал чекер. Кажется, что символ новой строки игнорируется. Таким образом, нет необходимости беспокоиться об удалении новой строки. Но в сочетании с вашей стратегией и решением @someone в комментариях мне удалось получить 24 символа. Я сделал программу еще быстрее, используя short вместо int. Так что у меня появился дополнительный символ «h». Но это позволило мне использовать тип данных char без дополнительных затрат. Таким образом, я также избавился от «символа», используя код символа.
LanceHAOH
@LanceHAOH: обратите внимание, что целочисленное переполнение со знаком - неопределенное поведение в C ++, включая все подписанные типы signed char. Если вы компилируете с включенной оптимизацией, этот код может не работать с современными компиляторами, если только вы не используете, gcc -fwrapvчтобы переполнение со знаком было четко определено как обход дополнения 2. Clang -fwrapvтоже поддерживает . ( unsignedцелочисленные типы в том числе unsigned charимеют четко определенное поведение (циклическое изменение) в ISO C ++). Это зависит от ABI, charявляется ли signed charили unsigned char, так что charможет быть в порядке.
Питер Кордес
10

Наконец-то я получил 24 уникальных персонажа, объединив ответы @ExpiredData и @someone. Кроме того, использование короткого типа данных вместо int помогло ускорить мою программу, поскольку для переполнения короткого типа данных требуется меньше времени.

Мой код выглядит следующим образом.

%:include<iostream>

short i;
short ii;
short iii;
short iiii;
char iiiii;

main() <%
    std::cin >> i;
    iiiii++;iiiii++;iiiii++;iiiii++;iiiii++;iiiii++;iiiii++;iiiii++;
    iiiii++;iiiii++;iiiii++;iiiii++;iiiii++;iiiii++;iiiii++;iiiii++;
    iiiii++;iiiii++;iiiii++;iiiii++;iiiii++;iiiii++;iiiii++;iiiii++;
    iiiii++;iiiii++;iiiii++;iiiii++;iiiii++;iiiii++;iiiii++;iiiii++;
    i++;
    for(ii++; ii < i; ii++) <%
        for(;iii;iii++);
        for(iii++; iii < ii; iii++)
            std::cout << iii << iiiii;
        std::cout << iii << std::endl;
    %>
%>
LanceHAOH
источник
@KevinCruijssen, он использует его в char iiiii;последней инициализации переменной.
Rɪᴋᴇʀ
1
@KevinCruijssen Это правда. Но это позволяет мне удалить символ ", потому что я могу использовать символьный код для представления символа пробела. Таким образом, чистая разница в используемых уникальных символах = 0.
LanceHAOH
9

23 уникальных персонажа, использующих Digraphs. (25 без). Нет UB.

Используйте синтаксис скобочных инициализаторов C ++ 11, чтобы инициализировать целое число нулями, int var{};избегая =и 0. (Или в вашем случае избегая глобальных iiii). Это дает вам источник нулей, отличных от глобальных переменных (которые статически инициализируются нулями, в отличие от локальных).

Текущие компиляторы принимают этот синтаксис по умолчанию, без необходимости включать какие-либо специальные опции.

(Целочисленный трюк с циклическим переносом - это весело и хорошо для игры в гольф с отключенной оптимизацией, но переполнение со знаком - неопределенное поведение в ISO C ++. Включение оптимизации превратит эти циклы с циклическим переносом в бесконечные циклы, если только вы не скомпилируете с помощью gcc / clang, -fwrapvчтобы хорошо переполнить целое число со знаком -определенное поведение: 2 дополнения.

Интересный факт: ISO C ++ std::atomic<int>имеет четко определенные 2 дополнения! int32_tдолжен быть дополнением 2, если определено вообще, но поведение переполнения не определено, поэтому он все еще может быть typedef для intили longна любой машине, где один из этих типов равен 32 битам, без дополнения и дополнения 2.)

Не полезно для этого конкретного случая:

Вы также можете инициализировать новую переменную как копию существующей, используя либо фигурные скобки, либо (с непустым инициализатором) парены для прямой инициализации .
int a(b)илиint a{b} эквивалентныint a = b;

Но int b();объявляет функцию вместо переменной, инициализированной в ноль.

Кроме того, вы можете получить ноль с int() или char(), то есть инициализацию нуля анонимного объекта.

Мы можем заменить ваши <=сравнения <сравнениями простым логическим преобразованием : сделайте приращение счетчика цикла сразу после сравнения, а не внизу цикла. IMO, это проще, чем альтернативы, предложенные людьми, например, использование ++в первой части a, for()чтобы превратить 0 в 1.

    // comments aren't intended as part of the final golfed version
    int n;
    std::cin >> n;      // end condition

    for(int r{}; r < n;) {      // r = rows from 0 .. n-1
        ++r;
        for(int i{}; i < r;) {
            ++i;
            std::cout << i << ' ';
        }
        std::cout << std::endl;
    }

Мы могли бы сыграть в гольф, for(int r{}; r++ < n;)но IMO, что людям труднее читать. Мы не оптимизируем общее количество байтов.

Если бы мы уже использовали h , мы могли бы сохранить 'или "для места.

Предполагая среду ASCII или UTF-8, пространство char значение со значением 32. Мы можем легко создать его в переменной, а затемcout << c;

    char c{};
    c++; c++;            // c=2
    char cc(c+c+c+c);    // cc=8
    char s(cc+cc+cc+cc); // s=32 = ' ' = space in ASCII/UTF-8

И другие значения, очевидно, могут быть созданы из последовательности ++ и удвоения, основываясь на битах их двоичного представления. Эффективно сдвигая 0 (ничего) или 1 (++) в LSB, прежде чем удвоить в новую переменную.

Эта версия использует h вместо 'или ".

Это намного быстрее, чем любая из существующих версий (не полагаясь на длинный цикл), и не содержит неопределенного поведения . Он компилируется без предупреждений сg++ -O3 -Wall -Wextra -Wpedantic и сclang++ . -std=c++11необязательно. Это легальный и портативный ISO C ++ 11 :)

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

Количество уникальных байтов: 25 , исключая комментарии, которые я удалилg++ -E . И исключая пробел и перевод строки, как ваш счетчик. Я использовал sed 's/\(.\)/\1\n/g' ladder-nocomments.cpp | sort | uniq -ic этот аскубунту для подсчета вхождений каждого персонажа, и wcподсчитал, сколько уникальных символов у меня было.

#include<iostream>

int main() {
    char c{};
    c++; c++;            // c=2
    char cc(c+c+c+c);    // cc=8
    char s(cc+cc+cc+cc); // s=32 = ' ' = space in ASCII/UTF-8

    int n;
    std::cin >> n;      // end condition

    for(int r{}; r < n;) {      // r = rows counting from 0
        ++r;
        for(int i{}; i < r;) {
            ++i;
            std::cout << i << s;
        }
        std::cout << std::endl;
    }
}

Только 2 fперсонажа из for. whileВместо этого мы могли бы использовать циклы, если бы мы использовалиw .

Мы могли бы переписать циклы в стиле ассемблера, i < r || goto some_label;чтобы написать условный переход внизу цикла или что-то еще. (Но использую orвместо ||). Нет, это не работает. gotoявляется оператором, подобным ifи не может быть подкомпонентом выражения, как это может быть в Perl. В противном случае мы могли бы использовать его для удаления (и )символов.

Мы могли бы торговать fна gс if(stuff) goto label;а for, и обе петли всегда выполняются по крайней мере 1 итерации , поэтому мы должны были бы только одну петлю-ветви в нижней части, как обычный ассемблереdo{}while структуры петли. Предполагая, что пользователь вводит целое число> 0 ...

Диграфы и триграфы

К счастью, триграфы были удалены с ISO C ++ 17, поэтому нам не нужно использовать ??>вместо} если мы играем в гольф для самой последней версии C ++.

Но только триграфы конкретно: ISO C ++ 17 все еще имеет орграфы как :>для ]и %>для} . Таким образом, за счет использования %мы можем избежать {и }, и использовать %:для# чистого сохранения на 2 меньше уникальных символов.

А в C ++ есть ключевые слова оператора, например, notдля !оператора или bitorдля |оператора. С помощью xor_eqfor ^=вы можете обнулить переменную i xor_eq i, но она содержит несколько символов, которые вы не использовали.

Ток g++уже игнорирует триграфы по умолчанию даже без -std=gnu++17; Вы должны использовать -trigraphsих, или -std=c++11что-то для строгого соответствия стандарту ISO, который их включает.

23 уникальных байта:

%:include<iostream>

int main() <%
    int n;
    std::cin >> n;

    for(int r<% %>; r < n;) <%
        ++r;
        for(int i<%%>; i < r;) <%
            ++i;
            std::cout << i << ' ';
        %>
        std::cout << std::endl;
    %>
%>

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

Окончательная версия использует 'одиночную кавычку вместо hили "для пробела. Я не хотел переписывать char c{}материал, поэтому я удалил его. Печать символа более эффективна, чем печать строки, поэтому я использовал это.

Гистограмма:

$ sed 's/\(.\)/\1\n/g' ladder-nocomments.cpp | sort | uniq -ic  | tee /dev/tty | wc -l
     15         // newline
     95         // space
     11 %
      2 '
      3 (
      3 )
      4 +
      9 :
     10 ;
     14 <
      8 >
      2 a
      4 c
      6 d
      3 e
      2 f
     12 i
      2 l
      2 m
     11 n
      5 o
      7 r
      5 s
     11 t
      3 u
25   // total lines, including space and newline

Разделитель пространства (до сих пор не решен)

В уже удаленном ответе Johan Du Toit предложил использовать, в частности, альтернативный разделитель std::ends. Это символ NUL char(0), и он печатается как нулевая ширина на большинстве терминалов. Таким образом, результат будет выглядеть 1234, а не 1 2 3 4. Или, что еще хуже, отделенный мусором от всего, что не рухнуло'\0' .

Если вы можете использовать произвольный разделитель, когда цифру 0легко создать cout << some_zeroed_var. Но никто не хочет 10203040, это даже хуже, чем без разделителя.

Я пытался придумать способ создания std::stringхолдинга" " без использования charстрокового литерала. Может быть, что-то добавить к этому? Может быть, с орграфом для []установки первого байта в значение 32после создания единицы длиной 1 через один из конструкторов?

Йохан также предложил std::iosфункцию-член fill (), которая возвращает текущий символ заполнения. По умолчанию для потока установлено значение std::basic_ios::init()и ' '.

std::cout << i << std::cout.fill();заменяет, << ' ';но использует .вместо' .

С -, мы можем взять указатель coutи использование ->fill()для вызова функции - члена:
std::cout << (bitand std::cout)->fill(). Или нет, мы не использовали bни того, ни другого, поэтому могли бы& вместо его лексического эквивалента bitand.

Вызов функции-члена без . или->

Поместите это в класс и определите operator char() { fill(); }

// not digraphed
struct ss : std::ostream {  // default = private inheritance
//      ss() { init(); }  // ostream's constructor calls this for us
        operator char() { return fill(); }
}

Затем ss s{}до цикла и std::cout << i << s;внутри цикла. Отлично, он собирает и работает нормально, но мы должны были использовать pи hдля operator char(), для чистой потери 1. По крайней мере , мы избегали , bчтобы функций - членов public, используя structвместо class. (И мы можем переопределить наследование protectedв случае, если это когда-нибудь поможет).

Питер Кордес
источник
@JohanduToit: хорошая идея с cout.fill()fromstd::ios , но мы ранее не использовали . Может быть, мы можем как-то вызвать его, взяв указатель и используя ->fill()функцию-член? Что-нибудь возвращает указатель на coutкакой-либо другой поток?
Питер Кордес
Ой, << (bitand std::cout)->fill()компилирует, но использует -. (Несмотря на имя токена, bitandэто просто лексический эквивалент &, а не только побитовый оператор and. Он также работает как оператор address-of.) Хм, есть какой-то шаблон или лямбда-выражение, которое может получить указатель на функцию-член что мы можем ()без использования .или ->?
Питер Кордес
1
Единственное, что я обнаружил, это то std::ios::left, что в gcc оно определено как 32, но я не мог найти способ извлечь из этого пользу. Я думаю, что я собираюсь позволить этому пойти и сделать некоторую фактическую работу :-)
Johan du Toit
@JohanduToit: Создание int32 не проблема, мой ответ уже показывает, как это сделать, ++начиная с int c{};нуля. Но да, я не спущусь по кроличьей норе, чтобы посмотреть лямбды, шаблоны или std::function. Или std::stringидея. Но мы не привыкли gк тому, что мы не можем объявить, std::stringне проиграв; моя идея использовать gotoвместо forне удалась. decltype(something)может дать нам charтип, но стоит нам y.
Питер Кордес
1
Вы можете использовать auto вместо char для оператора: struct ss : std::ostream { operator auto () { return fill(); } };но это мало помогает.
Йохан дю Туа
7

C ++ (gcc) x86_64 только для Linux, 9295 8900 8712 6812 5590 байт, 18 уникальных символов

int m[]={111111111111111+1111111111111+1111111111111+1111111111111+1111111111111+1111111111111+1111111111111+111111111+111111111+1111111+111111+11111+11111+11+11+11+11+11+1+1+1,11111111111+11111111111+11111111111+1111111111+111111111+111111111+111111111+111111+1111+1111+111+111+111+111+11+11+11+11+11+11+11+11+11+1+1+1,111111111111111+111111111111111+111111111111+111111111111+1111111111+1111111+1111111+11111+11111+11111+1111+111+111+11+11+11+11+11+11+11+11+11+1+1+1+1+1+1+1+1+1+1,111111111111111+111111111111111+1111111111111+1111111111111+11111111111+111111111+111111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+11111+1111+111+111+11+1+1+1,1111111111111+1111111111111+11111111111+11111111111+1111111111+1111111111+1111111111+111111+11111+11111+11111+11111+1111+1111+1111+1111+111+111+111+11+11+11+11+11+11,11111111111111+1111111111111+11111111111+11111111111+11111111111+1111111111+111111111+11111111+11111111+11111111+11111111+1111+1111+1111+1111+1111+1111+1111+1111+1111+111+1+1+1+1,111111111111111+1111111111111+1111111111111+1111111111111+1111111111111+11111111111+11111111111+1111111+11111+11111+1111+1111+11+11+11+11+11+11+11+1+1+1+1,111111111111+11111111111+1111111111+1111111111+1111111111+1111111111+1111111111+1111111111+11111111+11111+11111+11111+11111+11111+11111+1+1,111111111111111+11111111111111+11111111111+11111111111+1111111111+1111111+1111111+11111+111+111+111+111+111+111+111+111+11+11+1+1+1+1+1+1,11111111111+1111111111+111111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+11+1+1+1+1+1+1+1,111111111111+11111111111+11111111111+11111111+1111111+1111111+111111+111111+111111+111111+111111+111111+111111+111111+111111+11111+11111+111+111+111+111+111+111+111+1+1+1+1+1+1+1,11==1,1111111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+1111+1111+1111+1111+1111+1111+1111+1111+1111+111+111+111+11+11+11+1+1+1,1111111111111+111111111111+11111111111+1111111111+111111111+111111111+11111111+111111+111111+111111+11111+1111+111+111+1+1,111111111111+111111111111+11111111111+11111111111+11111111111+11111111111+111111111+111111111+11111111+111111+1111+1111+111+111+111,111111111111+11111111111+1111111111+1111111111+111111111+1111111+111+111+1+1+1+1,111111111111111+11111111111111+1111111111111+1111111111111+111111111111+1111111111+1111111111+1111111111+1111111+111111+111111+111111+11111+11111+11111+1111+1111+111+11+11+1+1+1+1,111111111111111+1111111111111+1111111111111+11111111111+1111111111+11111111+11111111+1111+1111+1111+111+111+111+111+11+11,111111111+111111111+11111111+11111111+11111111+1111111+1111111+111111+11111+1111+1111+1111+1111+111+111+11+11+11+11+11+1+1+1+1+1+1+1+1,11111111111111+111111111111+111111111111+11111111111+111111111+111111+111111+111111+1111+1111+1111+1+1+1+1+1+1+1+1,11111111111+11111111111+11111111111+11111111111+1111111111+1111111111+11111111+1111111+1111111+1111111+1111111+111111+11111+11+11+11+1+1+1+1+1+1+1+1,111111111111111+111111111111111+111111111111+1111111111+1111111111+11111111+11111111+1111111+1111111+111111+111111+11111+11111+111+11+11+1+1+1+1+1+1+1+1+1+1,11111111111111+11111111111111+111111111111+11111111111+11111111111+1111111+1111111+1111111+1111111+1111111+1111111+11+11+11+11+11+11+11+11+1,11111111111111+11111111111111+11111111111+1111111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+11111+11111+1111+1111+1111+111+111+111+111+111+111+11,111111111111111+1111111111111+111111111111+111111111111+111111111111+11111111111+1111111111+1111111111+111111111+111111+111111+111111+111111+1111+11+1+1,111111111111111+11111111111111+111111111111+111111111111+1111111111+1111111111+111111111+11111111+1111+1111+1111+111+111+111+111+111+11+11+11+11+11+11+11+11+1+1+1+1,11111111111111+11111111111111+11111111111111+11111111111+11111111111+1111111111+11111111+1111111+11111+11111+11111+1111+111+111+111+11+11+11+11+1+1+1+1+1+1,111111111111111+11111111111111+1111111111+111111111+111111111+111111111+11111111+1111111+111111+11111+1111+1111+1111+111+111+111+111+111+111+11+11+11+11+11+11+11+11+11+1+1+1+1,111111111111111+1111111111111+1111111111111+1111111111111+1111111111+111111111+111111111+111111111+11111111+1111111+11111+1111+1111+1111+111+111+111+11,1111111111111+1111111111+11111111+11111111+11111111+11111+1111+111+111+11+11+11+11+11+11+11+11+11+1+1+1+1+1+1+1+1+1+1,11111111111111+1111111111+1111111111+111111111+11111111+1111111+1111111+1111111+111111+11111+11111+11111+11111+11111+1111+1111+1111+111+111+11+11+11+11+11+11+11+1+1+1+1+1+1+1,11111111111111+1111111111+1111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+111111+11111+1111+1111+111+111+111+111+111+111+1+1+1+1+1+1,111111111111111+1111111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+1111111+111111+11111+11111+11111+1111+111+111+111+11+11+11+11+11,1111111111+111111111+1111111+1111111+111111+111111+11111+11111+11111+11111+11111+11111+1111+1111+1111+11+11+11+11+11+11+11+11+11+1+1+1,111111111111111+111111111111+111111111111+111111111111+11111111111+1111111111+1111111111+1111111111+11111111+11111+1111+1111+111+111+111+111+111+111+111+111+1,1111111111+111111111+111111111+11111111+1111111+1111111+1111111+111111+11111+11111+11111+11111+11111+111+111+111+11+11+11+1,11111111111111+11111111111111+1111111111+1111111111+1111111111+1111111111+11111111+11111111+11111111+11111111+1111111+1111111+111+111+111+111+11+11+11+11+11+11+11+1+1,111111111111+11111111111+1111111111+111111111+111111111+111111+111111+111111+111111+11111+11111+11+11+11+11+11+1,111111111+11111+11111+111+11+1+1+1+1+1+1+1+1+1};main(){((int(*)())m)();}

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

Это основано на идеях из этого ответа PPCG . Программа на машинном языке выражается в виде массива 32-битных целых чисел, каждый из которых представлен в виде суммы 1+11+111.... Оказывается, это может быть более эффективным, чтобы закодировать xкак yтаковой y%(1<<32)==x. Закодированная программа машинного языка следующая

0x0000000000000000:  55                         push    rbp
0x0000000000000001:  31 ED                      xor     ebp, ebp
0x0000000000000003:  53                         push    rbx
0x0000000000000004:  48 83 EC 18                sub     rsp, 0x18
0x0000000000000008:  48 8D 74 24 0C             lea     rsi, [rsp + 0xc]
0x000000000000000d:  31 C0                      xor     eax, eax
0x000000000000000f:  31 FF                      xor     edi, edi
0x0000000000000011:  6A 01                      push    1
0x0000000000000013:  5A                         pop     rdx
0x0000000000000014:  0F 05                      syscall 
0x0000000000000016:  89 C3                      mov     ebx, eax
0x0000000000000018:  85 C0                      test    eax, eax
0x000000000000001a:  74 0C                      je      0x28
0x000000000000001c:  6B ED 0A                   imul    ebp, ebp, 0xa
0x000000000000001f:  03 6C 24 0C                add     ebp, dword ptr [rsp + 0xc]
0x0000000000000023:  83 ED 30                   sub     ebp, 0x30
0x0000000000000026:  EB E0                      jmp     8
0x0000000000000028:  C7 44 24 0C 00 00 00 00    mov     dword ptr [rsp + 0xc], 0
0x0000000000000030:  FF C3                      inc     ebx
0x0000000000000032:  8B 44 24 0C                mov     eax, dword ptr [rsp + 0xc]
0x0000000000000036:  8D 78 01                   lea     edi, [rax + 1]
0x0000000000000039:  89 7C 24 0C                mov     dword ptr [rsp + 0xc], edi
0x000000000000003d:  E8 27 00 00 00             call    0x69
0x0000000000000042:  6A 20                      push    0x20
0x0000000000000044:  48 89 E6                   mov     rsi, rsp
0x0000000000000047:  52                         push    rdx
0x0000000000000048:  58                         pop     rax
0x0000000000000049:  50                         push    rax
0x000000000000004a:  5F                         pop     rdi
0x000000000000004b:  0F 05                      syscall 
0x000000000000004d:  5E                         pop     rsi
0x000000000000004e:  39 5C 24 0C                cmp     dword ptr [rsp + 0xc], ebx
0x0000000000000052:  7C DE                      jl      0x32
0x0000000000000054:  6A 0A                      push    0xa
0x0000000000000056:  48 89 E6                   mov     rsi, rsp
0x0000000000000059:  52                         push    rdx
0x000000000000005a:  58                         pop     rax
0x000000000000005b:  0F 05                      syscall 
0x000000000000005d:  5E                         pop     rsi
0x000000000000005e:  39 DD                      cmp     ebp, ebx
0x0000000000000060:  7F C6                      jg      0x28
0x0000000000000062:  48 83 C4 18                add     rsp, 0x18
0x0000000000000066:  5B                         pop     rbx
0x0000000000000067:  5D                         pop     rbp
0x0000000000000068:  C3                         ret     
0x0000000000000069:  85 FF                      test    edi, edi
0x000000000000006b:  74 2C                      je      0x99
0x000000000000006d:  89 F8                      mov     eax, edi
0x000000000000006f:  6A 0A                      push    0xa
0x0000000000000071:  59                         pop     rcx
0x0000000000000072:  48 83 EC 18                sub     rsp, 0x18
0x0000000000000076:  99                         cdq     
0x0000000000000077:  F7 F9                      idiv    ecx
0x0000000000000079:  89 C7                      mov     edi, eax
0x000000000000007b:  8D 42 30                   lea     eax, [rdx + 0x30]
0x000000000000007e:  89 44 24 0C                mov     dword ptr [rsp + 0xc], eax
0x0000000000000082:  E8 E2 FF FF FF             call    0x69
0x0000000000000087:  48 8D 74 24 0C             lea     rsi, [rsp + 0xc]
0x000000000000008c:  6A 01                      push    1
0x000000000000008e:  58                         pop     rax
0x000000000000008f:  50                         push    rax
0x0000000000000090:  5F                         pop     rdi
0x0000000000000091:  50                         push    rax
0x0000000000000092:  5A                         pop     rdx
0x0000000000000093:  0F 05                      syscall 
0x0000000000000095:  48 83 C4 18                add     rsp, 0x18
0x0000000000000099:  C3                         ret

... который основан на следующем C-коде.

void print(int x){
  if( x ) {
    int y=x%10+'0';
    print(x/10);
    write(1,&y,1);
  }
}
void f() {
  int i=0,j=0,k;
  for( ;read(0,&k,1);i=i*10+k-'0' );
  do {
    for( j++,k=0; print( ++k ), write(1," ",1), k<j; );
    write(1,"\n",1);
  } while(j<i );
}

Редактировать: теперь принимает входные данные stdinвместо argv[1]. Спасибо @ ASCII-only и @PeterCordes за их предложения!

Edit4: слегка улучшено кодирование.

ceilingcat
источник
-wфлаг пожалуйста: P (также можно переименовать iiв a)
ASCII-только
Вам нужно gcc -zexecstackдля этого, верно? Потому int m[]что нет const. (И последние наборы инструментов .rodataв любом случае помещают на неисполняемую страницу, поэтому даже const int m[]не работают, например, на моей системе Arch Linux с gcc8.2.1 20181127 и ld(GNU Binutils) 2.31.1.) В любом случае, вы забыли упомянуть об этом в своем ответе, но это в твоей ссылке TIO.
Питер Кордес
Кстати, алгоритм подсчета уникального подсчета OP не учитывает пробел и символ новой строки, поэтому вам не нужно делать все это ужасным для чтения, только массив: P
Питер Кордес
Вы можете сохранить байты машинного кода, скопировав 1с push %rax/ pop %rdiвместо другого push-немедленного. Или, проще говоря, для значений, которые не являются 64-битными, то есть не указателями, 2-байтовыми mov %eax, %edi. Кроме того, Linux syscallне уничтожает свои входные регистры, только raxс возвращаемым значением и RCX + R11 с сохраненными RIP и RFLAGS как часть работы syscallинструкции. Таким образом, вы можете оставить rdiи rdxустановить 1между вызовами, и использовать разные рег. Кроме того, RBX является сохраняемым при вызове, поэтому его нельзя сохранить в RBX. Это работает, потому что стартовый код CRT не волнует.
Питер Кордес
6

21 уникальный персонаж + 1 неустранимый перевод строки

%:include<iostream>
int(n)(int(i))<%
    if(--i)if(n(i))<%%>
    if(i)if(std::cout<<i<<std::addressof(std::cout)->fill())<%%>
%>
int(l)(int(i))<%
    if(n(-(--i)))<%%>
%>
int(m)(int(i))<%
    if(--i)if(m(i))<%%>
    if(i)if(l(-i))<%%>
    if(i)if(std::cout<<std::endl)<%%>
%>
int(c)(int(i))<%
    if(m(-(--i)))<%%>
%>
int(main)(int(i))<%
    if(std::cin>>i)<%%>
    if(c(-i))<%%>
%>

Пробелы не требуются, за исключением первой новой строки. Скомпилировано в g ++ 7.3.0.

Используемые символы: %:include<ostram>()f-.

Улучшения других ответов:

  1. Удалены точки с запятой, изменив forциклы наif и рекурсии.
  2. Получил космический характер std::addressof(std::cout)->fill(), ака std::cout.fill().
jimmy23013
источник
станд :: AddressOf, приятно!
Йохан дю Туа
2

21 20 уникальных персонажей, исключая пробелы

Все пробелы могут быть изменены на новые строки.

%:include<iostream>
%:include<list>
int n;
const int co<%%>;
const int ci<%not co%>;
const int cmu<%-ci-ci-ci-ci%>;
const char ctd<%-cmu-cmu-cmu-cmu-cmu-cmu-cmu-cmu%>;
const int cia<%-ctd-ctd-ctd-ctd-ctd-cmu%>;
const int ciu<%cia- -ci- -ci%>;

struct<%struct<%struct<%struct<%struct<%struct<%struct<%
int c<:ctd-ci:>;
%>d<:ctd:>;int c<:ctd-ci:>;%>d<:ctd:>;int c<:ctd-ci:>;
%>d<:ctd:>;int c<:ctd-ci:>;%>d<:ctd:>;int c<:ctd-ci:>;
%>d<:ctd:>;int c<:ctd-ci:>;%>d<:-cmu:>;int c<:-ci-cmu:>;
%>e<:co:><:ctd:><:ctd:><:ctd:><:ctd:><:ctd:><:ctd:>;

int i<:co:>;
auto ia<%e%>;
auto iu<%e%>;
int l<%std::cin>>n and co%>;

struct s<%
    int c<%std::cout<<i<:ciu:>- --i<:cia:><<ctd and n%>;
%>;
struct o<%
    int c<%--ia and n%>;
%>;
struct t<%
    std::list<s>c<%- --l%>;
    std::list<o>r<%-l%>;
    int m<%std::cout<<std::endl and n%>;
%>;
std::list<t>a<%n%>;
int main;

Выход с сегфо. Используемые символы: %:include<ostram>;-h.

Он работает в этой конкретной версии компилятора на 64-битной Linux:

g++-5 (Ubuntu 5.5.0-12ubuntu1) 5.5.0 20171010

С параметром:

-std=c++17

Даже тогда я не уверен, что это всегда будет работать. Это может также зависеть от многих других вещей.ciaи ciuсмещения памяти делятся на 4 между ia iuи i. ( int32-битный в этой версии.) Возможно, вам придется изменить числа в соответствии с фактическим смещением. Адреса были бы намного более предсказуемыми, если бы они все содержались в структуре. К сожалению, нестатическое autoне допускается в структуре.

e массив из 0 элементов типа элемента с размером (2 32 -1) × 2 32 байта. Если соответствующий тип указателя eуменьшен, то верхняя половина указателя будет уменьшена на (2 32 -1), что эквивалентно увеличению на единицу. Это может сбросить уменьшенный счетчик без использования знака равенства.

Более разумная версия, которая должна работать более надежно, но использует еще один символ =:

%:include<iostream>
%:include<list>
int n;
int ci<%not n%>;
int cmu<%-ci-ci-ci-ci%>;
char ctd<%-cmu-cmu-cmu-cmu-cmu-cmu-cmu-cmu%>;
int i;
int l<%std::cin>>n and n-n%>;

struct s<%
    int c<%std::cout<<- --i<<ctd and n%>;
%>;
struct t<%
    std::list<s>c<%- --l%>;
    int r<%i=n-n%>;
    int m<%std::cout<<std::endl and n%>;
%>;
std::list<t>a<%n%>;
int main;

Даже это не работает в последней версии g ++, потому что кажется, что оно больше не позволяет определять mainпроизвольный тип.

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

jimmy23013
источник
1

22 уникальных персонажа, исключая пробелы. Разделяет числа символом NUL, который правильно отображается в Windows.

%:include<iostream>
int main(int n)<%
    std::cin>>n;
    for(int r<%%>;r++<n;)<%
        for(int i<%%>;i<r;)
            std::cout<<++i<<std::ends;
        std::cout<<std::endl;
    %>
%>

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

Гистограмма:

[%] 0x25 = 9
[:] 0x3A = 11
[)] 0x29 = 3
[i] 0x69 = 11
[n] 0x6E = 12
[c] 0x63 = 4
[l] 0x6C = 2
[u] 0x75 = 3
[d] 0x64 = 8
[e] 0x65 = 4
[<] 0x3C = 13
[o] 0x6F = 5
[s] 0x73 = 7
[t] 0x74 = 12
[r] 0x72 = 6
[a] 0x61 = 2
[m] 0x6D = 2
[>] 0x3E = 7
[(] 0x28 = 3
[;] 0x3B = 7
[f] 0x66 = 2
[+] 0x2B = 4
Unique Characters: 22
Total Characters: 189
Йохан дю Туа
источник
std :: end - это символ NUL ( char(0)), а не пробел ( char(32)в ASCII / UTF-8). en.cppreference.com/w/cpp/io/manip/ends . Я попробовал это на своем рабочем столе Linux, чтобы убедиться, и вывод выглядит так 1234, а не1 2 3 4 . Это выглядит так же на вашем выходе TIO!
Питер Кордес
@PeterCordes, в ОП не указывается, как следует разделять числа ;-)
Johan du Toit
Вы действительно думаете , что они бы потратили характер на "для , " "если они могли бы использовать iiiiдля разделения с '0'для 10203040? Я полагаю, вы можете доказать, что в двоичном выводе программы все еще есть разделитель, но указание этого изменения и его описание на английском языке важно для вашего ответа, потому что это не замена замены! Я был бы счастлив удалить мое отрицательное мнение, если вы расширите свой ответ, чтобы объяснить и оправдать это.
Питер Кордес
1
@PeterCordes, Точка занята.
Йохан дю Туа