Нумерация страниц в стиле xkcd

65

Книга Рэндалла Манро «xkcd, том 0» использует довольно странную систему счисления для номеров страниц. Первые несколько номеров страниц

1, 2, 10, 11, 12, 20, 100, 101, 102, 110, 111, 112, 120, 200, 1000, 1001, ...

Это выглядит как троичный, но обратите внимание, что он прыгает с 20прямой к 100, от 120к 200и от 200к 1000. Один из способов определения этой последовательности состоит в том, чтобы сказать, что она перечисляет все троичные числа, которые содержат не более одного 2и не 1после этого 2. Вы можете найти это на OEIS в записи A169683 . Эта система счисления называется асимметричной двоичной системой .

Ваша задача - найти представление заданного натурального числа Nв этой системе счисления.

Вы можете написать программу или функцию, принимая ввод через STDIN (или ближайшую альтернативу), аргумент командной строки или аргумент функции и выводя результат через STDOUT (или ближайшую альтернативу), возвращаемое значение функции или параметр функции (out).

Выходные данные могут быть строкой, числом с десятичным представлением, равным асимметричному двоичному представлению, или списком цифр (в виде целых чисел или символов / строк). Вы не должны возвращать ведущие нули.

Это код гольф, поэтому самый короткий ответ (в байтах) выигрывает.

Интересный факт: в этой системе счисления есть некоторые достоинства. Увеличивая число, вы всегда будете менять не более двух соседних цифр - вам никогда не придется переносить изменение по всему номеру. С правильным представлением, которое позволяет увеличивать в O (1).

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

1 => 1
2 => 2
3 => 10
6 => 20
7 => 100
50 => 11011
100 => 110020
200 => 1100110
1000 => 111110120
10000 => 1001110001012
100000 => 1100001101010020
1000000 => 1111010000100100100
1048576 => 10000000000000000001

1000000000000000000 => 11011110000010110110101100111010011101100100000000000001102

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

Leaderboards

Вот фрагмент стека, который генерирует как регулярную таблицу лидеров, так и обзор победителей по языкам.

Чтобы убедиться, что ваш ответ обнаружен, начните его с заголовка, используя следующий шаблон уценки:

# Language Name, N bytes

где Nразмер вашего представления. Если вы улучшите свой счет, вы можете сохранить старые результаты в заголовке, вычеркнув их. Например:

# Ruby, <s>104</s> <s>101</s> 96 bytes

<script>site = 'meta.codegolf'; postID = 5314; isAnswer = true; QUESTION_ID = 51517</script><script src='https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js'></script><script>jQuery(function(){var u='https://api.stackexchange.com/2.2/';if(isAnswer)u+='answers/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJeRCD';else u+='questions/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJO6t)';jQuery.get(u,function(b){function d(s){return jQuery('<textarea>').html(s).text()};function r(l){return new RegExp('<pre class="snippet-code-'+l+'\\b[^>]*><code>([\\s\\S]*?)</code></pre>')};b=b.items[0].body;var j=r('js').exec(b),c=r('css').exec(b),h=r('html').exec(b);if(c!==null)jQuery('head').append(jQuery('<style>').text(d(c[1])));if (h!==null)jQuery('body').append(d(h[1]));if(j!==null)jQuery('body').append(jQuery('<script>').text(d(j[1])))})})</script>

Мартин Эндер
источник
32
У меня была эта книга с тех пор, как она появилась, и я никогда не замечал нумерацию страниц.
Алекс А.
2
@AlexA. У меня есть это на моем Kindle, где вы не можете сделать какую-либо интересную нумерацию страниц.
LegionMammal978
21
@ LegionMammal978: трагический.
Алекс А.
1
@ SuperJedi224 Похоже, консенсуса нет , так что извините (я бы сделал исключение из консенсуса, если бы это был единственный вид ввода, который мог обработать ваш язык, но, похоже, это не так).
Мартин Эндер
4
Это напоминает мне о том, как я раньше считал, когда мне было 3 года. Я рассуждал: «нет пятидесяти десяти, поэтому после ста девяти должно быть двести». Я осознал свою ошибку, только увидев разницу между 59->60и 109->110с дополнительными 0.
Cyoce

Ответы:

12

Pyth, 17 байт

Ljb3ye.f!-P-yZ01Q

Это несколько смехотворно медленно O(output^log_2(3)). Это экспоненциально по длине ввода, но не по экспоненте вдвойне, как некоторые ответы на странице. Некоторые идеи взяты из ответа @ Dennis, здесь .

Демонстрация.

Он использует .fфункцию Pyth «цикл, пока не найдено n совпадений».

isaacg
источник
32

CJam, 24 23 22 21 19 байтов

ri_)2b,,W%{2\#(md}/

Это подход O (log n) , где n - вход, который мгновенно завершает последний тест. Он преобразует n непосредственно в двоичный файл с перекосом, используя модульное деление на значения цифры 1 .

Этот код заканчивается ошибкой, которая переходит к STDERR с интерпретатором Java, что разрешено в соответствии с консенсусом по Meta .

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

Ошибка может быть устранена за счет 2 байтов, добавив 2>к W%.

Спасибо @ MartinBüttner за отыгрывание одного байта.

Фон

Косое двоичное представление a k ... a 0 соответствует целому числу n = (2 k + 1 -1) a k + ... + (2 1 -1) a 0 .

Поскольку оба (2 k -1) + ... + (2 1 -1) = 2 k + 1 - (k + 2) и (2 k -1) + ... + 2 (2 j -1) = 2 к + 1 - (2 J + 1 - 2 J + к + 1) меньше , чем 2 к + 1 -1 , значения в к к в 0 могут быть восстановлены путем последовательного модульного деления на 2 K + 1 -1 , 2 к -1 и др.

Для начала нам нужно сначала найти значение 2 k + 1 -1 . Поскольку n не больше 2 (2 k + 1 -1) , целое число n + 1 должно быть строго меньше, чем 2 k + 2 .

Таким образом, если взять целую часть двоичного логарифма n + 1, то получится k + 1 .

Наконец, мы видим, что целое число n + 1 имеет ⌊log 2 (n + 1) ⌋ цифр в базе 2.

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

ri    e# Read an integer N from STDIN.
2b,   e# Push the number of binary digits of N + 1, i.e, K + 2 = log(N + 1) + 1.
,W%   e# Push the range [K+1 ... 0].
{     e# For each J in the range:
  2\# e#   J -> 2**J
  (   e#     -> 2**J - 1
  md  e#   Perform modular division of the integer on the stack (initially N)
      e#   by 2**J - 1: N, 2**J - 1 -> N/(2**J - 1), N%(2**J - 1)
}/    e#

В двух последних итерациях мы выполняем модульное деление на 1 и 0 . Первый помещает нежелательный 0 в стек. Последняя попытка выполнения 0 0 md, которая извлекает из стека оба нежелательных 0 с, немедленно завершается, вместо того, чтобы что-либо выдвигать, и сбрасывает стек в STDOUT.

Деннис
источник
28

Python 2, 67 байт

def f(n):x=len(bin(n+1))-3;y=2**x-1;return n and n/y*10**~-x+f(n%y)

Кажется, работает для данных тестов. Если я правильно понял, это должно быть примерно O(place values set in output)так, так что он легко делает последний случай.

Звоните как f(100). Возвращает десятичное представление, равное косому двоичному файлу.

Python 3, 65 байт

def g(n,x=1):*a,b=n>x*2and g(n,x-~x)or[n];return a+[b//x,b%x][:x]

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

Звоните как g(100). Возвращает список цифр.

Sp3000
источник
это 2andскомпилировать в 3? Я в 2 и 2and2выдает синтаксическую ошибку
TankorSmash
3
@TankorSmash 2and2не будет работать, потому что он будет проанализирован как 2 and2- try 2and 2, который должен работать, если ваша версия Python достаточно новая (протестирована в Python 2.7.10)
Sp3000
О, хорошо, ты прав. Даже на 2.7.3 это работает.
TankorSmash
12

CJam, 22 21 20 байт

ri_me,3fb{0-W<1-!},=

Это подход O (e n n) , где n - вход. Он перечисляет первые ⌊e n неотрицательные целые числа в базе 3, удаляет те, которые имеют 2 с или 1 с после первых 2 (если есть), и выбирает n + 1- е число .

Попробуйте онлайн в интерпретаторе CJam .

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

ri    e# Read an integer N from STDIN.
_me,  e# Push [0 ... floor(exp(N))-1].
3fb   e# Replace each integer in the range by the array of its digits in base 3.
{     e# Filter; for each array A:
  0-  e#   Remove all 0's.
  W<  e#   Remove the last element.
  1-  e#   Remove all 1's.
  !   e#   Logical NOT. Pushes 1 iff the array is empty.
},    e#   If ! pushed 1, keep the array.
=     e# Select the (N+1)th element of the filtered array.
Деннис
источник
9

Pyth, 20 байт

Jt^2hslhQ#p/=%QJ=/J2

Запускается в O (log (input ())), что значительно меньше секунды для окончательного теста. Основано на прогоне до ошибки цикла. Нет завершающего перевода строки.

Демонстрация.

Объяснение:

Jt^2hslhQ#p/=%QJ=/J2
                        Implicit: Q is the input.
      lhQ                          log(Q+1,2)
     slhQ                    floor(log(Q+1,2))
    hslhQ                    floor(log(Q+1,2))+1
  ^2hslhQ                 2^(floor(log(Q+1,2))+1)
 t^2hslhQ                 2^(floor(log(Q+1,2))+1)-1
Jt^2hslhQ               J=2^(floor(log(Q+1,2))+1)-1
         #              until an error is thrown:
            =%QJ        Q=Q%J
                =/J2    J=J/2
           /            The value Q/J, with the new values of Q and J.
          p             print that charcter, with no trailing newline.

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

  • Удалить каждую цифру значения Jиз Qс =%QJ. Например, если Q=10и J=7, Qстановится 3, что соответствует перекосу двоичного файла, изменяющемуся от 110на 10. Это не влияет на первую итерацию.
  • Перейдите Jк следующему меньшему косому двоичному базовому значению с помощью =/J2. Это сражен деление на 2, изменение J=7к J=3, например. Поскольку это происходит до того, как выводится первая цифра, Jинициализируется на одну цифру выше необходимой.
  • Найти фактическое значение цифры с помощью /QJ(эффективно).
  • Напечатайте это значение pвместо печати по умолчанию в Pyth, чтобы избежать запятой новой строки.

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

isaacg
источник
8

ES6, 105 байт

f=n=>{for(o=0;n--;c?o+=Math.pow(3,s.length-c):o++)s=t(o),c=s.search(2)+1;return t(o);},t=a=>a.toString(3)

Использование: f(1048576)=> `" 10000000000000000001 "

Проверьте последний аргумент на свой страх и риск. Я сдался через 5 секунд.

И красивая печать с комментариями!

f=n=>{ //define function f with input of n (iteration)
    for(o=0; //define o (output value in decimal)
        n--; //decrement n (goes towards falsy 0) each loop until 0
        c?o+=Math.pow(3,s.length-c):o++) //if search finds a 2, increment output by 3^place (basically moves the 2 to the left and sets the place to 0), else ++
        s=t(o), //convert output to base 3      
        c=s.search(2)+1; //find the location of 2, +1, so a not-found becomes falsy 0.
    return t(o); //return the output in base 3
},

t=a=>a.toString(3);  //convert input a to base 3
Компас
источник
5
Кстати, безымянные функции вполне приемлемы, поэтому вам не нужно f=.
Мартин Эндер
2
-16 байт:f=n=>{for(o=0;~n--;o+=c?Math.pow(3,s.length+c):1)s=o.toString(3),c=~s.search(2);return s}
nderscore
@nderscore Довольно круто: D
Компас
1
-7 байт, если вы используете ES7: заменить Math.pow(3,s.length+c)на 3**(s.length+c).
Густаво Родригес
3
@GustavoRodrigues Я даже не закончил изучение ES6! @ _ @
Компас
7

Сетчатка, 55 байт

^
0a
(+`12(.*a)1
20$1
0?2(.*a)1
10$1
0a1
1a
)`1a1
2a
a
<empty line>

Принимает участие в одинарных.

Каждая строка должна идти в свой собственный файл, но вы можете запустить код как один файл с -sфлагом. Например:

> echo 11111|retina -s skew
12

Метод: Выполнение приращения для строки, введенной число раз, начиная со строки 0.

Мы используем следующие правила приращения:

  • если содержит 2: ^2 -> ^12; 02 -> 12;12 -> 20
  • если не содержит 2: 0$ -> 1$;1$ -> 2$

(Там может быть более одной 2в строке, ^и $отмечает начало и конец строки в правилах) .

Больше информации о Retina.

randomra
источник
7

Ява, 154 148

n->{String s="0";for(;n-->0;)s=s.contains("2")?s.replaceAll("(^|0)2","10").replace("12","20"):s.replaceAll("1$","2").replaceAll("0$","1");return s;}

Этот ответ принимает форму одной анонимной функции, которая принимает целочисленный аргумент и возвращает ответ в виде строки. Ниже приведен полный класс для тестирования этого решения.

import java.util.function.Function;
public class Skew {
    public static void main(String[] args){
        Function<Integer,String> skew = n->{String s="0";for(;n-->0;)s=s.contains("2")?s.replaceAll("(^|0)2","10").replace("12","20"):s.replaceAll("1$","2").replaceAll("0$","1");return s;};

        for(String s:args){
            System.out.println(skew.apply(Integer.parseInt(s)));
        }
    }
}
Анк-Морпорка
источник
5

Баш + кореутилс, 52

dc -e3o0[r1+prdx]dx|grep -v 2.\*[12]|sed -n $1{p\;q}

Это грубое насилие, поэтому оно довольно медленно для больших чисел.

Выход:

$ ./xkcdnum.sh 1000
111110120
$ 
Цифровая травма
источник
5

Java 337 335 253 246 244 байта

Метод, который принимает индекс как a longи возвращает результат в виде строки

Использует longдля индекса , так может теоретически обработать последний тестовый случай, но я действительно не хотел бы предложить это.

String f(long i){List<Long>l=new ArrayList<>();l.add(0L);for(;i-->0;){int j=l.indexOf(2);if(j!=-1){l.set(j,0L);if(j==0){l.add(0,1L);}else{l.set(j-1,l.get(j-1)+1);}}else{j=l.size()-1;l.set(j,l.get(j)+1);}}String s="";for(long q:l)s+=q;return s;}
SuperJedi224
источник
4
Вы можете немного сократить это, сделав его функцией, а не полной программой (и взяв ввод в качестве аргумента, а не из сканера).
Geobits
2
Вам не нужны скобки в if(j == 0) утверждении (четыре байта). Вам не нужно заявлять k; Вы можете просто использовать jснова (еще четыре). Вы можете использовать вывод обобщенного типа (в Java 7) в своем объявлении List ( new ArrayList<>();) (еще 4)
durron597
4

Хаскелл, 73 72

Спасибо @nimi за 1 байт!

Это решение не выиграет ни одной награды, последние пару тестов занимают слишком много времени, но, думаю, я играл в нее неплохо.

i(2:b)=1:0:b
i[b]=[b+1]
i(b:2:c)=b+1:0:c
i(b:c)=b:i c
s=(iterate i[0]!!)

Это решение - довольно наивный подход, который вычисляет асимметричное двоичное число n, увеличивая его в 0 nраз.

Анк-Морпорка
источник
4

CJam, 24 байта

Q{0\+2a/())+a\+0a*}ri*si

Это подход O (n log n) , где n - вход. Он начинается с асимметричного двоичного представления, равного 0, и увеличивает соответствующее целое число n раз.

Попробуйте онлайн в интерпретаторе CJam .

Фон

Увеличение числа в асимметричном двоичном коде можно выполнить, выполнив два простых шага:

  1. Заменить возможное 2 на 0 .

  2. Если 2 был заменен, увеличьте число слева.

    В противном случае увеличьте последнюю цифру.

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

Q     e# Push an empty array.
{     e# Define an anonymous function:
  0\+ e#   Prepend a 0 to the array.
  2a/ e#   Split the array at 2's.
  (   e#   Shift out the first chunk of this array.
  )   e#   Pop the last digit.
  )+  e#   Increment it and append it to the array.
  a\+ e#   Prepend the chunk to the array of chunks.
  0a* e#   Join the chunks, using [0] as separator.
      e#   If there was a 2, it will get replaced with a 0. Otherewise, there's
      e#   only one chunk and joining the array dumps the chunk on the stack.
}     e#
ri*   e# Call the function int(input()) times.
si    e# Cast to string, then to integer. This eliminates leading 0's.
Деннис
источник
4

VBA, 209 147 142 байта

Sub p(k)
For i=1To k
a=StrReverse(q)
If Left(Replace(a,"0",""),1)=2Then:q=q-2*10^(InStr(a,2)-1)+10^InStr(a,2):Else:q=q+1
Next
msgbox q
End Sub

Моя математика неэффективна, и мой гольф может использовать работу. Но это моя первая попытка в PoG, и я решил попробовать. Что-то вроде грубой силы.

Он просто считает на 1, если последняя цифра не равна 2, затем отступает на 2 и прыгает вперед на 10. Плюс тянущиеся 0.

Это перестает работать на 65534, потому что VBA настаивает на выдаче вывода в научной нотации, но логика должна работать нормально для еще больших чисел

С нетерпением жду предложений по игре в гольф, VBA не очень дружелюбен к гольфу, но он не так часто представлен, и я думаю, что он может превзойти Java по длине.

Edit1: спасибо Ману за помощь сбрить 62 байта

Edit2: поменялся местами debug.printв msgboxкачестве вывода. Сохранено 5 байт

JimmyJazzx
источник
1
Вы можете удалить скобки из Debug.Print (q). Кроме того, вы можете удалить большую часть пробелов (редактор вернет их обратно, но они не нужны). Вам не нужно заявлять k as Long, просто написать k. Это будет переменная типа Variant, и код все равно будет работать. С этими советами вы должны получить ~ 165 байтов.
CommonGuy
Еще несколько мыслей: вы можете пропустить первый и последний аргумент InStr, они не являются обязательными. Trim()не нужно, так как у вас нет пробелов. При правильном применении я получаю 147 байтов .
CommonGuy
1
Спасибо за справку, один быстрый вопрос, вывод должен быть стандартным. Я не уверен, что это будет в VBA. debug.print qбудет стандартный вывод? msgbox qкороче, но опять-таки кажется, что это не совсем стандартный вывод. Sheet1.cells(1,1)похоже на типичный вывод, но предполагает его работу в Excel. Я просто не совсем уверен в том, насколько строгий код-гольф в подобных вещах.
JimmyJazzx
Поздравляю, вы победили Java-ответ;) Я тоже не знаю ... Просто используйте MsgBox, если кто-то жалуется, вы все равно можете изменить его обратно.
CommonGuy
4

Javascript ES6, 99 86 78 76 72 символов

f=n=>{for(s="1";--n;s=s.replace(/.?2|.$/,m=>[1,2,10][+m]||20));return s}

// Old version, 76 chars:
f=n=>{for(s="1";--n;s=s.replace(/02|12|2|.$/,m=>[1,2,10][+m]||20));return s}

// Old version, 86 chars:
f=n=>{for(s="1";--n;s=s.replace(/(02|12|2|.$)/,m=>[1,2,10,,,,,,,,,,20][+m]));return s}

// Old version, 99 chars:
f=n=>{for(s="1";--n;s=s.replace(/(^2|02|12|20|.$)/,m=>({0:1,1:2,2:10,12:20,20:100}[+m])));return s}

Контрольная работа:

;[1,2,3,6,7,50,100,200,1000,10000,100000,1000000,1048576].map(f) == "1,2,10,20,100,11011,110020,1100110,111110120,1001110001012,1100001101010020,1111010000100100100,10000000000000000001"

Интересный факт: в этой системе счисления есть некоторые достоинства. Увеличивая число, вы всегда будете менять не более двух соседних цифр - вам никогда не придется переносить изменение по всему номеру. С правильным представлением, которое позволяет увеличивать в O (1).

Спасибо за факт - это основа моего решения :)

Qwertiy
источник
Как я могу оставить ненужные скобки в регулярном выражении? o_O
Qwertiy
3

Октава, 107 101 байт

Должно быть O (log n), если я это правильно понимаю ...

function r=s(n)r="";for(a=2.^(uint64(fix(log2(n+1))):-1:1)-1)x=idivide(n,a);r=[r x+48];n-=x*a;end;end

Довольно-печати:

function r=s(n)
  r="";
  for(a=2.^(uint64(fix(log2(n+1))):-1:1)-1)
    x=idivide(n,a);
    r=[r x+48];
    n-=x*a;
  end
end

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

Вывод (я хочу 1e18 - 1показать, что могу сделать это точно, а последний набор выводов показывает, сколько времени потребуется для вычисления этого значения):

octave:83> s(uint64(1e18))
ans = 11011110000010110110101100111010011101100100000000000001102

octave:84> s(uint64(1e18)-1)
ans = 11011110000010110110101100111010011101100100000000000001101

octave:85> tic();s(uint64(1e18)-1);toc()
Elapsed time is 0.0270021 seconds.
dcsohl
источник
3

T-SQL, 221 189 177 байт

РЕДАКТИРОВАТЬ: Исходные версии этого кода будет производить неправильный вывод для некоторых чисел, это было исправлено.

При каждом запросе здесь просто добавьте число для вычисления перед первой запятой.

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

DECLARE @ BIGINT=,@T VARCHAR(MAX)='';WITH M AS(SELECT CAST(2AS BIGINT)I UNION ALL SELECT I*2FROM M WHERE I<@)SELECT @T += STR(@/(I-1),1),@%=(I-1)FROM M ORDER BY I DESC SELECT @T

И вот оно снова, но читабельно:

DECLARE 
    @ BIGINT=,
    @T VARCHAR(MAX)='';

WITH M AS
(
    SELECT
        CAST(2 AS BIGINT) I

    UNION ALL

    SELECT I * 2
    FROM M
    WHERE I < @
)

SELECT 
    @T+=STR(@/(I-1),1),
    @%=(I-1)
FROM M 
ORDER BY I DESC

SELECT @T

Если я использую только целые числа, это может быть немного короче: 157 байтов:

DECLARE @ INT=,@T VARCHAR(MAX)='';WITH M AS(SELECT 2I UNION ALL SELECT I*2FROM M WHERE I<@)SELECT @T+=STR(@/(I-1),1),@%=(I-1)FROM M ORDER BY I DESC SELECT @T

И еще раз, более читабельным:

DECLARE 
    @ INT=,
    @T VARCHAR(MAX)='';

WITH M AS
(
    SELECT
        2I

    UNION ALL

    SELECT 
        I * 2
    FROM M
    WHERE I < @
)

SELECT 
    @T+=STR(@/(I-1),1),
    @%=(I-1)
FROM M 
ORDER BY I DESC

SELECT @T
PenutReaper
источник
Помните @, это действительный идентификатор в SQL, и вы, скорее всего, можете сойти с него, Char(8000) который по-прежнему дешевле, чем nvarchar (max). Вы также можете преобразовать charвместо varcharили использовать strфункцию.
Майкл Б
@MichaelB О, я думал, что использовал @, глупая я. CHAR(8000)Совет довольно хорошо, я попробую это. Кажется, я всегда забываю о STR()благодарности за помощь.
PenutReaper
на самом деле не помогает Однако вы можете переписать часть после CTE в ::, select @t=concat(@t,@/i)которая должна быть меньше. Требуется sql2012, хотя.
Майкл Б
@MichaelB ах. CONCATЯ нахожусь на 2008. Поэтому я не могу проверить это без использования скрипта SQL прямо сейчас. Хороший звонок, хотя.
PenutReaper
3

Код машины Тьюринга, 333 293 байта

Я использую кодировку, как здесь .

Эта машина использует 9 состояний и 11 цветов.

Если двоичный ввод допустим, он может быть уменьшен до 4 цветов, что позволяет сэкономить несколько десятков байтов.

0 _ _ l 1
0 * * r 0
1 9 8 l 2 
1 8 7 l 2
1 7 6 l 2
1 6 5 l 2
1 5 4 l 2
1 4 3 l 2
1 3 2 l 2
1 2 1 l 2
1 1 0 l 2
1 0 9 l 1
1 _ _ r 8
2 _ _ l 3
2 * * l 2
3 _ 1 r 4
3 * * l 5
4 _ _ r 0
4 * * r 4
5 * * l 5
5 _ _ r 6
6 _ _ l 7
6 2 0 l 7
6 * * r 6
7 _ 1 r 4
7 0 1 r 4
7 1 2 r 4
8 _ _ * halt
8 * _ r 8

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

SuperJedi224
источник
2

Perl, 66 байт

Номер должен быть введен через STDIN.

$_=1;$c=<>;s/(.*)(.?)2(.*)/$1.$2+1 .$3.0/e||$_++while(--$c);print;
Фредерик
источник
Не могли бы вы объяснить, как работает ваше решение? Я не понимаю , как вам нужно (.?)в $2так (.*)в $1должен быть жадным и получить этот символ первой. Но если он будет удален, код больше не даст правильных результатов! Кстати, тебе не нужен финал ;.
CJ Деннис
@CJDennis Спасибо за сохраненный байт. Во всяком случае. получит цифру прямо перед двумя, если там нет цифры (например, 20). В таких случаях, как 120 или 10020, группы регулярных выражений, такие как: () (1) 2 (0) и (10) (0) 2 (0). Затем первая группа просто игнорируется, вторая группа (которая всегда либо одна цифра, если возможно, либо пустая) увеличивается, а третья группа (всегда состоящая из нулей) игнорируется и добавляется ноль. Я просто использовал запись OEIS в качестве руководства для этого регулярного выражения.
Фредерик
Я получил свой код до 53 байт: $c=<>;s/(.*)2(.*)/$1+1 .$2.0/e||$_++while($c--);print. Я был прав, (.?)никогда ничего не захватывал.
CJ Деннис
Можно оптимизировать до $_=1;$c=<>;s/(.?)2/1+$1.0/e||$_++while(--$c);print50 байтов. .*в начале или в конце можно оптимизировать, если вы просто замените его исходным текстом. Также нет смысла добавлять 0 в конце, так как в оригинале всегда есть только нули $3.
Thraidh
2

Pyth, 19 байт

m/=%Qtydtd^L2_SslhQ

Логарифмическая сложность. Легко заканчивается в необходимое количество времени. Вывод в виде списка цифр.

Демонстрация .

isaacg
источник
2

Perl, 84 70 67 байт

$n=<>;$d*=2while($d++<$n);$_.=int($n/$d)while($n%=$d--,$d/=2);print

Не очень гольф, становится лучше, но работает очень быстро!

Предложение Денниса снижает его до 51 (50 байт + ключ -p)

$d*=2while$d++<$_;$\.=$_/$d|0while$_%=$d--,$d/=2}{

Он должен вызываться так, как perl -p skew_binary.pl num_list.txtесли бы он num_list.txtсодержал одну строку с номером для кодирования на нем.

CJ Деннис
источник
@frederick, мы на краю своих мест и ждем 2.
Роберт Грант
@RobertGrant Он добавил свой комментарий от двух вещей к одному!
CJ Деннис
Две вещи: 1. Вместо использования $ ARGV [0], используйте <> в качестве ввода. Он будет принимать входные данные от stdin, если в качестве аргументов не будет никаких файлов. 2. Для нечетных схем подсчета, подобных этой, используйте регулярные выражения. Вместо выполнения нечетных математических операций вы можете заменить цифры в числе, как если бы это была строка. Самое приятное то, что вы можете использовать математические операции (например, приращение) над ним одновременно, при условии, что это строка, состоящая полностью из цифр. Проверьте документацию для операторов регулярных выражений, так как они могут быть очень полезны во многих случаях.
Фредерик
Извините, я нажал ввод, и он сохранился до того, как закончил комментарий.
Фредерик
@ frederick не будь таким скромным. Мы знаем, что случилось!
Роберт Грант
1

Математика, 65

Должно быть достаточно быстро, хотя я должен признать, что заглянул в другие материалы, прежде чем сделать это.

f = (n = #;
     l = 0; 
     While[n > 0,
      m = Floor[Log2[1 + n]];
      l += 10^(m - 1);
      n -= 2^m - 1
     ]; l)&

Использование:

f[1000000000000000000]

Выход:

11011110000010110110101100111010011101100100000000000001102

Начинает выдавать сообщения об ошибках MaxExtraPrecision где-то после 10 ^ 228 (для которых он вычисляет результат в 0,03 секунды на моем компьютере)

После снятия ограничения MaxExtraPrecision он будет обрабатывать числа примерно до 10 ^ 8000 в секунду.

Входные данные:

Timing[Block[{$MaxExtraPrecision = Infinity}, f[10^8000]];]

Выход:

{1.060807, Null}
число
источник
1

C, 95 байтов

void f(unsigned long i,int*b){for(unsigned long a=~0,m=0;a;a/=2,b+=!!m)m|=*b=i/a,i-=a**b;*b=3;}

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

Расширенный код

void f(unsigned long i,int*b)
{
    for (unsigned long a=~0, m=0;  a;  a/=2, b+=(m!=0)) {
        *b = i/a;               /* rounds down */
        i -= *b * a;
        m = m | *b;             /* m != 0 after leading zeros */
    }
    *b=3;                       /* add terminator */
}

Мы работаем путем последовательного вычитания, начиная с самой значимой цифры. Единственная сложность заключается в том, что мы используем переменную, mчтобы избежать печати начальных нулей. При unsigned long longжелании может быть сделано естественное расширение стоимостью 10 байтов.

Тестовая программа

Передайте числа для преобразования в качестве аргументов команды. Он преобразует intбуфер массива в печатную строку цифр. Время выполнения составляет менее одной миллисекунды для ввода 1000000000000000000.

#include <stdio.h>
#include <stdlib.h>
int main(int argc, char**argv)
{
    while (*++argv) {
        unsigned long i = strtoul(*argv, NULL, 10);
        int result[1024];
        f(i,result);

        /* convert to string */
        char s[1024];
        {char*d=s;int*p=result;while(*p!=3)*d++=*p+++'0';*d=0;}
        printf("%lu = %s\n", i, s);
    }

    return EXIT_SUCCESS;
}

Результаты теста

$ ./51517 $(seq 20)
1 = 1
2 = 2
3 = 10
4 = 11
5 = 12
6 = 20
7 = 100
8 = 101
9 = 102
10 = 110
11 = 111
12 = 112
13 = 120
14 = 200
15 = 1000
16 = 1001
17 = 1002
18 = 1010
19 = 1011
20 = 1012
Тоби Спейт
источник
Я думаю, что версия C ++ похожа, но может использовать auto a=~0ullдля небольшого преимущества ...
Тоби Спейт
0

CoffeeScript, 92 69 байт

Основываясь на ответе и обновлениях Qwertiy :

f=(n)->s='1';(s=s.replace /(.?2|.$)/,(m)->[1,2,10][+m]||20)while--n;s

# older version, 92 bytes
f=(n)->s='1';(s=s.replace /(^2|02|12|20|.$)/,(m)->{0:1,1:2,2:10,12:20,20:100}[+m])while--n;s
rink.attendant.6
источник
2
Переход на другой язык без даже простой оптимизации путем удаления ненужных скобок в регулярном выражении не кажется мне крутым ...
Qwertiy
@Qwertiy Я предоставил ссылку на ваш ответ, и с обоими ответами я не могу получить одинаковые результаты без скобок в регулярном выражении
rink.attendant.6
Весь случай заменен. Зачем вам это нужно, чтобы быть внутри группы? Версия JS работает в Firefox без скобок.
Qwertiy
0

Japt , 31 байт

_r/?2|.$/g_÷C ç20 ª°Zs3}}gU['0]

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

Почти прямой порт этого решения JS . Не знаю, есть ли лучший способ.

Распаковано и как это работает

X{Xr/?2|.$/gZ{Z÷C ç20 ||++Zs3}}gU['0]

X{     Declare a function...
Xr       Accept a string, replace the regex...
/?2|.$/g   /.?2|.$/   (g is needed to match *only once*, opposite of JS)
Z{       ...with the function... (matched string will be 0,1,2,02 or 12)
Z÷C        Implicitly cast the matched string into number, divide by 12
ç20        Repeat "20" that many times (discard fractions)
||         If the above results in "", use the next one instead
++Z        Increment the value
s3         Convert to base-3 string (so 0,1,2 becomes 1,2,10)
}}
gU['0] Repeatedly apply the function on "0", U (input) times
фонтанчик для питья
источник
0

Stax , 16 байт

üxëàè£öΦGΩ│Je5█ò

Запустите и отладьте его

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

Распакованный, размазанный и прокомментированный, это выглядит так. В этой программе регистр x изначально содержит входные данные.

z       push []
{       start block for while loop
 |X:2N  -log2(++x)
 {^}&   increment array at index (pad with 0s if necessary)
 xc:G-X unset high bit of x; write back to x register
w       while; loop until x is falsy (0)
$       convert to string

Запустите этот

рекурсивный
источник