17
\$\begingroup\$

Problem

Let's define a generalized Cantor set by iteratively deleting some rational length segments from the middle of all intervals that haven't yet been deleted, starting from a single continuous interval.

Given the relative lengths of segments to delete or not, and the number of iterations to do, the problem is to write a program or function that outputs the relative lengths of the segments that have or have not been deleted after n iterations.

Example 3,1,1,1,2

Example: Iteratively delete the 4th and 6th eighth

Input:

n – number of iterations, indexed starting from 0 or 1

l – list of segment lengths as positive integers with gcd(l)=1 and odd length, representing the relative lengths of the parts that either stay as they are or get deleted, starting from a segment that doesn't get deleted. Since the list length is odd, the first and last segments never get deleted. For example for the regular Cantor set this would be [1,1,1] for one third that stays, one third that gets deleted and again one third that doesn't.

Output:

Integer list o, gcd(o)=1, of relative segment lengths in the nth iteration when the segments that weren't deleted in the previous iteration are replaced by a scaled down copy of the list l. The first iteration is just [1]. You can use any unambiguous output method, even unary.

Examples

n=0, l=[3,1,1,1,2] →                 [1]
n=1, l=[3,1,1,1,2] →     [3,    1,    1,    1,    2]
n=2, l=[3,1,1,1,2] → [9,3,3,3,6,8,3,1,1,1,2,8,6,2,2,2,4]

n=3, l=[5,2,3]     → [125,50,75,100,75,30,45,200,75,30,45,60,45,18,27]
n=3, l=[1,1,1]     → [1,1,1,3,1,1,1,9,1,1,1,3,1,1,1]

You can assume the input is valid. This is , so the shortest program measured in bytes wins.

\$\endgroup\$
  • \$\begingroup\$ Would it be acceptable to input and output the indices of non-deleted segments instead of the lengths? For instance, [0, 1, 2, 4, 6, 7] instead of [3, 1, 1, 1, 2]? \$\endgroup\$ – Mnemonic May 22 '18 at 15:06
  • \$\begingroup\$ @Mnemonic it's not too far from unary, so I'd say it's fine. \$\endgroup\$ – Angs May 22 '18 at 15:25
  • \$\begingroup\$ Could you add one (or multiple) test case(s) for even-sized input-lists? \$\endgroup\$ – Kevin Cruijssen May 23 '18 at 7:09
  • 1
    \$\begingroup\$ @KevinCruijssen the input lists are guaranteed to be odd-sized \$\endgroup\$ – Angs May 23 '18 at 7:18

12 Answers 12

6
\$\begingroup\$

Jelly,  15 13  12 bytes

-2 thanks to Dennis (using a Link rather than a chain allows right to be used implicitly by ¡; No need to wrap the 1 in a list due to the fact that Jelly prints lists of one item the same as the item)
-1 thanks to Erik the Outgolfer (use Ɗ to save the newline from using Ç)

1×€³§JḤ$¦ẎƊ¡

A full program printing a list in Jelly format (so [1] is printed as 1)

Try it online!

How?

1×€³§JḤ$¦ẎƊ¡ - Main link: segmentLengths; iterations
1            - literal 1 (start with a single segment of length 1)
           ¡ - repeat...
             - ...times: implicitly use chain's right argument, iterations
          Ɗ  - ...do: last 3 links as a monad (with 1 then the previous output):
   ³         - (1) program's 3rd argument = segmentLengths
 ×€          -  1  multiply €ach (e.g. [1,2,3] ×€ [1,2,1] = [[1,4,3],[2,4,2],[3,6,3]])
        ¦    -  2  sparse application... 
       $     - (2) ...to: indices: last two links as a monad:
     J       - (2)          range of length = [1,2,3,...,numberOfLists]
      Ḥ      - (2)          double            [2,4,6,...] (note: out-of bounds are ignored by ¦)
    §        - (2) ...of: sum each (i.e. total the now split empty spaces)
         Ẏ   -  3  tighten (e.g. [[1,2,3],4,[5,6,7]] -> [1,2,3,4,5,6,7])
             - implicit print
\$\endgroup\$
4
\$\begingroup\$

Python 2, 120 107 104 103 100 99 89 bytes

f=lambda n,l:n and[x*y for i,x in enumerate(l)for y in[f(n-1,l),[sum(l)**~-n]][i%2]]or[1]

Try it online!


Saved

  • -10 bytes, thanks to Neil
\$\endgroup\$
  • 1
    \$\begingroup\$ 89 bytes \$\endgroup\$ – Neil May 22 '18 at 21:47
  • \$\begingroup\$ @Neil, Thanks :) \$\endgroup\$ – TFeld May 23 '18 at 7:00
4
\$\begingroup\$

R, 94 bytes

f=function(n,a)"if"(n,unlist(Map(function(g,i)g(i),c(c,sum),split(m<-a%o%f(n-1,a),row(m)))),1)

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Haskell, 76 58 bytes

l%0=[1]
l%n=do(x,m)<-l%(n-1)`zip`cycle[l,[sum l]];map(*x)m

Try it online!

The function (%) takes the list of line lengths l as first argument and the number of iterations n as second input.

Thanks to Angs and Ørjan Johansen for -18 bytes!

\$\endgroup\$
  • \$\begingroup\$ You should be able to save at least 7 bytes by switching to a recursion on n and dropping # altogether \$\endgroup\$ – Angs May 23 '18 at 23:59
  • \$\begingroup\$ Independently of @Angs 's suggestion, the original % can be shortened to l%a=do(x,m)<-zip a$a>>[l,[sum l]];(*x)<$>m . \$\endgroup\$ – Ørjan Johansen May 24 '18 at 18:09
3
\$\begingroup\$

JavaScript (Firefox 42-57), 80 bytes

f=(n,l,i=0)=>n--?[for(x of l)for(y of(i^=1)?f(n,l):[eval(l.join`+`)**n])x*y]:[1]

Needs those specific versions because it uses both array comprehensions and exponentiation.

\$\endgroup\$
3
\$\begingroup\$

JavaScript (Node.js), 71 bytes

l=>f=(n,c=1,e)=>n--?''+l.map(_=>(e=!e)?f(n,c*_):eval(l.join`+`)**n*c):c

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Java 10, 261 bytes

L->n->{if(n<1){L.clear();L.add(1);}else if(n>1){var C=new java.util.ArrayList<Integer>(L);for(int l=C.size(),i,x,t,s;n-->1;)for(i=x=0;i<L.size();){t=L.remove(i);if(i%2<1)for(;i%-~l<l;)L.add(i,C.get((i++-x)%l)*t);else{x++;s=0;for(int c:C)s+=c;L.add(i++,t*s);}}}}

Modifies the input-List instead of returning a new one to save bytes.

Try it online.

L->n->{                       // Method with List and integer parameters and no return-type
  if(n<1){                    //  If `n` is 0:
    L.clear();                //   Remove everything from the List
    L.add(1);}                //   And only add a single 1
                              //  Else-if `n` is 1: Leave the List as is
  else if(n>1){               //  Else-if `n` is 2 or larger:
    var C=new java.util.ArrayList<Integer>(L);
                              //   Create a copy of the input-List
    for(int l=C.size(),       //   Set `l` to the size of the input-List
        i,x,t,s;              //   Index and temp integers
        n-->1;)               //   Loop `n-1` times:
      for(i=x=0;              //    Reset `x` to 0
          i<L.size();){       //    Inner loop `i` over the input-List
        t=L.remove(i);        //     Remove the current item, saving its value in `t`
        if(i%2<1)             //     If the current iteration is even:
          for(;i%-~l<l;)      //      Loop over the copy-List
            L.add(i,C.get((i++-x)%l)*t);
                              //       And add the values multiplied by `t`
                              //       at index `i` to the List `L`
        else{                 //     Else (the current iteration is odd):
          x++;                //      Increase `x` by 1
          s=0;for(int c:C)s+=c;
                              //      Calculate the sum of the copy-List
          L.add(i++,t*s);}}}} //      Add this sum multiplied by `t`
                              //      at index `i` to the List `L`
\$\endgroup\$
2
\$\begingroup\$

Jelly, 13 bytes

Ø1××S¥ƭ€³Ẏ$¡Ṗ

Try it online!

Full program. Outputs 1 instead of [1]. Annoyingly, doesn't work like ×S¥ in this context, and ƭ doesn't work well with nilads. >_<

\$\endgroup\$
2
\$\begingroup\$

APL (Dyalog Classic), 20 bytes

{(∊⊢×⍵(+/⍵)⍴⍨≢)⍣⍺,1}

Try it online!

\$\endgroup\$
2
\$\begingroup\$

K (ngn/k), 27 bytes

{x{,/y*(#y)#x}[(y;+/y)]/,1}

Try it online!

{ } is a function with arguments x and y

(y;+/y) a pair of y and its sum

{ }[(y;+/y)] projection (aka currying or partial application) of a dyadic function with one argument. x will be (y;+/y) and y will be the argument when applied.

,1 singleton list containing 1

x{ }[ ]/ apply the projection x times

(#y)#x reshape to the length of the current result, i.e. alternate between the outer y and its sum

y* multiply each element of the above with the corresponding element of the current result

,/ concatenate

\$\endgroup\$
1
\$\begingroup\$

Ruby, 73 bytes

->a,l{r=[1];a.times{s=p;r=r.flat_map{|x|(s=!s)?l.map{|y|x*y}:x*l.sum}};r}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Pyth, 20 bytes

us.e?%k2*bsQ*LbQGE]1

Input is segment array l, then iterations n. Try it online here, or verify all the test cases at once here.

us.e?%k2*bsQ*LbQGE]1   Implicit, Q=1st arg (segment array), E=2nd arg (iterations)
u                E     Execute E times, with current value G...
                  ]1   ... and initial value [1]:
  .e            G        Map G, with element b and index k:
        *bsQ               Multiply b and the sum of Q {A}
            *LbQ           Multiply each value of Q by b {B}
    ?%k2                   If k is odd, yield {A}, otherwise yield {B}
 s                       Flatten the resulting nested array
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.