package leetcode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;

/**
 * https://leetcode.com/problems/open-the-lock/description/
 */
public class Problem753 {
    public int openLock(String[] deadends, String target) {
        Set<String> deads = new HashSet<>();
        for (String dead : deadends) {
            deads.add(dead);
        }
        int result = 0;
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        queue.add("0000");
        while (!queue.isEmpty()) {
            String current = queue.remove();
            System.out.println(current);
            if (deads.contains(current)) {
                continue;
            }
            if (current.equals(target)) {
                return result;
            }
            for (String neighbor : getNeighbors(current)) {
                if (!visited.contains(neighbor)) {
                    queue.add(neighbor);
                    visited.add(neighbor);
                }
            }
        }
        return -1;
    }

    private static List<String> getNeighbors(String node) {
        List<String> neighbors = new ArrayList<>();
        for (int i = 0; i < node.length(); i++) {
            int n1 = (node.charAt(i) - '0' - 1) % 10;
            if (n1 < 0) {
                n1 = 9;
            }
            neighbors.add(node.substring(0, i) + n1 + node.substring(i + 1));
            int n2 = (node.charAt(i) - '0' + 1) % 10;
            neighbors.add(node.substring(0, i) + n2 + node.substring(i + 1));
        }
        return neighbors;
    }

    public static void main(String[] args) {
        Problem753 prob = new Problem753();
        System.out.println(prob.openLock(new String[]{"0201", "0101", "0102", "1212", "2002"}, "0202")); // 6
//        System.out.println(prob.openLock(new String[]{"8888"}, "0009")); // 1
//        System.out.println(prob.openLock(new String[]{"8887", "8889", "8878", "8898", "8788", "8988", "7888", "9888"}, "8888")); // -1
//        System.out.println(prob.openLock(new String[]{"0000"}, "8888")); // -1
//        System.out.println("1234".substring(0, 1) + '0' + "1234".substring(2));
    }
}

@@ -446,32 +446,8 @@
   %7D%0A
-        int result = 0;%0A
     
@@ -503,22 +503,25 @@
   Queue%3C
-String
+NodeDepth
 %3E queue 
@@ -560,22 +560,40 @@
 eue.add(
+new NodeDepth(
 %220000%22
+, 0)
 );%0A     
@@ -634,22 +634,25 @@
         
-String
+NodeDepth
  current
@@ -674,49 +674,8 @@
 ();%0A
-            System.out.println(current);%0A
     
@@ -700,32 +700,37 @@
 contains(current
+.node
 )) %7B%0A           
@@ -782,16 +782,21 @@
 current.
+node.
 equals(t
@@ -832,14 +832,21 @@
 urn 
-result
+current.level
 ;%0A  
@@ -874,22 +874,25 @@
    for (
-String
+NodeDepth
  neighbo
@@ -966,16 +966,21 @@
 neighbor
+.node
 )) %7B%0A   
@@ -1049,32 +1049,37 @@
 ted.add(neighbor
+.node
 );%0A             
@@ -1156,33 +1156,119 @@
 tic 
-List%3CString%3E getNeighbors
+class NodeDepth %7B%0A        private final String node;%0A        private final int level;%0A%0A        public NodeDepth
 (Str
@@ -1275,16 +1275,27 @@
 ing node
+, int depth
 ) %7B%0A    
@@ -1302,19 +1302,172 @@
     
-List%3CString
+    this.node = node;%0A            this.level = depth;%0A        %7D%0A    %7D%0A%0A    private static List%3CNodeDepth%3E getNeighbors(NodeDepth nodeDepth) %7B%0A        List%3CNodeDepth
 %3E ne
@@ -1523,16 +1523,26 @@
  0; i %3C 
+nodeDepth.
 node.len
@@ -1573,24 +1573,34 @@
   int n1 = (
+nodeDepth.
 node.charAt(
@@ -1701,32 +1701,73 @@
   neighbors.add(
+new NodeDepth(%0A                nodeDepth.
 node.substring(0
@@ -1778,16 +1778,26 @@
  + n1 + 
+nodeDepth.
 node.sub
@@ -1798,32 +1798,70 @@
 de.substring(i +
+ 1),%0A                nodeDepth.level +
  1));%0A          
@@ -1868,24 +1868,34 @@
   int n2 = (
+nodeDepth.
 node.charAt(
@@ -1945,58 +1945,21 @@
 dd(n
-ode.substring(0, i) + n2 + node.substring(i + 1));
+ew NodeDepth(
 %0A   
@@ -1959,34 +1959,32 @@
 th(%0A        
-%7D%0A
         
 return neigh
@@ -1975,610 +1975,152 @@
     
-return neighbors;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem753 prob = new Problem753();%0A        System.out.println(prob.openLock(new String%5B%5D%7B%220201%22, %220101%22, %220102%22, %221212%22, %222002%22%7D, %220202%22)); // 6%0A//        System.out.println(prob.openLock(new String%5B%5D%7B%228888%22%7D, %220009%22)); // 1%0A//        System.out.println(prob.openLock(new String%5B%5D%7B%228887%22, %228889%22, %228878%22, %228898%22, %228788%22, %228988%22, %227888%22, %229888%22%7D, %228888%22)); // -1%0A//        System.out.println(prob.openLock(new String%5B%5D%7B%220000%22%7D, %228888%22)); // -1%0A//        System.out.println(%221234%22.substring(0, 1) + '0' + %221234%22.substring(2))
+nodeDepth.node.substring(0, i) + n2 + nodeDepth.node.substring(i + 1),%0A                nodeDepth.level + 1));%0A        %7D%0A        return neighbors
 ;%0A  

Solve problem 753 (first problem in 2018, happy new year)