fork download
copy 
  1. import java.io.*;
  2. import java.text.SimpleDateFormat;
  3. import java.util.*;
  4.  
  5. class Expense_8_puzzle implements Comparable<Expense_8_puzzle> {
  6.     int[][] mat;
  7.     int[] movablePlaceHolder;
  8.     int cost;
  9.     int depth;
  10.     Expense_8_puzzle predecessor;
  11.     String action;
  12.  
  13.     static final Map<String, int[]> movableActions = new HashMap<>();
  14.  
  15.     static {
  16.         movableActions.put("DOWN", new int[]{-1, 0});
  17.         movableActions.put("UP", new int[]{1, 0});
  18.         movableActions.put("RIGHT", new int[]{0, -1});
  19.         movableActions.put("LEFT", new int[]{0, 1});
  20.     }
  21.  
  22.     Expense_8_puzzle(int[][] mat, int[] movablePlaceHolder, int cost, int depth, Expense_8_puzzle predecessor, String action) {
  23.         this.mat = new int[3][3];
  24.         for (int i = 0; i < 3; i++) {
  25.             this.mat[i] = Arrays.copyOf(mat[i], mat[i].length);
  26.         }
  27.         this.movablePlaceHolder = Arrays.copyOf(movablePlaceHolder, movablePlaceHolder.length);
  28.         this.cost = cost;
  29.         this.depth = depth;
  30.         this.predecessor = predecessor;
  31.         this.action = action;
  32.     }
  33.  
  34.     @Override
  35.     public int compareTo(Expense_8_puzzle other) {
  36.         return Integer.compare(this.cost, other.cost);
  37.     }
  38.  
  39.     // Method to parse input file and create the problem state
  40.     static Expense_8_puzzle convertToMatFromFile(String fileName) throws IOException {
  41.         BufferedReader br = new BufferedReader(new FileReader(fileName));
  42.         String line;
  43.         int[][] mat = new int[3][3];
  44.         int[] movablePlaceHolder = new int[2];
  45.  
  46.         for (int i = 0; i < 3; i++) {
  47.             line = br.readLine();
  48.             String[] tokens = line.split(" ");
  49.             for (int j = 0; j < tokens.length; j++) {
  50.                 mat[i][j] = Integer.parseInt(tokens[j]);
  51.                 if (mat[i][j] == 0) {
  52.                     movablePlaceHolder[0] = i;
  53.                     movablePlaceHolder[1] = j;
  54.                 }
  55.             }
  56.         }
  57.         br.close();
  58.         return new Expense_8_puzzle(mat, movablePlaceHolder, 0, 0, null, null);
  59.     }
  60.  
  61.     // Expansions for the current state (children nodes)
  62.     List<Expense_8_puzzle> getExpansions() {
  63.         List<Expense_8_puzzle> expansions = new ArrayList<>();
  64.         int x = movablePlaceHolder[0], y = movablePlaceHolder[1];
  65.  
  66.         for (Map.Entry<String, int[]> entry : movableActions.entrySet()) {
  67.             String action = entry.getKey();
  68.             int[] dir = entry.getValue();
  69.             int tempA = x + dir[0], tempB = y + dir[1];
  70.  
  71.             // Valid grid boundaries
  72.             if (tempA >= 0 && tempA < 3 && tempB >= 0 && tempB < 3) {
  73.                 int[][] tempMat = new int[3][3];
  74.                 for (int i = 0; i < 3; i++) {
  75.                     tempMat[i] = Arrays.copyOf(mat[i], mat[i].length);
  76.                 }
  77.                 tempMat[x][y] = tempMat[tempA][tempB];
  78.                 tempMat[tempA][tempB] = 0;
  79.                 int tileValue = tempMat[x][y];
  80.                 expansions.add(new Expense_8_puzzle(tempMat, new int[]{tempA, tempB}, this.cost + tileValue, this.depth + 1, this, action));
  81.             }
  82.         }
  83.         return expansions;
  84.     }
  85.  
  86.     // Trace the path from current to root (predecessors)
  87.     List<String> parentChainGenerator() {
  88.         List<String> path = new ArrayList<>();
  89.         Expense_8_puzzle state = this;
  90.  
  91.         while (state.predecessor != null) {
  92.             path.add("Move " + state.mat[state.predecessor.movablePlaceHolder[0]][state.predecessor.movablePlaceHolder[1]] + " " + state.action);
  93.             state = state.predecessor;
  94.         }
  95.         return path;  // No need to reverse. It prints from current to root.
  96.     }
  97.  
  98.     // Heuristic function
  99.     static int estimate_heuristicValues(Expense_8_puzzle state, Expense_8_puzzle goal) {
  100.         int cost = 0;
  101.         for (int i = 0; i < 3; i++) {
  102.             for (int j = 0; j < 3; j++) {
  103.                 int tile = state.mat[i][j];
  104.                 if (tile != 0) {
  105.                     int goalI = (tile - 1) / 3;
  106.                     int goalJ = (tile - 1) % 3;
  107.                     int moves = Math.abs(i - goalI) + Math.abs(j - goalJ);
  108.                     cost += moves * tile;
  109.                 }
  110.             }
  111.         }
  112.         return cost;
  113.     }
  114.  
  115.     // Parent chain from current state to root (no reversal)
  116.     static List<Expense_8_puzzle> getParentChain(Expense_8_puzzle state) {
  117.         List<Expense_8_puzzle> chain = new ArrayList<>();
  118.         while (state != null) {
  119.             chain.add(state);  // Start from current state
  120.             state = state.predecessor;
  121.         }
  122.         return chain;
  123.     }
  124.  
  125.     // Log state and its predecessor chain
  126.     static void dumpLogger(Expense_8_puzzle presentPuzzleMat, List<Expense_8_puzzle> successors, Set<String> closedSet, Collection<Expense_8_puzzle> frontier, int NPop, String logFile, Expense_8_puzzle goalState, String method) throws IOException {
  127.         if (logFile != null) {
  128.             BufferedWriter fileEditor = new BufferedWriter(new FileWriter(logFile, true));
  129.  
  130.             if (method.equals("a*") || method.equals("greedy")) {
  131.                 fileEditor.write(String.format("Generating successors to < state = %s, action = {%s} g(n) = %d, d = %d, f(n) = %d, Parent = Pointer to %s >:\n",
  132.                         Arrays.deepToString(presentPuzzleMat.mat), presentPuzzleMat.action == null ? "Start" : presentPuzzleMat.action, presentPuzzleMat.cost,
  133.                         presentPuzzleMat.depth, presentPuzzleMat.cost + estimate_heuristicValues(presentPuzzleMat, goalState),
  134.                         presentPuzzleMat.predecessor == null ? "None" : Arrays.deepToString(presentPuzzleMat.predecessor.mat)));
  135.             } else {
  136.                 fileEditor.write(String.format("Generating successors to < state = %s, action = {%s} cost = %d, d = %d, Parent = Pointer to %s >:\n",
  137.                         Arrays.deepToString(presentPuzzleMat.mat), presentPuzzleMat.action == null ? "Start" : presentPuzzleMat.action, presentPuzzleMat.cost,
  138.                         presentPuzzleMat.depth, presentPuzzleMat.predecessor == null ? "None" : Arrays.deepToString(presentPuzzleMat.predecessor.mat)));
  139.             }
  140.  
  141.             fileEditor.write("\tsuccessors generated -> \n");
  142.             fileEditor.write("\tClosed: " + closedSet + "\n");
  143.             fileEditor.write("\tFringe: [\n");
  144.  
  145.             // Iterate over frontier and log the state and its predecessor chain
  146.             for (Expense_8_puzzle state : frontier) {
  147.                 List<Expense_8_puzzle> predecessorChain = getParentChain(state);  // Correct predecessor chain
  148.  
  149.                 // Print chain from current state to root
  150.                 StringBuilder predecessorChainStr = new StringBuilder();
  151.                 for (int i = 0; i < predecessorChain.size(); i++) {  // Keep order as-is
  152.                     Expense_8_puzzle p = predecessorChain.get(i);
  153.                     predecessorChainStr.append(String.format("< state = %s, action = {Move %s}, g(n) = %d, d = %d, f(n) = %d >",
  154.                             Arrays.deepToString(p.mat), p.action, p.cost, p.depth, method.equals("a*") || method.equals("greedy") ? (p.cost + estimate_heuristicValues(p, goalState)) : p.cost));
  155.                     if (i != predecessorChain.size() - 1) {  // Append arrow unless last state
  156.                         predecessorChainStr.append(" -> ");
  157.                     }
  158.                 }
  159.                 fileEditor.write("\t\t" + predecessorChainStr.toString() + "\n");
  160.             }
  161.  
  162.             fileEditor.write("\t]\n");
  163.             fileEditor.close();
  164.         }
  165.     }
  166.  
  167.  
  168.     // DLS (Depth-Limited Search)
  169.     static Expense_8_puzzle dls(Expense_8_puzzle start, Expense_8_puzzle goal, int DL, boolean logBoolean, String logFile) throws IOException {
  170.         Stack<Expense_8_puzzle> frontier = new Stack<>();
  171.         Set<String> closedSet = new HashSet<>();
  172.         frontier.push(start);
  173.         int NPop = 0, NGen = 1, NExp = 0, MFSize = 0;
  174.  
  175.         while (!frontier.isEmpty()) {
  176.             MFSize = Math.max(MFSize, frontier.size());
  177.             Expense_8_puzzle presentPuzzleMat = frontier.pop();
  178.             NPop++;
  179.  
  180.             if (presentPuzzleMat.depth > DL) {
  181.                 continue;
  182.             }
  183.  
  184.             if (Arrays.deepEquals(presentPuzzleMat.mat, goal.mat)) {
  185.                 System.out.println("Nodes Expanded: " + NExp);
  186.                 System.out.println("Nodes Generated: " + NGen);
  187.                 System.out.println("Nodes Popped: " + NPop);
  188.                 System.out.println("Max Fringe Size: " + MFSize);
  189.                 return presentPuzzleMat;
  190.             }
  191.  
  192.             String matStr = Arrays.deepToString(presentPuzzleMat.mat);
  193.             if (closedSet.contains(matStr)) {
  194.                 continue;
  195.             }
  196.  
  197.             closedSet.add(matStr);
  198.             NExp++;
  199.             List<Expense_8_puzzle> successors = presentPuzzleMat.getExpansions();
  200.             for (Expense_8_puzzle neighbor : successors) {
  201.                 if (neighbor.depth <= DL) {
  202.                     frontier.push(neighbor);
  203.                     NGen++;
  204.                 }
  205.             }
  206.  
  207.             if (logBoolean) {
  208.                 dumpLogger(presentPuzzleMat, successors, closedSet, frontier, NPop, logFile, goal, "dls");
  209.             }
  210.         }
  211.         return null;
  212.     }
  213.  
  214.  
  215.     // BFS
  216.     static Expense_8_puzzle bfs(Expense_8_puzzle start, Expense_8_puzzle goal, boolean logBoolean, String logFile) throws IOException {
  217.         Queue<Expense_8_puzzle> frontier = new LinkedList<>();
  218.         Set<String> closedSet = new HashSet<>();
  219.         frontier.add(start);
  220.         int NPop = 0, NGen = 1, NExp = 0, MFSize = 0;
  221.  
  222.         while (!frontier.isEmpty()) {
  223.             MFSize = Math.max(MFSize, frontier.size());
  224.             Expense_8_puzzle presentPuzzleMat = frontier.poll();
  225.             NPop++;
  226.  
  227.             if (Arrays.deepEquals(presentPuzzleMat.mat, goal.mat)) {
  228.                 System.out.println("Nodes Expanded: " + NExp);
  229.                 System.out.println("Nodes Generated: " + NGen);
  230.                 System.out.println("Nodes Popped: " + NPop);
  231.                 System.out.println("Max Fringe Size: " + MFSize);
  232.                 return presentPuzzleMat;
  233.             }
  234.  
  235.             String matStr = Arrays.deepToString(presentPuzzleMat.mat);
  236.             if (closedSet.contains(matStr)) {
  237.                 continue;
  238.             }
  239.  
  240.             closedSet.add(matStr);
  241.             NExp++;
  242.             List<Expense_8_puzzle> successors = presentPuzzleMat.getExpansions();
  243.             for (Expense_8_puzzle neighbor : successors) {
  244.                 frontier.add(neighbor);
  245.                 NGen++;
  246.             }
  247.  
  248.             if (logBoolean) {
  249.                 dumpLogger(presentPuzzleMat, successors, closedSet, frontier, NPop, logFile, goal, "bfs");
  250.             }
  251.         }
  252.         return null;
  253.     }
  254.  
  255.  
  256.  
  257.     // IDS
  258.     static Expense_8_puzzle ids(Expense_8_puzzle start, Expense_8_puzzle goal, boolean logBoolean, String logFile) throws IOException {
  259.         int DL = 0;
  260.         while (true) {
  261.             Expense_8_puzzle result = dls(start, goal, DL, logBoolean, logFile);
  262.             if (result != null) {
  263.                 return result;
  264.             }
  265.             DL++;
  266.         }
  267.     }
  268.  
  269.     // UCS
  270.     static Expense_8_puzzle ucs(Expense_8_puzzle start, Expense_8_puzzle goal, boolean logBoolean, String logFile) throws IOException {
  271.         PriorityQueue<Expense_8_puzzle> frontier = new PriorityQueue<>();
  272.         Set<String> closedSet = new HashSet<>();
  273.         frontier.add(start);
  274.         int NPop = 0, NGen = 1, NExp = 0, MFSize = 0;
  275.  
  276.         while (!frontier.isEmpty()) {
  277.             MFSize = Math.max(MFSize, frontier.size());
  278.             Expense_8_puzzle presentPuzzleMat = frontier.poll();
  279.             NPop++;
  280.  
  281.             if (Arrays.deepEquals(presentPuzzleMat.mat, goal.mat)) {
  282.                 System.out.println("Nodes Expanded: " + NExp);
  283.                 System.out.println("Nodes Generated: " + NGen);
  284.                 System.out.println("Nodes Popped: " + NPop);
  285.                 System.out.println("Max Fringe Size: " + MFSize);
  286.                 return presentPuzzleMat;
  287.             }
  288.  
  289.             String matStr = Arrays.deepToString(presentPuzzleMat.mat);
  290.             if (closedSet.contains(matStr)) {
  291.                 continue;
  292.             }
  293.  
  294.             closedSet.add(matStr);
  295.             NExp++;
  296.             List<Expense_8_puzzle> successors = presentPuzzleMat.getExpansions();
  297.             for (Expense_8_puzzle neighbor : successors) {
  298.                 frontier.add(neighbor);
  299.                 NGen++;
  300.             }
  301.  
  302.             if (logBoolean) {
  303.                 dumpLogger(presentPuzzleMat, successors, closedSet, frontier, NPop, logFile, goal, "ucs");
  304.             }
  305.         }
  306.         return null;
  307.     }
  308.  
  309.     // Greedy
  310.     static Expense_8_puzzle greedy(Expense_8_puzzle start, Expense_8_puzzle goal, boolean logBoolean, String logFile) throws IOException {
  311.         PriorityQueue<Expense_8_puzzle> frontier = new PriorityQueue<>(Comparator.comparingInt(s -> estimate_heuristicValues(s, goal)));
  312.         Set<String> closedSet = new HashSet<>();
  313.         frontier.add(start);
  314.         int NPop = 0, NGen = 1, NExp = 0, MFSize = 0;
  315.  
  316.         while (!frontier.isEmpty()) {
  317.             MFSize = Math.max(MFSize, frontier.size());
  318.             Expense_8_puzzle presentPuzzleMat = frontier.poll();
  319.             NPop++;
  320.  
  321.             if (Arrays.deepEquals(presentPuzzleMat.mat, goal.mat)) {
  322.                 System.out.println("Nodes Expanded: " + NExp);
  323.                 System.out.println("Nodes Generated: " + NGen);
  324.                 System.out.println("Nodes Popped: " + NPop);
  325.                 System.out.println("Max Fringe Size: " + MFSize);
  326.                 return presentPuzzleMat;
  327.             }
  328.  
  329.             String matStr = Arrays.deepToString(presentPuzzleMat.mat);
  330.             if (closedSet.contains(matStr)) {
  331.                 continue;
  332.             }
  333.  
  334.             closedSet.add(matStr);
  335.             NExp++;
  336.             List<Expense_8_puzzle> successors = presentPuzzleMat.getExpansions();
  337.             for (Expense_8_puzzle neighbor : successors) {
  338.                 frontier.add(neighbor);
  339.                 NGen++;
  340.             }
  341.  
  342.             if (logBoolean) {
  343.                 dumpLogger(presentPuzzleMat, successors, closedSet, frontier, NPop, logFile, goal, "greedy");
  344.             }
  345.         }
  346.         return null;
  347.     }
  348.  
  349.     // A*
  350.     static Expense_8_puzzle aStar(Expense_8_puzzle start, Expense_8_puzzle goal, boolean logBoolean, String logFile) throws IOException {
  351.         PriorityQueue<Expense_8_puzzle> frontier = new PriorityQueue<>(Comparator.comparingInt(s -> s.cost + estimate_heuristicValues(s, goal)));
  352.         Set<String> closedSet = new HashSet<>();
  353.         frontier.add(start);
  354.         int NPop = 0, NGen = 1, NExp = 0, MFSize = 0;
  355.  
  356.         while (!frontier.isEmpty()) {
  357.             MFSize = Math.max(MFSize, frontier.size());
  358.             Expense_8_puzzle presentPuzzleMat = frontier.poll();
  359.             NPop++;
  360.  
  361.             if (Arrays.deepEquals(presentPuzzleMat.mat, goal.mat)) {
  362.                 System.out.println("Nodes Expanded: " + NExp);
  363.                 System.out.println("Nodes Generated: " + NGen);
  364.                 System.out.println("Nodes Popped: " + NPop);
  365.                 System.out.println("Max Fringe Size: " + MFSize);
  366.                 return presentPuzzleMat;
  367.             }
  368.  
  369.             String matStr = Arrays.deepToString(presentPuzzleMat.mat);
  370.             if (closedSet.contains(matStr)) {
  371.                 continue;
  372.             }
  373.  
  374.             closedSet.add(matStr);
  375.             NExp++;
  376.             List<Expense_8_puzzle> successors = presentPuzzleMat.getExpansions();
  377.             for (Expense_8_puzzle neighbor : successors) {
  378.                 frontier.add(neighbor);
  379.                 NGen++;
  380.             }
  381.  
  382.             if (logBoolean) {
  383.                 dumpLogger(presentPuzzleMat, successors, closedSet, frontier, NPop, logFile, goal, "a*");
  384.             }
  385.         }
  386.  
  387.         return null;
  388.     }
  389.  
  390.     public static void main(String[] args) throws IOException {
  391.         if (args.length < 2) {
  392.             System.out.println("Usage: java Expense_8_puzzle <start-file> <goal-file> <method> <log-file>");
  393.             return;
  394.         }
  395.  
  396.         String startFile = args[0];
  397.         String goalFile = args[1];
  398.  
  399.         String method = "a*";
  400.         boolean logBoolean = false;
  401.         String logFile = "traceDateTime.txt" ;
  402.         // trace-Date-Time.txt 
  403.         logFile = "trace-" + new SimpleDateFormat("yyyy-MM-dd-HH-mm-ss").format(new Date()) + ".txt";
  404.         if(args.length > 2){
  405.             if(args[2].equals("true") || args[2].equals("false")){
  406.                 logBoolean = Boolean.parseBoolean(args[2]);
  407.             }
  408.             else{
  409.                 method = args[2];
  410.             }
  411.         }
  412.         if(args.length > 3){
  413.             logBoolean = Boolean.parseBoolean(args[3]);
  414.         }
  415.  
  416.  
  417.         Expense_8_puzzle startState = Expense_8_puzzle.convertToMatFromFile(startFile);
  418.         Expense_8_puzzle goalState = Expense_8_puzzle.convertToMatFromFile(goalFile);
  419.  
  420.         Expense_8_puzzle answer = null;
  421.  
  422.         switch (method) {
  423.             case "bfs":
  424.                 answer = Expense_8_puzzle.bfs(startState, goalState, logBoolean, logFile);
  425.                 break;
  426.             case "dfs":
  427.                 answer = Expense_8_puzzle.dls(startState, goalState, Integer.MAX_VALUE, logBoolean, logFile);
  428.                 break;
  429.             case "dls":
  430.                 int DL = 10;
  431.                 Scanner sc = new Scanner(System.in);
  432.                 System.out.println("Enter the depth limit: ");
  433.                 String inputTaken = sc.nextLine();
  434.                 if(inputTaken.length() > 0 && inputTaken.matches("[0-9]+")){
  435.                     DL = Integer.parseInt(inputTaken);
  436.                 }
  437.                 else{
  438.                     System.out.println("Invalid input, using default depth limit of 10");
  439.                 }
  440.  
  441.                 answer = Expense_8_puzzle.dls(startState, goalState, DL, logBoolean, logFile);
  442.                 break;
  443.             case "ids":
  444.                 answer = Expense_8_puzzle.ids(startState, goalState, logBoolean, logFile);
  445.                 break;
  446.             case "ucs":
  447.                 answer = Expense_8_puzzle.ucs(startState, goalState, logBoolean, logFile);
  448.                 break;
  449.             case "greedy":
  450.                 answer = Expense_8_puzzle.greedy(startState, goalState, logBoolean, logFile);
  451.                 break;
  452.             case "a*":
  453.                 answer = Expense_8_puzzle.aStar(startState, goalState, logBoolean, logFile);
  454.                 break;
  455.             default:
  456.                 System.out.println("Unknown method!");
  457.                 return;
  458.         }
  459.  
  460.         if (answer != null) {
  461.             System.out.println("Solution Found at depth " + answer.depth + " with cost of " + answer.cost);
  462.             List<String> steps = answer.parentChainGenerator();
  463.             for (String step : steps) {
  464.                 System.out.println("\t" + step);
  465.             }
  466.         } else {
  467.             System.out.println("No answer found.");
  468.         }
  469.     }
  470. }
  471.  
Success #stdin #stdout 0.09s 54908KB
comments (?)
stdin
copy 
insert into friend (
select f1.id1, f2.id2
from friend f1, friend f2, friend f3
where f1.id2=f2.id1
and f2.id2=f3.id1
and f1.id1 < f1.id2
and f2.id1 < f2.id2
and not exists (
select d.id1, d.id2
from friend d
where d.id1=f1.id1
and d.id2=f2.id2)
)
stdout
copy 
Usage: java Expense_8_puzzle <start-file> <goal-file> <method> <log-file>
https://ideone.com/2vGHdL
language:
Java (HotSpot 12)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!