5
\$\begingroup\$

I've been around for a while, watching you golf and I really enjoy it. I came up with a challenge for you all so let's begin!

Challenge

I assume that everyone knows what Finite State Machine (FSM) is, I will edit the the description if needed.

  • Your program will take only one input consisting in a string that represents a FSM.
  • The first character of the input is the FSM's initial state and the last character is the FSM's final state.
  • Transitions are represented as two consecutive characters (AB will be the transition from state A to state B. ABCD will be the two transitions A to B and C to D)
  • In this challenge, the FSM is considered valid when you have at least one path from the initial state to the final state.

Goal

Output a truthy value, telling the world if the input is a valid FSM (any equivalent for True of False is fine)

Bonus

  • -20% if you add all the sequences of valid paths to the output

Examples

AB should output (with bonus) true AB

ABC should output false (No transition to state C)

ABCEBD should output (with bonus) true ABD (The presence of unreachable states C and E doesn't make it false)

ISSTSFTF should output (with bonus) true ISF ISTF

ABACBCCD should output (with bonus) true ACD ABCD

ABACBCD should output false

ABACADCDBCDEBE should output (with bonus) true ABE ADE ACDE ABCDE

Final word

If you think this challenge lacks something, please tell me, I'd really like to see the answers you can come up with

Improve this question
\$\endgroup\$
18
  • 3
    \$\begingroup\$ You should probably clarify that the transition pairs are not overlapping. So ABCD represents only two transitions A->B and C->D and not B->C. Otherwise the challenge would be trivial. \$\endgroup\$ Commented Jan 14, 2016 at 20:46
  • 1
    \$\begingroup\$ It would also be a good to have a truthy test case where some state other than the final state is not reachable. \$\endgroup\$ Commented Jan 14, 2016 at 20:46
  • 4
    \$\begingroup\$ Never assume that we know. :P I know I don't know what a Finite State Machine is. \$\endgroup\$ Commented Jan 14, 2016 at 20:47
  • 5
    \$\begingroup\$ This is not that related to finite state machines. It's just reachability in a directed graph. \$\endgroup\$ Commented Jan 14, 2016 at 20:50
  • 3
    \$\begingroup\$ Darn.. I looked in Peter Taylor's graph theory challenge index for a dupe target, but the entry under reachability was 'too many to mention'. \$\endgroup\$ Commented Jan 14, 2016 at 20:53

1 Answer 1

Reset to default
3
\$\begingroup\$

JavaScript (ES6), 81 bytes

s=>(a=[...s]).map(_=>a.map((m,i)=>p=i%2&r[s[i-1]]?r[m]=1:r[m]),r={},r[s[0]]=1)&&p

Explanation

Takes the states as a string and returns a 1 for true or undefined for false. This method was the shortest I could find, but it means that it's impossible to include the bonus because it just determines reachability, not the paths.

s=> (a=[...s]) // a = states as an array .map(_=> // loop a number of times to ensure all states have been reached a.map((m,i)=> // for each state m at index i p= // p = the reachability of the final state i%2 // if this is the last state of a pair &r[s[i-1]]? // and the first state is reachable r[m]=1 // set the last state and p to reachable :r[m] // else set p to the reachability of the state ), r={}, // map of truthy values for reachable states r[s[0]]=1 // set the initial state to reachable ) &&p // return the final result

Test

var solution = s=>(a=[...s]).map(_=>a.map((m,i)=>p=i%2&r[s[i-1]]?r[m]=1:r[m]),r={},r[s[0]]=1)&&p
<input type="text" id="input" value="ABACADCDBCDEBE" /> <button onclick="result.textContent=solution(input.value)">Go</button> <pre id="result"></pre>

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Nice one! I like the explanation. :) \$\endgroup\$ Commented Jan 14, 2016 at 23:16
  • \$\begingroup\$ @Askirkela Thanks. Nice first challenge, by the way! I enjoyed making this. \$\endgroup\$ Commented Jan 14, 2016 at 23:22

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.