Номера StickStack

22

StickStack - это очень простой язык программирования, основанный на стеке, с двумя инструкциями:

  • | толкает длину стека на стек
  • -извлекает два верхних элемента из стека и возвращает их разницу ( second topmost - topmost)

Детали языка

  • Стек пуст в начале программы.
  • Все инструкции выполняются последовательно слева направо.
  • Если в стеке меньше 2 чисел, -инструкция недопустима.
  • В конце выполнения стек должен содержать ровно одно число .

Любое целое число может быть сгенерировано программой StickStack. Например:

|||--||-- generates the number 2 through the following stack states:

[]
[0]
[0, 1]
[0, 1, 2]
[0, -1]
[1]
[1, 1]
[1, 1, 2]
[1, -1]
[2]    

Для оценки вашего кода StickStack вы можете использовать этот онлайн (CJam) оценщик . (Спасибо за @Martin за код.)

Задание

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

счет

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

Входные тесты

(Каждый номер - это отдельный контрольный пример.)

-8607 -6615 -6439 -4596 -4195 -1285 -72 12 254 1331 3366 3956 5075 5518 5971 7184 7639 8630 9201 9730

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

randomra
источник
Я предлагаю добавить пункт, который говорит: «И работает в разумные сроки», чтобы предотвратить грубую силу.
@Reticality, что подразумевается в «действителен, только если вы запустили свою программу во всех тестовых случаях»
edc65

Ответы:

7

Python 2 - 5188

Довольно эффективный по времени, и, кажется, (вероятно) оптимальное решение. Я заметил, что такой шаблон, как

|||||-|||-|-|-|------ (оптимальное решение для 25)

можно выделить как

 0  |
-1  |                  
+2   |                 -
-3    |               -
+4     | |           -
-5      - |         -
+6         | | | | -
-7          - - - -

где каждое общее значение в конце является суммой (значение каждого уровня умножается на число '|'). Так, например, выше, у нас есть -1*1 + 2*1 - 3*1 + 4*2 - 5*1 + 6*4 = 25. Используя это, я написал это решение, которое выдает схожие результаты с другими ответами, и в тривиальное время.

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

def solution(num):
    if num == 0:
        return '|'

    neg = num<0
    num = abs(num)
    high = int(num**0.5)

    def sub(high):
        counts = [1]*high
        total = num - (high+neg)/2

        if total%high == 0:
            counts[-1] += total/high
        else:
            counts[-1] += total/high
            if (total%high)%2==1 and not neg:
                counts[-1] += 1
                counts[-(total%high)-1] += 1
            elif (total%high)%2==0 and neg:
                counts[(total%high)-2] += 1
                counts[0] += 1
            else:
                counts[total%high-1] += 1

        string = ""
        for c in counts[::-1]:
            string = '|-'*(c-1)+'|'+string+'-'
        return '|'+string

    return min((sub(h) for h in range(2-neg,2*high+2,2)), key=lambda s: len(s))

Вот код, который я использовал для его тестирования

string = "-8607 -6615 -6439 -4596 -4195 -1285 -72 12 254 1331 3366 3956 5075 5518 5971 7184 7639 8630 9201 9730"
total = 0

def string_to_binary(string):
    total = 0
    for i,char in enumerate(string[::-1]):
        total += (char=='|')*(2**i)
    return total

def stickstack(bits,length):
    stack = []
    for i in range(length):
        d,bits = divmod(bits,2**(length-i-1))
        if d == 1:
            stack.append(len(stack))
        else:
            stack[-2] -= stack[-1]
            stack = stack[:-1]
    return stack

for num in string.split():
    s = solution(int(num))
    print '%s:' % num
    print s
    result = stickstack(string_to_binary(s),len(s))
    print 'Result: %s' % result
    print 'Length: %s' % len(s)
    total += len(s)
    print

print 'Total length: %s' % total
KSab
источник
2
Отличное решение! Я считаю, что оценка является оптимальной (основываясь на моих расчетах грубой силы) и основываясь на вашем описании, я думаю, что ваш алгоритм всегда дает наилучшие решения.
Рандомра
@randomra Я думаю, вполне вероятно, что так оно и есть, но я был всего лишь грубым принуждением примерно до +/- 100, поэтому я не был готов сказать, что он обязательно был лучшим, но теперь, когда я думаю об этом, я не вижу как это можно сделать лучше.
KSab
+1 очень приятно. Как я могу попробовать это? Какой питон? (Я не питонист, я просто случайно установил Python 3.4 на свой ноутбук).
edc65
@ edc65 Я добавил код, чтобы проверить его; также это использует Python 2.7, поэтому такие вещи, как операторы print, не будут работать с Python 3
KSab
Несмотря на то, что это стоит, я могу подтвердить, что этот результат является оптимальным: я попробовал решение грубой силы (действительно BFS), проверяя до длины 450 (и все еще работает). Те же результаты твои.
edc65
12

Ява, 5208 5240 5306 6152

Это рекурсивная функция, которая подходит ближе к цели, с базовыми случаями, когда она попадает в пределы 5 (что часто составляет всего один шаг).

В принципе, вы можете получить (a*b)+(a/2)для (a+b)*2палок с простым рисунком. Если aнечетно, результат будет отрицательным, что приводит к некоторой странной логике.

Это займет минуту или около того для 2 31 -1, с длиной 185,367 в результате. Тем не менее, он работает практически мгновенно для всех тестовых случаев. Это баллы 4*(sqrt|n|)в среднем. Самый длинный индивидуальный тестовый пример 9730, в результате которого получается стек флеш длиной 397:

|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||-|||||||||||||||||||||-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|--------------------------------------------------------------------------------------------------|-

Обновить:

Нашел более короткий способ сложения / вычитания из основного шаблона. Вернуться в лидеры (пока)!


С помощью жгута и тестовых случаев:

import static java.lang.Math.*;

public class StickStacker {

    public static void main(String[] args){
        StickStacker stacker = new StickStacker(); 
        int tests[] = {-8607,-6615,-6439,-4596,-4195,-1285,-72,12,254,1331,3366,3956,5075,5518,5971,7184,7639,8630,9201,9730};
        int sum = 0;
        for(int test : tests){
            String sticks = stacker.stickStack3(test);
            sum += sticks.length();
            System.out.println("In: " + test + "\t\tLength: " + sticks.length());
            System.out.println(sticks+"\n");
        }
        System.out.println("\n\nTotal: "+sum);          
    }

    String stickStack3(int n){return"|"+k(n);}
    String k(int n){
        String o="";
        int q=(int)sqrt(abs(n)),a,b,d=1,e=0,c=1<<30,
        z[]={232,170,42,10,2,0,12,210,52,844,212};
        a=n>0?q:-q;
        a-=n>0?a%2<1?0:1:a%2<0?0:-1;

        for(b=0;b<abs(a)+10;b++)
            if(abs(n-(a*b+a/2-(n>0?0:1)))<abs(a)&&abs(a)+b<c){
                    c=abs(a)+b;
                    d=a;e=b;
            }

        for(a=0;a++<e;)o+="-|";
        for(a=0;a++<abs(d);)o="|"+o+"-";

        c=n-(d*e+d/2-(n>0?0:1));
        if(c>0&&c<abs(d)){
            if(c%2==0)
                o=o.substring(0,c)+"-|"+o.substring(c);
            else
                o=o.substring(0,c+1)+"-|"+o.substring(c+1)+"|-";
            c=0;
        }else if(c<0&-c<abs(d)){
            if(c%2!=0)
                o=o.substring(0,-c)+"-|"+o.substring(-c);
            else
                o=o.substring(0,-c-1)+"-|"+o.substring(-c-1)+"|-";  
            c=0;
        }

        return n==0?"":n<6&&n>-6?
                Long.toBinaryString(z[n+5])
                .replaceAll("0","-")
                .replaceAll("1","|"):
                o+k(c);
    }
}

Будет ли гольф (больше) в маловероятном случае точного галстука.

Geobits
источник
Вы уверены, что набрали 2 ^ 31? Мой счет за 2 ^ 30 составляет 131099, а 185369 за 2 ^ 31-1.
edc65
@ edc65 Я, должно быть, набрал его неправильно. Я думал, что это кажется немного низким ... В любом случае, спасибо, что заметили и дали немного конкуренции. Теперь пришло время посмотреть, смогу ли я сделать лучше :)
Geobits
4

JavaScript (ES6) 5296 6572

Редактировать Как я уже говорил в своем объяснении, я не очень хорошо решаю целочисленные уравнения. Мое предположение о значении b было не очень хорошим, поэтому я расширил диапазон значений, которые нужно попробовать. И (вау) я сейчас веду.

Редактировать 2 Исправление ошибки, те же результаты. У меня есть идея, но я не могу ее закрепить.

Байт: ~ 460, вполне гольф. Он работает на 32-битных целых числах, время выполнения около 0.

Код представляет собой функцию F (скрыт во фрагменте) ниже.
Запустите фрагмент для проверки (в FireFox).

объяснение

Положительные числа, для начала. Начните с "базы" (попробуйте в CJam, если хотите, пробелы разрешены)

| gives 0  
||| -- gives 1
||||| ---- gives 2
||||||| ------ gives 3 

Резюме: 1 палка, затем b * 2 палочки, затем b * 2 тире

Затем попробуйте добавить один или несколько '- |' в середине раскола. Каждый из них добавляет фиксированный прирост, который в два раза превышает начальную базу и может повторяться много раз. Итак, у нас есть формула с b = base и r = инкрементный коэффициент повторения

v=b+r*2*b

b=1, r=0 to 3, inc=2
| || -- 1 
| || -| -- 3 
| || -| -| -- 5 
| || -| -| -| -- 7

b=3, r=0 to 3, inc=6
| |||||| ------ 3
| |||||| -| ------ 9
| |||||| -| -| ------ 15
| |||||| -| -| -| ------ 21

Видеть? Значение addes быстро увеличивается, и каждое добавление по-прежнему составляет всего 2 символа. Базовый прирост дает еще 4 символа каждый раз.

Учитывая v и нашу формулу v = b + r * 2 * b, нам нужно найти 2 целых числа b и r. Я не эксперт в такого рода уравнениях, но b = int sqrt (v / 2) - хорошее начальное предположение.

Тогда у нас есть r и b, которые вместе дают значение около v. Мы достигаем v точно с повторным увеличением (|| -) или уменьшением (| -).

Следуйте тому же рассуждению для отрицательных чисел, увы формула похожа, но не равна.

edc65
источник
1

JavaScript, 398710

94 байта / символы кода

Я придумал решение! ... а затем прочитайте ответ Спарра, и он был точно таким же.

Подумал, что я все равно опубликую, так как js допускает немного меньшее число символов.

Вот незавершенная версия кода:

function p(a){
    s = "";
    if(a<=0){
        for(i=0; i<-2*a-1;i++)
            s="|"+s+"-";
        return "|"+s;
    }
    return "|"+p(0-a)+"-";
}
Нейт Янг
источник
1
хорошо, если мы играем в гольф решения 398710, игра! кто-то может пройти через cjam или pyth и победить нас обоих :(
Спарр
1

Python, 398710 (71 байт)

Я думаю, самое простое решение. Использует 4 * n (+/- 1) символа стика для представления n.

def s(n):return'|'*(n*2+1)+'-'*n*2 if n>=0 else'|'*(n*-2)+'-'*(n*-2-1)
Sparr
источник