language agnostic - trucos - barajar problemas de baraja de cartas en idioma agnóstico

trucos con barajas

Question

No hace mucho tiempo estuve en una entrevista, que requería resolver dos problemas muy interesantes. Tengo curiosidad de cómo abordarías las soluciones.

Problema 1:

Producto de todo excepto actual

Escriba una función que tome como entrada dos matrices enteras de longitud len, input e index, y genere una tercera matriz, result, tal que: result [i] = producto de todo en input excepto input [index [i]]

Por ejemplo, si la función se llama con len = 4, input = {2,3,4,5} e index = {1,3,2,0}, el resultado se establecerá en {40,24,30 , 60}.

IMPORTANTE: su algoritmo debe ejecutarse en tiempo lineal.

Problema 2: (el tema estaba en una de las publicaciones de Jeff)

Barajar el mazo de cartas de manera uniforme

1. Diseñe (ya sea en C ++ o en C #) un mazo de clase para representar un mazo de cartas ordenado, donde un mazo contiene 52 cartas, divididas en 13 rangos (A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K) de los cuatro palos: espadas (?), Corazones (?), Diamantes (?) Y palos (?).

2. Basado en esta clase, diseña e implementa un algoritmo eficiente para barajar una baraja de cartas. Las cartas deben barajarse uniformemente, es decir, cada carta en el mazo original debe tener la misma probabilidad de terminar en cualquier posición posible en el mazo barajado. El algoritmo debe implementarse en un método shuffle () de la clase Deck: void shuffle ()

3. ¿Cuál es la complejidad de su algoritmo (como una función del número n de cartas en el mazo)?

4. Explica cómo probarías que las cartas se barajan de manera uniforme según tu método (prueba de caja negra).

PD: tuve dos horas para codificar las soluciones

Answer 1

Barajar baraja de cartas uniformemente en C ++

#include <algorithm>

class Deck {
  // each card is 8-bit: 4-bit for suit, 4-bit for value
  // suits and values are extracted using bit-magic
  char cards[52];
  public:
  // ...
  void shuffle() {
    std::random_shuffle(cards, cards + 52);
  }
  // ...
};

Complejidad: Lineal en N. Se realizan exactamente 51 intercambios. Ver http://www.sgi.com/tech/stl/random_shuffle.html

Prueba :

  // ...
  int main() {
    typedef std::map<std::pair<size_t, Deck::value_type>, size_t> Map;
    Map freqs;    
    Deck d;
    const size_t ntests = 100000;

    // compute frequencies of events: card at position
    for (size_t i = 0; i < ntests; ++i) {
      d.shuffle();
      size_t pos = 0;
      for(Deck::const_iterator j = d.begin(); j != d.end(); ++j, ++pos) 
        ++freqs[std::make_pair(pos, *j)]; 
    }

    // if Deck.shuffle() is correct then all frequencies must be similar
    for (Map::const_iterator j = freqs.begin(); j != freqs.end(); ++j)
      std::cout << "pos=" << j->first.first << " card=" << j->first.second 
                << " freq=" << j->second << std::endl;    
  }

Como de costumbre, una prueba no es suficiente.

Answer 2

Producto de todo excepto corriente en C

void product_except_current(int input[], int index[], int out[], 
                            int len) {
  int prod = 1, nzeros = 0, izero = -1;

  for (int i = 0; i < len; ++i) 
    if ((out[i] = input[index[i]]) != 0)
      // compute product of non-zero elements 
      prod *= out[i]; // ignore possible overflow problem
    else {
      if (++nzeros == 2) 
         // if number of zeros greater than 1 then out[i] = 0 for all i
         break; 
      izero = i; // save index of zero-valued element
    }

  //  
  for (int i = 0; i < len; ++i)  
    out[i] = nzeros ? 0 : prod / out[i];                               

  if (nzeros == 1)
    out[izero] = prod; // the only non-zero-valued element
}

Answer 3

Producto de todo excepto corriente en Python

from numpy import array

def product(input, index):
    a = array(input)[index]

    if a[a == 0].size != 1:
        a = a.prod() / a # product except current
    else:
        # exaclty one non-zero-valued element in `a`
        nzi = a.nonzero() # indices of non-zero-valued elements
        a[a == 0] = a[nzi].prod()
        a[nzi] = 0

    return a

Ejemplo:

for input in ([2,3,4,5], [2,0,4,5], [0,3,0,5]):
    print product(input, [1,3,2,0]) 

Salida:

[40 24 30 60]
[40  0  0  0]
[0 0 0 0]

Answer 4

Para el primero, primero calcule el producto de los contenidos completos de la entrada, y luego para cada elemento del índice, divida el producto calculado por la entrada [índice [i]], para completar su matriz de resultados.

Por supuesto, tengo que suponer que la entrada no tiene ceros.

Answer 5

Primera pregunta:

int countZeroes (int[] vec) {
int ret = 0;
foreach(int i in vec) if (i == 0) ret++;

return ret;
}

int[] mysticCalc(int[] values, int[] indexes) {
    int zeroes = countZeroes(values); 
    int[] retval = new int[values.length];
    int product = 1;

    if (zeroes >= 2) { // 2 or more zeroes, all results will be 0
        for (int i = 0; i > values.length; i++) {
            retval[i] = 0;      
        }
        return retval;
    }
    foreach (int i in values) {
        if (i != 0) product *= i; // we have at most 1 zero, dont include in product;
    }
    int indexcounter = 0;
    foreach(int idx in indexes) {
        if (zeroes == 1 && values[idx] != 0) {  // One zero on other index. Our value will be 0
            retval[indexcounter] = 0;
        }
        else if (zeroes == 1) { // One zero on this index. result is product
            retval[indexcounter] = product;
        }
        else { // No zeros. Return product/value at index
            retval[indexcounter] = product / values[idx];
        }
        indexcouter++;
    }   
    return retval;
}

En el peor de los casos, este programa pasará por 3 vectores una vez.

Answer 6

Tnilsson, estoy de acuerdo en que la solución YXJuLnphcnQ es posiblemente más rápida, pero la idea es la misma. Olvidé agregar, que el idioma es opcional en el primer problema, así como también el segundo.

Tienes razón, ese cálculo de ceros, y el producto en el mismo ciclo es mejor. Quizás esa era la cosa.

Answer 7

Tnilsson, gran solución (porque lo hice de la misma manera: P).

No veo otra forma de hacerlo en tiempo lineal. Alguien ? Porque el gerente de reclutamiento me dijo que esta solución no era lo suficientemente fuerte.

¿Nos falta algo de súper complejo, hacemos todo en una sola línea de retorno, solución?

Answer 8

Tnilsson, también utilicé la mezcla de Fisher-Yates :). Estoy muy interesado, sobre la parte de prueba :)

Answer 9

Una solución de tiempo lineal en C # 3 para el primer problema es:

IEnumerable<int> ProductExcept(List<int> l, List<int> indexes) {
    if (l.Count(i => i == 0) == 1) {
        int singleZeroProd = l.Aggregate(1, (x, y) => y != 0 ? x * y : x);
        return from i in indexes select l[i] == 0 ? singleZeroProd : 0;
    } else {
        int prod = l.Aggregate(1, (x, y) => x * y);
        return from i in indexes select prod == 0 ? 0 : prod / l[i];
    }
}

Editar: ¡ Tomó en cuenta un solo cero! Mi última solución me tomó 2 minutos mientras estaba en el trabajo, así que no me siento tan mal :-)

Answer 10

Vaibhav, desafortunadamente tenemos que suponer, que podría haber un 0 en la tabla de entrada.

Answer 11

YXJuLnphcnQ, esa es la forma en que lo hice también. Es el más obvio.

Pero el hecho es que si escribe un algoritmo, que simplemente mezcla todas las tarjetas en la posición de colección una vez a la derecha cada vez que llama a sort () pasaría la prueba, aunque la salida no sea aleatoria.

Answer 12

Segundo problema

    public static void shuffle (int[] array) 
    {
        Random rng = new Random();   // i.e., java.util.Random.
        int n = array.length;        // The number of items left to shuffle (loop invariant).
        while (n > 1) 
        {
            int k = rng.nextInt(n);  // 0 <= k < n.
            n--;                     // n is now the last pertinent index;
            int temp = array[n];     // swap array[n] with array[k] (does nothing if k == n).
            array[n] = array[k];
            array[k] = temp;
        }
    }

Este es un copiar / pegar del artículo de wikipedia sobre la mezcla aleatoria de Fisher-Yates . O (n) complejidad

Answer 13

Aquí está la respuesta al segundo en C # con un método de prueba. Shuffle se ve O (n) para mí.

Editar: Después de mirar la mezcla de Fisher-Yates, descubrí que había reinventado ese algoritmo sin saberlo :-) es obvio, sin embargo. Implementé el enfoque de Durstenfeld que nos lleva de O (n ^ 2) -> O (n), ¡realmente inteligente!

public enum CardValue { A, Two, Three, Four, Five, Six, Seven, Eight, Nine, Ten, J, Q, K }
public enum Suit { Spades, Hearts, Diamonds, Clubs }

public class Card {
    public Card(CardValue value, Suit suit) {
        Value = value;
        Suit = suit;
    }

    public CardValue Value { get; private set; }
    public Suit Suit { get; private set; }
}

public class Deck : IEnumerable<Card> {
    public Deck() {
        initialiseDeck();
        Shuffle();
    }

    private Card[] cards = new Card[52];

    private void initialiseDeck() {
        for (int i = 0; i < 4; ++i) {
            for (int j = 0; j < 13; ++j) {
                cards[i * 13 + j] = new Card((CardValue)j, (Suit)i);
            }
        }
    }

    public void Shuffle() {
        Random random = new Random();

        for (int i = 0; i < 52; ++i) {
            int j = random.Next(51 - i);
            // Swap the cards.
            Card temp = cards[51 - i];
            cards[51 - i] = cards[j];
            cards[j] = temp;
        }
    }

    public IEnumerator<Card> GetEnumerator() {
        foreach (Card c in cards) yield return c;
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
        foreach (Card c in cards) yield return c;
    }
}

class Program {
    static void Main(string[] args) {
        foreach (Card c in new Deck()) {
            Console.WriteLine("{0} of {1}", c.Value, c.Suit);
        }

        Console.ReadKey(true);
    }
}

Answer 14

En Haskell:

import Array

problem1 input index = [(left!i) * (right!(i+1)) | i <- index]
  where left  = scanWith scanl
        right = scanWith scanr
        scanWith scan = listArray (0, length input) (scan (*) 1 input)

Answer 15

Trilsson hizo un tema separado sobre la parte de prueba de la pregunta

Cómo probar la aleatoriedad (caso en punto - Mezcla)

muy buena idea Trilsson :)