Proyecto EULER # 11 - Producto más grande en una cuadrícula C ++ -- ++ campo con beginner campo con programming-challenge camp codereview Relacionados El problema

Project Euler #11 - Largest product in a grid C++


1
vote

problema

Español

https://projecteuler.net/problem=11

¿Alguna idea? Además, al medir con Chrono, se necesitan supuestamente 4 ms para calcular, ¿es este valor confiable? Los problemas anteriores tardaron con poco más de tiempo para calcular, por lo que soy sospechoso, y sigo siendo un principiante, así que no estoy seguro de cuánto tiempo "debería" tomar o si Chrono es bueno para medir el tiempo de computación.

  x + 17  
Original en ingles

https://projecteuler.net/problem=11

Any thoughts? Also, when measuring with chrono it takes supposedly 4 ms to compute, is this reliable value? Previous problems took little longer to compute so I'm suspicious, and I'm still a beginner so I'm not sure how long it "should" take or if chrono is good for measuring computing time.

#include <fstream> #include <vector> #include <string>  int main() {     std::ifstream input("grid.txt");     std::vector<std::vector<int>> numbers(20, std::vector<int>(20));      char c;     std::string str;      int row{ 0 };     int column{ 0 };     //convert from ascii to decimal     while (input.get(c))     {         str += c;         if (((int)c - 48 == -16) || ((int)c - 48 == -38)) //space or new line         {             numbers[row][column] = std::stoi(str);             column++;             str.clear();         }         if (column == 20)         {             row++;             column = 0;         }     }     int product;     int maxProduct{ 0 };     for (int i = 0; i < 20; i++)     {         product = 0;         for (int j = 0; j < 20; j++)         {             // horizontal             if (j >= 3)             {                 product = numbers[i][j] * numbers[i][j - 1] * numbers[i][j - 2] * numbers[i][j - 3];                 if (product > maxProduct)                     maxProduct = product;             }              if (j <= 16)             {                 product = numbers[i][j] * numbers[i][j + 1] * numbers[i][j + 2] * numbers[i][j + 3];                 if (product > maxProduct)                     maxProduct = product;             }             // vertical             if (i >= 3)             {                 product = numbers[i][j] * numbers[i - 1][j] * numbers[i - 2][j] * numbers[i - 3][j];                 if (product > maxProduct)                     maxProduct = product;             }              if (i <= 16)             {                 product = numbers[i][j] * numbers[i + 1][j] * numbers[i + 2][j] * numbers[i + 3][j];                 if (product > maxProduct)                     maxProduct = product;             }             // diagonal             if (i >= 3 && j >= 3)             {                 product = numbers[i][j] * numbers[i - 1][j - 1] * numbers[i - 2][j - 2] * numbers[i - 3][j - 3];                 if (product > maxProduct)                     maxProduct = product;             }             if (i <= 16 && j <= 16)             {                 product = numbers[i][j] * numbers[i + 1][j + 1] * numbers[i + 2][j + 2] * numbers[i + 3][j + 3];                 if (product > maxProduct)                     maxProduct = product;             }             if (i >= 3 && j <= 16)             {                 product = numbers[i][j] * numbers[i - 1][j + 1] * numbers[i - 2][j + 2] * numbers[i - 3][j + 3];                 if (product > maxProduct)                     maxProduct = product;             }             if (i <= 16 && j >= 3)             {                 product = numbers[i][j] * numbers[i + 1][j - 1] * numbers[i + 2][j - 2] * numbers[i + 3][j - 3];                 if (product > maxProduct)                     maxProduct = product;             }         }     }      return 0; } 
        
   
   

Lista de respuestas

3
 
vote
vote
La mejor respuesta
 

Entrada

Uso de números mágicos como 48 y -16 hace que su código sea muy críptico y difícil de entender. Considere comparar con los caracteres en su lugar.

Algoritmo / Logic

Creo que dos cosas que realmente podrían simplificar su código son:

  1. Limite las iteraciones de los bucles de quitbtn7 a quitbtn8 . Esto te hará evitar algunos controles innecesarios.

  2. Solo intente obtener los 4 números en la dirección delantera. No hay necesidad de verificar la dirección hacia atrás, ya que ya está marcado en la dirección delantera.

 

Input

Using magic numbers like 48 and -16 makes your code very cryptic and hard to understand. Consider comparing with the characters instead.

Algorithm / Logic

I think two things that could really simplify your code are:

  1. Limit the loops iterations from [0, 0] to [16, 16]. This will make you avoid some unnecessary checks.

  2. Only try to get the 4 numbers in the forward direction. There is no need to check in the backward direction as well since it's already checked in the forward direction.

 
 
2
 
vote

Tengo algunas observaciones generales sobre la resolución de problemas que no se relacionan directamente con el algoritmo:

  • Tiene muchas constantes en el código, esto significa que sería difícil probarlo, digamos, una entrada más pequeña para verificar que su algoritmo está funcionando correctamente. Una mejor solución sería generalizar la entrada a matrices de tamaño arbitrariamente y longitudes de subsecuencia. No se necesita mucho más código para hacer, y es mucho más fácil de probar. También encuentro que generalizar el problema a menudo produce una mejor comprensión del problema concreto también.

  • En la misma paleta, coloca tanto el análisis y el cálculo de la entrada en main . Esto hace que la separación del método de entrada del algoritmo sea imposible, por lo que dificulta la prueba. Dividir estos en 1 o 2 funciones separadas.

  • Para determinar empíricamente qué tan eficiente es su algoritmo, es ayuda para poder variar el tamaño de la entrada y ver cómo varía el tiempo como resultado. Esto se debe a que existen muchos factores en juego, como el costo (fijo) de analizar la entrada, cualquier corte de caché que puede (o puede que no ocurran) y los tiempos en que el sistema operativo pueda prevenir la ejecución de su programa a favor. de otro. Para obtener una imagen precisa, necesitará un tamaño de muestra bastante grande, así que repita el cálculo de unos pocos millones de veces y tome el promedio.

 

I have some general observations about problem solving that don't directly relate to the algorithm:

  • You have a lot of constants in the code, this means that it would be difficult to test with, say, a smaller input to verify that your algorithm is working correctly. A better solution would be to generalize the input to arbitrarily sized matrices and subsequence lengths. It doesn't take much more code to do, and it is way easier to test with. I also find that generalizing the problem often yields a better understanding of the concrete problem as well.

  • In the same vane, you place both your input parsing and calculation in main. This makes separating the input method from the algorithm impossible so it makes testing difficult. Split these into 1 or 2 separate functions.

  • To empirically determine how efficient your algorithm is, it is helps to be able to vary the input size and see how the time varies as a result. This is because there are potentially many factors at play, such as the (fixed) cost of parsing the input, any cache misses that may (or may not occur), and times where the operating system may preempt the execution of your program in favor of another one. To get an accurate picture, you will need a fairly large sample size, so repeat the calculation a few million times and take the average.

 
 
 
 

Relacionados problema

6  Proyecto EULER # 7: 10001ST PRIME  ( Project euler 7 10001st prime ) 
Esta es mi implementación de Project Euler # 7 . ¿Lo he exagerado de nuevo? ¿Hay algo más que debería o no debo hacer? Se ejecuta en 9 milisegundos en mi com...

61  Uso de funciones separadas para Project Euler 1  ( Using separate functions for project euler 1 ) 
Comencé a programar con Java y C ++, así que estoy acostumbrado a tener una función "principal" que llama a otras funciones que realizan el trabajo real. En l...

6  Las vocales en una cadena están en orden alfabético  ( Vowels in a string are in alphabetical order ) 
Tarea Escriba una implementación que devuelva si un 99887776655544330 tiene vocales (idioma inglés) en orden alfabético (A-Z) o no. Feedback es mi v...

6  Encontrar el siguiente palíndromo de una cadena de números  ( Finding the next palindrome of a number string ) 
Aquí está el problema: Un entero positivo se llama palíndromo si su representación en el El sistema decimal es el mismo cuando se lee de izquierda a dere...

56  Proyecto Euler Problema 1 en Python - Múltiples de 3 y 5  ( Project euler problem 1 in python multiples of 3 and 5 ) 
Me gustaría sugerencias para optimizar esta solución de fuerza bruta a problema 1 . El algoritmo actualmente comprueba cada entero entre 3 y 1000. Me gustarí...

4  Encuentre el número de subcadenas de una cadena numérica mayor que una cadena numérica dada  ( Find the number of substrings of a numerical string greater than a given num str ) 
Pregunta: http://qa.geeksforgeeks.org/9744/vinay-queried-interesting -Problem-optimización Entrada La primera línea contiene n que denota la longitud...

6  Solución de codewars a "ascensor simple"  ( Codewars solution to simple elevator ) 
Soy nuevo en la programación (menos de un año), y me gustaría mejorar. Resolví un problema en las claquinas y copié tanto mi solución como la solución venci...

1  Codificación de Google Jam: Tienda Credit Java Solution  ( Google code jam store credit java solution ) 
Sería genial si pudiera obtener este código revisado. Me encantaría consejos sobre cómo podría mejorar mi código. problema Recibirá un crédito C en una...

5  Proyecto EULER NO. 17: contando letras para escribir los números de 1 a 1000  ( Project euler no 17 counting letters to write the numbers from 1 to 1000 ) 
Soy muy nuevo en la programación y, cierto, estoy avergonzado de compartir mi código para la crítica. Este código funciona y produce la respuesta correcta a l...

5  Cuatro cuatro para obtener cualquier número  ( Four fours to get any number ) 
Decidí resolver un problema de Código Golf llamado los cuatro cuatro . Descripción del problema: El Puzzle Four Fours es un popular rompecabezas matemát...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos