Semaphors

semaphors.groovy

import groovy.json.*

class Node {

    def links = []
    def timeOff
    def timeOn
    def id
    def period

    Node(int timeOff, int timeOn, int id){
        this.timeOff = timeOff
        this.timeOn = timeOn
        this.id = id
        this.period = timeOff + timeOn
    }

    int getTimeUntilOpen(int initial){
       return ((initial % period) > timeOff) ? 0 : timeOff - (initial % period)
    }

    @Override
    public String toString(){
        return "ID: $id OFF: $timeOff ON: $timeOn"
    }

    @Override
    public boolean equals(Object obj){
        this.id == ((Node)obj).id
    }
}

class Link {

    def duration
    Node next

    Link(def duration, Node next){
        this.duration = duration;
        this.next = next
    }

    int getTimeUntilNextHop(int initial){
        //println "Calculate time until next: INITIAL: $initial, DURATION: $duration"
        return (duration + next.getTimeUntilOpen(initial+duration))
    }

    @Override
    public String toString(){
        return "DURATION: $duration, NEXT: ${next.id}"
    }

}

class Graph {

    def nodesMap = [:]
    Solution bestSolution = null

    static Graph fromFile(String filename){
        def text = new File(filename).text
        def parsed = new JsonSlurper().parseText(text)

        def nodes = parsed.nodes
        def relationships = parsed.relationships

        Graph graph = new Graph()

        nodes.each {

            def node = new Node(it.timeOff, it.timeOn, it.id)
            //println "Created node ${node.id} OFF: ${node.timeOff} ON: ${node.timeOn}"
            graph.nodesMap[it.id] = node
        }

        relationships.each {
            Node destination = graph.nodesMap[it.destination]
            def link = new Link(it.duration, destination)
            graph.nodesMap[it.origin].links << link

            //println "Created link from ${it.origin} to ${it.destination} with time ${it.duration}"

            Node origin = graph.nodesMap[it.origin]
            def secondLink = new Link(it.duration, origin)
            graph.nodesMap[it.destination].links << secondLink

            //println "Created link from ${it.destination} to ${it.origin} with time ${it.duration}"
        }
        
        //println graph.nodesMap[3].links
        
        return graph
    }

    void bestPathFromTo(Node start, Node destination, int time, List<Node> path){

        //println "FROM: ${start.id} TO: ${destination.id} WITH TIME $time"

        if(start == destination){
            if (bestSolution == null || bestSolution.duration > time){
                bestSolution = new Solution()
                bestSolution.duration = time
                bestSolution.path.addAll(path)
            }
        } else {

            start.links.each { link ->

                if(!path.contains(link.next)){
                    int newTime = link.getTimeUntilNextHop(time)
                    //println "With time $time, from $start.id to $destination.id newTime = $newTime"
                    path << link.next
                    bestPathFromTo(link.next, destination, time+newTime, path)
                    path.remove(link.next)
                } else {
                    //println "REPEATED! PATH: $path NOW: ${start.id} TO: ${link.next.id}"
                }
            }
        }
    }

    void bestPathFromTo(int from, int to){
        Node starting = nodesMap[from]
        Node destination = nodesMap[to]
        int startTime = starting.timeOff

        //println "START WITH ${starting.id} GOING TO ${destination.id} AND TIME $startTime"

        bestPathFromTo(starting, destination, startTime, [] << starting)

    }
}

class Solution {

    List<Node> path = []
    int duration

    @Override
    public String toString(){
        def initial = "Duration: $duration | Hops: ${path.size - 1}\n"

        path.eachWithIndex { it, index ->
            if(index > 0) initial += ","
            initial += "${it.id}"
        }

        return initial
    }
}

def graph = Graph.fromFile('semaphors2.json')

graph.bestPathFromTo(1, 7)

println "SOLUTION"
println graph.bestSolution

semaphors.json

{

  "nodes": [

      {
        "timeOn": 4,
        "timeOff": 1,
        "id": 1
      },
      {
        "timeOn": 5,
        "timeOff": 3,
        "id": 2
      },
      {
        "timeOn": 4,
        "timeOff": 3,
        "id": 3
      }
  ],
  "relationships": [
    {
      "origin": 1,
      "destination": 2,
      "duration": 2
    },
    {
      "origin": 1,
      "destination": 3,
      "duration": 20
    },
    {
      "origin": 2,
      "destination": 3,
      "duration": 1
    }
  ]
}

semaphors2.json

{

  "nodes": [

      {
        "timeOn": 7,
        "timeOff": 2,
        "id": 1
      },
      {
        "timeOn": 1,
        "timeOff": 1,
        "id": 2
      },
      {
        "timeOn": 2,
        "timeOff": 1,
        "id": 3
      },
      {
        "timeOn": 1,
        "timeOff": 9,
        "id": 4
      },
      {
        "timeOn": 5,
        "timeOff": 7,
        "id": 5
      },
      {
        "timeOn": 8,
        "timeOff": 2,
        "id": 6
      },
      {
        "timeOn": 7,
        "timeOff": 7,
        "id": 7
      }
  ],
  "relationships": [
    {
      "origin": 1,
      "destination": 2,
      "duration": 5
    },
    {
      "origin": 1,
      "destination": 3,
      "duration": 4
    },
    {
      "origin": 2,
      "destination": 4,
      "duration": 1
    },
    {
      "origin": 3,
      "destination": 4,
      "duration": 7
    },
    {
      "origin": 4,
      "destination": 6,
      "duration": 1
    },
    {
      "origin": 4,
      "destination": 5,
      "duration": 10
    },
    {
      "origin": 6,
      "destination": 7,
      "duration": 1
    },
    {
      "origin": 5,
      "destination": 7,
      "duration": 20
    }
  ]
}