Category: Labs

Home / Category: Labs

Cheat Engine Tutorial: Tutorial v3 – Stage 7

December 9, 2015 | Article, Labs | No Comments

We have seen Cheat Engine on previous introduction. As said on that article, Cheat Engine has provide a “cheat me” program to let us practice using Cheat Engine. Officially it is called Cheat Engine Tutorial. In this article we will use Cheat Engine and practice in “cheating” the program. Specifically, we will do the “seventh stage”.

In this article I use:

  1. Windows 8 64-bit
  2. Cheat Engine 6.3
  3. Cheat Engine Tutorial v3

Prerequisite

At least you understand the basic layout of Cheat Engine. You should know how to load a running process to Cheat Engine. If you don’t, please refer back to the introduction.

Open the Cheat Engine Tutorial v3

cheat_0

If you get to this article after beat the sixth stage, make sure you clear the previous result by click on ‘New scan‘ and clear work area.

Some of this article will involve assembly language. Even though it is not a requirement, but knowing some assembly will ease you. You can learn assembly at my Assembly Language Tutorial page or watching Assembly Language Primer Video for Hackers.

Password

Every stage can be accessed individually. To access this stage from Cheat Engine Tutorial’s main window, enter 525927 to password line edit.

Hint

Dark Byte (Cheat Engine creator) wrote this as hint:

This step will explain how to use multi-level pointers.
In step 6 you had a simple level-1 pointer, with the first address found already being the real base
address. This step however is a level-4 pointer. It has a pointer to a pointer to a pointer to a pointer
to a pointer to the health.

You basicly do the same as in step 6. Find out what accesses the value, look at the instruction and what
probably is the base pointer value, and what is the offset, and already fill that in or write it down.
But in this case the address you'll find will also be a pointer. You just have to find out the pointer
to that pointer exactly the same way as you did with the value. Find out what accesses that address you
found, look at the assembler instruction, note the probable instruction and offset, and use that.
and continue till you can't get any further (usually when the base address is a static address, shown up
as green)

Click Change Value to let the tutorial access the health.
If you think you've found the pointer path click Change Register. The pointers and value will then change
and you'll have 3 seconds to freeze the address to 5000

Extra: This problem can also be solved using a auto assembler script, or using the pointer scanner
Extra2: In some situations it is recommended to change ce's codefinder settings to Access violations when
encountering instructions like mov eax,[eax] since debugregisters show it AFTER it was changed, making it
hard to find out the the value of the pointer

Solution 1

OK, in fifth stage we face Level 1 pointer, it means:

Pointer -> data

In this stage we face Level 4 pointer. Let P1, P2, P3, P4 are pointers, we can define level 4 pointer as:

P1 -> P2 -> P3 -> P4 -> data

Like always, get the address of value. I think we have cover it everytime so let’s skip and assume you have found the address, add it to working area. For example, here is my working area. Pay attention to the addresses we found along the way as we will play with address a lot. Of course, my result can be different to yours, so adjust it to yours.

cheat_8_1

Right-click on it and choose “Pointer scan for this address”.

cheat_8_2

Two new window appears. In the first window there are all options we can choose to do pointer scan. It ask what address will pointer scanner scans to. It will search the whole attached process pointed to address specified. Well, just accept and click OK. When it ask you to save the result, just do what it says.

cheat_8_3

Wait for it to load and the second window will list all scanned and filtered pointer. It may take a couple of minutes, depend on your system.

cheat_8_4

Now go to Cheat Engine Tutorial and click “Change Pointer”. Notice, the old address value will go to 0. Now initiate a new search for new value displayed on Cheat Engine Tutorial. Like always, when you find it, add it to working area. Here is what mine looks like.

cheat_8_5

Look at the address of our new found entry (the one with red underline). You can write down, or just copy the address. If you want to copy the address, double-click on the address and you will have a new dialog. Just copy the text (see the red circle below).

cheat_8_6

Now go back to the pointer scanner and click “Pointer Scanner” menu on menubar. Click on “Rescan memory – Removes pointers not pointing to the right address”.

cheat_8_7

You will have another window appear. Now write or paste the address we have copied before. See the red circle below. Next, press OK.

cheat_8_8

Depend on the situation, you may have one or more result. If you found one, you are lucky. On several attempts, I have found more than one result because I do this stage marathon from stage one (I don’t know if this is the cause). If this is the case, just pick one. I pick the first entry.

Double click the entry you choose. It will be added to our working area. Here is what my working area looks like.

cheat_8_9

Now to make sure we have the correct address, go to Cheat Engine Tutorial and click ‘Change pointer’. If our address display the correct / same value, we got what we want. Change the value and freeze it. You can go to next (last) stage by clicking ‘Change pointer’ once more.

Solution 2

This solution will search address manually. Therefore, it will heavily use low level / assembly language representation like we did in fifth stage.

I remind you, I use 64-bit Windows and 64-bit version of both Cheat Engine and Cheat Engine Tutorial. Windows 64-bit and 32-bit differs in ABI (Application Binary Interface), set of protocol which manages what each register, memory layout, stack, etc are used for. The 64-bit OS make use of 64-bit capability processor, addressing at most 2^64 (two power to 64) memory address. The register name also different, for example: EAX is 32-bit register, the 64-bit counterpart is RAX. Therefore, you should adjust the result written here to your environment. It should not be hard, I will explain it from ground up. If you have beat the fifth stage (you should have), you can easily beat seventh stage using this solution.

First, get the address of value. I think we have cover it everytime so let’s skip and assume you have found the address, add it to working area. Pay extra attention to the every address written in working area, I will show you why. Now, my working area is like this:

cheat_8_10

Right click on the entry, and choose “Find out what writes to this address”.

A debugger will be attached. Now go back to Cheat Engine Tutorial and click ‘Change value’. Then go back to our debugger. See the following picture (you can open it in new tab if you can see the image clearly).

cheat_8_11

We find instruction which write to our address. The above code is written in Intel assembly language style (as opposed to AT&T representation). The destination is memory location pointed by RSI + 18 or 18 byte from RSI. So let’s find out what value in RSI, see the red circle. Now copy the value and close the debugger window. If you are in 32-bit windows, I believe it’s on general purpose register EAX, or EBX.

Oh, and remember or write down that the offset is 18. We will refer this as offset1.

Now back to Cheat Engine. Initiate a new scan, the value we want to search is Hexadecimal so tick the Hex. Enter the value we got before, the RSI. Add the result entry to work area, there should be only one result. Here is mine:

cheat_8_12

Now right-click the 2nd entry and choose “Find out what accesses this address”. Go back to Cheat Engine Tutorial, click ‘Change value’. Go back to debugger and see what happens.

cheat_8_13

I got 2 results, so which one. Well, both use the address of [rsi] so the offset is 0. Refer this to offset2. But the first result move the value to RAX. Let’s pick this one. Copy the value of RSI then close the debugger.

Do a new search with hex value the latest content of RSI we get. Add the result to work area.

cheat_8_14

“Find out what accesses this address”, again. You know what next, right? Now the offset (offset3) I got is 18.

Initiate new search, add the result to work area. “Find out what access this address”. Now I got the offset (offset4) 10.

Before we go, let’s recap what we have so far.

cheat_8_15

And also our offsets: 18, 0, 18, 10

Now initiate a new search. This time you will see one result with green colored address.

cheat_8_17

Good! Now add it to our work area, manually. On Cheat Engine, click ‘Add address manually’ button. A new window will appear. Tick the pointer. Click ‘Add Offset’ button until we have FOUR offset text box. Write the offset with the offsets we collect so far (see table above). For the address, write it with the address of the result (in my example: 1002C7740). Here is what I do:

cheat_8_16

If you do this correctly, you will see the value. Click OK.

Click on the latest entry on our work area. Double-click it to change the value. Change the value to 5000 and froze it. On Cheat Engine Tutorial, click ‘Change pointer’. If you do all steps like in this article, you will unlocked the Next button. Congratulation!

Cheat Engine Tutorial: Tutorial v3 – Stage 6

December 9, 2015 | Article, Labs | No Comments

We have seen Cheat Engine on previous introduction. As said on that article, Cheat Engine has provide a “cheat me” program to let us practice using Cheat Engine. Officially it is called Cheat Engine Tutorial. In this article we will use Cheat Engine and practice in “cheating” the program. Specifically, we will do the “sixth stage”.

In this article I use:

  1. Windows 8 64-bit
  2. Cheat Engine 6.3
  3. Cheat Engine Tutorial v3

Prerequisite

At least you understand the basic layout of Cheat Engine. You should know how to load a running process to Cheat Engine. If you don’t, please refer back to the introduction.

Open the Cheat Engine Tutorial v3

cheat_0

If you get to this article after beat the fifth stage, make sure you clear the previous result by click on ‘New scan‘ and clear work area.

Some of this article will involve assembly language. Even though it is not a requirement, but knowing some assembly will ease you. You can learn assembly at my Assembly Language Tutorial page or watching Assembly Language Primer Video for Hackers.

Password

Every stage can be accessed individually. To access this stage from Cheat Engine Tutorial’s main window, enter 013370 to password line edit.

Hint

Dark Byte (Cheat Engine creator) wrote this as hint:

Code injection is a technique where one injects a piece of code into the target process, and then reroute
the execution of code to go through your own written code

In this tutorial you'll have a health value and a button that will decrease your health with 1 each time
you click it. Your task is to use code injection to increase the value of your health with 2 every time
it is clicked

Start with finding the address and then find what writes to it.
then when you've found the code that decreases it browse to that address in the disassembler, and open
the auto assembler window (ctrl+a)
There click on template and then code injection, and give it the address that decreases health (If it
isn't already filled in correctly)
That will generate a basic auto assembler injection framework you can use for your code.

Notice the alloc, that will allocate a block of memory for your code cave, in the past, in the pre
windows 2000 systems, people had to find code caves in the memory(regions of memory unused by the game),
but that's luckily a thing of the past since windows 2000, and will these days cause errors when trying
to be used, due to SP2 of XP and the NX bit of new CPU's

Also notice the line newmem: and originalcode: and the text "Place your code here"
As you guessed it, write your code here that will increase the  health with 2.
a usefull assembler instruction in this case is the "ADD instruction"
here are a few examples:
"ADD [00901234],9" to increase the address at 00901234 with 9
"ADD [ESP+4],9" to increase the address pointed to by ESP+4 with 9
In this case, you'll have to use the same thing between the brackets as the original code has that
decreases your health

Notice:
It is recommended to delete the line that decreases your health from the original code section, else
you'll have to increase your health with 3 (you increase with 3, the original code decreases with 1, so
the end result is increase with 2), which might become confusing. But it's all up to you and your
programming.

Notice 2:
In some games the original code can exist out of multiple instructions, and sometimes, not always, it
might happen that a code at another place jumps into your jump instruction end will then cause unknown
behavior. If that happens, you should usually look near that instruction and see the jumps and fix it,
or perhaps even choose to use a different address to do the code injection from. As long as you're able
to figure out the address to change from inside your injected code.

Solution

Information we got from the hint:

  1. We can change game logic
  2. objective: everytime the button clicked, our HP is increased by 2 instead of decreased

Like always, get the address of value. I think we have cover it everytime so let’s skip and assume you have found the address, add it to working area. Right-click on it and choose “Find out what writes to this address”.

cheat_5_2

Cheat Engine might ask your confirmation to attach a debugger, this is our intention so if it asks you just confirm agree. After pressing the button, you will see a debugger window.

cheat_5_3

Go to Cheat Engine Tutorial and press ‘Hit me’. Go back to Cheat Engine debugger and find whether our list has been populated. Here we have one or more entries. Choose the first one. As seen from this picture, my entry is an instruction FF 8B 88070000 – dec [rbx+00000788] on address 100030142.

cheat_7_1

Press ‘Show disassembler’ button. A new window appears. It will gives us a window full of assembly language program and hexadecimal code. The first table is disassembler, list every operation in assembly language. We are now stop at the top instruction. Following it is a hex dumping, viewing the memory in hexadecimal format.

cheat_7_2

Make sure you highlight the code for decrement (it should be highlighted by default).

Now click Tools and then click Auto assemble. Alternatively you can press Ctrl +A. A new window appear, something like a simple editor.

cheat_7_3

cheat_7_4

Now, click Template and click “Code Injection”. Code Injection is operation allow us alter the program logic by reroute the flow control. Cheat Engine can inject a new jump to the running application when the execution reach certain address. In the destination address, we will then create a chunk of instruction which will be executed when the flow arrive.

cheat_7_5

When a confirmation dialog shown, just press OK. Basically it will ask you where we will jump when the execution reach this address. Any code is find, Cheat Engine will take care the job for creating a code for memory allocation etc. Now we have something like this:

cheat_7_6

Now we have some section here. The first block is allocation and initialization, done by Cheat Engine. Don’t touch this, I highly warn you. The next is a label newmem. This will be the place where we place our code. The next is originalcode, it has function like implied by name. Later is exit, when the execution of this chunk end. And the final block is taken care by Cheat Engine.

Copy the line after label original code.

Now there is two different path we can take but both accomplice the same objective. Let’s see the first path.

We know that in assembly language, opcode dec is used to decrease the operand (register / memory address) by 1. What should we do if we want the resultant is increased by 2 instead of decreased by one? OK, we have opcode add which can use. Now let’s do some math here. X – 1 = 2, what is X? Yes, it’s three. So we should add 3 first before the code is subtracted by 1. Replace line started by // with following code:

add [rbx+00000788], 3

OK, where do I find magic number 00000788? See the dec line, you got what you need.

OK, it’s fun doing some math, but there is an easier way. Now let’s find out the second method.

Delete the line started with dec opcode. Now, instead of adding 3, you can add only 2.

add [rbx+00000788], 2

Any path you choose, it should give the same result.

Now press Execute and then go back to Cheat engine Tutorial. Press ‘Hit me’ and see your HP is raised by 2. You will also see the ‘Next’ button is now enabled. Cheers, you beat this stage!

Cheat Engine Tutorial: Tutorial v3 – Stage 5

December 9, 2015 | Article, Labs | No Comments

We have seen Cheat Engine on previous introduction. As said on that article, Cheat Engine has provide a “cheat me” program to let us practice using Cheat Engine. Officially it is called Cheat Engine Tutorial. In this article we will use Cheat Engine and practice in “cheating” the program. Specifically, we will do the “fifth stage”.

In this article I use:

  1. Windows 8 64-bit
  2. Cheat Engine 6.3
  3. Cheat Engine Tutorial v3

Prerequisite

At least you understand the basic layout of Cheat Engine. You should know how to load a running process to Cheat Engine. If you don’t, please refer back to the introduction.

Open the Cheat Engine Tutorial v3

cheat_0

If you get to this article after beat the fourth stage, make sure you clear the previous result by click on ‘New scan‘ and clear work area.

Some of this article will involve assembly language. Even though it is not a requirement, but knowing some assembly will ease you. You can learn assembly at my Assembly Language Tutorial page or watching Assembly Language Primer Video for Hackers.

Password

Every stage can be accessed individually. To access this stage from Cheat Engine Tutorial’s main window, enter 098712 to password line edit.

Hint

Dark Byte (Cheat Engine creator) wrote this as hint:

In the previous step I explained how to use the Code finder to handle changing locations. But that method
alone makes it difficult to find the address to set the values you want.
That's why there are pointers:

At the bottom you'll find 2 buttons. One will change the value, and the other changes the value AND the
location of the value.
For this step you don't really need to know assembler, but it helps a lot if you do.

First find the address of the value. When you've found it use the function to find out what accesses this
address. Change the value again, and a item will show in the list. Double click that item. (or select
and click on more info) and a new window will open with detailed information on what happened when the
instruction ran.
If the assembler instruction doesn't have anything between a '[' and ']' then use another item in the list.
If it does it will say what it think will be the value of the pointer you need.
Go back to the main cheat engine window (you can keep this extra info window open if you want, but if you
close it, remember what is between the [ and ] ) and do a 4 byte scan in hexadecimal for the value
the extra info told you.
When done scanning it may return 1 or a few hundred addresses. Most of the time the address you need will
be the smallest one. Now click on manually add and select the pointer checkbox.

The window will change and allow you to type in the address of a pointer and a offset.
Fill in as address the address you just found.
If the assembler instruction has a calculation (e.g: [esi+12]) at the end then type the value in that's
at the end. else leave it 0. If it was a more complicated instruction look at the calculation.

example of a more complicated instruction:
[EAX*2+EDX+00000310] eax=4C and edx=00801234.
In this case EDX would be the value the pointer has, and EAX*2+00000310 the offset, so the offset you'd
fill in
would be 2*4C+00000310=3A8.  (this is all in hex, use cal.exe from windows in scientific mode to
calculate)

Back to the tutorial, click OK and the address will be added, If all went right the address will show
P->xxxxxxx, with xxxxxxx being the address of the value you found. If thats not right, you've done
something wrong. Now, change the value using the pointer you added in 5000 and freeze it. Then click
Change pointer, and if all went right the next button will become visible.

extra:
And you could also use the pointer scanner to find the pointer to this address

About Pointer

This section will discuss little thing about pointer. If you think you know what pointer is, you can skip this section and head to solution section.

An object in programming is instantiation of type or class. Generally, an object is a chunk of memory that can hold data. An object has a memory address (where its data begins). In C++ for example, we know various object like integer, character, floating point number, and also object instantiated from class.

An object that holds the memory address of another object is referred as a pointer. Therefore, pointer do not hold actual data, but it “point” to another object who has the data.

Accessing a pointer will indirectly accessing the variable or value pointed by the pointer. Pointer is commonly used when we do a pass by reference when calling a function.

Let’s see some code for pointer, in C++

#include <iostream>
using namespace std;

int main() {
    int data = 10;
    int * pointer = & data;
    int data2 = 5;

    cout << "Memory location of data is " << &data << endl;
    cout << "Memory location of data2 is " << &data << endl;
    cout << "Pointer now point to " << pointer << endl;

    cout << endl;

    cout << "The data we have:" << endl;
    cout << "data:     " << data << endl;
    cout << "data2:    " << data2 << endl;
    cout << "*pointer: " << *pointer << endl;

    cout << endl;

    data = 20;

    cout << "The data now:" << endl;
    cout << "data:     " << data << endl;
    cout << "data2: " << data2 << endl;
    cout << "*pointer: " << *pointer << endl;

    cout << endl;

    *pointer = 30;

    cout << "After modification on *pointer:"<<endl;
    cout << "data:     " << data << endl;
    cout << "data2:    " << data2 << endl;
    cout << "*pointer: " << *pointer << endl;

    pointer = & data2;

    cout << "Memory location of data is " << &data << endl;
    cout << "Memory location of data2 is " << &data << endl;
    cout << "Pointer now point to " << pointer << endl;

    *pointer = 10;

    cout << "After modification on *pointer:"<<endl;
    cout << "data:     " << data << endl;
    cout << "data2:    " << data2 << endl;
    cout << "*pointer: " << *pointer << endl;

    return 0;
}

In C++, to get a memory address of an object we use operator & in front of the object. Pointer can be accessed in two different manner: accessing the address value and accessing the pointed object.

In above codes, we see pointer is initialized to point the address of data ( pointer = & data ). Remember that pointer is also an object which hold other memory location as its value. Therefore, the value of pointer is now the address of data. Accessing the address value means accessing the value of pointer. Operation means to change the address pointed by pointer ( pointer = & data2 ). After that operation, pointer point to data2, not data anymore. Another one is accessing the pointed object as if we are directly manipulate them. You can see by manipulating value of data and data2 from *pointer.

In application, pointer is used heavily, because pointer is flexible. One can use a single object or having necessary amount of object. When the object is needed, it can be manipulated by pointer in any side of memory segment.

Solution 1

Information we got from the hint:

  1. It use pointer, one level pointer
  2. Address of value can change each time we press button “Change pointer”

Like always, get the address of value. I think we have cover it everytime so let’s skip and assume you have found the address, add it to working area. Right-click on it and choose “Find out what writes to this address”.

cheat_5_2

Cheat Engine might ask your confirmation to attach a debugger, this is our intention so if it asks you just confirm agree. After pressing the button, you will see a debugger window.

cheat_5_3

Go to Cheat Engine Tutorial and press ‘Change value’. Here we have one or more entries. Choose the first one. As seen from this picture, my entry is an instruction 89 02 – mov [rdx], eax on address 10002F985.

cheat_6_1

Press ‘More information’ button. A new window appears. It will gives us more information about current address and, codes in assembly language for some lines around current breakpoint. This window also display current condition of CPU registers.

Find where it says “The value of the pointer needed to find this address is probably XXXXXXXX”. For my case, it is 01103380. Basically we will find a pointer which point to, in my case 01103380.

cheat_6_2

Now close the information window and or just move it to another area of your screen. Then go back to main Cheat Engine interface and start a new scan. This time, check Hex so we will find a hexadecimal value instead of decimal. Type in the value with XXXXXXXX, whatever you got previously.

I got 1 address, a memory address points to 01103380, which is 1002C7710. We will copy the address, but we do this manually (not double clicking the entry). Press “Add address manually” button.

cheat_6_3

A new window will appear. Type in the address we got. The address for my case is 1002C7710. For offset, leave it as 0.

cheat_6_4

Press OK to finish adding. Now see the working area, there should be a new entry there, our newly created entry. The value should be the same as the other address (see the above entry). If you got “??” then you did it wrong. Try it again until you got something like this:

cheat_6_5

Try pressing “Change value” on the Cheat Engine Tutorial. Both value on our working area will change. Now change the value of entry with address “P -> XXXXXXXX” to 5000. Then, check a checkbox on column “Active” to freeze the value. Go back to Cheat Engine Tutorial and press “Change pointer”. CET will count down. If you do it right, CET will stop and the next button should be unlocked.

Cheat Engine Tutorial: Tutorial v3 – Stage 4

December 9, 2015 | Article, Labs | No Comments

We have seen Cheat Engine on previous introduction. As said on that article, Cheat Engine has provide a “cheat me” program to let us practice using Cheat Engine. Officially it is called Cheat Engine Tutorial. In this article we will use Cheat Engine and practice in “cheating” the program. Specifically, we will do the “fourth stage”.

In this article I use:

  1. Windows 8 64-bit
  2. Cheat Engine 6.3
  3. Cheat Engine Tutorial v3

Prerequisite

At least you understand the basic layout of Cheat Engine. You should know how to load a running process to Cheat Engine. If you don’t, please refer back to the introduction.

Open the Cheat Engine Tutorial v3

cheat_0

If you get to this article after beat the third stage, make sure you clear the previous result by click on ‘New scan‘ and clear work area.

Password

Every stage can be accessed individually. To access this stage from Cheat Engine Tutorial’s main window, enter 888899 to password line edit.

Hint

Dark Byte (Cheat Engine creator) wrote this as hint:

Sometimes the location something is stored at changes when you restart the game, or even while you're
playing.. In that case you can use 2 things to still make a table that works.
In this step I'll try to describe how to use the Code Finder function.

The value down here will be at a different location each time you start the tutorial, so a normal
entry in the address list wouldn't work.
First try to find the address. (you've got to this point so I assume you know how to)
When you've found the address, right-click the address in Cheat Engine and choose "Find out what
writes to this address". A window will pop up with an empty list.
Then click on the Change value button in this tutorial, and go back to Cheat Engine. If everything
went right there should be an address with assembler code there now.
Click it and choose the replace option to replace it with code that does nothing. That will also add
the code address to the code list in the advanced options window. (Which gets saved if you save your
table)

Click on stop, so the game will start running normal again, and close to close the window.
Now, click on Change value, and if everything went right the Next button should become enabled.

Note: When you're freezing the address with a high enough speed it may happen that next becomes
visible anyhow

Solution

Information we got from the hint:

  1. Address of value can change each time we press button

There are multiple solutions exist to solve this. They are:

  1. Solution 1
  2. Solution 2

Solution 1

Again this stage is similar to our first stage, except the memory address can change.

First, find the address. The value is initialized by 100. Assume the data is 4 bytes long. Set the scan option to following:

cheat_5_1

We got so many address, let’s narrow down. Go to Cheat Engine Tutorial and press “Change value”. Remember what is the new value written there. Mine is 516. Go back to Cheat Engine and filter the address and display only the address having 516 as current value. It should be only one. Copy the entry to our working area.

cheat_5_2

Now, on the working area, right-click the entry and press “Find out what writes to this address”. You will be asked a confirmation that debugger will be attached to current process. Well, that’s our intention so click ‘Yes’. Then a new window should pop up. Let’s refer this window as debugger. The window has table, a rich text editor, and some buttons. Well, the list is still empty but we will fill it 😀

cheat_5_3

Now go to Cheat Engine Tutorial and click “Change Value” and back to above dialog. Now you should see a new entry there. The entry has something written in assembly language. Now select that entry and click the replace button.

cheat_5_4

A new dialog will pop up. Clear the text on line editor and then press OK. Therefore, change this

cheat_5_5

to

cheat_5_6

Now you are brought back to debugger. Click ‘Stop’ button to stop the debugger and click ‘Close’ (the very same button) to close it.

Now go to Cheat Engine Tutorial and click Change Value. The ‘Next’ button should be unlocked now.

Solution 2

This solution will use Pointer Scan. This solution is very easy and handy. A more detail explanation can be found we discussing multilevel pointer (Stage 7)

First, get the address of value. I think we have done it many times so let’s skip and assume you have found the address, add it to working area. Here is my result:

cheat_5_20

Right-click on the address and choose “Pointer scan for this address”.

cheat_8_2

Two new window appears, just press OK.

cheat_5_22

It will ask you what filename will be the result saved to. After deciding the filename, the second window will traverse your memory and search for the pointers. It would take a while, depends on your system. Here is my result.

cheat_5_23

Now go to Cheat Engine Tutorial and click “Change pointer”. Now initiate a new search for new value displayed on Cheat Engine Tutorial. When you find it, add it to working area. Here is what mine looks like.

cheat_5_24

Look at the address of our newly found entry. Write it down or just copy the address.

Now go back to the pointer scanner and click “Pointer scanner” menu on menubar. Click on “Rescan memory – Removes pointers not pointing to the right address”.

cheat_8_7

You will have another window appear. Now write or paste the address we have copied before.

cheat_5_25

If you encounter more than one entry, you should pick one. Choose the first one with address listed as Tutorial not else (THREADSTACK, for example).

cheat_5_26

Double click the entry to add it to our working area.

cheat_5_27

You should see the address is in form P-> XXXXXXXX, similar to the form in solution one. It is a pointer, and the pointed address is having the same value as in Cheat Engine Tutorial. To make sure we have the correct address, go to Cheat Engine Tutorial and click ‘Change pointer’. You would see the value change.

To advance to next stage, on Cheat Engine, set the value to 5000 then froze the address. On Cheat Engine Tutorial, click ‘Change pointer’. Wait and the ‘Next’ button will be unlocked in some seconds. Congratulation!

Cheat Engine Tutorial: Tutorial v3 – Stage 3

December 9, 2015 | Article, Labs | No Comments

We have seen Cheat Engine on previous introduction. As said on that article, Cheat Engine has provide a “cheat me” program to let us practice using Cheat Engine. Officially it is called Cheat Engine Tutorial. In this article we will use Cheat Engine and practice in “cheating” the program. Specifically, we will do the “third stage”.

In this article I use:

  1. Windows 8 64-bit
  2. Cheat Engine 6.3
  3. Cheat Engine Tutorial v3

Prerequisite

At least you understand the basic layout of Cheat Engine. You should know how to load a running process to Cheat Engine. If you don’t, please refer back to the introduction.

Open the Cheat Engine Tutorial v3

cheat_0

If you get to this article after beat the second stage, make sure you clear the previous result by click on ‘New scan‘ and clear work area.

Password

Every stage can be accessed individually. To access this stage from Cheat Engine Tutorial’s main window, enter 890124 to password line edit.

Hint

Dark Byte (Cheat Engine creator) wrote this as hint:

In the previous tutorial we used bytes to scan, but some games store information in so called 'floating
point' notations. (probably to prevent simple memory scanners from finding it the easy way)
a floating point is a value with some digits behind the point. (like 5.12 or 11321.1)

Below you see your health and ammo. Both are stored as Floating point notations, but health is stored as
a float and ammo is stored as a double.
Click on hit me to lose some health, and on shoot to decrease your ammo with 0.5

You have to set BOTH values to 5000 or higher to proceed.

Exact value scan will work fine here, but you may want to experiment with other types too.

Solution

Information we got from the hint:

  1. No integer, only float and double number
  2. objective: get both values to at least 5000
  3. Ammo can be decreased by 0.5
  4. Health can be decreased by random value

This stage is similar to our first stage, except the number is stored as not integer. And also, we got two instead of one. One is float, another is double. But the scanning procedure is similar. We know the value.

Now set the value type to ‘Float’ and the value to 100. Click the first scan.

cheat_4_1

Well, I got 2 address. This is good enough, the narrower the result is better. On the result entries (on my case), you might see that there are value represented by 100.0 and 100. You might think that the right one is the memory which has value 100.0, aren’t you? But hold it, we can’t say it right now.

Go to Cheat Engine Tutorial and click ‘Hit me’. The health point will be decreased by random number. I got myself shot and found my HP now 98.66. Go back to Cheat Engine and see which one is changed. Now it seems our prediction is incorrect. See the changed one? That’s the one we want. Double click it to copy it to our work area.

cheat_4_3

Good! Now change the value to 5000.

Next, we need to change the ammo. Do a new scan and set the value type to ‘Double’. Set the value to 100 and click ‘First Scan’. Don’t erase the entry we made on work area, we still need it (maybe). Luckily, I got one address only.

cheat_4_5

Now go to Cheat Engine Tutorial and click ‘Fire’ to decrease the ammo value. Now let’s see if the result is the right one. My ammo is 99.5 now. Let’s go back to Cheat Engine. Bingo! The value is right, it’s also 99.5! Copy to work area.

cheat_4_6

Now, edit the ammo and set the value to 5000. Now go back to Cheat Engine Tutorial and see whether Next button is now enabled. If so, congratulation! You have beat the third stage. If not, something’s wrong. You should recheck your work. Good luck!

Cheat Engine Tutorial: Tutorial v3 – Stage 2

December 9, 2015 | Article, Labs | No Comments

We have seen Cheat Engine on previous introduction. As said on that article, Cheat Engine has provide a “cheat me” program to let us practice using Cheat Engine. Officially it is called Cheat Engine Tutorial. In this article we will use Cheat Engine and practice in “cheating” the program. Specifically, we will do the “second stage”.

In this article I use:

  1. Windows 8 64-bit
  2. Cheat Engine 6.3
  3. Cheat Engine Tutorial v3

Prerequisite

At least you understand the basic layout of Cheat Engine. You should know how to load a running process to Cheat Engine. If you don’t, please refer back to the introduction.

Open the Cheat Engine Tutorial v3

cheat_0

If you get to this article after beat the first stage, make sure you clear the previous result by click on ‘New scan‘.

Password

Every stage can be accessed individually. To access this stage from Cheat Engine Tutorial’s main window, enter 419482 to password line edit.

Hint

Dark Byte (Cheat Engine creator) wrote this as hint:

Ok, seeing that you've figured out how to find a value using exact value let's move on to the next step.

In the previous test we knew the initial value so we could do a exact value, but now we have a status bar
where we don't know the starting value.
We only know that the value is between 0 and 500. And each time you click 'hit me' you lose some health.
The amount you lose each time is shown above the status bar.

Again there are several different ways to find the value. (like doing a decreased value by... scan), but
I'll only explain the easiest. "Unknown initial value", and decreased value.
Because you don't know the value it is right now, a exact value wont do any good, so choose as scantype
'Unknown initial value', again, the value type is 4-bytes. (most windows apps use 4-bytes)
click first scan and wait till it's done.

When it is done click 'hit me'. You'll lose some of your health. (the amount you lost shows for a few
seconds and then disappears, but you don't need that)
Now go to Cheat Engine, and choose 'Decreased Value' and click 'Next Scan'
When that scan is done, click hit me again, and repeat the above till you only find a few.

We know the value is between 0 and 500, so pick the one that is most likely the address we need, and add
it to the list.
Now change the health to 5000, to proceed to the next step.

Solution

Information we got from the hint:

  1. The target is integer, initialized by unknown value
  2. Value is between 0 and 500
  3. ‘Hit me’ will decrease the Health by certain value, which will be shown
  4. objective is to change the value to 5000

The value is represented by progress bar, we don’t know the exact value. We have no choice here, set the type to ‘Unknown initial value’. Make the value type as 4 byte.

cheat_3_1

Click ‘First Scan’ and wait until the interface goes back to normal like nothing happened. It should go back to 4 byte.

cheat_3_2

Now got back to the tutorial application and click ‘Hit me’. You should see a thing says “-(Random number”. In my case, it is -8.

cheat_3_3

As you can see, I got my HP lost by 8. Go to Cheat Engine, change the value type to “Decreased value by…”. Then put the number of HP you lost. Press Next scan.

cheat_3_4

Now I see the result and found 11 entries on my list. Let’s see, I get many 0, a frequently changing value (see the red one), a memory with value 1, one with value 440, and the rest with value 400.000+. The 0 and 1 is not likely be the answer. The changing address is also, we don’t even change the value again. The huge value is also not the possible answer, the value should be on range 0 to 500. Then we are left with only one option, 440.

cheat_3_5

Copy it to our working area. Let’s change the value to at least 5000. Go back to Cheat Engine Tutorial and you would see that the Next button is enabled now. The progress bar should also get full. If it didn’t, you did it wrong. Once you click the Next button, you finish this stage 🙂

Cheat Engine Tutorial: Tutorial v3 – Stage 1

December 9, 2015 | Article, Labs | No Comments

We have seen Cheat Engine on previous introduction. As said on that article, Cheat Engine has provide a “cheat me” program to let us practice using Cheat Engine. Officially it is called Cheat Engine Tutorial. In this article we will use Cheat Engine and practice in “cheating” the program. Specifically, we will do the “first stage”.

In this article I use:

  1. Windows 8 64-bit
  2. Cheat Engine 6.3
  3. Cheat Engine Tutorial v3

Prerequisite

At least you understand the basic layout of Cheat Engine. You should know how to load a running process to Cheat Engine. If you don’t, please refer back to the introduction.

Open the Cheat Engine Tutorial v3

cheat_0

Password

Every stage can be accessed individually. To access this stage from Cheat Engine Tutorial’s main window, enter 090453 to password line edit.

Hint

Dark Byte (Cheat Engine creator) wrote this as hint:

Now that you have opened the tutorial with Cheat Engine lets get on with the next step.

You see at the bottom of this window the text Health: xxx
Each time you click 'Hit me'  your health gets decreased.

To get to the next step you have to find this value and change it to 1000

To find the value there are different ways, but I'll tell you about the easiest, 'Exact Value':
First make sure value type is set to at least 2 bytes or 4 bytes, 1 byte will also work, but you'll run
into an easy to fix problem when you've found the address and want to change it. The 8-byte may perhaps
works if the bytes after the address are 0, but I wouldn't take the bet.
Single, double, and the other scans just don't work, because they store the value in a different way.

When the value type is set correctly, make sure the scantype is set to 'Exact Value'
Then fill in the number your health is in the value box. And click 'First Scan'
After a while (if you have a extremely slow pc) the scan is done and the results are shown in the list on
the left

If you find more than 1 address and you don't know for sure which address it is, click 'Hit me', fill in
the new health value into the value box, and click 'Next Scan'
repeat this until you're sure you've found it. (that includes that there's only 1 address in the
list.....)

Now double click the address in the list on the left. This makes the address pop-up in the list at the
bottom, showing you the current value.
Double click the value, (or select it and press enter), and change the value to 1000.

If everything went ok the next button should become enabled, and you're ready for the next step.

Note:
If you did anything wrong while scanning, click "New Scan" and repeat the scanning again.
Also, try playing around with the value and click 'hit me'

Solution

Information we got from the hint:

  1. The target is integer, initialized with 100
  2. ‘Hit me’ will decrease the Health
  3. objective is to change the value to 1000

It is also stated that the value can 2-bytes or 4-bytes (Dark Byte said we should set the scan type to at least 2-bytes. Let’s assume the value is stored on 4-byte data value. Cheat Engine uses this by default. Type in 100 in the Value box, make sure Hex is unchecked. Click first scan.

cheat_2_1

Look at the result (left). Find the table that shows “Address” and “Value”. An address is where the data is stored and the value is what the data is. The actual value.

cheat_2_2

Now go to the tutorial and click “Hit me”. Now the health should go down. In my case, I got it to 96. Let’s refer this value as myHP. Go back to Cheat Engine. Type the value of myHP you got then press next scan. Alternatively, if the number of entries is not much, search the entries which the Value is the value of myHP and the Previous say 100 (our previous value before we click “Hit me”)

cheat_2_3

For this tutorial, there should be only one value. Now, my address is 011E0920, which might be different with your result. It will not be same every time, so if you don’t see the same value I got, don’t panic!. Now, double click the address so the entry got copied to our working area.

See the “Next” button on Cheat Engine Tutorial? It is greyed and blocked so we can’t go to the next tutorial. Don’t worry, we will make it clickable now. Remember our objective? Set the value of myHP to 1000. To do so, double click on myHP entry on working area, right to the value.

cheat_2_4

A new window will appear, like this.

cheat_2_5

Change 96 or whatever value you got to 1000, like this:

cheat_2_6

Go back to Cheat Engine Tutorial and see that the next button is enabled now. Click the Next button and you finished the First stage.

Programming Problem Set: 99 Problems Chapter 5

December 9, 2015 | Labs | No Comments

Ninety-nine Problems is generalized version to famous P-99: Ninety-Nine Prolog Problems collection used for teaching programming. The problems initially set for prolog but later many solutions come from various programming language. The purpose of this problem is to give us opportunity to practice our skills in logic programming. The goal is to find the most elegant solution of the given problem. Efficiency is important, but logical clarity is even more crucial.

The problem set are divided into seven categories / chapters: Lists, Arithmetic, Logic and Codes, Binary Trees, Multiway Trees, Graphs, and Miscellaneous.

In this chapter you will be only given a problem set. The solution might come however it would be on different page.

This chapter will cover about Multiway Trees. Multiway tree is composed of a root element and a (possibly) empty set of successors which are multiway trees themselves.

The problems in this chapter is a continuation of previous chapter, therefore the numbering will start from the last problem.

For the sake of writing, we will denote tree node as t (value, left, right).

63. Check whether a given object / term is a multiway tree

The predicate is succeeds if and only if its argument is a representing a multiway tree.

example:
is_tree_mp(t(a,[t(f,[t(g,[])]),t(c,[]),t(b,[t(d,[]),t(e,[])])])) -> true

64. Count the nodes of a multiway tree

Example: nnodes_m_p( t(a,[t(f,[])]),N )
 ->
2
Write another version which allows for a flow pattern

65. Tree construction from a node string

We suppose that the nodes of a multiway tree contain single characters. In the
depth-first order sequence of its nodes, a special character ^ has been inserted
whenever, during the tree traversal, the move is a backtrack to the previous level.

By this rule, the tree in the figure opposite is represented as: <tt>afg^^c^bd^e^^^</tt>

Define the syntax of the string and write a predicate tree(String,Tree) to construct
the Tree when the String is given. Work with atoms (instead of strings). Make your
predicate work in both directions.

66. Determine the internal path length of a tree

We define the internal path length of a multiway tree as the total sum of the path
lengths from the root to all nodes of the tree. By this definition, the tree in the
figure of problem 5.03 has an internal path length of 9

Write a predicate ipl(Tree,IPL) for the flow pattern (+,-).

67. Construct the bottom-up order sequence of the tree nodes

Write a predicate bottom_up(Tree,Seq) which constructs the bottom-up sequence of the
nodes of the multiway tree Tree. Seq should be a Prolog list.

What happens if you run your predicate back words?

68. Lisp-like tree representation

There is a particular notation for multiway trees in Lisp. Lisp is a prominent
functional programming language, which is used primarily for artificial intelligence
problems. As such it is one of the main competitors of Prolog. In Lisp almost
everything is a list, just as in Prolog everything is a term.

The following pictures show how multiway tree structures are represented in Lisp.

Note that in the "lispy" notation a node with successors (children) in the tree is
always the first element in a list, followed by its children. The "lispy"
representation of a multiway tree is a sequence of atoms and parentheses '(' and ')',
which we shall collectively call "tokens". We can represent this sequence of tokens as
a Prolog list; e.g. the lispy expression (a (b c)) could be represented as the Prolog
list ['(', a, '(', b, c, ')', ')']. Write a predicate tree_ltl(T,LTL) which constructs
the "lispy token list" LTL if the tree is given as term T in the usual Prolog notation.

Example:
tree_ltl_p (t(a,[t(b,[]),t(c,[])]),LTL).
-->
['(', a, '(', b, c, ')', ')']

As a second, even more interesting exercise try to rewrite tree_ltl/2 in a way that
the inverse conversion is also possible: Given the list LTL, construct the Prolog
tree T. Use difference lists.

Solution:

  1. Haskell
  2. Lisp
  3. Prolog
  4. Python

Programming Problem Set: 99 Problems Chapter 4

December 9, 2015 | Labs | No Comments

Ninety-nine Problems is generalized version to famous P-99: Ninety-Nine Prolog Problems collection used for teaching programming. The problems initially set for prolog but later many solutions come from various programming language. The purpose of this problem is to give us opportunity to practice our skills in logic programming. The goal is to find the most elegant solution of the given problem. Efficiency is important, but logical clarity is even more crucial.

The problem set are divided into seven categories / chapters: Lists, Arithmetic, Logic and Codes, Binary Trees, Multiway Trees, Graphs, and Miscellaneous.

In this chapter you will be only given a problem set. The solution might come however it would be on different page.

This chapter will cover about Binary Trees. Binary is either empty or it is composed of a root element and two successors, which are binary tree themselves.

The problems in this chapter is a continuation of previous chapter, therefore the numbering will start from the last problem.

For the sake of writing, we will denote tree node as t (value, left, right).

45. Check whether a given object / term is a binary tree

The predicate is succeeds if and only if its argument is a representing a binary tree.

example:
is_tree_p( t(a, t(b, null, null), null) -> true

46. Construct a completely balanced binary trees

In a completely balanced binary tree, the following property holds for every node: The number
of nodes in its left subtree and the number of nodes in its right subtree are almost equal,
which means their difference is not greater than one.

Write cbal_tree/2 to construct completely balanced binary trees for a given number of nodes.
The predicate should generate all solutions via backtracking. Put the letter 'x' as information
into all nodes of the tree.

Example: cbal_tree_p( 4 )
 ->
t(x, t(x, null, null), t(x, null, t(x, null, null)))
t(x, t(x, null, null), t(x, t(x, null, null), null))
...etc

47. Symmetric binary trees

Let us call a binary tree symmetric if you can draw a vertical line through the root node
and then the right subtree is the mirror image of the left subtree. Write symmetric/1 to check
whether a given binary tree is symmetric.

Hint: Write mirror/2 first to check whether one tree is the mirror image of another.
We are only interested in the structure, not in the contents of the nodes. 48. Binary search trees (dictionaries)
Write a predicate to construct a binary search tree from a list of integer numbers.

Example:
construct_p( [3,2,5,7,1] ).
-> t(3, t(2, t(1, nil, nil), nil), t(5, nil, t(7, nil, nil)))

49. Generate and test paradigm

Apply the generate-and-test paradigm to construct all symmetric, completely balanced binary trees
with a given number of nodes.

Example: sym_cbal_trees_p( 5 )
 ->
[t(x, t(x, nil, t(x, nil, nil)), t(x, t(x, nil, nil), nil)), t(x, t(x, t(x, nil, nil), nil),
 t(x, nil, t(x, nil, nil)))]

How many such trees are there with 57 nodes? Investigate about how many solutions there are for a
given number of nodes. What if the number is even? Write the appropriate solution.

50. Construct height-balanced binary trees

In a height-balanced binary tree, the following property holds for every node:
The height of its left subtree and the height of its right subtree are almost equal, which means their
difference is not greater than one.

Write a predicate hbal_tree/2 to construct height-balanced binary trees for a given height.
The predicate should generate all solutions via backtracking. Put the letter 'x' as information into
all nodes of the tree.

Example: hbal_p( 3 )
 ->
t(x, t(x, t(x, nil, nil), t(x, nil, nil)), t(x, t(x, nil, nil), t(x, nil, nil)))
t(x, t(x, t(x, nil, nil), t(x, nil, nil)), t(x, t(x, nil, nil), nil))
...etc

51. Construct height-balanced binary trees with a given number of nodes

Consider a height-balanced binary tree of height H. What is the maximum number of nodes it can contain?
Clearly, MaxN = 2^H - 1. However, what is the minimum number MinN? This question is more difficult.
Try to find a recursive statement and turn it into a predicate minNodes/2 defined as follwos:

minNodes_p( H ) -> the minimum number of nodes in a height -balanced binary tree of height H.

On the other hand, we might ask: what is the maximum height H a height-balanced binary tree with N nodes
can have?

maxHeight_p( N ) -> the maximum height of a height balanced binary tree with N nodes

Now, we can attack the main problem: construct all the height-balanced binary trees with a given number
of nodes.

hbal_tree_nodes_p( N ) -> height-balanced binary tree with N nodes.

Find out how many height-balanced trees exist for N = 15

52. Count the leaves of a binary tree

A leaf is a node with no successors.

Example: count_leaves_p( t(a, t(b, t(c, null, null), t(d, null, null)), t(e, null, null)) )
 -> 3

The leaf are [ t(c, null, null), t(d, null, null)), t(e, null, null)) ]

53. Collect the leaves of a binary tree in a list

A leaf is a node with no successors.

Example:
leaves_p( t(a, t(b, t(c, null, null), t(d, null, null)), t(e, null, null)) )
 ->
[ t(c, null, null), t(d, null, null)), t(e, null, null)) ]

54. Collect the internal nodes of a binary tree in a list

An internal node of a binary tree has either one or two non-empty successors.
Example: internals_p( t(a, t(b, t(c, null, null), t(d, null, null)), t(e, null, null)) )
->
[ t(a, t(b, t(c, null, null), t(d, null, null)), t(e, null, null)),
  t(b, t(c, null, null), t(c, null, null)) ]

55. Collect the nodes at a given level in a list

A node of a binary tree is at level N if the path from the root to the node has length N-1.
The root node is at level 1.

Example: atlevel_p( 2, t(a, t(b, t(c, null, null), t(d, null, null)), t(e, null, null)) )
->
[ t(b, t(c, null, null), t(d, null, null)), t(e, null, null)) ]

56. Construct a complete binary tree

A complete binary tree with height H is defined as follows:
The levels 1,2,3,...,H-1 contain the maximum number of nodes (i.e 2**(i-1) at the level i,
note that we start counting the levels from 1 at the root). In level H, which may contain less
than the maximum possible number of nodes, all the nodes are "left-adjusted". This means that in a
levelorder tree traversal all internal nodes come first, the leaves come second, and empty successors
(the nil's which are not really nodes!) come last.

Particularly, complete binary trees are used as data structures (or addressing schemes) for heaps.

We can assign an address number to each node in a complete binary tree by enumerating the nodes in
levelorder, starting at the root with number 1. In doing so, we realize that for every node X with
address A the following property holds: The address of X's left and right successors are 2*A and 2*A+1,
respectively, supposed the successors do exist. This fact can be used to elegantly construct a complete
binary tree structure. Write a predicate complete_binary_tree/2 with the following specification:

Example: complete_binary_tree_p( 3 ) -> The complete binary tre with N nodes

57. Layout a binary tree

Given a binary tree as the usual Prolog term t(X,L,R) (or nil). As a preparation for drawing the tree,
a layout algorithm is required to determine the position of each node in a rectangular grid.
Several layout methods are conceivable, one of them is shown in the illustration above.
In this layout strategy, the position of a node v is obtained by the following two rules:
(1) x(v) is equal to the position of the node v in the inorder
(2) y(v) is equal to the depth of the node v in the tree sequence

58. Layout a binary tree (2)

Figure located above

An alternative layout method is depicted in the above illustration. Find out the rules and write
the corresponding solution.
Hint: On a given level, the horizontal distance between neighboring nodes is constant.

Use the same conventions as in problem 57.

59. Layout a binary tree (3)

Figure located above

Yet another layout strategy is shown in the above illustration. The method yields a very compact
layout while maintaining a certain symmetry in every node. Find out the rules and write the
solution.
Hint: Consider the horizontal distance between a node and its successor nodes.
How tight can you pack together two subtrees to construct the combined binary tree?

Use the same conventions as in problem 57 and 58 and test your predicate in an appropriate way.
Note: This is a difficult problem. Don't give up too early!

Which layout do you like most?

60. A string representation of binary trees

Somebody represents binary trees as strings of the following type (see example):

a(b(d,e),c(,f(g,)))

(a) Write a solution which generates this string representation, if the tree is given as
usual (as nil or t(X,L,R) term). Then write a predicate which does this inverse;
i.e. given the string representation, construct the tree in the usual form.
Finally, combine the two predicates in a single predicate tree_string/2 which can be used in
both directions.

(b) Write the same predicate tree_string/2 using difference lists and a single predicate
tree_dlist/2 which does the conversion between a tree and a difference list in both directions.

For simplicity, suppose the information in the nodes is a single letter and there are no
spaces in the string.

61. Preorder and inorder sequence of binary trees

We consider binary trees with nodes that are identified by single lower-case letters, as in the
example of problem 60.

(a) Write predicates preorder/2 and inorder/2 that construct the preorder and inorder sequence of a
given binary tree, respectively. The results should be atoms, e.g. 'abdecfg' for the preorder sequence
of the example in problem 4.16.

(b) Can you use preorder/2 from problem part a) in the reverse direction;
i.e. given a preorder sequence, construct a corresponding tree? If not, make the necessary arrangements.

(c) If both the preorder sequence and the inorder sequence of the nodes of a binary tree are given,
then the tree is determined unambiguously. Write a predicate pre_in_tree/3 that does the job.

(d) Solve problems (a) to (c) using difference lists.

What happens if the same character appears in more than one node. Try for instance pre_in_tree(aba,baa,T).

62. Dotstring representation of binary trees

We consider again binary trees with nodes that are identified by single lower-case letters, as in
the example of problem 60. Such a tree can be represented by the preorder sequence of its nodes in
which dots (.) are inserted where an empty subtree (null) is encountered during the tree traversal.
For example, the tree shown in problem 60 is represented as <tt>'abd..e..c.fg...'</tt>.
First, try to establish a syntax (BNF or syntax diagrams) and then write a predicate tree_dotstring/2
which does the conversion in both directions. Use difference lists.

Solution:

  1. Haskell
  2. Lisp
  3. Prolog
  4. Python

Programming Problem Set: 99 Problems Chapter 3

December 9, 2015 | Labs | No Comments

Ninety-nine Problems is generalized version to famous P-99: Ninety-Nine Prolog Problems collection used for teaching programming. The problems initially set for prolog but later many solutions come from various programming language. The purpose of this problem is to give us opportunity to practice our skills in logic programming. The goal is to find the most elegant solution of the given problem. Efficiency is important, but logical clarity is even more crucial.

The problem set are divided into seven categories / chapters: Lists, Arithmetic, Logic and Codes, Binary Trees, Multiway Trees, Graphs, and Miscellaneous.

In this chapter you will be only given a problem set. The solution might come however it would be on different page.

This chapter will cover about Logic and Codes. The problems in this chapter served as continuation of previous problems, therefore the numbering will start from the last problem.

40. Truth tables for logical expression

Define and/2, or/2, nand/2, nor/2, xor/2, impl/2 and equ/2 (for logical equivalence) which
succeed or fail according to the result of their respective operations;
e.g. and(A,B) will succeed, if and only if both A and B succeed.

Now, write a predicate table/3 which prints the truth table of a given logical expression in two variables.

Example: table_p( A, B, xor(A,B) )
->
true true false
true false true
false true true
false false false

41. Truth tables for logical expressions (2)

Continue problem 40 by defining and/2, or/2, etc as being operators. This allows to write the
logical expression in the more natural way, as in the example: A and (A or not B).
Define operator precedence as usual; i.e. as in C.

Example: table2_p( A, B, A and (A or not B) )
 ->
true true true
true false true
false true false
false false false

41. Truth tables for logical expressions (2)

Generalize problem 41 in such a way that the logical expression may contain any number
of logical variables. Define table/2 in a way that table(List,Expr) prints the truth table
for the expression Expr, which contains the logical variables enumerated in List.

The index is started from 1.

Example: table3_p( [A,B,C], A and (B or C) equ A and B or A and C)
 ->
<tt>true true true true
true true false true
true false true true
true fail false true
false true true true
false true false true
false false true true
false false false true

43. Gray code

An n-bit Gray code is a sequence of n-bit strings constructed according to
certain rules. For example,

n = 1: C(1) = ['0','1'].
n = 2: C(2) = ['00','01','11','10'].
n = 3: C(3) = ['000','001','011','010','110','111','101','100'].

Find out the construction rules and write a predicate with the following specification:

% gray(N,C) :- C is the N-bit Gray code

Can you apply the method of "result caching" in order to make the predicate more
efficient, when it is to be used repeatedly?

44. Huffman code

First of all, study a good book on discrete mathematics or algorithms for a detailed
description of Huffman codes, or consult wikipedia

We suppose a set of symbols with their frequencies, given as a list of fr(S,F) terms.
Example: [fr(a,45),fr(b,13),fr(c,12),fr(d,16),fr(e,9),fr(f,5)]. Our objective is to
construct a list hc(S,C) terms, where C is the Huffman code word for the symbol S.
In our example, the result could be Hs = [hc(a,'0'), hc(b,'101'), hc(c,'100'), hc(d,'111'),
hc(e,'1101'), hc(f,'1100')] [hc(a,'01'),...etc.].

Example: huffman_p(Fs,Hs)
-> Hs is the Huffman code table for the frequency table Fs

Solution:

  1. Haskell
  2. Lisp
  3. Prolog
  4. Python

Social media & sharing icons powered by UltimatelySocial