Ruby, Sudoku challenge and How to tackle problems

Ruby

I‘ve used Ruby some 12 years ago, and today I’m still loving it. The main reason for me is that I feel it makes the life of a programmer easy. Not convinced? Let me show you some examples in a while.

Recently, I’m playing around with some programming challenges (hobby) mainly from a site call Code Signals. One of few challenges, which I tried recently, could be solved easily within few lines codes in Ruby.

Challenge 1. First Not Repeating Character

According to the site, this is one of the interview questions that is asked by Amazon.

The challenge is fairly simple. Give a string s, you will need to find the first instance of repeating character. Conditions of solving this challenge are that you can only iterate once and/or uses O(1) additional memory.
If no unique character found, return “_”.

Examples

For s = “abacabad”, the output should be

firstNotRepeatingCharacter(s) = 'c'

For s = “abacabaabacaba”, the output should be

firstNotRepeatingCharacter(s) = '_'

My Solution

def firstNotRepeatingCharacter(s)
# O(1) memory access
hashmap = {}

# Interate each character in string
s.chars.each do |c|
# if not found in hashmap, register true,
# otherwise register false
unless hashmap.has_key? c
hashmap[c] = true
else
hashmap[c] = false
end
end
  # returns non duplicates if value is true
find = hashmap.select{ |k,v | v == true}

# if found, return the key of the first item in hashmap
unless find.empty?
return find.keys.first
end

# Otherwise, return '_'
'_'
end

My solution is not as brilliant as compared to many people out there. But yet, it’s a systematic approach to solving the problem. Select inbuilt in Ruby core is helpful, for me not writing code to pick the non-duplicates.

Other Solution by a user, brandon_t17

def firstNotRepeatingCharacter(s)
s.chars.uniq.each{|c| return c if s.chars.count(c) == 1}
return "_"
end

This is the neatest solution I ever come across. It does not require to use additional memory access (^excluding the possibility that the method of uniq will have additional memory access).

Challenge 2. Rotating image

This challenge has been asked by Amazon, Microsoft and Apple.

Give a grid of numbers

a = [[1, 2, 3],
[4, 5, 6],
[7, 8, 9]]

Output after rotated (clockwise)

rotateImage(a) =
[[7, 4, 1],
[8, 5, 2],
[9, 6, 3]]

My Solution

After reading the requirements, thousands of thoughts came across my mind. One of the thoughts I had in mind is that if I were in an interview that given this problem, I might fail the interview.

After some thought, it wasn’t too difficult to implement a solution, especially in Ruby.

To rotate, the algorithm is fairly simple

new_array []
for each column in array:
new_row = []
from last row to 1st:
new_row.append(item)
new_array.append(new_row)

In Ruby, an n by n matrix shall have the ability to use an in-built method call transpose. Transpose, instead of reading the bottom to top, per column, it reads top to bottom. Thus the first column will return [1,4,7] before a transformation. In order to solve that, we just need to reverse each new row after the transpose operation. And that yields the following code in Ruby.

def rotateImage(a)
a.transpose.map(&:reverse)
end

Isn’t this neat? So far single line of code for both challenges.

So far in Ruby

So far I’ve demonstrated the power of Ruby doing so much with little code. “Code less, do more” as I say. Which brings me to the challenge Sudoku I’ve done recently.


Sudoku Challenge

Believed it or not but this challenge is being asked by Apple and Uber. Well, I do know many of the hi-tech companies employs brilliant engineers/coders, probably the bests in the market. But really, to solve Sudoku??? I have been developing and programming for quite some time, 15 years or so, although I’m not a developer by profession, I did programming to solve some work issues and as a hobby, but solving Sudoku is not something I could relate over these years.

Requirements

The requirements of the challenge is to check if that a given Sudoku grid puzzle is valid or not. If the Sudoku grid is valid, return true, otherwise false. The grid does not have to be solvable.

The first few problems I encounter before even attempting to solve this problem are:

  • I have no knowledge of sudoku rules
  • I am not a reader. TL;DR (sorry for this long article)
  • Anxious to solve the problem before all else.

So all these problems are fallen dominoes over the main problem. I did not read the instructions carefully, I missed the point “The grid does not have to be solvable” and start working on the problem. Until I wasted enough time and met those obstacles, I’ve decided to revisit my own issues before working on the problem.

The Path to Solution

First, I read the instructions carefully again.

Second, I studied the rules. The rules are simple. For a position of x,y in the grid, the value must not have duplication in the following:

  • the x-axis of the position
  • the y-axis of the position
  • within the block

So for the below diagram, in the position of x, x shall not have a duplicate in the yellow area.

9x9 Grid of Sudoku

I then began working on the algorithm to solve this problem. To start on I need some form of validators to register and detect duplicate if any

  • First, I need a 9x rows of hashtable to register each value in the grid for each visit,
  • Then, I need 9x column of hashtable to register each value in the grid for each visit
  • Lastly, I need 9x block of hashtable to register each value in the grid for each visit. a block is a 3x3 sub-grid of the 9x9 grid in sudoku.
9 x (3x3 ) sub-grids in Sudoku

My pseudo algorithm then goes about like this:

For each position of x,y in grid:
if position in grid has value:
if row already has value:
return false
else:
register value to row
repeat the same for column and block

After writing the pseudo code, which seems very simple, I continue to put to test of the algorithm to code.

My first issue and what I want to do is by solving this problem by recursion. The skeleton code looks like this:

def solvable(grid, i)
# return true when we exceed metrix boundary
return true if i > (grid.size**2 - 1)

# advancing the position in grid
return solvable(grid, i+1)
end
def sudoku2(grid)
solvable(grid, 0)
end

The first issue is actually I want increment i which is the index/position in the grid but from this index of i, I need to derive the value of x and y, before I can access the value of the grid.

It turns out with some basic math skill we can derive x and y with i. Thus, I use Ruby’s lambda and store the formula as

$pos = -> (n) { y = (n/9); x = n - (y*9); [x,y] }

So when I do a

x,y = $pos.call(i)

it shall return me the x, y position of the current index i, the recursive method is executing.

Finally, I can implement the rest of the pseudocode to the skeleton, in which I thought, but I hit into another problem.

To store/register value in the 3 stores, I mention in the beginning,

  • row
  • column
  • block

For row, its row[y], for the column, its col[x], but how do I know which block to store the value? Again, with simple maths, we can derive which index of the block given the coordinates x and y in the grid.

$find_blk = -> (x, y) { (y/3) * 3 + (x/3) }

Now for the full solution,

# these hash validates row, col and block in sudoko
$row = 9.times.map { Hash.new }
$col = 9.times.map { Hash.new }
$blk = 9.times.map { Hash.new }
# given the value of counter n, returns the position in metrix
$pos = -> (n) { y = (n/9); x = n - (y*9); [x,y] }
# return which block depending on position
$find_blk = -> (x, y) { (y/3) * 3 + (x/3) }
def solvable(grid, i)
# return true when we reach the grid's limit
return true if i > (grid.size**2 - 1)
  # return pos x,y of metrix depending on index, i 
x, y = $pos.call(i)
  # We only interest position of the grid that contains value
if grid[y][x] != '.'
# Check column
if $col[y].has_key? grid[y][x]
return false
else
$col[y][grid[y][x]] = true
end
# Check row
if $row[x].has_key? grid[y][x]
return false
else
$row[x][grid[y][x]] = true
end
# check blk
if $blk[$find_blk.call(x, y)].has_key? grid[y][x]
return false
else
$blk[$find_blk.call(x, y)][grid[y][x]] = true
end
end
  return solvable(grid, i+1)
end

And we’re done for this Challenge!….but not quite for me.

Extending the challenge.

A few years back, the Prime Minister of Singapore publishes his source code of a program he wrote in C, for solving the Sudoku puzzle. This inspires me to try and provide a solver since I already had the sudoku validator already, it is should not be too difficult to implement a solver at the same time. That’s what I thought.

So to cut the long story on this. The issue I encounter is when I try to implement solving the puzzle in the same solvable method. One method of solving a sudoku grid is to implement Backtracking. Since I already had a recursive function that works, implementing would be easy. But that’s not the truth. The problem is, if the puzzle is not solvable and the detection lies in the far end block of the grid(e.g. bottom right block for example) the recursive function would keep recursing and iterating possible values which is too big a number to be computational feasible till dies out of exhaustive attempts.

Hence and therefore, I had to split functions, first check if the given puzzle is already solvable or not, if it is, then solves it. End of story.


Conclusion and Closing

Ruby is a good language and tool to work and learn with. Although there are many languages e.g. Python is gaining popularity over Ruby. I still feel Ruby is neater (not raising a debate here, just my preference, I code in Python too)

As regards to solving a problem, these are some personal remarks.

  • Never get too overwhelmed by the problem. Many times, problems which might seem too difficult at first, but turn out to be simple.
  • The same as above but opposite. What usually you thought to be simple at first might not be till you implement.
  • Keep on trying and experimenting, don’t give up!
  • Practice, practice, and practice….. the samurai way! Practice till perfection
  • Learn by sharing, Learn from others. Sites like Code Signals, provide an excellent platform to learn from others. Sharing your code, offer an opportunity to receive bugs reports and/or feedback.
  • Knowledge is swiss army knife. Apart from coding, math and other general knowledge will prove useful in time to come.

Source Code