title: Decompose a permutation into cycles

text:
# Question
Title: Decompose a permutation into cycles
There is a well-known theorem that any permutation can be decomposed into a set of cycles. Your job is to write the shortest possible program to do so.

## Input:

Two lines. The first contains a number `N`, the second contains `N` distinct integers in the range `[0,N-1]` separated by spaces. These integers represent a permutation of `N` elements.

## Output:

One line for each cycle in the permutation. Each line should be a space-separated list of integers in cycle order.

Cycles can be output in any order, and each cycle can be output starting at any position.

## Example 1:

```
8
2 3 4 5 6 7 0 1

```

This input encodes the permutation 0-\>2, 1-\>3, 2-\>4, 3-\>5, 4-\>6, 5-\>7, 6-\>0, 7-\>1. This decomposes into cycles like this:

```
0 2 4 6
1 3 5 7

```

An equally valid output would be

```
5 7 1 3
2 4 6 0

```

## Example 2:

```
8
0 1 3 4 5 6 7 2

```

valid output:

```
0
1
4 5 6 7 2 3

```

# Answer
**C ~~145~~ 134 Characters**

```
N,A[999],i,j,f;main(){gets(&i);for(;~scanf("%d",A+N);)N++;for(;j<N;j++,f=f&&!puts(""))while(i=A[j]+1)f=printf("%d ",j),A[j]=-1,j=--i;}

```

http://www.ideone.com/BrWJT
> 4 votes

# Answer
# Python 131 chars

```
input();d=dict((i,int(x))for i,x in enumerate(raw_input().split()))
while d:
 x=list(d)[0]
 while x in d:print x,;x=d.pop(x)
 print

```

the ending newline is not needed
> 3 votes

# Answer
# J (between 2 and 32)

I'm not quite clear on i/o format, but I think `C.` would do, if the following output would be accepted:

```
   C. 0 1 3 4 5 6 7 2
┌─┬─┬───────────┐
│0│1│7 2 3 4 5 6│
└─┴─┴───────────┘

```

(It looks better in the J terminal.)

If it needs to be a named function that complies to my best understanding of the i/o format, that'd be 32 characters, of which 30 are for output format conversion...

```
g=:>@(":L:0)@(C.@".@}.~>:@i.&LF)

```

In action:

```
   g=:>@(":L:0)@(C.@".@}.~>:@i.&LF)
   g
>@(":L:0)@(C.@".@}.~ >:@i.&(10{a.))
   t
8
0 1 3 4 5 6 7 2
   g t
0
1
7 2 3 4 5 6

```

## Explanation:

J is executed from right to left (practically). `@` is a 'function' (not technically a function, but that's close enough) to combine functions.

* `i.&LF` \- find the first index of `LF`, a predefined variable containing ASCII character number 10, the line feed.
* `>:` \- find the first `LF`, and increment it's index by one. We don't actually want the linefeed, we want the array that follows it.
* `}.~` \- Selects the part of the input that we want.
* `".` \- Since the input format is valid J (*\*\õ/\**) we can just use the `eval` verb (I know it's not actually called `eval`.) to turn it into an array
* `C.` \- Pure magic. I really have no idea what this does, but it seems to work!
* `":L:0` \- Representation. Turns the output of `C.` into a boxed sequence of strings
* `>` \- Unbox. The actual output is actually a string array (there are spaces behind the first to numbers of the example).
> 2 votes

# Answer
## Haskell, 131 characters

```
n%l|all(>n)l=(n:l>>=(++" ").show)++"\n"|1<3=""
c(_:a)=a>>=(\n->n%(takeWhile(/=n)$iterate(a!!)$a!!n))
main=interact$c.map read.words

```
* Edit: (135 -\> 131) `>=` became `>`, eliminated two `tail` calls though pattern matching & pre-application of `a!!`.
> 1 votes

# Answer
# C (sort of), 139 chars

```
n,j,t,a[999];main(){scanf("%*i");for(;scanf("%i",a+n)>0;)n++;while(n--)if(a[j=n]+1){for(;t=a[j]+1;a[j]=-1,j=t)printf("%i ",--t);puts("");}}

```

The final newline is not included.

I said "sort-of" because AFAIK for example

1. it's not legal to omit declaration for variadic functions (ANSI C89: 3.3.2.2)
2. `int` cannot be omitted for variable declaration (I didn't find where it's said it can be omitted and implicit type declaration is only described for functions. The grammar specification in the standard is basically useless as accepts much more than valid C declarations, for example `double double void volatile x;`)
3. a newline at the end of a non-empty source file is mandatory (ANSI C89: A.6.2)

but the above code compiled with `gcc -ocycles cycles.c` apparently works anyway.
> 1 votes

# Answer
# Clojure, 145

```
(let[v(vec(repeatedly(read)read))](loop[a(set v)b 0](cond(a(v b))(do(print" "b)(recur(disj a(v b))(v b)))(seq a)(do(prn)(recur a(first a)))1"")))

```

Somewhat ungolfed, and broken out into a function (input must be a vector, which is what (vec(repeatedly(read)read)) from above produces):

```
(defn p [v]
  (loop [a (set v) b 0]
    (cond
     (a (v b)) (do (print" "b) (recur (disj a (v b)) (v b)))
     (seq a) (do (prn) (recur a (first a)))
     1 "")))

```

(Wow, just noticed this challenge is over 3 year old. Oh well, had fun doing it anyways!)
> 1 votes

# Answer
# Jelly, 17 bytes

```
ḲVJ’,Ɗy¥Ƭ`ZṢ€Q€QG

```

Try it online!

or with modern I/O standards, 14 bytes.

Takes `N` on STDIN and the list of numbers as the first command line argument

The last 5 bytes feel far too long for such a simple task

## How it works

```
ḲVJ’,Ɗy¥Ƭ`ZṢ€Q€QG - Main link. Takes a string S on the left
Ḳ                 - Split S on spaces
 V                - Evaluate each element. Call this list of integer L
       ¥          - Group the previous 2 links into a dyad f(A, L):
     Ɗ            -   Group the previous 3 links into a monad g(A):
  J               -     Length range of A
   ’              -     Decrement to use 0 indexing
    ,             -     Pair with A
      y           -   Transliterate L using the mapping from g(A)
        Ƭ         - While results are unique, repeatedly apply f(A, L),
         `        -  starting with f(L, L)
          Z       - Transpose
           Ṣ€     - Sort each subarray
             Q€   - Deduplicate each subarray
               Q  - Deduplicate the whole array
                G - Join each subarray with spaces and the subarrays by newlines

```
> 1 votes

# Answer
# JavaScript (Node.js), 110 bytes

```
(n,N=[])=>n.flatMap(e=>~N.indexOf(e)?[]:[(U=(T,P=T[T.length-1])=>N.push(P)&&(e==n[P]?T:U([...T,n[P]])))([e])])

```

Try it online!

This is the version which takes in a list of integers and outputs a 2d list, where each sublist is a cycle.

This version takes in the number of numbers (not used). The numbers are taken as a space-separated string, and the function returns a string formatted as described in the question. It is 141 bytes long.
> 1 votes

# Answer
# JavaScript (Node.js), 59 bytes

```
x=>x.flatMap(g=a=>1/x[a]?[[a,...g(x[a],x[a]=g)[0]||[]]]:[])

```

Try it online!

# JavaScript (Node.js), 60 bytes

```
x=>x.flatMap(g=a=>[1/x[a]?[a,...g(x[a],delete x[a])[0]]:[]])

```

Try it online!
> 1 votes

# Answer
# Wolfram Language (Mathematica), 46 bytes

```
Needs["Combinatorica`"];Combinatorica`ToCycles

```

Complete code with test cases is:

```
Needs["Combinatorica`"];
Combinatorica`ToCycles /@
{
 {3, 4, 5, 6, 7, 8, 1, 2},
 {1, 2, 4, 5, 6, 7, 8, 3},
 {1, 2, 3},
 {1 , 2 , 4 , 5 , 6, 7 , 8, 3}
}
// Grid

```

$$ \left( \begin{array}{ccc} \\{3,5,7,1\\} & \\{4,6,8,2\\} & \text{Null} \\ \\{1\\} & \\{2\\} & \\{4,5,6,7,8,3\\} \\ \\{1\\} & \\{2\\} & \\{3\\} \\ \\{1\\} & \\{2\\} & \\{4,5,6,7,8,3\\} \\ \end{array} \right) $$
> 1 votes

# Answer
Python3.8, 129 chars

```
def v(i):_=a[i];a[i]=-1;return~_ and[i]+v(_)or[]
input()
for i in range(len(a:=[*map(int,input().split())])):~a[i]and print(v(i))

```
> 0 votes

# Answer
# MATL, 20 bytes

```
:wQy"yy)]v"@quS!]Xhu

```

Try it out!

Takes the liberty of assuming the second input is inside a pair of square brackets, but otherwise sticks to the requirements (spending 2 bytes on the 0-indexing for example). Works pretty similar to caird coinheringaahing's Jelly answer.
> 0 votes

---
Tags: code-golf, math, combinatorics, permutations
---


title: Counting orthogonal circulant matrices

text:
# Question
Title: Counting orthogonal circulant matrices
Two rows of a matrix are *orthogonal* if their inner product equals zero. Call a matrix with all rows pairwise orthogonal an *orthogonal matrix*. A circulant matrix is one where each row vector is rotated one element to the right relative to the preceding row vector. We will only be interested in matrices where the entries are either `-1` or `1`.

**Task**

Write code to count as many different `n/2` by `n` orthogonal, circulant matrices as possible in 2 minutes (for even `n`).

**Input**

The code has no input. It can try any even values of `n` it likes. For example, the code could try all `n` that are multiplies of `4` starting from the smallest and also try `n = 2`.

**Output**

The number of orthogonal circulant matrices you have found. There should also be a simple switch in your code to enable it to output the matrices themselves.

**Score**

The number of circulant matrices you have found.

**Hints**

Orthogonal `n/2` by `n` circulant matrices only exist when `n` is a multiple of `4` or `n` is less than `4`.

An example orthogonal circulant matrix is:

```
-1  1 -1 -1
-1 -1  1 -1

```

**Tips for a naive approach**

The most naive approach is just to iterate over all possible matrices. This can be sped up using the following two observations.

* To test orthogonality of a circulant matrix we need only compare each row to the first one. This is implemented in the sample code.
* We can iterate over Lyndon words and then if we find an orthogonal matrix multiply by the number of possible rotations. This is idea as yet untested so may be buggy.

**Sample code**

This is a very simple and naive python answer. I ran it using `timeout 120`.

```
import itertools
def check_orthogonal(row):
    for i in xrange(1,int(n/2)):
        if (sum(row[j]*row[(j+i) % n] for j in xrange(n)) != 0):
            return False
    return True

counter = 0
for n in xrange(4,33,4):
    for row in itertools.product([-1,1],repeat = n):
        if check_orthogonal(row):
            counter +=1
            print "Counter is ", counter, ". n = ", n

```

**Correctness tests**

For `n = 4,8,12,16,20,24,28`, the number of distinct matrices you should get is `12,40,144,128,80,192,560`, respectively.

**Levels of awesomeness**

Judging by the sample code, I hereby present two levels of awesomeness that any answer can aspire to achieve.

* Silver level awesomeness is achieved by getting a score or *1156*.
* Gold level of awesomeness is to get higher than that.

**Languages and libraries**

You can use any language or library you like (that wasn't designed for this challenge). However, for the purposes of scoring I will run your code on my machine so please provide clear instructions for how to run it on Ubuntu.

**My Machine** The timings will be run on my machine. This is a standard Ubuntu install on an 8GB AMD FX-8350 Eight-Core Processor. This also means I need to be able to run your code.

**Leading answers**

* **332** by flawr in **Octave**
* **404** by R.T. in **Python**
* **744** by Sample Solution using **pypy**
* **1156** by Thomas Kwa using **Java**. Silver level awesomeness!
* **1588** by Reimer Behrends in **OCaml**. Gold level awesomeness!

# Answer
> 5 votes
# OCaml, 1588 (n = 36)

This solution uses the usual bit pattern approach to represent vectors of -1s and 1s. The scalar product is as usual calculated by taking the xor of two bit vectors and subtracting n/2. Vectors are orthogonal iff their xor has exactly n/2 bits set.

Lyndon words are not per se useful as a normalized representation for this, as they exclude any pattern that is a rotation of itself. They are also relatively expensive to compute. Therefore, this code uses a somewhat simpler normal form, which requires that the longest consecutive sequence of zeroes after rotation (or one of them, if there are multiples) must occupy the most significant bits. It follows that the least significant bit is always 1.

Observe also that any candidate vector must have at least n/4 ones (and at most 3n/4). We therefore only consider vectors with n/4 ... n/2 bits set, since we can derive others via complement and rotation (in practice, all such vectors seem to have between n/2-2 and n/2+2 ones, but that seems to also be difficult to prove).

We build these normal forms from the least significant bit up, observing the constraint that any remaining runs of zeroes (called "gaps" in the code) must follow our normal form requirement. In particular, as long as at least one more 1-bit has to be placed, there must be room for the current gap and another than that is at least as big as the current gap or any other gap observed so far.

We also observe that the list of results is small. Therefore, we do not try to avoid duplicates during the discovery process, but simply record the results in per-worker sets and calculate the union of these sets at the end.

It is worth noting that the runtime cost of the algorithm still grows exponentially and at a rate that is comparable to that of the brute-force version; what this buys us is essentially a reduction by a constant factor, and comes at the cost of an algorithm that is more difficult to parallelize than the brute-force version.

Output for n up to 40:

```
 4: 12
 8: 40
12: 144
16: 128
20: 80
24: 192
28: 560
32: 0
36: 432
40: 640

```

The program is written in OCaml, to be compiled with:

```
ocamlopt -inline 100 -nodynlink -o orthcirc unix.cmxa bigarray.cmxa orthcirc.ml

```

Run `./orthcirc -help` to see what options the program supports.

On architectures that support it, `-fno-PIC` may offer some small additional performance gain.

This is written for OCaml 4.02.3, but may also work with older versions (as long as they aren't too old).

---

UPDATE: This new version offers better parallelization. Note that it uses `p * (n/4 + 1)` worker threads per instance of the problem, and some of them will still run considerably shorter than others. The value of `p` must be a power of 2. The speedup on 4-8 cores is minimal (perhaps around 10%), but it scales better to a large number of cores for large `n`.

```
let max_n = ref 40
let min_n = ref 4
let seq_mode = ref false
let show_res = ref false
let fanout = ref 8

let bitcount16 n =
  let b2 n = match n land 3 with 0 -> 0 | 1 | 2 -> 1 | _ -> 2 in
  let b4 n = (b2 n) + (b2 (n lsr 2)) in
  let b8 n = (b4 n) + (b4 (n lsr 4)) in
  (b8 n) + (b8 (n lsr 8))

let bitcount_data =
  let open Bigarray in
  let tmp = Array1.create int8_signed c_layout 65536 in
    for i = 0 to 65535 do
      Array1.set tmp i (bitcount16 i)
    done;
    tmp

let bitcount n =
  let open Bigarray in
  let bc n = Array1.unsafe_get bitcount_data (n land 65535) in
  (bc n) + (bc (n lsr 16)) + (bc (n lsr 32)) + (bc (n lsr 48))

module IntSet = Set.Make (struct
  type t = int
  let compare = Pervasives.compare
end)

let worker_results = ref IntSet.empty

let test_row vec row mask n =
  bitcount ((vec lxor (vec lsr row) lxor (vec lsl (n-row))) land mask) * 2 = n

let record vec len n =
  let m = (1 lsl n) - 1 in
  let rec test_orth_circ ?(row=2) vec m n =
    if 2 * row >= n then true
    else if not (test_row vec row m n) then false
    else test_orth_circ ~row:(row+1) vec m n
  in if test_row vec 1 m n &&
        test_orth_circ vec m n then
  begin
    for i = 0 to n - 1 do
      let v = ((vec lsr i) lor (vec lsl (n - i))) land m in
      worker_results := IntSet.add v !worker_results;
      worker_results := IntSet.add (v lxor m) !worker_results
    done
  end

let show vec n =
  for i = 0 to n / 2 - 1 do
    let vec' = (vec lsr i) lor (vec lsl (n - i)) in
    for j = 0 to n-1 do
      match (vec' lsr (n-j)) land 1 with
      | 0 -> Printf.printf "  1"
      | _ -> Printf.printf " -1"
    done; Printf.printf "\n"
  done; Printf.printf "\n"; flush stdout

let rec build_normalized ~prefix ~plen ~gap ~maxgap ~maxlen ~bits ~fn =
  if bits = 0 then
    fn prefix plen maxlen
  else begin
    let room = maxlen - gap - plen - bits in
    if room >= gap && room >= maxgap then begin
      build_normalized
        ~prefix:(prefix lor (1 lsl (plen + gap)))
        ~plen:(plen + gap + 1)
        ~gap:0
        ~maxgap:(if gap > maxgap then gap else maxgap)
        ~maxlen
        ~bits:(bits - 1)
        ~fn;
      if room > gap + 1 && room > maxgap then
        build_normalized ~prefix ~plen ~gap:(gap + 1) ~maxgap ~maxlen ~bits ~fn
    end
  end

let rec log2 = function
| 0 -> -1
| n -> 1 + (log2 (n lsr 1))

let rec test_gap n pat =
  if n land pat = 0 then true
  else if pat land 1 = 0 then test_gap n (pat lsr 1)
  else false

let rec test_gaps n maxlen len =
  let fill k = (1 lsl k) -1 in
  if len = 0 then []
  else if test_gap n ((fill maxlen) lxor (fill (maxlen-len))) then
    len :: (test_gaps n maxlen (len-1))
  else test_gaps n maxlen (len-1)

let rec longest_gap n len =
  List.fold_left max 0 (test_gaps n len len)

let start_search low lowbits maxlen bits fn =
  let bits = bits - (bitcount low) in
  let plen = log2 low + 1 in
  let gap = lowbits - plen in
  let maxgap = longest_gap low lowbits in
  worker_results := IntSet.empty;
  if bits >= 0 then
    build_normalized ~prefix:low ~plen ~gap ~maxgap ~maxlen ~bits ~fn;
  !worker_results

let spawn f x =
  let open Unix in
  let safe_fork () = try fork() with _ -> -1 in
  let input, output = pipe () in
  let pid = if !seq_mode then -1 else safe_fork() in
  match pid with
  | -1 -> (* seq_mode selected or fork() failed *)
     close input; close output; (fun () -> f x)
  | 0 -> (* child process *)
    close input;
    let to_parent = out_channel_of_descr output in
    Marshal.to_channel to_parent (f x) [];
    close_out to_parent; exit 0
  | pid -> (* parent process *)
    close output;
    let from_child = in_channel_of_descr input in
    (fun () ->
      ignore (waitpid [] pid);
      let result = Marshal.from_channel from_child in
      close_in from_child; result)

let worker1 (n, k) =
  start_search 1 1 n k record

let worker2 (n, k, p) =
  start_search (p * 2 + 1) (log2 !fanout + 1) n k record

let spawn_workers n =
  let queue = Queue.create () in
  if n = 4 || n = 8 then begin
    for i = n / 4 to n / 2 do
      Queue.add (spawn worker1 (n, i)) queue
    done
  end else begin
    for i = n / 2 downto n / 4 do
      for p = 0 to !fanout - 1 do
        Queue.add (spawn worker2 (n, i, p)) queue
      done
    done
  end;
  Queue.fold (fun acc w -> IntSet.union acc (w())) IntSet.empty queue

let main () =
  if !max_n > 60 then begin
    print_endline "error: cannot handle n > 60";
    exit 1
  end;
  min_n := max !min_n 4;
  if bitcount !fanout <> 1 then begin
    print_endline "error: number of threads must be a power of 2";
    exit 1;
  end;
  for n = !min_n to !max_n do
    if n mod 4 = 0 then
    let result = spawn_workers n in
    Printf.printf "%2d: %d\n" n (IntSet.cardinal result);
    if !show_res then
      IntSet.iter (fun v -> show v n) result;
    flush stdout
  done

let () =
  let args =[("-m", Arg.Set_int min_n, "min size of the n by n/2 matrix");
             ("-n", Arg.Set_int max_n, "max size of the n by n/2 matrix");
             ("-p", Arg.Set_int fanout, "parallel fanout");
             ("-seq", Arg.Set seq_mode, "run in single-threaded mode");
             ("-show", Arg.Set show_res, "display list of results") ] in
  let usage = ("Usage: " ^
               (Filename.basename Sys.argv.(0)) ^
               " [-n size] [-seq] [-show]") in
  let error _ = Arg.usage args usage; exit 1 in
  Arg.parse args error usage;
  main ()

```

# Answer
> 3 votes
## Java, 1156 matrices

This uses fairly naive bitmasking, and takes under 15 seconds for n=28 on my machine.

Circulant matrices are determined by their first rows. Therefore, I represent the first rows of the matrices as bit vectors: 1 and 0 represent -1 and 1. Two rows are orthogonal when the number of set bits when they're xor'd together is n/2.

```
import java.util.Arrays;

class Main {

    static void dispmatrix(long y,int N)
    {
        int[][] arr = new int[N/2][N];
        for(int row=0; row < N/2; row++)
        {
            for(int col=0; col < N; col++)
            {
                arr[row][col] = (int) ((y >>> (N+row-col)) & 1L);
            }
        }
        System.out.println(Arrays.deepToString(arr));
    }

  public static void main(String[] args) {

    int count = 0;
    boolean good;
    boolean display = false;
    long y;
    for(int N=4; N <= 28 ;N += 4)
    {
    long mask = (1L << N) - 1;
    for(long x=0; x < (1L<<N); x++)
    {
        good = true;
        y = x + (x << N);

        for(int row = 1; row < N/2; row++)
        {
            good &= N/2 == Long.bitCount((y ^ (y >>> row)) & mask);
        }

        if(good)
        {
            if(display) dispmatrix(y,N);
            count++;
        }

    }
    System.out.println(count);
    }
  }
}

```

I can't get Eclipse to work right now, so this was tested on repl.it.

Here are the number of first rows that are orthogonal to the first r rows afterwards for n=28:

```
[268435456, 80233200, 23557248, 7060320, 2083424, 640304, 177408, 53088, 14896, 4144, 2128, 1008, 1008, 560]

```

Optimizations:

* Since orthogonality doesn't change with a cyclic rotation of both rows, we just need to check that the first row is orthogonal to the rest.
* Rather than manually do an N-bit cyclic shift N/2 times, I store the bits to be shifted in at the top of the `long`, and then use a single `and` with the lower N bits to extract the needed ones.

Possible further optimizations:

* Generate Lyndon words. According to my calculations this only makes sense if Lyndon words can be generated in less than ~1000 cycles each.
* If Lyndon words take too long, we can still only check the bit vectors that start in `00`, and use their rotations (and rotations of the NOT) when we find an orthogonal matrix. We can do this because `0101...01` and `1010...10` are not possible first rows, and all the others contain either a `00` or a `11`.
* Branch maybe halfway through when the matrix is probably orthogonal. I don't know how much branching will cost, though, so I'll need to test.
* If the above works, start with a row other than row 1?
* Maybe there's some mathematical way to eliminate some possibilities. I don't know what that would be.
* Write in C++, of course.

# Answer
> 2 votes
# Python (404 matrices on i5-5300U)

Mainly posting this as a starting point for others to improve on, this can be cleaned up a lot, parallelized, etc.

```
import numpy
import itertools
import time

def findCirculantOrthogonalRows(n, t1, timeLimit):
  validRows = []
  testMatrix = numpy.zeros((n//2, n))
  identityMatrixScaled = n*numpy.identity(n//2)
  outOfTime = False
  for startingRowTuple in itertools.product([1, -1], repeat=n):
     for offset in range(n//2):
       for index in range(n):
         testMatrix[offset][index] = startingRowTuple[(index-offset) % n]

     if(numpy.array_equal(identityMatrixScaled, testMatrix.dot(testMatrix.transpose()))):
      validRows.append(startingRowTuple)

    if(time.clock() - t1 >= timeLimit):
      outOfTime = True
      break

  return (validRows, outOfTime)

n = 4
validFirstRows = []
t1 = time.clock()
timeLimit = 120
fullOutput = True

while(True):
  print('calling with', n)
  (moreRows, outOfTime) = findCirculantOrthogonalRows(n, t1, timeLimit)

  if(len(moreRows) > 0):
    validFirstRows.extend(moreRows)

  if(outOfTime == True):
    break

  n += 4

print('Found', len(validFirstRows), 'circulant orthogonal matrices in', timeLimit, 'seconds')

if(fullOutput):
  counter = 1
  for r in validFirstRows:
    n = len(r)
    matrix = numpy.zeros((n//2, n))
    for offset in range(n//2):
      for index in range(n):
        matrix[offset][index] = r[(index-offset) % n]
    print('matrix #', counter, ':\n', matrix)
    counter += 1
    input()

```

# Answer
> 2 votes
# Matlab/Octave, 381 / 328 matrices

Also just the naive approach, trying every possible combination.

```
counter = 0;
%ok: 2,4,8
%none:
tic
for n=[2,4,8,12,16,20];
    m=n/2;
    N=2^n-1;
    for k=1:N

        k/N; %remove ; in order to see progress
        v=(dec2bin(k,n)-'0')*2-1;               %first row

        z=toeplitz([v(1) fliplr(v(m+2:n))], v); %create circulante matrix
        w = z * z.';
        if norm(w - diag(diag(w))) < eps
            counter = counter+1;
            %n    %remove % in order to see the matrices
            %z
        end
        if toc>120;
            break;
        end
    end
end
counter

```

# Answer
> 1 votes
# Matlab, 431 matrices

Adjusted from @flawr's answer, using Parallel Pool technique

> Number of Parallel Pool workers: 6
> CPU: Intel(R) Core(TM) i7-10750H CPU @2.60GHz
> Memory: 16.0 GB

```
% Turn off the unnecessary warnings
warning('off', 'MATLAB:nearlySingularMatrix')

counter = 0;
main_timer = tic;

% Define the loop indices
loop_indices = [2,4,8,12,16,20,24,28,32,36,40,44,48,52,56,60];

% Use parfor instead of for to enable parallel computing
% Requires Parallel Computing Toolbox
parfor idx = 1:length(loop_indices)
    n = loop_indices(idx);
    m = n / 2;
    N = 2^n - 1;

    for k = 1:N
        % Use toc with the main_timer to get elapsed time
        if toc(main_timer) > 120
            break;
        end

        % Use built-in de2bi function for better performance
        v = (de2bi(k, n, 'left-msb') * 2) - 1;

        z = toeplitz([v(1) fliplr(v(m+2:n))], v);
        w = z * z.';

        % Use normest for faster estimation of matrix norm
        if normest(w - diag(diag(w))) < eps
            counter = counter + 1;
        end
    end
end

counter

```

---
Tags: math, fastest-code, binary-matrix
---


title: Play Rock-Paper-Scissors 25

text:
# Question
Title: Play Rock-Paper-Scissors 25
RPS 25 is a version of Rock Paper Scissors which has 25 hand symbols instead of just 3. Each symbol defeats 12 symbols, and is defeated by 12 others. Here's a link to a chart showing which symbols defeat which.

The challenge here is simple: your program should take in two strings representing the symbols thrown by each of the players, and output which player wins. You can do this in multiple ways:

* Outputting one of three distinct symbols, one indicating the first input wins and one indicating the second input wins, and one if there's a tie
* Outputting one of 25 distinct symbols indicating which hand symbol wins, outputting either one if there's a tie (since there only is a tie if both players play the same symbol)

The strings can be all lowercase, ALL UPPERCASE, or Title Case.

The following describes all of the possible outcomes; each symbol is followed by a colon, then a list of all of the symbols which it defeats.

```
GUN: ROCK SUN FIRE SCISSORS AXE SNAKE MONKEY WOMAN MAN TREE COCKROACH WOLF
DRAGON: DEVIL LIGHTNING NUKE DYNAMITE GUN ROCK SUN FIRE SCISSORS AXE SNAKE MONKEY
MOON: AIR BOWL WATER ALIEN DRAGON DEVIL LIGHTNING NUKE DYNAMITE GUN ROCK SUN
TREE: COCKROACH WOLF SPONGE PAPER MOON AIR BOWL WATER ALIEN DRAGON DEVIL LIGHTNING
AXE: SNAKE MONKEY WOMAN MAN TREE COCKROACH WOLF SPONGE PAPER MOON AIR BOWL
DYNAMITE: GUN ROCK SUN FIRE SCISSORS AXE SNAKE MONKEY WOMAN MAN TREE COCKROACH
ALIEN: DRAGON DEVIL LIGHTNING NUKE DYNAMITE GUN ROCK SUN FIRE SCISSORS AXE SNAKE
PAPER: MOON AIR BOWL WATER ALIEN DRAGON DEVIL LIGHTNING NUKE DYNAMITE GUN ROCK
MAN: TREE COCKROACH WOLF SPONGE PAPER MOON AIR BOWL WATER ALIEN DRAGON DEVIL
SCISSORS: AXE SNAKE MONKEY WOMAN MAN TREE COCKROACH WOLF SPONGE PAPER MOON AIR
NUKE: DYNAMITE GUN ROCK SUN FIRE SCISSORS SNAKE AXE MONKEY WOMAN MAN TREE
WATER: ALIEN DRAGON DEVIL LIGHTNING NUKE DYNAMITE GUN ROCK SUN FIRE SCISSORS AXE
SPONGE: PAPER MOON AIR BOWL WATER ALIEN DRAGON DEVIL LIGHTNING NUKE DYNAMITE GUN
WOMAN: MAN TREE COCKROACH WOLF SPONGE PAPER MOON AIR BOWL WATER ALIEN DRAGON
LIGHTNING: NUKE DYNAMITE GUN ROCK SUN FIRE SCISSORS AXE SNAKE MONKEY WOMAN MAN
BOWL: WATER ALIEN DRAGON DEVIL LIGHTNING NUKE DYNAMITE GUN ROCK SUN FIRE SCISSORS
WOLF: SPONGE PAPER MOON AIR BOWL WATER ALIEN DRAGON DEVIL LIGHTNING NUKE DYNAMITE
MONKEY: WOMAN MAN TREE COCKROACH WOLF SPONGE PAPER MOON AIR BOWL WATER ALIEN
SUN: FIRE SCISSORS AXE SNAKE MONKEY WOMAN MAN TREE COCKROACH WOLF SPONGE PAPER
DEVIL: LIGHTNING NUKE DYNAMITE GUN ROCK SUN FIRE SCISSORS AXE SNAKE MONKEY WOMAN
AIR: BOWL WATER ALIEN DRAGON DEVIL LIGHTNING NUKE DYNAMITE GUN ROCK SUN FIRE
COCKROACH: WOLF SPONGE PAPER MOON AIR BOWL WATER ALIEN DRAGON DEVIL LIGHTNING NUKE
SNAKE: MONKEY WOMAN MAN TREE COCKROACH WOLF SPONGE PAPER MOON AIR BOWL WATER
ROCK: SUN FIRE SCISSORS AXE SNAKE MONKEY WOMAN MAN TREE COCKROACH WOLF SPONGE
FIRE: SCISSORS AXE SNAKE MONKEY WOMAN MAN TREE COCKROACH WOLF SPONGE PAPER MOON

```

## Test cases

| Player 1 | Player 2 | Winner | Player Winning |
| --- | --- | --- | --- |
| Gun | Rock | Gun | 1 |
| Rock | Gun | Gun | 2 |
| Dynamite | Gun | Dynamite | 1 |
| Gun | Dynamite | Dynamite | 2 |
| Nuke | Scissors | Nuke | 1 |
| Paper | Sponge | Sponge | 2 |
| Moon | Paper | Paper | 2 |
| Man | Tree | Man | 1 |
| Gun | Gun | Gun | Neither |

Standard loopholes are forbidden. Since this is , the shortest code wins.

# Answer
# Charcoal, ~~69~~ 67 bytes

```
⊕÷⊖﹪↨Ｅ²⌕”$⌊↘sM²o⌕J⊘bＡ″⌕‴‹⪫IïΣ↓|‖Ｐ¦？S↷Tσ⊞ωºＢh✂νDδＷcＤ\`9;1”…Ｓ³±¹¦⁷⁵¦³⁶

```

Try it online! Link is to verbose version of code. Takes input in upper case and outputs `-` if the first input wins and `--` if the second input does, nothing for a tie. Explanation:

```
      ²                     Literal integer `2`
     Ｅ                      Map over implicit range
        ”...”               Compressed lookup table
       ⌕                    Find index of
              Ｓ             Next input
             …              Truncated to length
               ³            Literal integer `3`
    ↨           ±¹          Take the difference (literally base `-1`)
   ﹪                        Modulo
                   ⁷⁵       Literal integer `75`
  ⊖                         Decremented
 ÷                          Integer divided by
                      ³⁶    Literal integer `36`
⊕                           Incremented
                            Implicitly output that many `-`s

```

The compressed string contains the first three letters of each word. The two inputs are then located within that string, and the second index is considered as a cyclic offset from the first index. If this is zero, then the result is a tie; if it is `3` to `36`, then the first input wins, otherwise the second input wins. Alternatively, the second input does not lose if it is above `36` and the first input does not lose if it is `36` or below.

Alternatively the two indexes could be considered to be a signed cyclic offset of between `-36` and `36` corresponding to an offset of between `-12` and `12` in the original list of symbols, in which case the sign of the offset would indicate which symbol is the winner.

Another approach I tried was to make the offset even or odd depending on which symbol wins. This is easier to show with Rock-Paper-Scissors-Lizard-Spock. By placing the symbols in the order Spock-Lizard-Rock-Paper-Scissors, each symbol beats those symbols an even number of places after it, e.g. Rock beats Scissors and Lizard. However this is slightly less golfy to implement in Charcoal. (Note that the symbols can also be placed in the order Spock-Rock-Scissors-Lizard-Paper whereby each symbol beats the two to its right and loses to the two to its left.)
> 6 votes

# Answer
# Python,  ~~116~~  94 bytes

```
lambda a,b:[b,a][(h(b)-h(a))%25%2]
h=lambda s:b"SBOMAK1;R?0=T3%".find(int(s*3,35)%86)

```

(contains nine unprintable characters).

**Try it online!**

---

### Previous

```
lambda a,b:[a,b][(h(b)-h(a))%50<26]
h=lambda s:' DMNNLTDLDOANWRBBAIMMPRSGWWCRTTMAWNMESEAXSSFFSURR'.find((s*2)[:5:4])

```

An unnamed function that accepts the two throws as uppercase strings and returns the winning throw as a string.

**Try it online!**

##### How?

The throws each beat the twelve throws before them in the circular list `GUN DYNAMITE NUKE LIGHTNING DEVIL DRAGON ALIEN WATER BOWL AIR MOON PAPER SPONGE WOLF COCKROACH TREE MAN WOMAN MONKEY SNAKE AXE SCISSORS FIRE SUN ROCK`.

If we take the first and fifth characters of each of the throws, repeating characters if necessary (e.g. the fifth character of 'GUN' is 'U') we get distinct results: `GU DM NN LT DL DO AN WR BB AI MM PR SG WW CR TT MA WN ME SE AX SS FF SU RR` and none of these appear more than once in a concatenated version, `GUDMNNLTDLDOANWRBBAIMMPRSGWWCRTTMAWNMESEAXSSFFSURR`.

The first and "fifth" characters are extracted with `(s*2)[:5:4]` \- that is the throw, `s`, repeated twice and then sliced starting with (implicit) index `0`, stepping by `4` up to, but not including index `5`.

The helper function, `h`, `find`s the first index at which those characters appear in the concatenated string to identify the location in the circular list. The `GU` may be replaced with a space as `find` returns `-1` if the input is not found (thus all indices are reduced by two).

The unnamed function calls the helper for each throw, takes the difference, modulos by fifty to deal with the circular nature of the ordering and checks if the second throw won or tied by seeing if that was less than twenty-six.
> 12 votes

# Answer
# JavaScript, 158 bytes

```
(a,b,v='ngeperoonAirowlteriengonvilingukeiteGunockSunireorsAxeakekeymanManreeacholf',m=v.indexOf(a.slice(-3)),n=v.indexOf(b.slice(-3)))=>n-m+(n>m?0:75)>36?b:a

```

Try it:

```
f=(a,b,v='ngeperoonAirowlteriengonvilingukeiteGunockSunireorsAxeakekeymanManreeacholf',m=v.indexOf(a.slice(-3)),n=v.indexOf(b.slice(-3)))=>n-m+(n>m?0:75)>36?b:a

;arr='Sponge Paper Moon Air Bowl Water Alien Dragon Devil Lightning Nuke Dynamite Gun Rock Sun Fire Scissors Axe Snake Monkey Woman Man Tree Cockroach Wolf'.split` `;

for(i=0;i<25;++i)
  for(j=0;j<25;++j)
    document.write(`<p>${arr[i]} vs ${arr[j]} - winner is ${f(arr[i], arr[j])}</p>`)
```

## Explanation

Imagine that we have a round table and all sorts of options are sitting at the table. I have ordered these options so that to the right of each option 12 options are all those options that can be defeated by this option, and to the left 12 options are all those options that can defeat this option:

`Sponge Paper Moon Air Bowl Water Alien Dragon Devil Lightning Nuke Dynamite Gun Rock Sun Fire Scissors Axe Snake Monkey Woman Man Tree Cockroach Wolf`

And all I need is to check if the second option is to the right of the first option. If yes, then the first one wins; if not, then the second one wins

## UPD 252 -\> 227

Thanks to Arnauld for the tip to reduce bytes count

## UPD 227 -\> 195

Based on Neil's tip
> 8 votes

# Answer
# Python, ~~234 230 134~~ 127 bytes

```
lambda a,b,v='SpoRocPapSunMooFirAirSciBowAxeWatSnaAliMonDraWomDevManLigTreNukCocDynWolGun'.find:(a,b)[(v(b[:3])-v(a[:3]))%75%2]

```

Attempt This Online!

*-96 thanks to* @Neil*!*
> 6 votes

# Answer
# JavaScript (ES6), 94 bytes

Expects `[x,y]`, using title case.

```
a=>a[a.map(s=>p="DWgMlktAwSironeRpufyCNTL".indexOf(s[parseInt(s,36)*75%687%4])-p,p=25),p%25%2]

```

Try it online!

### Credits

* This is based on the observation first made by Neil that the outcome is based on a circular list.
* The odd/even interleaving trick which allows the final modulo 2 was borrowed from Jonathan Allan's answer.

### How?

We use a hash function to isolate one of the first 4 letters1 of each word. This is enough to get 25 distinct symbols (including an undefined one for 'Man'). We then look for the symbols into a lookup string to get the correct positions in the circular list.

```
 s         | hash(s) | s[hash(s)] | index in lookup
-----------+---------+------------+-----------------
 Man       |    3    |     n/a    |       -1
 Devil     |    0    |     'D'    |        0
 Woman     |    0    |     'W'    |        1
 Dragon    |    3    |     'g'    |        2
 Monkey    |    0    |     'M'    |        3
 Alien     |    1    |     'l'    |        4
 Snake     |    3    |     'k'    |        5
 Water     |    2    |     't'    |        6
 Axe       |    0    |     'A'    |        7
 Bowl      |    2    |     'w'    |        8
 Scissors  |    0    |     'S'    |        9
 Air       |    1    |     'i'    |       10
 Fire      |    2    |     'r'    |       11
 Moon      |    1    |     'o'    |       12
 Sun       |    2    |     'n'    |       13
 Paper     |    3    |     'e'    |       14
 Rock      |    0    |     'R'    |       15
 Sponge    |    1    |     'p'    |       16
 Gun       |    1    |     'u'    |       17
 Wolf      |    3    |     'f'    |       18
 Dynamite  |    1    |     'y'    |       19
 Cockroach |    0    |     'C'    |       20
 Nuke      |    0    |     'N'    |       21
 Tree      |    0    |     'T'    |       22
 Lightning |    0    |     'L'    |       23

```

*1: Using only 3 letters is also possible, for instance with this expression.*
> 4 votes

# Answer
# Wolfram Language (Mathematica), 698 bytes

```
Module[{t,keys},t=<|"air"->"dvbgfjnhipt`","alien"->"gfjnhipt`qcr","axe"->"rlxkuewsomad","bowl"->"vbgfjnhipt`q","cockroach"->"ws`madvbg`jn","devil"->"jnhipt`qc`lx","dragon"->"fj`hipt`qcrl","dynamite"->"ipt`qcrlxkue","gun"->"pt`qcrlxkuew","lightning"->"nhipt`qcrlxk","man"->"uewsomadvbgf","monkey"->"xkuewsomadvb","moon"->"advbgfjnhipt","nuke"->"hipt`qrclxku","paper"->"madvbgfjnhip","rock"->"t`qcrlxkuews","scissors"->"crlxkuewsoma","snake"->"lxkuewsomadv","sponge"->"omadvbgfjnhi","sun"->"`qcrlxkuewso","tree"->"ewsomadvbgfj","water"->"bgfjnhipt`qc","wolf"->"somadvbgfjnh","woman"->"kuewsomadvbg"|>;keys=Keys@t;If[n==e||StringContainsQ[t[n],FromCharacterCode[97+FirstPosition[keys,e][[1]]-1]],n,e]]

```

Explicit Mathematica code is as follows:

```
r[n_, e_]:=
Module[{t, keys},
  t = <|"air" -> "dvbgfjnhipt`", "alien" -> "gfjnhipt`qcr", "axe" -> "rlxkuewsomad", "bowl" -> "vbgfjnhipt`q", "cockroach" -> "ws`madvbg`jn", "devil" -> "jnhipt`qc`lx", "dragon" -> "fj`hipt`qcrl", "dynamite" -> "ipt`qcrlxkue", "gun" -> "pt`qcrlxkuew", "lightning" -> "nhipt`qcrlxk", "man" -> "uewsomadvbgf", "monkey" -> "xkuewsomadvb", "moon" -> "advbgfjnhipt", "nuke" -> "hipt`qrclxku", "paper" -> "madvbgfjnhip", "rock" -> "t`qcrlxkuews", "scissors" -> "crlxkuewsoma", "snake" -> "lxkuewsomadv", "sponge" -> "omadvbgfjnhi", "sun" -> "`qcrlxkuewso", "tree" -> "ewsomadvbgfj", "water" -> "bgfjnhipt`qc", "wolf" -> "somadvbgfjnh", "woman" -> "kuewsomadvbg"|>;
  keys = Keys[t];
  If[n == e || StringContainsQ[t[n], FromCharacterCode[97 + FirstPosition[keys, e][[1]] - 1]],
    n,
    e
  ]
]

```

Try it online!

*How to store the game rule in the code with minimum number of bytes?*
> 3 votes

# Answer
# 05AB1E, 48 bytes

```
.•2y§Á°rÃ‡ŽGιRjºU¤ÓqtÕ·¢ŸÝ)≠A÷`d•I04SδèJkÆ50%₂@è

```

Port of *@JonathanAllan*'s (previous) Python answer.

Input as a lowercase pair; outputs the winner (or either for ties) from the input-pair.

Try it online or verify all test cases.

**Explanation:**

```
.•2y§Á°rÃ‡ŽGιRjºU¤ÓqtÕ·¢ŸÝ)≠A÷`d•
                   # Push compressed string "a dmnnltdldoanwrbbaimmprsgwwcrttmawnmeseaxssffsurr"
  I                # Push the input-pair
   04S             # Push [0,4]
      δ            # Map over the input-pair:
       è           #  Get their (modular) 0-based 0th/first and 4th/fifth characters
        J          # Join each inner pair of characters together
         k         # Get their 0-based indices in the string
          Æ        # Reduce it by subtracting
           50%     # Modulo-50
              ₂@   # Is larger than or equal to 26
                è  # Use that 0 or 1 to 0-based index into the (implicit) input-pair
                   # (after which the result is output implicitly)

```

See this 05AB1E tip of mine (section *How to compress strings not part of the dictionary?*) to understand why `.•2y§Á°rÃ‡ŽGιRjºU¤ÓqtÕ·¢ŸÝ)≠A÷`d•` is `"a dmnnltdldoanwrbbaimmprsgwwcrttmawnmeseaxssffsurr"` (`a`  could be just `gu` for the same byte-count).
> 3 votes

---
Tags: code-golf
---


# Question
Title: Recognize most smaller primes with a regex
This time, you are working on a regex. Your regex is meant to approximately full-match the base-10 representations of primes \\$0 \le p \< 1000\\$, while ignoring any non-numeric string or composite in the range. You can full-match 2, 53 or 419, but not 0, 82 or example.

The approximately is important -- a minimum of **900** numbers have to produce the right output. You can match more numbers correctly (but as this is a challenge you probably shouldn't). For clarification, how numbers above 1000 are matched **doesn't matter** and they can produce whatever output you like.

Test cases part 1, strings which should be matched (primes under 1000):

```
5
739
211
617
103
503
11
13
17
23
71
89
257

```

Part 2: strings that shouldn't be matched

```
five
5o
2q11
716
102_3
42 + 1
term in A000040
16
204

```

Your score is the number of characters in your regex. Lowest score wins. Have fun!

# Answer
# ~~90~~ ~~79~~ ~~72~~ ~~67~~ ~~65~~ 64 bytes

`^(?!([258][0369]*[147]|[1475][258]|[147]{3}|[0369])+$)\d+[1379]$`

Matches 2–3-digit numbers not divisible by 2, 3, or 5, with an added bit (the `5` in `[1475]`) that removes 8 false positives (527, 529, 551, 553, 559, 581, 583, 589) and adds 4 false negatives (521, 523, 557, 587).

-2 thanks to Nahuel Fouilleul; -9 by removing `[258]{3}`, which was not necessary; -7 by removing one `[0369]*`; -5, -2, -1 with successive improvements on an idea from tsh.
> 27 votes

# Answer
# ~~101~~  96 bytes

This is manually optimized and probably sub-optimal.

```
^((10?|19|82)[1379]|(31|46?|64|88)[137]|(6?5|8|17|23?|26|3[578]|44|5[069])[39]|(22|61|85)[379])$

```

Try it online!

This matches 68 prime numbers and nothing else.
> 7 votes

# Answer
# 69 primes, 831 composites, 83 bytes

```
^((3+|46?|60?|1[0359]?|75|9[479])[17]|(3?[78]|6?[15]|[15][069]|2[236]?|4[34])[39])$

```

Try it online! Link is to test suite that counts the number of correctly matched integers. (The composite number that it incorrectly detects as prime is 169.)

# 68 primes, 832 composites, 85 bytes

```
^((31?|46?|60?|1[0359]?|75|9[479])[17]|(1[079]?|2[236]?|5[069]?|73?|82?|3[578])[39])$

```

Try it online! Link is to test suite that counts the number of matched prime numbers.

Try it online! Link is to test suite that counts the number of correctly matched integers.
> 6 votes

# Answer
# Classic regex, ~~526~~ 452 characters.

```
9(9(7|1)|83|7(|7|1)|67|53|4(7|1)|37|29|1(9|1)|07)|
8(9|8(7|3|1)|77|63|5(9|7|3)|3(|9)|2(9|7|3|1)|11|09)|
7(|9(|7)|87|73|6(9|1)|5(7|1)|43|3(|9|3)|27|1(|9)|0(9|1))|
6(91|83|7(|7|3)|61|5(9|3)|4(7|3|1)|31|1(|9|7|3)|0(7|1))|
5(|9(|9|3)|87|7(7|1)|6(9|3)|57|4(7|1)|3|2(3|1)|0(9|3))|
4(9(9|1)|87|7(|9)|6(7|3|1)|57|4(9|3)|3(|9|3|1)|21|1(|9)|0(9|1))|
3(|97|8(9|3)|7(|9|3)|67|5(9|3)|4(9|7)|3(7|1)|1(|7|3|1)|07)|
2(|9(|3)|8(3|1)|7(7|1)|6(9|3)|5(7|1)|41|3(|9|3)|2(9|7|3)|11)|
1(9(|9|7|3|1)|81|7(|9|3)|6(7|3)|5(7|1)|49|3(|9|7|1)|27|1(|3)|0(9|7|3|1))

```

**This is non-competitive answer for reference, giving the accurate match.**

Two more bytes `^...$` may be needed in a given implementation language/utility to anchor this.

In POSIX world, this is an "extended" regex (ERE); a basic regex (BRE) requires escaped parentheses, otherwise they are literal.

This was calculated by creating a trie structure out of the data set, applying path compression, and then converting to regex.

This can be improved by reducing patterns like `(9|7|3|1)` into `[9731]` character classes, and empty branches `(|3)` into `3?` and such:

```
9(9[71]|83|7[71]?|67|53|4[71]|37|29|1[91]|07)|
8(9|8[731]|77|63|5[973]|39?|2[9731]|11|09)|
7(97?|87|73|6[91]|5[71]|43|3[93]?|27|19?|0[91])?|
6(91|83|7[73]?|61|5[93]|4[731]|31|1[973]?|0[71])|
5(9[93]?|87|7[71]|6[93]|57|4[71]|3|2[31]|0[93])?|
4(9[91]|87|79?|6[731]|57|4[93]|3[931]?|21|19?|0[91])|
3(97|8[93]|7[93]?|67|5[93]|4[97]|3[71]|1[731]?|07)?|
2(93?|8[31]|7[71]|6[93]|5[71]|41|3[93]?|2[973]|11)?|
1(9[9731]?|81|7[93]?|6[73]|5[71]|49|3[971]?|27|13?|0[9731])

```
> 5 votes

# Answer
# JavaScript (Node.js), 405 bytes

```
1(0[1379]|13?|27|3[179]?|49|5[17]|6[37]|7[39]?|81|9[1379]?)|2(11|2[379]|3[39]?|41|5[17]|6[39]|7[17]|8[13]|93?)?|3(07|1[137]?|3[17]|4[79]|5[39]|67|7[39]?|8[39]|97)?|4(0[19]|19?|21|3[139]?|4[39]|57|6[137]|79?|87|9[19])|5(0[39]|2[13]|3|4[17]|57|6[39]|7[17]|87|9[39]?)?|6(0[17]|1[379]?|31|4[137]|5[39]|61|7[37]?|83|91)|7(0[19]|19?|27|3[39]?|43|5[17]|6[19]|73|87|97?)?|8(09|11|2[1379]|39?|5[379]|63|77|81|9)|97

```

Try it online!

Similar to the one below, but optimized by a simple program I wrote similar to https://github.com/noprompt/frak

---

# JavaScript (Node.js), ~~578 bytes~~

```
2|3|5|7|11|13|17|19|23|29|31|37|41|43|47|53|59|61|67|71|73|79|83|89|97|101|103|107|109|113|127|131|137|139|149|151|157|163|167|173|179|181|191|193|197|199|211|223|227|229|233|239|241|251|257|263|269|271|277|281|283|293|307|311|313|317|331|337|347|349|353|359|367|373|379|383|389|397|401|409|419|421|431|433|439|443|449|457|461|463|467|479|487|491|499|503|509|521|523|541|547|557|563|569|571|577|587|593|599|601|607|613|617|619|631|641|643|647|653|659|661|673|677|683|691|701|709|719|727|733|739|743|751|757|761|769|773|787|797|809|811|821|823|827|829|839|853|857|859|863|877|881

```

Try it online!

contains 152 of the 168 prime numbers under 1000 ~90%

cant get simpler can it?
> 3 votes

# Answer
# Any flavor, 148 bytes

```
^([389]?113?|2(39?|2[379]|[147]1|[9862]3)?|(1[023569]?|4[568]?|6[147]?|9[03469]?|3[013469]?|8[8572]|7[259]|5[4578]|)7|1?[357]|[258]9|[37]1|[4785]3)$

```

Try it online!

Matches 68 of the 168 primes between 0 and 1000 as being prime, and all 832 of the composites, totalling 900, or 90% of the total 1000.
> 3 votes

# Answer
# .NET regex, ~~236~~ ~~229~~ ~~222~~ ~~210~~ ~~202~~ ~~198~~ 192 bytes

`^(?!(?(((?<-4>(){10})|){99}((?<4-2>)|){990}(?=[6-9](?<4>){6})?(?=[3-59](?<4>){3})?([258](?<4>)|[147])?).)+$(?(5)|(\6)?()){31}(?(4)(?(6)(?<A-6>(?<-4>))){31}(?>(?<6-A>)(\4)?|){31}){499}\7|[01]$)`

Try it online!
Try it online! \- Kaz's 456 byte POSIX ERE compatible solution, for comparison
Try it online! \- primes matched in unary, for comparison

This correctly identifies all \\$168\\$ primes and \\$832\\$ non-primes in the range \\$\[0,999\]\\$. (Processing that entire range on TIO takes ~~30~~ **4 seconds**.) As such it competes in the 100% category, as one other answer to this challenge has done, and not 90%-or-better as the challenge asks for.

Earlier versions of this were split into two levels of golf, one running in a reasonable amount of time, and the other experiencing exponential slowdown (being probably too slow to finish processing the entire range before the heat death of the universe). But since the 194 byte mark was reached, that version became obsolete, and now the shortest version is approximately equal in speed to the fastest version.

*-8 bytes (210 → 202) by using a variant of jimmy23013's digit capture technique instead of binary*

The primary challenge here is that a regex can only do its work within the space of the input. In unary, this is no problem as far as matching primes go. But in decimal, the digits don't provide enough space to do the necessary computational work – numeric variables cannot be stored in the form of captured portions of the input string, as the number of possible states of each such a capture, including the unset state, would only be \\$n({n+1})/2+2\\$ at best (if every digit is unique), or \\$n+2\\$ at worst (if all digits are identical), when it needs to be \\$10^n\\$ – where \\$n\\$ is the number of decimal digits in the input.

This regex uses .NET's Balanced Groups feature to do its magic. In .NET, each time a capture has been made to a particular group, using `(`...`)` or `(?<n>`...`)`, it is pushed onto that group's capture stack, which retains the full information of every substring contained in that stack, in order. That's overkill in this case, as this regex only pushes empty strings\* onto the capture stacks. Each emulated numeric variable is stored as the number of times a capture has been pushed onto the stack of a particular group. (Popping is done using `(?<-n>`...`)`, which asserts the stack is non-empty and removes the capture at the top of that stack – as well as matching the enclosed pattern, which can be unrelated. As far as this regex is concerned, it simply asserts that the variable is nonzero and then decrements it.)
<sub>\*Not that it makes any difference given how the regex works, but following the 210 → 202 golf, if the last digit of the input is in `[124578]`, the topmost capture on the `\4` stack will contain that digit. The rest are empty.</sub>

But even with this trick, it is impossible to do unbounded arithmetic. A repeated operation (incrementing and/or decrementing a capture stack variable) can only be either done as many times as there are characters in the input, or done a hard-coded maximum number of times. These can be combined and multiplied, but that still only means it could be repeated a number of times that is proportional to a polynomial function of the input string's length, whereas to be able to scale with decimal input (or any base besides unary), it'd need to be an exponential function.

So at the time of this posting, I had thought it impossible to match all primes up to infinity in decimal with a pure regex. But it turns out to be possible after all, by doing base-encoded arithmetic and long division; that regex is much longer.

In the commented explanation below, I use the shorthand `Cn` to signify the capture count of group `\n`:

```
^               # Anchor to start
(?!             # Negative lookahead - assert that none of the following two
                # alternatives can match.
    # Match any composite number in decimal

    # Parse the number, translating decimal into the capture count C4
    (?( # This entire section is wrapped inside a lookahead conditional,
        # which just acts as a golfed lookahead since it always matches.
        ((?<-4>(){10})|){99}    # C2 += C4 * 10; C4 = 0
        ((?<4-2>)     |){990}   # C4 += C2;      C2 = 0

        # Read this digit, adding it to C4
        (?=  [6-9] (?<4>){6})?  # C4 += 6, if digit is in [      6789]
        (?=  [3-59](?<4>){3})?  # C4 += 3, if digit is in [   345   9]
        (    [258] (?<4>)   |   # C4 += 2, if digit is in [  2  5  8 ]
             [147]          )?  # C4 += 1, if digit is in [ 1  4  7  ]
      )
        .           # Consume digit
    )+$             # Loop until all digits have been read.

    # C6 = any number from 2 to 31 (31 is the largest prime ≤ sqrt(999))
    (?(5)|      # Conditional - On each iteration, only do anything if \5 is
                # unset.
        (\6)?   # On any iteration after the first, \5 can be set, which
                # signals that no further iterations after the next will
                # increment C6. Doing it this way ensures that C6 will be
                # incremented at least twice.
        ()      # C6 += 1
    ){31}       # Iterate 31 times, to give C6 a possible range from 2 to 31.
                # We can't accomplish this as "{2,31}" because then .NET,
                # like Perl but unlike PCRE, would only do the minimum number
                # of iterations (i.e. 2) before exiting the loop due to a
                # zero-width match.
    # Divide C4 / C6, enforcing that the remainder is zero. The quotient is the
    # number of iterations that start with C4 != 0, i.e. the number of non-NOP
    # iterations.
    (?(4)       # Make each iteration of this loop conditional upon C4 != 0, so
                # that if the division finishes and C4 is still nonzero, the
                # loop will fail to match and will immediately backtrack to try
                # a different value of C6; this provides a huge speedup,
                # relative to putting "(?!\4)" after the end of the loop (which
                # would can't do anyway now, since it doesn't always capture
                # empty strings). Thus, the loop can only finish and exit if
                # C4 == 0 after the division has completed, which, if C7 ≥ 2,
                # means that C4's original value was composite.
        # Total effect of the following loop: C4 -= C6; CA = C6; C6 = 0
        (?(6)           # Make each iteration conditional upon C6 != 0, so that
                        # this loop can't finish without fully subtracting C6
                        # from C4. If C4 was less than C6, this loop will fail
                        # to match before it can finish, and the regex will
                        # backtrack to try a smaller value of C6.
            (?<A-6>(?<-4>))     # CA += 1; C6 -= 1; C4 -= 1
        ){31}                   # Do the above the maximum of up to 31 times,
                                # the maximum value that C6 could have had.
        (?>(?<6-A>)(\4)?|){31}  # C6 = CA; CA = 0;
                                # \7 = set if C4 != 0, i.e. if quotient ≥ 2
    ){499}                      # Handle a quotient of up to floor(999 / 2)
    \7                          # Assert that the quotient was ≥ 2
|   # or...
    # Match the decimal numbers 0 or 1
    [01]$
)

```

This algorithm can do \\$\[0,3333\]\\$ in 56 seconds on TIO (the regex becomes **195 bytes**): Try it online!

---

Here is an alternative **195 byte** version that does not do any direct matching against the digits after their initial reading. I'm including this not just because it's an interesting variation of the algorithm, more like `^(?>(x(x*))\1+$)\2` whereas the above version is like `^(?!(xx+)\1+$)xx`, but because it just might be possible to golf to a shorter length than the above version.

`^(?=(?(((?<-4>(){10})|){99}((?<4-2>)|){990}(?=[6-9](?<4>){6})?(?=[3-59](?<4>){3})?([258](?<4>)|[147])?).)+$(?(6)|(|())){31}(?(4)(?(5)(?<9-5>(?<-4>))){31}(?>(?<5-9>)(\9)?(\4)?|){31}){499}\8)(?!\7)`

Try it online!

```
^               # Anchor to start
(?=             # Atomic lookahead
    # Parse the number, translating decimal into the capture count C4
    (?( # This entire section is wrapped inside a lookahead conditional,
        # which just acts as a golfed lookahead since it always matches.
        ((?<-4>(){10})|){99}    # C2 += C4 * 10; C4 = 0
        ((?<4-2>)     |){990}   # C4 += C2;      C2 = 0

        # Read this digit, adding it to C4
        (?=  [6-9] (?<4>){6})?  # C4 += 6, if digit is in [      6789]
        (?=  [3-59](?<4>){3})?  # C4 += 3, if digit is in [   345   9]
        (    [258] (?<4>)   |   # C4 += 2, if digit is in [  2  5  8 ]
             [147]          )?  # C4 += 1, if digit is in [ 1  4  7  ]
      )
        .           # Consume digit
    )+$             # Loop until all digits have been read.

    # C5 = any number from 1 to 31 (31 is the largest prime ≤ sqrt(999))
    (?(6)|      # Conditional - On each iteration, only do anything if \6 is
                # unset.
        (|())   # C5 += 1; if this chooses to set \6, then for the rest of the
                # loop, C5 will no longer be incremented. This has the effect of
                # trying values in the order from 31 down to 1.
    ){31}       # Iterate 31 times, to give C5 a possible range from 2 to 31.
                # We can't accomplish this as "{2,31}" because then .NET,
                # like Perl but unlike PCRE, would only do the minimum number
                # of iterations (i.e. 2) before exiting the loop due to a
                # zero-width match.
    # Divide C4 / C5, enforcing that the remainder is zero. The quotient is the
    # number of iterations that start with C4 != 0, i.e. the number of non-NOP
    # iterations.
    (?(4)       # Make each iteration of this loop conditional upon C4 != 0, so
                # that if the division finishes and C4 is still nonzero, the
                # loop will fail to match and will immediately backtrack to try
                # a different value of C5; this provides a huge speedup,
                # relative to putting "(?!\4)" after the end of the loop (which
                # would can't do anyway now, since it doesn't always capture
                # empty strings). Thus, the loop can only finish and exit if
                # C4 == 0 after the division has completed, which, if C7 ≥ 2,
                # means that C4's original value was composite.
        # Total effect of the following loop: C4 -= C5; C9 = C5; C5 = 0
        (?(5)           # Make each iteration conditional upon C5 != 0, so that
                        # this loop can't finish without fully subtracting C5
                        # from C4. If C4 was less than C5, this loop will fail
                        # to match before it can finish, and the regex will
                        # backtrack to try a smaller value of C5.
            (?<9-5>(?<-4>))     # C9 += 1; C5 -= 1; C4 -= 1
        ){31}                   # Do the above the maximum of up to 31 times,
                                # the maximum value that C5 could have had.
        # Total effect of the following loop: C5 = C9; C9 = 0
        # (as well as the possible setting of \7 and/or \8)
        (?>
            (?<5-9>)            # C5 += 1; C9 -= 1
            (\9)?               # \7 = set if C9 == 0, i.e. C5_initial ≥ 2
            (\4)?               # \8 = set if C4 != 0, i.e. if quotient ≥ 2
        |
        ){31}
    ){499}                      # Handle a quotient of up to floor(999 / 2)
    \8                          # Assert that the quotient was ≥ 2
)
(?!\7)                  # Assert C5_initial == 1, i.e. that the largest divisor
                        # resulting in a quotient ≥ 2 was 1

```

---

It should also be possible to implement a finite-bounded primality test in regex flavors that don't have balanced groups, but do have persistent backreferences (Perl / Java / Python<sup>`regex`</sup> / Ruby / PCRE); it would have to be done in emulated binary, so there'd have to be a capture group for each bit, at each location where emulated addition/subtraction is done – which means \\$10\\$ of them for each variable at each arithmetic location to handle \\$\[0,999\]\\$, and each one would have to implement its own copying and carry/borrow in each addition/subtraction operation – so, such a regex would probably be enormous, and would likely only pass the breaking-even point against POSIX ERE at a larger maximum range of handled primes (maybe one more decimal digit would be enough, or maybe not).
> 3 votes

---
Tags: code-golf, decision-problem, primes, regular-expression
---


title: Hunt for discount

text:
# Question
Title: Hunt for discount
#### Story

My local pizza delivery introduced new discount. You get 50% discount from every second item on your order.

But being greedy capitalists, they forgot to mention that they will rearrange items the way they need to give you as little as possible.

#### Example

Imagine you ordered

```
- Pizza $20
- Pizza $20
- Coke $2
- Coke $2

```

You expect to get $10 discount from the second pizza and $1 from the coke, but they rearrange it as

```
- Pizza $20
- Coke $2
- Pizza $20
- Coke $2

```

and give you $2.

#### Trick

Later I noticed that I can place as many orders as I want simultaneously, so I just split my order into two:

```
 1.
 - Pizza $20
 - Pizza $20
 2.
 - Coke $2
 - Coke $2

```

and I got the discount I deserve.

#### Problem

Can you please help me to write a program that calculate the maximum discount I can get by splitting my order.

It should accept a list of prices and return an amount.

For simplicity, all prices are even numbers, so the result is always an integer. Order is never empty. Input have no specific order.

This is code golf, do all usual rules applies.

#### Testcases

```
[10]             -> 0
[10,20]          -> 5
[10,20,30]       -> 10
[2,2,2,2]        -> 2
[4,10,6,8,2,40]  -> 9

```

# Answer
# Python 3, 33 bytes

```
lambda a:sum(sorted(a)[-2::-2])/2

```

Try it online!

This is my first answer :D
> 21 votes

# Answer
# APL (Dyalog Extended), ~~11~~ 10 bytes

−1 thanks to Jonah.

Anonymous tacit prefix function.

```
⌊∨+.÷∞2⍴⍨≢

```

Try it online!

the tally of item prices

`⍴⍨` use that to reshape…

`0∞` the list `[0,infinity]`

`+.÷` sum the division of the following by that:

the item prices sorted into descending order

floor (because the infinity is actually just the largest representable float and thus the values are slightly too large)
> 10 votes

# Answer
# 05AB1E, 6 bytes

```
{RιθO;

```

Try it online!

Sort, `R`everse, split into even and odd indices, get second part, sum and take half.
> 7 votes

# Answer
# Jelly, 7 bytes

```
ṢU0Hƭ€S

```

Try it online!

Based on Adám's method, so go upvote that as well

## How it works

```
ṢU0Hƭ€S - Main link. Takes a list L on the left
ṢU      - Sort L in descending order
    ƭ€  - Tie the previous 2 atoms, and alternate between the two for each element:
  0     -   At odd-indexed elements: Replace the element with 0
   H    -   At even-indexed elements: Halve the element
      S - Sum

```
> 5 votes

# Answer
# Vyxal `s`, 4 bytes

```
sṘy½

```

Try it Online!

5 bytes without the flag. Port of ovs's answer but with two key differences:

* `y`, uninterleave, pushes both halves separately on the stack, so we don't need to get the second half
* We have the `s` flag, so we don't need to sum the list in the code.

```
s    # Sort
 Ṙ   # Reverse
  y  # Interleave
   ½ # Take half (vectorised)

```
> 5 votes

# Answer
## Perl 5, ~~49~~ ~~44~~ 43 bytes

```
sub f{@_=sort$a-$b,@_;pop;pop()/2+(@_&&&f)}

```

Try it online!

-6 thanx to @kjetil-s; previous.
> 5 votes

# Answer
# , 35 bytes

Thanks to att for spotting a bug.

```
function(p).5*p%*%!rank(-p,,"f")%%2

```

Try it online!

Takes the dot-product (`%*%`) of `p/2` and a vector of 0s and 1s, with the 1s at the positions corresponding to even ranks in the sorted version of `-p`. We need to use `.5*p` instead of `p/2` because of operator precedence. The `"f"` is needed to handle ties correctly in the vector of ranks.

Dominic van Essen also has an R answer, with a different strategy, currently at 36 bytes.
> 5 votes

# Answer
# Wolfram Language (Mathematica), 25 bytes

```
-Tr@Sort[-#/2][[2;;;;2]]&

```

Try it online!
> 4 votes

# Answer
## Perl 5, ~~66~~ 64 bytes

```
use List::Util pairmap,sum;sub f{sum+pairmap{$b/2}sort{$b-$a}@_}

```

Try it online!
> 4 votes

# Answer
# , 36 bytes

```
function(p)sum(-sort(-c(p,0))*0:1)/2

```

Try it online!

Assumes the price of each item in the order is non-negative.
> 4 votes

# Answer
# Charcoal, 23 bytes

```
Ｗ⁻θυＦ№ι⌊ι⊞υ⌊ιＩ⊘ΣＥυ×ι﹪κ²

```

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

```
Ｗ⁻θυＦ№ι⌊ι⊞υ⌊ι

```

Sort the input in descending order.

```
Ｉ⊘ΣＥυ×ι﹪κ²

```

Multiply each value by its index modulo 2, then take half the sum.
> 3 votes

# Answer
# JavaScript (ES6), 49 bytes

```
f=a=>1/a.sort((a,b)=>a-b)?0:a.pop(a.pop())/2+f(a)

```

Try it online!

### How?

Because `sort()` operates in lexicographical order by default, we unfortunately need the explicit callback function `(a, b) => a - b`, although all test cases would pass without it.

We can stop as soon as the array is empty or only one element remains. Hence the test `1 / a` which evaluates to:

* `Infinity` (truthy) if the array is empty
* A positive float (truthy) if the array is a singleton
* `NaN` (falsy) when at least 2 elements remain

Because the `.pop()` method ignores its argument(s), the expression `a.pop(a.pop())` simply discards the last element and returns the penultimate one.
> 3 votes

# Answer
# Nibbles, 6 bytes

```
/+`%~>>\`<_~

```

Attempt This Online!

```
/+`%~>>\`<_~
          _  Input as a list of numbers
        `<   Sort
       \     Reverse
     >>      Remove first item
  `%~        Take every odd-indexed item
 +           Sum
/          ~ Halve

```
> 3 votes

# Answer
# Husk, 7 bytes

```
ṁ½Ċ2Θ↔O

```

Try it online!

```
      O  # sort in ascending order
     ↔   # reverse
    Θ    # prepend a zero
  Ċ2     # get every 2nd element, starting at the first
ṁ½       # halve each of these, and then sum the results

```
> 2 votes

# Answer
# C (gcc), <sup>~~100~~ ~~78~~</sup> 73 bytes (maybe 74 bytes because of the L"!")

```
r;f(a,l)int*a;{qsort(a,l,4,L"\x72b068bǃ");for(r=0;l--;++a)r+=*++a/2;r=r;}

```

Try it online!

Saved a whopping 22 bytes thanks to ceilingcat!!!
> 2 votes

# Answer
# PHP, 68 bytes

FWIW, as small I can go down in PHP.

```
function d($a){rsort($a);for($c=0;$b=$a[++$i]/2;$i++)$c+=$b;echo$c;}

```

Try it online!
> 2 votes

# Answer
# MathGolf, 9 bytes

```
êzhrg¥§Σ½

```

Try it online.

**Explanation:**

```
ê         # Read the inputs as integer-list
 z        # Sort this list in decreasing order
  h       # Push the length of the list (without popping the list itself)
   r      # Pop and push a list in the range [0, length)
    g     # Filter this list by:
     ¥    #  Modulo-2 (only keep the odd values)
      §   # Use those to index into the decreasing ordered input-list
       Σ  # Sum this list
        ½ # Halve the sum
          # (after which the entire stack - this value - is output implicitly as result)

```
> 2 votes

# Answer
# TI-Basic, 27 bytes

```
Prompt A
SortD(ʟA
sum(ʟAseq(fPart(I/2),I,0,dim(ʟA)-1

```

Output is stored in `Ans` and is displayed at the end.
> 2 votes

# Answer
# Jelly, 7 bytes

```
~ỤỤ~ḂHḋ

```

Try it online!

Or, more to the point, `ỤỤ^LḂḋH`. Turns out, there's a ton of 7-byters--and when that's the case, it really seems like there ought to be one in 6. I wouldn't normally post this until I've found something that does beat the existing solution in 7, but it's continued to elude me, and this is at least different enough for someone else to maybe springboard off of.

```
 ỤỤ        Get a permutation of [1 .. len(input)] in the same order as
~          the bitwise negation of the input.
   ~Ḃ      Is the bitwise negation of each element odd?
     H     Halve the results,
      ḋ    and take the dot product with the input.

```

Bonus in-between: `ṢUḊm2SH`
> 2 votes

# Answer
# PARI/GP, ~~43~~ 30 bytes

saved 13 bytes thanks to the comment.

adapted from @Basto's answer

---

30 bytes:

```
a->-[0..#a-1]%2/2*vecsort(-a)~

```

Try it online!

34 bytes:

```
a->[0..#a-1]%2/2*vecsort(-a)~*(-1)

```

Try it online!

---

43 bytes:

```
a->sum(i=0,(#a-2)\2,vecsort(a)[#a-1-2*i])/2

```

Try it online!

---

It calculates the sum of alternating elements in the input array `a` after sorting it in decreasing order.
> 2 votes

# Answer
# Ruby, 34 bytes

```
f=->l{*l,a,b=l.sort;b ?a/2+f[l]:0}

```

Try it online!
> 1 votes

# Answer
# Japt `-x`, 8 bytes

+1 byte to handle unsorted inputs.

```
ñÍË*½*Eu

```

Try it
> 1 votes

# Answer
# jq, 37 bytes

```
sort|.[range(length-1;-1;-2)]=0|add/2

```

Try it online!
> 1 votes

# Answer
# Haskell + hgl, 17 bytes

```
mF(//2)<cr<uaL<sr

```

## Explanation

This is a very simple chain of operations:

* `sr` sorts the input.
* `uaL` divides it into two lists, those at even indices and those at odd indices.
* `cr` gets the even indices.
* `mF` sums them together using a custom function ...
* `(//2)` divides by 2.

## Reflections

Ok so there's a lot to reflect on.

The fact that `uaL` exists is basically just dumb luck. I made `uaL` because I needed it to make something else and I just gave it a name because I thought it could come in handy at some point. If it didn't exist this would be a lot longer.

Initially I was going to use `im` which takes a list and a list of indices and produces a list of all the indices. This would have been pretty cumbersome.

We probably need a couple of index / slicing builtins because next time we probably won't be as lucky that something like `uaL` just happens to exist.

Next up is dividing by 2. Arithmetic is something I haven't put a lot of time into so I know it's lacking. However, there should be builtins to divide things by small amounts. `dv2` should exist and would have saved a byte. I also noticed that `fdv` a function that is supposed to be the flip of `dv` is exactly the same as `dv`. This is just a bug.

So there's a lot to work on here.
> 1 votes

# Answer
# Arturo, 35 bytes

```
$=>[/∑map reverse sort&[x,y][y]2]

```

Try it

Same method as most of the other answers. Sort, reverse, take every other element, sum, and halve.
> 1 votes

# Answer
# Thunno, \\$ 9 \log\_{256}(96) \approx \\$ 7.41 bytes

```
z;ZlAKS2/

```

Attempt This Online! or verify all test cases

Port of ovs's 05AB1E answer

#### Explanation

```
z;ZlAKS2/  # Implicit input
z;         # Reverse-sort
  Zl       # Uninterleave
    AK     # Last item
      S    # Sum
       2/  # Halve
           # Implicit output

```
> 1 votes

# Answer
# Java, 86 bytes

```
L->{int s=0,i=L.size();for(L.sort((a,b)->a<b?1:-1);i-->0;)s+=i%2*L.get(i);return s/2;}

```

Try it online.

**Explanation:**

```
L->{                      // Method with Integer-List parameter and Integer return-type
  int s=0,                //  Sum-integer, starting at 0
      i=L.size();         //  Index-integer, starting at the size of the input-List
  for(L.sort(             //  Sort the input-List
        (a,b)->a<b?1:-1); //  in reversed order
      i-->0;)             //  Loop `i` in the range (size,0]:
    s+=                   //   Increase the sum by:
       i%2                //    Check if the current `i` is odd (1 if odd; 0 if even)
       *L.get(i);         //    And multiply that to the current `i`'th value
  return s/2;}            //  After the loop, return halve the sum

```
> 1 votes

---
Tags: code-golf, array, arithmetic, optimization
---


title: Last non-zero digit of n!

text:
# Question
Title: Last non-zero digit of n!
Given an integer **1 ≤ N ≤ 1,000,000** as input, output the last non-zero digit of **N!**, where **!** is the factorial (the product of all numbers from **1** to **N**, inclusive). This is OEIS sequence A008904.

Your program needs finish within 10 seconds on a reasonable machine for any valid input.

# Test Cases

```
1 => 1
2 => 2
3 => 6
4 => 4
5 => 2
6 => 2
7 => 4
8 => 2
9 => 8
10 => 8
100 => 4
1000 => 2
10000 => 8
100000 => 6
1000000 => 4

```

This is a so the shortest code in bytes wins!

# Answer
> 10 votes
# Ruby - 63 chars

```
f=->n{n<2?1:6*[1,1,2,6,4,4,4,8,4,6][n%10]*3**(n/5%4)*f[n/5]%10}

```

Source - http://oeis.org/A008904

Handles f upto a thousand digits under a second.

# Test

```
irb(main):014:0> for n in 2..6
irb(main):015:1> puts f[10**n]
irb(main):016:1> end
4
2
8
6
4

```

# Answer
> 11 votes
## Mathematica, ~~45~~ 36 bytes

```
Last@Select[IntegerDigits[#!],#>0&]&

```

Very readable for a winning answer. :) (Then again, there's no GolfScript & Co. submission yet.)

This handles input 1,000,000 in about 5 seconds on my machine.

# Answer
> 4 votes
## Python - 75

```
n=input()
g=1
while n:
 g*=n
 while g%10<1:g/=10
 g%=10**9
 n-=1
print g%10

```

# Answer
> 3 votes
## PARI/GP - 27 bytes

This trades speed for size -- the testcase takes a long time (~6 seconds).

```
n->n!/10^valuation(n!,5)%10

```

This version is much faster (~15 microseconds) but takes 81 bytes:

```
n->r=1;while(n,r*=Mod(4,10)^(n\10%2)*[1,2,6,4,2,2,4,2,8][max(n%10,1)];n\=5);lift(r)

```

You can use this (non-golfed) code to test either:

```
[%(10^n) | n <- [1..6]]

```

# Answer
> 3 votes
# JavaScript, 59 bytes

Based on this answer

```
f=n=>n>9?'6248'[(a=n/5|0)%4]*f(a)*f(n%5)%10:'1126422428'[n]

```

Try it:

```
f=n=>n>9?'6248'[(a=n/5|0)%4]*f(a)*f(n%5)%10:'1126422428'[n]

;[
  0, // 1
  1, // 1
  2, // 2
  3, // 6
  4, // 4
  5, // 2
  6, // 2
  7, // 4
  8, // 2
  9, // 8
  10, // 8
  20, // 4
  100, // 4
  1000, // 2
  10000, // 8
  100000, // 6
  1000000, // 4
].forEach(n=>console.log(n, f(n)))
```

Modified formula is:

$$ D(0) = 1 \\ D(1) = 1 \\ D(2) = 2 \\ D(3) = 6 \\ D(4) = 4 \\ D(5) = 2 \\ D(6) = 2 \\ D(7) = 4 \\ D(8) = 2 \\ D(9) = 8 \\ D(n) = (LastDigitOf(2^{\lfloor n/5 \rfloor}) * D(\lfloor n/5 \rfloor) * D(n \mod 5)) \mod 10, \\;where \\;n \> 9 $$

## How?

The original formula is \\$D(n) = (2^{\[n/5\]} * D(\[n/5\]) * D(n \mod 5)) \mod 10\\$

But there is a problem: we need to calculate \\$2^{\[n/5\]}\\$. For example if \\$n = 10 000 \\$ then we need to calculate \\$2^{2000}\\$ which is already too hard (in JS it will output `Infinity`). But I discovered that we don't need to calculate it instead of this we just need to calculate the last digit of \\$2^{\[n/5\]}\\$. Why? Because each time we just need to calculate the last digit of \\$2^{\[n/5\]} * D(\[n/5\]) * D(n \mod 5)\\$

### Theorem

The last digit of multiplication is the last digit of multiplication of last digits of each multiplier

### Proof

Let's say we have two numbers \\$a\\$ and \\$b\\$. We can represent each of them to the power of `10`:

$$ a = x\_n * 10^n + x\_{n - 1} * 10^{n - 1} + \ldots + x\_1 * 10^1 + x\_0 \\ b = y\_n * 10^m + y\_{m - 1} * 10^{m - 1} + \ldots + y\_1 * 10^1 + y\_0 $$

or

$$ a = (x\_n * 10^{n - 1} + x\_{n - 1} * 10^{n - 2} + \ldots + x\_1) * 10 + x\_0 \\ b = (y\_n * 10^{m - 1} + y\_{m - 1} * 10^{m - 2} + \ldots + y\_1) * 10 + y\_0 $$

When we multiply them we will get:

$$ a * b = (...) * 10 + x\_0 * y\_0 $$

Now it is clear that the last digit of multiplication is the last digit of \\$x\_0 * y\_0\\$, where the \\$x\_0\\$ and \\$y\_0\\$ are the last digits of \\$a\\$ and \\$b\\$ respectively. So we proved the theorem

Now we need to find the last digits of powers of `2`. Let's write some of them:

$$ 2^0 = 1 \\ 2^1 = 2 \\ 2^2 = 4 \\ 2^3 = 8 \\ 2^4 = 16 \\ 2^5 = 32 \\ 2^6 = 64 \\ 2^7 = 128 \\ 2^8 = 256 $$

Now we can see the pattern `1 (2 4 8 6) (2 4 8 6)` and can write it \\$(k = \[n / 5\])\\$:

```
if (k == 0) return 1;
else return [6, 2, 4, 8][k % 4];

```

We can ignore the first case when `k == 0` and here is why:

`k % 4 == 0` when `k is one of [0, 4, 8, 12, 16, ...]` but we need to consider cases when `k is one of [0, 4, 8]` because for bigger values we will run recursion. The second multiplier in our formula is \\$D(k)\\$ and for `k is on of [0, 4, 8]` we get `[1, 4, 2]` respectively. We had to multiply these values by `1` but instead of this we will multiply them by `6` so we will get `[1, 24, 12]`, the last digits of these values are `[1, 4, 2]`. Now we can see that it doesn't matter to multiply them by `1` or `6` the last digits will be the same

The last thing we need it is to prove that \\$\[n / 5\] = \lfloor n / 5 \rfloor\\$ for \\$n \ge 0\\$. I think it is obvious

# Answer
> 2 votes
# Perl, 53 ~~58~~ ~~61~~ characters

All whitespace can be removed, but I left it in for "readability". Note: not using some silly explicit formula from Sloane.

```
sub f {
    $_ = $1 * ++$n || 1, /(.{1,7}?)0*$/ while $n < $_[0];
    $1 % 10
}

```

Calculates f(10^6) in 8.7 seconds on my machine.

**Update**: OP wanted it to be a whole program:

```
$_ = $1 * ++$n || 1, /(.{1,7}?)0*$/ while $n < $ARGV[0];
print $1 % 10

```

That makes it 55 characters.

# Answer
> 2 votes
# CJam - 28

```
1ri{I)*_AbW%{}#A\#/1e7%}fIA%

```

You can try it at http://cjam.aditsu.net/ for values up to 10000 or so; for larger numbers you should use the java interpreter. 1000000 runs in about 3 seconds on my laptop.

**Explanation:**

Unfortunately the straightforward solution is too slow, so I'm keeping only the last 7 digits (before the trailing zeros) after each multiplication.

```
1           push 1 on the stack
ri          read a token and convert to integer
{           loop (for I from 0 to N - 1)
    I)      push I and increment
    *       multiply with the previous value (initially 1)
    _Ab     duplicate and convert to array of digits
    W%      reverse array
    {}#     find the position of the first non-zero digit
    A\#     raise 10 to that power
    /       divide, thus removing all trailing zeros
    1e7%    keep the remainder modulo 10000000
}fI         end for loop
A%          get the last digit

```

**Note:** this language is a lot newer than the question.

# Answer
> 2 votes
# Mathematica, 34 bytes

```
Mod[#!/10^IntegerExponent[#!],10]&

```

# Answer
> 2 votes
# C, ~~150~~ ~~140~~ 135 bytes

```
r,d;f(k,x){r=x<5?3:f(k+1,x/5);return(d=x%5)?r*"33436"[d]*(1<<d*k%4)%5:r;}main(int c,char**v){c=atoi(*++v);printf("%d",c<2?1:2*f(0,c));}

```

This is the version for ASCII systems; replace the string `33436` with `11214` for an EBCDIC system, or with `\1\1\2\1\4` for a portable program.

C solutions are a bit hampered by the requirement to provide a full program; however, this does answer the question fully.

Try it online (requires Javascript):

## Explanation

It's based on the algorithm outlined in Least Significant Non-Zero Digit of n!, turned around so that we recurse in to find the highest power of five, and do the calculation on the way out. The tables of constants were too big, so I reduced them by finding a relationship between the previous residue `r`, the current digit `d` and the recursion depth `k`:

| r | d=0 | d=1 | d=2 | d=3 | d=4 |
| --- | --- | --- | --- | --- | --- |
| 0 | 0 | 3×2^k | 1×2^2k | 3×2^3k | 2 |
| 1 | 1 | 1×2^k | 2×2^2k | 1×2^3k | 4 |
| 2 | 2 | 2×2^k | 4×2^2k | 2×2^3k | 3 |
| 3 | 3 | 3×2^k | 3×2^2k | 3×2^3k | 2 |
| 4 | 4 | 4×2^k | 4×2^2k | 4×2^3k | 1 |

For `r>0`, this resolves to a constant times `r` times `2^dk` (mod 5); the constants are in `a[]` below (inlined in the golfed code). We also observe that `(2^4)%5` is 1, so we can reduce the exponent to avoid overflowing the range of `int`.

```
const int a[] = { 1, 1, 2, 1, 4 };
int f(int k, int x)
{
    int r = x<5 ? 3 : f(k+1,x/5); /* residue - from recursing to higher-order quinary digits */
    int d = x%5;
    if (!d)
        return r;
    return r * a[d] * (1 << d*k%4) % 5;
}

int main(int c, char **v)
{
    c = atoi(*++v);
    printf("%d",
           c<2
           ? 1                  /* special-case 0 & 1 */
           : 2*f(0,c));         /* otherwise, it's 2 times r */
}

```

## Tests:

```
$ for i in 100 1000 10000 100000; do echo $i: `./694 $i`; done
100: 4
1000: 2
10000: 8
100000: 6
1000000: 4

```

Performance is respectable, too. Here's a maximum input for a system with 32-bit `int`:

```
$ time ./694 2147483647
8
real    0m0.001s
user    0m0.000s
sys     0m0.000s

```

I got the same timings with a maximal 64-bit `int`, too.

# Answer
> 2 votes
# Java (OpenJDK 8), 62 bytes

```
n->{long f=n;for(;n>1||f%10==0;)f=n>1?f*--n:f/10;return f%10;}

```

Try it online!

Similar to @Kevin Cruijssen but saves 5 bytes by combining the loops.

# Answer
> 1 votes
## Python3

**239 Chars**

Can do 10000 in ~3.2 seconds (Ideone cuts me off at 8 seconds, i'm sure it'll take longer than 10secs though :( )

```
from functools import *
N=100
r=range
s=(p for p in r(2,N)if all(p%n>0for n in r(2,p)))
f=lambda n,x:n//x+(n//x>0and f(n//x,x)or 0)
e=list([p,f(N,p)]for p in s)
e[0][1]-=e[2][1]
e[2][1]=0
print(reduce(lambda x,y:x*y,map(lambda x:x[0]**x[1],e))%10)

```

## Python2.6

**299 Chars** (a bit faster)
```
from itertools import *
N=100000
r=xrange
def s(c=count(2)):
        while 1:p=c.next();c=ifilter(p.__rmod__,c);yield p
f=lambda n,x:n//x+(n//x>0and f(n//x,x)or 0)
e=[[p,f(N,p)]for p in takewhile(lambda x:x<N,s())]
e[0][1]-=e[2][1]
e[2][1]=0
print(reduce(lambda x,y:x*y,map(lambda x:pow(x[0],x[1],10),e))%10)

```

# Answer
> 1 votes
# PHP - 105

```
 <?foreach(explode("\n",`cat`)as$n)if($n){$f=rtrim(gmp_strval(gmp_fact($n)),'0');echo substr($f,-1)."\n";}

```

Runs under 10 seconds with the given testcase.

# Answer
> 1 votes
## Haskell, 78 characters

```
f n=head$dropWhile(=='0')$reverse$show$product[1..n]
main=interact(show.f.read)

```

(Would probably need to be compiled to compute 1,000,000! in 10 secs).

# Answer
> 1 votes
## J – ~~42~~ 40 characters

A whole program. Save this program in a file and run with `jconsole script.ijs 1234`. Notice that this program does not exit the interpreter after printing a result. Type `^D` or `exit]0` to exit the interpreter.

```
echo([:{:@(#~*)10&#.inv@*)/1+i.".>{:ARGV

```

Here is an explanation:

* `x #. y` interprets the integer vector `y` as a base `x` number; for example, `10 #. 1 2 3 4` yields `1234`.
* `u inv` yields the *inverse* of a verb `u`. In particular, `x #. inv y` represents `y` as a base `x` number; for example, `10 #. 1234` yields `1 2 3 4`. Notice that `inv` is defined as `^:_1`, that is, `u` applied -1 time.
* `x * y` is the *product* of `x` and `y`, thus `x 10&#.inv@* y` yields a base-10 representation of the product of `x` and `y`.
* `x # y` copies the *n*-th item of `y` as often as the *n*-th item of `x`; when `x` is a vector of booleans, `x` selects which items of `y` to take. For instance, `1 0 1 0 # 1 2 3 4` yields `1 3`.
* `* y` yields the *signum* of `y`.
* `x u~ y` is the *reflexive* of `u`, that is, the same as `y u x`.
* Thus, `y #~ * y` yields a vector of all items of `y` that are positive. In tacit notation, this can written with a *hook* as `(#~ *)`.
* `{: y` yields the last item in `y`.
* assembled together, we get the tacit phrase `([:{:@(#~*)10&#.inv@*)`.
* `u/ y` is the *reduction* of `y`, that is, the dyadic verb `u` inserted between elements of `y`. For instance, `+/1 2 3 4` is like `1 + 2 + 3 + 4` and yields `10`.
* Thus, the phrase `([:{:@(#~*)10&#.inv@*)/ y` yields the last digit of the product of the items of `y`.
* `ARGV` is a boxed vector of the command line arguments.
* `".>{:ARGV` is the last argument unboxed and interpreted as a number.
* `i. y` computes natural numbers from `0` to `y - 1`.
* Thus, `1+i. y` yields natural numbers from `1` to `y`. I could have also used `>:` *increment* here, but `1+` is clearer at the same cost of characters.
* The entire program just applies `1+i.".>{:ARGV` (the vector of `1` to the number in the last command line argument) to the verb `([:{:@(#~*)10&#.inv@*)/` and prints the result with `echo`.

# Answer
> 1 votes
# Attache, 64 bytes

```
{k.=Floor[_/5]If[_<2,1,6*Digits@$`U1sTny@(_%10)*3^(k%4)*$@k%10]}

```

Try it online!

Simple implementation of the OEIS formula. `Digits@$`U1sTny` compresses the hardcoded dictionary using Attache's compressed number feature. `$` refers to the function itself within this answer.

# Answer
> 1 votes
# Perl 6,  ~~26~~  35 bytes

```
{[*](1..$_)~~/.*<(<-[0]>/}

```

Try it

---

As a full program:

```
put [*](1..@*ARGS[0])~~/.*<(<-[0]>/

```

Try it

## Expanded:

```
{
  [*]( 1..$_ ) # reduce using &infix:« * »
  ~~           # match with
  /
    .*         # any number of values (so it matches from the end)
    <(         # only capture the following
    <-[0]>     # any value but 0 (negated character class)
  /
}

```

# Answer
> 1 votes
# C (gcc), 72 bytes (function)

```
f(n,d)long long n,d;{for(d=1;n;d%=10000)for(d*=n--;d%10<1;d/=10);d%=10;}

```

Try it online!

# C (gcc), ~~101~~ 99 bytes (whole program)

```
main(){long long n,d=1;for(scanf("%lld",&n);n;d%=10000)for(d*=n--;d%10<1;d/=10);printf("%d",d%10);}

```

Try it online!

This question is just shy of 8 years old so "reasonable machine" is not the same as back then, but I'm getting times of ~.01 seconds on my computer when doing all test cases together, so unless computers have increased in speed by a factor of 1000 this last decade, it should be fine.

# Answer
> 0 votes
# AWK, ~~47~~ 57 bytes

```
{for(p=$1;--$1;p=(p*$1)%1e4)while(!(p%10))p/=10;$0=p%10}1

```

Try it online!

Original solution did not handle "large" input values very well. Could add `-M` to force it to work, but that also requires a lot more processing time.

# Answer
> 0 votes
# PowerShell Core, 56 bytes

```
($s=1).."$args"|%{$s=+("$(($s%1e5)*$_)".Trim(48))}
$s%10

```

Try it online!

Naive implementation, takes under 5 seconds on my local, 25 seconds on TIO
I'll rework it when I get a chance

---
Tags: code-golf, math, number-theory, factorial, restricted-time
---


title: Durable Durations

text:
# Question
Title: Durable Durations
# Introduction

Time is a really simple concept. Seconds pass, one after the other, all the same. But humans love making it hard. This Stackoverflow question has gathered many answers and even though they are surprisingly long and complex, most of them will still fail for certain inputs. Can you format a number of seconds into a timestamp for human consumption not only precisely, but correctly?

# Challenge

Build a human-readable timestamp from a floating point number of seconds. The timestamp must be formatted as `hh:mm:ss.zzz`. Single digit hours, minutes and seconds must be formatted with a leading zero. If the number of complete hours is zero, the hours and leading colon must be omitted, making the output format `mm:ss.zzz`. Please note that the number of hours may have more than two digits. For inputs that cannot be expressed as a finite number, the result must be `--:--.---` (see below for examples of this that probably apply to your language). This is `code-golf`, so the shortest code in bytes wins.

# Example Input and Output

```
0          -> 00:00.000
-0         -> 00:00.000
1          -> 00:01.000
-1         -> -00:01.000
0.001      -> 00:00.001
3.141528   -> 00:03.142
3600       -> 01:00:00.000
3599.9995  -> 01:00:00.000
363600     -> 101:00:00.000
17999.9999 -> 05:00:00.000
Infinity   -> --:--.---
-Infinity  -> --:--.---
NaN        -> --:--.---

```

# Answer
# JavaScript (ES6), 112 bytes

```
f=n=>1/n?n<0?'-'+f(-n):(n=n*1e3+.5,(k=n/36e5|0)?k>9?k:'0'+k:'')+new Date(n).toJSON().slice(13+!k,-1):'--:--.---'

```

Try it online!

### How?

We use the `toJSON()` method to extract the minutes, seconds and milliseconds directly in the expected format. Such a date representation is always expressed as UTC, so we don't have to bother about the system time zone.

```
1970-01-01T00:00:00.000Z
              \_______/

```

Hours are formatted manually. Unless there's no complete hour and the field is not inserted at all, the leading colon in the above string is also included.
> 4 votes

# Answer
# JavaScript™, 161 bytes

```
t=n=>(f=parseInt,O='0',p=n<0?(n=-n,'-'):'',h=f(n/3600),m=f(n/60%60),s=(n%60).toFixed(3),n-n==0?p+(h?(h>9?h:O+h)+':':'')+(m>9?m:O+m)+':'+(s<10?O+s:s):'--:--.---')

```

I could save 13 bytes if I used `|0` to truncate `h` & `m`, but I think that would cause it to fail on very large numbers (e.g. `Number.MAX_SAFE_INTEGER/3600|0 === -1966140585`.

Also, this is somewhat silly, but I *think* this could even work in an old ES3-only engine if the arrow function were swapped out for a normal one? (the other JS answer uses `.toJSON` which was added in ES5 I believe).

```
(n => (
    // constants
    f = parseInt,
    O = '0',
    // variables
    p = n<0?(n=-n,'-'):'',
    h = f(n/3600),
    m = f(n/60%60),
    s = (n%60).toFixed(3),
    // return value
    n-n==0
        ? p+(h?(h>9?h:O+h)+':':'')+(m>9?m:O+m)+':'+(s<10?O+s:s)
        : '--:--.---'
) )

```
> 3 votes

# Answer
# 05AB1E, 44 bytes

```
3.òÄƵ/v60ym‰`}₄*ò)T‰J`₄+¦)…::..ι¬_·.$JIï'-Ãì

```

05AB1E doesn't have `NaN` nor `Inf`. It can handle number-strings with leading 0s though, so I've added a test case to my test suite for it.

Formatting takes about 2/3rd of the code, although can most likely be golfed a bit more..

Try it online or verify all test cases.

**Explanation:**

Step 1: Get the individual hours, minutes, seconds, and milliseconds:

```
3.ò       # Round the (implicit) input by 3 decimals
   Ä      # Take the absolute value of it
Ƶ/        # Push compressed integer 210
  v       # Loop over its digits `y`:
   60ym   #  Push 60 to the power `y`
          #  (3600,60,1 in the three iterations respectively)
       ‰  #  Divmod the top integer by this
        ` #  Pop and push the quotient and remainder separately to the stack
   }      # After the loop
    ₄*    # Multiply the top (decimal) value by 1000
      ò   # (Banker's) round it to the nearest integer
       )  # Wrap all values on the stack into a list

```

See this 05AB1E tip of mine (section *How to compress large integers?*) to understand why `Ƶ/` is `210`.

Step 2: Format and output them:

```
T‰        # Divmod all values in the list by 10
  J       # Then join the pairs together
          # (≥10 will remain unchanged; <10 will have a single leading 0)
   `      # Pop and push all values to the stack again
    ₄+    # Add 1000 to the top value
      ¦   # Remove the leading 1
          # (to format numbers #/##/### to "00#"/"0##"/"###" respectively)
       )  # Wrap the stack back into a list
…::.      # Push string "::."
    .ι    # Interleave the list with this as list [":",":","."]
¬         # Push the first item (without popping the list itself)
 _        # Check if it's 0; or technically "00" (1 if "00"; 0 otherwise)
  ·       # Double it
   .$     # Remove that many leading items from the list
     J    # Join everything in the stack together
I         # Push the input again
 ï        # Cast it to an integer (edge case "-0" becomes 0)
  '-Ã    '# Only keep the potential "-" (or an empty string otherwise)
     ì    # Prepend that to the string
          # (after which the result is output implicitly)

```
> 2 votes

# Answer
# MATLAB, 114 bytes

```
function d(i),if~isfinite(i),'--:--.---',end,f='hh:mm:ss.SSS';if abs(i)<3600,f=f(4:12);end,i=seconds(i);i.Format=f

```

Using MATLAB's built in 'duration' class (and its derivative, seconds) I can convert the float input i to a duration and change the output format to the proper format for the challenge. If the input is nan or inf though, the duration will be displayed as nan or inf, so I hard-coded the exception string.

TIO doesn't have MATLAB, but octave, and octave doesn't have the builtin 'seconds' class, so I can't show a TIO link.
> 2 votes

# Answer
# Charcoal, 64 bytes

```
≔∕⌊⁺·⁵×φＮφθＦ‹θ⁰-≦↔θ⊞υ﹪%06.3f﹪θ⁶⁰Ｆ²«≧÷⁶⁰θ¿¬‹θι⊞υ﹪%02d⎇ιθ﹪θ⁶⁰»⪫⮌υ:

```

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

```
≔∕⌊⁺·⁵×φＮφθ

```

Input the number of seconds and round it to the nearest millisecond (rounding `0.5` to infinity). (Note that Charcoal only supports inputs of the form `-?\d+(.\d+)?`.)

```
Ｆ‹θ⁰-

```

If the number is negative then output a `-`.

```
≦↔θ

```

Take the absolute value of the input.

```
⊞υ﹪%06.3f﹪θ⁶⁰

```

Take the seconds part of the value and format it to `6` zero-filled characters of which `3` are decimals.

```
Ｆ²«

```

Repeat for the minutes and the hours.

```
≧÷⁶⁰θ

```

Floor divide the value by `60`.

```
¿¬‹θι

```

If the value is not a zero number of hours, then...

```
⊞υ﹪%02d⎇ιθ﹪θ⁶⁰

```

... format the minutes or hours as appropriate to `2` zero-filled characters.

```
»⪫⮌υ:

```

Correct the order of the parts of the time and join them with `:`s.

I did try writing a Retina answer but implementing rounding was too arduous. Without rounding it took 135 bytes: Try it online! Link includes test cases.
> 2 votes

# Answer
# C (gcc), ~~200~~ ~~183~~ 175 bytes

* -8 thanks to Juan Ignacio Díaz

I round to the nearest millisecond before performing calculations to avoid incorrect displays around 3599.9995 seconds. To remove the hours part if not required and fix up spacing for negative values, I use positional formatting in `printf()`.

```
f(a,b,c,d)double a,b;{c=*(long*)&a<0;b=fabs(rint(a*1000)/1000);d=b<3600;printf(a*0?"--:--.---":"%5$0*4$.f:%0*.f:%06.3f"+d*10,c*d+2,fmod((d?a:b)/60,60),fmod(b,60),c+2,a/3600);}

```

Try it online!
> 1 votes

# Answer
# Python, 123 bytes

```
lambda x:'--:--.---'*(x*0!=x*0)or'-'*(x<0)+f'{(q:=abs(round(x,3)))/3600:02.0f}:'*(q>=3600)+f'{q//60%60:02.0f}:{q%60:06.3f}'

```

Attempt This Online!

~~I don't believe Python has the concept of `Infinity` or `NaN`, so this function only accepts a floating point number.~~ TIL about `float('inf')` and `float('nan')`.

```
(x*0!=x*0)          # If the input is infinite or NaN...
'--:--.---'*        # ...return the result filled with '-'
or                  # Otherwise:
'-'*(x<0)           # Prefix with '-' if the input is negative
q:=abs(round(x,3))  # Initialize q = abs(x) rounded to 3 decimals
*(q>=3600)          # If q >= 3600...
+f'{q/3600:02.0f}:' # ...append q/3600, padded with 0s. Append ':'

# Finally, append minutes (q//60%60) padded with 0s, a literal ':',
# and seconds (q%60) padded with 0s and rounded to 3 decimal places
+f'{q//60%60:02.0f}:{q%60:06.3f}'

```
> 1 votes

# Answer
# C (gcc), 162 bytes

Building on @ErickF's answer, fixed the output for \\$-0\\$.

```
f(a,b,c)double a,b;{b=fabs(rint(a*1e3)/1e3);c=b<3600;printf(a*0?"--:--.---":"%5$0*4$.f:%0*.f:%06.3f"+c*10,a<0&c|2,fmod((c*a?a:b)/60,60),fmod(b,60),a<0|2,a/3600);}

```

Try it online!
> 1 votes

# Answer
# Perl 5 `-MPOSIX=fmod -n`, 113 bytes

```
$_*=1;s/-//;$_=.001*int$_*1000+.5;printf$&.(($h=0|$_/3600)>10?"$h:":"0$h:"x!!$h)."%02d:%06.3f",$_/60%60,fmod$_,60

```

Try it online!
> 0 votes

---
Tags: code-golf, string, floating-point
---