4
\$\begingroup\$

This question already has an answer here:

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

\$\endgroup\$

marked as duplicate by Mego, xnor code-golf Jan 15 '16 at 0:39

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 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\$ – Martin Ender Jan 14 '16 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\$ – Martin Ender Jan 14 '16 at 20:46
  • 4
    \$\begingroup\$ Never assume that we know. :P I know I don't know what a Finite State Machine is. \$\endgroup\$ – Addison Crump Jan 14 '16 at 20:47
  • 5
    \$\begingroup\$ This is not that related to finite state machines. It's just reachability in a directed graph. \$\endgroup\$ – feersum Jan 14 '16 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\$ – feersum Jan 14 '16 at 20:53
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>

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.