optimizar pegar texto

Question

Alguien me preguntó ¿cómo puede pegar una cadena de 1000 veces en el bloc de notas de Windows. Mientras que esto se puede hacer fácilmente usando editores como Vi, estoy tratando de responder a su pregunta con el bloc de notas solamente. Así que el problema va como este, tenemos 2 opciones:

1. Podemos pegar el contenido del portapapeles en 1 pulsación de tecla (C-v).
2. Podemos duplicar el texto usando 4 pulsaciones de teclas (C-a C-c [abajo] C-v). Esto duplica el texto en el portapapeles.

¿Cómo podemos optimizar el número de pulsaciones necesarias?

---

Escribí un pequeño programa para calcular el número de pulsaciones necesarias que utiliza una heurística simple: Si (valor en la pantalla de la pulsación de tecla k - 4) > (el valor de pantalla para las pulsaciones de teclas k - 1) + portapapeles de valor, a continuación, doble la pantalla de valor de uso C-a C-c down C-p más seguir pegando con C-v

#include <stdio.h>

#define TIMES_TO_PRINTED 1000

int main() {
  int clip[100], screen[100], keystroke;
  int i;

  for (i = 0; i < 100; i++) {
    clip[i] = 0;
    screen[i] = 0;
  }

  keystroke = 0;
  screen[1] = 1;
  clip[1] = 1;
  while (screen[keystroke] < TIMES_TO_PRINTED && keystroke < 100) {
    keystroke++;

    if (keystroke > 4) {
      if ((screen[keystroke - 4] * 2) >
          (screen[keystroke - 1] + clip[keystroke])) {
        screen[keystroke] = screen[keystroke - 4] * 2;
        clip[keystroke + 1] = screen[keystroke - 4];
      } else {
        screen[keystroke] = screen[keystroke - 1] + clip[keystroke];
        clip[keystroke + 1] = clip[keystroke];
      }
    } else {
      screen[keystroke] = screen[keystroke - 1] + clip[keystroke];
      clip[keystroke + 1] = clip[keystroke];
    }
    printf("%d - %d - %d\n", clip[keystroke], keystroke, screen[keystroke]);
  }

  printf("%d %d", screen[keystroke], keystroke);
  return 0;
}

que las salidas:

Clipboard - keystroke - screen value
1 - 1 - 1
1 - 2 - 2
1 - 3 - 3
1 - 4 - 4
1 - 5 - 5
1 - 6 - 6
1 - 7 - 7
1 - 8 - 8
1 - 9 - 10
5 - 10 - 15
5 - 11 - 20
5 - 12 - 25
5 - 13 - 30
5 - 14 - 35
5 - 15 - 40
5 - 16 - 50
25 - 17 - 75
25 - 18 - 100
25 - 19 - 125
25 - 20 - 150
25 - 21 - 175
25 - 22 - 200
25 - 23 - 250
125 - 24 - 375
125 - 25 - 500
125 - 26 - 625
125 - 27 - 750
125 - 28 - 875
125 - 29 - 1000

---

Por lo tanto el uso de este heurístico podemos llegar a los 1000 utilizando el 29 de pulsaciones de teclas. No estoy seguro de si esta es la solución óptima, también es hay alguna otra manera de solucionarlo, en lugar de la enumeración de todas las posibilidades?

Answer 1

Descargo de responsabilidad:

Estoy asumiendo que sólo podemos utilizar las dos opciones: copiar y pegar, en particular yo no uso ninguna de las supresiones o parcial de selección. También asumo que empezamos con vaciar el portapapeles y una línea en el editor. Para obtener el resultado con el editor vacía (la línea en el portapapeles), sólo restan 2.

Intro:

Supongamos por un segundo, que podríamos ejecutar $x$ pastas para cualquier número real $x > 0$, incluso si $x \notin \mathbb{N}$. Si tuviéramos que repetir continuamente copiar todos (C-a C-C Down) y, a continuación, $x$ pastas (C-v), entonces obtenemos el crecimiento de la $(x+1)^y$ $(x+3)\cdot y$ pulsaciones de teclas, por lo tanto para calcular la mejor estrategia para llegar a $n$ podemos minimizar $(x+3)\cdot y$ bajo restricción $y \log(x+1) -\log n = 0$.

El Lagrangiano se define como:

$$L(x, y, \lambda) = (x+3)\cdot y + \lambda \cdot \Big(y \log (x+1) - \log n\Big)$$

and the gradient of $L$ equals $$\nabla L(x,y,\lambda) = \left[y+\lambda\cdot\frac{y}{x+1}, x+3 + \lambda \cdot \log(x+1),y\cdot\log(x+1)-\log n\right]^T$$

so $\nabla L(x,y,\lambda) = 0$ gives us $y = (-\lambda) \frac{y}{x+1}$ which is equivalent to $\lambda = -x - 1$ which can be substituted into second equation: $$x + 3 + (-x-1) \cdot \log(x+1) = 0,$$ es decir, $x = e^{W(2/e)+1}-1 \approx 3.32$ donde $W$ es la de Lambert W-función. A partir de ahí se puede derivar $y= \frac{\log n}{W(2/e)+1}$. Para ser adecuada, se debe verificar que en efecto es mínimo, pero voy a saltar. Observar que el valor de $x$ es independiente de $n$, lo que significa que en el idealizado estrategia óptima la relación de copiar todos/paste que sigue siendo el mismo.

Solución:

Por supuesto, podemos tener un problema de ejecución de exactamente $e^{W(2/e)+1}-1$ pastas, pero el de arriba nos dice que debemos tratar de estrategias que son los más cercanos a ese número. De hecho, debido a que sólo tenemos dos opciones (no eliminación), que son aún más limitados, por ejemplo, para cualquier factor principal de $n$ vamos a tener que ejecutar un paso con $p-1$ C-v's. La pregunta es cómo dividir $p^k$ en grupos. Esto es obvio para $p \geq 4 > 3.32$, por lo que haciendo exactamente $(p-1)$-pegar pasos es la mejor. Para $p = 3$ tenemos otra opción posible para hacer los pasos de usar $3^2-1 = 8$ C-v's, pero que es peor, porque la $\frac{5}{\log 3} < \frac{11}{\log 9}$. Finalmente, para $p = 2$ hacer $3$-pegar estrategia es mejor que el $1$-pegar de la estrategia. Cuando tenemos el factor de $2^k$ donde $k$ es impar, entonces haciendo $(2^3-1)$-pegar versus $(2^2-1)$-pegar + $(2^1-1)$-pegar requieren tanto de la $10$ de las pulsaciones de teclado, así que no importa.

Estrategia:

Resumiendo:

• Si $n = 1$ luego se detendrá.
• Si $n$ es regular y tiene paridad $2k+i > 0$, a continuación, realice C-a C-c Down C-v C-v C-v $k$ veces y C-a C-c Down C-v $i$ veces para luego seguir con una estrategia de $\frac{n}{2^{2k+i}}$.
• Si $n$ es extraño, entonces, encontrar algunos de los mejores del factor de $p$$n$, realice C-a C-c Down , seguido por $p-1$ C-v y, a continuación, continuar con una estrategia de $\frac{n}{p}$.

Para $n=1000$ esto te lleva C-a C-c Down C-v C-v C-v C-a C-c Down C-v C-a C-c Down C-v C-v C-v C-v C-a C-c Down C-v C-v C-v C-v C-a C-c Down C-v C-v C-v C-v para un total de 31 pulsaciones de teclas.

Editar:

Aquí es un simple código en C (porque el OP C) que calcula el valor óptimo el uso de sólo dos operaciones (copiar todo y pegar) para cualquier valor de pantalla de hasta 1000, suponiendo que partimos de la pantalla comienzan vacío, y la línea para pegar en el portapapeles (como se pretendía que fuera por la OP en el comentario). El resultado se puede ver aquí, en particular, la solución óptima para 1000 es de 29 (que es el mismo que 31-3+1, es decir, ajustando mi respuesta a comenzar con una pantalla vacía).

Espero que esto ayude a $\ddot\smile$.

Answer 2

Me gustaría duplicar el texto de $7$ tiempos, eliminar tres líneas y el doble de otro $3$ veces. Bam, $1000$ copias del texto.

O, si no podemos eliminar el texto, me gustaría utilizar el hecho de que $$1000=512+256+128+64+32+8$$ (en otras palabras, $1000$ en decimal es $1111101000$ en binario.

Así, primero se doble el texto tres veces, y pegar. Doble dos veces, pegarlo de nuevo. Doble, pegar de nuevo. Doble, pegar de nuevo. Doble, pegar de nuevo. Doble, pegar una última vez.