C# Design algorithm using DFS similar to Sudoku solver
It is a medium level algorithm which can be solved using depth first search. The challenge part is to work on bit manipulation, how to change one bit from index = 0 to index = 15?
Case study:
I need to warmup bit manipulation to learn to solve two problems in the following:
I need to warmup bit manipulation to learn to solve two problems in the following:
- Change one bit - how to change it?
Use bit operator XOR. As we know, 0 ^ 0 = 0, 0 ^1 = 1, 1 ^ 1 = 0; and there are 16 bits to alter, and we can use left shift operator to generate an integer to set nth bit to 1 whereas n is from 0 to 15. In other words, I have to come out the express 1 << i.
So, the answer is last ^ (1 << i), whereas is from 0 to 15. - How to prove two numbers are the same except one bit?
Assume that m and n only have one bit different, so m ^ n = 2^p, p is from p to 15. And p & (p - 1) = 0 <=> all bits from 0 to p should be 0.
Here are highlights:
- Understand how to run DFS to search all possible paths until one path is found.
- Work on DFS search - base case, backtracking, mark visited using HashSet to avoid deadloop;
- Time complexity and space analysis is similar to my favorite algorithm Sudoku solver.
Actionable Items
I could not solve the algorithm in weekly contest 160 on Oct. 26, 2019. I spent over 20 minutes to analyze, but I could not come out using DFS algorithm to work on all bits from 0 to 15.
I have to practice more often in weekdays, solve more medium algorithms.
I could not solve the algorithm in weekly contest 160 on Oct. 26, 2019. I spent over 20 minutes to analyze, but I could not come out using DFS algorithm to work on all bits from 0 to 15.
I have to practice more often in weekdays, solve more medium algorithms.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace _1238_circular_permutation
{
class Program
{
static void Main(string[] args)
{
}
/// <summary>
/// 1238 Circular Permutation in Binary Representation
/// The idea is similar to Sudoku solver; Each step using DFS to search all options.
/// </summary>
/// <param name="n"></param>
/// <param name="start"></param>
/// <returns></returns>
public IList<int> CircularPermutation(int n, int start)
{
var result = new List<int>();
var set = new HashSet<int>();
result.Add(start);
set.Add(start);
runDFS(n, set, result, start);
return result;
}
/// <summary>
/// similar to Sudoku solver
/// backtracking
/// DFS path - mark visited
/// </summary>
/// <param name="n"></param>
/// <param name="hashSet"></param>
/// <param name="result"></param>
/// <param name="start"></param>
/// <returns></returns>
private static bool runDFS(int n, HashSet<int> hashSet, IList<int> result, int start)
{
if (hashSet.Count == (int)Math.Pow(2, n))
{
int x = result[result.Count - 1] ^ start; // XOR operator - first and last are different
return (x & (x - 1)) == 0;
}
var length = result.Count;
int last = result[length - 1];
for (int i = 0; i < 16; i++)
{
int next = last ^ (1 << i); // XOR operator - change ith bit
if (next <= (Math.Pow(2, n) - 1) && !hashSet.Contains(next))
{
hashSet.Add(next);
result.Add(next);
if(runDFS(n, hashSet, result, start))
{
return true;
}
hashSet.Remove(next);
result.RemoveAt(result.Count - 1);
}
}
return false;
}
}
}
