Générer les étapes pour une chaîne donnée en parcourant un graphe

Question

Vous disposez de la grille suivante.

A B C D
E F G H
I J K L
M N O P
Q R S T
U V W X
Y Z

Votre curseur commence toujours à A et vous avez l'opération Gauche (L), Droite (R), Haut (U), Bas (D) et Entrée (E). QUESTION : Étant donné une chaîne de caractères, imprimez la séquence d'opération pour générer la chaîne de caractères ?

Par exemple :

> INPUT : CGH 
> OUTPUT : R R E D E R E

Cette question m'a été posée lors de l'entretien.

My approach : Je pensais résoudre cela en calculant la distance de Manhattan et faire un BFS sur le graphe, mais je pense que ce n'est pas optimal. et même je dois changer la distance de Manhattan pour chaque lettre. Merci d'avance

Answer 1

On peut partir d'une approche naïve. Conseil : regardez la séquence initiale comme une matrice, chaque lettre a une position : les indices de ligne et de colonne.

Étape 1.

Créez une table de hachage : clé - est une lettre, valeur - est indiciel dans la matrice 2d. Vous l'utiliserez pour une recherche rapide, par exemple, la lettre 'C' étant donnée, quel est son indice matriciel ? C'est [0,2].

La construction prend O(N) temps et O(N) espace car il faut itérer sur l'entrée et la stocker. Résoudre une lettre prend O(1) dans le cas moyen + si vous utilisez une bonne fonction de hachage, le pire cas de O(N) ne serait pas un problème.

Étape 2.

Étant donné 2 lettres de l'entrée, résolvez le décalage. Vous obtiendrez ainsi le morceau souhaité de la séquence de sortie.

Cela prend O(1) temps et O(1) espace.

Étape 3.

Répétez l'étape 2 jusqu'à ce que vous atteigniez la fin de la séquence.

Cela prend O(N) temps et O(N) espace qui est utilisé pour construire la sortie.

Résumé.

Cette solution utilise une table de hachage pour une recherche rapide des lettres. Offset pour la résolution des chemins (L/R/U/D/E). Elle prend également une complexité temporelle O(N) et une complexité spatiale O(N).

Answer 2

Tout d'abord, la position de la lettre dans la grille est facile à calculer :

function get_pos( c : char)
begin
  int col ← (c-'A') modulo 4
  int row ← (c-'A') div 4
  return (row,col)
end

En supposant que les positions (6,2) et (6,3) peuvent être utilisées

Nous pouvons simplement définir une soustraction entre les coordonnées des cellules comme :

function subtract( pos1, pos2 : position )
begin
  return (pos2.row-pos1.row, pos2.col-pos1.col)
end

Si la soustraction donne une paire (x,y), le chemin est simplement x fois le caractère 'R' si x est positif ou 'L' si x est négatif, éventuellement rien si x est zéro, et de même y fois le caractère 'D' si y est positif ou 'U' si y est négatif, éventuellement rien si y est zéro, puis nous terminons avec le caractère 'E'.

function print_row_path( pos1, pos2 : position )
begin
  path ← subtract(pos1,pos2)
  if path.row > 0 then
    print_times_char(path.row,'R')
  else if path.row < 0
    print_times_char(-path.row,'L')
  end if
end

function print_col_path( pos1, pos2 : position )
begin
  path ← subtract(pos1,pos2)
  if path.col > 0 then
    print_times_char(path.col,'D')
  else if path.col < 0
    print_times_char(-path.col,'U')
  end if
end

function print_path_direction( pos1, pos2 : position ; first_direction : direction )
begin
  if (first_direction = FIRST_MOVE_ROW) then
    print_row_path(pos1,pos2)
    print_col_path(pos1,pos2)
  else
    print_col_path(pos1,pos2)
    print_row_path(pos1,pos2)
  end if
  print 'E'
end

function print_path(start, end : char)
begin
  position pos1 ← get_pos(start)
  position pos2 ← get_pos(end)
  print_path_direction(pos1,pos2, FIRST_MOVE_ROW)
end

Où print_times_char(t,c) est une fonction qui imprime t fois le caractère c. J'ai défini deux "saveurs" d'impression de chemin, l'une imprimant les mouvements de ligne en premier et l'autre imprimant les mouvements de colonne en premier.

En supposant que les positions (6,2) et (6,3) sont interdites

Si nous ne sommes pas autorisés à utiliser les positions (6,2) et (6,3) alors :

• si 'A' ≤ début,fin ≤ 'X' ou 'Y' ≤ début,fin ≤ 'Z' : (6,2) ou (6.3) ne seront jamais utilisés dans le chemin.
• si 'A' ≤ start ≤ 'X' et 'Y' ≤ end ≤ 'Z' : pour s'assurer de ne pas utiliser les cellules interdites, imprimer d'abord les mouvements de colonnes.
• si 'A' ≤ end ≤ 'X' et 'Y' ≤ start ≤ 'Z' : cette fois, nous devons d'abord imprimer les mouvements de lignes.

En pseudo-code :

function print_path_wo_forbidden(start, end : char)
begin
  position pos1 ← get_pos(start)
  position pos2 ← get_pos(end)
  if if 'A' ≤ start ≤ 'X' and 'Y' ≤ end ≤ 'Z' then
    print_path_direction(pos1,pos2, FIRST_MOVE_COLUMN)
  else
    print_path_direction(pos1,pos2, FIRST_MOVE_COLUMN)
  end if
end

Complexité

L'impression du chemin entre deux positions est clairement en O(1), donc pour une chaîne de longueur n nous pouvons construire un algorithme O(n).

Answer 3

Vous pouvez représenter les lettres par des paires de coordonnées A = [0,0], F = [1,1] etc., il suffit alors de calculer le décalage entre la lettre actuelle et la lettre souhaitée et de l'utiliser.

Answer 4

Ce qu'a dit oleski, mais honnêtement, une table de hachage représente trop de travail de programmation inutile, surtout si votre langage n'en possède pas une en natif.

Il est souvent beaucoup plus facile d'utiliser un tableau pour représenter les emplacements de votre grille de la manière suivante :

struct point{
   int x; 
   int y;
};

point map[256];
point['C'] = (0,2);