Clash Royale CLAN TAG#URR8PPP

up vote
12
down vote

favorite

A nondeterministic finite automaton is a finite state machine where a tuple $(state,symbol)$ is mapped to multiple states. Ie. we replace the usual $delta : Q times Sigma to Q $ transition function of a DFA with another function $Delta : Q times Sigma to mathcalP(Q)$.

If you know what an NFA is you might want to skip the next section.

Formal Definition

An NFA is uniquely described by

$Q$ a finite set of states

$Sigma$ a finite set of symbols

$Delta : Q times Sigma to mathcalP(Q)$ the transition function

$q_0 in Q$ the initial state

$F subseteq Q$ a set of final states

The machine starts out in $q_0$ and reads a finite string of symbols $w in Sigma^*$, for each symbol it will simultaneously apply the transition function function with a current state and add each new set of states to the set of current states.

Challenge

For this challenge we will ignore $F $ to simplify it, furthermore the alphabet will always be the (lower-case) letters $texttta $ to $textttz $ and the set of states will be $0 dots N$ for some non-negative integer $N$. The initial state will always be $0$.

Given a word $w in textttadotstextttz^*$ and a description of the NFA, your task is to determine all the final states.

Example

Consider the string $textttabaab$ and the following description:

state, symbol, new-states
0, 'a', [1]
1, 'a', [0]
1, 'b', [1,2]

The machine will start in $q_0 = 0$:

read an $texttta$: new states $1$

read a $textttb$: new states $1,2$

read an $texttta$: new states $0$

read an $texttta$: new states $1$

read a $textttb$: new states $1,2$

So the final states and thus the output would be $1,2$.

Note: In step (2) the transition of state $2$ maps to $emptyset$ as the description only includes transitions to non-empty sets.

Rules

The input will consist of a string and some kind of description of the NFA (without $epsilon$-transitions):

the input string will always be element of $textttadotstextttz^*$

valid inputs (not limited to):
- list/array of tuples/lists
- new-line separated input

the description of the NFA will only contain transitions with non-empty sets as result
- you may abbreviate rules with the same characters if their result is the same (eg. rules 0,'a',[1,2] and 0,'b',[1,2] could be abbreviated with 0,"ab",[1,2]
- you may take each rule separate (eg. rule 0,'a',[1,2] can be 0,'a',[1] and 0,'a',[2])

you may choose upper-case letters if you want

you may take the number of states as input

you may assume some kind of ordering of the inputs (eg. ordered by state or symbols)

The output will be a list/set/new-line separated output etc. of the final states

order doesn't matter

no duplicates (as it's a set)

Test cases

These examples will be in the format description word -> states where description is a list of tuples (state,symbol,new-states):

 "x" -> 
 "" -> [0]
[(0,'a',[1]),(1,'a',[0]),(1,'b',[1,2])] "abaab" -> [1,2]
[(0,'a',[1]),(1,'a',[0]),(1,'b',[1,2])] "abc" -> 
[(0,'p',[0,1]),(0,'g',[2]),(1,'c',[1]),(1,'g',[4]),(1,'p',[2]),(2,'c',[0])] "ppcg" -> [2,4]
[(0,'f',[1]),(1,'o',[1,2]),(2,'b',[3]),(3,'a',[4]),(4,'r',[0,4])] "foobar" -> [0,4]
[(0,'f',[1]),(1,'o',[1,2]),(2,'b',[3]),(3,'a',[4]),(4,'r',[0,4])] "fooooooobar" -> [0,4]
[(0,'f',[1]),(1,'o',[1,2]),(2,'b',[3]),(3,'a',[4]),(4,'r',[0,4])] "fobarfo" -> [1,2]
[(0,'f',[1]),(1,'o',[1,2]),(2,'b',[3]),(3,'a',[4]),(4,'r',[0,4])] "foobarrf" -> [1]
[(0,'d',[1,2]),(1,'u',[2]),(2,'u',[2,3]),(2,'p',[3]),(3,'p',[3])] "dup" -> [3]
[(0,'a',[0,2]),(0,'b',[3]),(1,'a',[1]),(1,'b',[1]),(2,'b',[1,4]),(4,'b',[2])] "aab" -> [3,1,4]
[(0,'a',[0,2]),(0,'b',[3]),(1,'a',[1]),(1,'b',[1]),(2,'b',[1,4]),(4,'b',[2])] "abb" -> [1,2]

edited Sep 4 at 23:42

asked Sep 4 at 16:22

BWO

9,33011570

related
â€“Â BWO
Sep 4 at 16:25

3

This brings back scary memories from my automaton course.
â€“Â Rushabh Mehta
Sep 4 at 16:29

Can we take input with individual lines for each new state, e.g. this for worked example?
â€“Â ovs
Sep 4 at 16:43

@ovs: Sure go ahead!
â€“Â BWO
Sep 4 at 16:53

add a commentÂ |Â

up vote
12
down vote

favorite

If you know what an NFA is you might want to skip the next section.

Formal Definition

An NFA is uniquely described by

$Q$ a finite set of states

$Sigma$ a finite set of symbols

$Delta : Q times Sigma to mathcalP(Q)$ the transition function

$q_0 in Q$ the initial state

$F subseteq Q$ a set of final states

Challenge

Given a word $w in textttadotstextttz^*$ and a description of the NFA, your task is to determine all the final states.

Example

Consider the string $textttabaab$ and the following description:

state, symbol, new-states
0, 'a', [1]
1, 'a', [0]
1, 'b', [1,2]

The machine will start in $q_0 = 0$:

read an $texttta$: new states $1$

read a $textttb$: new states $1,2$

read an $texttta$: new states $0$

read an $texttta$: new states $1$

read a $textttb$: new states $1,2$

So the final states and thus the output would be $1,2$.

Note: In step (2) the transition of state $2$ maps to $emptyset$ as the description only includes transitions to non-empty sets.

Rules

The input will consist of a string and some kind of description of the NFA (without $epsilon$-transitions):

the input string will always be element of $textttadotstextttz^*$

valid inputs (not limited to):
- list/array of tuples/lists
- new-line separated input

the description of the NFA will only contain transitions with non-empty sets as result
- you may abbreviate rules with the same characters if their result is the same (eg. rules 0,'a',[1,2] and 0,'b',[1,2] could be abbreviated with 0,"ab",[1,2]
- you may take each rule separate (eg. rule 0,'a',[1,2] can be 0,'a',[1] and 0,'a',[2])

you may choose upper-case letters if you want

you may take the number of states as input

you may assume some kind of ordering of the inputs (eg. ordered by state or symbols)

The output will be a list/set/new-line separated output etc. of the final states

order doesn't matter

no duplicates (as it's a set)

Test cases

These examples will be in the format description word -> states where description is a list of tuples (state,symbol,new-states):

 "x" -> 
 "" -> [0]
[(0,'a',[1]),(1,'a',[0]),(1,'b',[1,2])] "abaab" -> [1,2]
[(0,'a',[1]),(1,'a',[0]),(1,'b',[1,2])] "abc" -> 
[(0,'p',[0,1]),(0,'g',[2]),(1,'c',[1]),(1,'g',[4]),(1,'p',[2]),(2,'c',[0])] "ppcg" -> [2,4]
[(0,'f',[1]),(1,'o',[1,2]),(2,'b',[3]),(3,'a',[4]),(4,'r',[0,4])] "foobar" -> [0,4]
[(0,'f',[1]),(1,'o',[1,2]),(2,'b',[3]),(3,'a',[4]),(4,'r',[0,4])] "fooooooobar" -> [0,4]
[(0,'f',[1]),(1,'o',[1,2]),(2,'b',[3]),(3,'a',[4]),(4,'r',[0,4])] "fobarfo" -> [1,2]
[(0,'f',[1]),(1,'o',[1,2]),(2,'b',[3]),(3,'a',[4]),(4,'r',[0,4])] "foobarrf" -> [1]
[(0,'d',[1,2]),(1,'u',[2]),(2,'u',[2,3]),(2,'p',[3]),(3,'p',[3])] "dup" -> [3]
[(0,'a',[0,2]),(0,'b',[3]),(1,'a',[1]),(1,'b',[1]),(2,'b',[1,4]),(4,'b',[2])] "aab" -> [3,1,4]
[(0,'a',[0,2]),(0,'b',[3]),(1,'a',[1]),(1,'b',[1]),(2,'b',[1,4]),(4,'b',[2])] "abb" -> [1,2]

edited Sep 4 at 23:42

asked Sep 4 at 16:22

BWO

9,33011570

related
â€“Â BWO
Sep 4 at 16:25

3

This brings back scary memories from my automaton course.
â€“Â Rushabh Mehta
Sep 4 at 16:29

Can we take input with individual lines for each new state, e.g. this for worked example?
â€“Â ovs
Sep 4 at 16:43

@ovs: Sure go ahead!
â€“Â BWO
Sep 4 at 16:53

add a commentÂ |Â

up vote
12
down vote

favorite

If you know what an NFA is you might want to skip the next section.

Formal Definition

An NFA is uniquely described by

$Q$ a finite set of states

$Sigma$ a finite set of symbols

$Delta : Q times Sigma to mathcalP(Q)$ the transition function

$q_0 in Q$ the initial state

$F subseteq Q$ a set of final states

Challenge

Given a word $w in textttadotstextttz^*$ and a description of the NFA, your task is to determine all the final states.

Example

Consider the string $textttabaab$ and the following description:

state, symbol, new-states
0, 'a', [1]
1, 'a', [0]
1, 'b', [1,2]

The machine will start in $q_0 = 0$:

read an $texttta$: new states $1$

read a $textttb$: new states $1,2$

read an $texttta$: new states $0$

read an $texttta$: new states $1$

read a $textttb$: new states $1,2$

So the final states and thus the output would be $1,2$.

Note: In step (2) the transition of state $2$ maps to $emptyset$ as the description only includes transitions to non-empty sets.

Rules

The input will consist of a string and some kind of description of the NFA (without $epsilon$-transitions):

the input string will always be element of $textttadotstextttz^*$

valid inputs (not limited to):
- list/array of tuples/lists
- new-line separated input

the description of the NFA will only contain transitions with non-empty sets as result
- you may abbreviate rules with the same characters if their result is the same (eg. rules 0,'a',[1,2] and 0,'b',[1,2] could be abbreviated with 0,"ab",[1,2]
- you may take each rule separate (eg. rule 0,'a',[1,2] can be 0,'a',[1] and 0,'a',[2])

you may choose upper-case letters if you want

you may take the number of states as input

you may assume some kind of ordering of the inputs (eg. ordered by state or symbols)

The output will be a list/set/new-line separated output etc. of the final states

order doesn't matter

no duplicates (as it's a set)

Test cases

These examples will be in the format description word -> states where description is a list of tuples (state,symbol,new-states):

 "x" -> 
 "" -> [0]
[(0,'a',[1]),(1,'a',[0]),(1,'b',[1,2])] "abaab" -> [1,2]
[(0,'a',[1]),(1,'a',[0]),(1,'b',[1,2])] "abc" -> 
[(0,'p',[0,1]),(0,'g',[2]),(1,'c',[1]),(1,'g',[4]),(1,'p',[2]),(2,'c',[0])] "ppcg" -> [2,4]
[(0,'f',[1]),(1,'o',[1,2]),(2,'b',[3]),(3,'a',[4]),(4,'r',[0,4])] "foobar" -> [0,4]
[(0,'f',[1]),(1,'o',[1,2]),(2,'b',[3]),(3,'a',[4]),(4,'r',[0,4])] "fooooooobar" -> [0,4]
[(0,'f',[1]),(1,'o',[1,2]),(2,'b',[3]),(3,'a',[4]),(4,'r',[0,4])] "fobarfo" -> [1,2]
[(0,'f',[1]),(1,'o',[1,2]),(2,'b',[3]),(3,'a',[4]),(4,'r',[0,4])] "foobarrf" -> [1]
[(0,'d',[1,2]),(1,'u',[2]),(2,'u',[2,3]),(2,'p',[3]),(3,'p',[3])] "dup" -> [3]
[(0,'a',[0,2]),(0,'b',[3]),(1,'a',[1]),(1,'b',[1]),(2,'b',[1,4]),(4,'b',[2])] "aab" -> [3,1,4]
[(0,'a',[0,2]),(0,'b',[3]),(1,'a',[1]),(1,'b',[1]),(2,'b',[1,4]),(4,'b',[2])] "abb" -> [1,2]

edited Sep 4 at 23:42

asked Sep 4 at 16:22

BWO

9,33011570

If you know what an NFA is you might want to skip the next section.

Formal Definition

An NFA is uniquely described by

$Q$ a finite set of states

$Sigma$ a finite set of symbols

$Delta : Q times Sigma to mathcalP(Q)$ the transition function

$q_0 in Q$ the initial state

$F subseteq Q$ a set of final states

Challenge

Given a word $w in textttadotstextttz^*$ and a description of the NFA, your task is to determine all the final states.

Example

Consider the string $textttabaab$ and the following description:

state, symbol, new-states
0, 'a', [1]
1, 'a', [0]
1, 'b', [1,2]

The machine will start in $q_0 = 0$:

read an $texttta$: new states $1$

read a $textttb$: new states $1,2$

read an $texttta$: new states $0$

read an $texttta$: new states $1$

read a $textttb$: new states $1,2$

So the final states and thus the output would be $1,2$.

Note: In step (2) the transition of state $2$ maps to $emptyset$ as the description only includes transitions to non-empty sets.

Rules

The input will consist of a string and some kind of description of the NFA (without $epsilon$-transitions):

the input string will always be element of $textttadotstextttz^*$

valid inputs (not limited to):
- list/array of tuples/lists
- new-line separated input

the description of the NFA will only contain transitions with non-empty sets as result
- you may abbreviate rules with the same characters if their result is the same (eg. rules 0,'a',[1,2] and 0,'b',[1,2] could be abbreviated with 0,"ab",[1,2]
- you may take each rule separate (eg. rule 0,'a',[1,2] can be 0,'a',[1] and 0,'a',[2])

you may choose upper-case letters if you want

you may take the number of states as input

you may assume some kind of ordering of the inputs (eg. ordered by state or symbols)

The output will be a list/set/new-line separated output etc. of the final states

order doesn't matter

no duplicates (as it's a set)

Test cases

These examples will be in the format description word -> states where description is a list of tuples (state,symbol,new-states):

 "x" -> 
 "" -> [0]
[(0,'a',[1]),(1,'a',[0]),(1,'b',[1,2])] "abaab" -> [1,2]
[(0,'a',[1]),(1,'a',[0]),(1,'b',[1,2])] "abc" -> 
[(0,'p',[0,1]),(0,'g',[2]),(1,'c',[1]),(1,'g',[4]),(1,'p',[2]),(2,'c',[0])] "ppcg" -> [2,4]
[(0,'f',[1]),(1,'o',[1,2]),(2,'b',[3]),(3,'a',[4]),(4,'r',[0,4])] "foobar" -> [0,4]
[(0,'f',[1]),(1,'o',[1,2]),(2,'b',[3]),(3,'a',[4]),(4,'r',[0,4])] "fooooooobar" -> [0,4]
[(0,'f',[1]),(1,'o',[1,2]),(2,'b',[3]),(3,'a',[4]),(4,'r',[0,4])] "fobarfo" -> [1,2]
[(0,'f',[1]),(1,'o',[1,2]),(2,'b',[3]),(3,'a',[4]),(4,'r',[0,4])] "foobarrf" -> [1]
[(0,'d',[1,2]),(1,'u',[2]),(2,'u',[2,3]),(2,'p',[3]),(3,'p',[3])] "dup" -> [3]
[(0,'a',[0,2]),(0,'b',[3]),(1,'a',[1]),(1,'b',[1]),(2,'b',[1,4]),(4,'b',[2])] "aab" -> [3,1,4]
[(0,'a',[0,2]),(0,'b',[3]),(1,'a',[1]),(1,'b',[1]),(2,'b',[1,4]),(4,'b',[2])] "abb" -> [1,2]

edited Sep 4 at 23:42

asked Sep 4 at 16:22

BWO

9,33011570

edited Sep 4 at 23:42

asked Sep 4 at 16:22

BWO

9,33011570

asked Sep 4 at 16:22

BWO

9,33011570

asked Sep 4 at 16:22

BWO

9,33011570

related
â€“Â BWO
Sep 4 at 16:25

3

This brings back scary memories from my automaton course.
â€“Â Rushabh Mehta
Sep 4 at 16:29

Can we take input with individual lines for each new state, e.g. this for worked example?
â€“Â ovs
Sep 4 at 16:43

@ovs: Sure go ahead!
â€“Â BWO
Sep 4 at 16:53

add a commentÂ |Â

related
â€“Â BWO
Sep 4 at 16:25

3

This brings back scary memories from my automaton course.
â€“Â Rushabh Mehta
Sep 4 at 16:29

Can we take input with individual lines for each new state, e.g. this for worked example?
â€“Â ovs
Sep 4 at 16:43

@ovs: Sure go ahead!
â€“Â BWO
Sep 4 at 16:53

related
â€“Â BWO
Sep 4 at 16:25

This brings back scary memories from my automaton course.
â€“Â Rushabh Mehta
Sep 4 at 16:29

Can we take input with individual lines for each new state, e.g. this for worked example?
â€“Â ovs
Sep 4 at 16:43

@ovs: Sure go ahead!
â€“Â BWO
Sep 4 at 16:53

add a commentÂ |Â

10 Answers
10

active

oldest

votes

up vote
7
down vote

Haskell, 66 bytes

import Data.List
f d=foldl(s c->nub[r|(y,r)<-d,g<-s,(g,c)==y])[0]

Try it online!

answered Sep 4 at 17:24

ovs

17.3k21056

You can get rid of the import for nub if you assume the states to be [Int], then you can use check each [0..] which is finite: 60 bytes
â€“Â BWO
Sep 4 at 21:52

@BWO This iterates over all Ints and over all current states and therefore still produces duplicate states. Example (changed [0..] to [0..3] for testing purposes, but this should not make a difference, right?)
â€“Â ovs
Sep 5 at 5:26

Yeah, not sure what I was thinking.. Nevermind..
â€“Â BWO
Sep 5 at 5:34

add a commentÂ |Â

up vote
4
down vote

Brachylog, 42 bytes

,0hÃ¡ÂºÂ¸&tÃ¡ÂµÂ˜

input as [string, nfa]
where nfa is a list of state transitions [ initial state, letter, new states as list ]

Explanation

,0 # Append 0 to the input (initial state)
 Ã¡ÂµÂ˜ # Find all unique outputs
 h # if first element (string)
 Ã¡ÂºÂ¸ # is empty
 &t # then: return last element (current state)
 | # else:
 Ã¢ÂˆÂ‹Ã¢Â‚ÂB # save the state transitions in "B"
 Ã¢ÂˆÂ‹I # take one of these transitions, save in "I"
 hJ # take the initial state requirement, store in "J"
 &tJ # make sure "J" is actually the current state
 &hhC # Save first char of string in C
 Ã¢ÂˆÂ§IÃ¢ÂˆÂ‹Ã¢Â‚ÂC # make sure the char requirement for the state transition is the current char
 Ã¢ÂˆÂ§ItÃ¢ÂˆÂ‹S # Make "S" equal to one of the new states
 &hb # Behead the string (remove first char)
 ;B,S # Add B (the state transitions) and S (the new state)
 Ã¢Â†Â° # recur this function

Try it online!

answered Sep 5 at 9:53

Kroppeb

90628

add a commentÂ |Â

up vote
3
down vote

Python 3, 103 80 bytes

thanks to @BWO

w=lambda n,f,a=0:w(n,f[1:],y for(x,c,y)in n if c==f[0]andx&a)if''<f else a

TIO

Previous "elegant" list comprehension(103 bytes):

def w(a,b):
 q=[0]
 for c in b:q=[j for s in q for i in a if s in i if i[1]==c for j in i[2]]
 return q

edited Sep 4 at 23:45

answered Sep 4 at 19:23

Quintec

25118

Shame that Python 3 lacks reduce.. But using recursion and actual sets still brings you down to 80 bytes.
â€“Â BWO
Sep 4 at 21:43

@BWO nice, thanks, haha btw the above is my new favorite example python code to show... one line giant list comprehensions amuse me way more than they should
â€“Â Quintec
Sep 4 at 22:06

I think you can save 2 bytes by replacing if''<f with if f.
â€“Â Chas Brown
Sep 5 at 19:17

@Chas Brown that fails if f is a falsy value such as empty string
â€“Â Quintec
Sep 5 at 19:24

Actually, what am I saying, ignore that
â€“Â Quintec
Sep 5 at 19:25

add a commentÂ |Â

up vote
3
down vote

JavaScript (ES6), 99 bytes

Takes input as (nfa)(string). Returns a Set.

a=>g=([c,...b],s=[0])=>c?g(b,a.reduce((p,[x,y,z])=>s.includes(x)&y==c?[...p,...z]:p,)):new Set(s)

Try it online!

edited Sep 5 at 6:33

answered Sep 4 at 16:45

Arnauld

63.7k580268

add a commentÂ |Â

up vote
3
down vote

R, 81 bytes

function(a,b,e,s)Reduce(function(A,x)unique(e[a%in%A&b==x]),el(strsplit(s,"")),0)

Try it online!

Straightforward answer using Reduce. Takes rules as three vectors of state, symbol, new-states called a,b,e.

Rules are separate (eg. rule 0,'a',[1,2] is 0,'a',1 and 0,'a',2).

answered Sep 5 at 19:36

JayCe

2,339415

add a commentÂ |Â

up vote
3
down vote

Brachylog v2, 31 bytes

b,ÃˆÂ®,ÃˆÂ®cÃ¢Â†Â”,0Ã¢Â†Â”Ã„Â¡Ã¢Â‚ÂƒkH&hg;HzÃ¢ÂˆÂ‹Ã¡ÂµÂˆÃ¡ÂµÂttÃ¡ÂµÂ˜

Try it online! (or with a more complex example)

Brachylog is really good at this sort of problem, and really bad at problems that require two separate inputs and an output. Almost all of this program is just plumbing.

Input format is a list containing two elements: the first is the list of state transitions ([oldState, symbol, newState]), and the second is the list of symbols. I originally planned this program to work with character codes for symbols (because Brachylog's string handling can be a bit weird sometimes), but it turns out that characters work too (although you have to write the input string as a list of characters, not as a string). If a state-symbol pair can transition to multiple different states, you write multiple transitions to deal with that.

Explanation

b,ÃˆÂ®,ÃˆÂ®cÃ¢Â†Â”,0Ã¢Â†Â”Ã„Â¡Ã¢Â‚ÂƒkH&hg;HzÃ¢ÂˆÂ‹Ã¡ÂµÂˆÃ¡ÂµÂttÃ¡ÂµÂ˜
 Ã¡ÂµÂ˜ Find all distinct outputs that can result from:
 b taking the input minus its first element,
 ,ÃˆÂ® appending a singleton list (i.e. an element)
 ,ÃˆÂ® then appending that same element again
 and transposing;
 c then concatenating the resulting lists,
 Ã¢Â†Â”,0Ã¢Â†Â” prepending a 0,
 Ã„Â¡Ã¢Â‚Âƒ grouping into blocks of 3 elements
 k (and discarding the last, incomplete, block),
 H& storing that while we
 h take the first input element,
 g z pair a copy of it with each element of
 ;H the stored value,
 Ã¡ÂµÂ assert that for each resulting element
 Ã¢ÂˆÂ‹Ã¡ÂµÂˆ its first element contains the second,
 Ã¡ÂµÂˆ Ã¡ÂµÂ returning the list of second elements,
 t then taking the last element of
 t the last element.

It's probably easier to follow this by looking at what some partial versions of the program would produce. Using the following input each time:

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]

we can observe the outputs of some prefixes of this program:

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,ÃˆÂ®,ÃˆÂ®
[[97,98,97,97,98],L,L]

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,ÃˆÂ®,ÃˆÂ®
[[97,A,A],[98,B,B],[97,C,C],[97,D,D],[98,E,E]]

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,ÃˆÂ®,ÃˆÂ®cÃ¢Â†Â”,0Ã¢Â†Â”
[0,97,A,A,98,B,B,97,C,C,97,D,D,98,E,E]

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,ÃˆÂ®,ÃˆÂ®cÃ¢Â†Â”,0Ã¢Â†Â”Ã„Â¡Ã¢Â‚Âƒk
[[0,97,A],[A,98,B],[B,97,C],[C,97,D],[D,98,E]]

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,ÃˆÂ®,ÃˆÂ®cÃ¢Â†Â”,0Ã¢Â†Â”Ã„Â¡Ã¢Â‚ÂƒkH&hg;Hz
[[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[0,97,A]],
 [[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[A,98,B]],
 [[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[B,97,C]],
 [[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[C,97,D]],
 [[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[D,98,E]]]

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,ÃˆÂ®,ÃˆÂ®cÃ¢Â†Â”,0Ã¢Â†Â”Ã„Â¡Ã¢Â‚ÂƒkH&hg;HzÃ¢ÂˆÂ‹Ã¡ÂµÂˆÃ¡ÂµÂ
e.g. [[0,97,1],[1,98,1],[1,97,0],[0,97,1],[1,98,1]]

For the first example here, L is initially an unknown element, but when we transpose it via , Brachylog realises that the only possibility is a list with the same length as the input. The last example here is nondeterministic; we're modelling nondeterminism in the NFA using the nondeterminism in Brachylog itself.

Possible improvements

Some of the syntax here, like Ã¢Â†Â”,0Ã¢Â†Â” and especially the mess with H&hg;HzÃ¢Â€Â¦Ã¡ÂµÂˆÃ¡ÂµÂ, is fairly clunky. It wouldn't surprise me if there were a terser way to phrse this.

Ã¢ÂˆÂ‹Ã¡ÂµÂˆÃ¡ÂµÂ is in its own right a fairly suspicious structure Ã¢Â€Â“ you'd expect to just be able to write Ã¢ÂˆÂ‹Ã¡ÂµÂˆÃ¡ÂµÂ Ã¢Â€Â“ but it doesn't parse for some reason.

edited Sep 6 at 20:40

community wiki

2 revs
ais523

Ã¢ÂˆÂ‹Ã¡ÂµÂˆÃ¡ÂµÂ doesn't parse because it is implemented such that multi-character meta-predicate names could in theory be used (if we ran out of single-symbol possibilities). In practice it's not currently used.
â€“Â Fatalize
Sep 7 at 6:52

add a commentÂ |Â

up vote
2
down vote

Coconut, 64 bytes

d->reduce$((s,c)->r for(*y,r)in d for S in s if[S,c]==y,?,0)

Try it online!

answered Sep 4 at 16:59

ovs

17.3k21056

add a commentÂ |Â

up vote
2
down vote

Clean, 68 bytes

This one based on ovs's Haskell solution is a bit shorter than my initial approach was.

now includes a test harness

import StdEnv
?d=foldl(s c=removeDup[r\(y,r)<-d,g<-s|(g,c)==y])[0]

Try it online!

edited Sep 5 at 0:30

answered Sep 4 at 23:08

ÃŽÂŸurous

5,2131931

1

@BWO Test harness added
â€“Â ÃŽÂŸurous
Sep 4 at 23:47

add a commentÂ |Â

up vote
1
down vote

Perl 6, 61 bytes

$s.comb

Try it online!

edited Sep 5 at 2:12

answered Sep 5 at 1:36

nwellnhof

3,503714

add a commentÂ |Â

up vote
1
down vote

Charcoal, 44 bytes

Ã¢ÂŠÂžÃÂ…Ã¢ÂÂ°Ã¯Â¼Â¦ÃŽÂ·Ã‚Â«Ã¢Â‰Â”ÃÂ…ÃŽÂ¶Ã¢Â‰Â”Ã¢ÂŸÂ¦Ã¢ÂŸÂ§ÃÂ…Ã¯Â¼Â¦ÃŽÂ¶Ã¯Â¼Â¦ÃŽÂ¸Ã‚Â¿Ã¢ÂˆÂ§Ã¢ÂÂ¼Ã‚Â§ÃŽÂ»Ã¢ÂÂ°ÃŽÂºÃ¢ÂÂ¼Ã‚Â§ÃŽÂ»Ã‚Â¹ÃŽÂ¹Ã¯Â¼Â¦Ã‚Â§ÃŽÂ»Ã‚Â²Ã‚Â¿Ã‚Â¬Ã¢Â„Â–ÃÂ…ÃŽÂ¼Ã¢ÂŠÂžÃÂ…ÃŽÂ¼Ã‚Â»Ã¯Â¼Â©ÃÂ…

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

Ã¢ÂŠÂžÃÂ…Ã¢ÂÂ°

Push 0 to the predefined empty list to set the inital state to $0$.

Ã¯Â¼Â¦ÃŽÂ·Ã‚Â«

Loop over the input.

Ã¢Â‰Â”ÃÂ…ÃŽÂ¶

Copy the state.

Ã¢Â‰Â”Ã¢ÂŸÂ¦Ã¢ÂŸÂ§ÃÂ…

Reset the state.

Ã¯Â¼Â¦ÃŽÂ¶

Loop over the copy of the state.

Ã¯Â¼Â¦ÃŽÂ¸

Loop over the NFA entries.

Ã‚Â¿Ã¢ÂˆÂ§Ã¢ÂÂ¼Ã‚Â§ÃŽÂ»Ã¢ÂÂ°ÃŽÂºÃ¢ÂÂ¼Ã‚Â§ÃŽÂ»Ã‚Â¹ÃŽÂ¹

If the entry matches, then...

Ã¯Â¼Â¦Ã‚Â§ÃŽÂ»Ã‚Â²

... loop over the new states...

Ã‚Â¿Ã‚Â¬Ã¢Â„Â–ÃÂ…ÃŽÂ¼

.... if they are not already in the list...

Ã¢ÂŠÂžÃÂ…ÃŽÂ¼Ã‚Â»

... add them to the list.

Ã¯Â¼Â©ÃÂ…

Cast the list of states to string for implicit output on separate lines.

answered Sep 5 at 19:29

Neil

75.1k744170

add a commentÂ |Â

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
);
);
, "mathjax-editing");

StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "200"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);

);

draft saved

draft discarded

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f171711%2fsimulate-an-nfa%23new-answer', 'question_page');

);

Post as a guest

Name

10 Answers
10

active

oldest

votes

10 Answers
10

active

oldest

votes

up vote
7
down vote

Haskell, 66 bytes

import Data.List
f d=foldl(s c->nub[r|(y,r)<-d,g<-s,(g,c)==y])[0]

Try it online!

answered Sep 4 at 17:24

ovs

17.3k21056

You can get rid of the import for nub if you assume the states to be [Int], then you can use check each [0..] which is finite: 60 bytes
â€“Â BWO
Sep 4 at 21:52

@BWO This iterates over all Ints and over all current states and therefore still produces duplicate states. Example (changed [0..] to [0..3] for testing purposes, but this should not make a difference, right?)
â€“Â ovs
Sep 5 at 5:26

Yeah, not sure what I was thinking.. Nevermind..
â€“Â BWO
Sep 5 at 5:34

add a commentÂ |Â

up vote
7
down vote

Haskell, 66 bytes

import Data.List
f d=foldl(s c->nub[r|(y,r)<-d,g<-s,(g,c)==y])[0]

Try it online!

answered Sep 4 at 17:24

ovs

17.3k21056

You can get rid of the import for nub if you assume the states to be [Int], then you can use check each [0..] which is finite: 60 bytes
â€“Â BWO
Sep 4 at 21:52

@BWO This iterates over all Ints and over all current states and therefore still produces duplicate states. Example (changed [0..] to [0..3] for testing purposes, but this should not make a difference, right?)
â€“Â ovs
Sep 5 at 5:26

Yeah, not sure what I was thinking.. Nevermind..
â€“Â BWO
Sep 5 at 5:34

add a commentÂ |Â

up vote
7
down vote

Haskell, 66 bytes

import Data.List
f d=foldl(s c->nub[r|(y,r)<-d,g<-s,(g,c)==y])[0]

Try it online!

answered Sep 4 at 17:24

ovs

17.3k21056

Haskell, 66 bytes

import Data.List
f d=foldl(s c->nub[r|(y,r)<-d,g<-s,(g,c)==y])[0]

Try it online!

answered Sep 4 at 17:24

ovs

17.3k21056

answered Sep 4 at 17:24

ovs

17.3k21056

answered Sep 4 at 17:24

ovs

17.3k21056

answered Sep 4 at 17:24

ovs

17.3k21056

You can get rid of the import for nub if you assume the states to be [Int], then you can use check each [0..] which is finite: 60 bytes
â€“Â BWO
Sep 4 at 21:52

@BWO This iterates over all Ints and over all current states and therefore still produces duplicate states. Example (changed [0..] to [0..3] for testing purposes, but this should not make a difference, right?)
â€“Â ovs
Sep 5 at 5:26

Yeah, not sure what I was thinking.. Nevermind..
â€“Â BWO
Sep 5 at 5:34

add a commentÂ |Â

You can get rid of the import for nub if you assume the states to be [Int], then you can use check each [0..] which is finite: 60 bytes
â€“Â BWO
Sep 4 at 21:52

@BWO This iterates over all Ints and over all current states and therefore still produces duplicate states. Example (changed [0..] to [0..3] for testing purposes, but this should not make a difference, right?)
â€“Â ovs
Sep 5 at 5:26

Yeah, not sure what I was thinking.. Nevermind..
â€“Â BWO
Sep 5 at 5:34

You can get rid of the import for nub if you assume the states to be [Int], then you can use check each [0..] which is finite: 60 bytes
â€“Â BWO
Sep 4 at 21:52

@BWO This iterates over all Ints and over all current states and therefore still produces duplicate states. Example (changed [0..] to [0..3] for testing purposes, but this should not make a difference, right?)
â€“Â ovs
Sep 5 at 5:26

Yeah, not sure what I was thinking.. Nevermind..
â€“Â BWO
Sep 5 at 5:34

add a commentÂ |Â

up vote
4
down vote

Brachylog, 42 bytes

,0hÃ¡ÂºÂ¸&tÃ¡ÂµÂ˜

input as [string, nfa]
where nfa is a list of state transitions [ initial state, letter, new states as list ]

Explanation

,0 # Append 0 to the input (initial state)
 Ã¡ÂµÂ˜ # Find all unique outputs
 h # if first element (string)
 Ã¡ÂºÂ¸ # is empty
 &t # then: return last element (current state)
 | # else:
 Ã¢ÂˆÂ‹Ã¢Â‚ÂB # save the state transitions in "B"
 Ã¢ÂˆÂ‹I # take one of these transitions, save in "I"
 hJ # take the initial state requirement, store in "J"
 &tJ # make sure "J" is actually the current state
 &hhC # Save first char of string in C
 Ã¢ÂˆÂ§IÃ¢ÂˆÂ‹Ã¢Â‚ÂC # make sure the char requirement for the state transition is the current char
 Ã¢ÂˆÂ§ItÃ¢ÂˆÂ‹S # Make "S" equal to one of the new states
 &hb # Behead the string (remove first char)
 ;B,S # Add B (the state transitions) and S (the new state)
 Ã¢Â†Â° # recur this function

Try it online!

answered Sep 5 at 9:53

Kroppeb

90628

add a commentÂ |Â

up vote
4
down vote

Brachylog, 42 bytes

,0hÃ¡ÂºÂ¸&tÃ¡ÂµÂ˜

input as [string, nfa]
where nfa is a list of state transitions [ initial state, letter, new states as list ]

Explanation

,0 # Append 0 to the input (initial state)
 Ã¡ÂµÂ˜ # Find all unique outputs
 h # if first element (string)
 Ã¡ÂºÂ¸ # is empty
 &t # then: return last element (current state)
 | # else:
 Ã¢ÂˆÂ‹Ã¢Â‚ÂB # save the state transitions in "B"
 Ã¢ÂˆÂ‹I # take one of these transitions, save in "I"
 hJ # take the initial state requirement, store in "J"
 &tJ # make sure "J" is actually the current state
 &hhC # Save first char of string in C
 Ã¢ÂˆÂ§IÃ¢ÂˆÂ‹Ã¢Â‚ÂC # make sure the char requirement for the state transition is the current char
 Ã¢ÂˆÂ§ItÃ¢ÂˆÂ‹S # Make "S" equal to one of the new states
 &hb # Behead the string (remove first char)
 ;B,S # Add B (the state transitions) and S (the new state)
 Ã¢Â†Â° # recur this function

Try it online!

answered Sep 5 at 9:53

Kroppeb

90628

add a commentÂ |Â

up vote
4
down vote

Brachylog, 42 bytes

,0hÃ¡ÂºÂ¸&tÃ¡ÂµÂ˜

input as [string, nfa]
where nfa is a list of state transitions [ initial state, letter, new states as list ]

Explanation

,0 # Append 0 to the input (initial state)
 Ã¡ÂµÂ˜ # Find all unique outputs
 h # if first element (string)
 Ã¡ÂºÂ¸ # is empty
 &t # then: return last element (current state)
 | # else:
 Ã¢ÂˆÂ‹Ã¢Â‚ÂB # save the state transitions in "B"
 Ã¢ÂˆÂ‹I # take one of these transitions, save in "I"
 hJ # take the initial state requirement, store in "J"
 &tJ # make sure "J" is actually the current state
 &hhC # Save first char of string in C
 Ã¢ÂˆÂ§IÃ¢ÂˆÂ‹Ã¢Â‚ÂC # make sure the char requirement for the state transition is the current char
 Ã¢ÂˆÂ§ItÃ¢ÂˆÂ‹S # Make "S" equal to one of the new states
 &hb # Behead the string (remove first char)
 ;B,S # Add B (the state transitions) and S (the new state)
 Ã¢Â†Â° # recur this function

Try it online!

answered Sep 5 at 9:53

Kroppeb

90628

Brachylog, 42 bytes

,0hÃ¡ÂºÂ¸&tÃ¡ÂµÂ˜

input as [string, nfa]
where nfa is a list of state transitions [ initial state, letter, new states as list ]

Explanation

,0 # Append 0 to the input (initial state)
 Ã¡ÂµÂ˜ # Find all unique outputs
 h # if first element (string)
 Ã¡ÂºÂ¸ # is empty
 &t # then: return last element (current state)
 | # else:
 Ã¢ÂˆÂ‹Ã¢Â‚ÂB # save the state transitions in "B"
 Ã¢ÂˆÂ‹I # take one of these transitions, save in "I"
 hJ # take the initial state requirement, store in "J"
 &tJ # make sure "J" is actually the current state
 &hhC # Save first char of string in C
 Ã¢ÂˆÂ§IÃ¢ÂˆÂ‹Ã¢Â‚ÂC # make sure the char requirement for the state transition is the current char
 Ã¢ÂˆÂ§ItÃ¢ÂˆÂ‹S # Make "S" equal to one of the new states
 &hb # Behead the string (remove first char)
 ;B,S # Add B (the state transitions) and S (the new state)
 Ã¢Â†Â° # recur this function

Try it online!

answered Sep 5 at 9:53

Kroppeb

90628

answered Sep 5 at 9:53

Kroppeb

90628

answered Sep 5 at 9:53

Kroppeb

90628

answered Sep 5 at 9:53

Kroppeb

90628

add a commentÂ |Â

up vote
3
down vote

Python 3, 103 80 bytes

thanks to @BWO

w=lambda n,f,a=0:w(n,f[1:],y for(x,c,y)in n if c==f[0]andx&a)if''<f else a

TIO

Previous "elegant" list comprehension(103 bytes):

def w(a,b):
 q=[0]
 for c in b:q=[j for s in q for i in a if s in i if i[1]==c for j in i[2]]
 return q

edited Sep 4 at 23:45

answered Sep 4 at 19:23

Quintec

25118

Shame that Python 3 lacks reduce.. But using recursion and actual sets still brings you down to 80 bytes.
â€“Â BWO
Sep 4 at 21:43

@BWO nice, thanks, haha btw the above is my new favorite example python code to show... one line giant list comprehensions amuse me way more than they should
â€“Â Quintec
Sep 4 at 22:06

I think you can save 2 bytes by replacing if''<f with if f.
â€“Â Chas Brown
Sep 5 at 19:17

@Chas Brown that fails if f is a falsy value such as empty string
â€“Â Quintec
Sep 5 at 19:24

Actually, what am I saying, ignore that
â€“Â Quintec
Sep 5 at 19:25

add a commentÂ |Â

up vote
3
down vote

Python 3, 103 80 bytes

thanks to @BWO

w=lambda n,f,a=0:w(n,f[1:],y for(x,c,y)in n if c==f[0]andx&a)if''<f else a

TIO

Previous "elegant" list comprehension(103 bytes):

def w(a,b):
 q=[0]
 for c in b:q=[j for s in q for i in a if s in i if i[1]==c for j in i[2]]
 return q

edited Sep 4 at 23:45

answered Sep 4 at 19:23

Quintec

25118

Shame that Python 3 lacks reduce.. But using recursion and actual sets still brings you down to 80 bytes.
â€“Â BWO
Sep 4 at 21:43

@BWO nice, thanks, haha btw the above is my new favorite example python code to show... one line giant list comprehensions amuse me way more than they should
â€“Â Quintec
Sep 4 at 22:06

I think you can save 2 bytes by replacing if''<f with if f.
â€“Â Chas Brown
Sep 5 at 19:17

@Chas Brown that fails if f is a falsy value such as empty string
â€“Â Quintec
Sep 5 at 19:24

Actually, what am I saying, ignore that
â€“Â Quintec
Sep 5 at 19:25

add a commentÂ |Â

up vote
3
down vote

Python 3, 103 80 bytes

thanks to @BWO

w=lambda n,f,a=0:w(n,f[1:],y for(x,c,y)in n if c==f[0]andx&a)if''<f else a

TIO

Previous "elegant" list comprehension(103 bytes):

def w(a,b):
 q=[0]
 for c in b:q=[j for s in q for i in a if s in i if i[1]==c for j in i[2]]
 return q

edited Sep 4 at 23:45

answered Sep 4 at 19:23

Quintec

25118

Python 3, 103 80 bytes

thanks to @BWO

w=lambda n,f,a=0:w(n,f[1:],y for(x,c,y)in n if c==f[0]andx&a)if''<f else a

TIO

Previous "elegant" list comprehension(103 bytes):

def w(a,b):
 q=[0]
 for c in b:q=[j for s in q for i in a if s in i if i[1]==c for j in i[2]]
 return q

edited Sep 4 at 23:45

answered Sep 4 at 19:23

Quintec

25118

edited Sep 4 at 23:45

answered Sep 4 at 19:23

Quintec

25118

answered Sep 4 at 19:23

Quintec

25118

answered Sep 4 at 19:23

Quintec

25118

Shame that Python 3 lacks reduce.. But using recursion and actual sets still brings you down to 80 bytes.
â€“Â BWO
Sep 4 at 21:43

@BWO nice, thanks, haha btw the above is my new favorite example python code to show... one line giant list comprehensions amuse me way more than they should
â€“Â Quintec
Sep 4 at 22:06

I think you can save 2 bytes by replacing if''<f with if f.
â€“Â Chas Brown
Sep 5 at 19:17

@Chas Brown that fails if f is a falsy value such as empty string
â€“Â Quintec
Sep 5 at 19:24

Actually, what am I saying, ignore that
â€“Â Quintec
Sep 5 at 19:25

add a commentÂ |Â

Shame that Python 3 lacks reduce.. But using recursion and actual sets still brings you down to 80 bytes.
â€“Â BWO
Sep 4 at 21:43

@BWO nice, thanks, haha btw the above is my new favorite example python code to show... one line giant list comprehensions amuse me way more than they should
â€“Â Quintec
Sep 4 at 22:06

I think you can save 2 bytes by replacing if''<f with if f.
â€“Â Chas Brown
Sep 5 at 19:17

@Chas Brown that fails if f is a falsy value such as empty string
â€“Â Quintec
Sep 5 at 19:24

Actually, what am I saying, ignore that
â€“Â Quintec
Sep 5 at 19:25

Shame that Python 3 lacks reduce.. But using recursion and actual sets still brings you down to 80 bytes.
â€“Â BWO
Sep 4 at 21:43

@BWO nice, thanks, haha btw the above is my new favorite example python code to show... one line giant list comprehensions amuse me way more than they should
â€“Â Quintec
Sep 4 at 22:06

I think you can save 2 bytes by replacing if''<f with if f.
â€“Â Chas Brown
Sep 5 at 19:17

@Chas Brown that fails if f is a falsy value such as empty string
â€“Â Quintec
Sep 5 at 19:24

Actually, what am I saying, ignore that
â€“Â Quintec
Sep 5 at 19:25

add a commentÂ |Â

up vote
3
down vote

JavaScript (ES6), 99 bytes

Takes input as (nfa)(string). Returns a Set.

a=>g=([c,...b],s=[0])=>c?g(b,a.reduce((p,[x,y,z])=>s.includes(x)&y==c?[...p,...z]:p,)):new Set(s)

Try it online!

edited Sep 5 at 6:33

answered Sep 4 at 16:45

Arnauld

63.7k580268

add a commentÂ |Â

up vote
3
down vote

JavaScript (ES6), 99 bytes

Takes input as (nfa)(string). Returns a Set.

a=>g=([c,...b],s=[0])=>c?g(b,a.reduce((p,[x,y,z])=>s.includes(x)&y==c?[...p,...z]:p,)):new Set(s)

Try it online!

edited Sep 5 at 6:33

answered Sep 4 at 16:45

Arnauld

63.7k580268

add a commentÂ |Â

up vote
3
down vote

JavaScript (ES6), 99 bytes

Takes input as (nfa)(string). Returns a Set.

a=>g=([c,...b],s=[0])=>c?g(b,a.reduce((p,[x,y,z])=>s.includes(x)&y==c?[...p,...z]:p,)):new Set(s)

Try it online!

edited Sep 5 at 6:33

answered Sep 4 at 16:45

Arnauld

63.7k580268

JavaScript (ES6), 99 bytes

Takes input as (nfa)(string). Returns a Set.

a=>g=([c,...b],s=[0])=>c?g(b,a.reduce((p,[x,y,z])=>s.includes(x)&y==c?[...p,...z]:p,)):new Set(s)

Try it online!

edited Sep 5 at 6:33

answered Sep 4 at 16:45

Arnauld

63.7k580268

edited Sep 5 at 6:33

answered Sep 4 at 16:45

Arnauld

63.7k580268

answered Sep 4 at 16:45

Arnauld

63.7k580268

answered Sep 4 at 16:45

Arnauld

63.7k580268

add a commentÂ |Â

up vote
3
down vote

R, 81 bytes

function(a,b,e,s)Reduce(function(A,x)unique(e[a%in%A&b==x]),el(strsplit(s,"")),0)

Try it online!

Straightforward answer using Reduce. Takes rules as three vectors of state, symbol, new-states called a,b,e.

Rules are separate (eg. rule 0,'a',[1,2] is 0,'a',1 and 0,'a',2).

answered Sep 5 at 19:36

JayCe

2,339415

add a commentÂ |Â

up vote
3
down vote

R, 81 bytes

function(a,b,e,s)Reduce(function(A,x)unique(e[a%in%A&b==x]),el(strsplit(s,"")),0)

Try it online!

Straightforward answer using Reduce. Takes rules as three vectors of state, symbol, new-states called a,b,e.

Rules are separate (eg. rule 0,'a',[1,2] is 0,'a',1 and 0,'a',2).

answered Sep 5 at 19:36

JayCe

2,339415

add a commentÂ |Â

up vote
3
down vote

R, 81 bytes

function(a,b,e,s)Reduce(function(A,x)unique(e[a%in%A&b==x]),el(strsplit(s,"")),0)

Try it online!

Straightforward answer using Reduce. Takes rules as three vectors of state, symbol, new-states called a,b,e.

Rules are separate (eg. rule 0,'a',[1,2] is 0,'a',1 and 0,'a',2).

answered Sep 5 at 19:36

JayCe

2,339415

R, 81 bytes

function(a,b,e,s)Reduce(function(A,x)unique(e[a%in%A&b==x]),el(strsplit(s,"")),0)

Try it online!

Straightforward answer using Reduce. Takes rules as three vectors of state, symbol, new-states called a,b,e.

Rules are separate (eg. rule 0,'a',[1,2] is 0,'a',1 and 0,'a',2).

answered Sep 5 at 19:36

JayCe

2,339415

answered Sep 5 at 19:36

JayCe

2,339415

answered Sep 5 at 19:36

JayCe

2,339415

answered Sep 5 at 19:36

JayCe

2,339415

add a commentÂ |Â

up vote
3
down vote

Brachylog v2, 31 bytes

b,ÃˆÂ®,ÃˆÂ®cÃ¢Â†Â”,0Ã¢Â†Â”Ã„Â¡Ã¢Â‚ÂƒkH&hg;HzÃ¢ÂˆÂ‹Ã¡ÂµÂˆÃ¡ÂµÂttÃ¡ÂµÂ˜

Try it online! (or with a more complex example)

Brachylog is really good at this sort of problem, and really bad at problems that require two separate inputs and an output. Almost all of this program is just plumbing.

Explanation

b,ÃˆÂ®,ÃˆÂ®cÃ¢Â†Â”,0Ã¢Â†Â”Ã„Â¡Ã¢Â‚ÂƒkH&hg;HzÃ¢ÂˆÂ‹Ã¡ÂµÂˆÃ¡ÂµÂttÃ¡ÂµÂ˜
 Ã¡ÂµÂ˜ Find all distinct outputs that can result from:
 b taking the input minus its first element,
 ,ÃˆÂ® appending a singleton list (i.e. an element)
 ,ÃˆÂ® then appending that same element again
 and transposing;
 c then concatenating the resulting lists,
 Ã¢Â†Â”,0Ã¢Â†Â” prepending a 0,
 Ã„Â¡Ã¢Â‚Âƒ grouping into blocks of 3 elements
 k (and discarding the last, incomplete, block),
 H& storing that while we
 h take the first input element,
 g z pair a copy of it with each element of
 ;H the stored value,
 Ã¡ÂµÂ assert that for each resulting element
 Ã¢ÂˆÂ‹Ã¡ÂµÂˆ its first element contains the second,
 Ã¡ÂµÂˆ Ã¡ÂµÂ returning the list of second elements,
 t then taking the last element of
 t the last element.

It's probably easier to follow this by looking at what some partial versions of the program would produce. Using the following input each time:

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]

we can observe the outputs of some prefixes of this program:

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,ÃˆÂ®,ÃˆÂ®
[[97,98,97,97,98],L,L]

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,ÃˆÂ®,ÃˆÂ®
[[97,A,A],[98,B,B],[97,C,C],[97,D,D],[98,E,E]]

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,ÃˆÂ®,ÃˆÂ®cÃ¢Â†Â”,0Ã¢Â†Â”
[0,97,A,A,98,B,B,97,C,C,97,D,D,98,E,E]

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,ÃˆÂ®,ÃˆÂ®cÃ¢Â†Â”,0Ã¢Â†Â”Ã„Â¡Ã¢Â‚Âƒk
[[0,97,A],[A,98,B],[B,97,C],[C,97,D],[D,98,E]]

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,ÃˆÂ®,ÃˆÂ®cÃ¢Â†Â”,0Ã¢Â†Â”Ã„Â¡Ã¢Â‚ÂƒkH&hg;Hz
[[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[0,97,A]],
 [[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[A,98,B]],
 [[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[B,97,C]],
 [[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[C,97,D]],
 [[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[D,98,E]]]

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,ÃˆÂ®,ÃˆÂ®cÃ¢Â†Â”,0Ã¢Â†Â”Ã„Â¡Ã¢Â‚ÂƒkH&hg;HzÃ¢ÂˆÂ‹Ã¡ÂµÂˆÃ¡ÂµÂ
e.g. [[0,97,1],[1,98,1],[1,97,0],[0,97,1],[1,98,1]]

Possible improvements

edited Sep 6 at 20:40

community wiki

2 revs
ais523

Ã¢ÂˆÂ‹Ã¡ÂµÂˆÃ¡ÂµÂ doesn't parse because it is implemented such that multi-character meta-predicate names could in theory be used (if we ran out of single-symbol possibilities). In practice it's not currently used.
â€“Â Fatalize
Sep 7 at 6:52

add a commentÂ |Â

up vote
3
down vote

Brachylog v2, 31 bytes

b,ÃˆÂ®,ÃˆÂ®cÃ¢Â†Â”,0Ã¢Â†Â”Ã„Â¡Ã¢Â‚ÂƒkH&hg;HzÃ¢ÂˆÂ‹Ã¡ÂµÂˆÃ¡ÂµÂttÃ¡ÂµÂ˜

Try it online! (or with a more complex example)

Brachylog is really good at this sort of problem, and really bad at problems that require two separate inputs and an output. Almost all of this program is just plumbing.

Explanation

b,ÃˆÂ®,ÃˆÂ®cÃ¢Â†Â”,0Ã¢Â†Â”Ã„Â¡Ã¢Â‚ÂƒkH&hg;HzÃ¢ÂˆÂ‹Ã¡ÂµÂˆÃ¡ÂµÂttÃ¡ÂµÂ˜
 Ã¡ÂµÂ˜ Find all distinct outputs that can result from:
 b taking the input minus its first element,
 ,ÃˆÂ® appending a singleton list (i.e. an element)
 ,ÃˆÂ® then appending that same element again
 and transposing;
 c then concatenating the resulting lists,
 Ã¢Â†Â”,0Ã¢Â†Â” prepending a 0,
 Ã„Â¡Ã¢Â‚Âƒ grouping into blocks of 3 elements
 k (and discarding the last, incomplete, block),
 H& storing that while we
 h take the first input element,
 g z pair a copy of it with each element of
 ;H the stored value,
 Ã¡ÂµÂ assert that for each resulting element
 Ã¢ÂˆÂ‹Ã¡ÂµÂˆ its first element contains the second,
 Ã¡ÂµÂˆ Ã¡ÂµÂ returning the list of second elements,
 t then taking the last element of
 t the last element.

It's probably easier to follow this by looking at what some partial versions of the program would produce. Using the following input each time:

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]

we can observe the outputs of some prefixes of this program:

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,ÃˆÂ®,ÃˆÂ®
[[97,98,97,97,98],L,L]

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,ÃˆÂ®,ÃˆÂ®
[[97,A,A],[98,B,B],[97,C,C],[97,D,D],[98,E,E]]

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,ÃˆÂ®,ÃˆÂ®cÃ¢Â†Â”,0Ã¢Â†Â”
[0,97,A,A,98,B,B,97,C,C,97,D,D,98,E,E]

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,ÃˆÂ®,ÃˆÂ®cÃ¢Â†Â”,0Ã¢Â†Â”Ã„Â¡Ã¢Â‚Âƒk
[[0,97,A],[A,98,B],[B,97,C],[C,97,D],[D,98,E]]

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,ÃˆÂ®,ÃˆÂ®cÃ¢Â†Â”,0Ã¢Â†Â”Ã„Â¡Ã¢Â‚ÂƒkH&hg;Hz
[[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[0,97,A]],
 [[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[A,98,B]],
 [[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[B,97,C]],
 [[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[C,97,D]],
 [[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[D,98,E]]]

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,ÃˆÂ®,ÃˆÂ®cÃ¢Â†Â”,0Ã¢Â†Â”Ã„Â¡Ã¢Â‚ÂƒkH&hg;HzÃ¢ÂˆÂ‹Ã¡ÂµÂˆÃ¡ÂµÂ
e.g. [[0,97,1],[1,98,1],[1,97,0],[0,97,1],[1,98,1]]

Possible improvements

edited Sep 6 at 20:40

community wiki

2 revs
ais523

Ã¢ÂˆÂ‹Ã¡ÂµÂˆÃ¡ÂµÂ doesn't parse because it is implemented such that multi-character meta-predicate names could in theory be used (if we ran out of single-symbol possibilities). In practice it's not currently used.
â€“Â Fatalize
Sep 7 at 6:52

add a commentÂ |Â

up vote
3
down vote

Brachylog v2, 31 bytes

b,ÃˆÂ®,ÃˆÂ®cÃ¢Â†Â”,0Ã¢Â†Â”Ã„Â¡Ã¢Â‚ÂƒkH&hg;HzÃ¢ÂˆÂ‹Ã¡ÂµÂˆÃ¡ÂµÂttÃ¡ÂµÂ˜

Try it online! (or with a more complex example)

Brachylog is really good at this sort of problem, and really bad at problems that require two separate inputs and an output. Almost all of this program is just plumbing.

Explanation

b,ÃˆÂ®,ÃˆÂ®cÃ¢Â†Â”,0Ã¢Â†Â”Ã„Â¡Ã¢Â‚ÂƒkH&hg;HzÃ¢ÂˆÂ‹Ã¡ÂµÂˆÃ¡ÂµÂttÃ¡ÂµÂ˜
 Ã¡ÂµÂ˜ Find all distinct outputs that can result from:
 b taking the input minus its first element,
 ,ÃˆÂ® appending a singleton list (i.e. an element)
 ,ÃˆÂ® then appending that same element again
 and transposing;
 c then concatenating the resulting lists,
 Ã¢Â†Â”,0Ã¢Â†Â” prepending a 0,
 Ã„Â¡Ã¢Â‚Âƒ grouping into blocks of 3 elements
 k (and discarding the last, incomplete, block),
 H& storing that while we
 h take the first input element,
 g z pair a copy of it with each element of
 ;H the stored value,
 Ã¡ÂµÂ assert that for each resulting element
 Ã¢ÂˆÂ‹Ã¡ÂµÂˆ its first element contains the second,
 Ã¡ÂµÂˆ Ã¡ÂµÂ returning the list of second elements,
 t then taking the last element of
 t the last element.

It's probably easier to follow this by looking at what some partial versions of the program would produce. Using the following input each time:

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]

we can observe the outputs of some prefixes of this program:

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,ÃˆÂ®,ÃˆÂ®
[[97,98,97,97,98],L,L]

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,ÃˆÂ®,ÃˆÂ®
[[97,A,A],[98,B,B],[97,C,C],[97,D,D],[98,E,E]]

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,ÃˆÂ®,ÃˆÂ®cÃ¢Â†Â”,0Ã¢Â†Â”
[0,97,A,A,98,B,B,97,C,C,97,D,D,98,E,E]

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,ÃˆÂ®,ÃˆÂ®cÃ¢Â†Â”,0Ã¢Â†Â”Ã„Â¡Ã¢Â‚Âƒk
[[0,97,A],[A,98,B],[B,97,C],[C,97,D],[D,98,E]]

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,ÃˆÂ®,ÃˆÂ®cÃ¢Â†Â”,0Ã¢Â†Â”Ã„Â¡Ã¢Â‚ÂƒkH&hg;Hz
[[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[0,97,A]],
 [[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[A,98,B]],
 [[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[B,97,C]],
 [[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[C,97,D]],
 [[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[D,98,E]]]

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,ÃˆÂ®,ÃˆÂ®cÃ¢Â†Â”,0Ã¢Â†Â”Ã„Â¡Ã¢Â‚ÂƒkH&hg;HzÃ¢ÂˆÂ‹Ã¡ÂµÂˆÃ¡ÂµÂ
e.g. [[0,97,1],[1,98,1],[1,97,0],[0,97,1],[1,98,1]]

Possible improvements

edited Sep 6 at 20:40

community wiki

2 revs
ais523

Brachylog v2, 31 bytes

b,ÃˆÂ®,ÃˆÂ®cÃ¢Â†Â”,0Ã¢Â†Â”Ã„Â¡Ã¢Â‚ÂƒkH&hg;HzÃ¢ÂˆÂ‹Ã¡ÂµÂˆÃ¡ÂµÂttÃ¡ÂµÂ˜

Try it online! (or with a more complex example)

Brachylog is really good at this sort of problem, and really bad at problems that require two separate inputs and an output. Almost all of this program is just plumbing.

Explanation

b,ÃˆÂ®,ÃˆÂ®cÃ¢Â†Â”,0Ã¢Â†Â”Ã„Â¡Ã¢Â‚ÂƒkH&hg;HzÃ¢ÂˆÂ‹Ã¡ÂµÂˆÃ¡ÂµÂttÃ¡ÂµÂ˜
 Ã¡ÂµÂ˜ Find all distinct outputs that can result from:
 b taking the input minus its first element,
 ,ÃˆÂ® appending a singleton list (i.e. an element)
 ,ÃˆÂ® then appending that same element again
 and transposing;
 c then concatenating the resulting lists,
 Ã¢Â†Â”,0Ã¢Â†Â” prepending a 0,
 Ã„Â¡Ã¢Â‚Âƒ grouping into blocks of 3 elements
 k (and discarding the last, incomplete, block),
 H& storing that while we
 h take the first input element,
 g z pair a copy of it with each element of
 ;H the stored value,
 Ã¡ÂµÂ assert that for each resulting element
 Ã¢ÂˆÂ‹Ã¡ÂµÂˆ its first element contains the second,
 Ã¡ÂµÂˆ Ã¡ÂµÂ returning the list of second elements,
 t then taking the last element of
 t the last element.

It's probably easier to follow this by looking at what some partial versions of the program would produce. Using the following input each time:

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]

we can observe the outputs of some prefixes of this program:

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,ÃˆÂ®,ÃˆÂ®
[[97,98,97,97,98],L,L]

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,ÃˆÂ®,ÃˆÂ®
[[97,A,A],[98,B,B],[97,C,C],[97,D,D],[98,E,E]]

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,ÃˆÂ®,ÃˆÂ®cÃ¢Â†Â”,0Ã¢Â†Â”
[0,97,A,A,98,B,B,97,C,C,97,D,D,98,E,E]

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,ÃˆÂ®,ÃˆÂ®cÃ¢Â†Â”,0Ã¢Â†Â”Ã„Â¡Ã¢Â‚Âƒk
[[0,97,A],[A,98,B],[B,97,C],[C,97,D],[D,98,E]]

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,ÃˆÂ®,ÃˆÂ®cÃ¢Â†Â”,0Ã¢Â†Â”Ã„Â¡Ã¢Â‚ÂƒkH&hg;Hz
[[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[0,97,A]],
 [[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[A,98,B]],
 [[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[B,97,C]],
 [[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[C,97,D]],
 [[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[D,98,E]]]

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,ÃˆÂ®,ÃˆÂ®cÃ¢Â†Â”,0Ã¢Â†Â”Ã„Â¡Ã¢Â‚ÂƒkH&hg;HzÃ¢ÂˆÂ‹Ã¡ÂµÂˆÃ¡ÂµÂ
e.g. [[0,97,1],[1,98,1],[1,97,0],[0,97,1],[1,98,1]]

Possible improvements

edited Sep 6 at 20:40

community wiki

2 revs
ais523

edited Sep 6 at 20:40

community wiki

2 revs
ais523

community wiki

2 revs
ais523

community wiki

2 revs
ais523

Ã¢ÂˆÂ‹Ã¡ÂµÂˆÃ¡ÂµÂ doesn't parse because it is implemented such that multi-character meta-predicate names could in theory be used (if we ran out of single-symbol possibilities). In practice it's not currently used.
â€“Â Fatalize
Sep 7 at 6:52

add a commentÂ |Â

Ã¢ÂˆÂ‹Ã¡ÂµÂˆÃ¡ÂµÂ doesn't parse because it is implemented such that multi-character meta-predicate names could in theory be used (if we ran out of single-symbol possibilities). In practice it's not currently used.
â€“Â Fatalize
Sep 7 at 6:52

Ã¢ÂˆÂ‹Ã¡ÂµÂˆÃ¡ÂµÂ doesn't parse because it is implemented such that multi-character meta-predicate names could in theory be used (if we ran out of single-symbol possibilities). In practice it's not currently used.
â€“Â Fatalize
Sep 7 at 6:52

add a commentÂ |Â

up vote
2
down vote

Coconut, 64 bytes

d->reduce$((s,c)->r for(*y,r)in d for S in s if[S,c]==y,?,0)

Try it online!

answered Sep 4 at 16:59

ovs

17.3k21056

add a commentÂ |Â

up vote
2
down vote

Coconut, 64 bytes

d->reduce$((s,c)->r for(*y,r)in d for S in s if[S,c]==y,?,0)

Try it online!

answered Sep 4 at 16:59

ovs

17.3k21056

add a commentÂ |Â

up vote
2
down vote

Coconut, 64 bytes

d->reduce$((s,c)->r for(*y,r)in d for S in s if[S,c]==y,?,0)

Try it online!

answered Sep 4 at 16:59

ovs

17.3k21056

Coconut, 64 bytes

d->reduce$((s,c)->r for(*y,r)in d for S in s if[S,c]==y,?,0)

Try it online!

answered Sep 4 at 16:59

ovs

17.3k21056

answered Sep 4 at 16:59

ovs

17.3k21056

answered Sep 4 at 16:59

ovs

17.3k21056

answered Sep 4 at 16:59

ovs

17.3k21056

add a commentÂ |Â

up vote
2
down vote

Clean, 68 bytes

This one based on ovs's Haskell solution is a bit shorter than my initial approach was.

now includes a test harness

import StdEnv
?d=foldl(s c=removeDup[r\(y,r)<-d,g<-s|(g,c)==y])[0]

Try it online!

edited Sep 5 at 0:30

answered Sep 4 at 23:08

ÃŽÂŸurous

5,2131931

1

@BWO Test harness added
â€“Â ÃŽÂŸurous
Sep 4 at 23:47

add a commentÂ |Â

up vote
2
down vote

Clean, 68 bytes

This one based on ovs's Haskell solution is a bit shorter than my initial approach was.

now includes a test harness

import StdEnv
?d=foldl(s c=removeDup[r\(y,r)<-d,g<-s|(g,c)==y])[0]

Try it online!

edited Sep 5 at 0:30

answered Sep 4 at 23:08

ÃŽÂŸurous

5,2131931

1

@BWO Test harness added
â€“Â ÃŽÂŸurous
Sep 4 at 23:47

add a commentÂ |Â

up vote
2
down vote

Clean, 68 bytes

This one based on ovs's Haskell solution is a bit shorter than my initial approach was.

now includes a test harness

import StdEnv
?d=foldl(s c=removeDup[r\(y,r)<-d,g<-s|(g,c)==y])[0]

Try it online!

edited Sep 5 at 0:30

answered Sep 4 at 23:08

ÃŽÂŸurous

5,2131931

Clean, 68 bytes

This one based on ovs's Haskell solution is a bit shorter than my initial approach was.

now includes a test harness

import StdEnv
?d=foldl(s c=removeDup[r\(y,r)<-d,g<-s|(g,c)==y])[0]

Try it online!

edited Sep 5 at 0:30

answered Sep 4 at 23:08

ÃŽÂŸurous

5,2131931

edited Sep 5 at 0:30

answered Sep 4 at 23:08

ÃŽÂŸurous

5,2131931

answered Sep 4 at 23:08

ÃŽÂŸurous

5,2131931

answered Sep 4 at 23:08

ÃŽÂŸurous

5,2131931

1

@BWO Test harness added
â€“Â ÃŽÂŸurous
Sep 4 at 23:47

add a commentÂ |Â

1

@BWO Test harness added
â€“Â ÃŽÂŸurous
Sep 4 at 23:47

@BWO Test harness added
â€“Â ÃŽÂŸurous
Sep 4 at 23:47

add a commentÂ |Â

up vote
1
down vote

Perl 6, 61 bytes

$s.comb

Try it online!

edited Sep 5 at 2:12

answered Sep 5 at 1:36

nwellnhof

3,503714

add a commentÂ |Â

up vote
1
down vote

Perl 6, 61 bytes

$s.comb

Try it online!

edited Sep 5 at 2:12

answered Sep 5 at 1:36

nwellnhof

3,503714

add a commentÂ |Â

up vote
1
down vote

Perl 6, 61 bytes

$s.comb

Try it online!

edited Sep 5 at 2:12

answered Sep 5 at 1:36

nwellnhof

3,503714

Perl 6, 61 bytes

$s.comb

Try it online!

edited Sep 5 at 2:12

answered Sep 5 at 1:36

nwellnhof

3,503714

edited Sep 5 at 2:12

answered Sep 5 at 1:36

nwellnhof

3,503714

answered Sep 5 at 1:36

nwellnhof

3,503714

answered Sep 5 at 1:36

nwellnhof

3,503714

add a commentÂ |Â

up vote
1
down vote

Charcoal, 44 bytes

Ã¢ÂŠÂžÃÂ…Ã¢ÂÂ°Ã¯Â¼Â¦ÃŽÂ·Ã‚Â«Ã¢Â‰Â”ÃÂ…ÃŽÂ¶Ã¢Â‰Â”Ã¢ÂŸÂ¦Ã¢ÂŸÂ§ÃÂ…Ã¯Â¼Â¦ÃŽÂ¶Ã¯Â¼Â¦ÃŽÂ¸Ã‚Â¿Ã¢ÂˆÂ§Ã¢ÂÂ¼Ã‚Â§ÃŽÂ»Ã¢ÂÂ°ÃŽÂºÃ¢ÂÂ¼Ã‚Â§ÃŽÂ»Ã‚Â¹ÃŽÂ¹Ã¯Â¼Â¦Ã‚Â§ÃŽÂ»Ã‚Â²Ã‚Â¿Ã‚Â¬Ã¢Â„Â–ÃÂ…ÃŽÂ¼Ã¢ÂŠÂžÃÂ…ÃŽÂ¼Ã‚Â»Ã¯Â¼Â©ÃÂ…

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

Ã¢ÂŠÂžÃÂ…Ã¢ÂÂ°

Push 0 to the predefined empty list to set the inital state to $0$.

Ã¯Â¼Â¦ÃŽÂ·Ã‚Â«

Loop over the input.

Ã¢Â‰Â”ÃÂ…ÃŽÂ¶

Copy the state.

Ã¢Â‰Â”Ã¢ÂŸÂ¦Ã¢ÂŸÂ§ÃÂ…

Reset the state.

Ã¯Â¼Â¦ÃŽÂ¶

Loop over the copy of the state.

Ã¯Â¼Â¦ÃŽÂ¸

Loop over the NFA entries.

Ã‚Â¿Ã¢ÂˆÂ§Ã¢ÂÂ¼Ã‚Â§ÃŽÂ»Ã¢ÂÂ°ÃŽÂºÃ¢ÂÂ¼Ã‚Â§ÃŽÂ»Ã‚Â¹ÃŽÂ¹

If the entry matches, then...

Ã¯Â¼Â¦Ã‚Â§ÃŽÂ»Ã‚Â²

... loop over the new states...

Ã‚Â¿Ã‚Â¬Ã¢Â„Â–ÃÂ…ÃŽÂ¼

.... if they are not already in the list...

Ã¢ÂŠÂžÃÂ…ÃŽÂ¼Ã‚Â»

... add them to the list.

Ã¯Â¼Â©ÃÂ…

Cast the list of states to string for implicit output on separate lines.

answered Sep 5 at 19:29

Neil

75.1k744170

add a commentÂ |Â

up vote
1
down vote

Charcoal, 44 bytes

Ã¢ÂŠÂžÃÂ…Ã¢ÂÂ°Ã¯Â¼Â¦ÃŽÂ·Ã‚Â«Ã¢Â‰Â”ÃÂ…ÃŽÂ¶Ã¢Â‰Â”Ã¢ÂŸÂ¦Ã¢ÂŸÂ§ÃÂ…Ã¯Â¼Â¦ÃŽÂ¶Ã¯Â¼Â¦ÃŽÂ¸Ã‚Â¿Ã¢ÂˆÂ§Ã¢ÂÂ¼Ã‚Â§ÃŽÂ»Ã¢ÂÂ°ÃŽÂºÃ¢ÂÂ¼Ã‚Â§ÃŽÂ»Ã‚Â¹ÃŽÂ¹Ã¯Â¼Â¦Ã‚Â§ÃŽÂ»Ã‚Â²Ã‚Â¿Ã‚Â¬Ã¢Â„Â–ÃÂ…ÃŽÂ¼Ã¢ÂŠÂžÃÂ…ÃŽÂ¼Ã‚Â»Ã¯Â¼Â©ÃÂ…

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

Ã¢ÂŠÂžÃÂ…Ã¢ÂÂ°

Push 0 to the predefined empty list to set the inital state to $0$.

Ã¯Â¼Â¦ÃŽÂ·Ã‚Â«

Loop over the input.

Ã¢Â‰Â”ÃÂ…ÃŽÂ¶

Copy the state.

Ã¢Â‰Â”Ã¢ÂŸÂ¦Ã¢ÂŸÂ§ÃÂ…

Reset the state.

Ã¯Â¼Â¦ÃŽÂ¶

Loop over the copy of the state.

Ã¯Â¼Â¦ÃŽÂ¸

Loop over the NFA entries.

Ã‚Â¿Ã¢ÂˆÂ§Ã¢ÂÂ¼Ã‚Â§ÃŽÂ»Ã¢ÂÂ°ÃŽÂºÃ¢ÂÂ¼Ã‚Â§ÃŽÂ»Ã‚Â¹ÃŽÂ¹

If the entry matches, then...

Ã¯Â¼Â¦Ã‚Â§ÃŽÂ»Ã‚Â²

... loop over the new states...

Ã‚Â¿Ã‚Â¬Ã¢Â„Â–ÃÂ…ÃŽÂ¼

.... if they are not already in the list...

Ã¢ÂŠÂžÃÂ…ÃŽÂ¼Ã‚Â»

... add them to the list.

Ã¯Â¼Â©ÃÂ…

Cast the list of states to string for implicit output on separate lines.

answered Sep 5 at 19:29

Neil

75.1k744170

add a commentÂ |Â

up vote
1
down vote

Charcoal, 44 bytes

Ã¢ÂŠÂžÃÂ…Ã¢ÂÂ°Ã¯Â¼Â¦ÃŽÂ·Ã‚Â«Ã¢Â‰Â”ÃÂ…ÃŽÂ¶Ã¢Â‰Â”Ã¢ÂŸÂ¦Ã¢ÂŸÂ§ÃÂ…Ã¯Â¼Â¦ÃŽÂ¶Ã¯Â¼Â¦ÃŽÂ¸Ã‚Â¿Ã¢ÂˆÂ§Ã¢ÂÂ¼Ã‚Â§ÃŽÂ»Ã¢ÂÂ°ÃŽÂºÃ¢ÂÂ¼Ã‚Â§ÃŽÂ»Ã‚Â¹ÃŽÂ¹Ã¯Â¼Â¦Ã‚Â§ÃŽÂ»Ã‚Â²Ã‚Â¿Ã‚Â¬Ã¢Â„Â–ÃÂ…ÃŽÂ¼Ã¢ÂŠÂžÃÂ…ÃŽÂ¼Ã‚Â»Ã¯Â¼Â©ÃÂ…

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

Ã¢ÂŠÂžÃÂ…Ã¢ÂÂ°

Push 0 to the predefined empty list to set the inital state to $0$.

Ã¯Â¼Â¦ÃŽÂ·Ã‚Â«

Loop over the input.

Ã¢Â‰Â”ÃÂ…ÃŽÂ¶

Copy the state.

Ã¢Â‰Â”Ã¢ÂŸÂ¦Ã¢ÂŸÂ§ÃÂ…

Reset the state.

Ã¯Â¼Â¦ÃŽÂ¶

Loop over the copy of the state.

Ã¯Â¼Â¦ÃŽÂ¸

Loop over the NFA entries.

Ã‚Â¿Ã¢ÂˆÂ§Ã¢ÂÂ¼Ã‚Â§ÃŽÂ»Ã¢ÂÂ°ÃŽÂºÃ¢ÂÂ¼Ã‚Â§ÃŽÂ»Ã‚Â¹ÃŽÂ¹

If the entry matches, then...

Ã¯Â¼Â¦Ã‚Â§ÃŽÂ»Ã‚Â²

... loop over the new states...

Ã‚Â¿Ã‚Â¬Ã¢Â„Â–ÃÂ…ÃŽÂ¼

.... if they are not already in the list...

Ã¢ÂŠÂžÃÂ…ÃŽÂ¼Ã‚Â»

... add them to the list.

Ã¯Â¼Â©ÃÂ…

Cast the list of states to string for implicit output on separate lines.

answered Sep 5 at 19:29

Neil

75.1k744170

Charcoal, 44 bytes

Ã¢ÂŠÂžÃÂ…Ã¢ÂÂ°Ã¯Â¼Â¦ÃŽÂ·Ã‚Â«Ã¢Â‰Â”ÃÂ…ÃŽÂ¶Ã¢Â‰Â”Ã¢ÂŸÂ¦Ã¢ÂŸÂ§ÃÂ…Ã¯Â¼Â¦ÃŽÂ¶Ã¯Â¼Â¦ÃŽÂ¸Ã‚Â¿Ã¢ÂˆÂ§Ã¢ÂÂ¼Ã‚Â§ÃŽÂ»Ã¢ÂÂ°ÃŽÂºÃ¢ÂÂ¼Ã‚Â§ÃŽÂ»Ã‚Â¹ÃŽÂ¹Ã¯Â¼Â¦Ã‚Â§ÃŽÂ»Ã‚Â²Ã‚Â¿Ã‚Â¬Ã¢Â„Â–ÃÂ…ÃŽÂ¼Ã¢ÂŠÂžÃÂ…ÃŽÂ¼Ã‚Â»Ã¯Â¼Â©ÃÂ…

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

Ã¢ÂŠÂžÃÂ…Ã¢ÂÂ°

Push 0 to the predefined empty list to set the inital state to $0$.

Ã¯Â¼Â¦ÃŽÂ·Ã‚Â«

Loop over the input.

Ã¢Â‰Â”ÃÂ…ÃŽÂ¶

Copy the state.

Ã¢Â‰Â”Ã¢ÂŸÂ¦Ã¢ÂŸÂ§ÃÂ…

Reset the state.

Ã¯Â¼Â¦ÃŽÂ¶

Loop over the copy of the state.

Ã¯Â¼Â¦ÃŽÂ¸

Loop over the NFA entries.

Ã‚Â¿Ã¢ÂˆÂ§Ã¢ÂÂ¼Ã‚Â§ÃŽÂ»Ã¢ÂÂ°ÃŽÂºÃ¢ÂÂ¼Ã‚Â§ÃŽÂ»Ã‚Â¹ÃŽÂ¹

If the entry matches, then...

Ã¯Â¼Â¦Ã‚Â§ÃŽÂ»Ã‚Â²

... loop over the new states...

Ã‚Â¿Ã‚Â¬Ã¢Â„Â–ÃÂ…ÃŽÂ¼

.... if they are not already in the list...

Ã¢ÂŠÂžÃÂ…ÃŽÂ¼Ã‚Â»

... add them to the list.

Ã¯Â¼Â©ÃÂ…

Cast the list of states to string for implicit output on separate lines.

answered Sep 5 at 19:29

Neil

75.1k744170

answered Sep 5 at 19:29

Neil

75.1k744170

answered Sep 5 at 19:29

Neil

75.1k744170

answered Sep 5 at 19:29

Neil

75.1k744170

add a commentÂ |Â

draft saved

draft discarded

draft saved

draft discarded

Post as a guest

Name

Category

Random preview

Simulate an NFA

Formal Definition

Challenge

Example

Rules

Test cases

Formal Definition

Challenge

Example

Rules

Test cases

Formal Definition

Challenge

Example

Rules

Test cases

Formal Definition

Challenge

Example

Rules

Test cases

10 Answers 10

Haskell, 66 bytes

Brachylog, 42 bytes

Explanation

Python 3, 103 80 bytes

JavaScript (ES6), 99 bytes

R, 81 bytes

Brachylog v2, 31 bytes

Explanation

Possible improvements

Coconut, 64 bytes

Clean, 68 bytes

Perl 6, 61 bytes

Charcoal, 44 bytes

Your Answer

Sign up or log in

Post as a guest

Post as a guest

10 Answers 10

10 Answers 10

Haskell, 66 bytes

Haskell, 66 bytes

Haskell, 66 bytes

Haskell, 66 bytes

Brachylog, 42 bytes

Explanation

Brachylog, 42 bytes

Explanation

Brachylog, 42 bytes

Explanation

Brachylog, 42 bytes

Explanation

Python 3, 103 80 bytes

Python 3, 103 80 bytes

Python 3, 103 80 bytes

Python 3, 103 80 bytes

JavaScript (ES6), 99 bytes

JavaScript (ES6), 99 bytes

JavaScript (ES6), 99 bytes

JavaScript (ES6), 99 bytes

R, 81 bytes

R, 81 bytes

R, 81 bytes

R, 81 bytes

Brachylog v2, 31 bytes

Explanation

Possible improvements

Brachylog v2, 31 bytes

Explanation

Possible improvements

Brachylog v2, 31 bytes

Explanation

Possible improvements

Brachylog v2, 31 bytes

Explanation

Possible improvements

Coconut, 64 bytes

10 Answers
10

10 Answers
10

10 Answers
10