Spock Web Console

subscribe to the feed Subscribe
Prisoners And Switches Problem v2 (via #spockwebconsole)
tweet this script Tweet

Prisoners And Switches Problem v2

Published 1 year ago by jp
Actions  ➤ Edit In Console Back To Console Show/Hide Line Numbers View Recent Scripts
import spock.lang.*

// Press 'Edit in Console' and then press 'Run Script' below
class Constants
{
    public static final boolean DEBUG_OUTPUT = true;
    public static final boolean RANDOM_SELECTION = true;
}

class PrisonersAndSwitchesSpec extends Specification
{
    private static def problemSizesToTest = [1, 2, 3, 4, 5, 9, 10];

    def "Eventually one prisoner has to answer that he is last"(int n)
    {
        setup:
        def problem = new PrisonersAndSwitchesProblem(n);

        when:
        def lastPrisoner = problem.solve();

        then:
        lastPrisoner != null;

        where:
        n << problemSizesToTest;
    }

    def "When a prisoners says he is last there should be no more prisoners that still have to visit the warden"(int n)
    {
        setup:
        def problem = new PrisonersAndSwitchesProblem(n);

        when:
        problem.solve();

        then:
        problem.getNonSelectedPrisonersCount() == 0;

        where:
        n << problemSizesToTest;
    }

    def "Prisoners decide on logic to use to operate the switches and how to answer if last"()
    {
        def problem = new PrisonersAndSwitchesProblem(n);

        expect:
        problem.prisoners.every { it.logic != null };
        problem.prisoners.every { it.logic.gangCode != null };

        where:
        n << problemSizesToTest;
    }

    def "Prisoners choose one prisoner to be their leader who will use different logic and count them"()
    {
        def problem = new PrisonersAndSwitchesProblem(n);        
        def leaders = problem.prisoners.findAll { it.logic instanceof GangLeaderLogic };

        expect:
        leaders.size() == 1;

        where:
        n << problemSizesToTest;
    }

    @Unroll
    def "Switch operation logic test: #state1, #state2 <-> #encoded"(int state1, int state2, int encoded)
    {
        setup:
        def gangCode = new GangCode();

        def s1 = new Switch(state1);
        def s2 = new Switch(state2);

        when:
        def actual = gangCode.encode(s1, s2);

        then:
        actual == encoded;

        when:
        s1 = new Switch(0);
        s2 = new Switch(0);
        gangCode.decode(s1, s2, encoded);

        then:
        s1.state == state1;
        s2.state == state2;

        where:
        state1 | state2 | encoded
        0 | 0 | 0
        0 | 1 | 1
        1 | 0 | 2
        1 | 1 | 3
    }
}

class PrisonersAndSwitchesFrameworkSpec extends Specification
{
    private static def problemSizesToTest = [1, 2, 3, 4, 5, 9, 10];

    def "Utils.random(n) should return an integer >= 0 and < n"(int n)
    {
        setup:
        def rnd = Utils.random(n);

        expect:
        (0..n-1).contains(rnd);

        where:
        n << [1, 2, 3, 4, 9, 10];
    }

    def "Switches should be initialized properly"(int[] state)
    {
        setup:
        def problem = new PrisonersAndSwitchesProblem(1, state);

        expect:
        problem.s1.state == state[0];
        problem.s2.state == state[1];

        where:
        state << PrisonersAndSwitchesProblem.possibleStartingStates;
    }

    def "The problem of size n should have n prisoners"(int n)
    {
        setup:
        def prisonerCount = new PrisonersAndSwitchesProblem(n).getNonSelectedPrisonersCount();

        expect:
        n == prisonerCount;

        where:
        n << problemSizesToTest;
    }

    def "The method selectNextPrisoner() should return a prisoner from the prisoner list"(int n)
    {
        setup:
        def problem = new PrisonersAndSwitchesProblem(n);
        def prisoner = problem.selectNextPrisoner();

        expect:
        problem.prisoners.contains(prisoner);

        where:
        n << problemSizesToTest;
    }

    def "The method step(Prisoner) should remove the selected prisoner from the notSelectedPrisoners list"(int n)
    {
        setup:
        def problem = new PrisonersAndSwitchesProblem(n);

        def prisoner = problem.selectNextPrisoner();

        when:
        problem.step(prisoner);

        then:
        problem.notSelectedPrisoners.contains(prisoner) == false;

        where:
        n << problemSizesToTest;
    }
}

class Utils
{
    public static int random(int n)
    {
        return (int)(Math.random() * n);
    }

    public static void debug(args)
    {
        if (Constants.DEBUG_OUTPUT)
        {
            println(args);
        }
    }
}

class Switch
{
    public static final int OFF = 0;
    public static final int ON = 1;

    public int state;

    public Switch(int state)
    {
        this.state = state;
    }
}

class GangCode
{
    public static final int LOCK_READY     = 0;
    public static final int LOCK_REQUESTED = 1;
    public static final int LOCK_GRANTED   = 2;
    public static final int LOCK_RELEASE   = 3;

    public int encode(Switch s1, Switch s2)
    {
        return s1.state * 2 + s2.state;
    }

    public void decode(Switch s1, Switch s2, int newState)
    {
        s1.state = (int)(newState / 2);
        s2.state = newState % 2;
    }
}

interface PrisonerLogic
{
    boolean operateSwitchesAndAnswerIfLast(Switch s1, Switch s2);
}

abstract class GangLogic implements PrisonerLogic
{
    protected GangCode gangCode;

    public GangLogic(GangCode gangCode)
    {
        this.gangCode = gangCode;
    }

    abstract boolean operateSwitchesAndAnswerIfLast(Switch s1, Switch s2);
}

class GangMemberLogic extends GangLogic
{
    private static final int REQUEST_LOCK = 0;
    private static final int RELEASE_LOCK = 1;
    private static final int DONE = 2;

    private int state = REQUEST_LOCK;

    public GangMemberLogic(GangCode gangCode)
    {
        super(gangCode);
    }

    public boolean operateSwitchesAndAnswerIfLast(Switch s1, Switch s2)
    {
        if (state != DONE && gangCode.encode(s1, s2) == gangCode.LOCK_READY)
        {
            state = RELEASE_LOCK;
            gangCode.decode(s1, s2, gangCode.LOCK_REQUESTED);
            Utils.debug(toString() + ": LOCK_REQUESTED");
        }
        else if (state == RELEASE_LOCK && gangCode.encode(s1, s2) == gangCode.LOCK_GRANTED)
        {
            state = DONE;
            gangCode.decode(s1, s2, gangCode.LOCK_RELEASE);
            Utils.debug(toString() + ": LOCK_RELEASED");
        }

        // Only the gang leader can give a positive answer
        return false;
    }
}

class GangLeaderLogic extends GangLogic
{
    private boolean lockReset = false;

    private int gangMembersLeft;

    public GangLeaderLogic(GangCode gangCode, int gangSize)
    {
        super(gangCode);

        gangMembersLeft = gangSize-1;
    }

    public boolean operateSwitchesAndAnswerIfLast(Switch s1, Switch s2)
    {
        boolean answer = false;

        int switchState = gangCode.encode(s1, s2);

        if (!lockReset)
        {
            lockReset = true;
            switchState = GangCode.LOCK_READY;
            Utils.debug(toString() + ": LOCK_RESET. Members left: " + gangMembersLeft);
        }
        else
        {
            switch (switchState)
            {
                case GangCode.LOCK_REQUESTED:
                    switchState = GangCode.LOCK_GRANTED;
                    Utils.debug(toString() + ": LOCK_GRANTED");
                    break;
                case GangCode.LOCK_RELEASE:
                    switchState = GangCode.LOCK_READY;
                    --gangMembersLeft;
                    Utils.debug(toString() + ": LOCK_READY. Members left: " + gangMembersLeft);
                    break;
                case GangCode.LOCK_READY:
                case GangCode.LOCK_GRANTED:
                default:
                    break;
            }
        }

        gangCode.decode(s1, s2, switchState);

        if (gangMembersLeft <= 0)
        {
            Utils.debug(toString() + ": All members accounted for. Answering that I am last.");
            answer = true;
        }

        return answer;
    }
}

class Prisoner implements PrisonerLogic
{
    private PrisonerLogic logic;

    public static void organize(List<Prisoner> prisoners)
    {
        // Prisoners decide to come up with some kind of gang code and logic for the switches
        def gangCode = new GangCode();
        prisoners.each { it.logic = new GangMemberLogic(gangCode) };

        // They also choose one prisoner to be their gang leader
        // who will use different logic
        def prisonersCount = prisoners.size();
        def randomPrisoner = prisoners[Utils.random(prisonersCount)];
        randomPrisoner.logic = new GangLeaderLogic(gangCode, prisonersCount);
    }

    public boolean operateSwitchesAndAnswerIfLast(Switch s1, Switch s2)
    {
        boolean answer;

        // When visiting the warden they act with the logic they agreen on based on their rank
        answer = logic.operateSwitchesAndAnswerIfLast(s1, s2);

        return answer;
    }
}

class PrisonersAndSwitchesProblem
{
    public static final int MAX_ITERATIONS = 10000;

    public static final int[][] possibleStartingStates = [
        [Switch.OFF, Switch.OFF ],
        [Switch.OFF, Switch.ON  ],
        [Switch.ON,  Switch.OFF ],
        [Switch.ON,  Switch.ON  ]
    ];

    private Switch s1;
    private Switch s2;
    
    private List<Prisoner> prisoners;
    private List<Prisoner> notSelectedPrisoners;

    public PrisonersAndSwitchesProblem(int prisonerCount)
    {
        init(prisonerCount, possibleStartingStates[Utils.random(4)]);
    }

    public PrisonersAndSwitchesProblem(int prisonerCount, int[] switchStartingStates)
    {
        init(prisonerCount, switchStartingStates);
    }

    private void init(int prisonerCount)
    {
        init(prisonerCount, possibleStartingStates[Utils.random(4)]);
    }

    private void init(int prisonerCount, int[] switchStartingStates)
    {
        s1 = new Switch(switchStartingStates[0]);
        s2 = new Switch(switchStartingStates[1]);
        
        prisoners = [];
        prisonerCount.times { prisoners << new Prisoner() };

        notSelectedPrisoners = prisoners.collect();

        Prisoner.organize(prisoners);
    }

    private Prisoner selectNextPrisoner()
    {
        return prisoners[Utils.random(prisoners.size())];
    }

    private boolean step(Prisoner selectedPrisoner)
    {
        notSelectedPrisoners.remove(selectedPrisoner);
        return selectedPrisoner.operateSwitchesAndAnswerIfLast(s1, s2);
    }

    public int getNonSelectedPrisonersCount()
    {
        return notSelectedPrisoners.size();
    }

    public Prisoner solve()
    {
        boolean randomly = Constants.RANDOM_SELECTION;

        Utils.debug("--- Solving for " + prisoners.size() + " prisoner(s), " +
            (randomly ? "selecting them randomly" : "selecting them in order") + 
            " ---");

        if (randomly)
        {
            return solveRandomly();
        }
        else
        {
            return solveIteartively();
        }
    }

    public Prisoner solveIteartively()
    {
        Prisoner selectedPrisoner;
        boolean last = false;
        int steps = 0;
        int iteration = 0;
        int maxIterations = 1 + (2 * prisoners.size()-1);

        while(!last && ++iteration <= maxIterations)
        {            
            for (int i = 0; i < prisoners.size(); ++i)
            {
                selectedPrisoner = prisoners[i];
                last = step(selectedPrisoner);
                ++steps;

                if (last) break;
            }
        }

        Utils.debug("Steps: " + steps);

        return last ? selectedPrisoner : null;   
    }

    public Prisoner solveRandomly()
    {
        Prisoner selectedPrisoner;
        boolean last = false;
        int iteration = 0;

        while(!last && ++iteration <= MAX_ITERATIONS)
        {            
            selectedPrisoner = selectNextPrisoner();
            last = step(selectedPrisoner);
        }

        Utils.debug("Steps: " + iteration);

        return last ? selectedPrisoner : null;
    }
}