Sort a list of tuples by Nth item in Python

Suppose you have a list of tuples that looks something like this:

[('abc', 121),('abc', 231),('abc', 148), ('abc',221)]

And you want to sort this list in ascending order by the integer value inside the tuples.

We can achieve this using the key keyword with sorted().

sorted([('abc', 121),('abc', 231),('abc', 148), ('abc',221)], key=lambda x: x[1])

key should be a function that identifies how to retrieve the comparable element from your data structure. For example, the second element of the tuple, so we access [1].

Source: StackOverflow.com

HackerEarth: Battle Of Bots 6: Draughts

Problem:

Sample Game

Draughts is a two player board game which is played on a 8X8 grid of cells and is played on opposite sides of the game-board. Each player has an allocated color, Red ( First Player ) or White ( Second Player ) being conventional. Players take turns involving diagonal moves of uniform game pieces in the forward direction only and mandatory captures by jumping over opponent pieces.

Rules:

  • Player can only move diagonally to the adjacent cell and in forward direction, if the diagonally adjacent cell is vacant.
  • A player may not move an opponent’s piece.
  • If the diagonally adjacent cell contains an opponent’s piece, and the cell immediately beyond it is vacant, the opponent’s piece may be captured (and removed from the game) by jumping over it in the forward direction only.
  • If a player made a jump, then its mandatory to keep on jumping as long as the jump is possible.
  • Player cannot move to the diagonally adjacent cell once the player made a jump.

The game will end when any of the players don’t have any move left. At the end of the game the player with majority of pieces will win.

We will play it on an 8X8 grid. The top left of the grid is [0,0] and the bottom right is [7,7].

Input:
The input will be a 8X8 matrix consisting only of 0o2. Then another line will follow which will contain a number –  1 or 2 which is your player id. In the given matrix, top-left is [0,0] and bottom-right is [7,7]. The x-coordinate increases from left to right, and y-coordinate increases from top to bottom.

The cell marked 0 means it doesn’t contain any stones. The cell marked 1 means it contains first player’s stone which is Red in color. The cell marked 2 means it contains second player’s stone which is white in color.

Output:
In the first line print the coordinates of the cell separated by space, the piece he / she wants to move.
In second line print an integer N, number of steps or jumps the piece will make in one move.
In the next N lines print the coordinates of the cells in which the piece will make jump.
You must take care that you don’t print invalid coordinates. For example, [1,1] might be a valid coordinate in the game play if [1,1] in diagonal to the piece in which is going to jump, but [9,10] will never be. Also if you play an invalid move or your code exceeds the time/memory limit while determining the move, you lose the game.

Starting state
The starting state of the game is the state of the board before the game starts.

0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 2 0 2 0 2 0 2
2 0 2 0 2 0 2 0

First Input
This is the input give to the first player at the start of the game.

0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 2 0 2 0 2 0 2
2 0 2 0 2 0 2 0
1
SAMPLE INPUT
0 1 0 1 0 1 0 1
1 0 1 0 1 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 2 0 0 0
0 0 0 0 0 0 0 0
0 0 2 0 0 0 0 0
0 0 0 2 0 0 0 2
2 0 2 0 2 0 2 0
1
SAMPLE OUTPUT
2 5
2
4 3
6 1

Explanation

This is player 1’s turn, and the player will move the piece at [2,5] and will make two jumps. First jump will be at [4,3and second jump will be at [6,1]

After his/her move the state of game becomes:

0 1 0 1 0 1 0 1
1 0 1 0 1 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 1 0 2 0 2 0 2
2 0 2 0 2 0 2 0

This state will be fed as input to program of player 2.

Other valid move for the first player is

2 5
1
3 6

But the following are invalid moves.
Case 1:

2 5
1
4 3

Because after making a jump its possible to jump again and its mandatory to jump as long as its possible to jump.

Case 2:

2 5
2
4 3
5 4

Because after making a jump its invalid to move to diagonally adjacent cell.

Here is the code of the Random Bot.

Time Limit:1.0 sec(s) for each input file.
Memory Limit:256 MB
Source Limit:1024 KB

Solution

This is the solution submitted by me

What is the dumbest code ever made that has become famous?

BogoSort is a moderately well-known algorithm to sort a list. Here’s how it works:

  1. Put the elements of the list in a random order.
  2. Check if the list is sorted. If not, start over.

BogoSort has an average running time of O((n+1)!), which is not very good. It is also the rare algorithm which has NO worst-case running time; if the input has at least two elements, it is possible for the algorithm to run for any amount of time.

Source: Quora

HackerRank: Manasa and Stones

Problem

Manasa is out on a hike with friends. She finds a trail of stones with numbers on them. She starts following the trail and notices that two consecutive stones have a difference of either a or b. Legend has it that there is a treasure trove at the end of the trail and if Manasa can guess the value of the last stone, the treasure would be hers. Given that the number on the first stone was 0, find all the possible values for the number on the last stone.

Note: The numbers on the stones are in increasing order.

Input Format
The first line contains an integer T, i.e. the number of test cases. T test cases follow; each has 3 lines. The first line contains nn (the number of stones). The second line contains a, and the third line contains b.

Output Format
Space-separated list of numbers which are the possible values of the last stone in increasing order.

Constraints
1T10
1n,a,b10^3

Sample Input

2
3 
1
2
4
10
100

Sample Output

2 3 4 
30 120 210 300 

Explanation

All possible series for the first test case are given below:

  1. 0,1,2
  2. 0,1,3
  3. 0,2,3
  4. 0,2,4

Hence the answer 2 3 4.

Series with different number of final steps for second test case are the following:

  1. 0, 10, 20, 30
  2. 0, 10, 20, 120
  3. 0, 10, 110, 120
  4. 0, 10, 110, 210
  5. 0, 100, 110, 120
  6. 0, 100, 110, 210
  7. 0, 100, 200, 210
  8. 0, 100, 200, 300

Hence the answer 30 120 210 300.

Solution

Original solution source

Bubble Sort Algorithm

Below is the code to do Bubble Sorting in Java for integer values

public class BubbleSort {
  
    // logic to sort the elements
    public static void srtbubble(int array[]) {
        int n = array.length;
        int k;
        for (int m = n; m >= 0; m--) {
            for (int i = 0; i < n - 1; i++) { k = i + 1; if (array[i] > array[k]) {
                    swap(i, k, array);
                }
            }
            print(array);
        }
    }
  
    private static void swap(int i, int j, int[] array) {
  
        int temp;
        temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
  
    private static void print(int[] input) {
          
        for (int i = 0; i < input.length; i++) {
            System.out.print(input[i] + ", ");
        }
        System.out.println("\n");
    }
  
    public static void main(String[] args) {
        int[] input = { 14, 21, 19, 62, 233, 142, 134, 10, 41 };
        srtbubble(input);
    }
}


Output:

14, 19, 21, 62, 142, 134, 10, 41, 233, 

14, 19, 21, 62, 134, 10, 41, 142, 233, 

14, 19, 21, 62, 10, 41, 134, 142, 233, 

14, 19, 21, 10, 41, 62, 134, 142, 233, 

14, 19, 10, 21, 41, 62, 134, 142, 233, 

14, 10, 19, 21, 41, 62, 134, 142, 233, 

10, 14, 19, 21, 41, 62, 134, 142, 233, 

10, 14, 19, 21, 41, 62, 134, 142, 233, 

10, 14, 19, 21, 41, 62, 134, 142, 233, 

10, 14, 19, 21, 41, 62, 134, 142, 233,

File Sorting based on parameters

Many times our file directories are full of files that we may like to be sorted in some particular manner. Below is the code to sort the files as per the following ways:

  • Month Sorting
  • Alphabetic Sorting
  • Music Album Sorting
  • Extension Sorting
import java.io.File;

import java.text.ParseException;
import java.text.SimpleDateFormat;

import java.util.Date;
import java.util.Scanner;
import java.util.TreeSet;

import org.blinkenlights.jid3.ID3Tag;
import org.blinkenlights.jid3.MP3File;
import org.blinkenlights.jid3.MediaFile;
import org.blinkenlights.jid3.v2.ID3V2_3_0Tag;

public class FileSorter {
    private Date getLastModified(File file) {
        return new Date(file.lastModified());
    }

    private String convert(Date file) throws ParseException {
        return new SimpleDateFormat("yyyy-MM").format(file.getTime());
    }

    public static void main(String[] args) {
        FileSorter p = new FileSorter();
        Scanner in = new Scanner(System.in);
        System.out.println("Please enter the folder path that you want sorted: ");
        String filePath = in.nextLine();
        System.out.println("Please enter what kind of sorting you want??");
        System.out.println("   1. Month Sorting");
        System.out.println("   2. Alphabetic Sorting");
        System.out.println("   3. Music Album Sorting");
        System.out.println("   5. Extension Sorting");
        try {
            int s = Integer.parseInt(in.nextLine());
            switch (s) {
            case 1:
                p.startSort(filePath);
                break;
            case 2:
                p.alphaSort(filePath);
                break;
            case 3:
                p.startMusicSort(filePath);
                break;
            case 5:
                p.extnSort(filePath);
                break;
            default:
                System.out.println("Invalid Option");
                break;
            }

        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    public String getRange(String path) {
        String ret_String = "";
        for (int i = 97; i <= 122; i++) { if ((int) path.toLowerCase().charAt(0) >= i && (int) path.toLowerCase().charAt(0) <= (i + 3)) { ret_String = ((char) i + "-" + ((char) (i + 3))); break; } else if ((int) path.toLowerCase().charAt(0) >= 32 && (int) path.toLowerCase().charAt(0) <= 64) {
                ret_String = ("#0-9");
                break;
            } else {
                i += 3;
            }
        }
        return ret_String;
    }

    public void startSort(String filePath) throws Exception, ParseException {

        File dir = new File(filePath);
        File folder = null;
        String newFilePath = null;
        TreeSet ts = new TreeSet();

        if (dir.isDirectory()) {

            for (File file : dir.listFiles()) {
                newFilePath = convert(getLastModified(file));
                ts.add(newFilePath);
            }

            for (String o : ts) {
                folder = new File(filePath + "\" + o);
                folder.mkdirs();

                for (File file : dir.listFiles()) {
                    newFilePath = convert(getLastModified(file));
                    if (newFilePath.equals(o)) {
                        if (file.isFile()) {
                            file.renameTo(new File(filePath + "\" + o + "\" + file.getName()));
                        }
                    }
                }
            }
        }
    }

    public void alphaSort(String filePath) throws Exception, ParseException {

        File dir = new File(filePath);
        File folder = null;
        String newFilePath = null;
        TreeSet ts = new TreeSet();

        if (dir.isDirectory()) {

            for (File file : dir.listFiles()) {
                newFilePath = getRange(file.getName());
                ts.add(newFilePath);
            }

            for (String o : ts) {
                folder = new File(filePath + "\" + o);
                folder.mkdirs();

                for (File file : dir.listFiles()) {
                    newFilePath = getRange(file.getName());
                    if (newFilePath.equals(o)) {
                        if (file.isFile()) {
                            file.renameTo(new File(filePath + "\" + o + "\" + file.getName()));
                        }
                    }
                }
            }
        }
    }

    public void extnSort(String filePath) throws Exception, ParseException {

        File dir = new File(filePath);
        File folder = null;
        String newFilePath = null;
        TreeSet ts = new TreeSet();

        if (dir.isDirectory()) {

            for (File file : dir.listFiles()) {
                if (file.getName().lastIndexOf(".") > 0) {
                    newFilePath =
                        (file.getName().substring(file.getName().lastIndexOf(".") + 1,
                                                  file.getName().length())).toLowerCase();
                } else {
                    continue;
                }
                ts.add(newFilePath);
            }

            for (String o : ts) {
                folder = new File(filePath + "\" + o);
                folder.mkdirs();

                for (File file : dir.listFiles()) {
                    if (file.getName().lastIndexOf(".") > 0) {
                        newFilePath =
                            (file.getName().substring(file.getName().lastIndexOf(".") + 1,
                                                      file.getName().length())).toLowerCase();
                    } else {
                        continue;
                    }

                    if (newFilePath.equals(o)) {
                        if (file.isFile()) {
                            file.renameTo(new File(filePath + "\" + o + "\" + file.getName()));
                        }
                    }
                }
            }
        }
    }

    public void startMusicSort(String filePath) throws Exception, ParseException {

        File dir = new File(filePath);
        File folder = null;
        String newFilePath = null;
        TreeSet ts = new TreeSet();

        if (dir.isDirectory()) {

            for (File file : dir.listFiles()) {
                newFilePath = (getAlbumName(file));
                ts.add(newFilePath);
            }

            for (String o : ts) {
                folder = new File(filePath + "\" + o);
                folder.mkdirs();

                for (File file : dir.listFiles()) {
                    newFilePath = (getAlbumName(file));
                    if (newFilePath.equals(o)) {
                        if (file.isFile()) {
                            file.renameTo(new File(filePath + "\" + o + "\" + file.getName()));
                        }
                    }
                }
            }
        }
    }

    private String getAlbumName(File oSourceFile) {
        MediaFile oMediaFile = new MP3File(oSourceFile);
        ID3Tag[] aoID3Tag;
        try {
            aoID3Tag = oMediaFile.getTags();
            for (int i = 0; i < aoID3Tag.length; i++) {
                if (aoID3Tag[i] instanceof ID3V2_3_0Tag) {
                    ID3V2_3_0Tag oID3V2_3_0Tag = (ID3V2_3_0Tag) aoID3Tag[i];
                    try {
                        return ("".equals(oID3V2_3_0Tag.getAlbum().trim()) ? "Misc" :
                                oID3V2_3_0Tag.getAlbum().replaceAll(""", "")); // reads TYER frame
                    } catch (Exception e) {
                        e.getStackTrace();
                    }
                }
            }
        } catch (Exception e) {
            e.getStackTrace();
        }
        return "Misc";
    }

    public String toString() {
        return super.toString();
    }
}

Libraries can be found at:

Comparable vs Comparator

There are many articles available on internet for this. But still I would write something about it.

What when and why?

A Comparable class is a class, which can be compared with the objects of its own type. Let us take an example of a book.

public class Book implements Comparable {
    String title;
    int    isbn;

    Book(String title, int isbn) {
        this.title = title;
        this.isbn  = isbn;
    }
    /* This method will be the default method used 
       to sort Book objects in a list or Array */
    public int compareTo(Object object) {
    // It should throw NullPointerException if object passed is null
    if (object==null)
    {
        throw new NullPointerException("compareTo: Argument passed is null");
    }
        Book other = (Book) object;
        if (this.title.equals(other.title)) {
            return this.isbn - other.isbn;
        }
        return this.title.compareTo(other.title);
    }
}

The moment your class implements Comparable, you can then use

List list = new LinkedList();
        list.add(new Book("Patterns", 12345));
        list.add(new Book("Apples", 34567));
        list.add(new Book("Examples", 23456));

        Collections.sort(list);


Using this you can sort your list.

But what if now, you want to add or use another sorting criteria defined in Book class… Here comes the need of Comparator.
There are two ways listed here to use the Comparator class.

First method

We create a anonymous class that implements Comparator and overrides compare method.

Collections.sort(list, new Comparator() {
            public int compare(Object obj1, Object obj2) {
                if(obj1 == null || obj2 == null){
                    throw new NullPointerException("compareTo: Argument passed is null");
                }
                Book book1 = (Book) obj1;
                Book book2 = (Book) obj2;
                return book1.isbn - book2.isbn;
            }
        });

 

Second Method

You define a class that implements Comparator like as below.

class BookComparator implements Comparator{
   
    public int compare(Object book1, Object book2){
   
        int b1= ((Book)book1).isbn;        
        int b2= ((Book)book2).isbn;
       
        if(b1> b2)
            return 1;
        else if(b1< b2)
            return -1;
        else
            return 0;    
    }
   
}

And use this newly defined comparator class as an argument to Collections.sort.

Arrays.sort(list, new BookComparator ());

Good reasons to use Comparator interface

  • I do not have permissions to edit the Book class.
  • Book class already implements Comparable interface, but I want to sort the objects using a different criteria
  • I want to have more than 1 criterias to sort the objects in different orders.

Reasons to implement Comparable interface

  • I want my class to have a default sorting criteria that can be used by the users of my class
  • Usually, one would like to sort the objects based on primary key

Few good links on this topic are here http://www.javadeveloper.co.in/java-example/java-comparator-example.htmlhttp://grdurand.com/static/presentation_four/comparable.htmlhttp://javarevisited.blogspot.com/2011/06/comparator-and-comparable-in-java.html