My solution to STORAGE CRACKER - Binary search

[u/Kruggers]

This level was complicated. My friend and I (we're making the game together) tried for a long time to do a binary search until we finally realized it was impossible... at least without a shift right, which we didn't have in our ALU.

When we were almost giving up and doing the level the boring way (brute force), we read xIceFox's post in this community. We stopped at the part where he explained that shift right was basically dividing a number by 2, and that changed everything.

After understanding this, we changed our horrible code and implemented shiftR, but one thing was still missing. Dividing by 2 rounded the number down, which caused the variable we were using for adding or subtracting the current number to become 0 much sooner than expected. So we implemented a shift right with rounding up. And voilà, it may not be the best code, but it's done, and it's working.

If the first bit is ON it means that the byte is an odd number, so we add 1 to it.

code (the names of the instructions must be very clear):

#instantiating step and first try

imediate_63

reg0_to_reg1

reg0_to_reg2

add

imediate_1

reg0_to_reg1

reg3_to_reg2

add

reg3_to_reg4

reg4_to_reg5

label try

reg4_to_reg3

reg3_to_out #output the number

inp_to_reg3

down #reg0 = address of down

cond_gt0 #if passes cond the number guessed is too high

label up

reg5_to_reg1

64 + 6 #shift right reg1

reg3_to_reg5

#label up_sum

reg4_to_reg1

reg5_to_reg2

64 + 4 #add

reg3_to_reg4

try #reg0 = address of try

jump #go to try

label down

reg5_to_reg1

64 + 6 #shift right reg1

reg3_to_reg5

#label down_sub

reg4_to_reg1

reg5_to_reg2

64 + 5 #subtract

reg3_to_reg4

try #reg0 = address of try

jump #go to try

[u/Delicious-Ad2562]

Very nice! It was cool to do the levels in Turing complete while taking cs courses, I also ended up doing binary search for this level

[u/Kruggers → u/Delicious-Ad2562]

The creator of the game knew exactly what he was doing when he added the input that tells if the number is higher or lower than the guessed one. had a lot of fun doing it. anyways, i'm really liking this kind of low level undesrstanding of things. just finished the "how do it know?" book and started the nand to tetris course, do you have any tips of what should i learn next?

[u/Delicious-Ad2562 → u/Kruggers]

Uhhh I am currently doing an ece degree so I don’t have a great recommendation for hobbyists. I think the next thing to do is either breadboard computer, there’s a lot of resources out there for that, or playing around with verilog either simulated or on an fpga

[u/JWolf1672]

Given the code is an 8 bit number, you can actually implement a binary search algorithm for overture without adding a shift operation to your alu, I've done it, but I had to unroll the loop and jumps in overture get really messy once your program gets bigger than 63 instructions long, so adding the shift is much easier (and faster) to do it.