The basis for this problem is that you did to make an optimal pattern so that all inputted sequences will be "accepted" if they fit the rules of the problem and "rejected" if they break any of them.

.

Above are some examples of functions that can be performed. (A) shows a machine that will only accept the sequences that repeat 12 as you must begin at start and end on a red dot.

In (B) the "*" means you can pass along that route without an input there. So (B) accepts 1111122222, 22222, 1122 etc but doesn't accept any sequence in which there is a 1 after the 2.

In (C) you can move along either route to reach an end. So 12222 and 1333 are both accepted sequences.

All routes have to be either single digit or single letter. Obviously shorthand like "odd", "even" can be used in answers rather than drawing loads of arrows.


Problem #1

Make an optimal machine using digits 0-9 that only accepts sequences where the digits sum are even and rejects if they are odd.

  • 7
    These things are called Finite State Machines, and requiring the simplest FSM makes a great puzzle, so I guess this puzzle type is one of the rare cases that would be on topic both here and on PCG. Nicely done! – Bass Nov 14 at 11:38
up vote 9 down vote accepted

Would this work?

Left part is "odd", right part is "even".

enter image description here

  • Correct well done, stay tuned for some more (and harder) ones. – Ben Franks Nov 14 at 11:36

This works:

enter image description here
Here odd means 1,3,5,7,9 / and even means 0,2,4,6,8

  • Correct solution +1. But jafe did answer first so I have given him the solution point. – Ben Franks Nov 14 at 11:35

I believe this solution should work:

enter image description here Where even means "even digit" and odd means "odd digit". Left node is START.

  • You can shrink this by one state. – Gareth McCaughan Nov 14 at 11:17
  • I'm not sure you can, I'll give it a little thought. The other solutions have one fewer node but I'm not sure you can use the same node as start and end (because then an empty string would be a correct one?) – NudgeNudge Nov 14 at 11:18
  • Solution works but can be optimised to use less points. – Ben Franks Nov 14 at 11:36

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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