Google Code Jam: Square Fields

Disclaimer: I'm not a computer scientist, neither a mathematician, so the code I'm going to post here is probably quite ugly and not optimized. Any suggestion for improvements is welcome!

You can read the original problem here. This time we are required to solve this puzzle:

You are given n points in the plane. You are asked to cover these points with k squares.

The squares must all be the same size, and their edges must all be parallel to the coordinate axes.

The basic idea I used to solve it, is to group the points in all possible combinations of k sets (so if we have ABC points and 2 squares, the combinations will be 'A BC', 'B AC', 'C AB'); then for each group in a combination find the square that contains those points and get the maximum square's side length of the combination. The result is the minimum side length between all combinations.
This brute-force algorithm is quite heavy and while it can solve the small input set quite easily it's no match for the large input. The solution took me quite some time to sort it out but i finally managed to make several simplifications and to solve the large input in about 17s (good enough for me).
The Python 3 code is at the end of the post. I've also made a multiprocessing version that use the same algorithm (when the un-optimized algorithm was running for hours...) but right now it's only half a second faster than the single processor one.

Google Code Jam: Old Magician

Disclaimer: I'm not a computer scientist, neither a mathematician, so the code I'm going to post here is probably quite ugly and not optimized. Any suggestion for improvements is welcome!

Just for fun I have decided to try solving some algorithmic puzzles from the Google Code Jam competition. I'm solving them in Python and I'm not setting any time limit for writing the solution (However I'll try to keep the execution time limit at 4 minutes for a small set and 8 minutes for the large one).

The first puzzle I solved is the Old Magician. This is a quite simple one and here is my code:
The "core" part of the program reads the number of the Black balls and if it's odd it means that the remaining ball must be Black. That's all :)
Next up, my solution for the Square Fields problem.

Hacking the Mario – The Reset II

This post is the last part of the explanation of the SMB Reset routine. Some of the variables that we are going to meet in this part are register buffers. Very easily, the use of buffers make the code safer (you apply the changes to the real registers only at safe points in your code, like at the beginning of the NMI) and they allow you to know the content of the registers themselves (many of them are write only).The next subroutine in the code, the one after the initialization of the sprite RAM that we saw last time, is at $8E19. This subroutine is used for resetting the Name Tables and the Attribute Tables.

$8E19>  LDA $2002 ; Clear the $2005/$2006 latch
$8E1C>  LDA $0778 ; Load the buffer of PPU #1
$8E1F>  ORA #$10 ; Set bit 4 and zeroes bits 0-3 
$8E21>  AND #$f0 ; (bkg pattern table at $1000 and increment by 1)
$8E23>  JSR $8EED ; Update PPU #1 and $0778
$8E26>  LDA #$24 ;
$8E28>  JSR $8E2D ; First work with name table 1 at $2400
$8E2B>  LDA #$20 ; After then, clean name table 0
$8E2D>  STA $2006 ; 
$8E30>  LDA #$00 ;
$8E32>  STA $2006 ; Final result: $2400 the first time, $2000 the second one
$8E35>  LDX #$04 ;
$8E37>  LDY #$c0 ;
$8E39>  LDA #$24 ;
$8E3B>  STA $2007 ; fill the proper Name Table (#1 or #0)
; with #$24 (black tile) for C0+3*100 times
$8E3E>  DEY ;
$8E3F>  BNE $8E3B ;
$8E41>  DEX ;
$8E42>  BNE $8E3B ; end fill Name Table
$8E44>  LDY #$40 ;
$8E46>  TXA ;
$8E47>  STA $0300 ; 
$8E4A>  STA $0301 ; 
$8E4D>  STA $2007 ; fill the attribute table with 00
$8E50>  DEY ;
$8E51>  BNE $8E4D ; end fill attribute table
$8E53>  STA $073F ; $2005 buffer 1
$8E56>  STA $0740 ; $2005 buffer 2
$8E59>  JMP $8EE6 ; Reset $2005

In SMB the background is scrolling during the game and to do that we need to use two Name Tables (with their Attribute Tables). The memory mirroring in the cartridge is set as vertical, so the Name Table #0 will start at $2000 and the #1 at $2400. This two Name Tables will be initialized using empty tiles.

As I said before, this code contains several buffered registers:

• $0778 buffer for PPU #1 ($2000)
• $073F and $0740 buffer for $2005, the scrolling register
• $0300 and $0301 will be explained in another post

At the beginning of the subroutine we set up the PPU writing on the PPU #1 register ($2000). This is done by changing the lower 5 bits read from the buffer at $0778 and then writing the final result to $2000 and back to $0778. The subroutine at $8EED simply store the accumulator to both the register and its buffer. The use of the buffer allow us to use this subroutine in other part of the program, ignoring the three high bits.

To cleaning the two Name Tables the programmer decided to use an interesting algorithm: the high byte of the first Name Table (#$24) is loaded into the accumulator, then a JSR is used to skip the next line, that would have loaded the accumulator with the high byte of the second Name Table (#$20). The next three instructions after the jump set the VRAM address to $2400, then a loop fills the first Name Table with the value #$24 (a black tile in the Pattern Table) and another loop zeroes the relative Attribute Table. When the subroutine reaches the ending RTS, the flow goes back to the instruction we skipped before that sets the VRAM address to $2000. The program continue as before with the two loops until he reaches another time the RTS instruction and this time he really exit the subroutine.

Actually, the final instruction of this subroutine is a simple JMP that goes to the end of another subroutine that we will see very likely in the next post. This is the instructions after the jump:

$8EE6>  STA $2005 
$8EE9>  STA $2005
$8EEC>  RTS

So this is just a little trick used to save some bytes. After the program returns to the Reset part, it simply enable the NMI (by ORing the $0778 buffer and calling the $8EED subroutine we saw earlier) and then it starts a forever loop.

The presence of a forever loop means that all the actual game is done during the NMI. This will be where the funny begins! So stay tuned!

Hacking the Mario – The Reset I

Let's start from the beginning. When you power up your NES, the first think it does is to look at memory location $FFFA for a pointer to the actual start of the program. This address is also used in case of reset and quite unsurprisingly in SMB this address is $8000 (the starting address of PGR-ROM).
The first lines of code are pretty standard stuff, disable the NMI (to do the startup without interruptions), reset the stack to point at $01FF and wait 2 VBlanks to warm up the PPU. All this from $8000 to $8012.
Then it starts the RAM initialization part. The page 7 of the RAM (from $0700 to $07FF) seems to be used as game variables storage. When you reset the console, the RAM is not automatically cleared. The SMB code does a check on some of those variables to spot if it was a reset or a power on and based on their values it cleans only some part of the memory.

$8014>  LDY #$fe    ; RAM cleaning: 
$8016>  LDX #$05    ;  if one byte of $07D7-$07DB is >= A, clear the memory to $07FE
$8018>  LDA $07D7,X ;  else if $07FF = A5, clear to $07D6
$801B>  CMP #$0a    ;   else clear to $07FE
$801D>  BCS $802B   ;
$801F>  DEX         ; Way to check Reset vs Power
$8020>  BPL $8018   ;
$8022>  LDA $07FF   ;
$8025>  CMP #$a5    ;
$8027>  BNE $802B   ;
$8029>  LDY #$d6    ;
$802B>  JSR $90CC   ; Clear RAM Subroutine to 0700+Y

Probably the memory after $07D7 contains the top scores and other data useful to keep during a reset. The routine in $90CC is the actual cleaner. It takes Y as input parameter and use a loop to clean the memory backwards  from $0700 + Y to $0000.

$90CC>  LDX #$07    ; SUB Clear_RAM ;Clear memory from $0000 to $0700+Y, skip $01FF to $0160
$90CE>  LDA #$00    ;
$90D0>  STA $06     ;
$90D2>  STX $07     ;
$90D4>  CPX #$01    ;
$90D6>  BNE $90DC   ;
$90D8>  CPY #$60    ;
$90DA>  BCS $90DE   ;
$90DC>  STA ($06),Y ;
$90DE>  DEY         ;
$90DF>  CPY #$ff    ;
$90E1>  BNE $90D4   ;
$90E3>  DEX         ;
$90E4>  BPL $90D2   ;
$90E6>  RTS         ; ENDSUB Clear_RAM

The loop is using the two addresses in Page Zero ($07 and $06) for indirectly address the whole RAM. I think that the 0x60 bytes skipped on page 1 are reserved as stack and in this way the cleaning routine can be called safely even outside the initialization part.

Continuing, there are some sound initialization (disable DPCM and enable all the other four sound channels) instructions and we set the memory $07FF to 0xA5 so next time we know if it was a reset (for now no idea what $07A7 is).

The subroutine at $8220 is responsible for initializing the RAM from $0200 to $02FF with 0xF8 every 5 bytes. Very likely this part of the RAM will contain the buffer for the SPR-RAM (coordinates of the sprites, tile index # and attributes).

$8220>  LDY #$00    ; SUB Init_Sprite_RAM ;Write every 4 byte #$F8 from $200
$8222>  BIT $04A0   ;
$8225>  LDA #$f8    ;
$8227>  STA $0200,Y ;
$822A>  INY         ;
$822B>  INY         ;
$822C>  INY         ;
$822D>  INY         ;
$822E>  BNE $8227   ;
$8230>  RTS         ; ENDSUB Init_Sprite_RAM

I don't really understand the meaning of the BIT instruction at address $8222, maybe some leftover from a previous version of the code...
There still some interesting subroutines before the end of the reset part and I will keep them for the next post!

Hacking the Mario - First steps

Hi everybody! With this post I would like to start talking about my new project: a study of the Super Mario Bross code for NES. Why I'm doing this? for no particular reasons. I don't want to make an hacked Super Mario game, there are already tons of them around. I'm just curious to see what techniques they used to program the NES (and a girl dumped me so I have a lot of free time to throw away). Very likely there are already several guides explaining the internals of the game, but there is no fun in simply reading them and this will be a simple log of what I am understanding of the code that I'm reading. I can't guarantee that the information I'll write here are accurate: I'm not a programmer, so if you're interested and you find some errors, don't be too much upset and just let me know :)
Some basic requisites if you would like to follow me:

1. Knowledge of 6502 asm.
2. A basic idea of how the NES works.

For the first point, I would recommend you to read the "Using 6502 Assembly Language" book that you can find at the bottom of this page. Just ignore the parts regarding the Apple II (NES and Apple II have nearly the same processor). For the second point, a good starting point is the info that you can find here. The Jeremy Chadwick is a very good reference txt. There are also a couple of useful tutorials in that page that can help moving the first steps with the system. Another useful tutorial is the Nerdy Nights one (with also a part about sound).

The last question before starting is: Why SMB? While it's not the smallest game of the NES library, it's been the first big hit of the system (it was actually among the first titles available for the system in USA). It doesn't use any mapper, only 32kb of PRG-ROM and only one CHR-ROM. Coming out 2 years after the release of the system, I expect that the programmers of the game used some sort of "from manual" code: they programmed what the hardware was supposed to do without "dirty tricks" that could make the code harder to read. We will see :)

The tools that I use are:

• Disassembler: dcc6502 that you can find here: www.neshq.com. If you want to run it under windows 7 64-bit, you can simply recompile the source file with something like Visual Studio Express (It uses the standard C libraries).
• HexEditor: no preferences.
• Emulator: FCEUX with its integrated debugging tools

To get the same disassembled code as mine from an iNES rom, first use the hex editor to delete the first 16 bytes from the file (the iNES header) then you can use the disassembler on it.

Stay tuned, in the next post we will start watching the code!

Kobe

Kobe è stato il primo errore di questo viaggio. OK, non era evitabile visto che la conferenza (ricordate? sono andato lì per lavoro) si teneva proprio in questa città, ma sarebbe stato l'ideale fermarsi solamente lo stretto necessario. Quello che non mi è piaciuto di Kobe è il suo stile occidentale. Le maggiori attrazioni turistiche sono il suo porto (che eccetto qualche scultura moderna è decismente triste), varie case occidentale (come la casa olandese con riproduzione di un mulino a vento, argh) ed un orto botanico adagiato sul fianco di una montagna (in Settembre niente di eccezzionale). Nella zona centrale della città, vi sono solamente alcuni tempi scintoisti, alcuni dei quali piuttosto grandi e nessun tempio buddista degno di nota. Durante il giorno, la zona sud pulula di negozi e ristoranti ed un enorme sottopassaggio collega la maggior parte dei centri commerciali e delle stazioni. Essendomi fermato a Kobe la prima settimana del viaggio, non ho girato per centri commerciali per evitare di appesantirmi inutilmente durante l'ultima settimana, quindi non ho idea se valga la pena fare shopping da quelle parti. Durante la notte, è la zona a nord delle stazioni a movimentarsi. Una serie infinita di cafè, club, karaoke e ristorantini si sviluppa in lungo e in alto alle centinaia di stradine di Kobe. Pare che in realtà questa sia la zona a luci rosse della città, o almeno così la pensano i miei colleghi. Anche se è vero che vi sono molte ragazze all'entrata di alcuni locali e che questi hanno "strani" prezzari all'entrata, con listini in minuti; io sono più propenso all'idea di somplici intrattenitrici, con cui poter bere un drink e parlare del più e del meno per un'ora o due (i prezzi poi erano relativamente bassi...).
Anche se la città non mi ha entusiasmato più di tanto, in generale mi sono divertito: andando al karaoke con i miei colleghi (30 persone in una stanza pensata per una ventina di Giapponesi) e assisetendo ad un festival di danza Yosakoi, che per la sua bellezza merita un post a parte!
Per il capitolo templi, l'Ikuta Shrine si trova in pieno centro. È un tempio carino con del personale (le ragazzine vestite di rosso e bianco!) che parlicchia inglese. Il secondo tempio, il Minatogawa shrine si trova leggermente fuori Kobe. Questo tempio è più grande del primo ed ha anche alcuni tempietti laterali. Purtroppo il parco posto dietro al tempio era chiuso, riducendone di molto le dimensioni effettive. Al momento ho trovato questi templi veramente belli, ma dopo aver visto quelli di Kyoto e Nara, beh ...

Giappone

Sono da poco tornato da un viaggio di lavoro in Giappone. Ho trascorso due settimane nella zona centrale compresa tra le città di Kobe, Osaka, Kyoto e Nara. È stato un viaggio fantastico! In questo blog posterò alcune foto e alcuni commenti, rigorosamente in ordine sparso, della mia esperienza. Una premessa: io adoro il Giappone. Molte persone lo vedono come un paese strano ed ostile, dove si mangia male e non ci si diverte. In realtà basta adattarsi un poco e semplicemente evitare gli aspetti meno piacevoli per gustarsi una indimenticabile vacanza.