Genera numero di 10 cifre usando una tastiera telefonica

Question

Data una tastiera del telefono come mostrato di seguito:

1 2 3 
4 5 6 
7 8 9 
    0 

Quanti diversi numeri di 10 cifre può essere formato a partire dal 1? Il vincolo è che il movimento da una cifra all'altra è simile al movimento del Cavaliere in una partita a scacchi.

Ad es. se siamo a 1 allora la cifra successiva può essere 6 o 8 se siamo a 6 allora la cifra successiva può essere 1, 7 o 0.

La ripetizione di cifre è consentita - 1616161616 è un numero valido.

Esiste un algoritmo di tempo polinomiale che risolve questo problema? Il problema ci impone di dare solo il conteggio dei numeri a 10 cifre e non necessariamente di elencare i numeri.

MODIFICA: Ho provato a modellare questo come un grafico con ogni cifra avente 2 o 3 cifre come i suoi vicini. Quindi ho usato DFS per navigare fino alla profondità di 10 nodi e quindi incrementare il conteggio dei numeri ogni volta che ho raggiunto la profondità di 10. Questo ovviamente non è tempo polinomiale. Supponendo che ogni cifra avesse solo 2 vicini, questo avrebbe richiesto almeno 2^10 iterazioni.

La variabile qui è il numero di cifre. Ho preso l'es. di numeri a 10 cifre. Potrebbe anche essere n-cifre.

Answer 1

Sicuro che può essere fatto in tempo polinomiale. È un esercizio eccellente in dynamic programming o memoization.

Supponiamo che N (il numero di cifre) sia uguale a 10 per l'esempio.

Pensate in modo simile a questo: Quanti numeri posso costruire utilizzando 10 cifre a partire da 1?

risposta è

[number of 9-digit numbers starting from 8] + 
[number of 9-digit numbers starting from 6]. 

Così quanti "numeri 9 cifre a partire da 8" sono lì? Beh,

[number of 8-digit numbers starting from 1] + 
[number of 8-digit numbers starting from 3] 

e così via. Il caso base viene raggiunto quando si ottiene la domanda "Quanti numeri a 1 cifra ci sono a partire da X" (e la risposta è ovviamente 1).

Quando si parla di complessità, l'osservazione chiave è che si riutilizza soluzioni precedentemente calcolate. Questo è per esempio, la risposta a "quanti numeri a 5 cifre a partire da 3" ci sono, può essere utilizzato sia quando si risponde "quanti numeri a 6 cifre sono lì a partire dal 8" E "quanti I numeri a 6 cifre ci sono a partire da 4 ". Questo riutilizzo fa collassare la complessità da esponenziale a polinomiale.

Diamo uno sguardo più da vicino la complessità di una soluzione di programmazione dinamica:

Tale attuazione riempirebbe in una matrice nel seguente modo:

num[1][i] = 1, for all 0<=i<=9 -- there are one 1-digit number starting from X. 

for digits = 2...N 
    for from = 0...9 
     num[digits][from] = num[digits-1][successor 1 of from] + 
          num[digits-1][successor 2 of from] + 
          ... 
          num[digits-1][successor K of from] 

return num[N][1]     -- number of N-digit numbers starting from 1. 

L'algoritmo riempie semplicemente la matrice di una cella alla un tempo e la matrice è di dimensione 10 * N e quindi viene eseguita nel tempo lineare .

---

Scritto giù dalla parte superiore della mia testa, correggimi se ci sono errori di battitura.

Answer 2

Questo può essere fatto in O (log N). Considerare la tastiera e le possibili mosse su di essa come un grafico G (V, E) dove i vertici sono le cifre disponibili e i bordi indicano quali cifre possono seguire quale. Ora, per ogni posizione di uscita i possiamo formare un vettore Paths (i) contenente il numero di diversi percorsi ogni vertice può essere raggiunto. Ora è abbastanza facile vedere che per una data posizione i e cifre v, i possibili percorsi che è possibile raggiungere è la somma dei diversi percorsi che potrebbero essere raggiunti attraverso le cifre precedenti, oppure Percorsi (i) [v] = somma (Percorsi (i-1) [v2] * (1 se (v, v2) in E altro 0) per v2 in V). Ora, questo sta prendendo la somma di ogni posizione del vettore precedente per una posizione corrispondente in una colonna della matrice di adiacenza. Possiamo quindi semplificarlo come Percorsi (i) = Percorsi (i-1) · A, dove A è la matrice di adiacenza del grafico. Eliminando la ricorsione e sfruttando l'associatività della moltiplicazione della matrice, questo diventa Percorsi (i) = Percorsi (1) · A^(i-1). Sappiamo Paths (1): abbiamo un solo percorso, alla cifra 1.

Il numero totale di percorsi per un numero n cifra è la somma dei percorsi per ogni cifra, quindi l'algoritmo finale diventa: TotalPaths (n) = somma ([1,0,0,0,0,0,0,0,0,0] · A^(n-1))

L'elevamento a potenza può essere calcolata tramite squadratura in O (log (n)) tempo, dato moltiplica costante di tempo, altrimenti O (M (n) * log (n)) dove M (n) è la complessità del vostro algoritmo arbitrario precisione moltiplicazione favorito per n numeri cifre.

Answer 3

Una risposta più semplice.

#include<stdio.h> 

int a[10] = {2,2,2,2,3,0,3,2,2,2}; 
int b[10][3] = {{4,6},{6,8},{7,9},{4,8},{0,3,9},{},{1,7,0},{2,6},{1,3},{2,4}}; 

int count(int curr,int n) 
{ 
    int sum = 0; 
    if(n==10) 
     return 1; 
    else 
    { 
     int i = 0; 
     int val = 0; 
     for(i = 0; i < a[curr]; i++) 
     { 
      val = count(b[curr][i],n+1); 
      sum += val; 
     } 
     return sum; 
    } 
} 

int main() 
{ 
    int n = 1; 
    int val = count(1,0); 
    printf("%d\n",val); 
} 

festeggiare !!

Answer 4

Questo problema può anche essere modellato come Constraint satisfaction problem (in breve CSP).

Suggerisco di utilizzare il solutore Minion (veloce e scalabile) che è possibile trovare here.

La modellazione può essere noiosa e richiede molto tempo (curva di apprendimento ripida).

Invece di utilizzare la lingua di Minion, il mio consiglio è di formulare il modello con un linguaggio di modellazione indipendente da solver come ESSENCE e trovare un convertitore di conseguenza.

Answer 5

Durata soluzione costante di tempo:

#include <iostream> 

constexpr int notValid(int x, int y) { 
return !((1 == x && 3 == y) || //zero on bottom. 
     (0 <= x && 3 > x && //1-9 
      0 <= y && 3 > y)); 
} 

class Knight { 
    template<unsigned N > constexpr int move(int x, int y) { 
     return notValid(x,y)? 0 : jump<N-1>(x,y); 
    } 

    template<unsigned N> constexpr int jump(int x, int y) { 
     return move<N>(x+1, y-2) + 
      move<N>(x-1, y-2) + 
      move<N>(x+1, y+2) + 
      move<N>(x-1, y+2) + 
      move<N>(x+2, y+1) + 
      move<N>(x-2, y+1) + 
      move<N>(x+2, y-1) + 
      move<N>(x-2, y-1); 
    } 

public: 
    template<unsigned N> constexpr int count() { 
     return move<N-1>(0,1) + move<N-1>(0,2) + 
      move<N-1>(1,0) + move<N-1>(1,1) + move<N-1>(1,2) + 
      move<N-1>(2,0) + move<N-1>(2,1) + move<N-1>(2,2); 
    } 
}; 

template<> constexpr int Knight::move<0>(int x, int y) { return notValid(x,y)? 0 : 1; } 
template<> constexpr int Knight::count<0>() { return 0; } //terminal cases. 
template<> constexpr int Knight::count<1>() { return 8; } 


int main(int argc, char* argv[]) { 
    static_assert((16 == Knight().count<2>()), "Fail on test with 2 lenght"); // prof of performance 
    static_assert((35 == Knight().count<3>()), "Fail on test with 3 lenght"); 

    std::cout<< "Number of valid Knight phones numbers:" << Knight().count<10>() << std::endl; 
    return 0; 
} 

Answer 6

funzione ricorsiva in Java:

public static int countPhoneNumbers (int n, int r, int c) { 
     if (outOfBounds(r,c)) { 
      return 0; 
     } else { 
      char button = buttons[r][c]; 
      if (button == '.') { 
       // visited 
       return 0; 
      } else { 
       buttons[r][c] = '.'; // record this position so don't revisit. 
       // Count all possible phone numbers with one less digit starting 
       int result=0; 
       result = countPhoneNumbers(n-1,r-2,c-1) 
             + countPhoneNumbers(n-1,r-2,c+1) 
             + countPhoneNumbers(n-1,r+2,c-1) 
             + countPhoneNumbers(n-1,r+2,c+1) 
             + countPhoneNumbers(n-1,r-1,c-2) 
             + countPhoneNumbers(n-1,r-1,c+2) 
             + countPhoneNumbers(n-1,r+1,c-2) 
             + countPhoneNumbers(n-1,r+1,c+2); 
       } 
       buttons[r][c] = button; // Remove record from position. 
       return result; 
      } 
     } 
    } 

Answer 7

ho deciso di affrontare questo problema e renderlo il più estensibile che posso. Questa soluzione permette di:

Definire la propria pensione (tastiera del cellulare, scacchiera, ecc)

Definire il proprio pezzo degli scacchi (cavaliere, Rook, Bishop, ecc); dovrai scrivere la classe concreta e generarla dalla fabbrica.

Recupera diverse informazioni tramite alcuni utili metodi di utilità.

Le classi sono le seguenti:

PadNumber: Classe che definisce un tasto sul pad telefono. Potrebbe essere rinominato in "Square" per rappresentare un quadrato di cartone.

ChessPiece: Classe astratta che definisce i campi per tutti i pezzi degli scacchi.

Movimento: interfaccia che definisce i metodi di movimento e consente la generazione di pezzi in fabbrica.

PieceFactory: classe di fabbrica per generare pezzi di scacchi.

Cavaliere: classe concreta che eredita da chesspiece e implementa Movimento

PhoneChess: classe di ingresso.

Driver: codice del conducente.

OK, ecco il codice :)

package PhoneChess; 

import java.awt.Point; 

public class PadNumber { 

private String number = ""; 
private Point coordinates = null; 

public PadNumber(String number, Point coordinates) 
{ 
    if(number != null && number.isEmpty()==false) 
     this.number = number; 
    else 
     throw new IllegalArgumentException("Input cannot be null or empty."); 

    if(coordinates == null || coordinates.x < 0 || coordinates.y < 0) 
     throw new IllegalArgumentException(); 
    else 
     this.coordinates = coordinates; 

} 

public String getNumber() 
{ 
    return this.number; 
} 
public Integer getNumberAsNumber() 
{ 
    return Integer.parseInt(this.number); 
} 

public Point getCoordinates() 
{ 
    return this.coordinates; 
} 
public int getX() 
{ 
    return this.coordinates.x; 
} 
public int getY() 
{ 
    return this.coordinates.y; 
} 

} 

chesspiece

package PhoneChess; 

import java.util.HashMap; 
import java.util.List; 

public abstract class ChessPiece implements Movement { 

protected String name = ""; 
protected HashMap<PadNumber, List<PadNumber>> moves = null; 
protected Integer fullNumbers = 0; 
protected int[] movesFrom = null; 
protected PadNumber[][] thePad = null; 
} 

Movimento Interfaccia:

package PhoneChess; 

import java.util.List; 

public interface Movement 
{ 
public Integer findNumbers(PadNumber start, Integer digits); 
public abstract boolean canMove(PadNumber from, PadNumber to); 
public List<PadNumber> allowedMoves(PadNumber from); 
public Integer countAllowedMoves(PadNumber from); 
} 

PieceFactory

package PhoneChess; 

public class PieceFactory 
{ 
    public ChessPiece getPiece(String piece, PadNumber[][] thePad) 
    { 
    if(thePad == null || thePad.length == 0 || thePad[0].length == 0) 
     throw new IllegalArgumentException("Invalid pad"); 
    if(piece == null) 
     throw new IllegalArgumentException("Invalid chess piece"); 

    if(piece.equalsIgnoreCase("Knight")) 
     return new Knight("Knight", thePad); 
    else 
     return null; 
} 
} 

Cavaliere classe

package PhoneChess; 

import java.util.ArrayList; 
import java.util.HashMap; 
import java.util.List; 

public final class Knight extends ChessPiece implements Movement { 

/**Knight movements 
* One horizontal, followed by two vertical 
* Or 
* One vertical, followed by two horizontal 
* @param name 
*/ 

public Knight(String name, PadNumber[][] thePad) 
{ 
    if(name == null || name.isEmpty() == true) 
     throw new IllegalArgumentException("Name cannot be null or empty"); 

    this.name = name; 
    this.thePad = thePad; 
    this.moves = new HashMap<>(); 
} 


private Integer fullNumbers = null; 

@Override 
public Integer findNumbers(PadNumber start, Integer digits) 
{ 
    if(start == null || "*".equals(start.getNumber()) || "#".equals(start.getNumber())) { throw new IllegalArgumentException("Invalid start point"); } 
    if(start.getNumberAsNumber() == 5) { return 0; } //Consider adding an 'allowSpecialChars' condition 
    if(digits == 1) { return 1; }; 

    //Init 
    this.movesFrom = new int[thePad.length * thePad[0].length]; 
    for(int i = 0; i < this.movesFrom.length; i++) 
     this.movesFrom[i] = -1; 

    fullNumbers = 0; 
    findNumbers(start, digits, 1);  
    return fullNumbers; 
} 

private void findNumbers(PadNumber start, Integer digits, Integer currentDigits) 
{ 
    //Base condition 
    if(currentDigits == digits) 
    { 
     //Reset 
     currentDigits = 1; 
     fullNumbers++; 
     return; 
    } 
    if(!this.moves.containsKey(start)) 
     allowedMoves(start); 

    List<PadNumber> options = this.moves.get(start); 
    if(options != null) 
    { 
     currentDigits++; //More digits to be got 
     for(PadNumber option : options) 
      findNumbers(option, digits, currentDigits); 
    } 
} 

@Override 
public boolean canMove(PadNumber from, PadNumber to) 
{ 
    //Is the moves list available? 
    if(!this.moves.containsKey(from.getNumber())) 
    { 
     //No? Process. 
     allowedMoves(from); 
    } 
    if(this.moves.get(from) != null) 
    { 
     for(PadNumber option : this.moves.get(from)) 
     { 
      if(option.getNumber().equals(to.getNumber())) 
       return true; 
     } 
    } 
    return false; 

} 

/*** 
* Overriden method that defines each Piece's movement restrictions. 
*/ 
@Override 
public List<PadNumber> allowedMoves(PadNumber from) 
{ 
    //First encounter 
    if(this.moves == null) 
     this.moves = new HashMap<>(); 


    if(this.moves.containsKey(from)) 
     return this.moves.get(from); 
    else 
    { 
     List<PadNumber> found = new ArrayList<>(); 
     int row = from.getY();//rows 
     int col = from.getX();//columns 

     //Cases: 
     //1. One horizontal move each way followed by two vertical moves each way 
     if(col-1 >= 0 && row-2 >= 0)//valid 
     { 
      if(thePad[row-2][col-1].getNumber().equals("*") == false && 
        thePad[row-2][col-1].getNumber().equals("#") == false) 
      { 
       found.add(thePad[row-2][col-1]); 
       this.movesFrom[from.getNumberAsNumber()] = this.movesFrom[from.getNumberAsNumber()] + 1; 
      } 

     } 
     if(col-1 >= 0 && row+2 < thePad.length)//valid 
     { 
      if(thePad[row+2][col-1].getNumber().equals("*") == false && 
        thePad[row+2][col-1].getNumber().equals("#") == false) 
      { 
       found.add(thePad[row+2][col-1]); 
       this.movesFrom[from.getNumberAsNumber()] = this.movesFrom[from.getNumberAsNumber()] + 1; 
      } 
     } 
     if(col+1 < thePad[0].length && row+2 < thePad.length)//valid 
     { 
      if(thePad[row+2][col+1].getNumber().equals("*") == false && 
        thePad[row+2][col+1].getNumber().equals("#") == false) 
      { 
       found.add(thePad[row+2][col+1]); 
       this.movesFrom[from.getNumberAsNumber()] = this.movesFrom[from.getNumberAsNumber()] + 1; 
      } 
     } 
     if(col+1 < thePad[0].length && row-2 >= 0)//valid 
     { 
      if(thePad[row-2][col+1].getNumber().equals("*") == false && 
        thePad[row-2][col+1].getNumber().equals("#") == false) 
      found.add(thePad[row-2][col+1]); 
     } 
     //Case 2. One vertical move each way follow by two horizontal moves each way 

     if(col-2 >= 0 && row-1 >= 0) 
     { 
      if(thePad[row-1][col-2].getNumber().equals("*") == false && 
        thePad[row-1][col-2].getNumber().equals("#") == false) 
      found.add(thePad[row-1][col-2]); 
     } 
     if(col-2 >= 0 && row+1 < thePad.length) 
     { 
      if(thePad[row+1][col-2].getNumber().equals("*") == false && 
        thePad[row+1][col-2].getNumber().equals("#") == false) 
      found.add(thePad[row+1][col-2]); 
     } 

     if(col+2 < thePad[0].length && row-1 >= 0) 
     { 
      if(thePad[row-1][col+2].getNumber().equals("*") == false && 
        thePad[row-1][col+2].getNumber().equals("#") == false) 
      found.add(thePad[row-1][col+2]); 
     } 
     if(col+2 < thePad[0].length && row+1 < thePad.length) 
     { 
      if(thePad[row+1][col+2].getNumber().equals("*") == false && 
        thePad[row+1][col+2].getNumber().equals("#") == false) 
      found.add(thePad[row+1][col+2]); 
     } 

     if(found.size() > 0) 
     { 
      this.moves.put(from, found); 
      this.movesFrom[from.getNumberAsNumber()] = found.size(); 
     } 
     else 
     { 
      this.moves.put(from, null); //for example the Knight cannot move from 5 to anywhere 
      this.movesFrom[from.getNumberAsNumber()] = 0; 
     } 
    } 

    return this.moves.get(from); 


} 

@Override 
public Integer countAllowedMoves(PadNumber from) 
{ 
    int start = from.getNumberAsNumber(); 

    if(movesFrom[start] != -1) 
     return movesFrom[start]; 
    else 
    { 
     movesFrom[start] = allowedMoves(from).size(); 
    } 
    return movesFrom[start]; 
} 

@Override 
public String toString() 
{ 
    return this.name; 
} 

} 

classe PhoneChess concorrente

package PhoneChess; 


public final class PhoneChess 
{ 
private ChessPiece thePiece = null; 
private PieceFactory factory = null; 

public ChessPiece ThePiece() 
{ 
    return this.thePiece; 
} 

public PhoneChess(PadNumber[][] thePad, String piece) 
{ 
    if(thePad == null || thePad.length == 0 || thePad[0].length == 0) 
     throw new IllegalArgumentException("Invalid pad"); 
    if(piece == null) 
     throw new IllegalArgumentException("Invalid chess piece"); 

    this.factory = new PieceFactory(); 
    this.thePiece = this.factory.getPiece(piece, thePad); 
} 

public Integer findPossibleDigits(PadNumber start, Integer digits) 
{ 
    if(digits <= 0) 
     throw new IllegalArgumentException("Digits cannot be less than or equal to zero"); 

    return thePiece.findNumbers(start, digits); 
} 

public boolean isValidMove(PadNumber from, PadNumber to) 
{ 
    return this.thePiece.canMove(from, to); 
} 

} 

codice del driver:

public static void main(String[] args) { 


    PadNumber[][] thePad = new PadNumber[4][3]; 
    thePad[0][0] = new PadNumber("1", new Point(0,0)); 
    thePad[0][1] = new PadNumber("2", new Point(1,0)); 
    thePad[0][2] = new PadNumber("3",new Point(2,0)); 
    thePad[1][0] = new PadNumber("4",new Point(0,1)); 
    thePad[1][1] = new PadNumber("5",new Point(1,1)); 
    thePad[1][2] = new PadNumber("6", new Point(2,1)); 
    thePad[2][0] = new PadNumber("7", new Point(0,2)); 
    thePad[2][1] = new PadNumber("8", new Point(1,2)); 
    thePad[2][2] = new PadNumber("9", new Point(2,2)); 
    thePad[3][0] = new PadNumber("*", new Point(0,3)); 
    thePad[3][1] = new PadNumber("0", new Point(1,3)); 
    thePad[3][2] = new PadNumber("#", new Point(2,3)); 

    PhoneChess phoneChess = new PhoneChess(thePad, "Knight"); 
    System.out.println(phoneChess.findPossibleDigits(thePad[0][1],4)); 
} 

} 

Answer 8

//Both the iterative and recursive with memorize shows count as 1424 for 10 digit numbers starting with 1. 
int[][] b = {{4,6},{6,8},{7,9},{4,8},{0,3,9},{},{1,7,0},{2,6},{1,3},{2,4}}; 
public int countIterative(int digit, int length) { 
    int[][] matrix = new int[length][10]; 
    for(int dig =0; dig <=9; dig++){ 
      matrix[0][dig] = 1; 
    } 
    for(int len = 1; len < length; len++){ 
     for(int dig =0; dig <=9; dig++){ 
      int sum = 0; 
      for(int i : b[dig]){ 
      sum += matrix[len-1][i]; 
      } 
      matrix[len][dig] = sum; 
     } 
    } 
    return matrix[length-1][digit]; 
} 

public int count(int index, int length, int[][] matrix){ 
    int sum = 0; 
    if(matrix[length-1][index] > 0){ 
     System.out.println("getting value from memoize:"+index + "length:"+ length); 
     return matrix[length-1][index]; 
    } 
    if(length == 1){ 
     return 1; 
    } 
    for(int i: b[index]) { 
     sum += count(i, length-1,matrix); 
    } 
    matrix[length-1][index] = sum; 
    return sum; 
} 

Answer 9

metodo restituisce lista di 10 numeri a due cifre a partire da 1. Anche in questo caso il conteggio è 1424 .

public ArrayList<String> getList(int digit, int length, String base){ 
    ArrayList<String> list = new ArrayList<String>(); 
    if(length == 1){ 
     list.add(base); 
     return list; 
    } 
    ArrayList<String> temp; 

    for(int i : b[digit]){ 
     String newBase = base +i; 
     list.addAll(getList(i, length -1, newBase)); 
    } 
    return list; 
} 

Answer 10

Non sono sicuro se ho perso qualcosa, ma leggendo la descrizione del problema sono arrivato a questa soluzione. Ha O (n) complessità temporale e O (1) complessità spaziale.

Ho pensato che il numero 1 è in un angolo, giusto? In ogni angolo puoi spostarti su uno dei lati (4 da 9 e 3, o 6 da 7 a 1) o uno dei lati "verticali" (8 da 3 e 1, o 2 da 9 e 7). Quindi, gli angoli aggiungono due mosse: una mossa laterale e una mossa "verticale". Questo è vero per tutti e quattro gli angoli (1,3,9,7).

Da ciascun lato, è possibile spostarsi su due angoli (7 e 1 da 6, 9 e 3 su 4) oppure raggiungere il tasto inferiore (0). Sono tre mosse. Due angoli e un fondo

Sul tasto inferiore (0), è possibile spostarsi su entrambi i lati (4 e 6). Quindi, in ogni fase, verifichi tutte le possibili conclusioni per il percorso della lunghezza precedente (cioè, quante sono finite su un angolo, un lato, un "verticale" o il "zero" in basso) e poi generano un nuovo finale conta in base alle regole di generazione indicate in precedenza.

• Ogni fine di un angolo aggiunge un lato e una verticale.
• Ogni lato finale aggiunge 2 angoli e un fondo.
• Ogni estremità verticale aggiunge 2 angoli.
• Ogni estremità inferiore aggiunge 2 lati.

Se si inizia dalla chiave '1', si inizia con una soluzione angolo possibile, in ogni passaggio si conta il numero di angolo, laterale, verticale e terminazioni inferiori del passo precedente e quindi applica le regole per generare il conteggio successivo.

In semplice codice javascript.

function paths(n) { 
    //Index to 0 
    var corners = 1; 
    var verticals = 0; 
    var bottom = 0; 
    var sides = 0; 

    if (n <= 0) { 
     //No moves possible for paths without length 
     return 0; 
    } 

    for (var i = 1; i < n; i++) { 
     var previousCorners = corners; 
     var previousVerticals = verticals; 
     var previousBottom = bottom; 
     var previousSides = sides; 

     sides = 1 * previousCorners + 2 * previousBottom; 
     verticals = 1 * previousCorners; 
     bottom = 1 * previousSides; 
     corners = 2 * previousSides + 2 * previousVerticals; 
     //console.log("Moves: %d, Length: %d, Sides: %d, Verticals: %d, Bottom: %d, Corners: %d, Total: %d", i, i + 1, sides, verticals, bottom, corners, sides+verticals+bottom+corners); 
    } 

    return sides + verticals + bottom + corners; 

} 

for (var i = 0; i <= 10; i++) { 
    console.log(paths(i)); 
} 

Answer 11

ricorsivo approccio Memoizzazione:

vector<vector<int>> lupt = { {4, 6}, {6, 8}, {9, 7}, {4, 8}, {3, 9, 0}, 
          {},  {1,7,0}, {6, 2}, {1, 3}, {2, 4} }; 

int numPhoneNumbersUtil(int startdigit, int& phonenumberlength, int currCount, map< pair<int,int>,int>& memT) 
{ 
    int noOfCombs = 0; 
    vector<int> enddigits; 

    auto it = memT.find(make_pair(startdigit,currCount)); 
    if(it != memT.end()) 
    { 
     noOfCombs = it->second; 
     return noOfCombs; 
    } 

    if(currCount == phonenumberlength) 
    { 
     return 1; 
    } 

    enddigits = lupt[startdigit]; 
    for(auto it : enddigits) 
    { 
     noOfCombs += numPhoneNumbersUtil(it, phonenumberlength, currCount + 1, memT); 
    } 

    memT.insert(make_pair(make_pair(startdigit,currCount), noOfCombs)); 
    return memT[make_pair(startdigit,currCount)]; 

} 

int numPhoneNumbers(int startdigit, int phonenumberlength) 
{ 
    map<pair<int,int>,int> memT; 
    int currentCount = 1; //the first digit has already been added 
    return numPhoneNumbersUtil(startdigit, phonenumberlength, currentCount, memT); 
} 

Answer 12

ho implementato sia la forza bruta e modelli di programmazione dinamici

import queue 


def chess_numbers_bf(start, length): 
    if length <= 0: 
     return 0 
    phone = [[7, 5], [6, 8], [3, 7], [9, 2, 8], [], [6, 9, 0], [1, 5], [0, 2], [3, 1], [5, 3]] 
    total = 0 
    q = queue.Queue() 
    q.put((start, 1)) 

    while not q.empty(): 
     front = q.get() 
     val = front[0] 
     len_ = front[1] 
     if len_ < length: 
      for elm in phone[val]: 
       q.put((elm, len_ + 1)) 
     else: 
      total += 1 
    return total 


def chess_numbers_dp(start, length): 
    if length <= 0: 
     return 0 

    phone = [[7, 5], [6, 8], [3, 7], [9, 2, 8], [], [6, 9, 0], [1, 5], [0, 2], [3, 1], [5, 3]] 
    memory = {} 

    def __chess_numbers_dp(s, l): 
     if (s, l) in memory: 
      return memory[(s, l)] 
     elif l == length - 1: 
      memory[(s, l)] = 1 
      return 1 
     else: 
      total_n_ways = 0 
      for number in phone[s]: 
       total_n_ways += __chess_numbers_dp(number, l+1) 
      memory[(s, l)] = total_n_ways 
      return total_n_ways 
    return __chess_numbers_dp(start, 0) 


# bf 
for i in range(0, 10): 
    print(i, chess_numbers_bf(3, i)) 
print('\n') 

for i in range(0, 10): 
    print(i, chess_numbers_bf(9, i)) 
print('\n') 

# dp 
for i in range(0, 10): 
    print(i, chess_numbers_dp(3, i)) 
print('\n') 

# dp 
for i in range(0, 10): 
    print(i, chess_numbers_dp(9, i)) 
print('\n')