Oświadczenie: chociaż od jakiegoś czasu jestem na tej stronie w celach rozrywkowych, to jest moje pierwsze pytanie, więc proszę wybaczyć wszelkie drobne błędy.

tło

Przydzielając nam pracę domową, mój nauczyciel jest naprawdę denerwujący i zapisuje wszystkie problemy, które musimy zrobić indywidualnie. W związku z tym na zawsze zajmuje mi zapisywanie , które problemy muszę zrobić. Pomyślałem, że moje życie będzie łatwiejsze, wyślę mu program, który sprawi, że lista problemów zajmie mniej miejsca.

Zapisując listę numerów stron lub problemów, używamy myślnika do oznaczenia zakresu. Na przykład 19-21staje się 19, 20, 21. Jeśli pomiędzy nimi jest przerwa, używane są dwa przedziały oddzielone przecinkami: 19-21, 27-31staje się 19, 20, 21, 27, 28, 29, 30, 31.
W tej chwili prawdopodobnie myślisz: „wydaje się to dość trywialne”. W rzeczywistości na to pytanie zostało już udzielone tu i tutaj .

Istnieje jednak pewien haczyk. Jeśli mamy zakres z jednakowymi kolejnymi cyframi, powtarzające się cyfry można pominąć. Na przykład: 15, 16, 17staje się 15-7i 107, 108, 109staje 107-9. W przypadku premii, jeśli ostatnia z kolei równa cyfra jest o 1 większa, a ostatnia cyfra górnego limitu jest mniejsza lub równa cyfrze dolnej, można pominąć następujące (przepraszam, jeśli zabrzmiało to myląco; być może niektóre przykłady to wyjaśnią) . 109-113staje się 109-3, ponieważ ostatnia ostatnia cyfra oznacza zwiększenie miejsca 10.

Wyzwanie

Twój program powinien pobierać listę liczb całkowitych poprzez dane wejściowe (cokolwiek jest standardowe dla twojego języka lub funkcji). Możesz zdecydować, czy ta lista jest rozdzielana przecinkami, spacjami, czy jako rzeczywista lista / tablica.

Wyprowadzaj najkrótszą drogę (najpierw posortowaną według liczby zakresów, a następnie sumy znaków zawartych w zakresach), aby przedstawić tę listę za pomocą tej notacji. Każdy zakres przerywany musi znajdować się w tym samym wierszu, ale zakresy można oddzielić przecinkami lub znakami nowej linii (dozwolone są znaki końca linii lub przecinków). Te zakresy muszą być w porządku.

Ponieważ nasza szkolna sieć Wi-Fi jest okropna , muszę zminimalizować plik, aby go wysłać. Najkrótszy kod (w bajtach) wygrywa.

Bonusy

Mój nauczyciel jest niechlujny, więc jest kilka rzeczy, które mogłyby mu pomóc. Wiele premii kumuluje się poprzez pomnożenie, np. Premia -10% (x 90%) i premia -25% (x 75%) = 90% * 75% = x 67,5% (premia -32,5%).

• Czasami układa je w niewłaściwej kolejności (nie jest nauczycielem matematyki). Zdobądź premię -20%, jeśli twój program może przyjmować liczby całkowite, które nie są sortowane od najmniej do największej.
• Nasza książka jest dziwna i każda sekcja zaczyna liczyć problemy od -10. Jeśli twój program akceptuje liczby ujemne, weź -25%.
• Jeśli zaakceptuje bonus niższej ostatniej cyfry, zwiększając miejsce 10, np. 25-32Zmniejszając do 25-2, weź bonus -50%.

Przypadki testowe

In:  1, 2, 3, 4, 5
Out: 1-5

In:  3, 4, 5, 9, 10, 11, 12
Out: 3-5, 9-12

In:  149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160
Out: 149-60

In: 1 2 3 4
Out: 1-4


For bonuses:

In: 109, 110, 111, 112, 113
Out: 109-3

In:  19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29
Out: 19-9

In: -3, -2, -1, 0, 1, 2
Out: -3-2

In: -3, -2, -1
Out: -3--1

Odpowiedź zostanie zaakceptowana w sobotę, 19 grudnia 2015 r.

GLHF!

LabVIEW, 97 * 0,8 * 0,75 * 0,5 = 29,1 Prymitywy LabVIEW

działa to poprzez zliczanie w górę, jeśli kolejne elementy są od siebie oddalone o 1, a następnie tworzy ciąg z liczby i liczby - liczba modulo 10, a niektóre mnożenie powodujące negatywy są suką.

Gif pokazuje wejście 8,9,10,11i wyjście 8-1. Do wejścia -5,-4,-3,1,3,4,5 -5--3,1,3-5wychodzi.

C ++ 11, 451 * 80% * 75% * 50% = 135,3 bajtów

Zaoszczędzono 9 bajtów dzięki @ kirbyfan64sos.

Zaoszczędź 19 bajtów dzięki @JosephMalle i @cat.

Zaoszczędź 11 bajtów dzięki @ pinkfloydx33.

#include<vector>
#include<cmath>
#include<algorithm>
#include<string>
#define T string
#define P append
using namespace std;T f(vector<int>v){sort(v.begin(),v.end());T r=to_T(v[0]);int b=1;int m=v[0];for(int i=1;i<=v.size();i++){if(i!=v.size()&&v[i]==v[i-1]+1){if(!b){m=v[i-1];}b=1;}else{if(b){T s=to_T(v[i-1]);r.P("-").P(s.substr(s.size()-(v[i-1]-m==1?1:log10(v[i-1]-m)),s.size()));}if(i!=v.size()){r.P(", ").P(to_T(v[i]));}b=0;}}return r;}

To kwalifikuje się do wszystkich bonusów.

Przykładowy test parametru i wynik:

In:  [1, 2, 3, 4, 5]
Out: 1-5

In:  [3, 4, 5, 9, 10, 11, 12]
Out: 3-5, 9-12

In:  [149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160]
Out: 149-60

In:  [1, 2, 3, 4]
Out: 1-4

In:  [109, 110, 111, 112, 113]
Out: 109-3

In:  [19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]
Out: 19-9

Rubin, 120, 118 * 0,8 * 0,75 * 0,5 = 35,4 bajtów

Pobiera na wejściu argumenty wiersza poleceń (przecinki są w porządku); wypisuje jeden zakres na linię na standardowe wyjście.

c=(b=(a=$*.map(&:to_i).sort).map &:succ)-a
puts (a-b).map{|m|(m<n=c.shift-1)?"#{m}-#{m<0?n:n%10**"#{n-m-1}".size}":m}

Z białymi znakami / komentarzami:

c=(
  b=(
    # a is the sorted input
    a=$*.map(&:to_i).sort
  # b is the set of successors of elements of a
  ).map &:succ
# c=b-a is the set of not-quite-least upper bounds of our ranges
)-a

# a-b is the set of greatest lower bounds of our ranges
puts (a-b).map {|m|
  # for each range [m,n], if there are multiple elements
  (m < n = c.shift-1) ?
    # yield the range, abbreviating n appropriately if positive
    "#{m}-#{m<0 ? n : n % 10 ** "#{n-m-1}".size}" :
    # in the one-element case, just yield that
    m
}

Przypadki testowe

$ ruby homework.rb 1, 2, 3, 4, 5
1-5

$ ruby homework.rb 3, 4, 5, 9, 10, 11, 12
3-5
9-2

$ ruby homework.rb 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160
149-60

$ ruby homework.rb 1 2 3 4
1-4

$ ruby homework.rb 109, 110, 111, 112, 113
109-3

$ ruby homework.rb 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29
19-9

Funkcje nieobjęte przypadkami testowymi

Nieuporządkowane dane wejściowe i zakresy jednoelementowe:

$ ruby homework.rb 2 17 19 22 0 1 8 20 18
0-2
8
17-0
22

Zakresy ujemne (nie można w nich skrócić większej liczby):

$ ruby homework.rb -17 -18 -19 -20 -21
-21--17

Skrót dowolnej liczby cyfr (tutaj do wprowadzania danych używa się zwykłego rozszerzenia bash):

$ ruby homework.rb {1234567..1235467} 2345999 2346000 2346001
1234567-467
2345999-1

JavaScript ES6, 229 * 80% * 75% * 50% = 68,7 bajtów

Wejście testowe

Korzystam z następujących danych testowych:

var A1=[
  5,6,7,            // => 5-7     # (a) group pages 
  2,3,              // => 2-3,5-7 # (b) must be properly sorted
  -9,-8,-7,         // => -10--8  # (c) allow negative numbers
  29,30,31,32,      // => 29-2    # (d) lower last digit implies increasing the 10s place
  9,10,11,12,       // => 9-11    # NOT 9-2
  36,37,38,39,40,41,42,43,44,45,46,47, 
                    // => 36-47   # NOT 36-7
  99,100,101,102,   // => 99-102  # NOT 99-2
  109,110,111,112,  // => 109-2   # NOT 109-12
],
// more tests, not specified in the question
A2=[
  120,124,       // => 120,124 # (e) handle single pages
],
A3=[
  135,136,135    // => 135-6   # (f) handle duplicates
];

Podstawowy: 229 bajtów

Ta wersja spełnia wymagania pytania (a) ze wszystkimi bonusami (c, d, e), ale zawiesza się na pojedynczych stronach. Może także obsługiwać duplikaty (f). Obsługuje strony ujemne do -10 000, które można łatwo zwiększyć przy (dużej) utracie prędkości.

F=(a)=>{var R=[],i=NaN,l,u;a.map(x=>R[1e4+x]=x);R.concat('').map(x=>(i!=i&&(l=x,u=l-1),i=0,u=(x+="")-u-1?l=console.log(l+'-'+(u>0?(l.length-u.length||(z=>{for(;l[i]==u[i];i++);})(),u.length-i-2||u-l>9||i++,u.slice(i)):u))||x:x))}
F(A1.concat(A3)) --> -9--7 2-3 5-7 9-12 29-2 36-47 99-102 109-2 135-136

(Powyższe dane wyjściowe pokazują spacje zamiast rzeczywistych nowych linii dla zwięzłości)

Pojedyncze strony: 233 bajty

Ta nieco dłuższa wersja dodatkowo spełnia wymagania (e) i wyświetla pojedyncze strony jako zakres z jednakowymi dolnymi i górnymi granicami

G=(a)=>{var R=[],i=NaN,l,u;a.map(x=>R[1e4+x]=x);R.concat('').map(x=>(i!=i&&(l=x,u=l-1),i=0,u=(x+="")-u-1?l=console.log(l+'-'+(u-l&u>0?(l.length-u.length||(z=>{for(;l[i]==u[i];i++);})(),u.length-i-2||u-l>9||i++,u.slice(i)):u))||x:x))}
G(A1.concat(A2,A3)) --> -9--7 2-3 5-7 9-12 29-2 36-47 99-102 109-2 120-120 124-124

GAP , 355 bajtów * 0,8 * 0,75 * 0,5 = 106,5

Spełnia to wszystkie bonusy. Kosztowało mnie prawie 100 dodatkowych bajtów, aby wszystko działało ładnie. Ta funkcja pomija cyfry wiodące tylko wtedy, gdy odstęp nie przepełnia się raz na miejscu. Na przykład 9 10 11wyjścia, 9-1ale 9 10 11 12 .. 20 21wyjścia 9-21.

Gdyby GAP był nieco mniej gadatliwy, mógłbym to zrobić bardzo krótko (również zaoszczędziłbym wiele bajtów, gdyby nie przestrzegał dokładnej składni.) Prawdopodobnie spróbuję zagrać w golfa nieco trudniej jutro. Zobacz poniżej przypadki testowe.

g:=function(l)local n;if not l=[] then Sort(l);n:=1;while not l=[] do;if not IsSubset(l,[l[1]..l[1]+n]) then if not n=1 then if n-1>10-l[1] mod 10 and n-1<11 then Print(l[1],"-",(l[1]+n-1) mod 10);else Print(l[1],"-",l[1]+n-1);fi;else Print(l[1]);fi;Print(", ");SubtractSet(l,[l[1]..l[1]+n-1]);g(l);fi;n:=n+1;od;fi;Print("\b\b  ");end; 

bez golfa:

g:=function(l)
    local n;
    if not l=[] then
        Sort(l);
        n:=1;
        while not l=[] do;
            if not IsSubset(l,[l[1]..l[1]+n]) then
                if not n=1 then
                    if n-1>10-l[1] mod 10 and n-1<11 then
                        Print(l[1],"-",(l[1]+n-1) mod 10);
                    else
                        Print(l[1],"-",l[1]+n-1);
                    fi;
                else
                    Print(l[1]);
                fi;
                Print(", ");
                SubtractSet(l,[l[1]..l[1]+n-1]);
                g(l);
            fi;
            n:=n+1;
        od; 
    fi;
    Print("\b\b  ");
end;

Zauważ, że w składni GAP [a..b]jest równoważne z [a,a+1,...,b]. Uważam, że te przypadki testowe pokazują, że ten program spełnia wszystkie wymagania. Jeśli coś jest nie tak, daj mi znać.

gap> h([1..5]);
1-5  
gap> h([3,4,5,9,10,11,12]);
3-5, 9-2  
gap> h([149..160]);
149-160  
gap> h([109..113]);
109-3  
gap> h([19..29]);
19-9  

gap> h([-1,-2,-3,-7,-20000,9,10,110101,110102]);
-20000, -7, -3--1, 9-10, 110101-110102  

gap> h([10101,10102,10103,10,11,12,13,14,15,16,234,999,1000,1001,1002]);
10-16, 234, 999-2, 10101-10103  

Lua, 322 * 80% * 75% * 50% = 96,6 Bajtów

Wreszcie zakończono z 3 wyzwaniami, wyniki poniżej 100 bajtów: D

Grał w golfa

function f(l)table.sort(l)l[#l+1]=-13 a=l[1]t,s=a,"" for _,v in next,l do if v-t>1 or t-v>1 then s,p,r=s..a.."-",""..t,""..a r:gsub("%d",function(c)p=r:find(c)~=r:len()and p:gsub("^(-?)"..c,"%1")or p r=r:gsub("^"..c,"")end)p=t-a<10 and t%10<a%10 and p:gsub("^(%d)","")or p s,a,t=s..p..",",v,v else t=v end end return s end

Bez golfa

function f(l)
    table.sort(l)
    l[#l+1]=-13 
    a=l[1] 
    t,s=a,"" 
    for _,v in next,l 
    do
        if v-t>1 or t-v>1
        then
            s,p,r=s..a.."-",""..t,""..a
            r:gsub("%d",function(c)
                p=r:find(c)~=#r and p:gsub("^(-?)"..c,"%1")or p
                r=r:gsub("^"..c,"")
            end)
            p=t-a<10 and t%10<a%10 and p:gsub("^(%d)","")or p
            s=s..p..","
            a,t=v,v
        else
            t=v
        end
    end
return s
end

Możesz przetestować lua online , aby zobaczyć, jak działa na testach, skopiuj wklej funkcję, a następnie ten kod:

a={1,2,3,4,5}
b={3,4,5,9,10,11,12,13,14,15,16,17,18,19,20,21}
c={149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160}
d={-7,8,5,-6,-5,6,7}
print(f(a))
print(f(b))
print(f(c))
print(f(d))

Java, 252 * 80% * 75% * 50% = 75,6 bajtów

Zdecydowałem się na metodę (jest znacznie mniejsza w Javie), oto wersja golfowa:

Grał w golfa

int p,c,s;String m(int[]a){p=s=c=0;c--;String o="";Arrays.sort(a);for(int n:a){if(s==0)o+=s=n;else if(n-p==1)c++;else{o+=t()+", "+(s=n);c=-1;}p=n;}return o+t();}String t(){return c>=0?"-"+(""+p).substring((""+Math.abs(p)).length()-(""+c).length()):"";}

A oto czytelna wersja:

int p, c, s;

String m(int[] a) {
    p = s = c = 0;
    c--;
    String o = "";
    Arrays.sort(a);
    for (int n : a) {
        if (s == 0)
            o += s = n;
        else if (n - p == 1)
            c++;
        else {
            o += t() + ", " + (s = n);
            c = -1;
        }
        p = n;
    }
    return o + t();
}

String t() {
    return c >= 0 ? "-" + ("" + p).substring(("" + Math.abs(p)).length() - ("" + c).length()) : "";
}

Po przetestowaniu są to wyniki:

import java.util.Arrays;
public class A {
    public static void main(String...s) {
        A a = new A();
        System.out.println(a.m(new int[] {1, 2, 3, 4, 5}));
        System.out.println(a.m(new int[] {3, 4, 5, 9, 10, 11, 12}));
        System.out.println(a.m(new int[] {149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160}));
        System.out.println(a.m(new int[] {109, 110, 111, 112, 113}));
        System.out.println(a.m(new int[] {19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29}));
        System.out.println(a.m(new int[] {1,10,11,16}));
        System.out.println(a.m(new int[] {-3,-2,-1,0,1,2,3}));
        System.out.println(a.m(new int[] {-3,-2,-1}));
    }

    int p,c,s;String m(int[]a){p=s=c=0;c--;String o="";Arrays.sort(a);for(int n:a){if(s==0)o+=s=n;else if(n-p==1)c++;else{o+=t()+", "+(s=n);c=-1;}p=n;}return o+t();}String t(){return c>=0?"-"+(""+p).substring((""+Math.abs(p)).length()-(""+c).length()):"";}
}

Wydajność:

1-5
3-5, 9-2
149-60
109-3
19-9
1, 10-1, 16
-3-3
-3--1

Aktualizacja:

Może teraz obsługiwać również liczby ujemne, zwiększając premię.

Japt, 127 bajtów * 80% * 75% * 50% = 38,1

Wow, to było jedno wyzwanie, które obejmowało wszystkie bonusy. Prawdopodobnie można go skrócić.

D=[]N=Nn-;DpNr@Y-1¥Xg1 ?[Xg Y]:DpX ©[YY]}D;Ds1 £[BC]=Xms;B¥C?B:B+'-+CsBg ¦'-©Cl ¥Bl ©C¬r@B¯Z ¥C¯Z ªC-B§ApCl -Z ©ÂBsX <ÂCsX ?Z:X

Wypróbuj online!

Jak to działa

Wyjaśnienie jest bardzo szorstkie; nie wahaj się zadawać pytań.

/*    Setting up basic variables    */
                      // Implicit: A = 10, N = list of input numbers.
D=[],N=Nn-;           // D = empty array, N = N sorted by subtraction.

/*    Finding ranges of page numbers    */    
Dp                    // Push into D the result of
NrXYZ{                // reducing each previous value X and item Y in N by this function,
}[];                  // starting with an empty array:
 Y-1==Xg1 ?           //  If Y is 1 more than the second item of X,
 [Xg Y]:              //   return [X[0], Y].
 DpX &&[YY]           //  Otherwise, push X into D and return [Y, Y].

/*    Formatting result    */
Ds1 mXYZ{             // Take the first item off of D and map each item X by this function:
 [BC]=Xms;            //  Set B and C to the first to items in X as strings.
 B==C?B               //  If B is the same as C, return B.
 :B+'-+Cs             //  Otherwise, return B + a hyphen + C.slice(
  Bg !='-&&           //   If B[0] is not a hyphen (B is not negative), AND
  Cl ==Bl &&          //   B and C are the same length,

  /*    Cutting off unnecessary digits    */
  Cq r                //    then C split into digits, reduced with
  rXYZ{               //    each previous value X, item Y, and index Z mapped by this function:
   Bs0,Z ==Cs0,Z ||   //     If B.slice(0,Z) equals C.slice(0,Z), OR
   C-B<=ApCl -Z       //     C - B <= 10 to the power of (C.length - Z);
   &&~~BsX <~~CsX     //     AND B.slice(X) is a smaller number than C.slice(X),
   ?Z:X               //     then Z; otherwise, X.
                      //   Otherwise, 0.

R, 167 bajtów x 80% x 75% x 50% -> 50,1

s=sort(scan(se=","));r=c();while(length(s)){w=s==1:length(s)+s[1]-1;x=s[w];s=s[!w];z=tail(x,1);r=c(r,paste0(x[1],"-",ifelse(z-x[1]<=10,z%%10,z%%100)))};cat(r,sep=", ")

Wcięte, z nowymi liniami:

s=sort(scan(se=","))
r=c()
while(length(s)){
w=s==1:length(s)+s[1]-1
x=s[w]
s=s[!w]
z=tail(x,1)
r=c(r, paste0(x[1],"-", ifelse(z-x[1]<=10, 
                               z%%10,
                               z%%100)))}
cat(r,sep=", ")

Przypadki testowe:

> s=sort(scan(se=","));r=c();while(length(s)){w=s==1:length(s)+s[1]-1;x=s[w];s=s[!w];r=c(r,paste0(x[1],"-",ifelse(tail(x,1)-x[1]<=10,tail(x,1)%%10,tail(x,1)%%100)))};cat(r,sep=", ")
1: 3, 4, 5, 9, 10, 11, 12
8: 
Read 7 items
3-5, 9-2
> s=sort(scan(se=","));r=c();while(length(s)){w=s==1:length(s)+s[1]-1;x=s[w];s=s[!w];r=c(r,paste0(x[1],"-",ifelse(tail(x,1)-x[1]<=10,tail(x,1)%%10,tail(x,1)%%100)))};cat(r,sep=", ")
1: 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160
13: 
Read 12 items
149-60

Działa dla bonusu -50%:

> s=sort(scan(se=","));r=c();while(length(s)){w=s==1:length(s)+s[1]-1;x=s[w];s=s[!w];r=c(r,paste0(x[1],"-",ifelse(tail(x,1)-x[1]<=10,tail(x,1)%%10,tail(x,1)%%100)))};cat(r,sep=", ")
1: 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29
12: 
Read 11 items
19-9
> s=sort(scan(se=","));r=c();while(length(s)){w=s==1:length(s)+s[1]-1;x=s[w];s=s[!w];r=c(r,paste0(x[1],"-",ifelse(tail(x,1)-x[1]<=10,tail(x,1)%%10,tail(x,1)%%100)))};cat(r,sep=", ")
1: 109, 110, 111, 112, 113
6: 
Read 5 items
109-3

Akceptuje nieposortowane dane wejściowe:

> s=sort(scan(se=","));r=c();while(length(s)){w=s==1:length(s)+s[1]-1;x=s[w];s=s[!w];r=c(r,paste0(x[1],"-",ifelse(tail(x,1)-x[1]<=10,tail(x,1)%%10,tail(x,1)%%100)))};cat(r,sep=", ")
1: 114, 109, 110, 111, 112, 113
7: 
Read 6 items
109-4

Akceptuje liczby ujemne:

> s=sort(scan(se=","));r=c();while(length(s)){w=s==1:length(s)+s[1]-1;x=s[w];s=s[!w];r=c(r,paste0(x[1],"-",ifelse(tail(x,1)-x[1]<=10,tail(x,1)%%10,tail(x,1)%%100)))};cat(r,sep=", ")
1: -1,0,1,2
4: 
Read 3 items
-1-2

sh, 135 * .8 * .75 * .5 = 40,5

tr , \\n|sort -n|awk -vORS="" '$1-o>1||!c{print p c$1;s=$1}{o=$1;c=", ";p=""}o>s{p="-"substr(o,length(o)-length(o-s-1)+1)}END{print p}'

Skrypt powłoki

tr , \\n|           # comma separated -> newline separated
sort -n|            # sort
awk -vORS=""        # suppress automatic newlines in output

skrypt awk

# on step > 1 or first run, end the current sequence and start a new one.
# on first run, p and c are empty strings.
$1-o>1||!c
    {print p c$1;s=$1}

# old = current, c = ", " except for first run, clear end string.
    {o=$1;c=", ";p=""}

# if the sequence is not a single number, its end is denoted by "-o".
# print only the last n digits of o.
o>s
    {p="-"substr(o,length(o)-length(o-s-1)+1)}

# end the current sequence without starting a new one.
END
    {print p}'

gdzie sjest początkiem bieżącej sekwencji i opoprzednią wartością wejściową.