How to solve problems with backtracking

Problem:

//soon

Code:

problem = [ ["A" ,"B" ,"C" ,"D" ,"E" ,"F" ],
            [None,None,None,None,None,None],
            [None,None,False,False,None,None],
            [None,None,False,False,None,None],
            [None,None,None,None,None,None],
            [None,None,None,None,None,None] ]

def isRow(p,r,v) : # Checks, if the value v is in p at row r
    for i in p[r] : 
        if i == v : return True 
    return False

def isColumn(p,c,v) : # Checks, if the value v is in p at column c
    for i in range(6) : 
        if p[i][c] == v : return True
    return False
    
def isDiagonal(p,r,c,v) :  # Checks, if the value v is in p in the diagonals from position r and c
    pos = [r-1,c-1]	# Check the top left values
    while pos[0] >= 0 and pos[1] >= 0 :
        if p[pos[0]][pos[1]] == v : return True
        pos = [pos[0]-1,pos[1]-1]
        
    pos = [r-1,c+1]	# Check the top right values
    while pos[0] >= 0 and pos[1] <= 5 :
        if p[pos[0]][pos[1]] == v : return True
        pos = [pos[0]-1,pos[1]+1]
    
    pos = [r+1,c+1] # Check the bottom right values
    while pos[0] <= 5 and pos[1] <= 5 :
        if p[pos[0]][pos[1]] == v : return True
        pos = [pos[0]+1,pos[1]+1]
        
    pos = [r+1,c-1] # Check the right left values
    while pos[0] <= 5 and pos[1] >= 0 :
        if p[pos[0]][pos[1]] == v : return True
        pos = [pos[0]+1,pos[1]-1]
 
    return False

def res(p,r=0,c=0) :
    values = ["A","B","C","D","E","F"]
    if r == 5 and c == 5 : # If last Value
        if p[r][c] == None : # And it is empty
            for v in values : # Check for every value
                if not (isRow(p,r,v) + isColumn(p,c,v) + isDiagonal(p,r,c,v)) : # Checks, if v can be placed at (r,c)
                    p[r][c] = v # Insert value
                    
                    for j in p : # Does the printing and formatting
                        str = "   "
                        for k in j : 
                            if k == False : str += "  "
                            else : str += k + " "
                        print(str)
                    print()
                    
                p[r][c] = None # Resets the position for cleaning
    elif p[r][c] == None : 
        for v in values :
            if not (isRow(p,r,v) + isColumn(p,c,v) + isDiagonal(p,r,c,v)) :
                p[r][c] = v
                if c == 5 : res(p,r+1,0) # If last value in row jump one down
                else : res(p,r,c+1) # else next value
            p[r][c] = None
    else : 
        if c == 5 : res(p,r+1,0)
        else : res(p,r,c+1)

res(problem)

Result:

   A B C D E F 
   C F E B A D 
   E A     F B 
   B D     C E 
   F C B E D A 
   D E A F B C 

   A B C D E F 
   C F E B A D 
   E A     F B 
   B D     C E 
   F C B E D A 
   D E F A B C 

   A B C D E F 
   D E A F B C 
   B C     D A 
   F D     C E 
   C A E B F D 
   E F D C A B 

   A B C D E F 
   D E A F B C 
   B C     D E 
   F D     C A 
   C A E B F D 
   E F D C A B 

   A B C D E F 
   D E A F B C 
   F C     D A 
   B D     C E 
   C A B E F D 
   E F D C A B 

   A B C D E F 
   D E A F B C 
   F C     D A 
   B D     C E 
   C A E B F D 
   E F D C A B 

   A B C D E F 
   D E A F B C 
   F C     D E 
   B D     C A 
   C A E B F D 
   E F D C A B 

   A B C D E F 
   D E F A B C 
   F C     D A 
   B D     C E 
   C A B E F D 
   E F D C A B 

   A B C D E F 
   D E F A B C 
   F C     D A 
   B D     C E 
   C A E B F D 
   E F D C A B 

   A B C D E F 
   D E F B A C 
   F C     D B 
   B A     C E 
   C D B E F A 
   E F A C B D 

   A B C D E F 
   D E F B C A 
   F C     D B 
   B D     A E 
   C A B E F D 
   E F D A B C 

   A B C D E F 
   D F E A B C 
   E C     D A 
   B D     F E 
   F A B E C D 
   C E D F A B 

   A B C D E F 
   D F E B A C 
   E A     D B 
   B C     F E 
   F D B E C A 
   C E A F B D 

   A B C D E F 
   D F E B A C 
   E A     F B 
   B C     D E 
   F D B E C A 
   C E A F B D 

   A B C D E F 
   D F E B A C 
   E A     F B 
   B C     D E 
   F D B E C A 
   C E F A B D 

   A B C D E F 
   D F E B A C 
   E C     D B 
   B A     F E 
   F D B E C A 
   C E A F B D 

   A B C D E F 
   D F E B A C 
   E C     D B 
   B D     F A 
   F E B A C D 
   C A D F B E 

   A B C D E F 
   D F E B A C 
   E C     D B 
   F A     C E 
   C D F E B A 
   B E A C F D 

   A B C D E F 
   D F E B A C 
   E C     D B 
   F D     C A 
   C E F A B D 
   B A D C F E 

   A B C D E F 
   D F E B A C 
   E C     F B 
   B A     D E 
   F D B E C A 
   C E A F B D 

   A B C D E F 
   D F E B C A 
   E C     D B 
   F D     A E 
   C A F E B D 
   B E D A F C 

   A B C D E F 
   F D E A B C 
   E C     D A 
   B F     C E 
   C A B E F D 
   D E F C A B 

   A B C D E F 
   F D E B A C 
   E C     D B 
   B F     C A 
   C E B A F D 
   D A F C B E 

   A B C D E F 
   F D E B C A 
   E C     D B 
   B F     A E 
   C A B E F D 
   D E F A B C 

How to restore deleted WhatsApp Chats

I accidentally reported a business partner in WhatsApp, and that deleted all of the chat messages.

I need them back!

a client of mine

And that’s how this journey started.

only works on android though

What happend?

My client had a conflict with a business partner of her. In her anger she wanted to block her on WhatsApp, so that further conversations have to be formal. But sadly she reported this partner, and if you do that, whatsapp deletes that chat.

What did I tried?

First I tried restoring an old backup with reinstalling WhatsApp and only have that old backup saved. But that didn’t work, WhatsApp just didn’t want to load any backup other than out of google drive.

Thanks to recent changes, on how the google drive backup system works, it isn’t easy/possible to access the backup.

So the only option is to encrypt the local backup. But therefore you need the key. This key is easy accessible – if your phone is rooted. But sadly every other way to access the key without root failed.

How to do it

1. Safe the local backups

Connect the phone to the computer, accept media access and go into the data system.

The backups are stored as /WhatsApp/Databases/msgstore-20XX-XX-XX.1.db.crypt12 or alike, either on the sd card or the internal storage. Better transfer them all to your computer.

The date of the backup is easily readable.

2. Root the phone

To access the key, you need to root your phone. Sadly I can’t help you with that – every phone is different.

But there are a lot of good tutorials out there. Just google for them.

3. Access the key

If the root is successful, go to the play store and download a „root file manager„. Use it to go to the root dictionary of your android. From there just go to /data/data/com.whatsapp/files/key and copy the „key“ file to the sd card or the internal storage.

Transfer the key file to your computer

4. Decrypt the backup

I used whatcrypt.com to decrypt the backup.

I hope pretty much that they are trustable. But I’m not able to check it.
So use it on you own risk.

Upload your key there and store it. Then go to „Decrypt WhatsApp Database“ and upload the database, that was created before the chat was deleted.

Congrats! You have an sql database in an zip-file! Uncompress the zip-file!

5. Get the data

To access the database I used DB Browser ( sqlitebrowser.org ).

Go to „Browse Data“ and open the Table „message_view“.

There are them, every message you’ve sent.

The interesting columns are

  • chat_row_id : Every chat has one id
  • from_me : Who sent the message
  • timestamp: When was it sent in UNIX in ms
  • data: The content of the message

Now you should check the data for chat messages of the lost chat. Now remember the chat_row_id from this message.

Go to execute SQL and run the following code, but change ? for the id you found out.

SELECT from_me, timestamp, data
FROM message_view
WHERE chat_row_id = ?

6. Use the Data

To get to this point I needed 6 hours. So the rest of the trick is pretty dirty – I wanted to finish. The code is terrible, the methods disgusting and the result just okay.
Please don’t judge.

Copy the table into a new excel sheet and safe it as messages.csv.

I wrote this code to convert the .csv to a stylized .html document. The code has a lot of bugs, is pretty bad code and isn’t commented, but it somehow did work.

puts "Start!"

mes = File.read("messages.csv").force_encoding('iso-8859-1')

pos = 0
res = []


while mes[pos+6] != nil do
  me = ( mes[pos] == "1" )
  pos += 2
  time = Time.at(mes[pos,10].to_i)
  pos += 14
  cont = ""
  while (mes[pos-1,2] != "0;") and (mes[pos-1,2] != "1;") do
    cont = cont + mes[pos]
    pos += 1
  end
  pos -= 1
  cont = cont.chop.chop
  if cont[0] == '"' then
    cont = cont[1,cont.size - 5]
  end

  if cont != "" and cont != nil then
    res.push( {:time => time , :me => me, :content => cont} )
  end
end

html = ""

res.each do |i|
  if i[:me] then
    html = '<div class="me"><div class="message">' + i[:content] + '</div><div class="time">' + i[:time].to_s[0,19] + '</div></div>' + html
  else
    html = '<div class="her"><div class="message">' + i[:content] + '</div><div class="time">' + i[:time].to_s[0,19] + '</div></div>' + html
  end
end

pos = 0

while html[pos] != nil do

  if html[pos] == "\n"
    html[pos] = "<br>"
  end
  pos += 1
end

html = '<html><head>
  <style>
  html {
        border-top: solid 20px #005e54;
  }
  body {
    background: #efe7dd url("https://cloud.githubusercontent.com/assets/398893/15136779/4e765036-1639-11e6-9201-67e728e86f39.jpg") repeat;
    padding: 20px;
    padding-top: 5px;
  }

  .me, .her {
    margin: 20px;
    padding: 20px 20px 8px 20px;
    width: 70%;
    max-width: 960px;

    box-shadow: 0px 5px 10px 0px rgba(0,0,0,0.2);
  }

  .me {
    background-color: #e1ffc7;
    position: relative;
    left:20%;

    border-radius: 15px 0px 15px 15px;
  }

  .her {
    background-color: #fefefe;

    border-radius: 0px 15px 15px 15px;
  }

  .message {
    font-family: "Roboto", sans-serif;
    width: 90%;
    max-width: 820px;
    line-height: 1.2em;
  }

  .time {
    font-family: "Roboto", sans-serif;
    color: grey;
    font-size: .7em;
    margin-top: 8px;
    text-align: right;
  }
  </style>
</head><body>' + html + "</body></html>"

output = File.open("messages.html","w")
output << html.force_encoding('iso-8859-1')
output.close

puts "Ende"

You need ruby to run it, but if someone wants, I can make it to an .exe.

This is the pure css for the WhatsApp like looks:

html {
    border-top: solid 20px #005e54;
  }
body {
    background: #efe7dd url("https://cloud.githubusercontent.com/assets/398893/15136779/4e765036-1639-11e6-9201-67e728e86f39.jpg") repeat;
    padding: 20px;
    padding-top: 5px;
  }

.me, .her {
    margin: 20px;
    padding: 20px 20px 8px 20px;
    width: 70%;
    max-width: 960px;

    box-shadow: 0px 5px 10px 0px rgba(0,0,0,0.2);
  }

.me {
    background-color: #e1ffc7;
    position: relative;
    left:20%;

    border-radius: 15px 0px 15px 15px;
  }

.her {
    background-color: #fefefe;

    border-radius: 0px 15px 15px 15px;
  }

.message {
    font-family: "Roboto", sans-serif;
    width: 90%;
    max-width: 820px;
    line-height: 1.2em;
  }

.time {
    font-family: "Roboto", sans-serif;
    color: grey;
    font-size: .7em;
    margin-top: 8px;
    text-align: right;
}

And thats how the .html looks like:

<html><head>
  <style>
  html {
        border-top: solid 20px #005e54;
  }
  body {
    background: #efe7dd url("https://cloud.githubusercontent.com/assets/398893/15136779/4e765036-1639-11e6-9201-67e728e86f39.jpg") repeat;
    padding: 20px;
    padding-top: 5px;
  }

  .me, .her {
    margin: 20px;
    padding: 20px 20px 8px 20px;
    width: 70%;
    max-width: 960px;

    box-shadow: 0px 5px 10px 0px rgba(0,0,0,0.2);
  }

  .me {
    background-color: #e1ffc7;
    position: relative;
    left:20%;


    border-radius: 15px 0px 15px 15px;
  }

  .her {
    background-color: #fefefe;

    border-radius: 0px 15px 15px 15px;
  }

  .message {
    font-family: "Roboto", sans-serif;
    width: 90%;
    max-width: 820px;
    line-height: 1.2em;
  }

  .time {
    font-family: "Roboto", sans-serif;
    color: grey;
    font-size: .7em;
    margin-top: 8px;
    text-align: right;
  }

  </style>
</head>
<body>
    <div class="her"><div class="message">Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam nonumy eirmod tempor invidunt ut labore et dolore magna <br> aliquyam erat, sed diam voluptua. At vero eos et accusam et justo duo dolores et ea rebum. Stet clita kasd gubergren, no sea takim</div><div class="time">2020-03-14 08:08:07</div></div>
    <div class="her"><div class="message">Lorem ipsum dolor</div><div class="time">2020-03-08 46:04:42</div></div>
    <div class="me"><div class="message">Lorem ipsum dolor sit amet, consetetur sadipscing elitr</div><div class="time">2020-03-06 19:46:58</div></div>
    <div class="her"><div class="message">Lorem ipsum dolor sit amet, sadipscing elitr</div><div class="time">2020-03-06 18:42:16</div></div>
    <div class="me"><div class="message">Lorem ipsum dolor sit amet, consetetur sadipscing elitr</div><div class="time">2020-03-06 18:49:48</div></div>
    <div class="her"><div class="message">Lorem ipsum dolor sit amet, consetetur sadipscing elitr</div><div class="time">2020-03-06 18:45:57</div></div></body>
</html>

I hope I could help!

Pick out mail adresses out of text documents

„I need to write a lot of customers a mail that their trips will be canceled. I only have the adresses saved in a word document, with many additional information. It would take a few hours to copy them hand by hand. Do you have a better idea?“

a client of mine

I had a pretty similar situation a few years back with another client. Back then I searched online for a tool, but couldn’t found one. So I said down and programmed it myself. After the one time use I just forgot about it and over the time I lost it somewhere in my files.

So when I got this request by my client, I first tried to find the file, but gave up short after. So back to programming again.

And due to the lack of a easy tool online I decided to publish the tool myself.

This is just the first, unpolished version. I’ll try to optimize it in the next days, add more features and make it a better user experience.

What does it do?

It asks the user to input the filename of a file on the same level the program is in. It loads it into a string, makes all the characters downcase and removes every line break. Then it searches the file with an RegEx, checks, if the address is already known, and then outputs the mail adresses in the terminal and creates the file/adds them to the file extractedmails.txt in a format, that allows you to just copy paste them into the sending form.

What to change?

I want to optimize the extraction progress, add an options menu for changing the output style, adding a filter and choose the output file. Also I want to add multiple language support.

The Program

The Code

# Mail RegEx
mail = /[a-zA-Z0-9._-]+@[a-zA-Z0-9](?:[a-zA-Z0-9-]{0,61}[a-zA-Z0-9])?(?:\.[a-zA-Z0-9](?:[a-zA-Z0-9-]{0,61}[a-zA-Z0-9])?)*/

# Imports the file as a string and formats it 
print("Bitte gib den Dateinamen der Datei an, die ich nach eMails durchsuchen soll: ")
filename = gets.chop
str = File.read(filename)
str = str.downcase
while str.slice!("\n ") != nil
end

# Uses the RegEx to store any mail in an array
m = mail.match(str)
puts("Alle Mails in der Datei:")
a = []

while m!=nil do
  if not a.include?(m[0]) then
    a.push(m[0])
  end
  str = m.post_match
  m = str.match(mail)
end

# Formats the array into a usable string
res = ""
a.each do |i|
  res = i + ", " + res
end
puts res = res.chop.chop

# Creates an output file
output = File.open( "extractedmails.txt","w" )
output << res
output.close
print "Finished"
gets

How to approximate pi out of random numbers

I know, I waste far to much of my time on youtube watching random videos. But out of luck I sometimes find inspiring stuff. Like this video by standupmaths:

And so I got on the journey to waist even more of my time.

How does it work?

The system of the approximation works pretty simple:

The probability, that two random numbers are coprime (Greatest common divisor is 1) to each other, is

x = \frac{6}{\pi^2}

The proof.

And it’s pretty easy to see, that

\pi = \sqrt{\frac {6}{x}}

So we need to take two steps:

  1. Check if two random numbers are coprime
  2. Generate many large numbers and check them

The possibility x is based on random numbers between 1 and inf. If we limit the maximum random number we decrease the value of pi. So we need to maximize the max random number, what increases the calculation time. So we need a fast coprime algorithm.

The code

My first try is based on the euclidean algorithm.

def coprime?(x,y)  # Finds out if two numbers are coprime (Euclidean algorithm)
  if y == 0 then
    return x == 1
  else
    return coprime?(y, x % y)
  end
end

def pi(time,height)  # Approximate Pi out of random numbers
  truestate = 0.0
  time.times do
      if coprime?(rand(1..height),rand(1..height)) then truestate += 1 end
  end
  return Math.sqrt(6 /(truestate / time))
end

t = Time.new
p pi(100000000,1000000)
p Time.new - t
Real Value:         3. 141592653589793
Calculated Value:   3. 141484581244406
def. Deviation:    -0. 00010807234538701138
rel.  Deviation:    0. 0034400495959707733%
Runtime:           65. 7191823 Seconds

On my PC the calculation time of this is around 66 seconds.
The value for pi changes in each runthrough, but its still pretty accurate.

The optimized version

Thanks to reddit I found a few changes, that improve the runtime by cutting in half:

def pi(time,height)  # Calculates Pi out of random numbers
  truestate = 0
  range = 1..height
  i = 0
  while i < time
    truestate += 1 if rand(range).gcd(rand(range)) == 1
    i += 1
  end
  Math.sqrt(6 / (truestate.to_f / time))
end

t = Time.new
p pi(100000000,1000000)
p Time.new - t
Real Value:         3. 141592653589793
Calculated Value:   3. 141516024003613
def. Deviation:    -7. 662958618004367e-05
rel.  Deviation:    0. 002439195485526291%
Runtime:           28. 2471332 Seconds

Lets look at the changes:

  • With using a while loop instead of a for loop we reduce the runtime by a bit
  • Using the truestate iterator as an integer we reduce the internal effort
  • With introducing a range variable we reduce the runtime by a lot
  • With the internal gcd() function we reduce the runtime by a lot, even more than any of the above together

The programs

I present you both algorithms in three ways:

  1. The basic code [ pi_calc_X.X.rb ]
  2. Does the calculation 400 times and returns the most accurate one [ pi_calc_gen_X.X.rb ]
  3. Gives out a remaining time estimate and calculates performance [ pi_long_X.X.rb ]