[2015-04-03] Challenge #208 [Hard] The Universal Machine

Direction.java

package turingmachine;

public enum Direction {
    LEFT(-1),RIGHT(1);
    
    private final int vector;
    private Direction(int vector){
        this.vector = vector;
    }
    
    public int getVector(){
        return vector;
    }
    
    public static Direction parseDirection(String directionString){
        switch(directionString){
            case "<":
                return Direction.LEFT;
            case ">":
                return Direction.RIGHT;
            default:
                throw new IllegalArgumentException(directionString + " is not a valid String representation of a Direction");
        }
    }
        
}

Tape.java

package turingmachine;

import java.lang.StringBuilder;
import java.util.List;
import java.util.ArrayList;

public class Tape {
    private final List<String> tapeList;
    private int zeroIndex;
    
    public Tape(List<String> tape){
        tapeList = tape;
        zeroIndex = 0;
    }

    public String get(int index){
        int adjustedIndex = index+zeroIndex;
        if(adjustedIndex < 0 || adjustedIndex >= tapeList.size()){
            return TuringMachine.UNDEFINED_SYMBOL;
        }
        
        String state = tapeList.get(adjustedIndex);
        return state == null ? TuringMachine.UNDEFINED_SYMBOL : state;
    }
    
    public void set(int index, String symbol){
        int adjustedIndex = index+zeroIndex;
        if(adjustedIndex<0){
            zeroIndex = -index;
            tapeList.add(0,symbol);
        } else if(adjustedIndex >= tapeList.size()){
            while(index+zeroIndex > tapeList.size()){
                tapeList.add(TuringMachine.UNDEFINED_SYMBOL);
            }
            tapeList.add(symbol);
        } else {
            tapeList.set(adjustedIndex,symbol);
        }
    }
    
    public String toStringWithHead(int headIndex){
        StringBuilder toStringBuilder =  new StringBuilder(2*tapeList.size()+4);
        int endIndex = Math.max(tapeList.size()-1,headIndex+zeroIndex);
        int startIndex = Math.min(0,headIndex+zeroIndex);
        for(int i=startIndex;i<=endIndex;i++){
            String s = i>=tapeList.size() || i <0 ? null : tapeList.get(i);
            toStringBuilder.append(s==null ? "_" : s);
        }
        toStringBuilder.append('\n');
        for(int i=startIndex;i<=endIndex;i++){
            if(i==zeroIndex){
                toStringBuilder.append("|");
            } else if (i==headIndex+zeroIndex) {
                toStringBuilder.append("^");
            } else {
                toStringBuilder.append(" ");
            }
        }
        return toStringBuilder.toString();
    }
}

TransitionFunction.java

package turingmachine;

public class TransitionFunction {
    private final String tapeSymbol;
    private final String headState;
    private final Result functionResult;
    
    public TransitionFunction(String tapeSymbol, String headState, String resultTapeSymbol, String resultHeadState, Direction resultDirection){
        this.tapeSymbol = tapeSymbol;
        this.headState = headState;
        functionResult = new Result(resultTapeSymbol,resultHeadState,resultDirection);
    }
    
    public static TransitionFunction parseTransitionFunction(String function){
        String[] parts = function.split(" ");
        
        String headState = parts[0];
        String tapeSymbol = parts[1];
        String resultHeadState = parts[3];
        String resultTapeSymbol = parts[4];
        Direction resultDirection = Direction.parseDirection(parts[5]);
        
        return new TransitionFunction(tapeSymbol,headState,resultTapeSymbol,resultHeadState,resultDirection);
    }

    public boolean appliesTo(String tapeSymbol, String headState){
        return this.tapeSymbol.equals(tapeSymbol) && this.headState.equals(headState);
    }
    
    public Result getResult(){
        return functionResult;
    }
    
    public static class Result {
        private final String resultTapeSymbol;
        private final String resultHeadState;
        private final Direction resultDirection;
        
        public Result(String tapeSymbol,String headState, Direction direction){
            resultTapeSymbol = tapeSymbol;
            resultHeadState = headState;
            resultDirection = direction;
        }
        
        public String getTapeSymbol(){
            return resultTapeSymbol;
        }
        
        public String getHeadState(){
            return resultHeadState;
        }
        
        public Direction getDirection(){
            return resultDirection;
        }
    }
}
    

TuringMachine.java

package turingmachine;

import java.util.Scanner;
import java.io.File;
import java.io.IOException;

import java.util.List;
import java.util.ArrayList;

public class TuringMachine {
    public static final String UNDEFINED_SYMBOL="_";
    
    private int headPosition;
    private String currentState;
    private final Tape machineTape;
    private final List<TransitionFunction> transitionFunctions;
    private final String acceptingState;
    
    public TuringMachine(String initialState, String endState, Tape tape, List<TransitionFunction> functions){
        headPosition  = 0;
        currentState = initialState;
        acceptingState = endState;
        machineTape = tape;
        transitionFunctions = functions;
    }
    
    private TransitionFunction.Result evaluate(){
        for(TransitionFunction tf : transitionFunctions){
            if(tf.appliesTo(machineTape.get(headPosition),currentState)){
                return tf.getResult();
            }
        }
        throw new IllegalStateException(String.format("Head State \"%s\" and tape symbol \"%s\" do not correspond to any known state",currentState,machineTape.get(headPosition)));
    }
    public void step(){
        TransitionFunction.Result result = evaluate();
        machineTape.set(headPosition,result.getTapeSymbol());
        headPosition += result.getDirection().getVector();
        currentState = result.getHeadState();
    }
    
    public void run(){
        while(!currentState.equals(acceptingState)){
            step();
        }
    }
    
    public static TuringMachine buildMachine(Scanner in){
        String initialState = in.nextLine();
        String endState = in.nextLine();
         
        String tapeString  = in.nextLine();
        List<String> tapeList = new ArrayList<>(tapeString.length());
        for(char c:tapeString.toCharArray()){
            tapeList.add(String.valueOf(c));
        }
        
        List<TransitionFunction> functions  = new ArrayList<>();
        while(in.hasNextLine()){
            functions.add(TransitionFunction.parseTransitionFunction(in.nextLine()));
        }
        return new TuringMachine(initialState,endState, new Tape(tapeList),functions);
    }
    
    public static void main(String[] args) throws IOException{
        String turingFile = args[0];
        Scanner in = new Scanner(new File(turingFile));
        TuringMachine machine = buildMachine(in);
        machine.run();
        System.out.println(machine.machineTape);
        System.out.println(machine.currentState);
    }   
}