title: List *all* the tuples!

text:
# Question
Title: List *all* the tuples!
Write a program, given an input *n*, will generate all possible n-tuples using natural numbers.

```
n=1
(1),(2),(3),(4),(5),(6)...

n=2
(1,1),(1,2),(2,1),(2,2),(1,3),(3,1),(2,3),(3,2),(3,3)...

n=6
(1,1,1,1,1,1) (1,1,1,1,2,1) (1,1,1,2,1,1)...

```
* The output may be in any order that does not break any other rules.
* The program must be written to run forever and list all applicable tuples exactly once, in theory.
    + In reality, your program will reach your integer type's limit and crash. This is acceptable as long the program *would* run infinitely long if only your integer type was unlimited.
    + Each valid tuple must be listed within finite time, if only the program were allowed to run that long.
* The output may, at your option, include zeroes in addition to the natural numbers.
* You may choose your program's output format for your convenience, as long as the separation between tuples and numbers inside each tuple is clear and consistent. (For example, one tuple per line.)
* The input (n) is an integer from one to six. Required behavior is undefined for inputs outside of this range.
* Code-golf rules apply, shortest program wins.

Thanks to "Artemis Fowl" for feedback during the sandbox phase.

# Answer
# Husk, 2 bytes

```
πN

```

Try it online!

## Explanation

`N` is the infinite list of natural numbers `[1,2,3,4,..`. `π` is Cartesian power. Result is an infinite list of lists. Each list of the desired length occurs exactly once because `π` is cool like that. Input and output are implicit.
> 25 votes

# Answer
# Haskell, 62 bytes

```
([1..]>>=).(!)
0!s=[[]|s<1]
n!s=[a:p|a<-[1..s],p<-(n-1)!(s-a)]

```

Try it online!

`n!s` generates all the `n`-tuples that sum to `s`.

Then the answer is `([1..]>>=).(!)`, i.e. `\n -> [t | s<-[1..], t<-n!s]`.

This is a function mapping an integer `n` to an infinite lazy list of tuples (lists of integers).
> 10 votes

# Answer
# Haskell, 50 bytes

```
f n=[l|k<-[0..],l<-mapM([0..k]<$f)[0..n],sum l==k]

```

Try it online!

Lists `n`-tuples sorted by sum. `mapM` does the heavy lifting to generate all `n`-tuples of numbers from 0 to k. The `<$f` trick is explained here.

# Haskell, 51 bytes

```
f 1=pure<$>[0..]
f n=[a-k:k:t|a:t<-f$n-1,k<-[0..a]]

```

Try it online!

Recursively stretches all `n-1`-tuples into all `n`-tuples by splitting the first number `a` of each `n-1`-tuple into two numbers `a-k,k` that sum to it, in every possible way.
> 5 votes

# Answer
# Pyth - 9 bytes

*Thanks to @FryAmTheEggman for the golf*

Loops through all x, and takes \[1..x\]^n. This makes duplicates, so only keeps ones that are new to that x, aka contain x in them. The formatting is a little weird, but it can be made standard with one more byte, `.V1j}#b^Sb`

```
.V1}#b^Sb

```

Try it online.
> 4 votes

# Answer
# Brachylog (v2), 9 bytes

```
~l.ℕᵐ+≜∧≜

```

Try it online!

This is an infinite generator that generates all possible tuples. The TIO link has a header that uses the generator to generate 1000 elements and prints them (but the generator could continue indefinitely if I asked for that instead; Brachylog's integers are unbounded).

It feels like there should be a terser way, but there are a lot of constraints and this is the tersest I can fit them into a single program.

## Explanation

```
~l.ℕᵐ+≜∧≜
  .        Generate
        ≜  all explicit
~l         lists whose length is {the input}
    ᵐ      for which every element
   ℕ       is non-negative
     +     and whose sum
      ≜    is used to order the lists (closest to zero first)
       ∧   [remove unwanted implicit constraint]

```

Incidentally, it strikes me as interesting just how different my explanations of the two  are, despite them doing the exact same thing from Brachylog's point of view. The first  is the first nondeterministic predicate in the program, so it sets the order of results; in this case, it calculates all possible explicit values for the sum of the list in the order 0, 1, 2, 3…, and is being used to ensure that the lists are output in order of their sum (this ensures that each possible list appears after a finite amount of output). The second  is used to calculate all the explicit possibilities for the list (rather than outputting a formula specifying how the elements of the list relate to each other).
> 3 votes

# Answer
# Wolfram Language (Mathematica), ~~62~~ 52 bytes

```
Do[Print/@(1+1~Table~#~FrobeniusSolve~--n),{n,∞}]&

```

Try it online!

---

-2 bytes with inconsistent separation: Try it online!
> 2 votes

# Answer
# C# (Visual C# Interactive Compiler), 148 bytes

```
n=>{var a=new int[n];int j=0;void g(int k){if(k<n)for(int i=0;i++<j;g(k+1))a[k]=i;else if(a.Sum()==j)WriteLine(string.Join(' ',a));}for(;;j++)g(0);}

```

Try it online!

-3 bytes thanks to @ASCIIOnly!

```
// n: size of tuples to generate
n=>{
  // a: current tuple workspace
  var a=new int[n];
  // j: target sum value
  int j=0;
  // recursive function that works on slot k
  void g(int k){

    // tuple is not fully generated,
    if(k<n)

      // try all values from (0,j]
      for(int i=0;i++<j;
        // recursive call - generates all
        // values from (0,j] in the next slot
        g(k+1)
      )
        // update the kth slot
        a[k]=i;

    // tuple is fully generated, however
    // we should only display if the sum
    // is equal to the target sum. tuples
    // are generated many times, this
    // let's us enforce that they are only
    // displayed once.
    else if(a.Sum()==j)
      WriteLine(string.Join(' ',a));
  }
  // increment the high value forever
  // while continually starting the
  // recursive function at slot 0
  for(;;j++)
    g(0);
}

```
> 2 votes

# Answer
# 05AB1E, ~~15~~ 11 bytes

```
[¼¾LIãvy¾å—

```

-4 bytes by creating a port of *@Maltysen*'s Pyth answer.

Try it online.

**Explanation:**

```
[             # Start an infinite loop:
 ¼            #  Increase the counter_variable by 1 (0 by default)
  ¾L          #  Create a list in the range [1, counter_variable]
    Iã        #  Take the cartesian power of this list with the input
      v       #  Loop over each list `y` in this list of lists:
       y¾å    #   If list `y` contains the counter_variable:
          —   #    Print list `y` with trailing newline

```
> 1 votes

# Answer
# MATL, 16 bytes

```
`@:GZ^t!Xs@=Y)DT

```

Tuples are ordered by increasing sum, and within a given sum they are ordered lexicographically.

**Try it online!**
> 1 votes

# Answer
# Jelly, 10 (9?) bytes

9 if we may output using non-consistent separation (which I have enquired about) -- removal of the .

```
‘ɼṗ³ċƇ®Ṅ€ß

```

**Try it online!**

### How?

```
‘ɼṗ³ċƇ®Ṅ€ß - Main Link: some argument, x (initially equal to n, but unused)
 ɼ         - recall v from the register (initially 0), then set register to, and yield, f(v)
‘          -   f = increment
           - (i.e. v=v+1)
   ³       - program's third command line argument (1st program argument) = n
  ṗ        - (implicit range of [1..v]) Cartesian power (n)
           - (i.e. all tuples of length n with items in [1..v])
     Ƈ     - filter keep those for which:
    ċ      -   count
      ®    -   recall from register
           - (i.e. keep only those containing v)
       Ṅ€  - print €ach
         ß - call this Link with the same arity
           - (i.e. call Main(theFilteredList), again the argument is not actually used)

```
> 1 votes

# Answer
# Python 2, ~~126~~ ~~112~~ ~~106~~ ~~101~~ ~~100~~ 83 bytes

```
n=input()
i=1
while 1:
 b=map(len,bin(i)[3:].split('0'));i+=1
 if len(b)==n:print b

```

Try it online!

5 bytes thx to mypetlion; 1 byte from the eagle eye of ArBo; 17 bytes from xnor!

Construct the ordered partitions of `m` into `n` bins, for `m = 0,1,2,3,...` by selecting for binary numbers with `n-1` `0`s and `m` `1`s.
> 1 votes

# Answer
# C# (.NET Core), ~~608 570~~ 567 bytes

```
using C=System.Console;using L=System.Collections.Generic.List<int[]>;class A{static void Main(){L x=new L(),y=new L(),z=new L();int i=int.Parse(C.ReadLine()),j=0,k,l,m;x.Add(new int[i]);while(i>0){j++;for(m=0;m++<i;){foreach(var a in y)x.Add(a);y=new L();foreach(var a in x){for(k=0;k<i;){int[] t=new int[i];System.Array.Copy(a,t,i);t[k++]=j;var b=true;z.AddRange(x);z.AddRange(y);foreach(var c in z){for(l=0;l<i;l++)if(c[l]!=t[l])break;if(l==i)b=false;}if(b)y.Add(t);}}}}for(k=0;k<x.Count;k++){C.Write("[ ");for(l=0;l<i;l++)C.Write(x[k][l]+" ");C.WriteLine("]");}}}

```

Try it online!

my god what have I done (so many loops, that's what I've done)

It should work, though!

If you move the print loop back one bracket, it will show you the list as it's built, every time it loops. (I recommend adding a newline or something to distinguish each loop if you do.)

Honestly, a *lot* of my time was spent fighting with the language...no pretty-printing arrays, assorted behaviors of ==...

Hopefully this version is easier to read.

```
using C=System.Console;
using L=System.Collections.Generic.List<int[]>;
class A{
    static void Main(){
        L x=new L(),y=new L(),z=new L();
        int i=int.Parse(C.ReadLine()),j=0,k,l,m;
        x.Add(new int[i]);
        while(i>0){
            j++;
            for(m=0;m++<i;){
                foreach(var a in y) x.Add(a);
                y=new L();
                foreach(var a in x){
                    for(k=0;k<i;){
                        int[] t=new int[i];
                        System.Array.Copy(a,t,i);
                        t[k++]=j;
                        var b=true;
                        z.AddRange(x);
                        z.AddRange(y);
                        foreach(var c in z){
                            for(l=0;l<i;l++) if(c[l]!=t[l])break;
                            if(l==i)b=false;
                        }
                        if(b)y.Add(t);
                    }
                }
            }
        }
        for(k=0;k<x.Count;k++){
            C.Write("[ ");
            for(l=0;l<i;l++)C.Write(x[k][l]+" ");
            C.WriteLine("]");
        }
    }
}

```
> 1 votes

# Answer
# Perl 6, 50 bytes

```
{grep $_,{S/.//.split(0)>>.chars}($++.base(2))xx*}

```

Try it online!

Anonymous code block that returns a lazy infinite list. This uses the same strategy as Chas Brown's answer.

### Explanation:

```
{grep $_,{S/.//.split(0)>>.chars}($++.base(2))xx*}
{                                                } # Anonymous code block
                                              xx*  # Repeat indefinitely
                                 ($++        )     # From the current index
                                     .base(2)      # Get the binary form
         {S/.//                 }   # Remove the first digit
               .split(0)            # And split by zeroes
                        >>.chars    # And get the length of each section
 grep   ,   # From this infinite list, filter:
      $_      # The groups with length the same as the input

```
> 1 votes

# Answer
# VDM-SL, 51 bytes

```
g(i)==if i=0then{}else{[x]^y|x:nat,y in set g(i-1)}

```

Recursive set comprehension with sequence concatenation..

Not on TIO, you could run in a program (if you turn on limits for nat type or it wont terminate):

```
functions
g:nat->set of ?
g(i)==if i=0then{}else{[x]^y|x:nat,y in set g(i-1)}

```

Includes the optional 0s in answer otherwise it would be 52 bytes binding on nat1
> 0 votes

# Answer
# Wolfram Language (Mathematica), 131 bytes

```
While[0<1,If[a~FreeQ~#,Print@#]&/@(b=Table[Select[Range@t~Tuples~{s},Tr@#==k&],{k,t,t(s=#)}]~Flatten~1);a={a}~Join~b;t++]&
t=1
a={}

```

Try it online!
> 0 votes

# Answer
# perl -M5.010 122 bytes

```
$n=shift;
$s.="for\$x$_(1..\$m){"for 1..$n;
$t.="\$x$_ "for 1..$n;
$u.='}'x$n;
eval"{\$m++;$s\$_=qq' $t';/ \$m /&&say$u;redo}"

```

Added some newlines for readabilities sake (not counted in the byte count)
> 0 votes

# Answer
# Python 2, 120 bytes

```
from random import*
m=n=input()
a=()
while 1:
 m+=len(a)==m**n;t=[randint(1,m)for _ in[1]*n]
 if(t in a)<1:a+=t,;print t

```

Try it online!

A bit longer than most other answers, but I liked the idea behind it.
> 0 votes

# Answer
# JavaScript (V8), 98 bytes

```
n=>{for(a=[],b=[j=1];;b.push(++j))(g=k=>k<n?b.map(i=>(a[k]=i)|g(k+1)):a.includes(j)&&print(a))(0)}

```

Try it online!

Hooray! Finally got it under 100 :) Basically a port of my C# answer.

```
// n: length of tuples to generate
n=>{
  // a: workspace for current tuple
  // b: range of numbers that grows
  //     - iteration 1: [1]
  //     - iteration 2: [1,2]
  //     - iteration 3: [1,2,3]
  // j: largest number in b
  for(a=[],b=[j=1];;b.push(++j))
    // g: recursive function to build tuples
    // k: index of slot for current recursive call
    (g=k=>
       // current slot less than the tuple size?
       k<n?
         // tuple generation not complete
         // try all values in current slot and
         // recurse to the next slot
         b.map(i=>(a[k]=i)|g(k+1)):
         // tuple generation complete
         // print tuple if it contains the
         // current high value
         a.includes(j)&&print(a)
    // start recursive function at slot 0
    )(0)
}

```
> 0 votes

# Answer
# Stax, 6 bytes

```
£ƒ$↔┬ï

```

Run and debug it

For input `n` the procedure is roughly

```
for i in [0..infinity]:
    get all the distinct n length arrays of positive integers that sum to i
    for each
        join with spaces
        implicitly output

```
> 0 votes

# Answer
# JavaScript (Node.js), ~~96~~ 90 bytes

```
n=>{for(i=0n;z=[];z.length-n||console.log(z))for(j=++i,w=0;j;j/=2n)w=j%2n?+!z.push(w):w+1}

```

Try it online!

V8 on TIO don't support BigInt
> 0 votes

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


title: Fastest unique finder

text:
# Question
Title: Fastest unique finder
Given 4096 16-bit integers, only four of which are unique and others appeared twice (so 2050 different integers exist). Find the four uniques.

To time precisely and limit RAM usage, your program will be run on a 12MHz 8051(with 128B RAM). I'll test with a random case generated by some code to test, but we aim at the worst case, so anyone can provide other test cases.

You can answer in C or ASM, but C will likely give some extra disadvantage. The input array is placed on ROM 0xE000-0xFFFF, and output is placed on extra write-only RAM 0x00-0x07. When you finish outputting, clear P3.5.

A C code that solves the problem with bad score, to better understand the I/O way:

```
#include <reg51.h>
sbit P3_5 = P3^5;
unsigned int code input[4096] _at_ 0xE000;
unsigned int pdata output[4] _at_ 0x00;
void main() {
    unsigned long i;
    unsigned int j;
    unsigned char cnt, wr = 0;
    for (i=0; i<65536L; ++i) {
        cnt = 0;
        for (j=0; j<4096; ++j) {
            if (input[j] == i) ++cnt;
        }
        if (cnt==1) { // Order doesn't matter
            output[wr++] = i;
        }
    }
    P3_5 = 0;
    while (1);
}

```

According to test this runs for 04:19:36.997507. Also see the example ASM solution that solve in several seconds.

---

For extreme push, I'll run the simulation on Proteus with such circuit:  and check the time when `DBT1` is actived.

* You can use all ROM in 0000-DFFF.
* You can assume RAM is initialized to 0.
* You can use SFRs, including pins, as RAM
* You don't need to `jmp $` after clearing `P3.5`
* You can write trash into outer RAM 08-FF, they'll be ignored

# Answer
# C, 0.480298s

## Codes

```
#ifndef LOCAL_DEBUG
#include <reg51.h>
sbit P3_5 = P3 ^ 5;
unsigned int code input[4096] _at_ 0xE000;
unsigned int pdata output[4] _at_ 0x00;
#else

#include <stdio.h>
#define int short

#define UNIQ1 17
#define UNIQ2 273
#define UNIQ3 1298
#define UNIQ4 1554

unsigned int input[4096] = {
UNIQ1,
UNIQ2,
UNIQ3,
UNIQ4
};
unsigned int output[4];

#endif

#define INPUT_SIZE 4096
#define BUCKET_BITS 4
#define BUCKET_SIZE (1 << (BUCKET_BITS))
#define BUCKET_MASK ((BUCKET_SIZE) - 1)

unsigned int buckets[BUCKET_SIZE];

#define buckets_value(n) (buckets[n] & ~(bucket_mask)) | ((n) << bit_offset)

void main() {
  unsigned int output_offset = 0;
  unsigned int i, j, k, l;
  unsigned int search_bucket = 0, search_bucket_2 = 0, bit_offset = 0, bit_offset_2, bucket_mask;
  unsigned int target_mask, target_value;
  do {
    bucket_mask = BUCKET_MASK << bit_offset;
    for (i = 0; i < BUCKET_SIZE; ++i) {
      buckets[i] = 0;
    }
    for (i = 0; i < INPUT_SIZE; ++i) {
      buckets[(input[i] >> bit_offset) & BUCKET_MASK] ^= input[i] | bucket_mask;
    }
    for (i = j = 0; i < BUCKET_SIZE; ++i) {
      if (buckets[i] != 0) ++j;
    }
    if (j <= 1) {
      bit_offset += BUCKET_BITS;
    }
  } while (j <= 1);
  if (j == 4) {
    for (i = 0; i < BUCKET_SIZE; ++i) {
      if (buckets[i] == 0) continue;
      output[output_offset++] = buckets_value(i);
    }
  } else if (j == 3) {
    for (i = 0; i < BUCKET_SIZE; ++i) {
      if (buckets[i] == 0) continue;
      if (buckets[i] & (BUCKET_MASK << bit_offset)) {
        output[output_offset++] = buckets_value(i);
      } else {
        search_bucket = i << bit_offset;
      }
    }
  } else if (j == 2) {
    for (i = k = 0; i < BUCKET_SIZE; ++i) {
      if (buckets[i] == 0) continue;
      if (buckets[i] & (BUCKET_MASK << bit_offset)) {
        l = buckets_value(i);
        if (k == 0) {
          for (j = 0; j < INPUT_SIZE; ++j) {
            if (input[j] == l) ++k;
          }
          if (k == 1) {
            output[output_offset++] = l;
          } else {
            search_bucket = i << bit_offset;
            k = 2;
          }
        } else if (k == 1) {
          search_bucket = i;
        } else {
          output[output_offset++] = l;
        }
      } else {
        if (search_bucket) {
          search_bucket_2 = i << bit_offset;
        } else {
          search_bucket = i << bit_offset;
        }
      }
    }
  }
  bit_offset_2 = bit_offset;
  target_mask = BUCKET_MASK << bit_offset;
  target_value = search_bucket;
  while (output_offset < 4) {
    bit_offset += BUCKET_BITS;
    bucket_mask = BUCKET_MASK << bit_offset;
    for (i = 0; i < BUCKET_SIZE; ++i) {
      buckets[i] = 0;
    }
    for (i = 0; i < INPUT_SIZE; ++i) {
      if ((input[i] & target_mask) != target_value) continue;
      buckets[(input[i] >> bit_offset) & BUCKET_MASK] ^= input[i] | bucket_mask;
    }
    for (i = j = 0; i < BUCKET_SIZE; ++i) {
      if (buckets[i] != 0) ++j;
    }
    if (j == 1) {
      continue;
    }
    for (i = 0; i < BUCKET_SIZE; ++i) {
      if (buckets[i] == 0) continue;
      if ((buckets[i] >> bit_offset) & BUCKET_MASK) {
        output[output_offset++] = buckets_value(i);
        --j;
      } else {
        target_mask |= bucket_mask;
        target_value |= i << bit_offset;
      }
    }
    if (j == 0) {
      bit_offset = bit_offset_2;
      target_mask = BUCKET_MASK << bit_offset;
      target_value = search_bucket_2;
    }
  }
#ifndef LOCAL_DEBUG
  P3_5 = 0;
  while (1);
#else
  for (i = 0; i < 4; i++) {
    printf("%d\n", output[i]);
  }
#endif
}

```

Try it online!

I'm not sure about its correctness. Please comment if you find out some failed testcases. I will try my best to fix it.

---

## Algorithm

Algorithm here only works when input array contains 4 unique values. It will fail if input array contains more than 4 values.

Consider xor of some numbers where most numbers occurred 2 times, and some occurred once. It is easy to prove: The xor result is zero if and only if we have at least 3 unique numbers here. Also, we try to count how many numbers at all. It is trivial to know: If the count is even / odd, then we have even / odd number of unique numbers here.

As there are only 4 unique numbers according to the description of this question. If both xor result is zero and count result is even, there should be 0 or 4 unique numbers.

By using this idea, we need to split numbers into some buckets while keep equals number in same buckets. You can do it by `(input[i] >> n) & m`. So we first split all values `input[i]` into 16 buckets based on `(input[i] >> 0) & 15`. We use `input[i] | bucket_mask` to mask out the bits for bucket name. We set them to 1s, so they are used to know count number in that buckets is odd or even.

```
for (i = 0; i < INPUT_SIZE; ++i) {
  buckets[(input[i] >> bit_offset) & BUCKET_MASK] ^= input[i] | bucket_mask;
}

```

We use above code. And after calculate these `buckets`:

* If `buckets[i] & bucket_mask` is non-zero: we know the bucket i contains 1 or 3 unique numbers (number count is odd).
* If `buckets[i] & bucket_mask` is zero, but `buckets[i]` is non-zero: we know the bucket i contains 2 unique numbers.
* If `buckets[i]` is zero, and some other bucket `bucket[j]` is non-zero: we know the bucket i contains no unique numbers.
* If all `buckets` are zero: 4 unique numbers are located in the same bucket. We need to try another 4 bits as mask and run the loop again.

After we know where the number is in some bucket:

* If the bucket contains only 1 unique numbers: the unique number is `(buckets[i] & ~(bucket_mask)) | ((i) << bit_offset)`;
* If the bucket contains more than 1 unique numbers: We loop again on numbers in this bucket, and split them into different buckets based on other bits;

---

## Analysis

Time complexity is \\$O\left(size \cdot bit / buckets + 2^{buckets} \right)\\$. \\$size\\$ is how many numbers the input contains. \\$bit\\$ is how many bits each input contains. \\$bucket\\$ is how many bits for bucket id (4 in above codes).

Extra storage complexity is \\$O\left(2^{buckets}\right)\\$.
> 7 votes

# Answer
# 5.003017s

```
    PAG equ R7
    APAG equ 7
    WRPTR equ R0

    org 0
    ; mov PAG, a  ; using that RAM is cleared
    ; mov WRPTR, a
mainloop:
    mov dptr, #0E000h
    ; clr 64-127
    clr a
    _ptr set 64
    rept 64
        mov _ptr, a
        _ptr set _ptr+1
    endm
scan:
    rept 128
        local exit
        clr a
        movc a, @a+dptr
        inc dpl
        add a, PAG
        add a, acc
        jnz exit
        clr a
        movc a, @a+dptr
        mov b, a
        orl b, #0D8h
        clr b.5
        mov b.2, c  ; 11011caa
        anl a, #0FCh
        mov 9, #exit/256
        mov 8, #exit mod 256
        mov 11, b
        mov 10, a
        mov sp, #11
        ret
exit:   ;inc dptr
        inc dpl
    endm
    inc dph
    mov a, dph
    jz not_scan
    jmp scan
not_scan:
    _ptr set 0
    xrl APAG, #0FFh
    inc PAG
    rept 64
        local j7, j6, j5, j4, j3, j2, j1, j0
        mov b, _ptr/8+64
        jnb b.7, j7
        mov a, PAG
        movx @WRPTR, a
        inc WRPTR
        mov a, #_ptr mod 256+7
        movx @WRPTR, a
        inc WRPTR
j7:     jnb b.6, j6
        mov a, PAG
        movx @WRPTR, a
        inc WRPTR
        mov a, #_ptr mod 256+6
        movx @WRPTR, a
        inc WRPTR
j6:     jnb b.5, j5
        mov a, PAG
        movx @WRPTR, a
        inc WRPTR
        mov a, #_ptr mod 256+5
        movx @WRPTR, a
        inc WRPTR
j5:     jnb b.4, j4
        mov a, PAG
        movx @WRPTR, a
        inc WRPTR
        mov a, #_ptr mod 256+4
        movx @WRPTR, a
        inc WRPTR
j4:     jnb b.3, j3
        mov a, PAG
        movx @WRPTR, a
        inc WRPTR
        mov a, #_ptr mod 256+3
        movx @WRPTR, a
        inc WRPTR
j3:     jnb b.2, j2
        mov a, PAG
        movx @WRPTR, a
        inc WRPTR
        mov a, #_ptr mod 256+2
        movx @WRPTR, a
        inc WRPTR
j2:     jnb b.1, j1
        mov a, PAG
        movx @WRPTR, a
        inc WRPTR
        mov a, #_ptr mod 256+1
        movx @WRPTR, a
        inc WRPTR
j1:     jnb b.0, j0
        mov a, PAG
        movx @WRPTR, a
        inc WRPTR
        mov a, #_ptr mod 256+0
        movx @WRPTR, a
        inc WRPTR
j0:
        _ptr set _ptr + 8
        if (_ptr = 256)
            orl APAG, #080h
        endif
    endm
    inc PAG
    cjne PAG, #0, mainloopJ
    clr P3.5
    jmp $
mainloopJ:
    xrl APAG, #07Fh
    inc PAG
    jmp mainloop

    org 0D800h
    rept 512
        _oa set (03FCh and $) mod 255 + ($>=0DC00h)*256
        xrl 64+_oa/8, #1 shl (_oa mod 8)
        ret
    endm

```

I know SFRs are enough to make 1024 tested numbers in a scan, but as this is an example solution, and I expect some much faster solutions than bit\[N\]&scan
> 4 votes

# Answer
# C, 87s

I don't have the means to test or even compile for the environment, so there are likely issues and further optimisations. I've no idea if the code (and stack?) will fit in 128B.

There are a couple of optimisations over the naïve C example:

* 4096x4096 iterations instead of 65536x4096 iterations.
* XOR trick - XOR all the input values together. Then once we've found 3 out of 4 non-duplicate values, these may be XORed against the xor accumulator one more time to cancel them out and leave the 4th non-duplicate value remaining.

There are likely better algorithms than this, but it's a start.

Hand-written assembly will certainly beat this, but for now, I don't know 8051 assembly at all, so I'll have to settle for C.

I am assuming in this architecture, `sizeof(int) == 2` and `sizeof(long) == 4`.

```
#include <reg51.h>
sbit P3_5 = P3^5;
unsigned int code input[4096] _at_ 0xE000;
unsigned int pdata output[4] _at_ 0x00;
void main() {
    unsigned int i, j;
    unsigned char dupfound, wr = 0;
    unsigned int xor_acum = 0;
    unsigned int v;
    unsigned int output_stage[3];

    for (i=0; i<4096; ++i) {
        v = input[i];
        xor_acum ^= v;
        if (wr < 3) {
            dupfound = 0;
            for (j=0; j<4096; ++j) {
                if (i != j && v == input[j]) {
                    dupfound = 1;
                    break;
                }
            }
            if (!dupfound) {
                output_stage[wr++] = v;
            }
        }
    }
    output[0] = output_stage[0];
    xor_acum ^= output_stage[0];
    output[1] = output_stage[1];
    xor_acum ^= output_stage[1];
    output[2] = output_stage[2];
    xor_acum ^= output_stage[2];
    output[3] = xor_acum;

    P3_5 = 0;
    while (1);
}

```
> 2 votes

---
Tags: fastest-code, restricted-memory
---


title: Implement Ash's float division

text:
# Question
Title: Implement Ash's float division
Ash has a bit of an interesting float division algorithm. It's designed to never return `NaN`, and things like signed zero and infinity need to be handled.

**How it works:**

Assume the inputs are positive for the rules below. One input being negative will always result in the output being negative, and both being negative will result in a positive output.

* Zero divided by anything is `0`
* Anything other than `0` divided by `0` is `Infinity`
* Anything other than `Infinity` divided by `Infinity` is `0`
* `Infinity` divided by anything other than `Infinity` is `Infinity`
* `Infinity` divided by `Infinity` is `1`
* All other division works as normal

**I/O:**

For languages with floats that support signed zero and positive/negative infinity, floats are an accepted I/O format. For others, using a string is allowed. You can use any reasonable format in this string, and you can represent the infinities with anything that can't be confused with another number (such as `I`, , `inf`, or `:(`).

Input will always be two floats in your chosen representation, and output will be a single one. Floating point errors and large numbers being represented as `Infinity` are allowed.

**Test cases:**

```
0 / 0                   0
0 / 1                   0
0 / 8                   0
0 / Infinity            0
0 / -0                 -0
0 / -1                 -0
0 / -8                 -0
0 / -Infinity          -0
-0 / 0                 -0
-0 / 1                 -0
-0 / 8                 -0
-0 / Infinity          -0
-0 / -0                 0
-0 / -1                 0
-0 / -8                 0
-0 / -Infinity          0
1 / 0                   Infinity
8 / 0                   Infinity
Infinity / 0            Infinity
1 / -0                 -Infinity
8 / -0                 -Infinity
Infinity / -8          -Infinity
-1 / 0                 -Infinity
-8 / 0                 -Infinity
-Infinity / 0          -Infinity
-1 / -0                 Infinity
-8 / -0                 Infinity
-Infinity / -0          Infinity
Infinity / 1            Infinity
Infinity / 8            Infinity
Infinity / -1          -Infinity
Infinity / -8          -Infinity
-Infinity / 1          -Infinity
-Infinity / 8          -Infinity
-Infinity / -1          Infinity
-Infinity / -8          Infinity
Infinity / Infinity     1
Infinity / -Infinity   -1
-Infinity / Infinity   -1
-Infinity / -Infinity   1
1 / 1                   1
1 / 8                   0.125
1 / Infinity            0
1 / -1                 -1
1 / -8                 -0.125
1 / -Infinity          -0
-1 / 1                 -1
-1 / 8                 -0.125
-1 / Infinity          -0
-1 / -1                 1
-1 / -8                 0.125
-1 / -Infinity          0
8 / 1                   8
8 / 8                   1
8 / Infinity            0
8 / -1                 -8
8 / -8                 -1
8 / -Infinity          -0
-8 / 1                 -8
-8 / 8                 -1
-8 / Infinity          -0
-8 / -1                 8
-8 / -8                 1
-8 / -Infinity          0
1 / 0.125               8
0.1 / 0.2               0.5
10 / -3                 -3.333333
1 / 0.0000000000000001  10000000000000000

```

**Other:**

This is , so shortest answer in bytes (per language) wins!

# Answer
> 30 votes
# Haskell, 35 bytes

```
x?y|isNaN$x/y=tanh x*tanh y|0<1=x/y

```

Try it online!

The relevant function is `(?)`, which takes two `Double`s as input and returns a `Double` as output.

## How?

The hyperbolic tangent is an amazing function (two bytes shorter than `signum`!).

| `x` | `tanh x` |
| --- | --- |
| `0.0` | `0.0` |
| `-0.0` | `-0.0` |
| `Infinity` | `1.0` |
| `-Infinity` | `-1.0` |

# Haskell, ~~30~~ 29 bytes

```
x?y|x/y<=1/0=x/y|0<1=tanh$x*y

```

Try it online!

Using MarcMush's amazing trick, which relies on the well-known formula1 $$ \tanh(x\cdot y)=\tanh(x)\cdot\tanh(y). $$

---

1 I know, I know, maths.

# Answer
> 13 votes
# JavaScript (ES6), 45 bytes

Expects `(a)(b)`, as Numbers. Returns a Number.

```
a=>b=>a/b||+(b?1/a?a/b:a*b>0||-1:1/a/b<0&&-0)

```

Try it online!

## How?

Let \\$\mathbb{R}^\*\\$ be \\$\\{x\in\mathbb{R}\mid x\neq0\\}\\$.

### Direct answers when `a/b` is truthy

Whenever \\$a/b\\$ is neither `NaN` nor \\$0\\$, we know for sure that it is the expected answer. The cases that are covered that way are:

* \\$a\in\mathbb{R}^\*\\$, \\$b\in\mathbb{R}^\*\\$ : standard division of non-zero, non-infinite floats
* \\$a\in\mathbb{R}^\*\\$, \\$b=\pm0\\$ : resulting in either \\$+\infty\\$ or \\$-\infty\\$
* \\$a=\pm\infty\\$, \\$b\in\mathbb{R}^\*\\$ : resulting in either \\$+\infty\\$ or \\$-\infty\\$
* \\$a=\pm\infty\\$, \\$b=\pm0\\$ : resulting in either \\$+\infty\\$ or \\$-\infty\\$

### Other cases

If \\$a/b\\$ is zero'ish, we test \\$b\\$:

* If \\$b\neq\pm0\\$:
    + If \\$1/a\neq\pm0\\$, \\$a/b\\$ is also the correct answer, which is either \\$0\\$ or \\$-0\\$
    + If \\$1/a=\pm0\\$ (i.e. \\$a=\pm\infty\\$), we also have \\$b=\pm\infty\\$ and the answer is either \\$1\\$ or \\$-1\\$ depending on the sign of \\$a\times b\\$ (we do `a*b>0||-1`)
* If \\$b=\pm0\\$, we also have \\$a=\pm0\\$ and the answer is either \\$0\\$ or \\$-0\\$ depending on the signs of \\$a\\$ and \\$b\\$ (we do `1/a/b<0&&-0`)

---

# JavaScript (ES6),  ~~42~~  33 bytes

Using MarcMush's improvement of Delfad0r's excellent trick with **tanh** saves  ~~3~~  12 bytes.

```
a=>b=>a/b<=1/0?a/b:Math.tanh(a*b)

```

Try it online!

# Answer
> 12 votes
# Julia 0.7, 26 bytes

imaginary brownie points for using `tanh` instead of `sign` (thanks Delfad0r)

```
a$b=a/b<=Inf?a/b:tanh(a*b)

```

Try it online!

# Answer
> 9 votes
# , ~~98~~ ~~95~~ ~~89~~ 88 bytes

-6 bytes thanks to Giuseppe

```
function(x,y=abs(scan(t=x)))cat("-"[!!sd(grepl("-",x))],c(z<-y[1]/y[2],!!y)[1+is.na(z)])

```

Try it online!

Expects a vector of strings, as R cannot handle signed 0. Infinity will be input and output as `Inf`.

* `x` contains the input as 2 strings, and `y` is the conversion to numeric in absolute value.
* First, call `grepl("-",x)`, giving a vector of two booleans. We need to output a `-` sign iff the two booleans are different, ie if the standard deviation is non-0.
* Second, compute the division of the two values. R's division agrees with Ash's in most cases, but will give `NaN` for the two cases which are ambiguous: `0/0` and `Inf/Inf`. If the quotient is not NaN, we output it; otherwise, we compute the boolean `!!y[1]`, convert to integer, and output that.

Note that we can use `is.na` instead of `is.nan`, as `is.na(NaN)` returns `TRUE`. (The two functions are nonetheless not equivalent; `is.nan(NA)` returns `FALSE`.)

# Answer
> 7 votes
# Scratch, 310 bytes

Try it online!

In scratchblocks4:

```
when gf clicked
ask()and wait
set[N v]to(answer
ask()and wait
set[D v]to(answer
set[Q v]to((N)/(D
if<(Q)=[NaN]>then
if<(A)contains(0)?>then
set[Q v]to(0
else
set[Q v]to(1
end
end
if<<(join(N)(D))contains(-)?>and<not<<(N)contains(-)?>and<(D)contains(-)?>>>>then
if<(Q)contains(-)?>then
else
set[Q v]to(join(-)(Q

```

Alternatively, 37 blocks. No picture this time!

# Answer
> 5 votes
# JavaScript (Node.js), 32 bytes

```
a=>b=>a/b+b/a?a/b:Math.sign(a*b)

```

Try it online!

| Rule | JavaScript (IEEE 754) |
| --- | --- |
| Zero divided by anything is `0` | 0/0 is NaN;
Same results for other values |
| Anything other than `0` divided by `0` is `Infinity` | Same Results |
| Anything other than `Infinity` divided by `Infinity` is `0` | Same Results |
| `Infinity` divided by anything other than `Infinity` is `Infinity` | Same Results |
| `Infinity` divided by `Infinity` is `1` | Infinity/Infinity=NaN |
| All other division works as normal | Same Results |

From above comparsion, we can see that, we only need to handle values when `a/b` is NaN. And whenever `a/b` is NaN, `Math.sign(a*b)` is what we want here.

So we use `a/b+b/a` to test `NaN` here. As long as `a/b` is not `NaN`, `a/b`, `b/a` have same signs. And adding them would always yield non-zero value. We know only `0`, `-0`, `NaN` is falsy. And the value here is non-zero. So we can ensure the result is `NaN` if `a/b+b/a` is falsy.

# Answer
> 4 votes
# C (gcc), ~~169~~ 157 bytes

Thanks to @ceilingcat for the -12.

`tanh` seems like the way to go if you want to win this one, so I decided to try this without using any intrinsics, looking at the sign and exponents instead. `NaN` and denormals are not handled.

Annotated version:

```
*i,*j,w,x,t,u,v; char*z;
float f(a,b) float a,b; {
  i=&a; j=&b; // Get the integer representations of the floats
  w=*i*2; x=*j*2; // Move the exponents into the MSB of a copy
  t=*j; // Save the original value that will be clobbered
  u=3[z=&w]; v=3[z=&x]; // Get the exponents
  b=v?
      ~v? // x/!0
        ~u?
          j=0,a/b: // !INF/!(0,INF)=a/b (indicate normal division)
          1/0.: // INF/!(0,INF)=INF
        !~u: // INF/INF=1 or !INF/INF=0
      u? // x/0
        1/0.: // !0/0=INF
        0; // 0/0=0

  // Adjust the sign if normal division not used
  // (if one value is negative, it will flip the sign)
  j?*j^=(*i^t)&1<<31:0;
  a=b; // Store the result in the return
}

```

```
*i,*j,w,x,t,u,v;char*z;float f(a,b)float a,b;{i=&a;j=&b;w=*i*2;x=*j*2;t=*j;u=3[z=&w];v=3[z=&x];b=v?~v?~u?j=0,a/b:1/0.:!~u:u?1/0.:0;j?*j^=(*i^t)&1<<31:0;a=b;}

```

Try it online!

# Answer
> 4 votes
# Jelly, 48 bytes

```
ẸṂ=?
ñç÷?
÷×¹?
®+©ṛ
”-eÇ
Ḋ⁸Ç?
ɠÇŒV
-1*®
7£2ŀ7£×¢

```

Takes input as newline-separated strings in STDIN, zero is `0.0`, and infinity is `inf`.

Try it online!

### How?

```
ẸṂ=?           - 1: λxλy: any(x, y) if x == y else min(x, y)
ñç÷?           - 2: λxλy: line3(x, y) if x÷y else line1(x, y)
÷×¹?           - 3: λxλy: x÷y if x else x×y
®+©ṛ           - 4: λx: add x to register; return x
”-eÇ           - 5: λx: link4("-" in x)
Ḋ⁸Ç?           - 6: λx: x[1:] if link5(x) else x
ɠÇŒV           - 7: eval(link6(read from stdin))
-1*®           - 8: (-1)^register
7£2ŀ7£×¢       - main: link2(link7, link7) * link8

```

---
Tags: code-golf, math, division, floating-point
---


title: Reach the number in minimum steps

text:
# Question
Title: Reach the number in minimum steps
In this challenge, you are given a number x. You have to find the minimum number of steps required to reach x from 1. At a particular point, you have two choices:

**1) Increment the number by 1**.

**2) Reverse the integer** (remove leading zeros after reversing)

```
Input: n=42
Output: 1>2>3>4>5>6>7>8>9>10>11>12>13>14>41>42 **(15 steps)**

```

The minimum steps to reach 42 from 1 is 15. This can be achieved if we increment numbers by 1 from 1 to 14 (13 steps). After reaching 14 we can reverse the number which will give us 41 (1 step). From 41 we can increment number by 1 to reach 42(1 step). Hence the total number is 15 steps, which is then the minimum.

Note that if we reverse the number after reaching 12 or 13, we will not get the minimum steps.

1\>2\>3\>4\>5\>6\>7\>8\>9\>10\>11\>12\>21\>22\>23\>32\>33\>34\>35\>36\>37\>38\>39\>40\>41\>42 **(25 steps)**

```
Input: n=16
Output: 1>2>3>4>5>6>7>8>9>10>11>12>13>14>15>16 **(15 steps)**

```

In this case we have to increment the numbers until we get 16, which will give us a minimum of 15 steps.

**Note**: Starting from 0 is also allowed, which will increase all output by 1.

# Answer
# Haskell, ~~82~~ 73 bytes

```
r=read.reverse.show
f 1=0
f a=1+(minimum$f(a-1):[f$r a|r a<a,mod a 10>0])

```

Try it online!

Simplest recursion method.

-9 bytes thanks to Christian Sievers
> 8 votes

# Answer
# C++, ~~140~~ ~~159~~ ~~147~~ 145 bytes

Edit: new solution without standard library, using a recursive function and pointer magic (constant 20 experimentally determined and not the same on other compilers)

Edit 2: -2 bytes thanks to ceilingcat

```
int*s,S,*G,x;int F(int Z,int*p=&x){int W=1,a=(*p)++,r=0;for(;r=r*10+a%10,a/=10;);G?W=r,p<=G?G=&W,S++,p=s:0:p=s=G=&W;return*p-Z&&W-Z?F(Z,p-20):S;}

```

Try it online!

```
int *s,S,*G,x;
int F(int Z,int*p=&x)
{
    int W=1,a=(*p)++,r=0;
    for(;r=r*10+a%10,a/=10;);
    G?W=r,p<=G?G=&W,S++,p=s:0:p=s=G=&W;
    return *p-Z&&W-Z?F(Z,p-20):S;
}

```

---

Old solution with standard library (159 bytes)

```
#include<set>
int Z(int N){int C=0,r,a;std::set T{1},S{1};for(;;++C,T=S,S={})for(int i:T){if(i==N)return C;for(r=0,a=i;r=r*10+a%10,a/=10;);S.insert({i+1,r});}}

```

Try it online!

```
int Z(int N)
{
    int C = 0, r, a;
    set T{ 1 }, S{ 1 };
    for (;; ++C, T = S, S = {})
        for (int i : T)
        {
            if (i == N)
                return C;
            for (r = 0, a = i; r = r * 10 + a % 10, a /= 10;);
            S.insert({ i + 1,r });
        }
}

```

Edit: add #include to byte count
> 5 votes

# Answer
# Jelly, 16 bytes

Recursion might well end up being less bytes.

```
ṚḌ;‘))Fṭ
1Ç¡ċ€ċ0

```

A monadic Link accepting a positive integer which yields a non-negative integer

**Try it online!**
Or try a faster, 17 byte version

### How?

```
ṚḌ;‘))Fṭ - Helper Link: next(achievable lists)
     )   - for each (list so far):
    )    -   for each (value, V, in that list):
Ṛ        -     reverse the digits of V
 Ḍ       -     convert that to an integer
   ‘     -     increment V
  ;      -     concatenate these results
      F  - flatten the results
         -   * with a Q here we de-duplicate these results making things faster
       ṭ - tack that to the input achievable lists

1Ç¡ċ€ċ0 - Main Link: positive integer, N
1       - literal one
  ¡     - repeat this (implicit N) times:
 Ç      -   the last Link as a monad - N.B. 1 works just as well as the list of lists [[1]]
   ċ€   - for each count the occurrences of (implicit N)
     ċ0 - count the zeros (i.e. the number of lists that did not yet contain N)

```
> 4 votes

# Answer
# 05AB1E (legacy), ~~15~~ 13 bytes

```
1¸[ÐIå#ís>«}N

```

-1 byte and much faster thanks to *@Jitse*, which also opened an opportunity for a second -1 byte.

Try it online or verify the first 100 test cases (with added `Ù` -uniquify- to increase the speed).

**Explanation:**

```
1¸        # Push 1 and wrap it into a list: [1]
  [       # Start an infinite loop:
   Ð      #  Triplicate the list
    Iå    #  If the input-integer is in this list:
      #   #   Stop the infinite loop
    í     #  Reverse each integer in the copy-list
     s    #  Swap to get the initial list again which we triplicated
      >   #  Increase each value by 1
       «  #  And also merge it
  }N      # After the infinite loop: push the loop-index
          # (which is output implicitly as result)

```

Uses the legacy version of 05AB1E, because using the index `N` outside a loop like that doesn't work in the new version.
> 2 votes

# Answer
# Perl 6, ~~26~~ 25 bytes

```
{+(1,{1+$_|+.flip}...$_)}

```

Try it online!

Does pretty much as the question asks. Starting from 1, either increment the Junction of values or flip it, repeating this until we find the one value we're looking for. Then return the length of the sequence. This is zero-indexed (as in, `1` returns `1`)

This times out for testcases with a larger number of steps, since for every step we're doubling the size of the Junction by running two operations over the entire thing.
> 2 votes

# Answer
C++ Recursive Solution:

```
int reverse(int n)//reverses the number
{
    int rev=0;
    while(n>0)
    {
        rev=rev*10+n%10;
        n/=10;
    }

    return rev;
}

int sol(int n, int x)
{
    if(n==x)// base case
        return 0;

    if(n>x)// base case
        return 1e5;

    if(reverse(n)<=n)// otherwise, recursion will happen infinitely
        return 1+sol(n+1,x);

    return 1+min(sol(n+1,x),sol(reverse(n),x));

}

int main()
{
   cout<<sol(1,42);
   return 0;
}

```

C++ Dynamic Programming Solution:

```
int dp[1000];
int reverse(int n)//reverses the number
{
    int rev=0;
    while(n>0)
    {
        rev=rev*10+n%10;
        n/=10;
    }

    return rev;
}

int sol(int n, int x)
{
    if(n==x)// base case
        return 0;

    if(n>x)// base case
        return 1e5;

    if(dp[n]!=-1)
        return dp[n];

    if(reverse(n)<=n)// otherwise, recursion will happen infinitely
        return dp[n]=1+sol(n+1,x);

    return dp[n]=1+min(sol(n+1,x),sol(reverse(n),x));

}

int main()
{

    fill_n(dp,1000,-1);

    sol(1,42);
    cout<<dp[1];
    return 0;
}

```
> 1 votes

# Answer
# Ruby, 67 bytes

Starts from 0. I noticed GB's Ruby solution after I finished my own, but the approaches used are drastically different (recursive vs. non-recursive) so I decided to post anyways.

```
f=->n{r=n.digits.join.to_i;n<9?n:[f[n-1],n>r&&n%10>0?f[r]:n].min+1}

```

Try it online!
> 1 votes

# Answer
# Charcoal, 47 bytes

```
Ｎθ≔⁰ηＷ⊖θ«Ｆ∧⁻⊖θＸχ⊖Ｌθ¬﹪⊖θＸχ÷⊕Ｌθ²«≦⮌θ≦⊕η»≦⊖θ≦⊕η»Ｉη

```

Try it online! Link is to verbose version of code. Explanation:

```
Ｎθ

```

Input the target.

```
≔⁰η

```

Set the number of steps to zero.

```
Ｗ⊖θ«

```

Repeat until the target becomes 1.

```
Ｆ∧⁻⊖θＸχ⊖Ｌθ¬﹪⊖θＸχ÷⊕Ｌθ²

```

Look to see if the target is of the form `xxx0001` or `xxxx0001`, but not `10..01`. (This expression fails for `1`, but fortunately the loop stops before we get here.)

```
«≦⮌θ≦⊕η»

```

If so then reverse the target and increment the number of steps.

```
≦⊖θ≦⊕η

```

Decrement the target and increment the number of steps.

```
»Ｉη

```

Output the number of steps once the target has been reduced to 1.
> 0 votes

# Answer
# Python 3, 78 bytes

```
f=lambda n,s={1}:n in s or-~f(n,{int(str(i)[::-1])for i in s}|{i+1for i in s})

```

Try it online!

Uses 0-indexing. Note that in Python `True == 1`.
> 0 votes

# Answer
# Ruby, 72 bytes

```
->i{*w=0;(0..i).find{[]==[i]-w=w.flat_map{|z|[z+1,z.digits.join.to_i]}}}

```

Try it online!
> 0 votes

# Answer
# Haskell, ~~71~~ 60 bytes

```
g[1]
g l x|elem x l=0|1>0=g([succ,read.reverse.show]<*>l)x+1

```

Try it online!

Considerably less efficient than 79037662's existing Haskell answer, but ~~2~~ 13 bytes is ~~2~~ 13 bytes.

### Explanation:

```
g[1]

```

The relevant function: call `g` with `[1]` as its first argument, `l`.

```
g l x|elem x l=0

```

`g` takes two arguments, `l` and `x`, and returns 0 if `l` contains `x`.

```
|1>0=g( ... )x+1

```

Otherwise, it returns 1 plus its return value for a modified value of `l`:

```
[ ... ]<*>l

```

Apply each function from a list of functions to each element of `l`, returning the results in a flat list, using the `Applicative` instance of lists. `succ` adds 1, and...

```
read.reverse.show

```

takes the string representation of its argument, reverses it, then re-interprets it as whatever the type is of the other list elements.
> 0 votes

---
Tags: code-golf, number, path-finding
---


title: Letters between two letters

text:
# Question
Title: Letters between two letters
Write a program that accepts a single lowercase word as input and outputs the number of pairs of letters that have the same number of letters between them in the word as in the alphabet.

For example, in the word 'nature', we have 4 pairs:

* nr: since there are three letters between them inside the word (a, t, u) and three letters between them in the alphabet (o, p, q)
* ae: since there are three letters between them inside the word (t, u, r) and three letters between them in the alphabet (b, c, d)
* tu: since there are no letters between them inside the word and no letters between them in the alphabet
* tr: since there is one letter between them inside the word (u) and one letter between them in the alphabet (s)

Since there are four pairs, the output in this case should be 4.

# Answer
> 5 votes
# Pyth, 19 bytes

```
lfqF-MSMCT.cCUBCMz2

```

Try it online: Demonstration

### Explanation:

```
lfqF-MSMCT.cCUBCMz2
                 z   read a string from input
               CM    convert into list of ascii-values
            CUB      create a list of pairs (ascii-value, index in string)
          .c      2  all combinations of length 2
 f                   filter for combinations T, which satisfy:
        CT              transpose T ((ascii1, ascii2), (index1, index2)
      SM                sort each list
    -M                  create the the difference for each
  qF                    check if they are equal
l                    print the number of remaining combinations

```

# Answer
> 4 votes
## R, 110 bytes

```
function(s){w=strsplit(s,"")[[1]]
O=outer
n=nchar(s)
sum(abs(O(r<-match(w,letters),r,"-"))==O(1:n,1:n,"-"))-n}

```

Degolfed:

```
F = function(s){
   chars = strsplit(s,"")[[1]]
   num_chars = nchar(s)
   letter_rank = match(chars, letters)
   rank_dist = abs(outer(letter_rank, letter_rank, "-"))
   position_dist = outer(1:num_chars, 1:num_chars, "-")
   return(sum(rank_dist == position_dist) - num_chars)
}

F("nature")
# [1] 4
F("supercalifragilisticexpialidocious")
# [1] 25

```

# Answer
> 3 votes
# Octave, 41 bytes

```
@(s)nnz(abs(s-s')==(t=1:(u=nnz(s)))-t')-u

```

# Answer
> 3 votes
# CJam, 36 bytes

```
r:A,{)Aew}%1>{{:B,B0=BW=-z)=}%}%e_:+

```

Try it Online.

# Answer
> 3 votes
# Husk, 8 bytes

```
#S≡Γ·…→Q

```

Try it online!

## Explanation

```
#S≡Γ·…→Q
       Q all continuous sublists
#        number of sublists which satisfy:
 S≡      has the same shape and distribution of truthy/falsy values as:
   Γ·…→  the range between its first and last character?

```

# Answer
> 2 votes
# J, 27 bytes

```
#-:@-~#\+/@,@:=&(|@-/~)3&u:

```

Usage:

```
   (#-:@-~#\+/@,@:=&(|@-/~)3&u:) 'nature'
4

```

Explanation:

```
#-:@-~#\+/@,@:=&(|@-/~)3&u:
      #\                    lengths of input prefixes (1,2,...,length)
                       3&u: codepoints of input
               &(     )     with the last two do parallel:
                 |@-/~      create difference table with itself and take absolute values
              =             compare the elements of the two difference tables
        +/@,@:              sum the table
#   -~                      subtract the length of the input (self-similar letters)
 -:@                        half the result (each pair was accounted twice)

```

Try it online here.

# Answer
> 2 votes
# CJam, 25 bytes

```
l:T,_2m*{_:-\Tf=:-z=},,\-

```

Try it online

Explanation:

```
l     Get input.
:T    Store in variable T for later use.
,     Calculate length.
_     Copy for use at the very end.
2m*   Use Cartesian power to calculate all possible position pairs.
{     Start filter.
  _     Create copy of index pair.
  :-    Calculate difference between indices.
  \     Swap copy of index pair to top.
  T     Get input string stored in variable T.
  f=    Extract the letters for the index pair.
  :-    Calculate difference of the two letters.
  z     Take the absolute value.
  =     Compare index difference and letter difference.
},    End filter.
,\
-     Pairs of identical indices passed the filter. Eliminate them from the
      count by subtracting the length of the input.

```

# Answer
> 2 votes
# JavaScript (ES6), 98 bytes

```
f=w=>(p=0,q="charCodeAt",[...w].map((c,a)=>{for(b=a;w[++b];)p+=Math.abs(w[q](a)-w[q](b))==b-a}),p)

```

## Usage

```
f("nature")
=> 4

```

## Explanation

```
f=w=>(
  p=0,                                 // p = number of pairs
  q="charCodeAt",
  [...w].map((c,a)=>{                  // iterate through each character of input
                                       // a = character A index
    for(b=a;w[++b];)                   // iterate through the remaining input characters
                                       // b = character B index
      p+=                              // add 1 to p if true or 0 if false
        Math.abs(w[q](a)-w[q](b))==b-a // compare absolute difference of character codes
                                       //     to difference of indices
  }),
  p                                    // return p
)

```

# Answer
> 2 votes
# Jelly, ~~32~~ 16 bytes

```
ḢØaṣU1¦=
ṫJÇ€Fċ1

```

Try it online!

–16 when I learned how to reverse just the first element of a list.

### How?

```
ḢØaṣU1¦=  - helper monadic link, e.g. nature
Ḣ         - pop first character       n
 Øa       - lowercase alphabet        abcdefghijklmnopqrstuvwxyz
   ṣ      - split list                abcdefghijklm opqrstuvwxyz
    U1¦   - reverse first element     mlkjihgfedcba opqrstuvwxyz
       =  - equate with string        mlkjihgfedcba opqrstuvwxyz
                                    = ature         ature
                                   -> 00000hgfedcba 00010tuvwxyz

ṫJÇ€Fċ1   - main monadic link, e.g. nature
 J        - range                   1 2 3 4 5 6
ṫ         - tail; remove n-1 chars  nature ature ture ure re e
  Ç€      - map previous link       00000hgfedcba 00010tuvwxyz ...
    F     - flatten                 00000hgfedcba 00010tuvwxyz ...
     ċ1   - count 1s                4

```

# Answer
> 1 votes
# Python 2, 91 chars

```
lambda i:sum(y-x==abs(ord(i[y])-ord(i[x]))for x in range(len(i))for y in range(x+1,len(i)))

```

# Answer
> 1 votes
## MATLAB, 84 bytes

```
s=input('');disp(sum(diff(nchoosek(find(s),2),[],2)==abs(diff(nchoosek(s,2),[],2))))

```

This line asks for a string as input. It then creates all possible pairs of letters and does the same for their corresponding indices. Then we determine whether the (absolute) difference of the values matches to finally sum all cases where it does. The result is displayed in the command window.

# Answer
> 1 votes
## PowerShell, ~~114~~ 100 Bytes

```
param($a)$b=$a.length;0..($b-1)|%{$i=$_;($_+1)..$b|%{$o+=[math]::Abs(+$a[$_]-$a[$i])-eq($_-$i)}};+$o

```

Pretty straight-forward, but uses a couple tricks.

* `param(..)` takes our input, saves it to `$a`.
* We set a temp variable `$b` to be the `.length` of our input. This saves a byte later.
* `0..($b-1)|%{..}` is the equivalent of a `for($i=0;$i-le($b-1);$i++){..}` loop, but quite a lot shorter.
* However, we need to set variable `$i` in order to keep that going into ...
* `($_+1)..$b|%{..}` the next `for` loop, since `$_` is only positional to the inner loop.
* We then use a lengthy .NET call to check if the absolute value between our two characters (here we use implicit casting with prepending `+` to save a bunch of bytes) is `-eq`ual to the positional difference in the array. Since we're explicitly given lowercase input, we don't need to do case conversion. This statement will return either `True` or `False`.
* We blatantly abuse implicit casting again to accumulate that result into `$o`, so `True` will add 1, while `False` will add 0.
* Once the loops are finished, we output `$o`. Note we need to do the same tricksy-cast-to-int with `+` to avoid printing `False` if there were no matches.

# Answer
> 1 votes
# JavaScript ES7, 93

Using *array comprehension*. ES6 with `.map.map.map` is 2 bytes longer.

Test running the snippet below with Firefox

```
f=s=>[for(x of s)x.charCodeAt()].map((a,i,s)=>s.map((b,j)=>t+=j>i&(b>a?b-a:a-b)==j-i),t=0)&&t

document.write('nature'+'\n'+f('nature'))
```

# Answer
> 0 votes
## Matlab~~(94)~~(80)

> Edit: I didnt take in case inversed alphabetic order,as (t,r) in 'nature', so more bytes to upweight :(

```
@(a)sum(arrayfun(@(x)sum(1:nnz(find(a==fix(x/2)+(-1)^x*(1:1:nnz(a))))-1),2:244))

```

---

* ~~binomial function throws a stupid exception when k is bigger than n and I cant catch exceptions inside `arraycell` function, otherwise I could golf it more.~~ **Who needs a built in function ??**

Now I could just do it by hand, simplifying binomial(n,2)=n/(2(n-2)!)=n(n-1)/2. remark that this last value reprensents sum of integers from 1 to n-1, this doesnt throw any exception in matlab, God bless maths.
* Ps: this method is diferent than slvrbld's

## Execution

```
  >> ans('abef')

  ans =

       2

  >> ans('abcd')

  ans =

       6

  >> ans('nature')

  ans =

       4

```

# Answer
> 0 votes
# Ruby, 74

```
 ->s{[*0...s.size].permutation(2).count{|i,j|(s[i].ord-s[j].ord).abs==j-i}}

```

Nothing super interesting here. I would have loved to use `eval("s[i].#{["succ"]*(j-i)*?.}")` but... seemed too long.

# Answer
> 0 votes
# Jelly, 12 bytes

```
ONƬ_JLƙ€c2SS

```

Try it online!

Got too caught up in figuring out the best way to do this with  and forgot to post an answer at all, but now that I've remembered I think I might leave that as an exercise to @cjquines ;)

---
Tags: code-golf
---


title: Work it harder, make it better

text:
# Question
Title: Work it harder, make it better
In this challenge your goal will be to output the lyrics to Daft Punk's Harder, Better, Faster, Stronger. Specifically, output this text:

```
Work It
Make It
Do It
Makes Us
Harder
Better
Faster
Stronger
More Than
Hour
Our
Never
Ever
After
Work Is
Over

Work It
Make It
Do It
Makes Us
Harder
Better
Faster
Stronger
More Than
Hour
Our
Never
Ever
After
Work Is
Over

Work It Harder Make It Better
Do It Faster, Makes Us Stronger
More Than Ever Hour After
Our Work Is Never Over

Work It Harder Make It Better
Do It Faster, Makes Us Stronger
More Than Ever Hour After
Our Work Is Never Over

Work It Harder Make It Better
Do It Faster, Makes Us Stronger
More Than Ever Hour After
Our Work Is Never Over

Work It Harder Make It Better
Do It Faster, Makes Us Stronger
More Than Ever Hour After
Our Work Is Never Over

Work It Harder Make It Better
Do It Faster, Makes Us Stronger
More Than Ever Hour After
Our Work Is Never Over

Work It Harder Make It Better
Do It Faster, Makes Us Stronger
More Than Ever Hour After
Our Work Is Never Over

Work It Harder Make It Better
Do It Faster, Makes Us Stronger
More Than Ever Hour After
Our Work Is Never Over

Work It Harder, Make It
Do It Faster, Makes Us
More Than Ever, Hour
Our Work Is Never Over

Work It Harder Make It Better
Do It Faster, Makes Us Stronger
More Than Ever Hour Af-
Our Work Is Never Over

Work It Harder Make It Better
Do It Faster, Makes Us Stronger
More Than Ever Hour Af-
Our Work Is Never Over

Work It Harder Make It Better
Do It Faster, Makes Us Stronger
More Than Ever Hour Af-
Our Work Is Never Over

Work It Harder
Make It Better
Do It Faster Makes Us Stronger
More Than Ever Hour
Our Work Is Never Over

Work It Harder
Do It Faster
More Than Ever
Our Work Is Never Over

Work It Harder
Make It Better
Do It Faster
Makes Us Stronger
More Than Ever
Hour After
Our Work Is Never Over

```

Your output may have a trailing newline or trailing whitespace.

**Built in compression methods are not allowed.**

This is code golf, so shortest code wins!

# Answer
# Ruby, ~~308~~ 303

```
puts a='Work It|Make It|Do It|Makes Us|Harder|Better|Faster|Stronger|More Than|Hour|Our|Never|Ever|After|Work Is|Over

'.split(?|),a
56.times{|i|puts a[j=i%4/2*4+i%4*2]+' '+a[j+4]+[[' ',', ','
']["l4yq62lhgnizb0kfu".to_i(36)/3**i%3]+a[j+1]+' ',''][i%51/48]+[a[j+5],['','Af-'][i%44/32]][7619655>>i-28&1]}

```

**Algorithm**

Song intro: Take 16 tokens, and print them twice (last one bears an extra newline)

Verses: Riffle the tokens together to make the verses, 4 tokens per line, in the following order:

```
 0  4  1  5
 2  6  3  7
 8 12  9 13
10 14 11 15

```

In some lines, the last token is omitted, or exchanged for `Af-`. These lines are noted with a 1 bit in the magic number 0x744447=7619655.

In three lines, the penultimate token is also omitted, those where `i%51/48==1`

The punctuation in the middle of the line can be one of `' '` `', '` `'\n'`. These are encoded in the number 02220010000200100010001001110010001000100010001000100010 (base 3) = "l4yq62lhgnizb0kfu" (base 36.)

**With comments**

```
puts a='Work It|Make It|Do It|Makes Us|Harder|Better|Faster|Stronger|More Than|Hour|Our|Never|Ever|After|Work Is|Over

'.split(?|),a                                                    #Set up array containing all 16 tokens, print it, and print it again (note newlines at end of last token.)

56.times{|i|                                                     #14 verses, 4 lines each

puts a[j=i%4/2*4+i%4*2]+                                         #expression cycles through 0,2,8,10. Print the first token on the line.

' '+a[j+4]+                                                      #print a space, and the second token on the line.

[[' ',', ','
']["l4yq62lhgnizb0kfu".to_i(36)/3**i%3]+a[j+1]+' ',''][i%51/48]+ #if i%51/48==1,print nothing. Otherwise print the 3rd token, followed by a space, and preceded by one of ' ' or ', ' or '\n'

[a[j+5],['','Af-'][i%44/32]][7619655>>i-28&1]                    #if 7619655>>i-28&1==0 print the fourth token. Otherwise print either nothing or Af- depending on the value of i%44/32

}

```
> 12 votes

# Answer
# Perl, ~~316~~ ~~309~~ ~~308~~ 307 bytes

The source must be encoded as Latin-1.

```
@c=split b,'
Â×
Ô
ÚáÐÙáÒ
ÅOÆÖáEváAftáØ
bÑÏábÝà
bÑÈ-
bÈÇÈÇbHoÆbur
btáÑbÏßËÌÊßÉbHoÜAfbÔ ÒÍbÝà ÐÎber, b Evb× ÙbÓ ÚbBettábOÜØ ÖßbStrongáÛbÕ
ÞàbÝs UsbOvábNevbDoàbÞ IsbFastbHardbMore Thanbur bMakebWorkber b Itber
';$e='ÞàÀÓÀÄÄÄÈÇÏÌÂÎÌÔ
ÛÍÌÅÃÃÃÁËßÊßÅÁÎáÛÍáÁËáÊáÉÇÕ';$f=chr$_+192,$e=~s/$f/$c[$_]/g for 0..34;print$e

```

# Explanation

We start out with the original lyrics. For brevity, let’s assume they are

```
lyrics = "Work Work Harder Harder"

```

Now we find short substrings (≥ 3 characters) that occur often. In this case, `"Work "` occurs twice. We replace each occurrence with character 0xE1. We also remember the replaced string in an array:

```
lyrics = "ááHarder Harder"
substs = ["Work "]

```

The next substring, `"Harder"`, is replaced with 0xE0. The `substs` array grows towards the front:

```
lyrics = "ááà à"
substs = ["Harder", "Work "]

```

This continues for a total of 34 iterations until we get to character 0xC0.

Now we concatenate the `substs` using the character `b` (which doesn’t occur in the lyrics) as a separator. In the Perl code, the `substs` array is stored in `@c` (using the bareword `b` to tell `split` where to split), the new jumbled lyrics are in `$e`, and the code simply reverses the 34 substitutions.
> 10 votes

# Answer
# Sprects, 302 bytes

```
:xxnnnnnnnmW12603 27428 3s59qp wb12604280qpb12603 2742803s59qp0wjb:ncvb:mcQb:WcEb:x1203 204203s50607809q0w0y0i0p0j01l0z00:c1263 27428, 3s59:vqp wj:Qqp, w:Eqp wAf-:b0y1liz00:0\n:1Work :2It :3Make:4Do :5 Us :6Harder :7Better\n:8Faster:9Stronger\n:qMore Than :wHour :yOur :iNever :pEver:jAfter :lIs :zOver

```

I just recently made this language and I decided to test it out with this challenge. It outputs `\n`s instead of new lines because it outputs into HTML, but the interpreter is written in JavaScript. Because of this, here's a version with `<br>`s instead of `\n`s:

```
:xxnnnnnnnmW12603 27428 3s59qp wb12604280qpb12603 2742803s59qp0wjb:ncvb:mcQb:WcEb:x1203 204203s50607809q0w0y0i0p0j01l0z00:c1263 27428, 3s59:vqp wj:Qqp, w:Eqp wAf-:b0y1liz00:0<br>:1Work :2It :3Make:4Do :5 Us :6Harder :7Better<br>:8Faster:9Stronger<br>:qMore Than :wHour :yOur :iNever :pEver:jAfter :lIs :zOver

```
> 6 votes

# Answer
## GolfScript (275 bytes)

This contains non-printable ASCII characters, so here's a hexdump:

```
0000000: 3a6b 2757 6f72 6b20 4974 0a4d 616b 6586  :k'Work It.Make.
0000010: 0444 6f8c 0873 2055 730a 4861 7264 6572  .Do..s Us.Harder
0000020: 0a42 6574 7485 0346 6173 8504 5374 726f  .Bett..Fas..Stro
0000030: 6e67 9503 4d6f 7265 2054 6861 6e0a 486f  ng..More Than.Ho
0000040: 7572 0a4f 8203 4e65 76ae 0345 8304 4166  ur.O..Nev..E..Af
0000050: b204 df06 730a 4f96 048c 07ed 7020 d606  ....s.O.....p ..
0000060: 20f4 0720 de07 fb05 20e4 062c 9b05 7320   .. .... ..,..s
0000070: 5573 20ee 1220 df04 20f3 0420 e406 f903  Us .. .. .. ....
0000080: 20e8 0720 4e65 9b04 eeff eeff eeb6 d206   .. Ne..........
0000090: fe03 e817 df0f 2ce0 05da 5c27 d908 2042  ......,...\'.. B
00000a0: 6574 d303 e017 2053 7472 6f6e 67bd 03e9  et.... Strong...
00000b0: 0ee8 0520 4166 2dec ffec 040a ec1b eb26  ... Af-........&
00000c0: e728 d80c c60f c128 4d61 6b65 d004 4265  .(.....(Make..Be
00000d0: 74c3 04d0 0e9a 0373 2055 7320 5374 726f  t......s Us Stro
00000e0: 6e67 e212 486f e303 4166 fc04 ed16 277b  ng..Ho..Af....'{
00000f0: 6b7b 7b6b 247d 2a30 3a6b 3b7d 7b31 3237  k{{k$}*0:k;}{127
0000100: 2e32 243c 7b2d 3a6b 7d2a 3b7d 6966 7d2f  .2$<{-:k}*;}if}/
0000110: 5d28 2b                                  ](+

```
> 4 votes

# Answer
# Ruby - 643 bytes

Edit: Golfed down from 899 to 830.

Edit2: 830 -\> 755.

Edit3: 755 -\> 684.

Edit4: 684 -\> 670.

Edit5: 670 -\> 643.

I haven't really used ruby, so I'm sure this could be golfed down, this is just an attempt:

```
l=%w[Work Make Do Harder Better Faster Stronger More Than Hour Our Never Ever After Over Faster,]
i,j,f,u,d=->x{l[x]+' It'},->x,y{l[x]+' It '+l[y]+' '},->a,b,c,d,e{a+' '+b+' '+c+' '+d+' '+e},'s Us ',l[6]
s,q,w,e,r,y,k=f[l[10],l[0],'Is',l[11],l[14]],j[0,3],j[1,4],j[2,15],j[2,5],->d,e{f[l[7],l[8],l[12],d,e]},l[1]+u
t,z,m=e+k,->a{puts q+w,t+d,y[l[9],a],s,''},y['','']
2.times{puts i[0],i[1],i[2],k,l[3],l[4],l[5],d,l[7]+' '+l[8],l[9],l[10],l[11],l[12],l[13],l[0]+' Is',l[14],''}
7.times{z[l[13]]}
puts q+i[1],t,f[l[7],l[8],l[12]+',',l[9],''],s,''
3.times{z['Af-']}
puts q,w,r+k+d,y[l[9],''],s,'',q,r,m,s,'',q,w,r,k+d,m,l[9]+' '+l[13],s

```
> 2 votes

# Answer
# JavaScript ES6, ~~440 bytes~~ 438 bytes

This is a bunch of simple compression optimizations. As a one-liner:

```
eval("a='w_m_d_u_h_b_f_s_M_H_O_N_E_A_W_VX';b='w hTm b_d f,Tu s_M ETH A_O W N VX';c=bRA/,'Y');o={};'wWork It|mMake It|dDo It|uMakes Us|hHard&bBett&fFast&sStrong&MMore Than|HHour|OOur|NNev&EEv&AAft&WWork Is|VOv&X\\n\\n|YAf-|_\\n|T 'R&/g,'er|').split('|').map(x=>o[x[0]]=x.slice(1));console.log((a+a+b.repeat(7)+bR._/g,'_')R,?T/g,',T')+c+c+c+bRT/,'_')R,/,'')+bR,?T. ._/g,'_')+bR,?T/g,'_'))R\\w/g,x=>o[x]).trim())".replace(/R/g,'.replace(/'))

```

This was written to be an executable script via `iojs --harmony_arrow_functions file.js`; you can shave off the `console.log()` overhead depending on the meaning of "output the lyrics".

## Explanation

After performing the outer `.replace()`, the code fed to `eval` is:

```
// The first three lines, with each phrase compressed to a single character, newlines
// compressed to _, and block-endings compressed to X. Call this compressed-format.
a = 'w_m_d_u_h_b_f_s_M_H_O_N_E_A_W_VX';

// The compressed-format main block: this is repeated seven times literally but
// every other stanza, besides `a` above, ultimately uses some simple variant
// of this block.
b = 'w hTm b_d f,Tu s_M ETH A_O W N VX';
// The new character T above is a new character we're adding to compressed-format, it is
// a space in the main block but also a hook for some regular expressions later.

// We need one more entry in compressed-format: some blocks, here assigned to
// the variable `c`, shorten "After" to Y = "Af-".
c = b.replace(/A/, 'Y');

// Now we want to build a lookup table for this compressed format above. That is done by
// these lines, which have also been compressed:
o={};
'wWork It|mMake It|dDo It|uMakes Us|hHard&bBett&fFast&sStrong&MMore Than|HHour|OOur|NNev&EEv&AAft&WWork Is|VOv&X\n\n|YAf-|_\n|T '
    .replace(/&/g, 'er|')
    .split('|')
    .map(x => o[x[0]] = x.slice(1));
// The fact that so many fragments end in 'er' allows us to actually shave a couple
// bytes above, but the compression scheme is fundamentally creating a dict like
//     {a: "Phrase 1", b: "Phrase 2", c: "Phrase 3", d: "Phrase 4"}
// from the string "aPhrase 1|bPhrase 2|cPhrase 3|dPhrase4".

// Now we have the part that actually does the work:
console.log(
    ( // build-string phase
        // first two opening blocks `a`
        a + a +

        // seven repetitions of `b`
        b.repeat(7) +

        // a version of `b` without final words and with commas before each T.
        b.replace(/._/g, '_').replace(/,?T/g, ',T') +

        // three repetitions with the 'Af-' suffix.
        c + c + c +

        // one with the first T converted into a newline and no commas
        b.replace(/T/, '_').replace(/,/, '') +

        // one with only the first halfs of the three lines
        b.replace(/,?T. ._/g, '_') +

        // one with no commas and all T's converted to newlines.
        b.replace(/,?T/g, '_')
    ) // end build-string phase
    // Now we convert from compressed-format to actual format
    .replace(/\w/g, x => o[x])
    // We are only told that one trailing newline is allowed; we have two extra:
    .trim()
)

```

# Kudos

* @vihan, who reminded me that ES6 also has this shiny new `.repeat` function for strings, saving 2 bytes.
> 2 votes

# Answer
## JAVA 518/490Bytes

Edit: unneeded 7 Bytes and added a Java 6 version with the static{} trick Edit2: Explanation expand

```
class E{public static void main(String[]_){String l="\n#, #Work#Make#Do#Makes Us#Hard#Bett#Fast#Strong#More#Than#Hour#Our#Nev#Ev#Aft#Af-#Work Is#Ov# #er# It",a="cwadwaewafagvahvaivajvakulamanaovapvaqvasatvaa",z="anusuovutvaa",y="kulupvu",x="cwugv",w="fujva",b=x+"udwuhvuaewuivb"+w,c=b+y+"muqvu"+z,d=x+"bdwaewuivbfakulupvbm"+z,e=b+y+"mur"+z,f=x+"adwuhvaewuivu"+w+y+z+x+"aewuivakulupv"+z+x+"adwuhvaewuiva"+w+"kulupvamuqv"+z,r=a+a+c+c+c+c+c+c+c+d+e+e+e+f;for(char o:r.toCharArray())System.out.print(l.split("#")[o-97]);}}

```

java6:

```
class E{static{String l="\n#, #Work#Make#Do#Makes Us#Hard#Bett#Fast#Strong#More#Than#Hour#Our#Nev#Ev#Aft#Af-#Work Is#Ov# #er# It",a="cwadwaewafagvahvaivajvakulamanaovapvaqvasatvaa",z="anusuovutvaa",y="kulupvu",x="cwugv",w="fujva",b=x+"udwuhvuaewuivb"+w,c=b+y+"muqvu"+z,d=x+"bdwaewuivbfakulupvbm"+z,e=b+y+"mur"+z,f=x+"adwuhvaewuivu"+w+y+z+x+"aewuivakulupv"+z+x+"adwuhvaewuiva"+w+"kulupvamuqv"+z,r=a+a+c+c+c+c+c+c+c+d+e+e+e+f;for(char o:r.toCharArray())System.out.print(l.split("#")[o-97]);}}

```

Thanks to @Chris Drost for the hint with the many "ER"s in the text. First String is a lookup table, second part uses the lowercase letters (which are a sequential block in ascii) as a index into the table by subtracting the magic value of a from the value.

Second part consists of multiple Strings of different length (short ones are common parts shared between multiple verses) which get assembled to a long one before the looping through the chars happens
> 2 votes

# Answer
# PowerShell, 659 Bytes

```
$a=@(" ","`n",",","Stronger","Make It","Do It","Makes Us","Harder","Better","Faster","Work It","More Than","Hour","Our","Never","Ever","After","Work Is","Over","Af-")
$z="1000070"
$y="01130017001400180101"
$x="010500090200060"
$v="00301110015001200"
$b="100104010501060107010801090103011101120113011401150116011701180101"
$c=$z+"0040008$x$v"+"16$y"
$d=$z+"20004$x"+"1110015020012$y"
$e=$z+"0040008$x$v"+"19$y"
$f=$z+"10400080105000900060003011100150012$y"
$g=$z+"105000901110015$y"+"10000701040008010500090106000301110015011200160113001700140018"
$($b,$b,$c,$c,$c,$c,$c,$c,$c,$d,$e,$e,$e,$f,$g|%{for($i=0;$i-lt$_.length;$i+=2){$a[$_.Substring($i,2)]}})-join''

```

Creates an array of keywords `$a`, then encodes the lyrics using a series of numerical strings which are sent into a `for` loop. The loop takes two-digit substrings, pulls the corresponding keyword from the `$a` array, and finally the `-join''` concatenates it all together.

I think this is about as good as this method can be done, as every time I tried to golf further (e.g., replacing `040008` with a new variable), it turned out to be a couple bytes longer because the substring length wasn't enough to account for all the extra quotes needed. Though there have been some new answers posted since I started that have slightly different methods that look like they might be shorter in PowerShell (like using ASCII characters to encode, rather than two-digits, maybe?), I'm going to stick with this one.

Edit - forgot the replacement encoding I used:

```
00  <space>
01  `n
02  ,
10  Work It
04  Make It
05  Do It
06  Makes Us
07  Harder
08  Better
09  Faster
03  Stronger
11  More Than
12  Hour
13  Our
14  Never
15  Ever
16  After
17  Work Is
18  Over
19  Af-

```
> 1 votes

# Answer
# GolfScript, 251 bytes golfed

```
'Work It
Make It
Do It
Makes Us
Harder
Better
Faster
Stronger
More Than
Hour
Our
Never
Ever
After
Work Is
Over

'2*.n/:a;56,{:@4%.2&+2*:^a=' ':|4^+a='jSRSSS]SSSSSST'81base 3@?/3%[|', 'n]=^)a=+@ 51%48/!*|237118176 2 55@-?/1&@44%32/'Af-'*5^+a=if^9/n*n}/

```

Try it online!

Eliminated unnecessary `[]` and simplified code accordingly. Changed `i` and `j` to `@` and `^` to permit removal of whitespace. Assigned first occurence of `' '` to variable `|` to avoid repeating the same three characters.

# GolfScript, First working version 262 bytes

```
'Work It
Make It
Do It
Makes Us
Harder
Better
Faster
Stronger
More Than
Hour
Our
Never
Ever
After
Work Is
Over

'2*.n/:a;56,{:i;[i 4%.2&+2*:j a=' '4j+a='jSRSSS]SSSSSST'81base 3i?/3%[' '', 'n]=j)a=+i 51%48/!*' '237118176 2 55i-?/1&i 44%32/'Af-'*5j+a=if j 9/n*n]}/

```

Try it online!

This is a port of my Ruby answer into golfscript using the same basic algorithm: output the list of tokens twice, then riffle them into the verses and build the verses line by line, adjusting for the peculiarities of each.

There are a couple of differences. The number for the correct mid-line punctuation is in base 81 (conveniently this makes one printable ascii character per verse); and the number encoding whether or not to print the last token is modified because the index is `55-i`instead of `i-28` (the latter was found to cause problems with negative powers generating fractional numbers instead of truncating to integer.)

**Commented**

```
'Work It
Make It
Do It
Makes Us
Harder
Better
Faster
Stronger
More Than
Hour
Our
Never
Ever
After
Work Is
Over

'2*                                               #make a string of all the tokens twice and push on the stack
.n/:a;                                            #duplicate the string, split into tokens at newline to form array. Assign to a
56,{:i;                                           #iterate through i= (0..55)
  [i 4%.2&+2*:j                                   #calculate j=(i%4+(i%4&2))*2 to cycle through 0 2 8 10.
  a=' '                                           #leave a[j] on stack followed by space (token A)
  4j+a=                                           #leave a[j+4] on stack (token B))
  'jSRSSS]SSSSSST'81base 3i?/3%[' '', 'n]=j)a=+   #leave ' ' ', ' or newline on stack as appropriate followed by a[j+1] (token C)
  i 51%48/!*                                      #multiply the data described in the previous line by  !(i%51/48)  (1 or 0)
  ' '                                             #leave a space on the stack
  237118176 2 55i-?/1&                            #leave 237118176/2**55-i & 1 on stack (true or false indicates token D required)
  i 44%32/'Af-'*5j+a=                             #leave i%44/32= 0 or 1 copies of 'Af-' on the stack. Leave a[j+5] on the stack.
  if                                              #depending on value of last but one line, select an option from the previous line.
  j 9/n*n]                                        #leave a newline on the stack. if 9/n is 1 or more (last line of verse) leave an additional newline
}/                                                #close the loop
                                                  #printing done by implied stack dump on program exit.

```
> 1 votes

# Answer
## Python - 1056 Charaters

```
a,b,d,s,w,i,t,e,f,h,H,mi,mu,mt,ad,n,o,O="After","Better","Do It ","Stronger","Work ","Is ","It ","Ever ","Faster ","Harder ","Hour ","Make It ","Makes Us ","More Than ","Af-","Never ","Our ","Over"
owinO=o+w+i+n+O
mus=mu+s
df=d+f
dfmu=df[0:-1]+", "+mu
dfmus=df+mus
dfcmus=df[0:-1]+", "+mus
ha=h+a
Ha=H+a
mib=mi+b
mte=mt+e
mteh=mte+H
mtech=mte[0:-1]+", "+H
mtehad=mteh+ad
mteha=mteh+a
wi=w+i
wt=w+t
wth=wt+h
wthmt=wth[0:-1]+", "+mi
wthmib=wth+mi+b
E = ""
l =[wt,mi,d,mu,h,b,f,s,mt,H,o,n,e,a,wi,O,E,wt,mi,d,mu,h,b,f,s,mt,H,o,n,e,a,wi,O,E,wthmib,dfcmus,mteha,owinO,E,wthmib,dfcmus,mteha,owinO,E,wthmib,dfcmus,mteha,owin
O,E,wthmib,dfcmus,mteha,owinO,E,wthmib,dfcmus,mteha,owinO,E,wthmib,dfcmus,mteha,owinO,E,wthmib,dfcmus,mteha,owinO,E,wthmt,dfmu,mtech,owinO,E,wthmib,dfcmus,mteha
d,owinO,E,wthmib,dfcmus,mtehad,owinO,E,wthmib,dfcmus,mtehad,owinO,E,wth,mib,dfmus,mteh,owinO,E,wth,df,mte,owinO,E,wth,mib,df,mus,mte,Ha,owinO]

for ln in l:
    print ln

```

Still room for improvement with variable names, but its a start.
> 0 votes

# Answer
# Ruby, 486 Bytes

```
i=%w(Work\ It Make\ It Do\ It Makes\ Us Harder Better Faster Stronger More\ Than Hour Our Never Ever After Work\ Is Over)
z=i[1]+p+i[5]
y=i[2]+p+i[6]
x=z+n+y
w=i[3]+p+i[7]
v=i[8]+p+i[12]
u=w+n+v
t="Our "+i[14]+" Never Over"
s=i[0]+p+i[4]
r=i[9]+p+i[13]
n="\n"
p=' '
m=', '
a=i.join n
q=n+t
l=s+n
b=s+p+x+m+u+p+r+q
c=s+m+i[1]+n+y+m+i[3]+n+v+m+i[9]+q
d=b.gsub("After","Af-")
e=l+x+p+u+p+i[9]+q
f=l+y+n+v+q
g=l+x+n+u+n+r+q
def o s
s+"

"
end
puts o(a)*2+o(b)*7+o(c)+o(d)*2+o(d)+o(e)+o(f)+g

```
> 0 votes

# Answer
## Ruby, 483 bytes

```
puts "#{'a buc bud bucs eufuguhuiuj kulumuoupuqua rutuu'*2}#{'a b f c b gud b h, cs e iuj k p l qum a r o tuu'*7}a b f, c bud b h, cs euj k p, lum a r o tuu#{'a b f c b gud b h, cs e iuj k p l num a r o tuu'*3}a b fuc b gud b h cs e iuj k p lum a r o tuua b fud b huj k pum a r o tuua b fuc b gud b hucs e iuj k pul qum a r o tu".gsub /./,Hash[[*?a..?u,' ',','].zip %w{Work It Make Do Us Harder Better Faster Stronger More Than Hour Our Af- Never Ever After Is s Over}+[?\n,' ',',']]

```

Works by encoding every word used in the song to a single letter, multiplying some stanzas, then substituting the encoded letters with the actual lyrics. Commas, spaces are left as is. `u` is a newline.
> 0 votes

# Answer
# PHP, 434 Bytes

```
$m="Make It";$b="$m Better";$o="Our Work Is Never Over
";$u="Makes Us";$s="$u Stronger";$d="Do It";$f="$d Faster";$e="More Than Ever";$h="Hour";$w="Work It Harder";echo strtr("001111111$w, $m
$f, $u
$e, $h
$o
222$w
$b
$f $s
$e $h
$o
$w
$f
$e
$o
$w
$b
$f
$s
$e
$h After
$o",["Work It
$m
$d
$u
Harder
Better
Faster
Stronger
More Than
$h
Our
Never
Ever
After
Work Is
Over

","$w $b
$f, $s
$e $h After
$o
","$w $b
$f, $s
$e $h Af-
$o
"]);

```

Try it online!
> 0 votes

# Answer
# PowerShell, ~~489~~ 431 bytes

```
$d='8t11 4our Aft93t93t93t93t93t93t96Harder, Make It
Do It Faster, 0
More Than Ever, Hour
3-
3-
3-
6Hard95er 0 7n Ever Hour
6Hard9Do It Fast9More Than Ev96Hard9590 7n Ev9Hour Aft9Our 8s Never Over';'Makes Us~
Make2r
Our
Nev9Ev9Aft98s
Ov9
8t~ It
Do It
Makes Us
Hard9Bett9Fast97n
Hou~64our Af~Harder 5er, Makes Us 7n Ever H~Make It Bett9Do It Fast~Our 8s Never Ov9
8t ~Strong9More Tha~Work I~er
'-split'~'|%{$d=$d-replace+$i++,$_}
$d

```

Try it online!
> 0 votes

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


# Question
Title: Interpret control characters like a terminal
Given a ASCII string containing control characters, compute what it should look like when printed to a terminal. Imagining the behaviour of a cursor, this is how to treat each character in the input:

* 0x08 backspace (`\b`): go left one (if already at the start of a line, do not go up)
* 0x09 horizontal tab (`\t`): go right one, and then right until the column number (0-indexed) is a multiple of 8
* 0x0A line feed (`\n`): go down one line and back to the start of the line
* 0x0B vertical tab (`\v`): go down one line without changing horizontal position
* 0x0D carriage return (`\r`): go back to the start of the line
* 0x20 space (): overwrite the previous character with a space, and go right one (This is the same behaviour as a normal character but it's here just for clarity)
* Any other printable ASCII character should be appended literally
* Any characters that aren't listed above (other control characters, NULL bytes, Unicode, etc.) will not be given in the input, so you don't have to handle them

Note: The behaviours above are those of modern terminal emulators; in the *olden days*, on a printer or teletype, `\n` would have done what `\v` does here, and `\v` would have moved the print head down so that the line number was a multiple of 8 (or however else the tab stops were configured). More information

Since this is like a terminal or printer, you can assume the output will never be longer than 80 columns.

Gaps that were never printed on (because the cursor moved over it) should be filled in with spaces, but gaps that are further to the right than the cursor ever went should be stripped off.

If you try these in a shell (particularly those with `\b` and `\r`), the shell prompt may overwrite some of the text - try printing a newline afterwards or add a `; sleep 1` to see the effect properly.

Here is a reference implementation: Try it online!

### Test cases

Input and output are given in C-style escaped string syntax. To clarify, your program does not need to interpret backslash escape sequences - the input will contain the literal control codes themselves.

```
Input           Output
-----------------------------------
""              ""
"A"             "A"
" "             " "
"\n"            "\n"
"A\nB\nC"       "A\nB\nC"
"\t"            "        "
"A\t"           "A       "
"A\t\t"         "A               "
"\tA"           "        A"
"A\tB\tC"       "A       B       C"
"ABCDEF\t"      "ABCDEF  "
"ABCDEFG\t"     "ABCDEFG "
"ABCDEFGH\t"    "ABCDEFGH        "
"ABCDEFGHI\t"   "ABCDEFGHI       "
"\b"            ""
"A\b"           "A"
"A\bB"          "B"
"A\n\bB"        "A\nB"
"AB\b\bC"       "CB"
"A\b "          " "
"\r"            ""
"A\r"           "A"
"A\rB"          "B"
"A\rB\rC"       "C"
"ABC\rD"        "DBC"
"A\rB\nC"       "B\nC"
"A\n\rB"        "A\nB"
"A \r"          "A "
"A\t\r"         "A       "
"AB\vC\rD"      "AB\nD C"
"\v"            "\n"
"A\v"           "A\n "
"A\vB"          "A\n B"
"AB\vCD"        "AB\n  CD"
"AB\v\bCD"      "AB\n CD"
"AB\v\rCD"      "AB\nCD"
"AB\tC\rD"      "DB      C"
"AB\t\bC"       "AB     C"
"AB\b\t"        "AB      "
"ABCDEF\b\t"    "ABCDEF  "
"ABCDEFG\b\t"   "ABCDEFG "
"ABCDEFGH\b\t"  "ABCDEFGH"
"ABCDEFGHI\b\t" "ABCDEFGHI       "
"a very long string that is approaching the 80-column limit\t!\n" "a very long string that is approaching the 80-column limit      !\n"

```

## Rules

# Answer
> 4 votes
# Charcoal, 31 bytes

```
ＦＳ≡℅ι⁸Ｍ¬¬ⅈ←⁹Ｍ⁻⁸﹪ⅈ⁸→χ⸿¹¹Ｍ↓¹³Ｍⅈ←ι

```

Try it online! Link is to verbose version of code. Explanation:

```
ＦＳ

```

Loop over the input string.

```
≡℅ι

```

Switch over the ordinal of the character, since Charcoal doesn't have ASCII control characters in its code page.

```
⁸Ｍ¬¬ⅈ←

```

For `\b`, move left if not already in the left column.

```
⁹Ｍ⁻⁸﹪ⅈ⁸→

```

For `\t`, move right until the next multiple of 8.

```
χ⸿

```

For `\n`, move to the start of the next line.

```
¹¹Ｍ↓

```

For `\v`, move down a line.

```
¹³Ｍⅈ←

```

For `\r`, move to the start of the current line.

```
ι

```

Otherwise just overwrite the character and move right.

# Answer
> 2 votes
# C (gcc), ~~250~~ ~~246~~ ~~249~~ 248 bytes

Thanks to ceilingcat for the -4/-1, which exposed a logic error which is fixed.

Takes the original string and returns the processed string.

**Annotated version:**

```
p,q, // position, max length
i,
c,a; // current character, buffer
f(s,u)char*s,*u;{
  for(u=a=calloc(strlen(s),9), // allocate a buffer able to handle all tabs
      p=q=0;c=*s++;)
    c-8? // backspace
      c-9? // tab
        c-10? // newline
          c-11? // vertical tab
            c-13? // carriage return
                *u++=c,q=++p>q?p:q // default
                  // store and advance position, updating the maximum
              :(u-=p,p=0) // carriage return
                 // reset position, not updating the maximum
            :(*u++='\n',memset(u,' ',p),u+=p) // vertical tab
              // store newline and p spaces
          :(*u++='\n',p=q=0) // newline
            // store newline and reset position and maximum
        :(i=8-p%8,i+p>q?u=memset(u+(q-p),' ',p+i-q)+(p+=i)-q,q=p:(u+=i,p+=i)) // tab
          // advance position, adding spaces to the end if needed
      :p&&u--+p--; // backspace
        // retreat position if not at start

  s=a;
}

```

```
p,q,i,c,a;f(s,u)char*s,*u;{for(u=a=calloc(strlen(s),9),p=q=0;c=*s++;)c-8?c-9?c-10?c-11?c-13?*u++=c,q=++p>q?p:q:(u-=p,p=0):(*u++=10,u=memset(u,32,p)+p):(*u++=c,p=q=0):(i=8-p%8,i+p>q?u=memset(u+q-p,32,p+i-q)+(p+=i)-q,q=p:(u+=i,p+=i)):p&&u--+p--;s=a;}

```

Try it online!

# Answer
> 1 votes
# JavaScript (Node.js), 140 bytes

```
s=>[l=[],...s.flatMap(n=>(p=n>31,c={8:c&&c-1,9:c+8&-8,11:c}[n]||p*c,p?l[c++]=n:(F=t=>t?F(--t,l[t]||=32):l)(c),9<n&n<12?[F(c,l=[])]:[]),c=0)]

```

Try it online!

Tio link use `l[t]=l[t]||32` since the node version is a bit old. Changing to `l[t]||=32` should work for newer version.

Input an array of integers. Output an array of array of integers.

```
s=>[
l=[], // l is current line, output first line (may be modified later)
...s.flatMap(n=>( // for each char
p=n>31, // p: is printable?
c={     // c: position (column) of cursor; adjust cursor
8:c&&c-1, // chr(8): move left
9:c+8&-8, // chr(9): tab
11:c      // chr(11): no move
}[n]||    // based on current char
p*c,      // for other printable chars, keep cursor original position
          // for other control chars, move corsor to beginning
p?
l[c++]=n: // printable, print
(F=t=>t?F(--t,l[t]||=32):l)(c), // control char, fill gaps with spaces
9<n&n<12?    // shall we move to next line?
[F(c,l=[])]: // output the next line
[]           // output nothing
),c=0 // cursor start with 0
)]

```

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


title: Compress a sparse matrix

text:
# Question
Title: Compress a sparse matrix
Compress a sparse matrix using Compressed sparse row (CSR, CRS or Yale format).

These are all the same form of compression (ignore new Yale).

Input may be any 2d data structure (list of lists, etc): e.g

```
[[0 0 0 0],
 [5 8 0 0],
 [0 0 3 0],
 [0 6 0 0]]

```

And the output should be three 1d data structures (list etc), that denote the outputs `A`, `IA` and `JA`, for example

```
[5, 8, 3, 6]
[0, 0, 2, 3, 4]
[0, 1, 2, 1,]

```

The process is described by wikipedia:

> * The array `A` is of length `NNZ` and holds all the nonzero entries of `M` in left-to-right top-to-bottom ("row-major") order.
> * The array `IA` is of length `m + 1`. It is defined by this recursive definition:
> * `IA[0] = 0`
>
> `IA[i] = IA[i − 1] + (number of nonzero elements on the (i − 1)-th row in the original matrix)`
> * Thus, the first `m` elements of `IA` store the index into `A` of the first nonzero element in each row of `M`, and the last element `IA[m]` stores `NNZ`, the number of elements in `A`, which can be also thought of as the index in `A` of first element of a phantom row just beyond the end of the matrix `M`. The values of the `i`-th row of the original matrix is read from the elements `A[IA[i]]` to `A[IA[i + 1] − 1]` (inclusive on both ends), i.e. from the start of one row to the last index just before the start of the next.\[5\]
> * The third array, `JA`, contains the column index in `M` of each element of `A` and hence is of length `NNZ` as well.

If your language doesn't support actual data structures, input and output may be text.

# Test cases

Input 1:

```
[[0 0 0 0],
 [5 8 0 0],
 [0 0 3 0],
 [0 6 0 0]]

```

Output 1:

```
[ 5, 8, 3, 6 ]
[ 0, 0, 2, 3, 4 ]
[ 0, 1, 2, 1, ]

```

Input 2

```
[[10 20 0 0 0 0],
 [0 30 0 40 0 0],
 [0 0 50 60 70 0],
 [0 0 0 0 0 80]]

```

Output 2:

```
[ 10 20 30 40 50 60 70 80 ]
[  0  2  4  7  8 ]
[  0  1  1  3  2  3  4  5 ]

```

Input 3:

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

```

Output 3:

```
[ ]
[ 0 0 0 0 ]
[ ]

```

Input 4:

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

```

Output 4:

```
[ 1 1 1 1 1 1 1 1 1 ]
[ 0 3 6 9 ]
[ 0 1 2 0 1 2 0 1 2 ]

```

Input 5:

```
[[0 0 0 0],
 [5 -9 0 0],
 [0 0 0.3 0],
 [0 -400 0 0]]

```

Output 5:

```
[ 5, -9, 0.3, -400 ]
[ 0, 0, 2, 3, 4 ]
[ 0, 1, 2, 1, ]

```

Assume inputs may contain any real number, you need not consider mathematical symbols or exponential representation (e.g. 5,000 will never be entered as 5e3). You will not need to handle `inf`, `-inf`, `NaN` or any other 'pseudo-numbers'. You may output a different representation of the number (5,000 *may* be output as 5e3 if you so choose).

# Scoring

This is a , fewest bytes wins.

# Answer
> 6 votes
# MATL, 19 bytes

```
!3#f!Dx0Gg!XsYshDq!

```

Input uses `;` as row separator.

Try it online! Or verify all test cases: , , , , .

### Explanation

```
!     % Implicit input. Transpose
3#f   % 3-output version of find: it takes all nonzero values and pushes
      % their column indices, row indices, and values, as column vectors
!     % Transpose into a row vector
D     % Display (and pop) vector of values
x     % Delete vector of row values
0     % Push 0
G     % Push input
g     % Convert to logical: nonzeros become 1
!     % Transpose
Xs    % Sum of columns. Gives a row vector
Ys    % Cumulative sum
h     % Prepend the 0 that's below on the stack
D     % Display (and pop) that vector
q     % Subtract 1 from the vector of row indices
!     % Transpose into a row vector. Implicitly display

```

# Answer
> 5 votes
# Mathematica, 78 bytes

```
{a=SparseArray@#;a@"NonzeroValues",a@"RowPointers",Join@@a@"ColumnIndices"-1}&

```

See this answer on mathematica.stackexchange.com.

# Answer
> 3 votes
# APL (Dyalog), ~~31~~ 28 chars or ~~36~~ 33 bytes\*

Requires `⎕IO←0` for zero based indexing. I/O is list of lists.

```
{(∊d)(0,+\≢¨d←⍵~¨0)(∊⍸¨⍵≠0)}

```

Try it online!

`{``}` anonymous function where the argument is represented by

`(``)(``)(``)` return a list of three things:

`⍵≠0` Boolean where the argument differs from 0
`⍸¨`**ɩ**ndices of those for each sub-list
**ϵ**nlist (flatten) to combine into single list

`⍵~¨0` remove zeros from each sub-list of the argument
`d←` store that as *d*
`≢¨` tally each
`+\` cumulative sum
`0,` prepend a zero

`∊d`**ϵ**nlist (flatten) *d* to combine into single list

---

* To run in Dyalog Classic, simply replace  with `⎕U2378`.

# Answer
> 3 votes
# Jelly, 24 bytes

```
n0S€0;;\S€,T€Ẏ$’$
Ẏḟ0W;Ç

```

Try it online!

# Answer
> 3 votes
## Haskell, 87 bytes

```
f s|a<-filter(/=0)<$>s=(id=<<a,scanl(+)0$length<$>a,s>>= \t->[i|(i,e)<-zip[0..]t,e/=0])

```

Try it online!

How it works:

```
a<-filter(/=0)<$>s           -- let a be the list of lists with all 0 removed]
                             -- e.g. [[1,0,0],[0,3,4]] -> [[1],[3,4]]

                             -- return a triple of

id=<<a                       -- a concatenated into a single list -> A

scanl(+)0$length<$>a         -- partial sums of the length of the sublists of a
                             -- strating with an additional 0 -> IA

s>>=                         -- map the lambda over the sublists of s and concatenate
                             -- into a single list
   \t->[i|(i,e)<-zip[0..]t,e/=0]  -- the indices of the non-zero elements -> JA

```

# Answer
> 3 votes
# Python+SciPy, 79 bytes

i guess built-ins were not forbidden

```
from scipy.sparse import*
A=csr_matrix(input())
print A.data,A.indptr,A.indices

```

Accepts input in the format `[[0, 0, 0, 0],[5, 8, 0, 0],[0, 0, 3, 0],[0, 6, 0, 0]]`

# Answer
> 3 votes
# , 70 bytes

```
function(m,M=t(m))list(M[x<-!!M],diffinv(colSums(x)),which(x,T)[,1]-1)

```

Try it online!

This is an old, challenge that didn't get an R answer for 3 years! Having to do this in row-major rather than column-major order costs 8 bytes (`,M=t(m))`).

# Answer
> 3 votes
# Python 3, 96 bytes

```
lambda m:list(map(list,zip(*[[e,i,j] for i,r in enumerate(m) for j,e in enumerate(r) if e!=0])))

```

Try it online!

# Answer
> 2 votes
# Japt, ~~31~~ ~~27~~ 17 bytes

Hopefully this output format is OK.

```
cf pUmè iT å+ Ucð

```

Try it

```
cf pUmè iT å+ Ucð     :Implicit input of 2D array U
c                     :Flat map
 f                    :  Filter
   p                  :Push the following two elements
    Um                :  First element: Map U
      è               :    Count the truthy elements in each
        i             :  Prepend
         T            :    Zero
           å+         :  Cumulatively reduce by addition
              Uc      :  Second element: Flat map U
                ð     :    0-based indices of truthy elements

```

# Answer
> 2 votes
# PHP, 107 bytes

```
<?for($y=[$c=0];$r=$_GET[+$l++];)foreach($r as$k=>$v)!$v?:[$x[]=$v,$z[]=$k,$y[$l]=++$c];var_dump($x,$y,$z);

```

Try it online!

# PHP, 109 bytes

```
<?$y=[$c=0];foreach($_GET as$r){foreach($r as$k=>$v)if($v){$x[]=$v;$z[]=$k;$c++;}$y[]=$c;}var_dump($x,$y,$z);

```

Try it online!

# Answer
> 2 votes
# JavaScript (ES6), 117 bytes

```
a=>[a.map((b,i)=>(b=b.filter((x,c)=>x&&o.push(c)),m[i+1]=m[i]+b.length,b),m=[0],o=[]).reduce((x,y)=>x.concat(y)),m,o]

```

Input is a 2D array of numbers and output is an array of `[A, IA, JA]`.

## Explained

```
a=>[
    a.map((b,i) => (                                // map each matrix row
            b = b.filter((x,c) => x                 // filter to only non-zero elements
                && o.push(c)                        // and add this index to JA
            )
            m[i+1] = m[i] + b.length,               // set next value of IA
            b                                       // and return filtered row
        ),
        m=[0],o=[]                          // initialize IA (m) and JA (o)
    ).reduce((x,y) => x.concat(y)),                 // flatten the non-zero matrix
m,o]                                                // append IA and JA

```

## Tests

```
let f=
a=>[a.map((b,i)=>(b=b.filter((x,c)=>x&&o.push(c)),m[i+1]=m[i]+b.length,b),m=[0],o=[]).reduce((x,y)=>x.concat(y)),m,o]

let run=x=>O.innerHTML+=f(x).map(s=>`[${s.join`, `}]`).join`\n`+"\n\n"
run([[0,0,0,0],[5,8,0,0],[0,0,3,0],[0,6,0,0]])
run([[10,20,0,0,0,0],[0,30,0,40,0,0],[0,0,50,60,70,0],[0,0,0,0,0,80]])
run([[0,0,0],[0,0,0],[0,0,0]])
run([[1,1,1],[1,1,1],[1,1,1]])
run([[0,0,0,0],[5,-9,0,0],[0,0,0.3,0],[0,-400,0,0]])
```

```
<pre id=O></pre>
```

# Answer
> 1 votes
# Python 2, 115 bytes

```
lambda m:zip(*[[v,i]for k in m for i,v in enumerate(k)if v])+[reduce(lambda a,b:a+[len(b)-b.count(0)+a[-1]],m,[0])]

```

Try it online!

Output is `[A, JA, IA]`

# Answer
> 1 votes
# Perl 6, 84 bytes

```
{.flatmap(*.grep(+*)),(0,|[\+] .map(+*.grep(+*))),.flat.kv.flatmap:{$^a%.[0]xx?$^b}}

```

Try it online!

The single matrix argument is in `$_`.

* `.flatmap(*.grep(+*))` selects the nonzero elements of the entire matrix.
* `[\+] .map(+*.grep(+*))` is the triangular reduction of the number of elements in each row (which some languages call `scan`). `(0,|...)` prepends a zero to that list.
* `.flat.kv` produces an indexed list of all elements of the matrix. `.flatmap: { $^a % .[0] xx ?$^b }` flat-maps over the modulus of each index by the number of columns in the array (`.[0]`, the number of elements in the first row), replicated by the element itself, interpreted as a boolean. That is, nonzero elements are replicated once, and zero elements are replicated zero times (ie, removed).

# Answer
> 1 votes
# Julia, ~~66~~ 63 bytes

```
using SparseArrays
n*a=getfield(sparse(a'),n)
!a=5a,3a.-1,4a.-1

```

`SparseArrays` is a standard library that stores with CSC instead of CSR (column instead of row or something), that's why we need to transpose (`a'`).

-6 bytes if 1-indexing was allowed

overloads `*` with `getfield` to save a few bytes

Try it online!

# Answer
> 1 votes
# Scala, 82 bytes

```
x=>x.flatMap(_.zipWithIndex).filter(_._1!=0).unzip->x.scanLeft(0)(_+_.count(_!=0))

```

Try it in Scastie!

Returns `((A, JA), IA)`

Explanation:

```
x =>     //The sparse matrix to be smooshed
x.flatMap(      //Do the following operation to each row, then flatten the result
  _.zipWithIndex //Zip each element with its column (makes tuples)
).filter(      //Keep the tuples where
  _._1!=0      //the first element isn't 0
).unzip        //Unzip into a tuple of two lists, A and JA
->             //Make that the first element of another 2-tuple with IA:
x.scanLeft(0)(  //Starting with 0
  _+_.count(_!=0)  //Add the number of nonzero elements in each row
)               //Keep the intermediate results, giving us IA

```

---
Tags: code-golf, number, array, matrix
---