Create a simple sudoku solver.
The input is a 81 digit string. Blank squares are zero's
Output is an 81 digit string with the solved puzzle
The test cases are simple enough that back tracking should be possible within the given time.
Good luck
#import <vector>
#import <unordered_set>
std::vector<std::vector<int>> puzzle;
std::vector<int> get_row(int r)
{
return puzzle[r];
}
std::vector<int> get_col(int c)
{
std::vector<int> col;
for (int r = 0; r < 9; r++)
{
col.push_back(puzzle[r][c]);
}
return col;
}
std::vector<int> get_block(int r, int c)
{
std::vector<int> block;
r = r / 3 * 3; //this gives the top row for the block of the given r. by abusing that int floors numbers ex 5/3 = 1 *3 = 3;
c = c / 3 * 3;
for (int y = r; y < r + 3; y++)
{
for (int x = c; x < c + 3; x++)
{
block.push_back(puzzle[y][x]);
}
}
return block;
}
std::unordered_set<int> get_options(int r, int c)
{
if (puzzle[r][c] != 0)
return {puzzle[r][c]};
std::unordered_set<int> options = {1, 2, 3, 4, 5, 6, 7, 8, 9};
std::vector<int> row = get_row(r);
std::vector<int> col = get_col(c);
std::vector<int> block = get_block(r, c);
for (int i = 0; i < 9; i++)
{
options.erase(row[i]);
options.erase(col[i]);
options.erase(block[i]);
}
return options;
}
bool backtrack(int r = 0, int c = 0)
{
if (r == 9)
return true; //returns true if you've finished the last row
int r2, c2;
while (puzzle[r][c] != 0) //if the square is already set, try next ones until you find a 0
{
if (c == 8) //calculate the next piece
{
c = 0;
r++;
}
else
c++;
if (r > 8)
return true; //if you find the end of the puzzle before a zero, return true.
}
if (c == 8) //calculate the next piece
{
c2 = 0;
r2 = r + 1;
}
else
{
r2 = r;
c2 = c + 1;
}
std::unordered_set<int> options = get_options(r, c);
if (options.size() == 0)
return false; //if there are no options something must have gone wrong before. return false
for (int o : options)
{
puzzle[r][c] = o; //set the square to one of the options
if (backtrack(r2, c2) == true)
return true;
puzzle[r][c] = 0; //return the square to 0;
}
return false;
}
std::string toString()
{
std::string puzzle_string;
for (int r = 0; r < 9; r++)
{
for (int c = 0; c < 9; c++)
{
puzzle_string += std::to_string(puzzle[r][c]);
}
}
return puzzle_string;
}
void set_puzzle(std::string puzzleString)
{
std::vector<std::vector<int>> newPuzzle;
for (int r = 0; r < 9; r++)
{
std::vector<int> row;
for (int c = 0; c < 9; c++)
{
row.push_back((int)puzzleString[r * 9 + c] - '0'); //converts char to int and puts it in the row
}
newPuzzle.push_back(row);
}
puzzle = newPuzzle;
}
std::string solve_sudoku(std::string puzzleString)
{
set_puzzle(puzzleString);
backtrack();
return toString();
}// TODO: Replace examples and use TDD by writing your own tests
Describe(Solve_Sudoku)
{
It(Medium_Sudokus)
{
Assert::That(solve_sudoku("300000000050703008000028070700000043000000000003904105400300800100040000968000200"), Equals("387419526259763418641528379716285943594631782823974165472396851135842697968157234"));
Assert::That(solve_sudoku("130400000705300000600020000000000027000900400000000085860500003059103000002004060"), Equals("138479652725316894694825731541638927283957416976241385867592143459163278312784569"));
Assert::That(solve_sudoku("090035406001000000007000089070940050100200000006800700008004030000600040605000000"), Equals("892735416561489372437162589273946158184257963956813724728594631319678245645321897"));
}
};For some unknown reason (there is a reason, but "for some unknown reason" sounds more fun) there is no product function in python
Let's add it!
note: The product of an empty list is 0.
def prod(numbers):
if numbers == []: return 0
product = 1
for number in numbers:
product *= number
return productimport codewars_test as test
# TODO Write tests
import solution # or from solution import example
# test.assert_equals(actual, expected, [optional] message)
@test.describe("Simple tests")
def test_group():
@test.it("Short lists")
def test_case():
test.assert_equals(prod([1,1]), 1)
test.assert_equals(prod([]), 0)
test.assert_equals(prod(range(1,10)), 362880)2048 is a single-player sliding block puzzle game designed by Italian web developer Gabriele Cirulli. The objective of the game is to slide numbered tiles on a grid to combine them to create a tile with the number 2048; however, one can continue to play the game after reaching the goal, creating tiles with larger numbers.
The question is how high you can go.
Every turn, a new tile will randomly appear in an empty spot on the board with a value of either 2 or 4. If two tiles of the same number collide, they will merge into a tile with the total value of the two tiles that collided.
For a given board size, return the highest numbers, and sum of all numbers.
For example, for a normal 4x4 board and you are really lucky, the best possible board is:
131072 65536 32768 16384
1024 2048 4096 8192
512 256 128 64
4 8 16 32
The best possible block is 131072, the sum of all blocks is 262140
def calculate_2048(size):
sq = 4
for _ in range(0,size*size-1): #calculating the highest square by simply multiplying it by 2
sq *= 2
highest = sq
sumtotal = sq
for _ in range(0,size*size-1): #calculating the highest score by adding up every number back down to 4
sq = int(sq/2)
sumtotal = int(sumtotal+sq)
return highest, int(sumtotal)import codewars_test as test
# TODO Write tests
import solution # or from solution import example
import random
# test.assert_equals(actual, expected, [optional] message)
@test.describe("2048")
def test_group():
@test.it("lower numbers")
def test_case():
test.assert_equals(calculate_2048(4), (131072,262140))
test.assert_equals(calculate_2048(1), (4,4))
test.assert_equals(calculate_2048(5), (67108864,134217724))
@test.it("random cases")
def random_tests():
sizes = [random.randint(1,20) for _ in range(10)]
for s in sizes:
test.assert_equals(calculate_2048(s), (2**(s*s+1),2**(s*s+2)-4)) #don't tell the actual solver it's this easyYour input is a list containing digits, strings, and iterables (lists, sets, tuples) containing those.
Unpack the list into a string with all values seperated by spaces
def isIterable(l): try: l[0] return True except: return False def unpackIterable(l): output = [] for item in l: if isIterable(item) and not isinstance(item, str): output += unpackIterable(item) else: output.append(item) return output def unpackList(l): outputList = [] for item in l: if isIterable(item) and not isinstance(item, str): outputList += unpackIterable(item) else: outputList.append(item) return " ".join(map(str, outputList))l = [1,2,3,4,[1,2,3],(1,2),'a']- def isIterable(l):
- try:
- l[0]
- return True
- except:
- return False
- def unpackIterable(l):
- output = []
- for item in l:
- if isIterable(item) and not isinstance(item, str):
- output += unpackIterable(item)
- else:
- output.append(item)
- return output
- def unpackList(l):
- outputList = []
- for item in l:
- if isIterable(item) and not isinstance(item, str):
- outputList += unpackIterable(item)
- else:
- outputList.append(item)
- return " ".join(map(str, outputList))
print(*l)
import codewars_test as test test.assert_equals(unpackList([1,2,3,4,[1,2,3],(1,2),'a']),'1 2 3 4 1 2 3 1 2 a') test.assert_equals(unpackList([1,2,3,4,[1,[2,3]],(1,2),'a']),'1 2 3 4 1 2 3 1 2 a') test.assert_equals(unpackList(['These',[['are','all'],'strings']]),'These are all strings')- import codewars_test as test
- test.assert_equals(unpackList([1,2,3,4,[1,2,3],(1,2),'a']),'1 2 3 4 1 2 3 1 2 a')
- test.assert_equals(unpackList([1,2,3,4,[1,[2,3]],(1,2),'a']),'1 2 3 4 1 2 3 1 2 a')
- test.assert_equals(unpackList(['These',[['are','all'],'strings']]),'These are all strings')