Alqoritm

Spiral Matrix – saat əqrəbi və əksi istiqamətində

Add Comment
451 Views
21/03/2018
spiral-matrix
Written by Mushfiq Mammadov

İşi dəyişdikdən sonra bloga vaxt ayırmağa imkan olmur, ona görə də bir həftəlik Novruz bayramı fasiləsindən istifadə edib alqortimlərlə bağlı bir məqalə əlavə edim dedim 🙂 Deməli intervülərdən birində belə bir tapşırıq verilmişdi:

Dinamik ölçülü (4x4, 5x7, 6x3 və s.) bir matris verilib. Matrisin elementlərini mərkəzdən başlayaraq spiral şəklində saat əqrəbi və əksi istiqamətində çap edin, təxminən aşağıdakı şəkillərə bənzər formada:

Əslində bu klassik və məşhur suallardan biridir. Matris kvadrat deyil, dinamik ölçülü olduqda məsələni həll etmək nisbətən daha da çətinləşir.

Bir məntiqdən yola çıxdım və tapşırığı aşağıdakı şəkildə həll etdim:

package az.mm.spiralmatrix;

import java.util.Scanner;

/**
 *
 * @author MM <[email protected]>
 */
public class Main {
    private static int row;
    private static int column;
    private int[][] matrix;

    public Main() {
        createMatrix();
    }

    public static void main(String[] args) {
        System.out.println("Please enter matrix lengths (example 4 3):");
        
        Scanner sc = new Scanner(System.in);
        row = sc.nextInt();
        column = sc.nextInt();
        Main m = new Main();
        m.spiralMatrixClockwise();
        m.spiralMatrixCounterClockwise();
    }

    private void spiralMatrixClockwise() {
        System.out.println("\nClockwise elements:");

        int left = (column%2 == 0) ? (column/2 - 1) : (column/2);
        int right = left + 1;
        int top = (row%2 == 0) ? (row/2 - 1) : (row/2);
        int bottom = top + 1;

        OUTER: while (true) {

            for (int i = left; i < right; i++) {
                if(!printElement(top, i)) break OUTER;
            }
            left--;

            for (int i = top; i < bottom; i++) {
                if(!printElement(i, right)) break OUTER;
            }
            top--;

            for (int i = right; i > left; i--) {
                if(!printElement(bottom, i)) break OUTER;
            }
            right++;

            for (int i = bottom; i > top; i--) {
                if(!printElement(i, left)) break OUTER;
            }
            bottom++;
        }
    }
    
    private void spiralMatrixCounterClockwise() {
        System.out.println("\n\nCounter Clockwise elements:");
        
        int right = column/2;
        int left = right - 1;
        int top = (row%2 == 0) ? (row/2 - 1) : (row/2);
        int bottom = top + 1;
        
        OUTER: while (true) {

            for (int i = right; i > left; i--) {
                if(!printElement(top, i)) break OUTER;
            }
            right++;

            for (int i = top; i < bottom; i++) {
                if(!printElement(i, left)) break OUTER;
            }
            top--;

            for (int i = left; i < right; i++) {
                if(!printElement(bottom, i)) break OUTER;
            }
            left--;
           
            for (int i = bottom; i > top; i--) {
                if(!printElement(i, right)) break OUTER;
            }
            bottom++;
        }
    }
    
    private boolean printElement(int i, int j) {
        if (i<0 || i>=row || j<0 || j>=column) return false;
        System.out.print(matrix[i][j] + " ");
       return true;
    }

    private void createMatrix() {
        matrix = new int[row][column];
        int value = 1;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                System.out.print((matrix[i][j] = value++) + "\t");
            }
            System.out.println();
        }
    }
}

Output:

Please enter matrix lengths (example 4 3):
4 3
1	2	3	
4	5	6	
7	8	9	
10	11	12	

Clockwise elements:
5 6 9 8 7 4 1 2 3 

Counter Clockwise elements:
5 4 7 8 9 6 3 2 1

 

Bu tapşırığı görüntülü şəkildə etməklə bağlı da ağlıma yeni bir ideya gəldi, necə alınacağı özüm üçün də maraqlı olduğundan yoxlamaq qərarına gəldim. Amma tapşırıqda görüntü istənilmirdi, sadəcə alqoritmin yazılması maraqlı idi, console print kifayət edirdi.

Spring MVC-ni yeni öyrənən vaxtlarım idi, sırf həvəs üçün və Spring MVC-də nəsə yazmağa bir bəhanə olsun deyə yazdım. Pis alınmadı, daha da yaxşı etmək olardı, amma vaxt az idi deyə çox dərinə getmədim, həm əsas lazım olanı əldə etmişdim. Məqsəd seçilmiş matrix üzərində xanaları mərkəzdən başlayaraq spiral şəklində rəngləmək və rəngləməni edərkən qırmızı rəngin artan rəng çalarlarından istifadə etmək idi.

Bu link vasitəsilə siz də test edə bilərsiniz.

Videoda gördüyünüz proyektin strukturu aşağıdakı şəkildədir:

Proyektdəki əsas class və faylları aşağıda qeyd edəcəm, ümumilikdə proyektin özünə isə github linkdən baxa bilərsiniz:

https://github.com/mmushfiq/SpiralMatrixSpringMVC

 

IndexController.java

package az.mm.spiralmatrix.controllers;

import az.mm.spiralmatrix.models.Element;
import az.mm.spiralmatrix.models.Matrix;
import az.mm.spiralmatrix.process.SpiralOrder;
import java.util.List;
import java.util.Map;
import javax.validation.Valid;
import org.springframework.stereotype.Controller;
import org.springframework.ui.Model;
import org.springframework.validation.BindingResult;
import org.springframework.web.bind.annotation.*;
import org.springframework.web.servlet.ModelAndView;

/**
 *
 * @author MM <[email protected]>
 */
@Controller
public class IndexController {

    @RequestMapping("/")
    public ModelAndView goHomePage() {
        ModelAndView model = new ModelAndView("index");
        return model;
    }
    
    @RequestMapping(value = "/create_matrix.htm", method = RequestMethod.POST)
    public ModelAndView createMatrix(@Valid @ModelAttribute("matrix") Matrix matrix, BindingResult result) {
        ModelAndView model = new ModelAndView("index");
        if (result.hasErrors()) return model;
        model.addObject("matrix", matrix);
        
        return model;
    }
    
    @ResponseBody
    @RequestMapping(value = "/spiral/elements", method = RequestMethod.GET)
    public List<Element> getElementList(@RequestParam Map<String, String> params) {
        int row = Integer.parseInt(params.get("row"));
        int column = Integer.parseInt(params.get("column"));
        String clockwise = params.get("clockwise");
        
        SpiralOrder spiralOrder = new SpiralOrder(row, column);
        List<Element> elementList;
        if("1".equals(clockwise)) 
            elementList = spiralOrder.getSpiralMatrixElementsClockwise();
        else 
            elementList = spiralOrder.getSpiralMatrixElementsCounterClockwise();
        
        return elementList;
    }
    
    @ExceptionHandler(value = Exception.class)
    public String handlerException(Exception e) {
        System.out.println("Exception occurs: " + e);
        return "exception";
    }

    @ModelAttribute
    public void addingCommonObjects(Model model) {
        model.addAttribute("matrix", new Matrix());  
    }

}

 

SpiralOrder.java

package az.mm.spiralmatrix.process;

import az.mm.spiralmatrix.models.Element;
import java.util.ArrayList;
import java.util.List;

/**
 *
 * @author MM <[email protected]>
 */
public class SpiralOrder {
    private final int row;
    private final int column;
    private final List<Element> elementList;

    public SpiralOrder(int row, int column) {
        this.row = row;
        this.column = column;
        elementList = new ArrayList<>();
    }
    
    public List<Element> getSpiralMatrixElementsClockwise() {

        int left = (column%2 == 0) ? (column/2 - 1) : (column/2);
        int right = left + 1;
        int top = (row%2 == 0) ? (row/2 - 1) : (row/2);
        int bottom = top + 1;

        OUTER: while (true) {

            for (int i = left; i < right; i++) {
                if(!printElement(top, i)) break OUTER;
            }
            left--;

            for (int i = top; i < bottom; i++) {
                if(!printElement(i, right)) break OUTER;
            }
            top--;

            for (int i = right; i > left; i--) {
                if(!printElement(bottom, i)) break OUTER;
            }
            right++;

            for (int i = bottom; i > top; i--) {
                if(!printElement(i, left)) break OUTER;
            }
            bottom++;
        }
        
        return elementList;
    }
    
    
    public List<Element> getSpiralMatrixElementsCounterClockwise() {
        
        int right = column/2;
        int left = right - 1;
        int top = (row%2 == 0) ? (row/2 - 1) : (row/2);
        int bottom = top + 1;
        
        OUTER: while (true) {

            for (int i = right; i > left; i--) {
                if(!printElement(top, i)) break OUTER;
            }
            right++;

            for (int i = top; i < bottom; i++) {
                if(!printElement(i, left)) break OUTER;
            }
            top--;

            for (int i = left; i < right; i++) {
                if(!printElement(bottom, i)) break OUTER;
            }
            left--;
           
            for (int i = bottom; i > top; i--) {
                if(!printElement(i, right)) break OUTER;
            }
            bottom++;
        }
        
        return elementList;
    }
    
    
    private boolean printElement(int i, int j) {
        if (i<0 || i>=row || j<0 || j>=column) return false;
        elementList.add(new Element(i, j));
       return true;
    }
}

 

Matrix.java

package az.mm.spiralmatrix.models;

import javax.validation.constraints.Min;

/**
 *
 * @author MM <[email protected]>
 */
public class Matrix {
    
    @Min(2)
    private String row;
    
    @Min(2)
    private String column;
    
    
    public Matrix() {
    }

    public String getRow() {
        return row;
    }

    public void setRow(String row) {
        this.row = row;
    }

    public String getColumn() {
        return column;
    }

    public void setColumn(String column) {
        this.column = column;
    }
    
}

 

Element.java

package az.mm.spiralmatrix.models;

/**
 *
 * @author MM <[email protected]>
 */
public class Element {
    private int row;
    private int column;

    public Element() {
    }

    public Element(int row, int column) {
        this.row = row;
        this.column = column;
    }
    
    public int getRow() {
        return row;
    }

    public void setRow(int row) {
        this.row = row;
    }

    public int getColumn() {
        return column;
    }

    public void setColumn(int column) {
        this.column = column;
    }
    
}

 

index.jsp

<%@page contentType="text/html" pageEncoding="UTF-8"%>
<%@taglib prefix="c" uri="http://java.sun.com/jsp/jstl/core"%>
<%@ taglib prefix="spring" uri="http://www.springframework.org/tags"%>
<%@ taglib prefix="springForm" uri="http://www.springframework.org/tags/form"%>
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
    "http://www.w3.org/TR/html4/loose.dtd">

<html>
    <head>
        <meta charset="utf-8">
        <meta http-equiv="X-UA-Compatible" content="IE=edge">
        <meta name="viewport" content="width=device-width, initial-scale=1">
        <!-- The above 3 meta tags *must* come first in the head; any other head content must come *after* these tags -->

        <c:url var="home" value="/" scope="request" />

        <title>Spiral Matrix</title>
        <link href="<c:url value="/resources/css/bootstrap.min.css" />" rel="stylesheet">
        <link href="<c:url value="/resources/css/bootstrap-theme.min.css" />" rel="stylesheet">

        <style>
            #matrix > tbody > tr > td {
                color: blue;
            }
            .error {
                color: #ff0000;
                font-style: italic;
            }
        </style>
    </head>
    <body style="background-image: url(<c:url value="/resources/img/background.png" />);">
        <div id="main-content" class="col-lg-12">
            <div class="container">
                <br/>
                <div class="well">
                    <springForm:form method="POST" class="navbar-form" commandName="matrix" action="${home}create_matrix.htm">
                        <div class="col-lg-7">
                            <springForm:input path="row" cssClass="form-control" placeholder="Row (min 2)" />
                            <springForm:errors path="row" cssClass="error" />
                            <springForm:input path="column" cssClass="form-control" placeholder="Column (min 2)" />
                            <springForm:errors path="column" cssClass="error" />
                            <input type="submit" value="Create matrix" class="btn btn-primary" style="/*float:right;*/">

                        </div>
                        <div class="col-lg-5">
                            <label class="radio-inline"><input type="radio" name="clockwise" value="1" checked>clockwise</label>
                            <label class="radio-inline"><input type="radio" name="clockwise" value="2">counter-clockwise</label>

                            <span id="run-spiral" href="#" class="btn btn-primary">Display spiral elements</span>
                        </div>
                    </springForm:form>
                    <div class="clearfix"></div>
                </div>

                <c:if test="${not empty matrix.row}">
                    <table id="matrix" class="table table-bordered">
                        <c:forEach var="row" begin="1" end="${matrix.row}">
                            <tr>
                                <c:forEach var="col" begin="1" end="${matrix.column}">
                                    <c:set var="count" value="${count + 1}" scope="page"/>
                                    <td style="width: 30px !important; text-align: center"><b>${count}</b></td>
                                </c:forEach>
                            </tr>
                        </c:forEach>
                    </table>
                </c:if>
            </div>
        </div>
    </div>

    <script src="<c:url value="/resources/js/jquery-3.2.0.min.js" />"></script>
    <script src="<c:url value="/resources/js/bootstrap.min.js" />"></script>
    <script src="<c:url value="/resources/js/index.js" />"></script>

</body>
</html>

 

index.js

//Jquery function
(function ($) {

    $("#run-spiral").click(function () {
        $('#matrix > tbody > tr > td').css('background-color', 'transparent');
        var row = $("input[name=row]").val();
        var column = $("input[name=column]").val();
        var myRadio = $('input[name=clockwise]');
        var clockwise = myRadio.filter(':checked').val();
     
        var url = "/SpiralMatrix/spiral/elements?row=" + row + "&column=" + column + "&clockwise=" + clockwise;

        var r = 255, b = 255, g = 255;
        var colors = [];
        for (var i = 0; i < 25; i++, b -= 15, g -= 15) {
            if (i < 18) {
                colors[i] = "rgb(255, " + b + ", " + g + ")";
            } else {
                r -= 15;
                colors[i] = "rgb(" + r + ", 0, 0)";
            }
            console.log('colors[' + i + ']=' + colors[i]);
        }
        for (var i = 25; i < 500; i++) {
            colors[i] = "rgb(150, 0, 0)";
        }

        $.get(url, function (data, status) {

            for (var x = 0, ln = data.length; x < ln; x++) {
                setTimeout(function (y) {
                    console.log("%d => %d", y, $("#matrix.table tr:eq(" + data[y].row + ") td:eq(" + data[y].column + ")").css("background-color", colors[y]));
                }, x * 300, x); // we're passing x
            }

        });
    });

})(jQuery);

 

Amma kod bəyənilməmişdi. Niyə görə bəyənilmədi, nələri dəyişdim, kodun son vəziyyəti necə oldu – bütün bunlarla bağlı bu məqalənin ikinci hissəsində yazacam.

You may also like

About the author

Mushfiq Mammadov

View all posts

Leave a Comment


The reCAPTCHA verification period has expired. Please reload the page.

 

This site uses Akismet to reduce spam. Learn how your comment data is processed.