Spotify Puzzles: il ReverseBinary con gli algoritmi di conversione Decimale/Binario e Binario/Decimale

Abbiamo già visto nel post Spotify Puzzles: risolvere il ReverseBinary in Java con 1 sola riga di codice come risolvere il puzzle Reverse Binary proposto da Spotify, sfruttando i metodi offerti dalle classi Integer e StringBuilder per manipolare gli oggetti, senza applicare nessuna logica di conversione tra i due sistemi di
numerazione.
Questa volta invece, implementeremo una soluzione alternativa che affronta il problema dal punto di vista concettuale, implementando quelli che sono gli algoritmi di conversione da un numero decimale alla sua relativa rappresentazione binaria e viceversa.

Per convertire un numero decimale in binario occorre dividere iterativamente per 2 il numero fino ad arrivare a 0 e prendere i resti di ogni divisione in ordine inverso.
L’esempio seguente mostra il processo, trovando la rappresentazione binaria del numero decimale 13, fornito come input di test dal puzzle proposto:

Decimal to Binary conversion

Nel nostro caso, ci basterà non effettuare l’inversione dei resti ma prenderli semplicemente nell’ordine in cui vengono generati per ottenere già la sequenza binaria invertita. Scriviamo quindi un metodo decToBinInverted che prende in input un intero e ci restituisce la sua rappresentazione binaria già invertita:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class ReverseBinary {

    private static ArrayList decToBinInverted(int n)
    {
        ArrayList num = new ArrayList();
        while (n > 0)
        {
            num.add(n%2);
            n=n/2;
        }

        return num;
    }

    public static void main(String[] args){
        int n = 0;
        ArrayList num = null;
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            n = Integer.parseInt(br.readLine());
        } catch (Exception e) {
           System.err.println("Error:" + e.getMessage()); }

        num = decToBinInverted(n);

        for (int i: num)
            System.out.print(i);
    }
}

Forniamo come input richiesto nuovamente il valore 13 e vediamo cosa ci stampa in output il programma:
INPUT
13
OUTPUT
1011

Per effettuare la conversione inversa e riconvertire quindi una sequenza binaria in un numero decimale non occorre far altro che moltiplicare ciascun bit della sequenza per le potenze di 2 crescenti, a partire dal bit meno significativo e sommare poi i valori ottenuti da ciascun bit.
Nella figura seguente è illustrata la conversione della stringa binaria ottenuta precedentemente:
Binary To Decimal conversion

Procediamo quindi con l’implementazione di questa logica nel nostro programma. Creaiamo un altro metodo che chiamiamo questa volta binToDec che prende in input l’array dei bit e ci restituisce l’intero decimale equivalente.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class ReverseBinary {

    private static ArrayList decToBin(int n)
    {
        ArrayList num = new ArrayList();
        while (n > 0)
        {
            num.add(n%2);
            n=n/2;
        }

        return num;
    }

    private static int binToDec(ArrayList num){
        int n=0;
        int exp = num.size()-1;

        for(int i : num) {
            n += i * Math.pow(2, exp);
            exp--;
        }

        return n;
    }

    public static void main(String[] args){
        int n = 0;
        ArrayList num = null;
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            n = Integer.parseInt(br.readLine());
        } catch (Exception e) {
            System.err.println("Error:" + e.getMessage()); }

        num = decToBin(n);

//      for (int i: num) {
//          System.out.print(i);
//      }

        System.out.println(binToDec(num));
    }
}

In questo caso abbiamo calcolato l’esponente relativo al bit più significativo e siamo andati a ritrovo fino all’ultimo bit, decrementando ogni volta l’esponente a cui elevare il 2 prima di moltiplicarlo per il bit stesso.

Proviamo ora ad eseguire il programma sui due casi di test forniti con il puzzle:

INPUT
13
OUTPUT
11

INPUT
47
OUTPUT
61

Sottoponendo il programma a Spotify per la verifica, otteniamo anche con questa versione una feedback positivo.

Schermata 2014-11-12 alle 21.13.27

Leave a Reply

Your email address will not be published. Required fields are marked *