title: Worst case of Slowsort

text:
# Question
Title: Worst case of Slowsort
## Background

Slowsort is an in-place, stable sorting algorithm that has worse-than-polynomial time complexity. The pseudocode for Slowsort looks like this:

```
procedure slowsort(A[], i, j)          // Sort array range A[i ... j] in-place.
    if i ≥ j then
        return
    m := floor( (i+j)/2 )
    slowsort(A, i, m)                  // (1.1)
    slowsort(A, m+1, j)                // (1.2)
    if A[j] < A[m] then
        swap A[j] , A[m]               // (1.3)
    slowsort(A, i, j-1)                // (2)

```
* (1.1) Sort the first half, recursively.
* (1.2) Sort the second half, recursively.
* (1.3) Find the maximum of the whole array by comparing the results of 1.1 and 1.2, and place it at the end of the list.
* (2) Sort the entire list (except for the maximum now at the end), recursively.

The recurrence relation of the worst-case time complexity (the number of swaps when the condition for (1.3) is always true1) is:

$$ \begin{alignat}{5} T(1) &= 0 \\ T(n) &= T\left(\left\lfloor\frac{n}{2}\right\rfloor\right) + T\left(\left\lceil\frac{n}{2}\right\rceil\right) + 1 + T(n-1) \end{alignat} $$

The first 50 terms of the sequence are:

```
0, 1, 3, 6, 11, 18, 28, 41, 59, 82,
112, 149, 196, 253, 323, 406, 507, 626, 768, 933,
1128, 1353, 1615, 1914, 2260, 2653, 3103, 3610, 4187, 4834,
5564, 6377, 7291, 8306, 9440, 10693, 12088, 13625, 15327, 17194,
19256, 21513, 23995, 26702, 29671, 32902, 36432, 40261, 44436, 48957

```

This sequence seems to coincide with A178855.

A proof by @loopy wait (which gives rise to multiple alternative formulas):

> Proof: start with A033485 (`a(n) = a(n-1) + a(floor(n/2)), a(1) = 1`) and verify that `a(2n+1)-a(2n-1)=2a(n)` (because `a(2n+1) = a(2n) + a(n) = a(2n-1) + 2a(n)`). Also verify that if `n` is even `2a(n)=a(n-1)+a(n+1)`. If we substitute `b(n)=a(2n-1)` we get `b(n)-b(n-1)=b(floor(n/2))+b(ceil(n/2))` which is already similar to T. If we now set `2T+1=b` we get back the recurrence defining `T`. As the initial terms also match this shows that `T(n)=((A033485(2n-1)-1)/2` which (shifted by one) is also given as a formula for A178855.

## Challenge

Evaluate the sequence \\$T(n)\\$. default I/O applies; you can choose one of the following:

* Without input, output the entire sequence \\$T(1), T(2), T(3), \cdots\\$ infinitely
* Given \\$n \> 0\\$, output \\$T(n)\\$ (corresponding to \\$n\\$th value under 1-indexing)
* Given \\$n \ge 0\\$, output \\$T(n+1)\\$ (corresponding to \\$n\\$th value under 0-indexing)
* Given \\$n \> 0\\$, output the first \\$n\\$ terms, i.e. \\$T(1), T(2), \cdots, T(n)\\$

Standard rules apply. The shortest code in bytes wins.

---

1 Don't ask me how, I don't know if it can actually happen.

# Answer
# Haskell, 31 bytes

-6 bytes thanks to @xnor.

```
a=s 0b
b=s 1$b<*"  "
s=scanl(+)

```

Try it online!

A178855 is the cumsum of A033485, while A033485 is the cumsum of `1, a(1), a(1), a(2), a(2), a(3), a(3), ...`, where `a` is A033485 itself.
> 14 votes

# Answer
# JavaScript (ES6), 31 bytes

Returns the \\$n\\$-th term, 0-indexed.

```
f=n=>n&&f(n>>1)+f(--n>>1)-~f(n)

```

Try it online!
> 5 votes

# Answer
# Husk, 12 bytes

```
∫Θ¡§+→ȯ→←½;1

```

Try it online!

Uses the idea of the Haskell answer.
> 4 votes

# Answer
# 05AB1E, ~~14~~ 10 bytes

```
λN<2÷₅+}.¥

```

-4 bytes porting *@alephalpha*'s Haskell answer and combining it with *@ovs*' 05AB1E approach of using `n-1`, so make sure to upvote both of them as well!

Outputs the infinite sequence.

Try it online.

**Explanation:**

```
λ        # Start a recursive environment,
         # to output the infinite sequence
         # Starting at a(0)=1 implicitly
         # Where every following a(n) is calculated by:
 N<      #  Push n-1
   2÷    #  Integer-divide it by 2
     ₅   #  Pop and push a((n-1)//2)
      +  #  Add it to the implicit previous item: a(n-1)+a((n-1)//2)
}        # After the recursive environment
 .¥      # Prepend 0 and get the cumulative sum of this list
         # (after which the infinite sequence is output implicitly)

```
> 4 votes

# Answer
# C (gcc), 34 bytes

```
f(n){n=n?f(n/2)+f(--n/2)-~f(n):0;}

```

Try it online!

Returns the \\$0\\$-indexed \\$n^\text{th}\\$ term.

Uses given formula.
> 4 votes

# Answer
# Vyxal 2.4.1, ~~19~~ ~~18~~ 17 bytes

```
λċ[½₌⌈⌊x$xn‹xṠ›|0

```

Try it Online!

Of course just as I decided to make  no longer sum the stack, an edge case where it's needed pops up.

## Explained

```
λċ[½₌⌈⌊x$xn‹xṠ›|0
λ                  # Start a monadic lambda taking argument n that:
 ċ[                #    if n != 1:
   ½₌⌈⌊             #        push the ceiling and floor of (n / 2)
      x$x          #        and call this lambda on both
         n‹x       #        then call this lambda on n - 1
            Ṡ›     #        finally, push the sum of the stack + 1
              |    #    else:
               0   #        return 0
                   # The lambda is automatically called on end of execution

```
> 3 votes

# Answer
# Jelly, 15 bytes

```
HḞ,ĊƊ;’ß€S‘µ0’?

```

Try It Online!

I don't think this is close to optimal.
> 3 votes

# Answer
# 05AB1E, ~~13~~ 12 bytes

Implements the recurrence relation

```
0λND<‚;ï₅O+>

```

Try it online!
> 3 votes

# Answer
# Python 3, 42 bytes:

```
f=lambda n:n and-~f(n//2)+f(~-n//2)+f(n-1)

```
> 2 votes

# Answer
# Retina 0.8.2, 33 bytes

```
.+
$*
+`1(1*)(1*\1)
$1$2¶$1¶$2
¶¶

```

Try it online! Outputs the 0-indexed `n`th value. Explanation: Uses the recurrence relation given in the question.

```
.+
$*

```

Convert to unary.

```
+`1(1*)(1*\1)

```

Find the floor and ceiling of half of `n`.

```
$1$2¶$1¶$2

```

Replace `n` with `n-1` and the above two values. This introduces two extra lines for each recurrence.

```
¶¶

```

Count half of the number of extra lines, which represents the number of `1`s summed as part of the recurrence.
> 1 votes

# Answer
# Rust, 56 bytes

```
fn f(n:i32)->i32{if n>0{f(n/2)-!f(!-n/2)+f(n-1)}else{0}}

```

Try it online!

Returns the \\$n\\$-th term, 0-indexed.
> 1 votes

# Answer
# Charcoal, 20 bytes

```
ＦＮ⊞υ∨¬υ⁺⌈υ§υ⊘⊖ＬυＩ↨¹υ

```

Try it online! Link is to verbose version of code. Outputs the 0-indexed `n`th value. Explanation:

```
ＦＮ

```

Input `n` and loop that many times.

```
⊞υ∨¬υ⁺⌈υ§υ⊘⊖Ｌυ

```

Generate the next term of `A033485`, or `1` if there are no terms yet. (Annoyingly the formula for this sequence assumes 1-indexing.)

```
Ｉ↨¹υ

```

Sum the terms (using base `1` in case there are none).
> 0 votes

# Answer
# Ruby, ~~38 ...~~ 35 bytes

```
f=->n{n<2?n:f[n/2]-~f[n-=1]+f[n/2]}

```

Try it online!

Recursive version, as a function, returns nth value.

# Ruby, 42 bytes

```
*r=a=b=c=0;loop{p c;a,b,*r=r+=[c+=a-~b]*4}

```

Try it online!

Non-recursive version, faster, prints whole list.
> 0 votes

---
Tags: code-golf, sequence, sorting
---


title: Cantor's unspeakable numbers

text:
# Question
Title: Cantor's unspeakable numbers
An unspeakable number is a number which is divisible by seven or has seven as one of its digits. A children game is to count skipping unspeakable numbers

```
1 2 3 4 5 6 ( ) 8 9 10 11 12 13 ( ) 15 16 ( ) 18 ...

```

Cantor's version of the game is the sequence defined by recursively filling in the sequence "1 2 3 4 5 6 ( ) 8..." into the gaps ( ) above.

`1 2 3 4 5 6 *1* 8 9 10 11 12 13 *2* 15 16 *3* 18 19 20 *4* 22 23 24 25 26 *5 6* 29 30 31 32 33 34 ***1*** 36 *8* 38 ...`

Print/output at least the first 7^7 numbers of Cantor's unspeakable number game...

While the definition is given recursively, you are not obliged to use recursion in the code.

This is , so the program with the shortest byte count wins!

Note: The sum of numbers in 1 to 7^7 is 203511962727. The last 10 numbers in that range are 823534 823535 221563 108068 823538 823539 823540 823541 823542 221565.

Pastebin dump of first 1000 iterates: http://pastebin.com/Ksiu9Svf

# Answer
> 7 votes
# Pyth, ~~25~~ ~~23~~ 22 bytes

*Thanks to @Maltysen for -2 bytes*

```
.V1=+Y
?}7+PbjbT@Y~hZb

```

A program that prints an infinite stream.

Try it online! (Output flushed at intervals and times out at 1 min)

**How it works**

```
.V1=+Y
?}7+PbjbT@Y~hZb

Z = 0, Y = []    Implicit variable assignment
.V1              Infinite incrementing for loop with variable b, starting at 1:
   =+Y            Y = Y +
(newline)          (Implicitly print the result of the following:)
?                   If
 }7                  7 is in
    Pb                the prime factorisation of b
   +                  or
      jbT             the digits of b:
         @Y            Index into Y at index
             Z          Z
           ~h          (Increment Z)
                    else:
              b      b

```

# Answer
> 23 votes
# Python 2, ~~77~~ ~~75~~ ~~74~~ 70 bytes

*Thanks to @MartinEnder for suggesting the limit of `9e5` which enderd up working after a change.
Thanks to @mschauer for suggesting an infinite stream, saving 4 bytes.*

```
def f(n=0):
 i=f()
 while 1:n+=1;yield next(i)if'7'in`n`or n%7<1else n

```

This is a generator that yields an infinite stream of the numbers.

# Answer
> 10 votes
# Perl, ~~47~~ ~~46~~ ~~41~~ 39 bytes

Saved 5 bytes thanks to @Dada

```
say$_=$_%7*!/7/?$_:$a[$b++]for@a=1..1e6

```

Try It Online! TIO Nexus, now with Perl support! This will truncate the output after a certain point, but if you have Perl installed, you can run it locally to produce the full output.

The code makes use of a couple of strange quirks of Perl's syntax, so I'll break down how it works below.

### Code breakdown:

```
say$_=$_%7*!/7/?$_:$a[$b++]for@a=1..1e6
                              @a=1..1e6 #Assign the range (1..1,000,000) to the array @a
                           for          #and then loop through this list, with $_ as an alias for the list member.  As an alias, modifying $_ modifies @a.
      $_%7*!/7/?$_:$a[$b++]             #Ternary operation
      $_%7                              #Returns the residue modulo 7...
          *!/7/                         #...and multiplies it by the negation of whether or not there exists a 7 $_
                                        #Since % and * have the same operator precedence, it must be evaluated in this order
                                        #otherwise we would get (!/7/*$_)%7 instead of ($_%7)*!/7/
               ?$_                      #If the result is non-zero (i.e. truthy), then return $_
                  :$a[$b++]             #Otherwise, return the $b-th element of @a, and increment $b
   $_=                                  #Reassign the result back to $_, modifying @a
say                                     #Prints the result of the assignment, separated by newlines

```

# Answer
> 6 votes
## Haskell, ~~67~~ 66 bytes

```
i#x|mod x 7<1||'7'`elem`show x=f!!i:(i+1)#(x+1)|y<-x+1=x:i#y
f=0#1

```

`f` is an infinite list of the numbers.

Try it online!

`f` starts a new iteration with `1` and an index which number to pick of 0. Whenever there's a gap we take a new iteration an pick it's `ith` element and continue the current iteration with `i+1`. If there's no gap, we take the current number `x` and go on without increasing `i`.

Edit: -1 byte thanks to @BMO.

# Answer
> 5 votes
# PHP, 80 (Wahooka) 57 54 bytes

While the idea is from Wahooka. I think my version is different enough to make it an own answer:

```
for(;;)echo$a[]=strpos(++$n,55)<-$n%7?"$n ":$a[+$b++];

```

# Answer
> 4 votes
# MATL, ~~26~~ 25 bytes

```
9e5:`t7\yFYA!7-A*~s:2M(2M

```

Try it online! with `9e5` replaced by `9e4`, so that the maximum running time and output size of the online compiler are not exceeded.

### How it works

This uses iteration instead of recursion. (In fact, MATL doesn't have recursion).

An array of numbers from `1` to `9e5` is first generated (this is enough, because `9e5` exceeds `7^7`). Then, numbers that are multiples of `7` or have `7` as digit are identified, and replaced by `1`, `2`, ... The process is iterated until there are no numbers that need to be replaced.

```
9e5:       % Generate array of numbers [1 2 ... 9e5]. This array will become the
           % output, after some numbers have been replaced
`          % Do...while
  t        %   Duplicate the array of numbers
  7\       %   Modulo 7. Gives zero for multiples of 7
  y        %   Duplicate the array of numbers
  FYA!     %   Matrix of decimal digits, with a column for each number
  7-       %   Subtract 7 to each entry of that matrix
  A        %   Array that contains "true" for columns that only contain nonzeros;
           %   that is, for numbers that do not have 7 as digit
  *        %   Multiply. This corresponds to a logical "and" of the two conditions.
           %   A zero indicates that the number at that index needs to be replaced
  ~        %   Logical negate. Each "true" corresponds to a number to be replaced
  s        %   Sum. This is the amount of numbers to be replaced, say n
  :        %   Push array [1 2 ... n]
  2M       %   Push array of logical values again
  (        %   Replace the numbers at the positions indicated by the logical array
           %   by the values [1 2 ... n]
  2M       %   Push n again. This is used as loop condition, so if it is nonzero
           %   the next iteration will be executed. Note that this executes one
           %   too many iterations: the exit condition is that no replacing has
           %   been needed in the current iteration; but then the current iteration
           %   (which will be the last) was not really necessary. This does not
           %   matter; the last iteration is useless but also harmless
           % End do...while implicitly. Display implicitly

```

# Answer
> 3 votes
# Tcl, 121 Bytes

The trivial solution using infinite loop, nothing fancy..

```
set r 0;set n 0;while {[set r [expr $r+1]]} {if {![expr $r%7]||(7 in[split $r ""])} {puts [set n [expr $n+1]]} {puts $r}}

```

Ungolfed:

```
set r 0
set n 0
while {[set r [expr $r+1]]} {
  if {![expr $r % 7] || (7 in [split $r ""])} {
    puts [set n [expr $n+1]]
  } {
    puts $r
  }
}

```

# Answer
> 3 votes
# PHP, ~~106~~ 80 bytes

Thank you Ismael Miguel for help with the ternary solution and shorter loop code using for instead of while.

Could not verify the last parts of the full sequence due to PhpFiddle's 30 second max runtime. Seems to work at least up to 1K based on the sample output provided by the OP.

**Golf:**

```
for($n=1;;$n++)echo$a[]=!(strpos($n,"7")>-1||$n%7==0)?"$n ":array_shift($a)." ";

```

**Original golfed version**:

```
$n=1;while(1){if(!(strpos($n,"7")>-1||$n%7==0)){echo$a[]=$n." ";}else{echo$a[]=array_shift($a)." ";}$n++;}

```

# Answer
> 3 votes
# Perl 6,  ~~74 57 54~~  53 bytes

```
sub u{my@u;(1..*).map: {if $_%%7||.comb('7') {@u||=u;@u.shift} else {$_}}}

```

```
sub u{(1..*).map: {$_%%7||.comb('7')??(@||=u).shift!!$_}}

```

```
sub u{map {$_%%7||.comb('7')??(@||=u).shift!!$_},1..*}

```

```
sub u{map {$_%%7||.comb(~7)??(@||=u).shift!!$_},1..*}

```

Try it

## Expanded:

```
sub u{
  map             # for each element transform using:

  { # bare block lambda with implicit parameter ｢$_｣

      $_ %% 7     # if it is divisible by 7
      ||          # or
      .comb(~7)   # contains the number 7 (implicit method call on ｢$_｣)

    ??            # then
      ( @ ||= u ) # store a new instance of the Seq into an unnamed state array if it is empty
                  # ( it is only empty the first time it is seen in this Seq instance )
      .shift      # pull one off of the front

    !!            # else
      $_          # return the value
  },

  1 .. *          # infinite range starting at one ( elements to be mapped over )
}

```

## Test:

```
$ time perl6 -e'sub u{map {$_%%7||.comb(~7)??(@||=u).shift!!$_},1..*};put 203511962727 == sum u()[^7**7]'
True

real    2m45.744s
user    2m45.416s
sys     0m0.212s

```

# Answer
> 3 votes
# Julia, 62 bytes

```
x=[];j=0;for i=1:7^7;x=[x;i%7<1||('7' in "$i")?x[j+=1]:i]end;x

```

Nothing fancy. Uses that the sequence within the gaps is the sequence itself. Makes excessive array copies to save some bytes.

# Answer
> 3 votes
# Dyalog APL, 39 bytes

`{(⍵⍴⍨⍴i)@(i←⍸('7'∊¨⍕¨⍵)∨0=7|⍵)⊢⍵}⍣≡⍳7*7`

`⍳7*7` is 1 2 3...77

`{ }⍣≡` is the *fixed point* operator - apply a function repeatedly until the result stabilises

`A@I⊢B` *amend* operator - replace the elements at indices `I` in `B` with `A`

`0=7|⍵` bitmask for where the argument is divisible by 7

`'7'∊¨⍕¨⍵` bitmask for where the decimal formatting of the argument contains a 7

or

at what indices is either of the above bitmasks true?

`i←` assign to `i`

`⍵⍴⍨⍴i` reshape the argument to the number of elements in `i`

# Answer
> 3 votes
## Javascript, 80 bytes

```
n=[]
r=l=>(m=n[l]=++n[l]||1,!/7/.test(m)m%7?m:r(l+1))
for(;;)console.log(r(0))

```

Since there is only a minimum requirements but not a maximum requirements, this solution continues to output indefinitely.

To verify that the algorithm is correct, you can execute the same code printing only the last 10 numbers and the sum:

```
n = []
r = l => (m = n[l] = ++n[l] || 1, !/7/.test(m) && m % 7 ? m : r(l + 1))
var tot = 0
for (i = 0; i + 1; i++) {
    v = r(0)
    tot += v
        if (i > Math.pow(7, 7) - 11) {
        console.log(v)
    }
    if (i === Math.pow(7, 7) - 1) {
        console.log(tot)
        break
    }
}

```

# Answer
> 2 votes
# Ceylon, 202 bytes

```
object u satisfies{Integer*}{iterator()=>object satisfies Iterator<Integer>{variable value i=0;late Iterator<Integer>n;next()=>if(++i%7<1||'7'in"``i``")then(i<8then(n=iterator())else n).next()else i;};}

```

This is not a function, but an object declaration implementing an infinite sequence (Iterable). The object can be printed directly, `print(u)` outputs this:

`{ 1, 2, 3, 4, 5, 6, 1, 8, 9, 10, 11, 12, 13, 2, 15, 16, 3, 18, 19, 20, 4, 22, 23, 24, 25, 26, 5, 6, 29, 30, ... }`

To print more, use `printAll(u)`. The following code uses newlines, and also prints the sum (and the first 30 elements shown above):

```
shared void run() {
    printAll(u.take(7^7), "\n");
    print(sum({0, * u.take(7^7)}));
    print(u);
}

```

Here is the ungolfed and commented version:

```
// Prints cantor's unspeakable numbers.
//
// Question:  http://codegolf.stackexchange.com/q/101231/2338
// My answer: http://codegolf.stackexchange.com/a/101297/2338

// this object u (which is like a singleton class with its single instance)
// implements the Iterable<Integer> interface.
object u satisfies {Integer*} {
    // That interface has just one formal method,
    // `shared formal Iterator<Integer> iterator()`.
    // Lets implement it by ...
    iterator()
    // ... providing for each call ...
            =>
                // ... a new (anonymous) object, which
                // implements the Iterator<Integer> interface.
                object satisfies Iterator<Integer> {
                    // This is the counter (the type `Integer`
                    // is longer than `value`, so we infer it).
                    // We start at 0.
                    variable value i = 0;
                    // This is a nested Iterator. It will be
                    // initialized when first needed, so we don't
                    // get an endless recursion when creating the
                    // first iterator.
                    late Iterator<Integer> n;
                    // `shared formal Integer next()` is the single method
                    // of Iterator which needs to be implemented.
                    next()
                    // each time it is called, the following
                    // expression will be evaluated.
                            =>
                                // increment the counter, then check if it
                                // is an unspeakable number.
                                if (++i % 7 < 1 || '7' in "``i``")
                                then
                                    // if so, take the nested iterator (and the
                                    //  first time, for i == 7, create it first),
                                    // and take its next element.
                                    (i < 8 then (n = iterator()) else n).next()
                                else
                                    // otherwise, just return i.
                                    i;
                };
}

```

# Answer
> 2 votes
# Ruby, 80 bytes

`l=->x{x%7==0||x.to_s[/7/]};a=(1..100);b=a.reject &l
p a.map{|x|!l[x]?x:b.shift}`

First submission, I'm sure it can be improved :)

# Answer
> 2 votes
# C ~~157~~ 155 Bytes

```
int c[999999],r;main(_,p){if(_){p=--_;c[_]=1;for(;;){printf("%d ",c[_]);main(0,++_+1);c[_]=r?_+1:c[p++];}}else!p?r=1:p%7?p%10-7?main(0,p/10):(r=0):(r=0);}

```

It looks right, I didn't bother to fully check. Goes up to 999999 which is apparently large enough.

Ungolfed version:

```
int cantor_n[1000000];

int cantor_n_safe(int x) {
    if (!x) return 1;
    if (x % 7 == 0) return 0;
    if (x % 10 == 7) return 0;
    return cantor_n_safe(x / 10);
}

int main(_, prev_index) {
    prev_index = --_;
    cantor_n[_] = 1;
    for(;;) {
        printf("%d ", cantor_n[_]);
        _++;
        if (!cantor_n_safe(_+1)) {
            cantor_n[_] = cantor_n[prev_index++];
        } else {
            cantor_n[_] = _+1;
        }
    }
    return 0;
}

```

Partially golfed version:

```
int c[999999];int r;
safe(x){
    !x?
        r=1:
        x%7?
            x%10-7?
                safe(x/10):
                (r=0):
            (r=0);
}

main(_){
    int p;
    p=--_;
    c[_]=1;
    for(;;){
        printf("%d ",c[_]);
        safe(++_+1);
        if (!r) {
            c[_]=c[p++];
        } else {
            c[_]=_+1;
        }
    }
}

```

# Answer
> 2 votes
## R, 86 bytes

```
x=1;while(T<7^7){T=T+1;x[T]=if(!T%%7|7%in%el(strsplit(c(T,""),""))){F=F+1;x[F]}else T}

```

Uses R's Truthy built-in `T` (initialized to `TRUE`/`1`) to count the numbers in the the sequence and the Falsy value `F` (initialized to `FALSE`/`0`) to count the unspeakables. Other than that the program simply checks whether each number is divisible by seven or contains the number.

# Answer
> 2 votes
# C - 115 bytes

```
s[99],r;g(x){return x%10-7&&(!x||g(x/10));};f(i){(r=++s[i])%7&&g(r)||f(i+1);}main(){for(;;f(0),printf("%d\n",r));}

```

EDIT: Thanks to @mschauer who pointed out I missed some things.

# Answer
> 1 votes
# Mathematica, 82 bytes

```
Nest[#2&[i=1,If[Or@@(#==7&)/@IntegerDigits@#,i++,#]&/@#]&,Table[i,{i,7^7}],20]

```

# Answer
> 1 votes
# JavaScript 81 bytes

### Original (98 bytes)

```
for(c=0,i=1;i<=Math.pow(7,7);i++)/7/.test(i)||i%7==0?(6==c?c=1:c++,console.log(c)):console.log(i);

```

### Golfed

```
p=console.log;for(c=0,i=1;i<9e5;i++)/7/.test(i)||i%7==0?(6==c?c=1:c++,p(c)):p(i);

```

# Answer
> 1 votes
## Befunge, 100 or 156 bytes

This first version is the more portable of the two, limiting itself to 7-bit memory cells, which is what you get in the reference interpreter.

```
"O":0>\#09#:p#-:#1_v<0$.<
9\*"~"g9+1:+1::p00:<+3$_^#g01$$<v"~":/"~"p9g00%"~"::+1+g9\*"~"+g
:#15#+5#g+#0%#17#\-#/!#+\#5:#5_^>%00g1+9p"~"/00g2+9p::7%!10>>p#0

```

The second version only works with interpreters that have 32-bit memory cells, and thus isn't strictly standard Befunge, but that lets us store larger values in memory without having to split them across cells.

```
"O":0>\#09#:p#-:#1_v<0$.<
%7::p9g00:+1g9:p00:<+1$_^#g01$$<v01!
:#15#+5#g+#0%#17#\-#/!#+\#5:#5_^>p#0

```

In both cases the program runs indefinitely, but the first version will overflow around the 2 million mark, while the second version should get up to the max int value (around 2 billion).

You can Try it online, but you'll need to kill the process to prevent it from trying to run forever.

# Answer
> 1 votes
## Clojure, 130 bytes

```
#(let[R(range(inc %))](rest((reduce(fn[[r s]i](if(or(=(mod i 7)0)((set(str i))\7))[(assoc r i(r s))(inc s)][r s]))[(vec R)0]R)0)))

```

Basic reduce, keeping track of contents of the result vector and how many values have been skipped. The last `0` takes first element of the reduced `[r s]`, `rest` drops first element of the 0-indexed result.

# Answer
> 1 votes
## Perl6, 41 bytes

```
put {($_=++$)%%7|m/7/??@_[$++]!!$_}…1e6

```

# Answer
> 1 votes
# Tcl, 72 bytes

```
while 1 {puts [expr {[incr i]%7&&7ni[split $i ""]?$i:([incr s]-1)%6+1}]}

```

Try it online!

# Answer
> 1 votes
# JavaScript, 64 bytes

```
for(f=n=>!/7/.test(m=++n[0])*m%7?m:f(n.t=n.t||[0]);;)alert(f(f))

```

```
output=[];index=0;for(f=n=>!/7/.test(m=++n[0])*m%7?m:f(n.t=n.t||[0]);index<100;)output[index++]=f(f);console.log(output.join(','))
```

# Answer
> 1 votes
# Japt, 25 bytes

```
[]L³õ@pX%7«/7/tX ?X:UgV°

```

Test the sum and last 10 elements.

Generates first 1,000,000 entries of the sequence and prints them. One million is the shortest number over `7**7 == 823543` in Japt.

The trailing newline is significant, as it activates the implicit assignment to `U`.

Generating the list only takes around a second, but outputting the entire array will likely make your browser hang.

### Unpacked & How it works

```
[]L³õX{UpX%7&&!/7/tX ?X:UgV++

[]                            Assign empty array to U
  L³õX{                       Map over 1 to 1,000,000 inclusive...
         X%7&&                  If X is not divisible by 7 and
              !/7/tX            X does not have a digit 7
                     ?X:UgV++   then X, otherwise the next element already in U
       Up                       Push it to the end of U

                              Implicit print U

```

Uses the property that the recursive definition can be resolved by looking at the already generated sequence.

# Answer
> 1 votes
# 05AB1E, 17 bytes

```
[N>ÐÑª˜7åi¯¾è¼}=ˆ

```

Port of *@TheBikingViking*'s Pyth answer, so make sure to upvote him as well!
Also outputs the infinite sequence, each number on a separated line.

Try it online.

**Explanation:**

```
[               # Start an infinite loop:
 N>             #  Push the 0-based loop-index + 1
   Ð            #  Triplicate this now 1-based index
    Ñ           #  Pop one and push a list of its divisors
     ª          #  Implicitly convert another number to a list of digits, and
                #  append this list of divisors to it
      ˜         #  Flatten it
       7åi      #  Pop and if it contains a 7
                #  (so either the digits contained a 7 or the divisors):
          ¯     #   Push the global array
           ¾è   #   Index the counter variable into it
             ¼  #   And increase the counter variable by 1 afterwards
         }      #  Close the if-statement
          =     #  Print the top number (without popping)
           ˆ    #  Pop and add it to the global array

```

If we only want to output the first \\$7^7\\$ results instead of printing indefinitely, the `[N>` could be `7mEN` instead.

---
Tags: code-golf, number, counting, recursion
---


# Question
Title: Find the substring with the most 1's in a sequence
# Introduction

I want to find the substring with the most `1`'s in a sequence of `0`'s and `1`'s.

# Input

Your program has two **inputs**, the sequence and the substring length.

The **sequence** is any number of `0`'s and `1`'s:

```
01001010101101111011101001010100010101101010101010101101101010010110110110

```

The **substring length** is any positive non-zero integer:

```
5

```

# Output

Your program should output the starting index of the first substring of the given length that contains the most `1`'s. With the above input, the output is:

```
10

```

The first character in the string starts at an index of `0`.

# Scoring

Shortest code wins!

# Rules

* Your program must always output the correct index for any valid inputs.
* You can pick your input/output method from any answer with positive score on the default options. Please specify the method you pick in your answer.

# Answer
> 11 votes
# Dyalog APL, 11

```
(-∘1+⍳⌈/)+/

```

Try it here. Usage:

```
   f ← (-∘1+⍳⌈/)+/
   4 f 0 1 1 0 1 1 1 0 0 0 0 1 1
1

```

### Explanation

This is a dyadic (meaning binary) function that takes the substring length from the left, and the sequence from the right. Its structure is the following:

```
   ┌───┴────┐
 ┌─┴──┐     /
 ∘  ┌─┼─┐ ┌─┘
┌┴┐ + ⍳ / +
- 1   ┌─┘
      ⌈

```

Explanation by explosion:

```
(-∘1+⍳⌈/)+/
(       )+/  ⍝ Take sums of substrings of given length, and feed to function in parentheses
    + ⌈/     ⍝ The array of sums itself, and its maximum
     ⍳       ⍝ First index of right argument in left
 -∘1         ⍝ Subtract 1 (APL arrays are 1-indexed)

```

As an example, let's take `4` and `0 1 1 0 1 1 1 0` as inputs. First we apply the function `+/` to them and get `2 3 3 3 3`. Then, `+` and `⌈/` applied to this array give itself and `3`, and `2 3 3 3 3 ⍳ 3` evaluates to `2`, since `3` first occurs as the second element. We subtract `1` and get `1` as the final result.

# Answer
> 11 votes
# Ruby, 42

```
f=->s,n{(0..s.size).max_by{|i|s[i,n].sum}}

```

Takes input by calling it, e.g.

`f['01001010101101111011101001010100010101101010101010101101101010010110110110',5]`

This compares substrings using their total ASCII value and returns the index of the maximum. I'm not sure if `max_by` is required by the Ruby spec to be stable but it appears to be in the C implementation.

# Answer
> 6 votes
# Python 2, 56

```
lambda s,l:max(range(len(s)),key=lambda i:sum(s[i:i+l]))

```

Accepts an array of integers, then the length.

# Answer
> 5 votes
## Batch - 222

Batch is obviously the perfect language for this kind of operation.

```
@echo off&setLocal enableDelayedExpansion&set s=%1&set l=-%2
:c
if defined s set/Al+=1&set "s=%s:~1%"&goto c
set s=%1&set x=0&for /l %%a in (0,1,%l%)do set c=!s:~%%a,%2!&set c=!c:0=!&if !c! GTR !x! set x=!c!&set y=%%a
echo !y!

```

**Un-golfed / dissected:**

Initial setup. The variable `s` is the input string, and `l` will be the length of the input string, minus the sub-string length (initialized at negative `%2` where `%2` is the given sub-string length).

```
@echo off
setLocal enableDelayedExpansion
set s=%1
set l=-%2

```

Get the length of the input as `l`, using a pure Batch string length solution - this mangles the variable `s` containing the input string, so we then set it again.

```
:c
if defined s (
    set /A l += 1
    set "s=%s:~1%"
    goto c
)
set s=%1

```

The value of `x` is used to check which sub-string had the greatest number of 1's. Start a loop from 0 to the length of the string, minus the sub-string length (variable `l`). Get the sub-string starting from the current point in the loop (`%%a`), `c` is set as the input string starting at `%%a`, and taking `%2` (the given sub-string length) characters. Any `0`s are removed from `c`, then the value of `c` is compared to `x` \- i.e. `111` is a greater number than `11` so we can just use the 'string' to do a greater than comparison. `y` is then set to current location in the string - which is finally outputted.

```
set x=0
for /l %%a in (0, 1, %l%) do (
    set c=!s:~%%a,%2!
    set c=!c:0=!
    if !c! GTR !x! (
        set x=!c!
        set y=%%a
    )
)
echo !y!

```

Using OPs example -

```
h:\>sub1.bat 01001010101101111011101001010100010101101010101010101101101010010110110110 5
10

```

# Answer
> 5 votes
# C# (Regex), 196

```
class Test{static void Main(string[]a){System.Console.Write(System.Text.RegularExpressions.Regex.Match(a[1],"(?=((?<o>1)|0){"+a[0]+"})(?!.+(?=[10]{"+a[0]+"})(?!((?<-o>1)|0){"+a[0]+"}))").Index);}}

```

The actual regex is not that long, but all the fluffs needed for a C# program to compile double the size of the code.

The actual regex, setting the length to 5:

```
(?=((?<o>1)|0){5})(?!.+(?=[10]{5})(?!((?<-o>1)|0){5}))

```
* `(?=((?<o>1)|0){5})`: Look-ahead to read 5 characters without consuming, and push all `1`'s into "stack" `o`.
* `(?=[10]{5})(?!((?<-o>1)|0){5})`: At a position which has 5 characters ahead, there is not enough item in "stack" `o` to pop out, i.e. the substring has strictly more `1` than what we have in the current position.
* `(?!.+(?=[10]{5})(?!((?<-o>1)|0){5}))`: A position as described above can't be found for the rest of the string, i.e. all position has less than or equal number of `1`'s.

Taking the first result gives the answer, since all substrings in front of it has some substring ahead with more `1`'s, and we have check that any index larger than the current index has less than or equal number of `1`'s.

(And I learn something nice: the "stack" is restored on backtracking).

# Answer
> 4 votes
# Pyth, 12

```
Mho/<>GNHZUG

```

This defines a function `g`, which requires a list of numbers and a number as input. E.g.

```
Mho/<>GNHZUGg[0 1 0 0 1 0 1 0 1 0 1 1 0 1 1 1 1 0 1 1 1 0 1 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 0 1 1 0 1 1 0)5

```

You can test it here: Pyth Compiler/Executor

### Explanation:

```
Mho/<>GNHZUG
M             defines a function g(G,H), G is the sequence, H the sequence length
  o       UG  orders the numbers between 0 and len(G)-1 according to the following key
    <>GNH     take the subsequence G[N:N+5]
   /     Z    count the zeros in this subsequence (this is the key)
 h            return the first value of the sorted list (minimum)

```

### Alternative:

```
Mho_s<>GNHUG

```

# Answer
> 4 votes
# J, 15 14 chars

```
   ([:(i.>./)+/\)

   5 ([:(i.>./)+/\) 0 1 0 0 1 0 1 0 1 0 1 1 0 1 1 1 1 0 1 1 1 0 1 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 0 1 1 0 1 1 0
10

```

# Answer
> 4 votes
# Haskell, 64 62 Bytes

```
n#l=0-(snd$maximum[(sum$take n$drop x l,-x)|x<-[0..length l]])

```

Usage:

```
5#[0,1,0,0,1,0,1,0,1,0,1,1,0,1,1,1,1,0,1,1,1,0,1,0,0,1,0,1,0,1,0,0,0,1,0,1,0,1,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,1,0,1,1,0,1,0,1,0,0,1,0,1,1,0,1,1,0,1,1,0]

```

# Answer
> 4 votes
# Matlab (42)

Let `s` denote the string and `n` the substring length. The result is `r`.

Compute convolution of `s` with a sequence of `n` ones, then find the maximum. Convolution is done easily with `conv`, and the `max` function returns the position of the *first* maximum. It's necessary to subtract `1` to the resulting index, because Matlab indexing starts at `1`, not `0`.

```
[~, r] = max(conv(s, ones(1,n), 'valid'));
r = r-1;

```

Golfed:

```
[~,r]=max(conv(s,ones(1,n),'valid'));r=r-1

```

# Answer
> 4 votes
# APL (Dyalog Unicode), 5 bytes

```
⊃∘⍒+/

```

Try it online!

`⊃∘⍒` is an idiom for "index of maximum", or "argmax", and `n +/ bitarray` computes the sums over all `n`-length segments. Uses the system setting `⎕IO←0` to make the output 0-based.

# Answer
> 3 votes
# JavaScript (ES6) 73

A function returning the requested value. The for loop scans the input string keeping a running total, saving the position of the max value.

```
F=(a,n)=>(x=>{for(r=t=i=x;a[i];t>x&&(x=t,r=i-n))t+=a[i]-~~a[i++-n]})(0)|r

```

**Ungolfed**

```
F=(a, n) => {
   for(x = r = t = i = 0; a[i]; i++)
     t += a[i] - ~~a[i-n], // ~~ convert undefined values (at negative index) to 0
     t > x && (x=t, r=i-n+1);
   return r;
}

```

**Test** In FireFox/FireBug console

```
F("01001010101101111011101001010100010101101010101010101101101010010110110110",5)

```

*Output* `10`

# Answer
> 3 votes
# Mathematica, ~~38~~ 36

```
f=#-1&@@Ordering[-MovingAverage@##]&

```

Example:

```
f[{0,1,0,0,1,0,1,0,1,0,1,1,0,1,1,1,1,0,1,1,1,0,1,0,0,1,0,1,0,1,0,0,0,1,0,1,0,1,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,1,0,1,1,0,1,0,1,0,0,1,0,1,1,0,1,1,0,1,1,0},5]

```

Output:

> 10

# Answer
> 3 votes
# PHP (96)

`for($a=$b=$c=0;(($d=@substr_count($s,1,$a,$n))>$c&&($b=$a)&&($c=$d))||$a++<strlen($s););echo $b;`

http://3v4l.org/J4vqa

variables `$s` and `$n` should be defined on the command line to the search string and substring length, respectively.

This would also work in any C-like language with appropriate functions for `substr_count()` and `strlen()`.

# Answer
> 3 votes
# K (ngn/k), ~~11~~ 6 bytes

```
*>+/':

```

Try it online!

Uses the "argmax" trick from Bubbler's answer.

* `+/':` do a window-reduce (with the first implicit arg being the window length, and the second the sequence)
* `*>` argmax/index of first maximum

# Answer
> 2 votes
### C# (Linq), 148 bytes

```
using System.Linq;class C{int F(string s,int l){return s.IndexOf(s.Skip(l-1).Select((c,i)=>s.Substring(i,l)).OrderBy(p=>-p.Sum(c=>c)).First());}}

```

Formatted:

```
using System.Linq;

class C
{
    int F(string s, int l)
    {
        return s.IndexOf(
            s
                .Skip(l - 1)
                .Select((c, i) => s.Substring(i, l))
                .OrderBy(p => -p.Sum(c => c))
                .First()
        );
    }
}

```

Takes input as method params.

What it does:

```
string result = s // string is also char collection
    .Skip(l - 1) // make it collection shorter by l-1
    .Select((c, i) => s.Substring(i, l)) // so we can iterate, and select all substrings
    .OrderBy(p => -p.Sum(c => c)) // order substrings descending by sum of characters
    .First() // take first (most ones)

return s.IndexOf(result); // find index of result string

```

# Answer
> 2 votes
# Scala - 70 Bytes

```
readLine.sliding(readInt).zipWithIndex.maxBy(x=>x._1.count(_=='1'))._2

```

But with function names as long as *zipWithIndex* I guess Scala is not the best choice for code golf.

# Answer
> 2 votes
### C, ~~245~~ 185

```
#include <stdio.h>
main(int argc,char **argv){char *p,*q;int i,s,m=0;for(p=argv[1];*p;p++){for(s=0,q=p;q-p<atoi(argv[2])&&*q;q++)s+=*q-'0';if(s>m){m=s;i=p-argv[1];}}printf("%d\n", i);}

```

**Formatted:**

```
#include <stdio.h>
main(int argc, char **argv) {
        char *p, *q;
        int i, s, m = 0;
        for (p = argv[1]; *p; p++) {
                for (s = 0, q = p; q - p < atoi(argv[2]) && *q; q++)
                        s += *q - '0';
                if (s > m) {
                        m = s;
                        i = p - argv[1];
                }
        }
        printf("%d\n", i);
}

```

**Usage:**

```
$ ./m1s 01001010101101111011101001010100010101101010101010101101101010010110110110 5
10

```

# Answer
> 2 votes
# Jelly, 5 bytes

```
ṡ§MḢ’

```

Try it online!

## How it works

```
ṡ§MḢ’ - Main link. Takes the sequence s on the left and the length n on the right
ṡ     - Overlapping slices of s of length n
 §    - Sum of each slice
  M   - Indices of the maximal element
   Ḣ  - First (smallest) one
    ’ - Decrement as Jelly uses 1 indexing

```

# Answer
> 2 votes
# Perl 5 `-pl`, 50 bytes

```
$i++,$;[y/1//]||=$i-1for<>=~/(?=(.{$_}))/g;$_=pop@

```

Try it online!

Input is on two lines with the length first and then the string.

# Answer
> 1 votes
# CJam, ~~25~~ 21 bytes

```
q~_,,{1$>2$<:+~}$(]W=

```

Test it here.

Takes input as an integer for the substring length, and an array of zeroes and ones as the sequence:

```
5
[0 1 0 0 1 0 1 0 1 0 1 1 0 1 1 1 1 0 1 1 1 0 1 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 0 1 1 0 1 1 0]

```

## Explanation

```
q~_,,{1$>2$<:+~}$(p];
q~                    "Read and evaluate the input.";
  _,                  "Duplicate the sequence and get its length N.";
    ,                 "Get an array [0 1 ... N-1].";
     {         }$     "Sort this array stably by the result of the given block.";
      1$              "Copy the sequence.";
        >             "Slice off the first i bits.";
         2$           "Copy the substring length.";
           <          "Truncate the sequence.";
            :+        "Get the sum to find the number of 1s.":
              ~       "Bitwise complement in order to sort from highest to lowest.";
                 (    "Shift off the first index from the sorted list.";
                  ]   "Wrap the entire stack in an array.";
                   W= "Extract the last element (the result), discarding the rest.";

```

The result is printed automatically at the end of the program.

Note that I'm also considering slices that start closer to the end than the desired substring length, but that's okay, because they are substrings of the last valid substring and will therefore never have more `1`s than that last valid substring.

# Answer
> 1 votes
## Java 329 bytes

was going to implent a .matches(regex), but it would have been near identical to the python solutions above, so i tried a sliding window instead. new here, so if anyone has any pointers be glad to hear them.

```
public class ssMostOnes{
public static void main(String[] a){
    int b=0,w=0;
    for(int i=0;i<a[0].length()-Integer.valueOf(a[1]);i++){
        int c=a[0].substring(i,i+Integer.valueOf(a[1])).length() - a[0].substring(i,i+Integer.valueOf(a[1])).replace("1","").length();
        if(c>w){w=c;b=i;}
    }
    System.out.println(b);
}

```

}

# Answer
> 1 votes
# Burlesque, 12 bytes

```
J'0;;qL[>mss

```

Try it online!

```
J     # Duplicate input
'0;;  # Split by 0s
qL[>m # Maximum by length
ss    # Find index of substring in original

```

---
Tags: code-golf, string, binary
---


title: Bootstrap JSF**k

text:
# Question
Title: Bootstrap JSF**k
In Javascript you can recover the complete language using only the symbols `()[]!+`. Here's the basics:

```
false       =>  ![]
true        =>  !![]
undefined   =>  [][[]]
NaN         =>  +[![]]
0           =>  +[]
1           =>  +!+[]
2           =>  !+[]+!+[]
10          =>  [+!+[]]+[+[]]
Array       =>  []
Number      =>  +[]
String      =>  []+[]
Boolean     =>  ![]
Function    =>  []["filter"]
eval        =>  []["filter"]["constructor"]( CODE )()
window      =>  []["filter"]["constructor"]("return this")()

```

That's great and all, but where did they get those first 6 characters from? I think it's best we help them out.

---

Simply write a program or function that outputs (at least) the 6 characters `[]()!+` in any order you want, as many times as you want, with as many other characters in between as you want. Shortest code wins. Gold star if you use less than 6 unique characters to do so.

# Answer
> 10 votes
# Bash + iw, ~~6~~ 4 bytes

```
iw w

```

Prints those six characters (and a lot more).

### Output

```
Usage:  iw [options] command
Options:
        --debug         enable netlink debugging
        --version       show version (3.11)
Commands:
        help [command]
                Print usage for all or a specific command, e.g.
                "help wowlan" or "help wowlan enable".
        event [-t] [-r] [-f]
                Monitor events from the kernel.
                -t - print timestamp
                -r - print relative timstamp
                -f - print full frame for auth/assoc etc.
        features

        commands
                list all known commands and their decimal & hex value
        phy
        list
                List all wireless devices and their capabilities.
        phy <phyname> info
                Show capabilities for the specified wireless device.
        dev
                List all network interfaces for wireless hardware.
        dev <devname> info
                Show information for this interface.
        dev <devname> del
                Remove this virtual interface
        dev <devname> interface add <name> type <type> [mesh_id <meshid>] [4addr on|off] [flags <flag>*]
        phy <phyname> interface add <name> type <type> [mesh_id <meshid>] [4addr on|off] [flags <flag>*]
                Add a new virtual interface with the given configuration.
                Valid interface types are: managed, ibss, monitor, mesh, wds.

                The flags are only used for monitor interfaces, valid flags are:
                none:     no special flags
                fcsfail:  show frames with FCS errors
                control:  show control frames
                otherbss: show frames from other BSSes
                cook:     use cooked mode
                active:   use active mode (ACK incoming unicast packets)

                The mesh_id is used only for mesh mode.
        dev <devname> ibss join <SSID> <freq in MHz> [HT20|HT40+|HT40-|NOHT] [fixed-freq] [<fixed bssid>] [beacon-interval <TU>] [basic-rates <rate in Mbps,rate2,...>] [mcast-rate <rate in Mbps>] [key d:0:abcde]
                Join the IBSS cell with the given SSID, if it doesn't exist create
                it on the given frequency. When fixed frequency is requested, don't
                join/create a cell on a different frequency. When a fixed BSSID is
                requested use that BSSID and do not adopt another cell's BSSID even
                if it has higher TSF and the same SSID. If an IBSS is created, create
                it with the specified basic-rates, multicast-rate and beacon-interval.
        dev <devname> ibss leave
                Leave the current IBSS cell.
        dev <devname> station dump
                List all stations known, e.g. the AP on managed interfaces
        dev <devname> station set <MAC address> mesh_power_mode <active|light|deep>
                Set link-specific mesh power mode for this station
        dev <devname> station set <MAC address> vlan <ifindex>
                Set an AP VLAN for this station.
        dev <devname> station set <MAC address> plink_action <open|block>
                Set mesh peer link action for this station (peer).
        dev <devname> station del <MAC address>
                Remove the given station entry (use with caution!)
        dev <devname> station get <MAC address>
                Get information for a specific station.
        dev <devname> survey dump
                List all gathered channel survey data
        dev <devname> mesh leave
                Leave a mesh.
        dev <devname> mesh join <mesh ID> [mcast-rate <rate in Mbps>] [beacon-interval <time in TUs>] [dtim-period <value>] [vendor_sync on|off] [<param>=<value>]*
                Join a mesh with the given mesh ID with mcast-rate and mesh parameters.
        dev <devname> mpath dump
                List known mesh paths.
        dev <devname> mpath set <destination MAC address> next_hop <next hop MAC address>
                Set an existing mesh path's next hop.
        dev <devname> mpath new <destination MAC address> next_hop <next hop MAC address>
                Create a new mesh path (instead of relying on automatic discovery).
        dev <devname> mpath del <MAC address>
                Remove the mesh path to the given node.
        dev <devname> mpath get <MAC address>
                Get information on mesh path to the given node.
        dev <devname> scan [-u] [freq <freq>*] [ies <hex as 00:11:..>] [meshid <meshid>] [lowpri,flush,ap-force] [ssid <ssid>*|passive]
                Scan on the given frequencies and probe for the given SSIDs
                (or wildcard if not given) unless passive scanning is requested.
                If -u is specified print unknown data in the scan results.
                Specified (vendor) IEs must be well-formed.
        dev <devname> scan trigger [freq <freq>*] [ies <hex as 00:11:..>] [meshid <meshid>] [lowpri,flush,ap-force] [ssid <ssid>*|passive]
                Trigger a scan on the given frequencies with probing for the given
                SSIDs (or wildcard if not given) unless passive scanning is requested.
        dev <devname> scan dump [-u]
                Dump the current scan results. If -u is specified, print unknown
                data in scan results.
        reg get
                Print out the kernel's current regulatory domain information.
        reg set <ISO/IEC 3166-1 alpha2>
                Notify the kernel about the current regulatory domain.
        dev <devname> auth <SSID> <bssid> <type:open|shared> <freq in MHz> [key 0:abcde d:1:6162636465]
                Authenticate with the given network.

        dev <devname> connect [-w] <SSID> [<freq in MHz>] [<bssid>] [key 0:abcde d:1:6162636465]
                Join the network with the given SSID (and frequency, BSSID).
                With -w, wait for the connect to finish or fail.
        dev <devname> disconnect
                Disconnect from the current network.
        dev <devname> link
                Print information about the current link, if any.
        dev <devname> offchannel <freq> <duration>
                Leave operating channel and go to the given channel for a while.
        dev <devname> cqm rssi <threshold|off> [<hysteresis>]
                Set connection quality monitor RSSI threshold.

        phy <phyname> wowlan show
                Show WoWLAN status.
        phy <phyname> wowlan disable
                Disable WoWLAN.
        phy <phyname> wowlan enable [any] [disconnect] [magic-packet] [gtk-rekey-failure] [eap-identity-request] [4way-handshake] [rfkill-release] [tcp <config-file>] [patterns [offset1+]<pattern1> ...]
                Enable WoWLAN with the given triggers.
                Each pattern is given as a bytestring with '-' in places where any byte
                may be present, e.g. 00:11:22:-:44 will match 00:11:22:33:44 and
                00:11:22:33:ff:44 etc.
                Offset and pattern should be separated by '+', e.g. 18+43:34:00:12 will match '43:34:00:12' after 18 bytes of offset in Rx packet.

                The TCP configuration file contains:
                  source=ip[:port]
                  dest=ip:port@mac
                  data=<hex data packet>
                  data.interval=seconds
                  [wake=<hex packet with masked out bytes indicated by '-'>]
                  [data.seq=len,offset[,start]]
                  [data.tok=len,offset,<token stream>]
        phy <phyname> coalesce show
                Show coalesce status.
        phy <phyname> coalesce disable
                Disable coalesce.
        phy <phyname> coalesce enable <config-file>
                Enable coalesce with given configuration.
                The configuration file contains coalesce rules:
                  delay=<delay>
                  condition=<condition>
                  patterns=<[offset1+]<pattern1>,<[offset2+]<pattern2>,...>
                  delay=<delay>
                  condition=<condition>
                  patterns=<[offset1+]<pattern1>,<[offset2+]<pattern2>,...>
                  ...
                delay: maximum coalescing delay in msec.
                condition: 1/0 i.e. 'not match'/'match' the patterns
                patterns: each pattern is given as a bytestring with '-' in
                places where any byte may be present, e.g. 00:11:22:-:44 will
                match 00:11:22:33:44 and 00:11:22:33:ff:44 etc. Offset and
                pattern should be separated by '+', e.g. 18+43:34:00:12 will
                match '43:34:00:12' after 18 bytes of offset in Rx packet.

        dev <devname> roc start <freq> <time in ms>

        wdev <idx> p2p stop

        wdev <idx> p2p start

        phy <phyname> set antenna <bitmap> | all | <tx bitmap> <rx bitmap>
                Set a bitmap of allowed antennas to use for TX and RX.
                The driver may reject antenna configurations it cannot support.
        dev <devname> set txpower <auto|fixed|limit> [<tx power in mBm>]
                Specify transmit power level and setting type.
        phy <phyname> set txpower <auto|fixed|limit> [<tx power in mBm>]
                Specify transmit power level and setting type.
        phy <phyname> set distance <distance>
                Set appropriate coverage class for given link distance in meters.
                Valid values: 0 - 114750
        phy <phyname> set coverage <coverage class>
                Set coverage class (1 for every 3 usec of air propagation time).
                Valid values: 0 - 255.
        phy <phyname> set netns <pid>
                Put this wireless device into a different network namespace
        phy <phyname> set rts <rts threshold|off>
                Set rts threshold.
        phy <phyname> set frag <fragmentation threshold|off>
                Set fragmentation threshold.
        dev <devname> set channel <channel> [HT20|HT40+|HT40-]
        phy <phyname> set channel <channel> [HT20|HT40+|HT40-]
        dev <devname> set freq <freq> [HT20|HT40+|HT40-]
        dev <devname> set freq <control freq> [20|40|80|80+80|160] [<center freq 1>] [<center freq 2>]
        phy <phyname> set freq <freq> [HT20|HT40+|HT40-]
                Set frequency/channel the hardware is using, including HT
                configuration.
        phy <phyname> set name <new name>
                Rename this wireless device.
        dev <devname> set mcast_rate <rate in Mbps>
                Set the multicast bitrate.
        dev <devname> set peer <MAC address>
                Set interface WDS peer.
        dev <devname> set noack_map <map>
                Set the NoAck map for the TIDs. (0x0009 = BE, 0x0006 = BK, 0x0030 = VI, 0x00C0 = VO)
        dev <devname> set 4addr <on|off>
                Set interface 4addr (WDS) mode.
        dev <devname> set type <type>
                Set interface type/mode.
                Valid interface types are: managed, ibss, monitor, mesh, wds.
        dev <devname> set meshid <meshid>
        dev <devname> set monitor <flag>*
                Set monitor flags. Valid flags are:
                none:     no special flags
                fcsfail:  show frames with FCS errors
                control:  show control frames
                otherbss: show frames from other BSSes
                cook:     use cooked mode
                active:   use active mode (ACK incoming unicast packets)
        dev <devname> set mesh_param <param>=<value> [<param>=<value>]*
                Set mesh parameter (run command without any to see available ones).
        dev <devname> set power_save <on|off>
                Set power save state to on or off.
        dev <devname> set bitrates [legacy-<2.4|5> <legacy rate in Mbps>*] [mcs-<2.4|5> <MCS index>*]
                Sets up the specified rate masks.
                Not passing any arguments would clear the existing mask (if any).
        dev <devname> get mesh_param [<param>]
                Retrieve mesh parameter (run command without any to see available ones).
        dev <devname> get power_save <param>
                Retrieve power save state.
Commands that use the netdev ('dev') can also be given the
'wdev' instead to identify the device.
You can omit the 'phy' or 'dev' if the identification is unique,
e.g. "iw wlan0 info" or "iw phy0 info". (Don't when scripting.)
Do NOT screenscrape this tool, we don't consider its output stable.

```

# Answer
> 4 votes
# GS2, 1 byte

Code:

```
ç

```

Try it online!

# Answer
> 4 votes
# Brain-Flak, ~~42~~ 40 + 3 = 43 bytes

Try it online

```
((((((()()()){}){}){}){}){}){(({})[()])}

```

It pushes 96 and loops through pushing every number smaller than 96. This requires the `-A` flag to run.

I suppose I get the "gold star" for what it's worth

# Answer
> 4 votes
# Brainfuck, 5 bytes

```
+[+.]

```

Try it online!

## Explanation

Increments the byte under the data pointer, then loops while the byte under the data pointer is not zero (until the value overflows and gets back to zero), incrementing and printing the value.

# Answer
> 3 votes
# Jelly, 3 bytes

```
³RỌ

```

Try it online!

# Answer
> 3 votes
## Sh, ~~16~~ 12 bytes

```
cat /dev/mem

```

Since you visited this page, `/dev/mem` must contain `[]()!+`, and anyway statistics says your RAM must contains the characters `[]()!+`

# Answer
> 3 votes
## CJam, 3 bytes

```
'^,

```

Try it online!

Prints all ASCII up to and including `]`.

# Answer
> 3 votes
## Pyke, 2 bytes

```
~a

```

Try it here!

Prints every char in range(0, 255)

# Answer
> 3 votes
# Perl 6, 12 bytes

```
put '!'..']'

```

```
put '[]()!+'

```

```
'[]()!+'.say

```

```
say ['()!+']

```

I think it is fairly conclusive that the minimum is 12 bytes.

# Answer
> 2 votes
## , 12 bytes

```
∅O("[]()!+")

```

Outputs `[]()!+`

# Answer
> 1 votes
# Python 2, 13 bytes

```
print'[]()!+'

```

Prints `[]()!+`

# Answer
> 0 votes
# Powershell, 10 different chars, 15 bytes

```
[char[]](1..99)

```

Explanation:

```
[char[]](1..1000)
        (x .. y)  #Range x y
[      ]          #Cast to
 char[]           #char array
                  #implict output(arrays are seperated by \n

```

Don't put this in a file. Because then the `implict output` doesn't work!

# Answer
> 0 votes
# 05AB1E, 2 bytes

```
žQ

```

Try it online!

Pushes the printable ASCII stack and implicitly prints it. The printable ASCII character set includes the JSFk characters.

# Answer
> 0 votes
# Text, 6 bytes

```
[]()!+

```

The challenge is quite uninteresting, so I made a quite uninteresting answer.

## Also works in (Try It Online)

PHP, ///, ReRegex, Canvas, Chain, ink, Charcoal, Corea, M4, and a lot more...

---
Tags: code-golf, kolmogorov-complexity
---


# Question
Title: Write a function that returns an iterable object of all valid points 4-directionally adjacent to (x, y)
A very common need in algorithms classes and computer science in general is to iterate 4-directionally over a grid or matrix (such as in BFS or DFS). This seems to often result in a lot of clunky and verbose code with a lot of arithmetic and comparisons within loops. I've seen many different approaches to this, but I can't shake the feeling that there's a more concise way to do this.

The challenge is to write a pure function that, given the width and height of a finite plane `n, m` originating at point `(0,0)`, and coordinates `(x,y)` that can represent any valid point within that plane, returns an iterable object of all points within the plane that are 4-directionally adjacent to `(x,y)`.

The goal is to define that function in as few bytes as possible.

Some examples to help illustrate valid input/output:

```
n = 5 (y-axis), m = 3 (x-axis) (zero-based)

matrix = [
    [A, B, C],
    [D, E, F],
    [G, H, I],
    [J, K, L],
    [M, N, O],
]

(x, y) => [valid iterable points]

E: (1, 1) => [(1, 0), (2, 1), (1, 2), (0, 1)]
A: (0, 0) => [(1, 0), (0, 1)]
L: (2, 3) => [(2, 2), (2, 4), (1, 3)]
N: (1, 4) => [(1, 3), (2, 4), (0, 4)]

```

```
n = 1 (y-axis), m = 1 (x-axis) (zero-based)

matrix = [
    [A],
]

(x, y) => [valid iterable points]

A: (0, 0) => []

```

```
n = 2 (y-axis), m = 1 (x-axis) (zero-based)

matrix = [
    [A],
    [B],
]

(x, y) => [valid iterable points]

A: (0, 0) => [(0, 1)]
B: (0, 1) => [(0, 0)]

```

And here's an example (this one in Python) of a function that satisfies the conditions:

```
def four_directions(x, y, n, m):
    valid_coordinates = []
    for xd, yd in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        nx, ny = x + xd, y + yd
        if 0 <= nx < m and 0 <= ny < n:
            valid_coordinates.append((nx, ny))
    return valid_coordinates

```

The example above defined a named function, but anonymous functions are also acceptable.

The inputs `n, m, x, y` are all unsigned 32-bit integers within the following ranges:

```
n > 0
m > 0
0 <= x < m
0 <= y < n

```

The output must take the form of an iterable (however your language of choice defines that) of (x, y) pairs.

*Additional clarifications:*

Complex numbers (and other representations/serializations) are OK as long as the consumer of the iterable can access `x` and `y` as integers knowing only their location.

Non-zero-based indexes are acceptable, but only if the language of choice is a non-zero-indexed language. If the language uses a mix of numbering systems, default to the numbering system of the data structure most commonly used to represent a matrix. If these are still all foreign concepts in the given language, any starting index is acceptable.

# Answer
> 13 votes
# Python 2, 66 bytes

```
lambda m,n,x,y:[(x-1,y),(x+1,y)][~x:m-x]+[(x,y-1),(x,y+1)][~y:n-y]

```

Try it online!

Lists the four neighbors, then uses list slicing to remove those that are out-of-bounds.

---

# Python 2, 71 bytes

```
lambda m,n,x,y:[(k/n,k%n)for k in range(m*n)if(k/n-x)**2+(k%n-y)**2==1]

```

Try it online!

Instead of checking which of the four neighbors are in-bounds, we do it the slower way of checking all in-bounds points for those that are neighbors, that is have Euclidian distance exactly 1 from `(x,y)`. We also use the classic div-mod trick to iterate over a grid, saving the need to write two loops like `for i in range(m)for j in range(n)`.

I tried using complex arithmetic to write the distance condition, but it turned out longer to write `abs((k/n-x)*1j+k%n-y)==1`.

---

# Python 2, 70 bytes

```
lambda m,n,x,y:[(x+t/3,y+t%3-1)for t in-2,0,2,4if m>x+t/3>=0<y+t%3<=n]

```

Try it online!

# Answer
> 6 votes
# Octave, 90 bytes

This uses a geometric approach: First we create an matrix of zeros of the desired size, and set a `1` to the desired location. Then we convolve with the kernel

```
[0, 1, 0]
[1, 0, 1]
[0, 1, 0]

```

which produces a new matrix of the same size with ones at the 4-neighbours of the original point. Then we `find()` the indices of the nonzero entries of this new matrix.

```
function [i,j]=f(s,a,b);z=zeros(s);z(a,b)=1;[i,j]=find(conv2(z,(v=[1;-1;1])*v'<0,'same'));

```

Try it online!

convolution is the key to success.

# Answer
> 3 votes
# Wolfram Language (Mathematica), ~~42~~ 37 bytes

```
pNorm[{##}-p]&~Array~#~Position~1&

```

Try it online!

Input `[{x,y}][{m,n}]`. 1-indexed, following Mathematica's convention.

# Answer
> 3 votes
# JavaScript (ES6), 74 bytes

Boring approach.

```
(h,w,x,y)=>[x&&[x-1,y],~x+w&&[x+1,y],y&&[x,y-1],++y-h&&[x,y]].filter(_=>_)

```

Try it online!

---

# JavaScript (Node.js), 74 bytes

Less boring but just as long. Takes input as `([h,w,x,y])`.

```
a=>a.flatMap((_,d,[h,w,x,y])=>~(x+=--d%2)*~(y+=--d%2)&&x<w&y<h?[[x,y]]:[])

```

Try it online!

---

# JavaScript (V8), 67 bytes

If all standard output methods were allowed, we could just print the valid coordinates with:

```
(h,w,x,y)=>{for(;h--;)for(X=w;X--;)(x-X)**2+(y-h)**2^1||print(X,h)}

```

Try it online!

# Answer
> 3 votes
# Jelly,  ~~13~~  12 bytes

```
2ḶṚƬNƬẎ+⁸%ƑƇ

```

A dyadic Link accepting a list of two (0-indexed) integers on the left, `[row, column]`, and two integers on the right, `[height, width]`, which yields a list of lists of integers, `[[adjacent_row_1, adjacent_column_1], ...]`.

**Try it online!**

### How?

```
2ḶṚƬNƬẎ+⁸%ƑƇ - Link: [row, column]; [height, width]   e.g. [3,2]; [5,3] (the "L" example)
2            - literal 2                                   2
 Ḷ           - lowered range                               [0,1]
   Ƭ         - collect up while distinct, applying:
  Ṛ          -   reverse                                   [[0,1],[1,0]]
     Ƭ       - collect up while distinct, applying:
    N        -   negate                                    [[[0,1],[1,0]],[[0,-1],[-1,0]]]
      Ẏ      - tighten                                     [[0,1],[1,0],[0,-1],[-1,0]]
        ⁸    - chain's left argument ([row, column])       [3,2]
       +     - add (vectorises)                            [[3,3],[4,2],[3,1],[2,2]]
           Ƈ - filter keep if:
          Ƒ  -   is invariant under:
         %   -     modulo ([height, width]) (vectorises)    [3,0] [4,2] [3,1] [2,2]
             - (...and [3,0] is not equal to [3,3] so ->)  [[4,2],[3,1],[2,2]]

```

# Answer
> 2 votes
# Perl 6, ~~56~~ 49 bytes

*-7 bytes thanks to nwellnhof!*

```
{grep 1>(*.reals Z/@^b).all>=0,($^a X+1,-1,i,-i)}

```

Try it online!

Removes the out of bounds elements by checking if when divided by the array bounds it is between 0 and 1. Takes input and output via complex numbers where the real part is the `x` coordinate and the imaginary is the `y`. You can extract these through the `.im` and `.re` functions.

# Answer
> 1 votes
# , ~~30~~ ~~29~~ 28 bytes

```
(([+.@#~&,1=|@-)j./)~j./&i./

```

Try it online!

How:

* Turn the right hand `m` x `n` arg into a grid of complex numbers `j./&i./`
* Same for left arg (our point) `j./`
* Create a mask showing where the distance between our point and the grid is exactly 1 `1=|@-`
* Use that to filter the grid, after flattening both `#~&,`
* Turn the result back into real points `+.@`

# Answer
> 1 votes
# Haskell, 62 bytes

Using

```
f m n a b = [(x,y)|x<-[0..m-1],y<-[0..n-1],(x-a)^2+(y-b)^2==1]

```

Try it online!

Boring approach: 81 bytes

```
f m n x y=filter (\(x,y)->x>=0&&y>=0&&x<m&&y<n) [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]

```

# Answer
> 0 votes
# C# (Visual C# Interactive Compiler), 91 bytes

```
(a,b,x,y)=>new[]{(x+1,y),(x-1,y),(x,y+1),(x,y-1)}.Where(d=>((x,y)=d,p:x>=0&x<a&y>=0&y<b).p)

```

Try it online!

Alternatively:

```
(a,b,x,y)=>new[]{(x+1,y),(x-1,y),(x,y+1),(x,y-1)}.Where(d=>((x,y)=d).Item1>=0&x<a&y>=0&y<b)

```

Try it online!

# Answer
> 0 votes
# Charcoal, 29 bytes

```
Ｊθη#ＦＩζＦＩε«Ｊικ¿№ＫＶ#⊞υ⟦ικ⟧»⎚Ｉυ

```

Try it online! Link is to verbose version of code. Takes inputs in the order x, y, width, height. Explanation:

```
Ｊθη#

```

Print a `#` at the provided position.

```
ＦＩζＦＩε«

```

Loop over the given rectangle.

```
Ｊικ

```

Jump to the current position.

```
¿№ＫＶ#⊞υ⟦ικ⟧

```

If there's an adjacent `#` then save the position.

```
»⎚Ｉυ

```

Output the discovered positions at the end of the loop.

Boring answer:

```
ＦＩζＦＩε¿⁼¹⁺↔⁻ιＩθ↔⁻κＩηＩ⟦ικ

```

Try it online! Link is to verbose version of code. Works by finding the adjacent positions mathematically.

# Answer
> 0 votes
# Pip `-xp`, 18 bytes

```
$ALaCGbFI1=$+:_ADc

```

Takes three command-line arguments: m, n, and a list containing x & y. Replit! Or, here's a similar program in Pip Classic with a header to simulate the `-x` flag: Try it online!

### Explanation

Generates a list of all points in the valid rectangle and filters for the ones that are one unit away from the given point.

```
$ALaCGbFI1=$+:_ADc
   aCGb             Generate a coordinate grid of a rows and b columns
$AL                 Fold on append-list: flatten once, giving a list of coord pairs
       FI           Filter on this function:
              _      The argument
               AD    Absolute difference (element-wise) with
                 c   The program's third argument
           $+:       The sum of the resulting pair
         1=          Must equal 1

```

---
Tags: code-golf, geometry
---


title: How to shorten the python code?

text:
# Question
Title: How to shorten the python code?
I'm writing a program that takes a number from input (call it x), loops from 0 to (x - 1) (let's call our iterator y) and prints \\$y^x+x\\$ for each y.

After the loop, it then prints "SUM: N" (without a newline) where the N is the sum of the all of the previously printed values.

How can I make the code I already have shorter?

Code (Python 3, 98 bytes):

```
E=print
A=int(input())
B=[]
for D in range(A):C=D**A+A;B.append(C);E(C)
E(end='SUM: '+str(sum(B)))

```

Try it online!

# Answer
# My attempt, ~~86~~ 79 bytes

```
E=print
A=int(input())
E(end='SUM: %d'%sum(E(C:=D**A+A)or C for D in range(A)))

```

Try it online!

Thanks to dingledooper for shaving off 7 bytes by removing the need for `B`.

We embed the assignment in a list comprehension for -9 bytes. `print` returns a falsy value, so `E(C:=D**A+A)or C` returns `C` which is collected into the generator `E(C:=D**A+A)or C for D in range(A)` that is passed to `sum`.

We also format the output with a `%d` to save bytes off `str`.
> 8 votes

# Answer
Just a different approach to reduce your code to 86 bytes. You don't need to rename the `print` function. The only thing you need is to first compute all the values and only then print them:

```
A=int(input())
B=[D**A+A for D in range(A)]
print(*B,f'SUM: {sum(B)}',sep='\n',end='')

```

Try it online!
> 11 votes

# Answer
Doing it in a list comprehension is a waste of time, it seems, mainly since you have to have a separate print statement for the final sum (due to the no-newline limit).

97 bytes:

```
E=print
f=lambda x:[E(g:=i**x+x)or g for i in range(x)]
E(end='SUM: '+str(sum(f(int(input())))))

```

Instead, there's a couple changes I noted.

```
E=print
A=int(input())
B=[]
for D in range(A):C=D**A+A;B.append(C);E(C)
E(end='SUM: '+str(sum(B)))

```

First, you can do `B+=[C]` instead of `B.append(C)`. That loses 5 bytes for 93. But we can also just use B as an integer and add - that saves us from having to do a sum later, so we can shave off a total of 11 for a total of 85.

```
E=print
A=int(input())
B=0
for D in range(A):C=D**A+A;B+=C;E(C)
E(end='SUM: '+str(B))

```

We can then do an inline variable assignment when printing `D**A+A` to save bytes as well, from `C=D**A+A;B+=C;E(C)` to `E(G:=D**A+A);B+=G`. This saves one byte, for 84 bytes.

```
E=print
A=int(input())
B=0
for D in range(A):E(G:=D**A+A);B+=G
E(end='SUM: '+str(B))

```

Lastly, calling `str` is long and unwieldy. There's no backticks to call `repr` like in Python 2, but we can just use autocasting print arguments to do it anyway. From `E(end='SUM: '+str(B))` to just `E('SUM: ',B,end='')`. We add two single quotes and a comma, but lose out on 5 bytes from the `str()`, for a total of -2 and a final byte count of 83.

```
E=print
B=0
A=int(input())
for D in range(A):E(G:=D**A+A);B+=G
E('SUM: ',B,end='')

```
> 5 votes

# Answer
Instead of adding all the terms to a list and calling `sum`, it's a lot shorter to keep a running total. This gets the solution down to 85 bytes:

```
E=print
A=int(input())
S=0
for D in range(A):C=D**A+A;S+=C;E(C)
E(end='SUM: '+str(S))

```

From here, two more optimizations can be made. The first is to make use of f-strings, saving three bytes. The second is to convert the for loop to a while loop, which saves another byte. With this we get an 81-byte solution:

```
E=print
A=int(input())
S=D=0
while D<A:C=D**A+A;S+=C;E(C);D+=1
E(end=f'SUM: {S}')

```

For Python \>=3.8, you can also utilize the walrus operator to save 1 more byte.

```
E=print
A=int(input())
S=D=0
while D<A:E(C:=D**A+A);S+=C;D+=1
E(end=f'SUM: {S}')

```
> 3 votes

---
Tags: code-golf, tips, python
---


title: Exchange capitalization

text:
# Question
Title: Exchange capitalization
Given two strings of letters, transfer the capitalization pattern of each string onto the other one. Fewest bytes wins.

```
Input:   CodeGolf xxPPCGxx
Output:  coDEGOlf XxppCgxx

```
* Both strings will be equal-length and nonempty, with only letters `a..z` and `A..Z`.
* You may output the two resulting strings in either order relative to the inputs.
* You may represent a pair of strings as one string with a non-letter single-character separator for input and/or output.
* You may represent a string as a list of characters or one-character strings, but not as a sequence of code point values unless these are simply strings in your language.
* Your input and output may represent strings differently.

**Test cases:**

```
CodeGolf xxPPCGxx -> coDEGOlf XxppCgxx
lower UPPER -> LOWER upper
MiXeD lower -> mixed LoWeR
A A -> A A
ABcd EfGh -> AbCd EFgh

```

# Answer
# Java (JDK 10), 66 bytes

```
a->b->{for(int i=a.length,t;i-->0;b[i]^=t)a[i]^=t=(a[i]^b[i])&32;}

```

Try it online!

## Explanations

```
a->b->{                           // Curried lambda
 for(int i=a.length,t;i-->0;      //  Descending loop on i,
                                  //  Declare t
     b[i]^=t                      //   Apply the case difference to b[i]
   )
  a[i]^=t=(a[i]^b[i])&32;         //   Assign the case difference of the two letters to t, and apply it to a[i].
}

```
> 15 votes

# Answer
# C (gcc), ~~86~~ ~~58~~ ~~55~~ 53 bytes

```
c(a,s,e)char*a,*s;{for(;*s++^=e=(*s^*a)&32;)*a++^=e;}

```

Try it online!
> 13 votes

# Answer
# Jelly, 9 bytes

```
O&32^/^OỌ

```

Try it online!

### How it works

```
O&32^/^OỌ  Main link. Argument: [s, t] (pair of strings)

O          Ordinal; replace each character with its code point.
 &32       Perform bitwise AND with 32, yielding 32 for lowercase letters, 0 for
           uppercase ones.
    ^/     Reduce by XOR, yielding 32 for letter pairs with different
           capitalizations, 0 for letter pair with matching capitalizations.
      ^O   XOR the result with each of the code points.
        Ọ  Unordinal; replace each code point with its character.

```
> 9 votes

# Answer
# APL (Dyalog Classic), ~~13~~ 12 bytes

```
⊖⊖819⌶¨⍨∊∘⎕a

```

Try it online!

input and output is a 2×N character matrix

`⎕a` is the uppercase English alphabet `'ABC...Z'`

`∊∘⎕a` returns a boolean matrix indicating which letters in the input are uppercase

`819⌶` converts its right argument to uppercase or lowercase depending on its boolean left argument ("819" is leetspeak for "BIG")

`819⌶¨⍨` does that for each (`¨`) character, swapping () the arguments

means reverse vertically; one  acts as the left argument to `819⌶` and the other is the final action
> 7 votes

# Answer
# Pyth, 10 bytes

```
rVV_mmrIk1

```

Try it here!

### Explanation & neat Pyth tricks used

* `rVV_mmrIk1` — Full program. Input is taken from STDIN as a list of two strings, and the output is written to STDOUT as a list of two lists of characters.
* `mm` — For each character in each of the strings:

+ `Ik` — Check if it is invariant under...
    + `r...1` — ... Converting to uppercase. Yields **True** for uppercase characters and **False** for lowercase ones.
* `_` — Reverse that list.
* `VV` — And double-vectorize the following function over the two lists:

+ `r` — Convert to uppercase if the value is `True` (aka `1`), else convert to lowercase.

This submission abuses the fact that `r0` and `r1` are the lowercase and uppercase functions in Pyth, and we use truth values (the values obtained by checking if each character is uppercase, reversed) yielding `True` for uppercase and `False` for lowercase. The fact that booleans are subclasses of integers in Python is very handy for the approach this answer is using. Porting Dennis and Jonathan's Jelly approaches both resulted in more than 18 bytes, so I am quite happy with the Pyth-specific tricks used here.
> 6 votes

# Answer
# MATL, 11 bytes

```
kG91<P32*-c

```

Try it online! Or verify all test cases.

### Explanation

```
k      % Implicit input: 2-row char matrix. Convert to lower-case
G      % Push input again
91<    % Less than 91?, element-wise. Gives 1 for upper-case
P      % Flip vertically
32*    % Multiply by 32, element-wise
-      % Subtract, element-wise
c      % Convert to char. Implicit display

```
> 4 votes

# Answer
# Haskell, 78 bytes

```
import Data.Char
c x|isUpper x=toUpper|1<2=toLower
(!)=zipWith c
x#y=(y!x,x!y)

```

Try it online!
> 4 votes

# Answer
# x86-64 machine code, 14 bytes

Callable from C (x86-64 SysV calling convention) with this prototype:

```
void casexchg(char *rdi, char *rsi);  // modify both strings in place

```

An explicit-length version with length in `rcx` is the same size. `void casexchg(char *rdi, char *rsi, int dummy, size_t len);`

---

This uses the same bit-exchange algo as the C and Java answers: **If both letters are the same case, neither needs to change. If they're opposite case, they both need to change.**

Use XOR to diff the case bit of the two strings. `mask = (a XOR b) AND 0x20` is 0 for same or 0x20 for differing. **`a ^= mask; b ^= mask` caseflip both letters iff they were opposite case.** (Because the ASCII letter codes for upper and lower differ only in bit 5.)

NASM listing (from `nasm -felf64 -l/dev/stdout`). Use `cut -b 26- <casexchg.lst >casexchg.lst` to turn this back into something you can assemble.

```
   addr    machine
 6         code          global casexchg
 7         bytes         casexchg:
 8                       .loop:
 9 00000000 AC               lodsb                ; al=[rsi] ; rsi++
10 00000001 3207             xor   al, [rdi]
11 00000003 2420             and   al, 0x20       ; 0 if their cases were the same: no flipping needed
12
13 00000005 3007             xor   [rdi], al      ; caseflip both iff their cases were opposite
14 00000007 3046FF           xor   [rsi-1], al
15
16 0000000A AE               scasb                ; cmp al,[rdi] / inc rdi
17                           ; AL=0 or 0x20.
18                           ; At the terminating 0 in both strings, AL will be 0 so JNE will fall through.
19                           ; 0x20 is ASCII space, which isn't allowed, so AL=0x20 won't cause early exit
20 0000000B 75F3             jne  .loop
21                       ;    loop  .loop            ; caller passes explict length in RCX
22
23 0000000D C3               ret

  size = 0xe bytes = 14
24 0000000E 0E           db $ - casexchg_bitdiff

```

The slow `loop` instruction is also 2 bytes, same as a short `jcc`. `scasb` is still the best way to increment `rdi` with a one-byte instruction. I guess we could `xor al, [rdi]` / `stosb`. That would be the same size but probably faster for the `loop` case (memory src + store is cheaper than memory dst + reload). And would still set ZF appropriately for the implicit-length case!

Try it online! with a \_start that calls it on argv\[1\], argv\[2\] and uses sys\_write on the result
> 4 votes

# Answer
# , 36 31 27 bytes

-9 bytes thanks to FrownyFrog!

```
(XOR"$32*[:~:/97>])&.(3&u:)

```

Try it online!

The previous solution was:

# , 36 31 bytes

-5 bytes thanks to FrownyFrog!

```
|:@(XOR 32*0~:/@|:97>])&.(3&u:)

```

Try it online!

## How it works:

```
                          (3&u:)  converts the strings to code points
   (                    )&.       then do the following and convert back to chars
                    97>]          check if they are uppercase letters
             0~:/@|:              transpose and check if the two values are different
          32*                     multiply by 32 (32 if different, 0 otherwise)
      XOR                         xor the code point values with 32 or 0
 |:@                              and transpose

```
> 3 votes

# Answer
# , 14 bytes

```
{`c$l+|x-l:_x}

```

Try it online! Input/output is a list of two strings.
> 3 votes

# Answer
# , ~~118 94 75~~ 72 bytes

```
m=sapply(scan(,""),utf8ToInt);w=m>96;apply(m-32*(w-w[,2:1]),2,intToUtf8)

```

Try it online!

~~There must be a much golfier way.~~ -43 bytes thanks to Giuseppe who pointed me to the MATL solution by Luis Mendo. TIO link contains a function solution for the same byte count.

```
m=sapply(a<-scan(,""),utf8ToInt)    # Turns input into a matrix of bytecode (2 columns)
w=m>96                              # Predicate : which chars are lower?
apply(m-32*(w-w[,2:1]),2,intToUtf8) # -32*w turns the string to UPPER
                                    # +32*w[,2:1] swaps capitalization
                                    # intToUtf8 turns bytecode to strings

```

Bonus: The output is a named vector whose names are the original input strings!
> 3 votes

# Answer
# Vyxal , 4 bytes

```
•??•

```

Try it Online!

Explanation:

```
•    # A with the capitalization of B
 ??  # Get both input strings (order ends up reversed)
   • # A with the capitalization of B
     # "ṡ" flag - Print entire stack, separated by spaces

```
> 3 votes

# Answer
# Python 3, 83 bytes

```
lambda a,b:(g(a,b),g(b,a))
g=lambda*a:[chr(ord(x)&95|(y>'Z')<<5)for x,y in zip(*a)]

```

Try it online!

-3 bytes thanks to Mr. Xcoder
-3 bytes thanks to Chas Brown
> 2 votes

# Answer
# JavaScript, ~~77~~ ~~74~~ 73 bytes

```
W=>W.map((w,x)=>w.map((c,i)=>W[+!x][i][`to${c>{}?'Low':'Upp'}erCase`]()))

```

```
f=
W=>W.map((w,x)=>w.map((c,i)=>W[+!x][i][`to${c>{}?'Low':'Upp'}erCase`]()))

console.log(
    f([[...'CodeGolf'],[...'xxPPCGxx']])
)
```

Takes an array of char arrays, outputs an array of char arrays.

-1 byte (@Arnauld): `c>'Z'``c>{}`
> 2 votes

# Answer
# Haskell, 78 bytes

```
c!d=([c..'z']++[';'..])!!sum[32|(c>'Z')/=(d>'Z')]
(#)=zipWith(!)
s%t=(s#t,t#s)

```

Try it online!
> 2 votes

# Answer
# QBasic, 133 bytes

```
INPUT a$,b$
FOR i=1TO LEN(a$)
c=ASC(MID$(a$,i,1))
d=ASC(MID$(b$,i,1))
s=32AND(c XOR d)
?CHR$(c XOR s);
r$=r$+CHR$(d XOR s)
NEXT
?
?r$

```

Takes the two strings comma-separated and outputs the results newline-separated. Uses the bit-fiddling algorithm from Dennis's Jelly answer. Other than that, the main golf trick here is that the first result string is printed directly, one character at a time, which is a little shorter than saving both result strings in variables and printing them outside the loop.
> 2 votes

# Answer
# Jelly, 13 bytes

```
=Œu=/ị"Ɱż"Œs$

```

**Try it online!**

Also 13: `=ŒuṚ×32ạŒlO$Ọ` (or `=ŒuṚæ«5ạŒlO$Ọ`)
> 1 votes

# Answer
# Python 3, ~~76~~ 75 bytes

```
lambda a,b:''.join(chr(ord(x)&95|ord(y)&32)for x,y in zip(a+' '+b,b+'a'+a))

```

Try it online!

Outputs the result as one string with a single-character separator.

Thx to Jonathon Allan for 1 byte.
> 1 votes

# Answer
# Retina, 75 bytes

```
^
¶
+`¶(([A-Z])|(.))(.*)¶(([A-Z])|(.))
$#6*$u$1$#7*$l$1¶$4$#2*$u$5$#3*$l$5¶

```

Try it online! Explanation: The newlines are used as markers to determine how much of the string has been processed. The regex tries to match against uppercase letters or failing that any characters. If an uppercase letter was matched then the other character is uppercased otherwise it is lowercased and vice versa, while the newlines are advanced to the next character.
> 1 votes

# Answer
# Assembly (nasm, x64, Linux), 25 bytes (123 bytes source)

Hex bytes:

```
0x88, 0xE6, 0x30, 0xC6, 0x80, 0xE6, 0x20, 0x88
0xF2, 0x66, 0x31, 0xD0, 0x88, 0x26, 0xAA, 0xAC
0x8A, 0x26, 0x8A, 0x07, 0x08, 0xE4, 0x75, 0xE8, 0xC3

```

The function entry point is at `a`, with the strings passed in using `RDI` and `RSI`.

```
b:MOV DH,AH
XOR DH,AL
AND DH,32
MOV DL,DH
XOR AX,DX
MOV [RSI],AH
STOSB
LODSB
a:MOV AH,[RSI]
MOV AL,[RDI]
OR AH,AH
JNZ b
RET

```

Try it online!
> 1 votes

# Answer
# Crystal, 108 bytes

```
def f(a,b)r=s=""
a.zip(b){|x,y|r+="`"<x<"{"?y.downcase: y.upcase
s+="`"<y<"{"?x.downcase: x.upcase}
{s,r}end

```

Try it online!

### How it works?

```
def f(a, b)                       # Strings as list of characters
r = s = ""                        # Strings buffers initialization
a.zip(b) do |x, y|                # Join two arrays to paired tuples and iterate
r+="`"<x<"{"?y.downcase: y.upcase # Check if character is downcase using triple
s+="`"<y<"{"?x.downcase: x.upcase # comparison and ascii table. Then apply it to
end                               # the other character using String methods
{s, r}                            # Return two new strings using a tuple
end                               # PS: Tuples are inmutable structures in Crystal

```
> 1 votes

# Answer
# TI-Basic, 225 bytes

```
Prompt Str1,Str2
"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ→Str3
"seq(inString(Str3,sub(Ans,I,1),I,1,length(Ans→u
Str1
u→F
Str2
augment(u,ʟF→S
augment(ʟF,Ans→F
".
For(I,1,dim(ʟS
Ans+sub(Str3,remainder(ʟF(I)-1,26)+1+26(ʟS(I)>26),1
End
Disp sub(Ans,2,length(Str1
sub(Ans,2+length(Str2),length(Str2

```

-1 byte if the `i` is replaced with the imaginary number `i`.
+3 bytes by replacing `remainder(ʟF(I)-1,26)` with `26fPart((ʟF(I)-1)/26)` if the calculator does not support `remainder(`.

Outputs are displayed, separated by a newline.
> 1 votes

# Answer
# Charcoal, 17 bytes

```
Ｅθ⭆ι⎇№α§§θ¬κμ↥λ↧λ

```

Try it online! Link is to verbose version of code. Takes input as an array of two strings. Explanation:

```
 θ                  Input array
Ｅ                   Map over strings
   ι                Current string
  ⭆                 Map over characters
         θ          Input array
           κ        Outer loop index
          ¬         Logical Not
        §           Index into array
            μ       Inner loop index
       §            Index into array
      α             Uppercase characters
     №              Count number of matches
              λ λ   Current character
             ↥      Uppercase
               ↧    Lowercase
    ⎇               Ternary
                    Implicitly print

```
> 0 votes

# Answer
## F#, 120 bytes

Bugger.

```
open System
let g=Seq.fold2(fun a x y->a+string(x|>if y>'Z'then Char.ToLower else Char.ToUpper))""
let b f s=g f s,g s f

```

Try it online!

The function `g` takes the two strings as parameters. `Seq.fold2` applies a function with an accumulator (`a`) to each element (`x` and `y`) in the strings. Initially `a` is an empty string, and it adds the converted character to it in each iteration.

`b` is the main function. It first converts `f` with respect to `s`, and then converts `s` with respect to `f`. It then returns a tuple with both values.
> 0 votes

# Answer
# Prolog (SWI), 121 bytes

```
[H|T]-[I|U]-[J|V]-[K|W]:-((H>96,I>96;H<92,I<92),J=H,K=I;H>96,J is H-32,K is I+32;J is H+32,K is I-32),T-U-V-W.
_-_-[]-[].

```

Try it online!
> 0 votes

# Answer
# Stax, 10 bytes

```
▌Ö↑o╓→ì]yç

```

Run and debug it

Here's an ungolfed representation of the same program to show how it works.

```
        Example
        ["Ab", "cd"]
:)      [["Ab", "cd"], ["cd", "Ab"]]    Get all rotations of input
m       ["cd", "Ab"]                    For each, run the rest of program; print result
  M     ["cA", "db"]                    Transpose matrix
  {     "cA"                            Begin block for mapping to result
    B   "A" 99                          "Pop" first element from string array; leave the rest
    96> "A" 1                           Is the character code > 96?
    :c  "a"                             Set case of string; 0 -> upper,  1 -> lower
  m     "ab"                            Perform the map using the block

```

Run this one
> 0 votes

# Answer
# Ruby, ~~74~~ 69 bytes

```
->a,b{a.zip(b).map{|x|x.one?{|y|y>?_}?x.map(&:swapcase):x}.transpose}

```

Try it online!

Input and output are arrays of chars, so the footer does back and forth transformations from strings.

I'm not yet sure whether this is a good approach to the problem, but this challenge definitely looks like a nice use scenario for `swapcase` method.
> 0 votes

# Answer
## PHP 4.1.2, 40 bytes

Replace the pair of quotation marks with byte A0 (in ISO-8859-1 or Windows-1252, this is NBSP) to get the byte count shown, then run from a web browser (or from the command line), providing the strings as the query string arguments (or environment variables) `a` and `b`.

```
<?=$a^$c=($a^$b)&str_pad("",2e5),_,$b^$c;

```

In this version of PHP, register\_globals is on by default, so the strings will automatically be assigned to the variables `$a` and `$b`. Increase the value `2e5` (200000) if necessary.

## PHP 7.1+, 58 bytes

Run on the command line, using `php -r 'code here' string1 string2`:

```
[,$a,$b]=$argv;echo("$b $a"^$a.=" $b")&str_pad("",3e5)^$a;

```

The value `3e5` (300000) is chosen to exceed (MAX\_ARG\_STRLEN * 2 + 1) on most Linux systems (specifically, x86 and other architectures for which PAGE\_SIZE is 4096, and MAX\_ARG\_STRLEN is thus 131072), to avoid problems with any possible input string. Increase if necessary.

Try it online!
> 0 votes

---
Tags: code-golf, string
---


# Question
Title: Temporally Dither an Image (Image to PWM Image)
# Background

I want to display *rich, vibrant images* on my theoretical fancy custom display, but due to budget constraints, it displays everything in 3-bit colour! Whilst Regular Dithering would work, I don't want to sacrifice resolution, so I would like my images to be dithered through time!

# Specs

Provided an Input Image, I would like you to show me several 3-bit color versions of that image, such that the average colour of all images is the original image.

## I/O

You must take an image as input.

You may either animate the image (Return a GIF, Video, or on the screen), or take time as an additional input. If time is taken as input, the output must be Deterministic for a given image and time, and must return as a static image.

## Example

*From Wikimedia Commons*

>

*A lot of quality was lost between recording the output and converting it to a gif, thus a still has also been provided*

## Victory

The victory condition is , as per previously stated budget constraints.

# Final Notes

Please consider the risk of photo-sensitivity when uploading an answer, and keep images to either external links, or wrapped in a spoiler. Videos of your solution running are not required, but are welcome.

# Answer
> 1 votes
# Wolfram Language (Mathematica), 24 bytes

```
Sign[#-Mod[1##,1]]&

```

Try it online!

Input `[image,time]`, where `image` is a 3-channel RGB `Image`, and outputs a frame.

A fairly straightforward approach: output whenever the floor of the accumulated value increases. Mathematica's `Image`s support arithmetic and can contain values of any size, but are clamped between 0 and 1 when displayed.

For the image in OP, a GIF output of t=1,2,...,255 can be viewed here (caution: blocks of flashing colors).
Averaging the frames:

# Answer
> 1 votes
# Perl 5 -ap, 110 bytes

```
srand($F[3]=1);
$_=(map{splice@b,rand@b,1}@b=((1)x($o=int$_*8/256),(0)x(8-$o)))[$ENV{F}]for@F[4..$#F];
$_="@F\n"

```

Can't try it online!

...but instead you can create an 8 frames animated GIF image with:

```
echo 'srand(7);$F[3]=1;$_=(map{splice@b,rand@b,1}@b=((1)x($o=int$_*8/256),(0)x(8-$o)))[$ENV{F}]for@F[4..$#F];$_="@F\n"' > program.pl
wget -N -O img.jpg "https://upload.wikimedia.org/wikipedia/commons/thumb/6/66/Johannes_Vermeer_%281632-1675%29_-_The_Girl_With_The_Pearl_Earring_%281665%29.jpg/335px-Johannes_Vermeer_%281632-1675%29_-_The_Girl_With_The_Pearl_Earring_%281665%29.jpg"
convert -compress none img.jpg img.ppm
perl -i -pe's/\n/ /' img.ppm
for f in {0..7};do cat img.ppm|F=$f perl -ap program.pl > img-frame$f.ppm;done  #~10sec
convert -delay 1 -loop 0 img-frame*.ppm img-animated.gif
xdg-open img-animated.gif

```

The `program.pl` reads the one line input (the example image of this challenge converted to the Plain PPM format) from STDIN and the frame number 0-7 (the time) from the environment variable F. The above commands works with `bash` shell, `wget`, the `convert` program from ImageMagick and `xdg-open` or any image viewer capable of viewing animated GIF images. To change to 16 frames, replace 7 with 15 and the two 8's with 16. Animated GIF image: https://drive.google.com/file/d/1s5WDGjwKLowdmildkYxUWGOWpRjS-Av6/view?usp=sharing

---
Tags: code-golf, graphical-output, image-processing
---


# Question
Title: How to solve the LCM in 50 bytes of Python
I've recently stumbled upon a Russian site called acmp.ru, in which one of the tasks, HOK, asks us to find the LCM of two positive integers. The full statement, translated to English is as follows:

> The only line of the input contains two natural numbers A and B separated by a space, not exceeding 46340.
> In the only line of the output, you need to output one integer - the LCM of the numbers A and B.

On the Python leaderboard, the top solution is just 50 bytes, followed by a stream of 52s.

Note that the scoring method for this site is *not* standard, and uses the following formula:

> max(code length without spaces, tabs and newlines, full code length divided by 4)

With this in mind, I have come up with two solutions that give a score of 52. One of them simply uses `math.lcm`, while the other one calculates it more directly:

```
from math import*
print(lcm(*map(int,input().split())))

```

```
a,b=map(int,input().split())
v=a
while v%b:v+=a
print(v)

```

Now I'm stumped. How can I save 2 bytes off my solution? (the Python version is 3.9.5).

# Answer
> 29 votes
***My solution to 50 bytes:***

```
v=1
for x in input().split()*6**6:v+=-v%int(x)
print(v)

```

### Explanation

The solution itself is relatively simple, but finding it was significantly more difficult.

First, note that the LCM of `a` and `b` is the smallest number `v` such that `v%a==0` and `v%b==0`.

The main logic for this algorithm is in `v+=-v%int(x)`. In a nutshell, it sets `v` to the first multiple of `x` greater than or equal to `v`. This means that if `v%x==0`, `v` doesn't change.

In a `for` loop, we repeat this process cyclically with both numbers. Whenever `v` is not divisible by `x`, `v+=-v%x` ensures that `v` becomes the immediate next divisor of `x`. This means that, at some point in the loop, `v` will equal the LCM. When it does, `v` will stop changing, since both numbers will be divisible by `v`.

To better illustrate the algorithm, here is an example on the input `36 27`:

```
                v=1
(36): v+=-v%36; v=36
(27): v+=-v%27; v=54
(36): v+=-v%36; v=72
(27): v+=-v%27; v=81
(36): v+=-v%36; v=108
(27): v+=-v%27; v=108
(36): v+=-v%36; v=108
...

```

It remains to determine how many iterations are required. In the worst case, `A` and `B` are coprime, for which the LCM is `A*B`. For this, we would need exactly `min(A,B)` iterations. The statement tells us that both numbers are guaranteed to be at most `46340`. We could simply use this number, but `6**6` is one shorter, and only does `316` extra operations.

---
Tags: code-golf, math, number-theory, tips, python
---


title: How to shorten the Python code? Part II

text:
# Question
Title: How to shorten the Python code? Part II
Code Python 3, 245 bytes

```
E=print
def F():
	B,C,A=1,1,1;yield 0
	while True:yield B;B,C,A=B+C+A+1,C+A+1,A+1
C=int(input())
D=0
for A in range(C):
	E(end='*'*(C-(C-A)+1));B=A
	while 0<B:E(end=' '+chr(42+B)*B);B-=1
	E();D+=1
for A in F():
	if D==0:E(end=str(A));break
	D-=1

```

Try it online!

## What it does?

Takes a number from input, loops from 0 to \\$x - 1\\$ (let's call iterator \\$y\\$), prints ASCII 41 ("\*"), \\$y\\$ times with a space and prints ASCII 42, \\$y - 1\\$ times with a space and repeat until the \\$y - x\\$ is \\$0\\$, print a newline and go to next iteration.

If the loop is ended, print the total of the output (not including the output of spaces and newlines).

# Answer
# Python 3, 106 bytes

```
C=int(input())
i=0
while i<C:i+=1;print(*[j*chr(42+j%i)for j in range(i,0,-1)])
print(C*~C*~-~C//6,end='')

```

Try it online!

The grand total can be computed as `C*(C+1)*(C+2)//6` (see tetrahedral numbers). So you don't need `F` at all! This saves a lot of bytes.

This formula can be golfed down to `C*-~C*-~-~C//6`, and then further to `C*~C*~-~C//6` because two of the `-`s cancel out in the product.

Then, I just wrote some simpler code to print the ASCII characters. Usually when you want output separated by spaces, `print(*[list comprehension])` is pretty good, so I tried that.

The clever thing here is using `j%i` to count like `0, i-1, i-2, ... 1` on each row. Try replacing it with just `j` and compare the output.

There are only two print calls now, so `E=print` doesn't save bytes anymore.

`print(end=str(num))` is longer than `print(num,end='')`.

## Tiny golfs in your code

* `B,C,A=1,1,1` can be `B=C=A=1`.
* `while True` can be `while 1`.
* `(C-(C-A)+1)` equals `(A+1)` equals `-~A`.
* `while 0<B` can be `while B` here.

Making a generator and extracting the `D`-th value seems painful. You can "inline" the iterator: delete the definition of `F` and just perform the logic inside `F`, `D` times at the end of your code:

```
E=print
C=int(input())
D=0
for A in range(C):
    E(end='*'*-~A);B=A
    while B:E(end=' '+chr(42+B)*B);B-=1
    E();D+=1
b=c=a=0
while D:b,c,a=b+c+a+1,c+a+1,a+1;D-=1
print(b,end='')

```

If we stare at the assignments long enough, we can figure out that `b,c,a=b+c+a+1,c+a+1,a+1` can be `a+=1;c+=a;b+=c`.

Also, we count up from `D=0` to `D=C`, so we can just use `C` instead of `D`:

```
E=print
C=int(input())
for A in range(C):
    E(end='*'*-~A);B=A
    while B:E(end=' '+chr(42+B)*B);B-=1
    E()
b=c=a=0
while C:a+=1;c+=a;b+=c;C-=1
print(b,end='')

```

But an even shorter way to just repeat some code `C` times is this:

```
exec("a+=1;c+=a;b+=c;"*C)

```

Of course, the tetrahedral number formula is even shorter than any of this.
> 12 votes

# Answer
*Make sure to check out Lynn's answer. It contains some great advice too.*

# Python 3, 237 bytes

```
E=print
def F():
 B=C=A=1;yield 0
 while 1:yield B;B,C,A=B+C+A+1,C+A+1,A+1
C=int(input())
D=0
for A in range(C):
 E(end='*'*(C-(C-A)+1));B=A
 while 0<B:E(end=' '+chr(42+B)*B);B-=1
 E();D+=1
for A in F():
 if D<1:E(end=str(A));break
 D-=1

```

Try it online!

My go at this. Will keep golfing later.

Try it online!
> 0 votes

# Answer
**Python 3, 132 bytes**

Here is my approach to this problem.

```
C=int(input())
print(*(' '.join(['*'*(A+1)]+[B*chr(42+B)for B in range(A,0,-1)])for A in range(C)),C*(C+1)*(C+2)//6,sep='\n',end='')

```

Please refer to Lynn's answer for more details and for a much shorter code. For example, my code could be further optimized by replacing `C*(C+1)*(C+2)//6` with `C*~C*~-~C//6`.

Try it online!
> 0 votes

---
Tags: code-golf, math, tips, python
---