From Asbjørn, 3 Years ago, written in Delphi (Object Pascal).
Embed
  1. program RangeCombo;
  2.  
  3. {$APPTYPE CONSOLE}
  4.  
  5. {$R *.res}
  6.  
  7. uses
  8.   System.SysUtils, System.Math, System.StrUtils, Generics.Defaults, Generics.Collections;
  9.  
  10. type
  11.   Func<TResult> = reference to function(): TResult;
  12.   Func<T, TResult> = reference to function(const Arg1: T): TResult;
  13.   Func<T1, T2, TResult> = reference to function(const Arg1: T1; const Arg2: T2): TResult;
  14.   Func<T1, T2, T3, TResult> = reference to function(const Arg1: T1; const Arg2: T2; const Arg3: T3): TResult;
  15.  
  16.   // various algorithms
  17.   Alg = record
  18.     class function Aggregate<T, TAccumulate>(const Input: TArray<T>; const F: Func<TAccumulate, T, TAccumulate>): TAccumulate; overload; static;
  19.     class function Aggregate<T, TAccumulate>(const Input: TArray<T>; const InitialValue: TAccumulate; const F: Func<TAccumulate, T, TAccumulate>): TAccumulate; overload; static;
  20.     class function Distinct<T>(const Input: TArray<T>): TArray<T>; static;
  21.     class function Sort<T>(const Input: TArray<T>): TArray<T>; overload; static;
  22.     class function Transform<T>(const Input: TArray<T>; const F: Func<T, T>): TArray<T>; overload; static;
  23.     class function Transform<T, TResult>(const Input: TArray<T>; const F: Func<T, TResult>): TArray<TResult>; overload; static;
  24.   end;
  25.  
  26.  
  27. { Alg }
  28.  
  29. class function Alg.Aggregate<T, TAccumulate>(const Input: TArray<T>;
  30.   const F: Func<TAccumulate, T, TAccumulate>): TAccumulate;
  31. begin
  32.   result := Aggregate<T, TAccumulate>(Input, Default(TAccumulate), F);
  33. end;
  34.  
  35. class function Alg.Aggregate<T, TAccumulate>(const Input: TArray<T>;
  36.   const InitialValue: TAccumulate;
  37.   const F: Func<TAccumulate, T, TAccumulate>): TAccumulate;
  38. var
  39.   elm: T;
  40. begin
  41.   result := InitialValue;
  42.   for elm in Input do
  43.   begin
  44.     result := F(result, elm);
  45.   end;
  46. end;
  47.  
  48. class function Alg.Distinct<T>(const Input: TArray<T>): TArray<T>;
  49. var
  50.   dict: TDictionary<T, integer>;
  51.   isPresent: boolean;
  52.   i, j: NativeInt;
  53. begin
  54.   dict := nil;
  55.   try
  56.     dict := TDictionary<T, integer>.Create;
  57.  
  58.  
  59.     SetLength(result, Length(Input));
  60.  
  61.     j := 0;
  62.     for i := 0 to High(Input) do
  63.     begin
  64.       isPresent := dict.ContainsKey(Input[i]);
  65.       if (isPresent) then
  66.         continue;
  67.  
  68.       dict.Add(Input[i], 1);
  69.  
  70.       result[j] := Input[i];
  71.       j := j + 1;
  72.     end;
  73.  
  74.     SetLength(result, j);
  75.   finally
  76.     dict.Free;
  77.   end;
  78. end;
  79.  
  80. class function Alg.Sort<T>(const Input: TArray<T>): TArray<T>;
  81. begin
  82.   result := Copy(Input);
  83.   TArray.Sort<T>(result, TComparer<T>.Default);
  84. end;
  85.  
  86. class function Alg.Transform<T, TResult>(const Input: TArray<T>;
  87.   const F: Func<T, TResult>): TArray<TResult>;
  88. var
  89.   i: NativeInt;
  90. begin
  91.   SetLength(result, Length(Input));
  92.   for i := 0 to High(Input) do
  93.     result[i] := F(Input[i]);
  94. end;
  95.  
  96. class function Alg.Transform<T>(const Input: TArray<T>; const F: Func<T, T>): TArray<T>;
  97. var
  98.   i: NativeInt;
  99. begin
  100.   SetLength(result, Length(Input));
  101.   for i := 0 to High(Input) do
  102.     result[i] := F(Input[i]);
  103. end;
  104.  
  105.  
  106. type
  107.   Functional = record
  108.   public
  109.     type BindArg1 = record end;
  110.     type BindArg2 = record end;
  111.   public
  112.     class function Bind<T1, T2, T3, TResult>(const f: Func<T1, T2, T3, TResult>; const Arg1: BindArg1; const Arg2: T2; const Arg3: T3): Func<T1, TResult>; overload; static;
  113.   end;
  114.  
  115. const _1: Functional.BindArg1 = ();
  116. const _2: Functional.BindArg2 = ();
  117.  
  118. { Functional }
  119.  
  120. class function Functional.Bind<T1, T2, T3, TResult>(const f: Func<T1, T2, T3, TResult>; const Arg1: BindArg1;
  121.   const Arg2: T2; const Arg3: T3): Func<T1, TResult>;
  122. begin
  123.   result :=
  124.     function(const Arg1: T1): TResult
  125.     begin
  126.       result := f(Arg1, Arg2, Arg3);
  127.     end;
  128. end;
  129.  
  130.  
  131.  
  132. type
  133.   Range = record
  134.     First: integer;
  135.     Last: integer;
  136.  
  137.     class operator Implicit(const Value: integer): Range;
  138.     class function FromString(const Str: string): Range; static;
  139.  
  140.     class function ToString(const R: Range): string; overload; static;
  141.     function ToString(): string; overload;
  142.   end;
  143.  
  144. function IsSingularRange(const R: Range): boolean;
  145. begin
  146.   result := (R.First = R.Last);
  147. end;
  148.  
  149. { Range }
  150.  
  151. class function Range.FromString(const Str: string): Range;
  152. var
  153.   elms: TArray<string>;
  154. begin
  155.   elms := Str.Split(['-']);
  156.  
  157.   case Length(elms) of
  158.     1: begin
  159.       result := elms[0].ToInteger();
  160.     end;
  161.     2: begin
  162.       result.First := elms[0].ToInteger();
  163.       result.Last := elms[1].ToInteger();
  164.     end;
  165.   else
  166.     raise EArgumentException.CreateFmt('Invalid range: "%s"', [Str]);
  167.   end;
  168. end;
  169.  
  170. class operator Range.Implicit(const Value: integer): Range;
  171. begin
  172.   result.First := Value;
  173.   result.Last := Value;
  174. end;
  175.  
  176. class function Range.ToString(const R: Range): string;
  177. begin
  178.   result := R.ToString();
  179. end;
  180.  
  181. function Range.ToString: string;
  182. begin
  183.   result := First.ToString();
  184.   if (not IsSingularRange(Self)) then
  185.     result := result + '-' + Last.ToString();
  186. end;
  187.  
  188.  
  189.  
  190. function CombineRanges(const Input: TArray<integer>): TArray<Range>;
  191. var
  192.   sortedInput: TArray<integer>;
  193. begin
  194.   sortedInput := Alg.Sort<integer>(Input);
  195.  
  196.   result := Alg.Aggregate<integer, TArray<Range>>(sortedInput,
  197.     function(const Accumulator: TArray<Range>; const Value: integer): TArray<Range>
  198.     var
  199.       r: Range;
  200.     begin
  201.       if (Length(Accumulator) = 0) then
  202.       begin
  203.         result := [Value];
  204.         exit;
  205.       end;
  206.  
  207.       r := Accumulator[High(Accumulator)];
  208.  
  209.       if (Value > (r.Last + 1)) then
  210.       begin
  211.         // need a new range
  212.         result := Accumulator + [Value];
  213.       end
  214.       else
  215.       begin
  216.         // extend last range
  217.         result := Accumulator;
  218.         result[High(result)].Last := System.Math.Max(r.Last, Value);
  219.       end
  220.     end
  221.   );
  222. end;
  223.  
  224. function ExpandRanges(const Input: TArray<Range>): TArray<integer>;
  225. begin
  226.   result := Alg.Sort<integer>(
  227.     Alg.Distinct<integer>(
  228.       Alg.Aggregate<Range, TArray<integer>>(Input,
  229.         function(const Accumulator: TArray<integer>; const Value: Range): TArray<integer>
  230.         var
  231.           i: integer;
  232.         begin
  233.           result := Accumulator;
  234.           for i := Value.First to Value.Last do
  235.           begin
  236.             result := result + [i];
  237.           end;
  238.         end
  239.       )
  240.     )
  241.   );
  242. end;
  243.  
  244. var
  245.   input: TArray<integer>;
  246.   ranges: TArray<Range>;
  247.   rangesStr: string;
  248.   values: TArray<integer>;
  249.   valuesStr: string;
  250.  
  251. begin
  252.   input := [1,2,3,4,6,7,8,13,14];
  253.  
  254.   try
  255.     ranges := CombineRanges(input);
  256.  
  257.     rangesStr := string.Join(
  258.       ', ',
  259.       Alg.Transform<Range, string>(
  260.         ranges,
  261.         Range.ToString
  262.       )
  263.     );
  264.  
  265.     WriteLn(rangesStr);
  266.  
  267.     WriteLn;
  268.     WriteLn;
  269.  
  270.  
  271.     rangesStr := '3, 13-16, 15 - 17, 1';
  272.  
  273.  
  274.     ranges := Alg.Transform<string, Range>(
  275.       Alg.Transform<string, string>(
  276.         rangesStr.Split([',']), // split all range elements
  277.         Functional.Bind<string, string, string, string>(ReplaceStr, _1, ' ', '') // remove any spaces
  278.       ),
  279.       Range.FromString
  280.     );
  281.  
  282.     values := ExpandRanges(ranges);
  283.  
  284.     valuesStr := string.Join(
  285.       ', ',
  286.       Alg.Transform<integer, string>(
  287.         values,
  288.         integer.ToString
  289.       )
  290.     );
  291.  
  292.     WriteLn(valuesStr);
  293.  
  294.   except
  295.     on E: Exception do
  296.       Writeln(E.ClassName, ': ', E.Message);
  297.   end;
  298.   WriteLn;
  299.   WriteLn('done');
  300.   ReadLn;
  301. end.

captcha