Skip to content

Instantly share code, notes, and snippets.

@nstanevski

nstanevski/01_FillTheMatrix.cs

Last active August 29, 2015 14:20
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save nstanevski/8d614eabc00f2ee39219 to your computer and use it in GitHub Desktop.
Save nstanevski/8d614eabc00f2ee39219 to your computer and use it in GitHub Desktop.
Download ZIP
Homework 02 - Multidimensional Arrays, Sets, Dictionaries
Raw
01_FillTheMatrix.cs
using System;
/*
* Write two programs that fill and print a matrix of size N x N.
* Filling a matrix in the regular pattern (top to bottom and left to right) is boring.
* Fill the matrix as described in both patterns below
* Example 1:
* 1 6 11 16 21
* 2 7 12 17 22
* 3 8 13 18 23
* 4 9 14 19 24
* 5 10 15 20 25
* Example 2:
* 1 10 11 20 21
* 2 9 12 19 22
* 3 8 13 18 23
* 4 7 14 17 24
* 5 6 15 16 25
*
*/
class FillTheMatrix
{
private static void TransposeMatrix(int[,] matrix)
{
int size = matrix.GetLength(0);
for (int i = 0; i < size; i++)
for (int j = i; j < size; j++)
{
int tmp = matrix[j, i];
matrix[j, i] = matrix[i, j];
matrix[i, j] = tmp;
}
}
private static void ReverseEvenRows(int[,] matrix)
{
int len = matrix.GetLength(0);
for (int i = 0; i < len; i++)
if (i % 2 == 1)
{
for (int j = 0; j < len/2 ; j++)
{
int tmp = matrix[i, j];
matrix[i, j] = matrix[i, len- j-1];
matrix[i, len-j-1] = tmp;
}
}
}
private static void PrintSquareMatrix(int[,] matrix)
{
int size = matrix.GetLength(0);
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
Console.Write("\t{0}", matrix[i, j]);
Console.WriteLine();
}
}
static void Main()
{
int size = int.Parse(Console.ReadLine());
//init matrix
int[,] matrix = new int[size, size];
for (int i = 0; i < size; i++)
for (int j = 0; j < size; j++)
matrix[i, j] = i * size + j + 1;
//transpose in-place
TransposeMatrix(matrix);
PrintSquareMatrix(matrix);
Console.WriteLine();
//transpose again to restore the original matrix
TransposeMatrix(matrix);
ReverseEvenRows(matrix);
TransposeMatrix(matrix);
PrintSquareMatrix(matrix);
}
}
Raw
02_MaximalSum.cs
using System;
using System.Linq;
/*
* Write a program that reads a rectangular integer matrix of size N x M 
* and finds in it the square 3 x 3 that has maximal sum of its elements.
* On the first line, you will receive the rows N and columns M.
* On the next N lines you will receive each row with its columns.
* Print the elements of the 3 x 3 square as a matrix, along with their sum.
*/
class MaximalSum
{
static void Main()
{
//get dimensions:
int[] dimensions = Console.ReadLine().Trim().Split().Select(p => int.Parse(p)).ToArray();
int numRows = dimensions[0], numCols = dimensions[1];
//initialize matrix:
int[,] matrix = new int[numRows, numCols];
for (int i = 0; i < numRows; i++)
{
int[] row = Console.ReadLine().Trim().Split().Select(p => int.Parse(p)).ToArray();
for (int j = 0; j < numCols; j++)
{
matrix[i, j] = row[j];
}
}
//find 3x3 platform with maximum sum
int maxSum = int.MinValue, maxSumRow = 0, maxSumCol = 0;
for (int row = 0; row < numRows - 2; row++)
{
for (int col = 0; col < numCols - 2; col++)
{
int currentSum = 0;
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
currentSum += matrix[row + i, col + j];
}
}
if (currentSum > maxSum)
{
maxSum = currentSum;
maxSumRow = row;
maxSumCol = col;
}
}
}
//print the result
Console.WriteLine("Sum: {0}", maxSum);
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
Console.Write("{0}\t", matrix[maxSumRow + i, maxSumCol + j]);
}
Console.WriteLine();
}
}
}
Raw
03_ShuffleMatrix.cs
using System;
/*
*Write a program which reads a string matrix from the console and performs certain operations
*with its elements. User input is provided like in the problem above – first you read
*the dimensions and then the data. Remember, you are not required to do this step first,
*you may add this functionality later.
* Your program should then receive commands in format: "swap x1 y1 x2 y2" where x1, x2, y1, y2
* are coordinates in the matrix. In order for a command to be valid, it should start with the
* "swap" keyword along with four valid coordinates (no more, no less). You should swap
* the values at the given coordinates (cell [x1, y1] with cell [x2, y2]) and print
* the matrix at each step (thus you'll be able to check if the operation was performed correctly).
* If the command is not valid (doesn't contain the keyword "swap", has fewer or more coordinates
* entered or the given coordinates do not exist), print "Invalid input!" and move
* on to the next command. Your program should finish when the string "END" is entered.
*/
class ShuffleMatrix
{
private static int numRows = 0;
private static int numCols = 0;
private static string[,] matrix;
private static bool validCommand(string[] cmdItems)
{
if (cmdItems.Length != 5 || !cmdItems[0].Equals("SWAP"))
return false;
int rowFrom = int.Parse(cmdItems[1]);
int colFrom = int.Parse(cmdItems[2]);
int rowTo = int.Parse(cmdItems[3]);
int colTo = int.Parse(cmdItems[4]);
if (!(rowFrom >= 0 && rowFrom < numRows))
return false;
if (!(rowTo >= 0 && rowTo < numRows))
return false;
if (!(colFrom >= 0 && colFrom < numCols))
return false;
if (!(colTo >= 0 && colTo < numCols))
return false;
return true;
}
private static void SwapValues(int rowFrom, int colFrom, int rowTo, int colTo)
{
string buffer = matrix[rowFrom, colFrom];
matrix[rowFrom, colFrom] = matrix[rowTo, colTo];
matrix[rowTo, colTo] = buffer;
}
private static void PrintMatrix()
{
for (int i = 0; i < matrix.GetLength(0); i++)
for (int j = 0; j < matrix.GetLength(1); j++)
{
Console.Write("{0}\t", matrix[i, j]);
}
Console.WriteLine();
}
static void Main()
{
//read dimensions, initialize matrix
numRows = int.Parse(Console.ReadLine().Trim());
numCols = int.Parse(Console.ReadLine().Trim());
matrix = new string[numRows, numCols];
for (int rowIndex = 0; rowIndex < numRows; rowIndex++)
for (int colIndex = 0; colIndex < numCols; colIndex++)
matrix[rowIndex, colIndex] = Console.ReadLine().Trim();
//process commands
string command = Console.ReadLine().ToUpper();
while (command != "END")
{
string[] cmdItems = command.Split();
if (!validCommand(cmdItems))
{
Console.WriteLine("Invalid input");
}
else
{
int rowFrom = int.Parse(cmdItems[1]);
int colFrom = int.Parse(cmdItems[2]);
int rowTo = int.Parse(cmdItems[3]);
int colTo = int.Parse(cmdItems[4]);
SwapValues(rowFrom, colFrom, rowTo, colTo);
PrintMatrix();
}
command = Console.ReadLine().ToUpper();
}
}
}
Raw
04_SequenceInMatrix.cs
using System;
/*
* We are given a matrix of strings of size N x M. Sequences in the matrix we define
* as sets of several neighbour elements located on the same line, column or diagonal.
* Write a program that finds the longest sequence of equal strings in the matrix.
*/
class SequenceInMatrix
{
private static int numRows = 0;
private static int numCols = 0;
private static string[,] matrix;
private static int countEquals(int rowIndex, int colIndex)
{
string val = matrix[rowIndex, colIndex];
int n = colIndex; int m = 0;
int seqSize = 1, maxSize=1;
//check for equal neighbours in the same row
while(n<matrix.GetLength(1)-1 && val.Equals(matrix[rowIndex, n+1])){
n++;
seqSize++;
}
if (seqSize > maxSize)
maxSize = seqSize;
//check for equal neighbours in the same col
seqSize = 1; n = rowIndex;
while (n < matrix.GetLength(0) - 1 && val.Equals(matrix[n+1, colIndex]))
{
n++;
seqSize++;
}
if (seqSize > maxSize)
maxSize = seqSize;
//check for equal neighbours in the same main diagonal
seqSize = 1; n = colIndex; m = rowIndex;
while (n < matrix.GetLength(1) - 1 && m<matrix.GetLength(0)-1
&& val.Equals(matrix[m + 1, n + 1]))
{
n++; m++;
seqSize++;
}
if (seqSize > maxSize)
maxSize = seqSize;
//check for equal neighbours in the same secondary diagonal
seqSize = 1; n = colIndex; m = rowIndex;
while (n > 0 && m < matrix.GetLength(0) - 1
&& val.Equals(matrix[m + 1, n - 1]))
{
n--; m++;
seqSize++;
}
if (seqSize > maxSize)
maxSize = seqSize;
return maxSize;
}
private static void PrintSequence(int maxLen, int maxRowInd, int maxColInd)
{
for (int i = 0; i < maxLen; i++)
{
Console.Write(matrix[maxRowInd, maxColInd]);
if(i<maxLen-1)
Console.Write(", ");
}
Console.WriteLine();
}
static void Main()
{
//read dimensions, initialize matrix
numRows = int.Parse(Console.ReadLine().Trim());
numCols = int.Parse(Console.ReadLine().Trim());
matrix = new string[numRows, numCols];
for (int rowIndex = 0; rowIndex < numRows; rowIndex++)
for (int colIndex = 0; colIndex < numCols; colIndex++)
matrix[rowIndex, colIndex] = Console.ReadLine().Trim();
//process
int maxLen = 1, maxRowInd = 0, maxColInd = 0;
for (int rowIndex = 0; rowIndex < numRows; rowIndex++){
for (int colIndex = 0; colIndex < numCols; colIndex++)
{
int numEquals = countEquals(rowIndex, colIndex);
if (numEquals > maxLen)
{
maxLen = numEquals;
maxRowInd = rowIndex;
maxColInd = colIndex;
}
}
}
PrintSequence(maxLen, maxRowInd, maxColInd);
}
}
Raw
05_CollectTheCoins.cs
using System;
using System.Collections.Generic;
using System.Linq;
/*
* You receive the layout of a board from the console. Assume it will always have 4 rows
* which you'll get as strings, each on a separate line. Each character in the strings
* will represent a cell on the board. Note that the strings may be of different length.
* You are the player and start at the top-left corner (that would be position [0, 0] on the board).
* On the fifth line of input you'll receive a string with movement commands which tell you
* where to go next, it will contain only these four characters – '>' (move right),
* '<' (move left), '^' (move up) and 'v' (move down).
* You need to keep track of two types of events – collecting coins (represented by the symbol '$',
* of course) and hitting the walls of the board (when the player tries to move off the board
* to invalid coordinates). When all moves are over, print the amount of money collected
* and the number of walls hit.
*/
class CollectTheCoins
{
private static bool CoinFound(List<char>[] board, int rowInd, int colInd)
{
if(board[rowInd][colInd] == '$'){
board[rowInd][colInd] = '*'; //mark as collected coin
return true;
}
return false;
}
static void Main()
{
//init board
List<char>[] board = new List<char>[4];
for (int i = 0; i < 4; i++)
{
List<char> line = Console.ReadLine().Trim().ToCharArray().ToList();
board[i] = line;
}
char[] directions = Console.ReadLine().Trim().ToCharArray();
int currRow = 0, currCol = 0;
int numCoins = 0, numWalls = 0;
//walking
foreach (char dir in directions)
{
switch (dir)
{
case '^':
if (currRow == 0)
{
numWalls++;
}
else
{
if (board[currRow - 1].Count - 1 < currCol)
{
numWalls++;
}
else
{
currRow--;
if (CoinFound(board, currRow, currCol))
numCoins++;
}
}
break;
case 'V':
if (currRow == 3)
{
numWalls++;
}
else
{
if (board[currRow + 1].Count - 1 < currCol)
{
numWalls++;
}else{
currRow++;
if (CoinFound(board, currRow, currCol))
numCoins++;
}
}
break;
case '>':
List<char> row = board[currRow];
if(currCol == row.Count - 1){
numWalls++;
}else
{
currCol++;
if (CoinFound(board, currRow, currCol))
numCoins++;
}
break;
case '<':
row = board[currRow];
if(currCol == 0){
numWalls++;
}else
{
currCol--;
if (CoinFound(board, currRow, currCol))
numCoins++;
}
break;
}
}
Console.WriteLine("Coins collected: {0}\nWalls hit: {1}", numCoins, numWalls);
}
}
Raw
06_CountSymbols.cs
using System;
using System.Collections.Generic;
using System.Linq;
/*
* Write a program that reads some text from the console and counts the occurrences
* of each character in it. Print the results in alphabetical (lexicographical) order.
*/
class CountSymbols
{
static void Main()
{
char[] inputArr = Console.ReadLine().ToCharArray();
Dictionary<char, int> counter = new Dictionary<char, int>();
foreach (char inputChar in inputArr)
{
if (counter.ContainsKey(inputChar))
counter[inputChar]++;
else
counter.Add(inputChar, 1);
}
char[] orderedKeys = counter.Keys.OrderBy(p => p).ToArray();
foreach (char key in orderedKeys)
Console.WriteLine("{0}: {1} time(s)", key, counter[key]);
}
}
Raw
07_PhoneBook.cs
using System;
using System.Collections.Generic;
using System.Linq;
class PhoneBook
{
static void Main()
{
string line = Console.ReadLine().Trim();
Dictionary<string, string> phonebook = new Dictionary<string, string>();
//fill the phonebook
while (!line.Equals("search"))
{
string[] items = line.Split('-');
if (phonebook.ContainsKey(items[0]))
phonebook.Remove(items[0]);
phonebook.Add(items[0], items[1]);
line = Console.ReadLine().Trim();
}
//print search results:
line = Console.ReadLine().Trim();
while (line.Length > 0)
{
if (phonebook.ContainsKey(line))
Console.WriteLine("{0} -> {1}", line, phonebook[line]);
else
Console.WriteLine("Contact {0} does not exist.", line);
line = Console.ReadLine().Trim();
}
}
}
Raw
08_NightLife.cs
using System;
using System.Collections.Generic;
using System.Linq;
/*
* There will be an arbitrary number of lines until you receive the string "END".
* Each line will contain data in format: "city;venue;performer". If either city, venue
* or performer don't exist yet in the database, add them. If either the city and/or venue
* already exist, update their info.
* Cities should remain in the order in which they were added, venues should be sorted
* alphabetically and performers should be unique (per venue) and also sorted alphabetically.
* Print the data by listing the cities and for each city its venues
* (on a new line starting with "->") and performers (separated by comma and space).
*/
class NightLife
{
static void Main()
{
Dictionary<string, SortedDictionary<string, SortedSet<string>>> program =
new Dictionary<string, SortedDictionary<string, SortedSet<string>>>();
String inputLine = Console.ReadLine().Trim();
while (!inputLine.Equals("END"))
{
string[] items = inputLine.Split(';');
string city = items[0];
string venue = items[1];
string performer = items[2];
if (!program.ContainsKey(city))
{
SortedDictionary<string, SortedSet<string>> cityProgram =
new SortedDictionary<string, SortedSet<string>>();
program[city] = cityProgram;
}
if (!program[city].ContainsKey(venue))
{
SortedSet<string> cityVenueProgram = new SortedSet<string>();
program[city][venue] = cityVenueProgram;
}
program[city][venue].Add(performer);
inputLine = Console.ReadLine().Trim();
}
//print results
foreach (string city in program.Keys)
{
Console.WriteLine(city);
SortedDictionary<string, SortedSet<string>> cityVenues = program[city];
foreach (string venue in cityVenues.Keys)
{
SortedSet<string> performers = cityVenues[venue];
string performersStr = string.Join(", ", performers);
Console.WriteLine("->{0}: {1}", venue, performersStr);
}
}
}
}
Raw
10_PlusRemove.cs
using System;
using System.Linq;
using System.Collections.Generic;
/*
* https://judge.softuni.bg/Contests/Practice/Index/84#0
*/
class PlusRemove
{
private static List<List<char>> text = new List<List<char>>();
private static bool checkForPlus(int rowIndex, int colIndex)
{
char ch = text[rowIndex][colIndex];
char ch2 = text[rowIndex][colIndex+1];
char ch3 = text[rowIndex][colIndex+2];
if (!(text[rowIndex - 1].Count > colIndex + 1))
return false;
if (!(text[rowIndex + 1].Count > colIndex + 1))
return false;
char ch4 = text[rowIndex-1][colIndex + 1];
char ch5 = text[rowIndex + 1][colIndex + 1];
if (Char.ToUpper(ch).Equals(Char.ToUpper(ch2)) && Char.ToUpper(ch).Equals(Char.ToUpper(ch3)) &&
Char.ToUpper(ch).Equals(Char.ToUpper(ch4)) && Char.ToUpper(ch).Equals(Char.ToUpper(ch5))
)
return true;
return false;
}
static void Main()
{
string line = Console.ReadLine();
while (!line.Equals("END"))
{
List<char> lineChars = line.ToList<char>();
text.Add(lineChars);
line = Console.ReadLine();
}
//process each row
bool isPlusShape = false;
HashSet<KeyValuePair<int, int>> plusCoordsSet = new HashSet<KeyValuePair<int, int>>();
for (int rowIndex = 1; rowIndex < text.Count - 1; rowIndex++)
{
for (int colIndex = 0; colIndex < text[rowIndex].Count - 2; colIndex++)
{
isPlusShape = checkForPlus(rowIndex, colIndex);
if (isPlusShape)
{
plusCoordsSet.Add(new KeyValuePair<int,int>(rowIndex, colIndex));
plusCoordsSet.Add(new KeyValuePair<int,int>(rowIndex, colIndex+1));
plusCoordsSet.Add(new KeyValuePair<int,int>(rowIndex, colIndex+2));
plusCoordsSet.Add(new KeyValuePair<int,int>(rowIndex-1, colIndex+1));
plusCoordsSet.Add(new KeyValuePair<int,int>(rowIndex+1, colIndex+1));
}
}
}
for (int rowInd = 0; rowInd < text.Count; rowInd++)
{
for (int colInd = 0; colInd < text[rowInd].Count; colInd++)
{
KeyValuePair<int, int> current = new KeyValuePair<int, int>(rowInd, colInd);
if (!plusCoordsSet.Contains(current))
{
Console.Write(text[rowInd][colInd]);
}
}
Console.WriteLine();
}
}
}
Raw
11_StringMatrixRotation.cs
using System;
using System.Collections.Generic;
using System.Text.RegularExpressions;
using System.Linq;
//https://judge.softuni.bg/Contests/Practice/Index/84#1
class StringMatrixRotation
{
private static List<List<char>> rotateText90(List<List<char>> text)
{
List<List<char>> res = new List<List<char>>();
//convert list to array of chars
char[,] chArr = new char[text.Count, text[0].Count];
for (int i = 0; i < text.Count; i++)
for (int j = 0; j < text[0].Count; j++)
chArr[i, j] = text[i][j];
//rotate the array
char[,] chArrRotated = new char[text[0].Count, text.Count];
for (int i = 0; i < text.Count; i++)
for (int j = 0; j < text[0].Count; j++)
chArrRotated[j, text.Count-i - 1]= chArr[i,j];
//convert rotated array back to list
for(int i=0; i<chArrRotated.GetLength(0); i++){
List<char> lineList = new List<char>();
for (int j = 0; j < chArrRotated.GetLength(1); j++)
lineList.Add(chArrRotated[i, j]);
res.Add(lineList);
}
return res;
}
static void Main()
{
//extract rotation value
string line = Console.ReadLine();
int rotation = int.Parse(Regex.Match(line, @"\d+").Value);
List<List<char>> text = new List<List<char>>();
rotation %= 360;
line = Console.ReadLine();
int maxLineLen = 0;
while(!line.Equals("END")){
maxLineLen = Math.Max(maxLineLen, line.Length);
List<char> lineList = line.ToCharArray().ToList();
text.Add(lineList);
line = Console.ReadLine();
}
//pad shorter strings with spaces:
foreach (List<char> lineList in text)
while (lineList.Count < maxLineLen)
lineList.Add(' ');
for (int i = 0; i < rotation / 90; i++)
text = rotateText90(text);
foreach(List <char> l in text){
foreach (char ch in l)
Console.Write(ch);
Console.WriteLine();
}
}
}
Raw
12_ToTheStars.cs
using System;
using System.Collections.Generic;
//https://judge.softuni.bg/Contests/Practice/Index/31#2
class ToTheStars
{
private static Dictionary<string, double[]> starProperties = new Dictionary<string, double[]>();
private static string GetLocation(double[] spaceShipCoord)
{
foreach (string starName in starProperties.Keys)
{
double[] starCoord = starProperties[starName];
if(spaceShipCoord[0] >= starCoord[0] - 1 && spaceShipCoord[0] <= starCoord[0] + 1
&& spaceShipCoord[1] >= starCoord[1] - 1 && spaceShipCoord[1] <= starCoord[1] + 1)
{
return starName.ToLower();
}
}
return "space";
}
static void Main()
{
//initialize dictionary of stars:
string[] items;
//Dictionary<string, double[]> starProperties = new Dictionary<string, double[]>();
for (double i = 0; i < 3; i++)
{
items = Console.ReadLine().Split();
double[]starCoords = {double.Parse(items[1]), double.Parse(items[2])};
starProperties.Add(items[0],starCoords);
}
items = Console.ReadLine().Split();
double[] spaceShipCoords = { double.Parse(items[0]), double.Parse(items[1]) };
double numTurns = double.Parse(Console.ReadLine());
for (double i = 0; i <= numTurns; i++)
{
string location = GetLocation(spaceShipCoords);
Console.WriteLine(location);
spaceShipCoords[1]++;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment