#include <iostream>

class Switch
{
public:
  Switch(bool c, Switch* n = nullptr, Switch* p = nullptr)
    : conducting(c), next(n), prev(p) {}
  ~Switch() { delete next; }
  
  bool getConducting() const { return conducting; }
  void toggleConducting() { conducting = !conducting; }
  
  Switch*& getNext()
  {
    return next;
  }
  
  Switch*& getPrev()
  {
    return prev;
  }
  
private:
  Switch(Switch const&) = delete;
  Switch& operator=(Switch const&) = delete;
  
  bool conducting;
  Switch* next;
  Switch* prev;
};

class Circuit
{
public:
  Circuit() : start(nullptr), current(nullptr) {}
  ~Circuit() { delete start; }

  void add(bool state)
  {
    start = new Switch(state, start);
    if (start->getNext())
      start->getNext()->getPrev() = start;
  }
  
  void print(std::ostream& os) const
  {
    Switch* cur = start;
    while (cur != nullptr)
    {
      bool on = cur->getConducting();

      if (cur == current)
        os << (on ? 'i' : 'o');
      else
        os << on;

      cur = cur->getNext();
    }
  }

  bool goForward()
  {
    if (current && current->getNext())
      current = current->getNext();
    else if (current && !current->getNext())
      return false;
    else if (start)
      current = start;
    
    if (current)
      current->toggleConducting();

    return true;
  }

  void goBack()
  {
    if (current)
      current = current->getPrev();
    else
      current = nullptr;
    
    if (current)
      current->toggleConducting();
  }

  /* Solves the puzzle as it is now, from the position we are at now.
   * This solves the problem with minimal state information.
   * (more difficult than requirements on exam)
   */
  void solveCurrentState(std::ostream& os)
  {
    Switch* cur = current;

    /* Enter first switch. */
    if (cur == nullptr)
    {
      os << "f";
      cur = start;
    }

    /* Get to last switch. This would toggle all switches once - but
     * we do not do it! Every switch value will be opposite to what's
     * correct after this operation. */
    while (cur->getNext() != nullptr)
    {
      os << "f";
      cur = cur->getNext();
    }

    /* Keep track of above fact in a variable initiated to false
     * unless we already were on last position (cur will be last after
     * above loop) */
    bool is_even_toggled = (cur == current);
    /* Also keep track of when we pass the start (current) position on
     * our way back. From that point on we toggled the switches one
     * time less. */
    bool passed_once = (cur != current);

    /* Go back to start and make sure all switches in front are
     * "off" */
    while (cur != nullptr)
    {
      if (cur->getPrev() == current)
        passed_once = false;
      
      if (cur->getConducting() == is_even_toggled)
      {
        /* Current switch is "on", and was toggled an even number of
         * times on the way here, or it is "off" and was toggled an
         * odd number of times on the way here. So it will be "on",
         * and we need to go back, forth and back again to make it
         * "off". In the process we will toggle the previous switch
         * two extra times. If we passed it on the way forward it will
         * be oddly toggled now. */
        os << "bfb";
        is_even_toggled = !passed_once;
      }
      else
      {
        /* Current switch is "off", and was toggled an even number of
         * times on the way here, or it is "on" and was toggled an odd
         * number of times on the way here. So it will be "off", and
         * we can just go back. The previous switch is toggled one
         * time when we step back, so will be evenly toggled if we
         * passed it on out way forward. */
        os << "b";
        is_even_toggled = passed_once;
      }
            
      cur = cur->getPrev();      
    }

    /* All switches now "off", so just go forward all the way, turning
     * them "on" int the process. */
    cur = start;
    while (cur != nullptr)
    {
      os << "f";
      cur = cur->getNext();
    }
    os << "f" << std::endl;
  }

  /* Check if a move forward will "win". */
  bool winConditionMet()
  {
    return (current != nullptr &&
            current->getNext() == nullptr &&
            isAllOn(start));
  }
  
private:

  /* Recursively check if all switches are "on" */
  bool isAllOn(Switch* s) const
  {
    if (!s)
      return true;
    return s->getConducting() && isAllOn(s->getNext());
  }

  Circuit(Circuit const&) = delete;
  Circuit& operator=(Circuit const&) = delete;
  
  Switch* start;
  Switch* current;
};


#include <random>

int main()
{
  std::random_device rnd;
  Circuit c;
  
  for (int i = 0; i < 10; ++i)
    c.add(rnd()%2);

  std::cout << "Switches in \"off\" state show as '0'." << std::endl;
  std::cout << "Switches in \"on\" state show as '1'." << std::endl;
  std::cout << "You show as 'i' if you are on an \"on\" switch." << std::endl;
  std::cout << "You show as 'o' if you are on an \"off\" switch." << std::endl;
  std::cout << "You can enter many commands at once." << std::endl;
  std::cout << "Command 'f' attempt to move forward." << std::endl;
  std::cout << "Command 'b' attempt to move backward." << std::endl;
  std::cout << "Command 's' print solution command string." << std::endl;
  std::cout << "Command 'q' quit the game." << std::endl;
  std::cout << "Press 'Enter' after your command(s)." << std::endl;

  char cmd;
  do
  {
    c.print(std::cout);
    std::cout << ": forward or back (f/b)? ";
    std::cin >> cmd;
    
    if ( cmd == 'f' || cmd == 'F' )
    {
      if ( ! c.goForward())
      {
        if ( c.winConditionMet() )
        {
          std::cout << "You win!" << std::endl;
          break;
        }
        else
        {
          std::cout << "Some switch is still off!" << std::endl;
        }
      }
    }
    else if ( cmd == 'b' || cmd == 'B' )
    {
      c.goBack();
    }
    else if ( cmd == 's' )
    {
      c.solveCurrentState(std::cout);
    }
  }
  while (cmd != 'q');
  
  std::cout << std::endl;
  return 0;
}