title: Polyglot self-interpreter time

text:
# Question
Title: Polyglot self-interpreter time
Your task is to make a program which interprets the language it is run in, but also works in many languages.

Let's say you make a Brainfuck-Underload self-interpreglot, as it will be called. Run in Brainfuck, this program should be a Brainfuck interpreter; run in Underload, it should be a Underload interpreter.

Your program should work like the hypothetical given above: given a list of languages L1, L2, L3, L4... up to Ln, it should be an L1 interpreter in L1, an L2 interpreter in L2, an L3 interpreter in L3, up to being an Ln interpreter in Ln.

Your program can handle errors in any way. However, it must never output to STDERR (or closest equivalent) if the input given for interpretation has no errors.

It must output to STDOUT (or closest equivalent) and take input from STDIN (or again, closest equivalent).

You can choose any interpretation of a given language, e.g. if your polyglot works in Brainfuck, it can interpret Brainfuck with finite or unbounded tape. You must specify what interpretations you choose to use for each language.

Programs must have at least 2 characters for this challenge to prevent empty programs from competing.

Functions such as exec and eval are allowed.

Only a Turing-complete subset of a language has to be interpreted.

Different languages have to be interpreted, not different language versions.

Your score is C/(L^3), where C is code length, computed in bytes with UTF-8 encoding, and L is the amount of languages. The lowest score wins: if two winning answers have the same score the one posted earlier wins.

Have fun.

# Answer
## GolfScript/MathGolf/CJam/Paradoc/FlogScript, 1 byte, score = 1/125 = 0.008

For all stack-based languages, input may be implicitly pushed onto the stack.

The most boring (yet probably the optimal) answer.

Going forward to see what is the most common character choice for an evaluation operator...

```
~

```

TIO for MathGolf

TIO for CJam

TIO for GolfScript

## What other languages have `~` as an evaluation built-in?

Not adding this language to the polyglot. Because I'm too lazy.

## Explanation

```
~    Evaluate the input

```
> 7 votes

# Answer
# Jelly, 05AB1E, GolfScript 8 bytes, score = \\$\frac 8 {27} \approx 0.296\\$

```
.Vq;~
ɠV

```

Try it online Jelly!

Try it online 05AB1E!

Try it online GolfScript!

In all cases, takes a program in the relevant language from STDIN and executes it, with any output going to STDOUT.
> 8 votes

# Answer
# Keg and Python 3, 19 characters, score = \\$ \frac{19}{8} \\$

```
exec(input())
"ø¿ß"

```

Try it online! (Keg)

Try it online! (Python 3)

Uses the same approach as Nick first did, but with Keg instead.

I'll have to figure out how to add another language to get competitive again.
> 4 votes

# Answer
# Clojure/Common Lisp/scheme/bash/ksh/posix sh/zsh/csh/yash/tcsh, <sup>~~34~~</sup> 33 bytes, score = 33/1000 = 0.033

*as low as 0.000327480423 points, see comment*

```
"w";eval $SHELL;exit
(eval(read))

```

Try it online!

Alternative for 31 bytes but does not work on clojure:

```
"w";eval $SHELL
#x1(eval(read))

```

Use (print "hoo") as input and it should work for all lisps. Try pwd for shells.

## lisp

Simple. These lisp dialects seem to all be similar enough to all work for this. Unfortunately, there is not a TIO for scheme. The only one of these I know is Common Lisp, which I am still learning.

Are the different implementations of CL different enough to be counted separate? Because then. . .

## shells

Just evaluates itself, then exits so it won't try to do the lisp part.
> 4 votes

# Answer
## GolfScript/Keg, 6 bytes, score = 3/4 = 0.75

Do we have to use at least one practical language? It doesn't seem to say that in the spec.

```
ß.~\;

```

## Golfscript

```
ß     # Odd undefined ops
 .    # Copy the input
  ~   # Evaluate it
   \; # Discard the unevaluated copy

```

## Keg

```
ß     # Take input & evaluate the input
 .    # Output the result as a number
  ~   # Push a random number
   \; # Escape the ; character

```
> 3 votes

# Answer
# PHP/Python 3/Javascript, 130 bytes, score = 130/27 ~ 4.814

```
[1//eval(input())
];eval("\x24a=\"/\";eval(`\x24{\x24a}/bin/echo 'eval(fgets(fopen(\"php://stdin\",\"r\")));'`);eval(prompt());");

```

Try it online - PHP

Try it online - Python 3

For javascript run it in the browser's console, as prompt is not defined in node.

NOTE - you can also put a brainfuck+ook self interpreter in there but it's too big. Explanation:

Python - the // operator is integer division, so the interpreter tries to calculate it, so it executes eval(input()), and then it errors out (which is allowed according to Should submissions be allowed to exit with an error?).

Javascript - the // is interpreted as a comment, so it gets the array \[1\]. Then it evals

```
$a="/";eval(`${$a}/bin/echo 'eval(fgets(fopen("php://stdin","r")));'`);eval(prompt());

```

And, then

```
`${$a}/bin/echo 'eval(fgets(fopen("php://stdin","r")));'`

```

evaluates to `//bin/echo 'eval(fgets(fopen("php://stdin","r")));'`, which then gets executed and ignored (as a comment), and then it runs `eval(prompt())` to execute the input.

PHP - `//eval(input())` is interpreted as a comment, so it get's the array \[1\] like in JS and does nothing with it. Then it evals

```
$a="/";eval(`${$a}/bin/echo 'eval(fgets(fopen("php://stdin","r")));'`);eval(prompt());

```

but in here

```
`${$a}/bin/echo 'eval(fgets(fopen("php://stdin","r")));'`

```

Is executed from the shell, and translates to `//bin/echo 'eval(fgets(fopen("php://stdin","r")));'` which returns `eval(fgets(fopen("php://stdin","r")));`. Then that gets evaled, which executes the code from the input. then it tries evaluating `prompt()` which doesn't exist and errors out.

PS - This is my first post here, so if I've done anything wrong/missed something please let me know.
> 2 votes

---
Tags: code-challenge, interpreter, polyglot, rosetta-stone
---


title: Verify Topology

text:
# Question
Title: Verify Topology
### Challenge

Given a set `T` of subsets of a finite set `S={1,2,3,...,n}`, determine whether `T` is a *topology* or not.

### Explanation

The *powerset* `P(S)` of some set `S` is the set of all subsets of `S`. Some examples:

```
S = {}, P(S) = {{}}
S = {1}, P(S) = {{}, {1}}
S = {1,2}, P(S) = {{}, {1}, {2}, {1,2}}
S = {1,2,3}, P(S) = {{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}

```

A *topology* `T` on the set `S` is a subset of `P(S)` with following properties:

* `{}` is in `T` and `S` is in `T`
* If `A` and `B` are in `T` then so is their intersection `A ∩ B`
* If `A` and `B` are in `T` then so is their union `A ∪ B` *

* This definition is not quite correct, but it is true for finite sets, which is sufficient for the purposes of this challenge. The actual axiom would allow for infinite unions as well, but that is irrelevant in the finite case.

### Details

* You can assume that `S = {1,2,...,n}` (or alternatively `S = {0,1,...,n}`) where `n` is the largest integer that appears in the sets of `T`.
* The input format is flexible: You can use a string, a list of lists or set of lists or any similar format your langauge can handle. You can also use sets like `S = {0,1,...,n}` if it is more convenient.
* The output must be truthey or falsey.
* You are allowed to take `n` (or alternatively `n+1` or `n-1`) as an additional input.
* If you work with ordered lists, you can assume that the numbers within a set are sorted. You can also assume that the list has a certain order (e.g. lexicographical.
* As we represent sets, you can assume that no two entries of their list-representation are equal.

### Examples

**Topologies**

```
{{}}  over {}
{{},{1}} over {1}
P(S) over S (see in the explanation)
{{},{1},{1,2}} over {1,2}
{{},{1},{2,3},{1,2,3}} over {1,2,3}
{{1}, {1,2,3}, {1,4,5,6}, {1,2,3,4,5,6}, {}, {2,3}, {4,5,6}, {2,3,4,5,6}}
{{}, {1}, {2,3}, {2}, {4,5,6}, {5,6}, {5}, {2,5,6}, {2,5}, {1,5}, {1,2,3,4,5,6}, {1,2,3}, {1,2}, {1,4,5,6}, {1,5,6}, {1,2,5,6}, {2,3,4,5,6}, {2,3,5,6}, {2,3,5}, {1,2,3,5}, {2,4,5,6}, {1,2,5}, {1,2,3,5,6}, {1,2,4,5,6}}
{{}, {1}, {1,2}, {1,2,3}, {1,2,3,4}, {1,2,3,4,5}, {1,2,3,4,5,6}, {1,2,3,4,5,6,7}, {1,2,3,4,5,6,7,8}, {1,2,3,4,5,6,7,8,9}}
{{}, {1}, {1,2,3}, {1,2,3,4,5}, {1,2,3,4,5,6,7}, {1,2,3,4,5,6,7,8,9}}

```

**non-Topologies**

```
{{1}} because {} is not contained
{{},{2}} because {1,2} is not contained
{{},{1,2},{2,3}} because the union {1,2,3} is not contained
{{},{1},{1,2},{2,3},{1,2,3}} because the intersection of {1,2} and {2,3} is not contained
{{},{1},{2},{3},{1,2},{2,3},{1,2,3}} because the union of {1} and {3} is not contained
{{}, {1}, {2,3}, {2}, {4,5,6}, {5,6}, {5}, {2,5,6}, {2,5}, {1,5}, {1,2,3,4,5,6}, {1,2,3}, {1,2}, {1,4,5,6}, {1,5,6}, {1,2,5,6}, {2,3,4,5,6}, {2,3,5,6}, {2,3,5}, {2,4,5,6}, {1,2,5}, {1,2,3,5,6}, {1,2,4,5,6}} because {1,2,3,5} is missing
{{}, {1}, {2}, {1,2,3}, {1,2,3,4,5}, {1,2,3,4,5,6,7}, {1,2,3,4,5,6,7,8,9}} because {1,2} is missing

```

# Answer
> 7 votes
# Python 2, ~~117~~ ~~99~~ ~~97~~ 91 bytes

```
n,x=input();sum(set.union(*x))!=n*-~n/2>q
[map(x.index,(i-i,i|j,i&j))for i in x for j in x]

```

Try it online!

Output is via exit code

# Answer
> 5 votes
# Mathematica, ~~87~~ ~~73~~ ~~66~~ 63 bytes

```
Outer[{#⋂#2,#⋃#2}&,#,#,1]~Flatten~2⋃{{},Range@#2}==#⋃#&

```

Takes `[T, n]` as input.

### Explanation

```
{#⋂#2,#⋃#2}&

```

Function that returns the intersection and the union of the inputs

```
Outer[ ... ,#,#,1]

```

Map that function onto the input list at level 1.

```
... ~Flatten~2

```

Flatten the result (the `Outer` part returns a bunch of nested `List`s).

```
... ⋃{{},Range@#2}

```

Take the union between the flattened list and `{{}, S}`. This removes duplicates and adds `{}` and `S` to the resulting list.

```
... ==#⋃#

```

Check whether the list from above is equal to the sorted version of the input.

# Answer
> 5 votes
# Haskell, ~~95 89 74~~ 78 bytes

```
import Data.List
t#n=all(`elem`t)$sort<$>[1..n]:[]:([union,intersect]<*>t<*>t)

```

Try it online!

Explanation:

```
                              ([union,intersect]<*>t<*>t) -- create all unions & intersections
                    [1..n]:[]:                            -- add the empty list and the full list
             sort<$>                                --sort them all
                                -- (as 'union' does not necessarily produce sorted outputs)
all(`elem`t)$                   -- check whether they are all already contained

```

# Answer
> 4 votes
# MATL, 38 bytes

```
!t~hXAs1>GXBXH2Z^!"@Z}Z|1MZ&hHm]vAGn~+

```

Input is a binary matrix where each row is a set, each column is an element, and each entry indicates membership. For example, `{{},{1},{1,2}}` is expressed as `[0 0;1 0;1 1]`. Use the linked Octave program to convert to this format.

Try it online! Or verify all test cases.

### Explanation

```
!        % Implicit input. Transpose
t~       % Push a negated copy
h        % Horizontally concatenate both matrices
XA       % All: true for columns containing only 1
s        % Sum
1>       % Does it exceed 1? If so, both the empty set and the total
         % set are in the input
G        % Push input again
XB       % Convert each row from binary to decimal. This gives a column
         % vector of numbers that encode each set's contents. Union and
         % intersection will be done as bitwise XOR and AND
XH       % Copy to clipboard H
2Z^!     % Cartesian square transposed: gives all pairs of numbers as
         % columns of a matrix
"        % For each column
  @      %   Push current column
  Z}     %   Split into the two numbers
  Z|     %   Bitwise XOR
  1M     %   Push the two numbers again
  Z&     %   Bitwise AND
  h      %   Concatenate the two results horizontally
  Hm     %   Are they members of the vector of encoded sets? This gives
         %   a row vector with the two results
]        % End
v        % Concatenate all stack contents into a vertical vector
A        % Does it only contain ones? This is the main result: true iff
         % input is a non-empty topology. The empty input gives false,
         % and so it needs to be special cased
G        % Push input again
n~       % Is it empty?
+        % Add thw two results. Implicit display

```

# Answer
> 3 votes
# Python 2, ~~92 71~~ 122 bytes

* Thanks a lot to @ovs for a heavy 19 bytes reduction: `&` and `|` shorthands for set operations.
* Thanks @notjagan for 5 bytes
* Thanks to @ovs for 2 bytes: `set()` as `i-i`

Lambda that takes a list of sets as input, and returns True/false. Simply checks if there is an empty set and the union and intersection of each sets(two sets iterated as `i` and `j`) exists in the given list of sets.

```
lambda x:x.sort()or all(k in x[-1]for k in range(1,max(x[-1])))and all(a in x for i in x for j in x for a in[i-j,i|j,i&j])

```

Try it online!

# Answer
> 2 votes
# Pyth, ~~24~~ 23 bytes

```
q@aasm,@Fd{Ssd*QQYJUEyJ

```

Test suite

This program takes input as an ordered list of ordered lists. The inner lists must be in ascending order and the order list must be sorted by length then lexicographically. I have confirmed that this is an allowed input format. Numbers start at 0, and N+1 is also taken as input.

As for how it works, we filter out anything not in P(S), then add S, `[]`, the intersection of every pair and the union of every pair, deduplicate, and check that the result is equal to the input.

# Answer
> 2 votes
## CJam (23 bytes)

```
{[,M2$2m*{_~&\~|$}/]^!}

```

Online test suite. This is an anonymous block (function). I assume `S = {0,1,...,n}`; the block takes an array of sorted arrays and `n+1` as parameters and leaves `0` or `1` on the stack. In the case `{{}}` the code and test framework assume that `n+1 = 0`.

# Answer
> 0 votes
# Axiom, 358 bytes

```
t(a,s)==(aa:=sort(removeDuplicates(a));ss:=sort(removeDuplicates(s));a:=sort(a);s:=sort(s);a~=aa or s~=ss=>false;a:=map(sort, a);~member?([],a) or ~member?(s,a)=>false;for x in a repeat(for j in x repeat if ~member?(j,s) then return false;for y in a repeat if ~member?(sort(setIntersection(x,y)),a) or ~member?(sort(setUnion(x,y)),a) then return false);true)

```

ungolfed and results:

```
-- all the List have to be sorted because in list [1,2]~=[2,1]
-- So here "set" means: "List without duplicate, sorted with sort() function"
-- Return true if
-- 1) a,s are set for above definition
-- 2) a is in P(s)
-- 3) s,[] are in a
-- 4) for all x and y in a => xUy is in a and x intersect y is in a
t1(a:List List INT, s:List INT):Boolean==
    aa:=sort(removeDuplicates(a));ss:=sort(removeDuplicates(s))
    a :=sort(a);                  s :=sort(s)
    a~=aa          or s~=ss        =>false   -- they are not sets but list with element duplicate
    a:=map(sort, a)                          -- subset of a has to be sorted too
    ~member?([],a) or ~member?(s,a)=>false
    for x in a repeat
       for j in x repeat if ~member?(j,s) then return false
       for y in a repeat if ~member?(sort(setIntersection(x,y)),a) or ~member?(sort(setUnion(x,y)),a) then return false
    true

(4) -> t([[]], [])
   (4)  true
                                                            Type: Boolean
(5) -> t([[],[1]], [1])
   (5)  true
                                                            Type: Boolean
(6) -> t([[],[1],[2,1]], [1,2])
   (6)  true
                                                            Type: Boolean
(7) -> t([[],[1],[2,3],[1,2,3]], [3,1,2])
   (7)  true
                                                            Type: Boolean
(8) -> t([[1], [1,2,3], [1,4,5,6], [1,2,3,4,5,6], [], [2,3], [4,5,6], [2,3,4,5,6]], [1,2,3,4,5,6])
   (8)  true
                                                            Type: Boolean
(9) -> t([[], [1], [2,3], [2], [4,5,6], [5,6], [5], [2,5,6], [2,5], [1,5], [1,2,3,4,5,6], [1,2,3], [1,2], [1,4,5,6], [1,5,6], [1,2,5,6], [2,3,4,5,6], [2,3,5,6], [2,3,5], [1,2,3,5], [2,4,5,6], [1,2,5], [1,2,3,5,6], [1,2,4,5,6]], [1,2,3,4,5,6])
   (9)  true
                                                            Type: Boolean
(10) -> t([[], [1], [1,2], [1,2,3], [1,2,3,4], [1,2,3,4,5], [1,2,3,4,5,6], [1,2,3,4,5,6,7], [1,2,3,4,5,6,7,8], [1,2,3,4,5,6,7,8,9]], [1,2,3,4,5,6,7,8,9])
   (10)  true
                                                            Type: Boolean
(11) -> t([[], [1], [1,2,3], [1,2,3,4,5], [1,2,3,4,5,6,7], [1,2,3,4,5,6,7,8,9]], [1,2,3,4,5,6,7,8,9])
   (11)  true
                                                            Type: Boolean
(2) -> t([[1]], [1])
   (2)  false
                                                            Type: Boolean
(4) -> t([[],[2]], [1,2])
   (4)  false
                                                            Type: Boolean
(5) -> t([[],[1,2],[2,3]], [1,2,3])
   (5)  false
                                                            Type: Boolean
(6) -> t([[],[1],[1,2],[2,3],[1,2,3]], [1,2,3])
   (6)  false
                                                            Type: Boolean
(7) -> t([[],[1],[2],[3],[1,2],[2,3],[1,2,3]] , [1,2,3])
   (7)  false
                                                            Type: Boolean
(8) -> t([[], [1], [2,3], [2], [4,5,6], [5,6], [5], [2,5,6], [2,5], [1,5],[1,2,3,4,5,6], [1,2,3], [1,2], [1,4,5,6], [1,5,6], [1,2,5,6], [2,3,4,5,6], [2,3,5,6], [2,3,5], [2,4,5,6], [1,2,5], [1,2,3,5,6], [1,2,4,5,6]], [1,2,3,4,5,6])
   (8)  false
                                                            Type: Boolean
(9) -> t([[], [1], [2], [1,2,3], [1,2,3,4,5], [1,2,3,4,5,6,7], [1,2,3,4,5,6,7,8,9]] , [1,2,3,4,5,6,7,8,9])
   (9)  false
                                                            Type: Boolean
(10) -> t([[], [1], [2,3], [2], [4,5,6], [5,6], [5], [2,5,6], [2,5], [1,5],[1,2,3,4,5,6], [1,2,3], [1,2], [1,4,5,6], [1,5,6], [1,2,5,6], [2,3,4,5,6], [2,3,5,6], [2,3,5], [2,4,5,6], [1,2,5], [1,2,3,5,6], [1,2,4,5,6]], [1,2,3,4,5,6])
   (10)  false
                                                            Type: Boolean

```

# Answer
> 0 votes
# Python, 87 bytes

`lambda n,T:(set(range(n))in T)&all(x in T for i in T for j in T for x in [i-i,i&j,i|j])`

Takes the number `n` and a list of sets `T` as input.

---
Tags: code-golf, math, decision-problem, set-theory, topology
---


title: Are these two DFAs equivalent?

text:
# Question
Title: Are these two DFAs equivalent?
Two Deterministic Finite Automata or DFAs can be checked to see if they accept same set of strings in polynomial time. See section 3.3 of this for a long list of methods and this SO question/answer for a much shorter list.

**Input**

Your input will be two DFAs. In order to be able to test your code, I have provided DFAs in the following format. This is taken directly from GAP (and slightly simplified).

```
Automaton( Type, Size, Alphabet, TransitionTable, Initial, Accepting )

```

For the input, Type will always be "det". Size is a positive integer representing the number of states of the automaton. Alphabet is the number of letters of the alphabet. TransitionTable is the transition matrix. The entries are non-negative integers not greater than the size of the automaton. We may write a 0 to mean that no transition is present. Initial and Accepting are, respectively, the lists of initial and accepting states. You can assume there will be exactly one initial state.

For example:

```
Automaton("det",4,2,[ [ 1, 3, 4, 0 ], [ 1, 2, 3, 4 ] ],[ 3 ],[ 2, 3, 4 ])

```

This has transition table:

```
   |  1  2  3  4
-----------------
 a |  1  3  4
 b |  1  2  3  4
Initial state:    [ 3 ]
Accepting states: [ 2, 3, 4 ]

```

And diagram:

It is equivalent to:

```
Automaton("det",3,2,[ [ 1, 3, 1 ], [ 1, 2, 3 ] ],[ 2 ],[ 2, 3 ])

```

which has diagram:

In order to remove parsing as a significant part of this challenge, you are free to perform trivial parsing of the input format before giving it to your code. This means you can delete any part or parts, reorder and change one type of bracket to another before passing the input to your code. For example, the previous example can be given as

```
3,2,[ [ 1, 3, 1 ], [ 1, 2, 3 ] ],[ 2 ],[ 2, 3 ]

```

if that helps.

Here is a more complicated example,

```
Automaton("det",6,4,[ [ 0, 2, 3, 5, 0, 0 ], [ 1, 3, 5, 0, 0, 0 ], [ 1, 3, 5, 6, 0, 0 ], [ 2, 3, 5, 0, 0, 0 ] ],[ 1 ],[ 1, 4, 5, 6 ])

```

has diagram:

It is equivalent to:

```
Automaton("det",5,4,[ [ 2, 2, 2, 4, 5 ], [ 2, 2, 3, 1, 4 ], [ 2, 2, 3, 1, 4 ], [ 2, 2, 5, 1, 4 ] ],[ 3 ],[ 1, 3 ])

```

with diagram:

# More examples of equivalent DFAs

1.

```
Automaton("det",18,4,[ [ 2, 2, 6, 10, 2, 6, 7, 16, 14, 10, 18, 14, 7, 14, 15, 16, 7, 18 ], [ 3, 3, 7, 11, 3, 7, 15, 11, 7, 17, 15, 18\
, 18, 7, 15, 17, 15, 15 ], [ 4, 4, 8, 7, 4, 13, 15, 15, 16, 7, 8, 7, 15, 7, 15, 15, 16, 13 ], [ 5, 5, 9, 12, 5, 14, 7, 13, 9, 14, 17, 12, \
13, 14, 15, 7, 17, 7 ] ],[ 1 ],[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18 ])

```

```
Automaton("det",16,4,[ [ 1, 2, 15, 15, 5, 6, 7, 7, 6, 2, 16, 12, 12, 16, 15, 16 ], [ 1, 3, 1, 7, 9, 15, 1, 1, 15, 8, 7, 3, 8, 15, 1, \
15 ], [ 1, 1, 2, 1, 13, 4, 4, 10, 10, 1, 15, 15, 15, 2, 1, 15 ], [ 1, 15, 3, 4, 5, 16, 15, 3, 14, 4, 11, 16, 11, 14, 15, 16 ] ],[ 5 ],[ 2,\
 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 ])

```
2.

```
Automaton("det",50,4,[ [ 2, 2, 9, 13, 17, 9, 13, 17, 9, 24, 28, 30, 13, 33, 36, 30, 17, 9, 13, 9, 13, 39, 30, 24, 25, 44, 42, 28, 24, 30, 47, 39, 33, 50, 36, 36, 42, 46, 39, 25, 24, 42, 43, 44, 36, 46, 47, 42, 25, 50 ], [ 3, 6, 10, 14, 18, 10, 14, 20, 10, 25, 14, 10, 32, 34, 34, 38, 20, 10, 14, 10, 14, 38, 10, 25, 43, 34, 25, 45, 46, 10, 32, 49, 34, 43, 34, 49, 50, 50, 49, 50, 46, 25, 43, 49, 49, 50, 45, 50, 43, 43 ], [ 4, 7, 11, 15, 19, 11, 15, 21, 22, 26, 26, 31, 15, 11, 25, 15, 21, 11, 15, 11, 15, 40, 15, 40, 43, 43, 44, 26, 26, 15, 44, 31, 41, 26, 47, 25, 25, 22, 40, 43, 40, 25, 43, 43, 47, 41, 44, 44, 44, 40 ], [ 5, 8, 12, 16, 5, 12, 16, 8, 23, 27, 29, 12, 23, 35, 37, 16, 8, 12, 16, 12, 16, 41, 23, 42, 25, 40, 27, 27, 29, 23, 48, 45, 37, 49, 35, 42, 37, 48, 42, 40, 41, 42, 43, 25, 45, 37, 27, 48, 49, 25 ] ],[ 1 ],[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 44, 45, 46, 47, 48, 49, 50 ])

```

```
Automaton("det",39,4,[ [ 1, 2, 3, 3, 5, 24, 7, 8, 22, 20, 8, 32, 18, 18, 3, 19, 25, 18, 19, 20, 25, 22, 23, 24, 25, 25, 24, 23, 5, 2, 35, 32, 19, 19, 35, 36, 36, 36, 36 ], [ 1, 38, 1, 23, 15, 9, 11, 26, 23, 28, 26, 10, 9, 26, 1, 3, 22, 26, 3, 28, 22, 23, 1, 15, 3, 3, 15, 1, 28, 27, 10, 27, 23, 23, 38, 15, 28, 15, 28 ], [ 1, 5, 1, 1, 1, 4, 12, 6, 6, 31, 31, 37, 37, 30, 5, 5, 29, 37, 3, 21, 4, 21, 4, 4, 4, 29, 30, 29, 1, 5, 29, 37, 5, 3, 29, 3, 3, 2, 2 ], [ 1, 16, 3, 4, 3, 21, 7, 18, 33, 39, 14, 13, 13, 14, 15, 16, 17, 18, 19, 34, 21, 34, 3, 19, 19, 16, 38, 15, 4, 33, 17, 18, 33, 34, 16, 19, 34, 38, 39 ] ],[ 7 ],[ 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39 ])

```

3.

```
Automaton("det",288,4,[[2, 6, 10, 14, 18, 6, 10, 14, 18, 25, 29, 33, 36, 40, 43, 46, 36, 53, 10, 14, 18, 10, 14, 18, 25, 29, 60, 36, 29, 67, 71, 75, 77, 81, 83, 87, 88, 90, 94, 40, 98, 46, 104, 108, 111, 46, 116, 120, 75, 123, 127, 129, 53, 10, 14, 131, 129, 71, 75, 136, 140, 143, 146, 87, 149, 75, 67, 68, 155, 153, 156, 159, 161, 163, 75, 165, 77, 170, 81, 172, 81, 67, 88, 123, 156, 146, 87, 88, 156, 90, 183, 186, 188, 87, 90, 183, 94, 192, 143, 197, 199, 116, 75, 104, 108, 204, 172, 108, 208, 120, 127, 159, 90, 199, 163, 159, 215, 156, 149, 120, 153, 217, 123, 218, 131, 221, 127, 159, 87, 123, 225, 88, 155, 67, 165, 136, 227, 143, 221, 123, 218, 221, 143, 68, 67, 88, 123, 127, 143, 217, 68, 67, 153, 154, 155, 156, 234, 235, 159, 120, 161, 237, 143, 217, 165, 143, 241, 199, 188, 242, 197, 75, 67, 165, 241, 217, 248, 250, 172, 146, 221, 161, 225, 234, 111, 186, 153, 75, 217, 75, 188, 192, 257, 188, 68, 120, 90, 186, 127, 90, 208, 146, 221, 259, 140, 120, 235, 208, 165, 262, 199, 188, 68, 120, 215, 267, 217, 218, 250, 83, 75, 165, 75, 215, 225, 208, 234, 71, 149, 153, 75, 235, 208, 234, 67, 265, 272, 233, 241, 143, 120, 242, 257, 155, 153, 143, 153, 248, 267, 250, 116, 120, 75, 237, 71, 235, 250, 163, 259, 227, 153, 262, 67, 75, 155, 233, 272, 265, 116, 241, 281, 272, 68, 149, 120, 155, 283, 163, 67, 208, 285, 265, 287, 233, 285, 68, 287, 68], [3, 7, 11, 15, 19, 7, 11, 15, 22, 26, 30, 15, 37, 41, 44, 47, 50, 54, 11, 15, 19, 11, 15, 22, 26, 30, 61, 37, 30, 68, 72, 30, 78, 47, 84, 26, 30, 91, 37, 96, 99, 102, 105, 109, 112, 115, 117, 109, 122, 124, 128, 130, 54, 11, 15, 130, 132, 72, 30, 137, 141, 122, 147, 132, 150, 30, 68, 154, 109, 68, 157, 109, 162, 164, 30, 166, 168, 99, 102, 173, 175, 176, 177, 124, 128, 147, 132, 30, 72, 168, 184, 115, 189, 132, 96, 99, 37, 166, 195, 96, 99, 201, 150, 105, 109, 205, 164, 109, 154, 109, 157, 109, 211, 112, 213, 109, 154, 72, 109, 195, 208, 215, 124, 208, 130, 150, 166, 224, 26, 124, 157, 30, 226, 217, 166, 115, 213, 150, 30, 124, 208, 150, 195, 208, 176, 177, 124, 72, 224, 208, 233, 217, 68, 154, 195, 214, 195, 208, 109, 109, 236, 117, 195, 208, 214, 195, 201, 99, 173, 166, 168, 177, 68, 246, 213, 215, 68, 251, 173, 147, 150, 254, 166, 195, 99, 175, 208, 30, 215, 122, 164, 166, 251, 173, 154, 195, 78, 258, 166, 168, 154, 147, 150, 260, 141, 226, 217, 154, 214, 254, 184, 263, 154, 195, 154, 109, 208, 208, 269, 84, 177, 246, 150, 154, 166, 215, 195, 166, 150, 208, 150, 208, 215, 195, 215, 213, 195, 208, 213, 150, 195, 166, 254, 109, 68, 224, 233, 68, 109, 236, 201, 226, 150, 213, 166, 208, 277, 117, 278, 213, 233, 236, 215, 279, 195, 208, 224, 201, 117, 280, 254, 195, 208, 109, 109, 226, 213, 213, 215, 215, 277, 280, 195, 208, 236, 233, 195, 208], [4, 8, 12, 16, 20, 8, 12, 16, 23, 27, 31, 34, 38, 42, 12, 48, 51, 55, 12, 16, 20, 12, 16, 23, 56, 58, 62, 51, 65, 69, 73, 76, 79, 69, 85, 42, 89, 92, 95, 42, 100, 48, 106, 31, 113, 48, 118, 68, 48, 125, 48, 51, 55, 12, 16, 62, 51, 133, 135, 138, 56, 144, 62, 148, 151, 48, 144, 154, 154, 155, 69, 118, 154, 69, 48, 161, 79, 171, 69, 174, 69, 69, 178, 180, 69, 85, 148, 138, 182, 92, 95, 155, 135, 42, 92, 95, 148, 193, 76, 198, 200, 118, 48, 202, 58, 62, 206, 207, 69, 209, 210, 89, 92, 200, 135, 178, 216, 69, 174, 68, 68, 138, 202, 65, 219, 222, 48, 118, 148, 56, 138, 118, 154, 69, 155, 138, 228, 144, 206, 106, 229, 174, 144, 154, 144, 138, 202, 48, 144, 138, 154, 144, 68, 154, 154, 69, 228, 133, 152, 165, 154, 69, 182, 240, 155, 135, 155, 200, 135, 243, 198, 210, 244, 155, 165, 152, 249, 144, 206, 219, 252, 154, 178, 255, 113, 155, 155, 210, 240, 135, 135, 65, 151, 48, 155, 209, 92, 155, 210, 92, 244, 62, 206, 138, 202, 68, 151, 144, 161, 68, 200, 135, 265, 165, 266, 73, 152, 207, 144, 62, 48, 161, 76, 249, 138, 69, 271, 133, 73, 265, 135, 151, 144, 266, 144, 155, 182, 133, 155, 182, 161, 274, 151, 161, 265, 135, 155, 266, 151, 144, 138, 161, 275, 69, 73, 276, 144, 135, 138, 249, 68, 68, 244, 135, 161, 151, 144, 155, 138, 155, 151, 144, 155, 151, 161, 161, 249, 69, 69, 244, 144, 155, 271, 276, 144, 155, 266, 265], [5, 9, 13, 17, 21, 9, 13, 17, 24, 28, 32, 35, 39, 28, 45, 49, 52, 9, 13, 17, 21, 13, 17, 24, 57, 59, 63, 64, 66, 70, 74, 32, 80, 82, 86, 28, 32, 93, 39, 97, 101, 103, 107, 110, 114, 66, 119, 121, 49, 126, 49, 52, 9, 13, 17, 63, 64, 134, 59, 139, 142, 145, 63, 64, 152, 66, 153, 68, 144, 70, 158, 160, 151, 134, 66, 167, 169, 101, 134, 59, 70, 82, 179, 181, 82, 86, 64, 66, 74, 169, 185, 187, 190, 97, 191, 101, 64, 194, 196, 191, 101, 160, 103, 203, 160, 63, 103, 121, 195, 110, 179, 110, 212, 114, 214, 167, 213, 134, 160, 153, 121, 158, 203, 187, 220, 223, 66, 119, 57, 142, 139, 59, 151, 134, 187, 66, 214, 152, 66, 107, 230, 231, 153, 144, 145, 139, 203, 103, 232, 187, 151, 152, 153, 154, 68, 70, 214, 187, 121, 160, 68, 238, 239, 230, 70, 214, 187, 101, 59, 194, 169, 179, 245, 247, 214, 232, 70, 152, 66, 220, 253, 144, 194, 196, 101, 70, 187, 194, 256, 190, 231, 66, 152, 66, 195, 196, 80, 247, 194, 169, 213, 63, 103, 139, 203, 261, 152, 68, 239, 121, 185, 264, 213, 214, 68, 268, 121, 121, 145, 63, 139, 270, 223, 195, 66, 238, 239, 187, 74, 230, 231, 121, 266, 153, 232, 195, 236, 273, 70, 74, 239, 66, 121, 268, 245, 119, 247, 153, 144, 153, 187, 270, 253, 195, 167, 230, 232, 119, 66, 70, 261, 153, 256, 264, 236, 144, 266, 273, 158, 247, 144, 68, 273, 121, 167, 282, 195, 70, 158, 284, 266, 286, 236, 288, 68, 286, 68, 288]],[1],[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255, 256, 257, 258, 259, 260, 261, 262, 263, 264, 265, 266, 267, 268, 269, 270, 271, 272, 273, 274, 275, 276, 277, 278, 279, 280, 281, 282, 283, 284, 285, 286, 287, 288])

```

```
Automaton("det",266,4,[[1, 127, 50, 50, 115, 249, 50, 8, 257, 10, 151, 12, 13, 14, 81, 78, 34, 106, 137, 107, 21, 22, 82, 89, 71, 43, 43, 62, 63, 63, 44, 10, 179, 171, 214, 265, 206, 38, 137, 152, 21, 151, 71, 22, 41, 41, 47, 13, 49, 50, 50, 210, 50, 210, 116, 90, 64, 49, 207, 207, 207, 62, 232, 64, 64, 89, 151, 236, 236, 70, 71, 236, 116, 260, 128, 75, 13, 38, 77, 133, 14, 82, 13, 13, 77, 235, 64, 64, 231, 206, 138, 91, 91, 206, 90, 264, 137, 169, 10, 10, 41, 71, 232, 228, 232, 21, 21, 107, 106, 110, 111, 266, 256, 114, 114, 116, 251, 251, 116, 114, 114, 111, 266, 260, 122, 182, 127, 128, 129, 213, 132, 132, 129, 49, 49, 138, 138, 138, 249, 71, 43, 43, 210, 235, 183, 214, 132, 265, 206, 138, 232, 64, 64, 153, 153, 64, 152, 152, 82, 236, 236, 82, 116, 116, 64, 207, 266, 64, 231, 169, 171, 250, 227, 70, 175, 175, 176, 10, 47, 178, 178, 110, 111, 266, 260, 122, 266, 127, 213, 49, 49, 152, 257, 153, 257, 90, 90, 183, 250, 264, 62, 228, 229, 82, 82, 206, 64, 266, 249, 249, 249, 242, 213, 214, 64, 116, 114, 114, 50, 50, 236, 236, 261, 115, 152, 251, 8, 228, 229, 229, 231, 232, 237, 235, 235, 236, 237, 235, 235, 235, 235, 235, 235, 242, 242, 242, 115, 251, 249, 250, 116, 116, 116, 207, 64, 265, 266, 257, 256, 266, 264, 261, 260, 264, 265, 266], [1, 125, 1, 114, 114, 121, 115, 3, 23, 19, 13, 15, 230, 28, 201, 202, 16, 84, 123, 103, 105, 208, 114, 84, 172, 199, 199, 119, 83, 83, 123, 170, 16, 31, 27, 26, 25, 104, 102, 23, 28, 13, 120, 208, 48, 103, 19, 230, 239, 1, 114, 218, 115, 219, 82, 140, 23, 208, 204, 216, 216, 119, 174, 119, 119, 84, 13, 115, 115, 50, 120, 50, 82, 204, 262, 79, 230, 104, 203, 85, 28, 114, 230, 230, 203, 3, 23, 119, 96, 96, 96, 123, 102, 140, 208, 3, 200, 200, 98, 97, 103, 120, 119, 120, 119, 28, 105, 103, 105, 54, 3, 23, 141, 1, 250, 50, 82, 114, 50, 1, 250, 3, 3, 219, 219, 125, 54, 263, 124, 124, 27, 124, 223, 208, 239, 25, 208, 208, 120, 120, 217, 217, 217, 120, 120, 142, 142, 141, 140, 140, 174, 174, 174, 204, 216, 23, 119, 23, 250, 114, 114, 250, 162, 162, 159, 205, 159, 159, 208, 123, 170, 1, 219, 50, 208, 208, 123, 177, 177, 19, 170, 173, 172, 172, 199, 199, 23, 186, 185, 184, 184, 23, 120, 216, 23, 140, 208, 120, 1, 3, 119, 120, 114, 114, 250, 239, 119, 3, 121, 3, 120, 219, 212, 212, 23, 50, 1, 250, 1, 114, 50, 114, 219, 114, 23, 114, 3, 120, 114, 114, 208, 119, 125, 121, 3, 50, 54, 120, 3, 120, 121, 3, 120, 218, 219, 217, 114, 114, 3, 1, 250, 250, 250, 253, 252, 173, 172, 120, 125, 3, 3, 219, 219, 3, 54, 3], [1, 1, 249, 249, 6, 1, 1, 247, 7, 130, 167, 17, 11, 66, 33, 33, 131, 136, 10, 32, 150, 9, 112, 36, 149, 112, 149, 56, 167, 37, 181, 130, 35, 147, 139, 51, 139, 11, 10, 234, 147, 37, 148, 113, 136, 136, 146, 24, 249, 1, 1, 249, 249, 249, 139, 6, 238, 127, 134, 238, 134, 9, 148, 238, 134, 167, 36, 50, 249, 247, 73, 249, 51, 139, 112, 167, 76, 76, 11, 167, 80, 73, 67, 66, 66, 135, 58, 58, 112, 139, 233, 100, 100, 2, 6, 95, 10, 32, 130, 130, 99, 94, 94, 56, 149, 150, 147, 150, 136, 51, 51, 51, 7, 51, 51, 51, 7, 6, 139, 139, 139, 2, 58, 134, 139, 7, 1, 112, 112, 249, 238, 238, 112, 249, 127, 238, 233, 238, 1, 149, 112, 149, 249, 135, 7, 139, 238, 51, 139, 238, 112, 238, 233, 234, 234, 134, 234, 190, 112, 50, 249, 73, 139, 51, 238, 134, 51, 134, 148, 32, 147, 145, 145, 145, 258, 259, 180, 130, 146, 189, 189, 51, 51, 134, 134, 139, 2, 1, 249, 127, 249, 191, 191, 191, 188, 188, 188, 188, 198, 197, 196, 196, 195, 187, 187, 139, 233, 134, 127, 127, 127, 49, 249, 139, 243, 211, 211, 211, 210, 210, 210, 210, 95, 209, 241, 209, 126, 117, 117, 9, 112, 112, 50, 50, 50, 50, 50, 50, 49, 49, 127, 127, 127, 249, 249, 249, 7, 7, 1, 247, 51, 139, 211, 134, 134, 51, 51, 7, 7, 2, 126, 145, 139, 247, 51, 51], [1, 51, 3, 4, 4, 7, 7, 50, 73, 61, 11, 12, 40, 109, 101, 93, 45, 18, 19, 20, 21, 64, 161, 29, 193, 118, 193, 65, 11, 42, 19, 59, 30, 46, 163, 164, 163, 40, 39, 57, 46, 42, 246, 60, 18, 21, 61, 158, 72, 50, 51, 53, 53, 3, 55, 55, 57, 246, 156, 64, 65, 64, 155, 64, 65, 11, 29, 68, 69, 236, 160, 72, 73, 55, 157, 11, 154, 154, 40, 11, 46, 160, 225, 192, 192, 86, 87, 88, 157, 118, 155, 19, 39, 74, 161, 239, 92, 92, 166, 254, 20, 144, 88, 240, 65, 109, 108, 21, 21, 50, 50, 73, 73, 50, 247, 236, 73, 161, 72, 3, 5, 54, 86, 239, 3, 51, 50, 64, 64, 161, 165, 64, 157, 161, 245, 165, 60, 64, 51, 240, 161, 240, 4, 144, 51, 55, 57, 73, 55, 57, 157, 157, 155, 57, 64, 156, 64, 87, 118, 160, 161, 248, 163, 164, 165, 168, 164, 168, 60, 19, 108, 3, 3, 72, 64, 60, 19, 194, 194, 61, 59, 247, 247, 193, 193, 5, 74, 7, 69, 244, 69, 156, 240, 65, 74, 74, 246, 143, 219, 86, 88, 144, 222, 222, 226, 72, 60, 239, 52, 54, 143, 239, 72, 72, 215, 221, 219, 224, 219, 220, 221, 222, 239, 220, 215, 222, 54, 160, 160, 161, 64, 64, 160, 68, 236, 236, 236, 160, 239, 240, 244, 245, 246, 69, 72, 161, 51, 160, 50, 50, 248, 118, 226, 255, 255, 248, 248, 160, 160, 245, 245, 72, 72, 236, 236, 236]],[12],[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255, 256, 257, 258, 259, 260, 261, 262, 263, 264, 265, 266])

```

4.

```
Automaton("det",9,4,[[1, 1, 2, 3, 1, 1, 2, 5, 2], [1, 1, 2, 8, 2, 2, 1, 6, 2], [1, 1, 2, 7, 2, 1, 2, 2, 2], [1, 1, 2, 9, 1, 1, 1, 1, 1]],[4],[2, 6])

```

```
Automaton("det",100,4,[[0, 1, 3, 7, 8, 9, 10, 11, 14, 15, 17, 18, 19, 21, 22, 23, 24, 25, 26, 28, 29, 30, 31, 32, 34, 36, 37, 40, 41, 42, 43, 44, 45, 46, 47, 48, 52, 53, 54, 55, 56, 57, 58, 59, 60, 62, 63, 64, 65, 66, 68, 69, 71, 72, 73, 78, 79, 81, 84, 85, 86, 90, 93, 94, 95, 98, 99, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 2, 4, 6, 7, 9, 10, 11, 12, 13, 15, 16, 19, 20, 21, 22, 23, 24, 25, 27, 28, 30, 31, 32, 35, 36, 37, 38, 40, 41, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 59, 60, 61, 64, 66, 67, 69, 70, 71, 75, 76, 78, 80, 81, 84, 85, 86, 87, 89, 92, 93, 95, 96, 97, 100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 15, 17, 19, 20, 22, 23, 26, 28, 29, 30, 32, 34, 35, 38, 40, 41, 45, 47, 49, 50, 53, 56, 57, 58, 59, 61, 62, 63, 64, 65, 66, 67, 68, 69, 71, 72, 73, 74, 76, 77, 79, 81, 82, 83, 85, 86, 87, 88, 89, 91, 92, 93, 94, 95, 96, 97, 98, 99, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [ 0, 1, 3, 4, 5, 7, 8, 9, 10, 11, 12, 14, 15, 19, 21, 22, 23, 24, 26, 27, 28, 32, 33, 34, 35, 39, 40, 42, 43, 46, 47, 51, 54, 55, 59, 60, 61, 63, 64, 67, 71, 72, 73, 74, 75, 76, 77, 78, 79, 82, 84, 85, 89, 90, 91, 92, 93, 94, 96, 97, 98, 99, 100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],[39],[1, 2, 5, 8, 10, 12, 13, 14, 15, 16, 17, 18, 19, 21, 24, 25, 28, 30, 31, 33, 35, 37, 41, 42, 43, 44, 49, 50, 52, 53, 57, 61, 63, 65, 66, 67, 69, 72, 73, 74, 75, 76, 77, 79, 80, 81, 82, 83, 85, 86, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 100])

```

5.

A pair of equivalent DFAs

# Non-equivalent DFAs

```

Automaton("det",100,4,[[0, 1, 2, 3, 5, 7, 9, 12, 13, 15, 20, 21, 23, 24, 25, 27, 29, 30, 31, 33, 34, 35, 36, 37, 40, 41, 42, 45, 46, 47, 48, 56, 57, 60, 62, 64, 65, 69, 70, 73, 74, 76, 80, 81, 82, 84, 86, 87, 88, 89, 90, 92, 93, 94, 95, 97, 98, 99, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 2, 3, 9, 11, 12, 13, 16, 19, 20, 21, 22, 23, 24, 25, 26, 27, 30, 36, 37, 38, 39, 40, 42, 47, 49, 52, 53, 54, 59, 60, 61, 62, 63, 64, 65, 68, 69, 71, 72, 75, 76, 78, 81, 82, 84, 86, 87, 88, 89, 90, 91, 92, 95, 96, 97, 98, 99, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [2, 3, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19, 21, 24, 25, 26, 27, 28, 29, 30, 33, 35, 36, 37, 38, 39, 41, 43, 46, 50, 51, 53, 55, 56, 58, 59, 60, 61, 62, 63, 64, 65, 67, 68, 70, 73, 74, 76, 77, 78, 80, 83, 86, 87, 89, 91, 92, 93, 95, 98, 100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 2, 3, 4, 6, 8, 13, 14, 15, 17, 19, 21, 22, 23, 25, 27, 28, 29, 30, 31, 32, 35, 36, 37, 40, 42, 46, 47, 48, 50, 51, 53, 54, 56, 58, 60, 61, 63, 64, 65, 66, 68, 70, 71, 72, 74, 75, 76, 79, 81, 82, 83, 84, 85, 86, 87, 89, 90, 91, 93, 94, 95, 96, 97, 99, 100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],[52],[1, 5, 6, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 23, 24, 25, 26, 27, 28, 29, 30, 32, 34, 35, 36, 37, 39, 40, 41, 42, 44, 46, 47, 49, 51, 52, 53, 54, 55, 60, 61, 62, 66, 67, 70, 72, 73, 74, 75, 76, 77, 79, 80, 81, 82, 83, 84, 86, 87, 89, 90, 92, 94, 96, 97, 98, 99, 100])

```

```
Automaton("det",100,4,[[0, 2, 3, 4, 6, 7, 10, 11, 14, 15, 16, 17, 19, 20, 21, 22, 24, 25, 26, 27, 28, 31, 34, 35, 36, 37, 38, 40, 42, 43, 44, 46, 48, 49, 51, 55, 56, 57, 58, 59, 61, 62, 63, 64, 69, 71, 72, 73, 76, 78, 79, 80, 83, 86, 87, 88, 89, 90, 91, 95, 96, 99, 100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 17, 18, 19, 22, 23, 24, 25, 26, 27, 29, 30, 31, 32, 34, 35, 36, 37, 40, 41, 42, 43, 45, 47, 48, 50, 51, 53, 56, 57, 59, 60, 62, 63, 64, 71, 72, 73, 75, 76, 77, 79, 80, 83, 85, 86, 87, 89, 90, 91, 92, 93, 96, 98, 99, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [ 0, 2, 3, 5, 6, 7, 8, 9, 10, 12, 13, 16, 18, 21, 23, 24, 26, 27, 28, 29, 30, 32, 34, 35, 36, 37, 39, 40, 41, 42, 45, 47, 48, 50, 51, 52, 53, 56, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 72, 73, 75, 76, 78, 79, 80, 82, 84, 85, 86, 89, 90, 93, 94, 97, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 2, 6, 7, 8, 9, 10, 11, 12, 13, 16, 18, 21, 22, 23, 24, 28, 30, 31, 32, 34, 36, 37, 38, 39, 40, 42, 44, 45, 47, 48, 51, 52, 53, 56, 57, 59, 60, 61, 62, 63, 64, 65, 67, 70, 74, 76, 83, 84, 86, 88, 90, 91, 93, 94, 95, 96, 97, 100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],[17],[1, 6, 7, 8, 9, 10, 11, 12, 13, 16, 18, 19, 22, 23, 27, 28, 29, 30, 32, 35, 36, 38, 40, 41, 42, 44, 46, 47, 48, 50, 51, 53, 54, 55, 62, 64, 66, 71, 72, 74, 75, 76, 79, 83, 86, 88, 89, 90, 91, 92, 94, 95, 96, 97, 98, 99, 100])

```

```
Automaton("det",100,4,[[2, 3, 6, 7, 8, 9, 10, 12, 14, 15, 16, 20, 21, 25, 26, 28, 29, 30, 32, 35, 36, 37, 40, 42, 43, 44, 46, 47, 48, 50, 53, 54, 55, 57, 58, 59, 62, 63, 64, 65, 67, 68, 69, 72, 73, 75, 77, 79, 81, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [2, 4, 5, 8, 13, 14, 15, 17, 18, 19, 20, 22, 23, 29, 30, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 45, 46, 47, 48, 49, 50, 51, 52, 54, 55, 56, 58, 59, 60, 63, 64, 65, 66, 67, 68, 70, 71, 72, 74, 75, 77, 78, 79, 82, 83, 84, 85, 86, 87, 93, 95, 96, 97, 98, 100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 3, 6, 7, 9, 10, 12, 13, 14, 15, 16, 17, 19, 20, 21, 23, 25, 27, 28, 30, 31, 32, 37, 38, 40, 41, 42, 45, 47, 49, 50, 51, 52, 56, 59, 61, 63, 64, 65, 68, 70, 72, 73, 74, 76, 77, 78, 80, 81, 85, 86, 87, 88, 92, 93, 94, 96, 98, 99, 100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17, 18, 20, 21, 22, 23, 24, 26, 27, 28, 30, 31, 33, 34, 35, 36, 37, 38, 39, 40, 42, 43, 44, 45, 48, 50, 51, 52, 53, 54, 55, 56, 58, 59, 60, 62, 64, 65, 66, 68, 69, 70, 71, 72, 74, 75, 76, 77, 79, 84, 86, 91, 92, 93, 96, 97, 100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],[46],[1, 2, 7, 8, 10, 12, 13, 15, 17, 18, 20, 22, 23, 24, 25, 27, 28, 29, 30, 32, 33, 35, 36, 37, 39, 41, 42, 44, 45, 47, 49, 50, 51, 52, 54, 55, 57, 59, 61, 63, 65, 66, 67, 68, 69, 70, 71, 73, 75, 76, 77, 79, 80, 81, 82, 85, 86, 88, 91, 92, 93, 94, 95, 96, 97, 98])

```

```
Automaton("det",100,4,[[0, 1, 4, 5, 7, 8, 9, 10, 11, 12, 15, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 33, 35, 36, 37, 39, 43, 44, 45, 46, 49, 50, 51, 52, 54, 55, 56, 57, 58, 59, 62, 63, 67, 68, 70, 72, 73, 74, 76, 77, 78, 81, 82, 83, 85, 87, 93, 94, 95, 96, 97, 98, 99, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 3, 4, 5, 8, 10, 12, 15, 16, 17, 18, 19, 20, 21, 27, 29, 30, 31, 32, 34, 35, 36, 39, 40, 42, 45, 46, 47, 49, 50, 51, 52, 55, 58, 59, 60, 61, 62, 63, 64, 66, 67, 70, 71, 72, 73, 74, 75, 77, 79, 80, 81, 82, 83, 84, 86, 87, 88, 89, 92, 94, 96, 98, 99, 100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 2, 3, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 20, 21, 23, 30, 31, 33, 34, 35, 37, 38, 39, 42, 43, 44, 46, 47, 48, 50, 52, 53, 54, 55, 56, 58, 59, 60, 61, 63, 64, 65, 66, 67, 70, 71, 75, 76, 77, 80, 82, 83, 84, 85, 86, 87, 88, 89, 91, 92, 94, 98, 100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 3, 4, 7, 8, 9, 10, 11, 12, 14, 16, 17, 18, 19, 20, 21, 22, 24, 26, 27, 28, 29, 31, 33, 34, 35, 37, 38, 40, 41, 43, 49, 50, 51, 52, 53, 54, 55, 57, 58, 59, 62, 64, 65, 66, 67, 68, 69, 71, 72, 75, 76, 77, 80, 81, 82, 83, 86, 87, 88, 91, 93, 94, 95, 96, 97, 98, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],[45],[2, 4, 6, 7, 11, 12, 14, 15, 16, 17, 19, 20, 24, 25, 27, 28, 29, 30, 37, 39, 41, 42, 44, 45, 46, 47, 48, 49, 50, 51, 52, 55, 56, 57, 58, 59, 61, 62, 63, 64, 65, 67, 71, 72, 76, 81, 82, 83, 84, 85, 86, 87, 88, 91, 92, 94, 95, 99, 100])

```

# Score

This question is and . Your code must be able to run all the test cases in less than a minute on TIO. Your code only needs to output something Truthy or Falsey depending on whether the two DFAs are equivalent or not.

\[GAP has a library function for this but I am not aware of any other languages that do. Please feel free to use whatever your language does provide however.\]

# Answer
# K (ngn/k), 101 bytes

```
{a:&,/~=\:/+/'x[2]=\:'!'#'*'*x:+@[;0;0,']'x;n:#**|*x;~#a^a^{?y@<y:y,/x@\:y}[,/'+\:'/(n;1)**x]/,n/x 1}

```

Try it online!

the argument `x` is a pair of dfa-s.

a dfa is `(TransitionTable;InitialState;FinalStates)`.

we prepend 0 to all rows in both transition tables. this way we can use 0-indexing, and state0 can act as a tarpit state to handle "no transition" transitions.

consider a new dfa whose states are the cartesian product of those of dfa0 and dfa1. when state `i` from dfa0 is paired with state `j` from dfa1, the resulting state is labelled `(i*n)+j` where `n` is the number of states in dfa1. `a` is the list of states in the new dfa for which one of the original states was final and the other was not.

we combine the initial states of dfa0 and dfa1 using the formula `(i*n)+j`. starting there, we compute the set of states in the new automaton that are reachable through its transitions. we test if that set is disjoint from `a` and return a boolean result.
> 8 votes

# Answer
# Prolog (SWI), 431 program + 5 interpreter = 436 bytes

```
m-->member.
g(A):-read_string(user_input,"\n",[],_,S),term_string(A,S).
f(I,T,S,R):-select(S,T,R),m(I,S),!;S=[I],R=T.
x(S,R)-->[N],{nth1(S,R,N);S=0,N=0}.
x(A,B,C,D)-->x(A,C),x(B,D).
c(_,_,[]).
c(M,E,[A,B|R]):-M=[S,T,C,D],(m(A,C)->m(B,D);\+m(B,D)),f(A,E,X,F),plus(B,N,0),(m(N,X)->c(M,E,R);f(N,F,Y,G),union(X,Y,Z),(P=..[x,A,B]),foldl(P,S,T,Q,R),c(M,[Z|G],Q)).
r:-g(a(A,[B],C)),g(a(D,[E],F)),(c([A,D,C,F],[],[B,E])->R=y;R=n),print(R).

```

Try it online!

Pass arguments `-t r` to the interpreter to make `r` the top-level goal.

Expects the DFAs on standard input, one per line, but with the initial `'Automaton("det", Size, Alphabet'` shortened to just `'a('`. Outputs a single character to standard output: `y` if the DFAs are equivalent, or `n` if they are not.

A more legible version, with comments:

```
/* Parse a line from stdin as the term A.
   For this program, the term is expected to be a
   Deterministic Finite Automaton in the form
     a(TransitionTable, [Initial], Accepting). */
get(A) :- read_string(user_input, "\n", [], _, S), term_string(A,S).

/* Find the Set in SetOfSets which contains I, and remove it from the
   larger SetOfSets.
   Or if no such Set exists, use the one-element Set [I] instead, and
   leave SetOfSets unchanged. */
find(I, SetOfSets, Set, Rest) :-
  select(Set, SetOfSets, Rest), member(I, Set), !.
find(I, SetOfSets, [I], SetOfSets).

/* Look up the next state from a row of a transition table, or
   two next states from corresponding rows.
   A zero is the failure state and always stays at zero without lookup. */
next_state(0,_) --> [0].
next_state(State,Row) --> [Next], {nth1(State,Row,Next)}.
next_state(State1,State2,Row1,Row2) -->
    next_state(State1,Row1), next_state(State2,Row2).

/* Check if two DFAs are equivalent!

   Equiv is a set of sets of positive state indices from DFA1, negative
   state indices from DFA2, and 0 for a common failure state. After the
   algorithm has examined a pair of states, it makes sure one element
   in Equiv contains both those states for future iterations. All such
   states in one set are tentatively presumed to be equivalent.

   Require is an even-length list. Every pair of elements is a state from
   DFA1 followed by a state from DFA2, and it must be shown that the pair
   of states is equivalent:
     1. If one state is an accept state and the other is not, the DFAs
        are NOT equivalent.
     2. Otherwise, if both states are in the same member of Equiv, no
        further processing is needed for the current pair, since those
        states or related states were already seen.
     3. Otherwise, for each letter in the common alphabet, for equivalent
        DFAs it is necessary that the next states for the two DFAs are
        equivalent.
        3a. Add these pairs of next states to Require for the next iteration.
        3b. Merge sets containing the current states into a common set
            within Equiv for the next iteration.
     4. Repeat until an Accept mismatch is found or until Require is empty.
        If Require is empty, the DFAs are equivalent.
*/
check(_,_,[]).
check(Params,Equiv,[State1,State2|Require]) :-
  /* format("Equiv: ~p~nRequire: ~p~n", [Equiv, [State1,State2|Require]]), */
  Params = [Trans1, Trans2, Accept1, Accept2],
  (member(State1,Accept1) -> member(State2,Accept2) ; \+member(State2,Accept2)),
  find(State1, Equiv, Set1, Equiv2), plus(State2, NegState2, 0),
  (member(NegState2,Set1) -> check(Params, Equiv, Require);
   find(NegState2, Equiv2, Set2, Equiv3), union(Set1, Set2, SetU),
   (P =.. [next_state, State1, State2]),
    foldl(P, Trans1, Trans2, RequireMore, Require),
   check(Params, [SetU|Equiv3], RequireMore)).

/* Top-level goal. Parse two DFAs from standard input, and check
   for equivalence. */
run :- get(a(Transitions1, [Init1], Accept1)), get(a(Transitions2, [Init2], Accept2)),
  (check([Transitions1, Transitions2, Accept1, Accept2], [], [Init1, Init2])
   -> R=y; R=n), print(R).

```

Try it online!
> 1 votes

---
Tags: code-golf, decision-problem, restricted-time
---


title: Is it a Self-divisor?

text:
# Question
Title: Is it a Self-divisor?
# Task

Write a function or program that takes `n` as a parameter and prints the first `n` self-divisors.

# Definition of Self-divisor

A positive integer is called a “self-divisor” if every decimal digit of the number is a divisor of the number, that is, the number is evenly divisible by each and every one of its digits.

### Example

For example, the number 128 is a self-divisor because it is evenly divisible by 1, 2, and 8. However, 26 is not a self-divisor because it is not evenly divisible by the digit 6. Note that 0 is not considered to be a divisor of any number, so any number containing a 0 digit is NOT a self-divisor. There are infinitely many self-divisors.

# Scoring

This is code-golf, so the shortest answer in bytes wins

# Answer
> 0 votes
# 05AB1E, 16 bytes

05AB1E probably has some sort of slice, but I failed to find it.

```
∞ʒDSÖß}ʒ0å_}ηs<è

```

Try it online!

# Explanation

```
∞                [1, 2, 3, ...]
 ʒ               Filter all that satisfies:
  DS                 its DigitS
    Ö                is divisible
     ß}              ßy the original number.
       ʒ         Filter out ^ that satisfies:
        0å_}         0 is å digit of the output.
            ηs<è Trunctuatè by the input.

```

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


# Question
Title: How quickly can you convert an NFA to a DFA?
# Convert NFA to DFA as quickly as possible.

**Input**

Your input will be an NFA. In order to be able to test your code, it needs to be able to handle an NFA in the following format. This is taken directly from GAP (and slightly simplified).

```
Automaton( Type, Size, Alphabet, TransitionTable, Initial, Accepting )

```

For the input, Type will always be "nondet". Size is a positive integer representing the number of states of the automaton. Alphabet is the number of letters of the alphabet. TransitionTable is the transition matrix. The entries are lists of non-negative integers not greater than the size of the automaton are also allowed. Initial and Accepting are, respectively, the lists of initial and accepting states.

Example input:

```
Automaton("nondet", 4, 2, [[[], [2], [3], [1, 2, 3, 4], [2, 4]],
                                [[], [1, 3, 4], [1], [2, 4]]], [1], [2, 3])

```

This is slightly easier to read as a transition table.

```
   |  1    2             3                4
--------------------------------------------------
 a |      [ 2 ]         [ 1, 2, 3, 4 ]   [ 2, 4 ]
 b |      [ 1, 3, 4 ]   [ 1 ]            [ 2, 4 ]
Initial state:    [ 1 ]
Accepting states: [ 2, 3 ]

```

**Output**

Your output must be a DFA that is **equivalent** to the input NFA. There is no need for your DFA to be minimal. For the output, Type will always be "det". Size is a positive integer representing the number of states of the automaton. Alphabet is the number of letters of the alphabet. TransitionTable is the transition matrix. The entries are non-negative integers not greater than the size of the automaton. The states should be labelled by consecutive integers. Initial and Accepting are, respectively, the lists of initial and accepting states. In the case of the example above, this would be:

```
Automaton("det", 2, 2, [[2, 2], [2, 2]], [1], [])

```

As a transition table this is:

```
   |  1  2
-----------
 a |  2  2
 b |  2  2
Initial state:   [ 1 ]
Accepting state: [  ]

```

(It is now clear this is a DFA that will not accept any input strings.)

# Test cases:

1. Input:

```
Automaton("nondet",2,4,[[[1], [2]], [[2], []], [[2], []] , [[1], [2]]],[1],[1, 2])

```

As a transition matrix:

```
   |  1       2
-------------------
 a | [ 1 ]   [ 2 ]
 b | [ 2 ]
 c | [ 2 ]
 d | [ 1 ]   [ 2 ]
Initial state:    [ 1 ]
Accepting states: [ 1, 2 ]

```

Here is the diagram of the NFA.

Output:

```
Automaton("det",3, 4,[[1, 2, 3], [2, 3, 3], [2, 3, 3], [1, 2, 3]], [1],[1, 2])

```

As a transition matrix:

```
   |  1  2  3
--------------
 a |  1  2  3
 b |  2  3  3
 c |  2  3  3
 d |  1  2  3
Initial state:    [ 1 ]
Accepting states: [ 1, 2 ]

```

Here is the diagram of the DFA.

2. Input:

```
Automaton("nondet",7,4,[[[1, 3, 4, 5], [2], [3], [3, 4], [3, 5], [], []], [[2, 3, 4, 7], [3], [], [], [3, 7], [3, 4], []], [[2, 3, 5, 6], [3], [], [3, 6], [], [], [3, 5]], [[1, 3, 6, 7], [2], [3], [], [], [3, 6], [3, 7]]],[1],[1, 2, 3, 4, 5, 6, 7])

```

Output:

```
Automaton("det",16,4,[[1, 2, 15, 15, 5, 6, 7, 7, 6, 2, 16, 12, 12, 16, 15, 16], [1, 3, 1, 7, 9, 15, 1, 1, 15, 8, 7, 3, 8, 15, 1, 15], [1, 1, 2, 1, 13, 4, 4, 10, 10, 1, 15, 15, 15, 2, 1, 15], [1, 15, 3, 4, 5, 16, 15, 3, 14, 4, 11, 16, 11, 14, 15, 16]],[5],[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16])

```
3. Input:

```
Automaton("nondet",12, 4,[[[1, 3, 5, 6], [2, 4, 7, 8], [3], [6], [3, 5], [3, 6], [4, 7], [4, 8], [4, 7], [4, 8], [], []], [[2, 3, 5, 10], [3, 4, 7, 12], [6], [], [4, 7], [3, 10], [], [4, 12], [3, 5], [4, 12], [4, 7], []], [[2, 3, 6, 9], [3, 4, 8, 11], [6], [], [3, 9], [4, 8], [4, 11], [], [4, 11], [3, 6], [], [4, 8 ]], [[1, 3, 9, 10], [2, 4, 11, 12], [3], [6], [4, 11], [4, 12], [], [], [3, 9], [3, 10], [4, 11], [4, 12]]],[1],[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12])

```

Output:

```
Automaton("det",39,4,[ [ 1, 19, 8, 5, 10, 10, 9, 25, 10, 10, 25, 10, 13, 35, 15, 20, 15, 19, 19, 21, 21, 10, 13, 19, 25, 25, 25, 36, 35, 10, 35, 35, 10, 10, 35, 36, 25, 19, 25 ], [ 1, 23, 1, 3, 6, 39, 39, 7, 39, 12, 8, 12, 32, 23, 21, 36, 16, 36, 32, 36, 32, 12, 32, 13, 22, 29, 32, 23, 39, 32, 39, 12, 32, 31, 12, 22, 22, 23, 7 ], [ 1, 30, 4, 1, 4, 10, 25, 4, 8, 5, 5, 10, 14, 34, 2, 14, 38, 30, 30, 14, 14, 10, 14, 30, 5, 4, 5, 34, 27, 5, 30, 30, 10, 4, 34, 34, 5, 30, 4 ], [ 1, 2, 39, 8, 39, 12, 7, 3, 25, 37, 37, 12, 27, 28, 15, 18, 15, 19, 19, 19, 19, 6, 33, 2, 11, 26, 27, 28, 22, 27, 12, 12, 33, 26, 37, 37, 37, 24, 39 ] ],[ 17 ],[ 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39 ])

```
4. Input:

```
Automaton("nondet",25,4,[[[1, 3, 6, 7], [2, 4, 8, 9], [3, 5, 10, 11], [4], [5], [3, 5, 6, 10, 18], [3, 5, 7, 11, 19], [4, 8], [4, 9], [5, 10], [5, 11], [4, 5, 8, 10, 22], [4, 5, 9, 11, 23], [5, 10], [5, 11], [], [], [5, 10, 18], [5, 11, 19], [5, 10, 22], [5, 11, 23], [], [], [], []], [[2, 3, 6, 13], [3, 4, 8, 15], [4, 5, 10, 17], [5], [], [4, 5, 8, 10, 18], [3, 5, 13, 17, 21], [5, 10], [4, 15], [], [5, 17], [3, 5, 6, 10, 22], [4, 5, 15, 17, 25], [4, 8], [5, 17], [5, 10], [], [], [5, 17, 21], [], [5, 17, 25], [5, 10, 18], [], [5, 10, 22], []], [[2, 3, 7, 12], [3, 4, 9, 14], [4, 5, 11, 16], [5], [], [3, 5, 12, 16, 20], [4, 5, 9, 11, 19], [4, 14], [5, 11], [5, 16], [], [4, 5, 14, 16, 24], [3, 5, 7, 11, 23], [5, 16], [4, 9], [], [5, 11], [5, 16, 20], [], [5, 16, 24], [], [], [5, 11, 19], [], [5, 11, 23]], [[1, 3, 12, 13], [2, 4, 14, 15], [3, 5, 16, 17], [4], [5], [4, 5, 14, 16, 20], [4, 5, 15, 17, 21], [5, 16], [5, 17], [], [], [3, 5, 12, 16, 24], [3, 5, 13, 17, 25], [4, 14], [4, 15], [5, 16], [5, 17], [], [], [], [], [5, 16, 20], [5, 17, 21], [5, 16, 24], [5, 17, 25]]],[1],[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25 ])

```
5. Input:

```
Automaton("nondet",38,4,[[[1, 3, 7, 8], [2, 4, 9, 10], [3, 5, 11, 12], [4, 6, 13, 14], [7], [8], [3, 5, 7, 11, 23], [3, 5, 8, 12, 24], [4, 6, 9, 13, 25], [4, 6, 10, 14, 26], [5, 11], [5, 12], [6, 13], [6, 14], [4, 5, 9, 11, 31], [4, 5, 10, 12, 32], [5, 6, 11, 13, 33], [5, 6, 12, 14, 34], [6, 13], [6, 14], [], [], [5, 11, 23], [5, 12, 24], [6, 13, 25], [6, 14, 26], [5, 11, 31], [5, 12, 32], [6, 13, 33], [6, 14, 34], [6, 13, 25], [6, 14, 26], [], [], [6, 13, 33], [6, 14, 34], [], []], [[2, 3, 7, 16], [3, 4, 9, 18], [4, 5, 11, 20], [5, 6, 13, 22], [8], [], [4, 5, 9, 11, 23], [3, 5, 16, 20, 28], [5, 6, 11, 13, 25], [4, 6, 18, 22, 30], [6, 13], [5, 20], [], [6, 22], [3, 5, 7, 11, 31], [4, 5, 18, 20, 36], [4, 6, 9, 13, 33], [5, 6, 20, 22, 38], [5, 11], [6, 22], [6, 13], [], [6, 13, 25], [5, 20, 28], [], [6, 22, 30], [6, 13, 33], [5, 20, 36], [], [6, 22, 38], [5, 11, 23], [6, 22, 30], [6, 13, 25], [], [5, 11, 31], [6, 22, 38], [6, 13, 33], []], [[2, 3, 8, 15], [3, 4, 10, 17], [4, 5, 12, 19], [5, 6, 14, 21], [8], [], [3, 5, 15, 19, 27], [4, 5, 10, 12, 24], [4, 6, 17, 21, 29], [5, 6, 12, 14, 26], [5, 19], [6, 14], [6, 21], [], [4, 5, 17, 19, 35], [3, 5, 8, 12, 32], [5, 6, 19, 21, 37], [4, 6, 10, 14, 34], [6, 21], [5, 12], [], [6, 14], [5, 19, 27], [6, 14, 26], [6, 21, 29], [], [5, 19, 35], [6, 14, 34], [6, 21, 37], [], [6, 21, 29], [5, 12, 24], [], [6, 14, 26 ], [6, 21, 37], [5, 12, 32], [], [6, 14, 34]], [[1, 3, 15, 16], [2, 4, 17, 18], [3, 5, 19, 20], [4, 6, 21, 22], [7], [8], [ 4, 5, 17, 19, 27], [4, 5, 18, 20, 28], [5, 6, 19, 21, 29], [5, 6, 20, 22, 30], [6, 21], [6, 22], [], [], [3, 5, 15, 19, 35], [3, 5, 16, 20, 36], [4, 6, 17, 21, 37], [4, 6, 18, 22, 38], [5, 19], [5, 20], [6, 21], [6, 22], [6, 21, 29], [6, 22, 30], [], [], [6, 21, 37], [6, 22, 38], [], [], [5, 19, 27], [5, 20, 28], [6, 21, 29], [6, 22, 30], [5, 19, 35], [5, 20, 36], [6, 21, 37], [6, 22, 38]]],[1],[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38])

```
6. Input:

```
Automaton("nondet",67,4,[[[1, 3, 8, 9], [2, 4, 10, 11], [3, 5, 12, 13], [4, 6, 14, 15], [5, 7, 16, 17], [8], [8], [3, 5, 8, 12, 28], [3, 5, 9, 13, 29], [4, 6, 10, 14, 30], [4, 6, 11, 15, 31], [5, 7, 12, 16, 32], [5, 7, 13, 17, 33], [6, 14], [6, 15], [ 7, 16], [7, 17], [4, 5, 10, 12, 40], [4, 5, 11, 13, 41], [5, 6, 12, 14, 42], [5, 6, 13, 15, 43], [6, 7, 14, 16, 44], [6, 7, 15, 17, 45], [7, 16], [7, 17], [], [], [5, 7, 12, 16, 28, 32, 52], [5, 7, 13, 17, 29, 33, 53], [6, 14, 30], [6, 15, 31], [7, 16, 32], [7, 17, 33], [5, 7, 12, 16, 40, 44, 56], [5, 7, 13, 17, 41, 45, 57], [6, 14, 42], [6, 15, 43], [7, 16, 44], [7, 17, 45], [6, 7, 14, 16, 30, 32, 60], [6, 7, 15, 17, 31, 33, 61], [7, 16, 32], [7, 17, 33], [], [], [6, 7, 14, 16, 42, 44, 64], [6, 7, 15, 17, 43, 45, 65], [7, 16, 44], [7, 17, 45], [], [], [7, 16, 32, 52], [7, 17, 33, 53], [7, 16, 44, 56], [7, 17, 45, 57], [7, 16, 32, 60], [7, 17, 33, 61], [7, 16, 44, 64], [7, 17, 45, 65], [], [], [], [], [], [], [], []], [[2, 3, 8, 19], [3, 4, 10, 21], [4, 5, 12, 23], [5, 6, 14, 25], [6, 7, 16, 27], [8], [], [4, 5, 10, 12, 28], [3, 5, 19, 23, 35], [5, 6, 12, 14, 30], [4, 6, 21, 25, 37], [6, 7, 14, 16, 32], [5, 7, 23, 27, 39], [7, 16], [6, 25], [], [7, 27], [3, 5, 8, 12, 40], [4, 5, 21, 23, 47], [4, 6, 10, 14, 42], [5, 6, 23, 25, 49], [5, 7, 12, 16, 44], [6, 7, 25, 27, 51], [6, 14], [7, 27], [7, 16], [], [6, 7, 14, 16, 30, 32, 52], [5, 7, 23, 27, 35, 39, 55], [7, 16, 32], [6, 25, 37], [], [7, 27, 39], [6, 7, 14, 16, 42, 44, 56], [5, 7, 23, 27, 47, 51, 59], [7, 16, 44], [6, 25, 49], [], [7, 27, 51], [5, 7, 12, 16, 28, 32, 60], [6, 7, 25, 27, 37, 39, 63], [6, 14, 30], [7, 27, 39], [7, 16, 32], [], [5, 7, 12, 16, 40, 44, 64], [6, 7, 25, 27, 49, 51, 67], [6, 14, 42], [7, 27, 51], [7, 16, 44], [], [], [7, 27, 39, 55], [], [7, 27, 51, 59], [], [7, 27, 39, 63], [], [7, 27, 51, 67], [7, 16, 32, 52], [], [7, 16, 44, 56], [], [7, 16, 32, 60], [], [7, 16, 44, 64], []], [[2, 3, 9, 18], [3, 4, 11, 20], [4, 5, 13, 22], [5, 6, 15, 24], [6, 7, 17, 26], [8], [], [3, 5, 18, 22, 34], [4, 5, 11, 13, 29], [4, 6, 20, 24, 36], [5, 6, 13, 15, 31], [5, 7, 22, 26, 38], [6, 7, 15, 17, 33], [6, 24], [7, 17], [7, 26 ], [], [4, 5, 20, 22, 46], [3, 5, 9, 13, 41], [5, 6, 22, 24, 48], [4, 6, 11, 15, 43], [6, 7, 24, 26, 50], [5, 7, 13, 17, 45], [7, 26], [6, 15], [], [7, 17], [5, 7, 22, 26, 34, 38, 54], [6, 7, 15, 17, 31, 33, 53], [6, 24, 36], [7, 17, 33], [7, 26, 38], [], [ 5, 7, 22, 26, 46, 50, 58], [6, 7, 15, 17, 43, 45, 57], [6, 24, 48], [7, 17, 45], [7, 26, 50], [], [6, 7, 24, 26, 36, 38, 62], [5, 7, 13, 17, 29, 33, 61], [7, 26, 38], [6, 15, 31], [], [7, 17, 33], [6, 7, 24, 26, 48, 50, 66], [5, 7, 13, 17, 41, 45, 65], [7, 26, 50], [6, 15, 43], [], [7, 17, 45], [7, 26, 38, 54], [], [7, 26, 50, 58], [], [7, 26, 38, 62], [], [7, 26, 50, 66], [], [], [7, 17, 33, 53], [], [7, 17, 45, 57], [], [7, 17, 33, 61], [], [7, 17, 45, 65]], [[1, 3, 18, 19], [2, 4, 20, 21], [3, 5, 22, 23 ], [4, 6, 24, 25], [5, 7, 26, 27], [8], [8], [4, 5, 20, 22, 34], [4, 5, 21, 23, 35], [5, 6, 22, 24, 36], [5, 6, 23, 25, 37], [6, 7, 24, 26, 38], [6, 7, 25, 27, 39], [7, 26], [7, 27], [], [], [3, 5, 18, 22, 46], [3, 5, 19, 23, 47], [4, 6, 20, 24, 48], [4, 6, 21, 25, 49], [5, 7, 22, 26, 50], [5, 7, 23, 27, 51], [6, 24], [6, 25], [7, 26], [7, 27], [6, 7, 24, 26, 36, 38, 54], [6, 7, 25, 27, 37, 39, 55], [7, 26, 38], [7, 27, 39], [], [], [6, 7, 24, 26, 48, 50, 58], [6, 7, 25, 27, 49, 51, 59], [7, 26, 50], [7, 27, 51], [], [], [5, 7, 22, 26, 34, 38, 62], [5, 7, 23, 27, 35, 39, 63], [6, 24, 36], [6, 25, 37], [7, 26, 38], [7, 27, 39], [5, 7, 22, 26, 46, 50, 66], [5, 7, 23, 27, 47, 51, 67], [6, 24, 48], [6, 25, 49], [7, 26, 50], [7, 27, 51], [], [], [], [], [], [], [], [], [7, 26, 38, 54], [7, 27, 39, 55], [7, 26, 50, 58], [7, 27, 51, 59], [7, 26, 38, 62], [7, 27, 39, 63], [7, 26, 50, 66], [7, 27, 51, 67]]],[1],[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67])

```
7. Input:

```
Automaton("nondet",96,4,[[[1, 3, 9, 10], [2, 4, 11, 12], [3, 5, 13, 14], [4, 6, 15, 16], [5, 7, 17, 18], [6, 8, 19, 20], [7 ], [8], [3, 5, 9, 13, 33], [3, 5, 10, 14, 34], [4, 6, 11, 15, 35], [4, 6, 12, 16, 36], [5, 7, 13, 17, 37], [5, 7, 14, 18, 38], [6, 8, 15, 19, 39], [6, 8, 16, 20, 40], [7, 17], [7, 18], [8, 19], [8, 20], [4, 5, 11, 13, 49], [4, 5, 12, 14, 50], [5, 6, 13, 15, 51], [5, 6, 14, 16, 52], [6, 7, 15, 17, 53], [6, 7, 16, 18, 54], [7, 8, 17, 19, 55], [7, 8, 18, 20, 56], [8, 19], [8, 20], [], [], [5, 7, 13, 17, 33, 37, 65], [5, 7, 14, 18, 34, 38, 66], [6, 8, 15, 19, 35, 39, 67], [6, 8, 16, 20, 36, 40, 68], [7, 17, 37], [7, 18, 38], [8, 19, 39], [8, 20, 40], [5, 7, 13, 17, 49, 53, 73], [5, 7, 14, 18, 50, 54, 74], [6, 8, 15, 19, 51, 55, 75], [6, 8, 16, 20, 52, 56, 76], [7, 17, 53], [7, 18, 54], [8, 19, 55], [8, 20, 56], [6, 7, 15, 17, 35, 37, 81], [6, 7, 16, 18, 36, 38, 82], [7, 8, 17, 19, 37, 39, 83], [7, 8, 18, 20, 38, 40, 84], [8, 19, 39], [8, 20, 40], [], [], [6, 7, 15, 17, 51, 53, 89], [6, 7, 16, 18, 52, 54, 90], [7, 8, 17, 19, 53, 55, 91], [7, 8, 18, 20, 54, 56, 92], [8, 19, 55], [8, 20, 56], [], [], [7, 17, 37, 65], [7, 18, 38, 66 ], [8, 19, 39, 67], [8, 20, 40, 68], [7, 17, 53, 73], [7, 18, 54, 74], [8, 19, 55, 75], [8, 20, 56, 76], [7, 17, 37, 81], [7, 18, 38, 82], [8, 19, 39, 83], [8, 20, 40, 84], [7, 17, 53, 89], [7, 18, 54, 90], [8, 19, 55, 91], [8, 20, 56, 92], [8, 19, 39, 67], [8, 20, 40, 68], [], [], [8, 19, 55, 75], [8, 20, 56, 76], [], [], [8, 19, 39, 83], [8, 20, 40, 84], [], [], [8, 19, 55, 91], [8, 20, 56, 92], [], []], [[2, 3, 9, 22], [3, 4, 11, 24], [4, 5, 13, 26], [5, 6, 15, 28], [6, 7, 17, 30], [7, 8, 19, 32], [8 ], [], [4, 5, 11, 13, 33], [3, 5, 22, 26, 42], [5, 6, 13, 15, 35], [4, 6, 24, 28, 44], [6, 7, 15, 17, 37], [5, 7, 26, 30, 46], [7, 8, 17, 19, 39], [6, 8, 28, 32, 48], [8, 19], [7, 30], [], [8, 32], [3, 5, 9, 13, 49], [4, 5, 24, 26, 58], [4, 6, 11, 15, 51], [ 5, 6, 26, 28, 60], [5, 7, 13, 17, 53], [6, 7, 28, 30, 62], [6, 8, 15, 19, 55], [7, 8, 30, 32, 64], [7, 17], [8, 32], [8, 19], [], [6, 7, 15, 17, 35, 37, 65], [5, 7, 26, 30, 42, 46, 70], [7, 8, 17, 19, 37, 39, 67], [6, 8, 28, 32, 44, 48, 72], [8, 19, 39], [7, 30, 46], [], [8, 32, 48], [6, 7, 15, 17, 51, 53, 73], [5, 7, 26, 30, 58, 62, 78], [7, 8, 17, 19, 53, 55, 75], [6, 8, 28, 32, 60, 64, 80], [8, 19, 55], [7, 30, 62], [], [8, 32, 64], [5, 7, 13, 17, 33, 37, 81], [6, 7, 28, 30, 44, 46, 86], [6, 8, 15, 19, 35, 39, 83], [7, 8, 30, 32, 46, 48, 88], [7, 17, 37], [8, 32, 48], [8, 19, 39], [], [5, 7, 13, 17, 49, 53, 89], [6, 7, 28, 30, 60, 62, 94], [6, 8, 15, 19, 51, 55, 91], [7, 8, 30, 32, 62, 64, 96], [7, 17, 53], [8, 32, 64], [8, 19, 55], [], [8, 19, 39, 67], [7, 30, 46, 70], [], [8, 32, 48, 72], [8, 19, 55, 75], [7, 30, 62, 78], [], [8, 32, 64, 80], [8, 19, 39, 83], [7, 30, 46, 86], [], [8, 32, 48, 88], [8, 19, 55, 91], [7, 30, 62, 94], [], [8, 32, 64, 96], [7, 17, 37, 65], [8, 32, 48, 72], [8, 19, 39, 67], [], [7, 17, 53, 73], [8, 32, 64, 80], [8, 19, 55, 75], [], [7, 17, 37, 81], [8, 32, 48, 88], [8, 19, 39, 83], [], [7, 17, 53, 89], [8, 32, 64, 96 ], [8, 19, 55, 91], []], [[2, 3, 10, 21], [3, 4, 12, 23], [4, 5, 14, 25], [5, 6, 16, 27], [6, 7, 18, 29], [7, 8, 20, 31], [8], [], [3, 5, 21, 25, 41], [4, 5, 12, 14, 34], [4, 6, 23, 27, 43], [5, 6, 14, 16, 36], [5, 7, 25, 29, 45], [6, 7, 16, 18, 38], [6, 8, 27, 31, 47], [7, 8, 18, 20, 40], [7, 29], [8, 20], [8, 31], [], [4, 5, 23, 25, 57], [3, 5, 10, 14, 50], [5, 6, 25, 27, 59], [ 4, 6, 12, 16, 52], [6, 7, 27, 29, 61], [5, 7, 14, 18, 54], [7, 8, 29, 31, 63], [6, 8, 16, 20, 56], [8, 31], [7, 18], [], [8, 20 ], [5, 7, 25, 29, 41, 45, 69], [6, 7, 16, 18, 36, 38, 66], [6, 8, 27, 31, 43, 47, 71], [7, 8, 18, 20, 38, 40, 68], [7, 29, 45], [8, 20, 40], [8, 31, 47], [], [5, 7, 25, 29, 57, 61, 77], [6, 7, 16, 18, 52, 54, 74], [6, 8, 27, 31, 59, 63, 79], [7, 8, 18, 20, 54, 56, 76], [7, 29, 61], [8, 20, 56], [8, 31, 63], [], [6, 7, 27, 29, 43, 45, 85], [5, 7, 14, 18, 34, 38, 82], [7, 8, 29, 31, 45, 47, 87], [6, 8, 16, 20, 36, 40, 84], [8, 31, 47], [7, 18, 38], [], [8, 20, 40], [6, 7, 27, 29, 59, 61, 93], [5, 7, 14, 18, 50, 54, 90], [7, 8, 29, 31, 61, 63, 95], [6, 8, 16, 20, 52, 56, 92], [8, 31, 63], [7, 18, 54], [], [8, 20, 56], [7, 29, 45, 69], [8, 20, 40, 68], [8, 31, 47, 71], [], [7, 29, 61, 77], [8, 20, 56, 76], [8, 31, 63, 79], [], [7, 29, 45, 85], [8, 20, 40, 84], [8, 31, 47, 87], [], [7, 29, 61, 93], [8, 20, 56, 92], [8, 31, 63, 95], [], [8, 31, 47, 71], [7, 18, 38, 66], [], [8, 20, 40, 68], [8, 31, 63, 79], [7, 18, 54, 74], [], [8, 20, 56, 76], [8, 31, 47, 87], [7, 18, 38, 82], [], [8, 20, 40, 84], [8, 31, 63, 95], [7, 18, 54, 90 ], [], [8, 20, 56, 92]], [[1, 3, 21, 22], [2, 4, 23, 24], [3, 5, 25, 26], [4, 6, 27, 28], [5, 7, 29, 30], [6, 8, 31, 32], [8], [8], [4, 5, 23, 25, 41], [4, 5, 24, 26, 42], [5, 6, 25, 27, 43], [5, 6, 26, 28, 44], [6, 7, 27, 29, 45], [6, 7, 28, 30, 46], [7, 8, 29, 31, 47], [7, 8, 30, 32, 48], [8, 31], [8, 32], [], [], [3, 5, 21, 25, 57], [3, 5, 22, 26, 58], [4, 6, 23, 27, 59], [4, 6, 24, 28, 60], [5, 7, 25, 29, 61], [5, 7, 26, 30, 62], [6, 8, 27, 31, 63], [6, 8, 28, 32, 64], [7, 29], [7, 30], [8, 31], [8, 32], [6, 7, 27, 29, 43, 45, 69], [6, 7, 28, 30, 44, 46, 70], [7, 8, 29, 31, 45, 47, 71], [7, 8, 30, 32, 46, 48, 72], [8, 31, 47], [8, 32, 48], [], [], [6, 7, 27, 29, 59, 61, 77], [6, 7, 28, 30, 60, 62, 78], [7, 8, 29, 31, 61, 63, 79], [7, 8, 30, 32, 62, 64, 80], [8, 31, 63], [8, 32, 64], [], [], [5, 7, 25, 29, 41, 45, 85], [5, 7, 26, 30, 42, 46, 86], [6, 8, 27, 31, 43, 47, 87], [6, 8, 28, 32, 44, 48, 88], [7, 29, 45], [7, 30, 46], [8, 31, 47], [8, 32, 48], [5, 7, 25, 29, 57, 61, 93], [5, 7, 26, 30, 58, 62, 94], [6, 8, 27, 31, 59, 63, 95], [6, 8, 28, 32, 60, 64, 96], [7, 29, 61], [7, 30, 62], [8, 31, 63], [8, 32, 64], [8, 31, 47, 71], [8, 32, 48, 72 ], [], [], [8, 31, 63, 79], [8, 32, 64, 80], [], [], [8, 31, 47, 87], [8, 32, 48, 88], [], [], [8, 31, 63, 95], [8, 32, 64, 96 ], [], [], [7, 29, 45, 69], [7, 30, 46, 70], [8, 31, 47, 71], [8, 32, 48, 72], [7, 29, 61, 77], [7, 30, 62, 78], [8, 31, 63, 79], [8, 32, 64, 80], [7, 29, 45, 85], [7, 30, 46, 86], [8, 31, 47, 87], [8, 32, 48, 88], [7, 29, 61, 93], [7, 30, 62, 94], [8, 31, 63, 95], [8, 32, 64, 96]]],[1],[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96])

```
8. The NFAs for 8, 9, 10, 11, 12, 13, 14, 15, 16 are here.The files have names k7nfa, k8nfa etc. As an example, the input for problem 7 is k7nfa. Hopefully the rest of the names are clear. If your code is correct for problem sizes I can test, I am happy to believe it is correct in general.

# Score

I will time your code on test cases 1..16 from above of increasing size. For each test \\$n\\$, the time limit is \\$2^n\\$ seconds. Your score will be the largest test case your code can process within its time limit. If two answers get to the same size then the one that is fastest on that largest test case wins. The test machine is an Intel(R) Xeon(R) CPU E5-2680 v4 @ 2.40GHz. You can use at most 16 of its cores.

# A possible solution method

One method for converting NFAs to DFAs is called subset construction. Because our NFAs will not have any \\$\epsilon\\$-moves it is slightly simpler than usual. Here is an overview of the algorithm:

Start at the initial state

1. Perform the following for the new DFA state. For each possible input symbol: Apply move to the newly-created state and the input symbol; this will return a set of states. This set of NFA states will be a single state in the DFA.
2. Each time we generate a new DFA state, we must apply step 1 to it. The process is complete when applying step 1 does not yield any new states.

The accepting states of the DFA are those which contain any of the finish states of the NFA.

# How can this be sped up?

There are have been some attempts to parallelize subset construction. E.g.

Other work has focussed on making the data structures as fast as possible, amongst other things.

# Testing

I will check your answers (for the smaller cases) using AreEquivAut .

\[Thank you to Christian Sievers for the example NFAs.\]

# Results

* **16** in \\$33812 \< 2^{16} = 65536\\$ seconds in **Rust** by Anders Kaseorg.

# Answer
# Rust, score 15 in ≈ 6000 s

Most of my optimization effort has actually gone into memory usage rather than speed, for reasons you can see in this table of results on my system (AMD Ryzen 1800X):

```
case       time     memory   DFA size
   1     0.00 s      2 MiB          3
   2     0.00 s      2 MiB         18
   3     0.00 s      2 MiB         57
   4     0.00 s      2 MiB        207
   5     0.00 s      2 MiB        318
   6     0.00 s      2 MiB       1201
   7     0.01 s      3 MiB      12230
   8     0.14 s      9 MiB      66324
   9     0.47 s     18 MiB     179766
  10     3.16 s     68 MiB     879932
  11    11.40 s    241 MiB    2385052
  12   100.64 s    886 MiB   10750324
  13   333.82 s   2026 MiB   29158718
  14  1810.72 s   9073 MiB  123222354
  15  6008.30 s  20631 MiB  333765796

```

Build with `cargo build --release` and run with `target/release/automaton < INPUT`.

### `src/main.rs`

```
use ahash::AHasher;
use hashbrown::hash_map::{HashMap, RawEntryMut};
use mimalloc::MiMalloc;
use nom::bytes::complete::tag;
use nom::character::complete::{char, digit1, multispace0};
use nom::combinator::{map, map_res};
use nom::multi::separated_list0;
use nom::sequence::{delimited, preceded};
use nom::IResult;
use std::collections::VecDeque;
use std::convert::TryInto;
use std::error::Error;
use std::hash::{Hash, Hasher};
use std::io;
use std::mem;
use std::str::FromStr;

#[global_allocator]
static GLOBAL: MiMalloc = MiMalloc;

#[derive(Debug)]
struct Automaton<Set> {
    size: u32,
    alphabet: usize,
    transitions: Vec<Vec<Set>>,
    initial: Set,
    accepting: Vec<u32>,
}

fn parse_vec<'a, T>(
    item: impl FnMut(&'a str) -> IResult<&'a str, T>,
    input: &'a str,
) -> IResult<&'a str, Vec<T>> {
    delimited(
        char('['),
        map(
            separated_list0(
                preceded(multispace0, char(',')),
                preceded(multispace0, item),
            ),
            |v| v.into_iter().collect(),
        ),
        preceded(multispace0, char(']')),
    )(input)
}

type Id = u32;
type Node = u128;
const ID_BITS: u32 = mem::size_of::<Id>() as u32 * 8;
const NODE_BITS: u32 = mem::size_of::<Node>() as u32 * 8;
const DEGREE: u32 = NODE_BITS / ID_BITS;

struct Trie {
    size: u32,
    nodes: Vec<Node>,
    ids: HashMap<Id, ()>,
}

fn pack(ids: [Id; DEGREE as usize]) -> Node {
    let mut node = 0;
    for k in 0..DEGREE {
        node |= (ids[k as usize] as Node) << ID_BITS * k;
    }
    node
}

fn unpack(node: Node) -> [Id; DEGREE as usize] {
    let mut ids = [0; DEGREE as usize];
    for k in 0..DEGREE {
        ids[k as usize] = (node >> ID_BITS * k) as Id;
    }
    ids
}

fn node_hash(node: Node) -> u64 {
    let mut hasher = AHasher::default();
    node.hash(&mut hasher);
    hasher.finish()
}

impl Trie {
    fn new(real_size: u32) -> Trie {
        let mut size = NODE_BITS;
        while size < real_size {
            size *= DEGREE;
        }
        let mut trie = Trie {
            size,
            nodes: vec![],
            ids: HashMap::new(),
        };
        let zero_id = trie.node_id(0);
        debug_assert_eq!(zero_id, 0);
        trie
    }

    fn node_id(&mut self, node: Node) -> Id {
        let hash = node_hash(node);
        let nodes = &mut self.nodes;
        match self
            .ids
            .raw_entry_mut()
            .from_hash(hash, |&id| nodes[id as usize] == node)
        {
            RawEntryMut::Occupied(e) => *e.key(),
            RawEntryMut::Vacant(e) => {
                let id: Id = nodes.len().try_into().unwrap();
                nodes.push(node);
                e.insert_with_hasher(hash, id, (), |&id| node_hash(nodes[id as usize]));
                id
            }
        }
    }

    fn vec_id(&mut self, low: u32, high: u32, vec: Vec<u32>) -> Id {
        if vec.is_empty() {
            0
        } else if high - low <= NODE_BITS {
            let mut node: Node = 0;
            for n in vec {
                node |= 1 << n - low;
            }
            self.node_id(node)
        } else {
            let step = (high - low) / DEGREE;
            let mut vecs: [Vec<u32>; DEGREE as usize] = Default::default();
            for n in vec {
                vecs[((n - low) / step) as usize].push(n);
            }
            let mut ids = [0; DEGREE as usize];
            for k in 0..DEGREE {
                ids[k as usize] = self.vec_id(
                    low + k * step,
                    low + (k + 1) * step,
                    mem::take(&mut vecs[k as usize]),
                );
            }
            self.node_id(pack(ids))
        }
    }

    fn parse_set<'a>(&mut self, input: &'a str) -> IResult<&'a str, Id> {
        let (input, vec) = parse_vec(map_res(digit1, u32::from_str), input)?;
        Ok((input, self.vec_id(0, self.size, vec)))
    }

    fn intersects(&self, size: u32, a: Id, b: Id) -> bool {
        if a == 0 || b == 0 {
            false
        } else {
            let a_node = self.nodes[a as usize];
            let b_node = self.nodes[b as usize];
            if size <= NODE_BITS {
                a_node & b_node != 0
            } else {
                let step = size / DEGREE;
                let a_ids = unpack(a_node);
                let b_ids = unpack(b_node);
                (0..DEGREE).any(|k| self.intersects(step, a_ids[k as usize], b_ids[k as usize]))
            }
        }
    }

    fn union(&mut self, size: u32, ids: &mut Vec<Id>) -> Id {
        ids.retain(|&id| id != 0);
        if ids.len() < 2 {
            ids.drain(..).next().unwrap_or(0)
        } else {
            let mut node;
            if size <= NODE_BITS {
                node = 0;
                for id in ids.drain(..) {
                    node |= self.nodes[id as usize];
                }
            } else {
                let step = size / DEGREE;
                let mut vecs: [Vec<Id>; DEGREE as usize] = Default::default();
                for vec in &mut vecs {
                    vec.reserve(ids.len());
                }
                for id in ids.drain(..) {
                    let ids1 = unpack(self.nodes[id as usize]);
                    for k in 0..DEGREE {
                        vecs[k as usize].push(ids1[k as usize]);
                    }
                }
                let mut ids = [0; DEGREE as usize];
                for k in 0..DEGREE {
                    ids[k as usize] = self.union(step, &mut vecs[k as usize]);
                }
                node = pack(ids)
            };
            self.node_id(node)
        }
    }

    fn for_each(&self, low: u32, high: u32, id: Id, f: &mut impl FnMut(u32)) {
        if id != 0 {
            let mut node = self.nodes[id as usize];
            if high - low <= NODE_BITS {
                while node != 0 {
                    let k = node.trailing_zeros();
                    f(low + k);
                    node &= !(1 << k);
                }
            } else {
                let step = (high - low) / DEGREE;
                let ids = unpack(node);
                for k in 0..DEGREE {
                    self.for_each(low + k * step, low + (k + 1) * step, ids[k as usize], f);
                }
            }
        }
    }
}

fn parse_nfa(input: &str) -> IResult<&str, (Trie, Automaton<Id>)> {
    let (input, _) = tag("Automaton")(input)?;
    let (input, _) = preceded(multispace0, char('('))(input)?;
    let (input, _) = preceded(multispace0, tag("\"nondet\""))(input)?;
    let (input, _) = preceded(multispace0, char(','))(input)?;
    let (input, size) = preceded(multispace0, map_res(digit1, u32::from_str))(input)?;
    let mut trie = Trie::new(size);
    let (input, _) = preceded(multispace0, char(','))(input)?;
    let (input, alphabet) = preceded(multispace0, map_res(digit1, usize::from_str))(input)?;
    let (input, _) = preceded(multispace0, char(','))(input)?;
    let (input, transitions) = preceded(multispace0, |input| {
        parse_vec(
            |input| parse_vec(|input| trie.parse_set(input), input),
            input,
        )
    })(input)?;
    let (input, _) = preceded(multispace0, char(','))(input)?;
    let (input, initial) = preceded(multispace0, |input| trie.parse_set(input))(input)?;
    let (input, _) = preceded(multispace0, char(','))(input)?;
    let (input, accepting) = preceded(multispace0, |input| {
        parse_vec(|input| map_res(digit1, u32::from_str)(input), input)
    })(input)?;
    let (input, _) = preceded(multispace0, char(')'))(input)?;

    Ok((
        input,
        (
            trie,
            Automaton {
                size,
                alphabet,
                transitions,
                initial,
                accepting,
            },
        ),
    ))
}

struct DFABuilder {
    nfa_accepting: Id,
    trie: Trie,
    set_dstate: HashMap<Id, u32>,
    queue: VecDeque<Id>,
    dfa: Automaton<u32>,
}

impl DFABuilder {
    fn visit(&mut self, set: Id) -> u32 {
        let DFABuilder {
            nfa_accepting,
            trie,
            set_dstate,
            queue,
            dfa,
        } = self;
        *set_dstate.entry(set).or_insert_with(|| {
            dfa.size += 1;
            if trie.intersects(trie.size, *nfa_accepting, set) {
                dfa.accepting.push(dfa.size);
            }
            queue.push_back(set);
            dfa.size
        })
    }
}

fn nfa_to_dfa(mut trie: Trie, nfa: Automaton<Id>) -> Automaton<u32> {
    let mut builder = DFABuilder {
        nfa_accepting: trie.vec_id(0, trie.size, nfa.accepting.clone()),
        trie,
        set_dstate: HashMap::new(),
        queue: VecDeque::new(),
        dfa: Automaton {
            size: 0,
            alphabet: nfa.alphabet,
            transitions: vec![vec![]; nfa.alphabet],
            initial: !0,
            accepting: vec![],
        },
    };
    builder.dfa.initial = builder.visit(nfa.initial);

    let mut sets = Vec::new();
    while let Some(set) = builder.queue.pop_front() {
        for (letter, transition) in nfa.transitions.iter().enumerate() {
            builder
                .trie
                .for_each(0, builder.trie.size, set, &mut |nstate| {
                    sets.push(transition[nstate as usize - 1])
                });
            let set1 = builder.trie.union(builder.trie.size, &mut sets);
            debug_assert!(sets.is_empty());
            let dstate = builder.visit(set1);
            builder.dfa.transitions[letter].push(dstate);
        }
    }

    builder.dfa
}

fn main() -> Result<(), Box<dyn Error>> {
    let mut line = String::new();
    io::stdin().read_line(&mut line)?;
    let (rest, (trie, nfa)) =
        delimited(multispace0, parse_nfa, multispace0)(&line).map_err(|e| e.to_string())?;
    if rest != "" {
        return Err("expected end of input".into());
    }

    let dfa = nfa_to_dfa(trie, nfa);
    println!(
        "Automaton(\"det\", {}, {}, {:?}, [{}], {:?})",
        dfa.size, dfa.alphabet, dfa.transitions, dfa.initial, dfa.accepting
    );

    Ok(())
}

```

### `Cargo.toml`

```
[package]
name = "automaton"
version = "0.1.0"
authors = ["Anders Kaseorg <andersk@mit.edu>"]
edition = "2018"

[dependencies]
nom = "6.2.1"
mimalloc = { version = "0.1.26", default-features = false }
hashbrown = { version = "0.11.2", features = ["raw"] }
ahash = "0.7.4"

```
> 12 votes

---
Tags: fastest-code, algorithm
---


# Question
Title: Determine the cyclical shift your program is in
~~Write a program that outputs the number 0.~~

That's a bit trivial, isn't it?

Let the length of your program be \\$S\\$. Write a program that outputs the number 0. When your program is cyclically shifted \\$i \< S\\$ bytes left, it should output \\$i\\$. To cyclically shift a string \\$i\\$ bytes left means to move the last \\$i\\$ bytes (including newlines) to the front, without changing the order.

For example, if your code is `ABCD`, then `ABCD` should output 0; `DABC` should output 1; `CDAB` should output 2; `BCDA` should output 3.

## Rules

* Your program must be at least **3** bytes long.
* "Output" represents any acceptable output: on the stack, to STDOUT, as a return value, as an exit code, etc.
* Your program is to not take any form of input.
* This is , so shortest code wins.

# Answer
> 10 votes
# brainfuck, 3 bytes

```
.++

```

Try it online!

**how it works**: it's really simple, actually. The internal memory is initialized at 0 so we output (with `.`) the original cell and we get 0. By shifting the program, we are shifting memory increments (done with `+`) to before the output, so each byte shifted corresponds to one more increment, and hence we increase the counter.

# Answer
> 7 votes
# Jelly, 3 bytes

```
‘n¬

```

The implicit input of a Jelly program is `0`:

**Try `‘n¬` online!** `0` incremented \\$\neq\\$ not(`0`) \\$\implies0+1 \neq 1 \implies 1\neq 1 \implies 0\\$
**Try `¬‘n` online!** not(`0`) incremented \\$\neq\\$ `0` \\$\implies1+1\neq 0 \implies 2\neq 0 \implies 1\\$
**Try `n¬‘` online!** (`0` \\$\neq\\$ not(`0`)) incremented \\$\implies(0\neq 1)+1 \implies 1+1 \implies 2\\$

# Answer
> 5 votes
# Keg `-hd`, 3 bytes

```
210

```

Try it online!

# How?

Keg only outputs the top item of the stack. These individual digits push themselves onto the stack. So for every cyclic shift, it outputs the character code of the top of the stack.

```
Program ->   Stack   -> Output last item
  210   -> [2, 1, 0] ->       [0]
  021   -> [0, 2, 1] ->       [1]
  102   -> [1, 0, 2] ->       [2]

```

# Answer
> 3 votes
# 05AB1E, 3 bytes

Right-shifts instead of left-shifts.

```
>>g

```

Try it online!

## Explanation

```
>>g : >>  Increment empty string twice
        g Find the length of the empty string (0)

>g> : >   Increment empty string
       g  Find the length (0)
        > Increment that (1)

g>> : g   Find length of empty string (0)
       >> Increment twice (2)

```

---
Tags: code-golf, source-layout
---


title: Take that frown and turn it around

text:
# Question
Title: Take that frown and turn it around
## A celebration of the many faces of APL

Given a string among those in column 1 or column 2 of the below table, return the string's neighbor to its right. In other words, if given a string in column 1 then return column 2's string on that row, and if given a string in column 2 then return column 3's string on that row.

The codepoints (other than `:`'s) are listed on the far right.

<sub> column 1 column 2 column 3</sub>
`:⊢` →  → `⊣:` U+22a2 U+2361 U+22a3
`:▷` →  → `◁:` U+25b7 U+2362 U+25c1
`:⋆` →  → `⋆:` U+22c6 U+2363 U+22c6
`:∘` →  → `∘:` U+2218 U+2364 U+2218
`:○` →  → `○:` U+25cb U+2365 U+25cb
`:≀` →  → `≀:` U+2240 U+2368 U+2240
`:∧` →  → `∨:` U+2227 U+2369 U+2228

*Anecdote:* Most of these symbols are valid or proposed in some APL dialect (they are all links).

Per request, just the symbols:

```
:⊢ ⍡ ⊣:
:▷ ⍢ ◁:
:⋆ ⍣ ⋆:
:∘ ⍤ ∘:
:○ ⍥ ○:
:≀ ⍨ ≀:
:∧ ⍩ ∨:

```

# Answer
## JavaScript (ES6), ~~108~~ 107 bytes

```
s=>(S="⊢▷⋆∘○≀∧⍡⍢⍣⍤⍥⍨⍩⊣◁⋆∘○≀∨")[S.search(s[1]||s)+7]+(s[1]?'':':')

```

### Demo

```
let f =

s=>(S="⊢▷⋆∘○≀∧⍡⍢⍣⍤⍥⍨⍩⊣◁⋆∘○≀∨")[S.search(s[1]||s)+7]+(s[1]?'':':')

;[
  ":⊢", ":▷", ":⋆", ":∘", ":○", ":≀", ":∧",
  "⍡", "⍢", "⍣", "⍤", "⍥", "⍨", "⍩"
]
.forEach(s => console.log(s + ' → ' + f(s)))
```
> 9 votes

# Answer
# Python 3, 105 bytes

```
lambda s:":⊢⍡⊣:▷⍢◁:⋆⍣⋆:∘⍤∘:○⍥○:≀⍨≀:∧⍩∨:".split(s)[1][:3-len(s)]

```

Try it online!
> 9 votes

# Answer
# C# (.NET Core), 148 134 bytes

```
s=>{var c="⊢⍡⊣▷⍢◁⋆⍣⋆∘⍤∘○⍥○≀⍨≀∧⍩∨";return c[c.IndexOf(s[s.Length-1])+1]+(s.Length<2?":":"");}

```

Try it online!

* 14 bytes saved after golfing a little.
> 5 votes

# Answer
# Jelly, 56 bytes

```
“¤'aẎṚl’b4ạ37ż“ɱaɲṢbḊİcİðdðṖeṖ@h@'i(‘ḅ⁹Ọɓi@€Ṁ‘ị;⁸LḂx@”:¤

```

A full program.

**Try it online!**

*Note:* (`ɱaɲ`!) While there is some pattern to the non-`:` ordinals (middle column almost consecutive, many left and rights being the same - only two off by one and one off by ten) it just does not seem quite enough for such a small data set to allow any byte saves over this.

The first thirteen bytes could also be `“¡ÐɼU¹’ṃ“"%#‘`.

### How?

```
“¤'aẎṚl’b4ạ37ż“ ... ‘ḅ⁹Ọɓi@€Ṁ‘ị;⁸LḂx@”:¤ - Main link: list of characters, frown
“¤'aẎṚl’                                 - base 250 number = 4064044420859
        b4                               - to base 4 = [3, 2, 3, 0, 2, 0, 3, 2, 3, 3, 2, 3, 0, 2, 0, 3, 2, 3, 3, 2, 3]
          ạ37                            - absolute diffence with 37 = [34, 35, 34, 37, 35, 37, 34, 35, 34, 34, 35, 34, 37, 35, 37, 34, 35, 34, 34, 35, 34]
              “ ... ‘                    - code page indexes = [162, 97, 163, 183, 98, 193, 198, 99, 198, 24, 100, 24, 203, 101, 203, 64, 104, 64, 39, 105, 40]
             ż                           - zip together = [[34, 162], [35, 97], [34, 163], [37, 183], [35, 98], [37, 193], [34, 198], [35, 99], [34, 198], [34, 24], [35, 100], [34, 24], [37, 203], [35, 101], [37, 203], [34, 64], [35, 104], [34, 64], [34, 39], [35, 105], [34, 40]]
                      ⁹                  - literal 256
                     ḅ                   - convert from base = [8866, 9057, 8867, 9655, 9058, 9665, 8902, 9059, 8902, 8728, 9060, 8728, 9675, 9061, 9675, 8768, 9064, 8768, 8743, 9065, 8744]
                       Ọ                 - convert to characters = "⊢⍡⊣▷⍢◁⋆⍣⋆∘⍤∘○⍥○≀⍨≀∧⍩∨"
                        ɓ                - dyadic chain separation, call that smiles
                         i@€             - first index of €ach frown character in smiles
                            Ṁ            - maximum (any ':' was not found so yielded 0)
                             ‘           - increment
                              ị          - index into smiles
                                       ¤ - nilad followed by link(s) as a nilad
                                ⁸        -   chain's left argument, frown
                                 L       -   length
                                  Ḃ      -   mod 2
                                     ”:  -   literal ':'
                                   x@    -   repeat with swapped @rguments
                               ;         - concatenate
                                         - implicit print

```

---

Employing Emigna's 05AB1E method of compression saves three for **53 bytes**:

```
“ȤỤ.ḍṅfḲBṆ µṾḢƲ¿ṭVÄ⁹L5ı;ṡaÐ’Ds3Ḍ+⁽œẉỌɓi@€Ṁ‘ị;⁸LḂx@”:¤

```

Try it online!
> 4 votes

# Answer
# Python 3, ~~140~~ ~~137~~ 116 bytes

```
lambda n,x=":⊢⍡⊣:▷⍢◁:⋆⍣⋆:∘⍤∘:○⍥○:≀⍨≀:∧⍩∨:":x[x.find(n)+len(n):x.find(n)+3]

```

Try it online!
> 3 votes

# Answer
# 05AB1E, ~~58~~ ~~56~~ 54 bytes

```
• î]D£Èтн»“¿āp÷ŒRÃÙŽ^мηWX·ć•3ô8728+çJ3ô':ý':.øI¡`3Ig-£

```

Try it online!

**Explanation**

```
• î]D£Èтн»“¿āp÷ŒRÃÙŽ^мηWX·ć•  # push a 63-digit base-255 compressed number
3ô                            # split in pieces of 3
  8728+                       # add 8728 to each
       çJ                     # convert to a string with the corresponding code points
         3ô                   # split in pieces of 3
           ':ý                # merge on ":"
              ':.ø            # surround with ":"
                  I¡          # split on input
                    `         # push as separate to stack, the tail on top
                     3Ig-£    # take the first 3-len(input) characters

```

The above method should work with any number in the range `[8676 ... 8728]`, so if I can find a number there that can be generated in 3 bytes I could save a byte over the current solution.
> 3 votes

# Answer
# PHP, 147 bytes

```
<?=($f=array_flip($y=str_split(⍣⋆⍤∘⍥○⍨≀∧⍩∨⊢⍡⊣▷⍢◁,3))[trim($argn,":")])>7?$y[$f+1].":"[$f%3>1]:$y[$f^1].":"[$f&1];

```

Try it online!
> 2 votes

# Answer
# APL (Dyalog Unicode), 103 bytes

-17 bytes thanks to Adám

```
(⌷∘S,':'/⍨14∘<)7+(S←'⊢▷⋆∘○≀∧⍡⍢⍣⍤⍥⍨⍩⊣◁⋆∘○≀∨')⍳⊢/

```

Try it online!

# APL (Dyalog Unicode), 118 bytes

Since the asker is an APL programmer...

```
{(':'/⍨14<X),⍨S⌷⍨X←7+⍸(S←'⊢▷⋆∘○≀∧⍡⍢⍣⍤⍥⍨⍩⊣◁⋆∘○≀∨')∘.=⊢/⍵}

```

Try it online!

## Explanation

```
S←'⊢▷⋆∘○≀∧⍡⍢⍣⍤⍥⍨⍩⊣◁⋆∘○≀∨'        ⍝ S is the lookup table.
⍸()∘.=⊢/⍵                             ⍝ Find the input in this LUT.
X←7+                                  ⍝ Add the index by 7 and assign to X.
S⌷⍨                                  ⍝ Index into the LUT.
,⍨                                   ⍝ Append:
':'/                                 ⍝ The colon
(⍨14<X)                              ⍝ if X is larger than 14.

```
> 2 votes

---
Tags: code-golf, string, unicode, apl
---


title: How much weight can you lift?

text:
# Question
Title: How much weight can you lift?
With all the gyms closed down with the COVID-19 situation, we have to exercise with the weight we have lying around at home. The problem is, we have a small selection of plates at varying weights, and can't immediately determine if we can create a setup at the desired weight.

Given an unsorted array of weighted plates and an unsorted array of barbells of different weights, determine the fewest amount of plates you need to put on a barbell to reach the desired weight, in ascending order mirrored at the halfway point, basically mirroring how it would be loaded on a real barbell (see example output). The plates have to be in pairs; you cannot use a particular plate an odd number of times since you put one plate on each side for equilibrium (e.g. every plate of a certain weight on one side should have a counterpart of the same weight on the otherside). If the desired weight cannot be achieved, approximate as closely as possible (while still maintaining equilibrium on both sides).

**Examples**:

**Input** (3 barbells, a set of plates, and goal weight): `[[10, 45, 6], [3.5,37,20,15,2.5,15,2.5,3.5,5,7], 47]`

**Output** (exact match, barbell and plate arrangement): `[10, [3.5,15,15,3.5]`

**Input** (3 barbells, a set of plates, and goal weight): `[[10, 45, 6], [3.5,37,20,15,2.5,15,2.5,3.5,5,7], 45]`

**Output** (exact match, barbell and plate arrangement): `[45, []]`

**Input** (3 barbells, a set of plates, and goal weight): `[[10, 45, 6], [3.5,37,20,15,2.5,15,2.5,3.5,5,7], 0]`

**Output** (closest approximation, barbell and plate arrangement): `[6, []]`

**Input** (3 barbells, a set of plates, and goal weight): `[[10, 45, 6], [3.5,37,20,15,2.5,15,2.5,3.5,5,7], 9001]`

**Output** (closest approximation, barbell and plate arrangement): `[45, [2.5,3.5,15,15,3.5,2.5]]`

Winners will be selected first by time complexity, then character count for tie-breaker.

# Answer
> 3 votes
# C++ (gcc), \\$ O(2^{\frac{|P|}4} \times (|B| + \frac{|P|}2)) \\$, 933 bytes

## Input/Output Format

Takes as input a vector of plates \\$ P \\$, a vector of barbells \\$ B \\$, and a target weight \\$ W \\$. It outputs the plate arrangement on the first line, and the barbell on the second line.

```
#include <bits/stdc++.h>
using namespace std;using d=double;
int f(auto b,auto p,d w){
unordered_map<d,int>u;vector<d>s,A,B;
for(auto i:p)u[i]++;
for(auto i:u)while((i.second-=2)>=0)s.push_back(i.first*2);
int z=s.size(),i,j,k;vector<pair<d,vector<d>>>x(1<<z/2),y(1<<z/2+1);d m=DBL_MAX,n,r;
for(i=0,k=1;i<z/2;i++){
for(j=0;j<k;j++)x[j+k]=x[j];
for(;j<k*2;j++)x[j].first+=s[i],x[j].second.push_back(s[i]/2);
auto _=x.begin();inplace_merge(_,_+k,_+k*2);k*=2;
}
for(k=1;i<z;i++){
for(j=0;j<k;j++)y[j+k]=y[j];
for(;j<k*2;j++)y[j].first+=s[i],y[j].second.push_back(s[i]/2);
auto _=y.begin();inplace_merge(_,_+k,_+k*2);k*=2;
}
for(auto f:b)
for(i=0,j=(1<<z-z/2)-1;i<1<<z/2&&j>=0;n>w?j--:i++){
n=x[i].first+y[j].first+f;
if(abs(n-w)<m)r=f,A=x[i].second,B=y[j].second,m=abs(n-w);
}
A.insert(A.end(),B.begin(),B.end());
sort(A.begin(),A.end());for(auto i:A)cout<<i<<' ';
reverse(A.begin(), A.end());for(auto i:A)cout<<i<<' ';
cout<<'\n'<<r;
}

```

Try it online!

## Explanation

The algorithm calculates all possible subset sums \\$ S \\$ of \\$ P \\$, and then finds the sum \\$ s + b \\$ which is closest to \\$ W \\$, where \\$ s \\$ and \\$ b \\$ are elements in \\$ S \\$ and \\$ B \\$, respectively. Using the meet-in-the-middle approach decreases the complexity quite a bit. (I'm aware this code is super long, and I'll try to shrink it a bit eventually).

# Answer
> 3 votes
# Python 2, \\$ O(2^{\frac{|W|}2} \cdot |B| \cdot |W| + |W|^2) \\$, 203 bytes

Naive implementation, looks at all combinations of possible weights \\$W\\$ and barbells \\$B\\$.

```
lambda B,W,T:min([(w+w[::-1],b)for w in p(sorted(sum([W.count(x)/2*[x]for x in set(W)],[])))for b in B],key=lambda(a,b):((T-sum(a)-b)**2,len(a)))
p=lambda l:l and[l[:1]+x for x in p(l[1:])]+p(l[1:])or[l]

```

Try it online!

### Ungolfed

```
def f(Barbells, Weights, Target):
  # For every pair of same weights keep one, order them ascending
  usable_weights = concat([Weights.count(x)/2 * [x] for x in set(Weights)])
  usable_weights = sorted(usable_weights)

  # list all possible combinations of symmetric weights and barbells
  possible_setups = [(w+w[::-1], b)for w in powerset(usable_weights)for b in Barbells]

  # Find the one with the weight being the closest to the target,
  # on a tie take the one with the lowest number of weights
  return min(possible_setups, key=lambda(a,b): ((Target - sum(a) - b)**2, len(a)))

concat = lambda ls:sum(ls, [])
powerset = lambda l:l and [l[:1]+x for x in powerset(l[1:])]+powerset(l[1:]) or [[]]

```

Try it online!

# Answer
> 1 votes
# Haskell, \\$O(Wlog(W)+B2^WW) \\$, 159 bytes

Worst case time, where \\$W\\$ is the number of weights and \\$B\\$ is the number of barbells.

```
import Data.List
h(a:b:r)|a==b,p<-h r=[a:q++[b]|q<-p]++p|1>0=h$b:r
h _=[[]]
(b#w)g|p<-h$sort w=snd$snd$minimum[(abs$g-a-sum q,(length q,(a,q)))|a<-b,q<-p]

```

Try it online!

I was never good at calculating time complexity, so feel free to correct me if you think I'm wrong. Here's some annotated source code to show some of my thinking:

```
import Data.List
-- O(h 0) = 1
-- O(h W) = 2*O(h$W-2) = 2^W
h(a:b:r)|a==b,p<-h r=[a:q++[b]|q<-p]++p|1>0=h$b:r
h _=[[]]
-- O(B#W$_) = W*log(W)+B*O(h W)*W = W*log(W)+B*2^W*W
(b#w)g|p<-h$sort w=snd$snd$minimum[(abs$g-a-sum q,(length q,(a,q)))|a<-b,q<-p]

```

The \\$Wlog(W)\\$ is for sorting the weights and the \\$W\\$ factor on the second part is for the linear time calculation of `length q` and `sum q`.

My implementation is a fairly straightforward brute force approach. I don't even optimize for the ideal case because it's extra bytes and it wouldn't help the worst case time anyway. The idea is to sort the list of weights and pick up on adjacent weights of equal value. I remove them from the list and recur, returning the resulting list along with those results with that weight on either side. In this way I build up a list of all possible weight combinations. Then it's a simple matter of looping over each barbell and finding the setup with the minimum error.

I've also tried to ensure that Haskell doesn't calculate some values like `h$sort w` and `h r` multiple times. I believe the compiler can usually optimize cases where it notices redundancy like that but I thought it best to err on the side of caution.

---
Tags: math, sequence, fastest-algorithm
---