Space is new Manifest Destiny

Manifest Destiny may be politically wrong term, as there are perceived winners and perceived losers (especially without any of their fault other than being at wrong place with wrong crowd) ;

But make no mistake, Space is new manifest destiny.

Initially we thought earth is extremely special we have everything for life. But the more we venture out the more we realize it is not so special,

We thought earth is with abundant water, ==> Wherever we poke on space, we are finding water! (Moon, Mars, exoplanets, asteroids etc..)

We thought milky way is our galaxy and the galaxy with one or more possible in the universe. But you adjust Hubble telescope lenses and you view ten’s or hundred’s of galaxies. They are everywhere.

There are billions of stars, three times more planets, three times more moons, ten times more asteroids. Probability of colonizing few of them is very high, provided humanity plays its cards well.

Current Capitalism, Current religion are not enough to drive humanity onto space. We need better tools.

Changes we will see to our shopping habits in five years

Self driving smart shopping carts

Shopping carts becomes more smart. Many intriguing features comes to them. Some of them –

  1. self driving ; you summon a cart and a cart comes to you.
  2. After unloading, you say bye-bye and cart automatically goes away.
  3. You can ride on the cart mostly by standing on the back of it.
  4. You just put stuff in the cart, it will show total bill, alternative items, adds more suggestions similar to the stuff, shows reviews, asks to add review. Whole inside-outside of shopping cart will be one big screen.
  5. No need to wait in line and pay, you can pay to your shopping cart.
  6. No need to unload stuff manually to your car, shopping cart and adjust height as per your car trunk height, and it can roll stuff onto trunk without you heavy lifting.
  7. Shopping carts will be charged automatically when needed.
  8. It even remembers your previous shopping history and shows you an auto generated personalized shopping list.
  9. Once you sign up on a list, it even gives you a map to navigate store for optimizing your time and to ensure delicate items are kept on top (infamous example: onions goes below, tomatoes goes on top 🙂 )

No need to bring along shopping cart (option 2)

You take your mobile phone and scan items you need and enter quantity. Pay and wait in your car. With in five minutes a shopping cart will come to your car with all the stuff you selected.

Mini autonomous stores in every community complex

In your apartment complex or gated community – a mini sans-human, complete autonomous store will be present. You can walk, pick and come out. If you need anything else, place order and you will get it by evening. You can even order from your bed and just walk in to collect your complete packed goods.

Autonomous food-trucks

Self driving, sans-human food trucks will be norm. You can vend your favorite lunch or dinner from them. Either it is burger or biryani or pasta all are prepared freshly in the morning and packed for you, heated and served.

Autonomous honey-pots 🙂

Name says all! Hopefully they will be better than current versions.

Autonomous mobile stores for countries like India

For countries like India, a mobile store will travel to rural areas with single human presence. (mostly for security reasons) ; People will vend stuff. Even mobile book stores go to school. Mobile book libraries from charity orgs will be norm.

The line between online – offline shopping will be blurred.

You don’t feel like specially online shopping or offline shopping. Offline will technically present as if you are shopping on your screen. Online will present as if you are shopping in a physical store. In the end both will be merged. Everybody comes to a new balance of what to buy online vs offline. What to buy in which stores.

A better photo editor – its almost time!

We have so many photo editors, painting programs – but they all suffer from one big drawback. “None of them are good for common human”

It is almost time to completely change the direction of these photo editors, painting programs. We can improve their usability greatly by incorporating voice commands.

Anybody remember Star Trek Voyager Fair Haven episode and how Captain programs his holo-crush! Editing a photo or painting should be as easy as this.

A probable photo editing episode

Computer open my photo Gallery

<here you go…>

Select Third photo on second row.

<Here is your photo selected>

Let us edit this a bit

<OK>

Auto adjust

<I am applying auto improvements. How does this look?>

hmm.. Better. Save and Continue

<What else do you want to do?>

Crop by 75%

<Does this looks OK?>

No. that’s a lot, add 5% back.

<How about this?>

OK.

(You get the picture>

A Probable painting session

Computer ! Let us do some painting …

<OK, here is canvas>

Change background color to gray

<Done>

Paint two pairs of eyes.

<OK>

Make them green

<OK>

Insert two small clouds in those eyes

<OK>

Reduce the size of clouds by 75%

<OK>

Let the clouds rain

<OK>

Let the rain appear like tears dropping from eyes

<OK>

Save and Continue …

(You get the picture!)

Conclusion

The technology is already there. We just need to piece it together and productize it.

Solving Sudoku like humans do

.. is not difficult, but intriguing.

Usually solved with blind back tracking. But it felt soul-less. I want to solve like humans do.

Step 1: Solve each cell which can be guessed with 100% probability.

Step 2: Pick one of the available options and move to next.

Step 3: If nothing matches, back-track and change one of previous cells done in step 2. If reached start still nothing – no solution found.

The whole program is at https://github.com/chavakiranasdev/kichavaLibrary/blob/master/leet/hard/sudoku/Sudoku/Solution.cs

It is written and tested on Leetcode, so we ended up converting input to our object and reconverted back to required format.

CellState

/// <summary>
/// Represents state of single Cell. 
/// </summary>
internal enum CellState
{
    Empty, // Not yet filled. 

    InitialValue, // This value is already given 

    SolvedWithConfidence, // We found it with 100% probability. 

    InProgress, // Currently in progress. 
}

CellLocation

/// <summary>
/// Represents a single cell location. 
/// Used during backtracking to remember path
/// </summary>
internal class CellLocation
{
    public int Row { set; get; }
    public int Column { set; get; }
}

Cell

/// <summary>
/// Represents a cell 
/// </summary>
internal class Cell
{
    public CellState State { get; set; }
    public int CurrentValue { get; set; }

    // We tried this number & it is not fit here.
    // Used during backtracking to not re-use discarded values.
    public List<int> NotFitForThisCell { get; set; }

    public Cell()
    {
        State = CellState.Empty;
        NotFitForThisCell = new List<int>();
    }

    public void Reset()
    {
        CurrentValue = 0;
        State = CellState.Empty;
    }

    public void ClearNotFitForThis()
    {
        NotFitForThisCell.Clear();
    }
}

Find a match with 100% probability

// This checks if there is only one fit for this cell. 
// If it finds more than one fit, then we return zero.
private int GetBestFit(int row, int column)
{
    var gridKey = GetGridNumber(row, column);
    var availableInAllThree = rowAvailableList[row].Intersect(columnAvailableList[column]).Intersect(gridAvailableList[gridKey]);
    if (availableInAllThree.Count() == 1)
    {
        return availableInAllThree.First();
    }
    return 0;
}

Datastructures

// Constants 
// we can generally solve sudoku of any size. 
// So far, tested only for size 9
private int SizeOfSudoku { get; set; }

// Private variables. 
// Later, we create a board of given size (e.g.. 9X9)
private Cell[,] cellBoard;

// Next three dictionaries (hash's) represent each row, column, grid and still available values at any instance. 
// For example, once we initialize with input values, we remove them from corresponding row, column, grid. 
// Instead of three hashe's we could use 9X9 hashes to do same for each cell. That should be good for perf, for now this what I used.
Dictionary<int, List<int>> rowAvailableList = new Dictionary<int, List<int>>();
Dictionary<int, List<int>> columnAvailableList = new Dictionary<int, List<int>>();
Dictionary<int, List<int>> gridAvailableList = new Dictionary<int, List<int>>();

Constructor

public Solution(int sizeOfSudoku = 9)
{
    SizeOfSudoku = sizeOfSudoku;
    cellBoard = new Cell[SizeOfSudoku, SizeOfSudoku];
}

Solution

public void SolveSudoku(char[][] board)
{
    Console.WriteLine("Start...");
    InitializeAllAvailableLiistsWithEverything();
    // Initialize given char array into our cell array. 
    InitializeCellArray(board);

    // First round - find all those which doesn't need guessing.
    bool isAtleastOneBestFitFound;
    int currentRow;
    int currentColumn;
    do
    {
        isAtleastOneBestFitFound = false;
        // Solve each row. 
        currentRow = 0;
        while (currentRow < SizeOfSudoku)
        {
            currentColumn = 0;
            while (currentColumn < SizeOfSudoku)
            {
                if (cellBoard[currentRow, currentColumn].CurrentValue == 0)
                {
                    var bestFit = GetBestFit(currentRow, currentColumn);
                    if (bestFit != 0)
                    {
                        // We have a match. Update the cell with this value.
                        isAtleastOneBestFitFound = true;
                        UpdateCellValue(currentRow, currentColumn, bestFit, CellState.SolvedWithConfidence);
                    }
                }
                currentColumn++;
            }
            currentRow++;
        }
    } while (isAtleastOneBestFitFound);

    // Second round - Try to do best guess
    bool response = true;
    response = SolveByRow();
    if (response == false)
    {
        Console.WriteLine("Bug: Unable to solve given Sudoku");
    }

    // we should be done now. 
    // Just put final result into char array instead of cell object array
    for (int i = 0; i < SizeOfSudoku; i++)
    {
        for (int j = 0; j < SizeOfSudoku; j++)
        {
            board[i][j] = Convert.ToChar(cellBoard[i, j].CurrentValue + 48);
        }
    }
}

SovleByRow

 private bool SolveByRow()
    {
        bool response = true;
        if (!SolveGivenSubBlock(rowStart: 0, rowEnd: SizeOfSudoku - 1, columnStart: 0, columnEnd: SizeOfSudoku - 1))
        {
            response = false;
            Console.WriteLine("Bug? Unable to solve some of the grid");
        }
        return response;
    }

SolveGivenSubBlock

 private bool SolveGivenSubBlock(int rowStart, int rowEnd, int columnStart, int columnEnd)
    {
        bool response = true;
        for (int currentRow = rowStart; currentRow <= rowEnd; currentRow++)
        {
            for (int currentColumn = columnStart; currentColumn <= columnEnd; currentColumn++)
            {
                if (!SolveGivenCell(currentRow, currentColumn))
                {
                    response = false; // do not overwrite this value for next cell's success, and thus above if
                }
            }
        }
        return response;
    }

SolveGivenCell

  private bool SolveGivenCell(int currentRow, int currentColumn)
    {
        bool response = true;
        var currentCell = cellBoard[currentRow, currentColumn];
        if (currentCell.CurrentValue == 0)
        {
            // go back tracking. 
            // This will first attempt to find best guess if not found then back tracks.
            if (!BackTrackRealThisTime(currentRow, currentColumn))
            {
                response = false;
                Console.WriteLine($"Bug? Unable to solve {currentRow} :: {currentColumn}");
            }
        }
        return response;
    }

Backtracking

 private bool BackTrackRealThisTime(int currentRow, int currentColumn)
    {
        var stack = new Stack<CellLocation>();
        // clear not fit for this, if any from prevous attempts.
        cellBoard[currentRow, currentColumn].ClearNotFitForThis();
        stack.Push(new CellLocation() { Row = currentRow, Column = currentColumn });

        while (stack.Count != 0)
        {
            var currentTopOfStack = stack.Peek();
            var bestGuess = GetBestGuess(currentTopOfStack.Row, currentTopOfStack.Column);
            if (bestGuess != 0)
            {
                // We have a guess. Update the cell with this value.
                UpdateCellValue(currentTopOfStack.Row, currentTopOfStack.Column, bestGuess, CellState.InProgress);
                stack.Pop(); // Remove this from stack.
                continue;
            }
            var previousCellLocation = GetPreviousInProgressCellLocation(currentTopOfStack);
            // Push this cell onto stack after emptying it.;
            var previousCell = cellBoard[previousCellLocation.Row, previousCellLocation.Column];
            previousCell.NotFitForThisCell.Add(previousCell.CurrentValue);
            RemoveCellValue(previousCellLocation.Row, previousCellLocation.Column);
            // Now that we are moving further back, current cell's notfit is no longer valid.
            cellBoard[currentTopOfStack.Row, currentTopOfStack.Column].ClearNotFitForThis();
            stack.Push(previousCellLocation);
        }
        return true; // stack is empty
    }

Conclusion

I tried to be lazy and backtrack in random, without remembering path – but on my machine it works, leetcode always timed out. Forcing me to be a better 🙂

Get rest of the code from above github link.

Notes while becoming a Gopher (aka learning Go language)

  1. Functions returning multiple values is taken to next level.  
  2. Golang’s documentation to get started is very well designed and implemented. Other languages can learn a bit from here to not make their complex-language learning extra-complex.  
  3. I thought I have seen last of pointers for major use cases, alas, I am mistaken.  
  4. “for” is new ‘while’.  
  5. Switch is all powerful.  (Good. I still remember how I suffered with switch in Java6 days)
  6. Methods are c# extension methods. (Or the otherway)  
  7. Go is C.Redefined. (Or C.Redesigned or C.Improved)  
  8. Go is not OOPS but Go is OOPS (Or Go is only a bit of OOPS and lot of Procedural)  
  9. Copy is actually CopyTo as destination is first argument and source is second argument.  
  10. Defer will do finally’s job, in more human way. Defer + Recover is catch; panic is throw exception. But the documentation says they don’t have try catch – I am a bit confused. It feels panic-defer-recover are more human friendly design of try-catch-finally.
  11. I may miss c#’s $_ string interpolation. 
  12. Loved separate name for rune. Makes conversing in Unicode characters more straightforward.