BastterCode semana 5 - MATRIX - Check if Every Row and Column Contains All Numbers
comentada em 11/03/2023 23:40

Aproveitando para quem ta participando, o que vcs acham de resolver uma questão extra por mês, de dificuldade média ?

fica confuso?
teria 1 mês para resolver e discutir

postado por @Giovanni em 07/02/2023 08:10:54

Aproveitando para quem ta participando, o que vcs acham de resolver uma questão extra por mês, de dificuldade média ?

fica confuso?
teria 1 mês para resolver e discutir

Acho uma boa ideia! 

Essa semana vai ser apertada para mim, então fui de XGH:

Ver mais

Ver mais

@Giovanni,
Gostei do desafio mensal. Acho que não fica confuso. Se ainda achar que fica confuso, na semana que lança ele não lança outro, só fica mais prazo pra postagens....

Bruteforce em C pra responder rápido. Depois eu filosofo.

bool checkValid(int** matrix, int matrixSize, int* matrixColSize){
    int i,j,verifyDigit;
    bool incomplete = false;
    for(verifyDigit=1;verifyDigit<=matrixSize&&!incomplete;verifyDigit++){
// Rows
        for(i=0;i<matrixSize&&!incomplete;i++){
            for(j=0;j<matrixSize;j++){
                if(matrix[i][j]==verifyDigit){
                    break;
                }
            }
            if(j==matrixSize){
                incomplete = true;
                break;
            }
        }

//Columns
        for(j=0;j<matrixSize&&!incomplete;j++){
            for(i=0;i<matrixSize;i++){
                if(matrix[i][j]==verifyDigit){
                    break;
                }
            }
            if(i==matrixSize){
                incomplete = true;
                break;
            }
        }

    }

    return !incomplete;
}?

péssimo desempenho, as expected.

postado por @Giovanni em 07/02/2023 08:10

Aproveitando para quem ta participando, o que vcs acham de resolver uma questão extra por mês, de dificuldade média ?

fica confuso?
teria 1 mês para resolver e discutir

@Giovanni, não fica confuso. Achei a ideia excelente! 

postado por @PMHM em 07/02/2023 08:47

Essa semana vai ser apertada para mim, então fui de XGH:


Ver mais

O que é XGH?

postado por @Giovanni em 07/02/2023 08:10

Aproveitando para quem ta participando, o que vcs acham de resolver uma questão extra por mês, de dificuldade média ?

fica confuso?
teria 1 mês para resolver e discutir

Excelente ideia! Aí no futuro, quando os desafios semanais começarem a ser nível médio, o desafio mensal pode passar a ser nível hard. 

brute force O(n³), melhorando pra O(n²):



Verifica soma, verifica duplicidade no hash. vira todo hash pra 1 numa linha, desvira pra zero na próxima (flipflop) pra não precisar zerar o hash toda vez.

bool checkValid(int** matrix, int matrixSize, int* matrixColSize){

    int i,j,k;
    int req_sum = matrixSize*(matrixSize+1)/2;
    int sum;
    int flipflop = 0;
 
    int freq[matrixSize];

    for(i=0;i<matrixSize;i++)
        freq[i]=0;

    for(i=0;i<matrixSize;i++){
        sum = 0;
        for(j=0;j<matrixSize;j++){
            sum += matrix[i][j];
            if(freq[(matrix[i][j]-1)]==flipflop)
                freq[(matrix[i][j]-1)] = !flipflop;
            else
                return false;
        }
        if(sum!=req_sum){
            return false;
        }

        flipflop=!flipflop;
    }

    for(j=0;j<matrixSize;j++){
        sum = 0;
        for(i=0;i<matrixSize;i++){
            sum += matrix[i][j];
            if(freq[(matrix[i][j]-1)]==flipflop)
                freq[(matrix[i][j]-1)] = !flipflop;
            else
                return false;
        }
        if(sum!=req_sum){
            return false;
        }

        flipflop=!flipflop;
    }

    return true;
}?

OBS: a variável k esqueci de apagar, não serve mais pra nada.

postado por @Giovanni em 07/02/2023 10:09

O que é XGH?

extreme go horse

Java, usando memorização em uma passada pela matriz, memória e runtime: O(nˆ2)


Confesso que esperava um runtime menor.

Bora pros desafios mensais tbm!

C#

public class Solution
{
    public bool CheckValid(int[][] matrix)
    {
        //armazena os número de 1 até x (comprimento da matriz)
        List<int> allNumbers = GetAllNumbers(matrix.Length);

        //para cada linha verificar se todos os itens da lista estão presentes
        for(int i = 0; i< matrix.Length; i++)
        {
            if (!ContainAllNumbers(allNumbers, matrix[i])) return false;
        }

        //para cada coluna verificar se todos os itens da lista estão presentes
        for (int i = 0; i < matrix.Length; i++)
        {
            int[] collum = GetMatrixCollum(matrix, i);
            if (!ContainAllNumbers(allNumbers, collum)) return false;
        }
                  
        return true;
    }

    private int[] GetMatrixCollum(int[][] matrix, int collumIndex)
    {
        List<int> collum = new List<int>();

        for(int i = 0; i < matrix.Length; i++)
        {
            collum.Add(matrix[i][collumIndex]);
        }

        return collum.ToArray();
    }

    private bool ContainAllNumbers(List<int> allNumbers, int[] array)
    {
        List<int> all = new List<int> (allNumbers);

        for(int i = 0; i < array.Length; i++)
        {
            if (all.Contains(array[i]))
            {
                all.Remove(array[i]);
            }
            else
            {
                return false;
            } 
        }

        return true;
    }

    private List<int> GetAllNumbers(int n)
    {
        List<int> allNumbers = new List<int>();

        for(int i = 1; i <= n; i++)
        {
            allNumbers.Add(i);
        }

        return allNumbers;
    }
}?

Dá pra refatorar e aproveitar código. Mas ta ai uma primeira versão.

Obrigado pelo feedback pessoal
me breve desafio mensal !

@Giovanni : XGH -> eXtreme Go Horse (XGH) – GO HORSE PROCESS

class Solution:
    def checkValid(self, matrix: List[List[int]]) -> bool: 
        result = True                                       #considera a resposta como verdadeira até que se prove falsa
        size = len(matrix[0])                               #mede o tamanho da matriz
        
        for i in range(size):                               #primeiro for, para encotrar as linhas e colunas da matriz
            row = Solution.grablist(matrix, i, True)        #puxa cada linha da matriz
            column = Solution.grablist(matrix, i, False)    #puxa cada coluna da matriz

            for k in range(size):                           #segundo for, para iterar dentro de cada linha e coluna se falta algum número
                if k+1 not in row or k+1 not in column:     #se falta um número na linha ou coluna...
                    result = False                          #... então resultado só pode ser falso...
                    break                                   #... e pode quebrar o segundo for
            
            if result == False: break                       #... e também quebra o 1o for

        return result
        
    # função abaixo para auxiliar a solução, recebe uma matriz, uma posição 'index' da matriz e se deseja-se linha ou coluna.
    # Retorna uma lista da enésima linha ou coluna da matriz.
    
    def grablist(matrixB: List[List[int]], index: int, isLine: bool) -> List[int]:
        if isLine == True:
            return matrixB[index]                           #para linha pega a enésima linha da matriz
        else:
            col = []
            for k in range(len(matrixB[0])):                #para coluna pega o enésimo item de cada linha.
                col.append(matrixB[k][index])               #e acrescenta ao fim de uma lista 'col'.
            return col

Criei uma função separada para pegar listas de cada linha ou coluna. Para leitura e compreensão do código acho que ficou bom, mas a eficiência do código ruim. Nessa hora C++ com ponteiros ficaria provavelmente melhor.

De acordo com o desafio mensal.

Ver mais

Solução usando bitwise operation

Beats 100% em CPU e 100% em consumo de memória também

O(n²) CPU
O(1) memory
Linguagem: Dart

Rock'n'roll baby

Kotlin

postado por @FlyCavok em 07/02/2023 23:33

Ver mais

Solução usando bitwise operation

Beats 100% em CPU e 100% em consumo de memória também

O(n²) CPU
O(1) memory
Linguagem: Dart

Rock'n'roll baby

Ta ai uma parada que eu nunca aprendi: bitwise operations haha
Vou aproveitar pra dar uma estudada, obrigado por compartilhar

Meu primeiro código em kotlin abaixo. Aprendi o básico sobre sintaxe, colchetes tal como em C, diferença entre val e var, equivalência de (0..3) com range(4) em Python.
Certamente tem jeito mais virtuoso de fazer, mas é o primeiro.

class Solution {
    fun checkValid(matrix: Array<IntArray>): Boolean {
    // size pega N numa matriz N x N.
    // linecheck e columncheck serão usados no loop para registrar quando
    // encontrado o valor numa linha ou coluna.
        val size = matrix.size
        var linecheck: Boolean
        var columncheck: Boolean

    // primeiro loop para gerar os valores que sãoesperados em cada linha ou coluna
        for (expected_value in 1..size){
    // segundo loop itera cada linha ou coluna da matriz
            for (a in 0..(size - 1)){
                // reset das 2 variáveis check para false
                linecheck = false
                columncheck = false
    // terceiro loop para iterar cada elemento dentro de uma linha ou coluna
                for (b in 0..(size-1)){
    // se encontrar o valor naquele elemento, linecheck torna-se true
                    if (matrix[a][b] == expected_value){
                        linecheck = true
                    }
    // se encontrar o valor naquele elemento, columncheck torna-se true
                    if (matrix[b][a] == expected_value){
                        columncheck = true
                    }
                    
    // se as duas varáveis são true não há porque continuar iterando dentro da linha e coluna
                    if (linecheck == true && columncheck == true){
                        break
                    }
                }
    // ao fim da iteração de cada linha e coluna, se houver um check false, já retorna false
            if (linecheck == false || columncheck == false ){
                return false
                }
            }
        }
    // depois dos loops, se não encontrar nada falso, é porque é verdadeiro
        return true
    }
}?

Queridos,
Queria pedir uma ajuda nesse desafio.
Dado a matriz abaixo, qual o resultado esperado? Ela é válida ou não?

Caso ela não seja válida, qual o critério que invalida ela?

matrix = [
 [15, 7, 18, 11, 19, 10, 14, 16, 8, 2, 3, 6, 5, 1, 17, 12, 9, 4, 13],                      
 [17, 15, 9, 8, 11, 13, 7, 6, 5, 1, 3, 16, 12, 19, 10, 2, 4, 14, 18],                      
 [19, 14, 12, 10, 8, 9, 17, 16, 4, 3, 13, 18, 1, 5, 7, 11, 2, 15, 6],                      
 [4, 2, 10, 15, 19, 16, 8, 9, 5, 3, 1, 11, 13, 14, 6, 18, 12, 17, 7],                      
 [13, 19, 9, 16, 5, 8, 6, 12, 14, 11, 18, 10, 7, 2, 3, 4, 15, 17, 1],                      
 [4, 7, 18, 11, 17, 16, 5, 12, 10, 1, 15, 13, 14, 6, 19, 2, 3, 9, 8],                      
 [14, 5, 15, 1, 18, 6, 12, 7, 8, 9, 3, 13, 2, 10, 19, 4, 11, 16, 17],                      
 [10, 3, 1, 8, 14, 19, 11, 18, 15, 13, 9, 12, 16, 17, 7, 4, 5, 2, 6],                      
 [14, 13, 19, 18, 7, 2, 4, 8, 10, 17, 12, 5, 15, 1, 6, 9, 11, 3, 16],                      
 [19, 8, 10, 18, 16, 12, 11, 17, 4, 9, 7, 2, 5, 13, 15, 3, 6, 1, 14],                      
 [1, 10, 6, 14, 7, 18, 3, 9, 4, 16, 5, 11, 13, 17, 15, 8, 19, 2, 12],                      
 [13, 10, 5, 16, 1, 19, 17, 3, 9, 11, 7, 8, 12, 6, 4, 2, 14, 15, 18],                      
 [17, 2, 1, 6, 9, 19, 18, 14, 4, 11, 12, 13, 16, 5, 8, 7, 3, 10, 15],                      
 [1, 4, 10, 5, 13, 6, 18, 11, 3, 2, 15, 14, 16, 12, 17, 19, 8, 9, 7],                      
 [2, 14, 3, 12, 16, 17, 11, 9, 1, 6, 5, 19, 10, 13, 4, 18, 7, 15, 8],
 [15, 9, 8, 18, 14, 13, 4, 12, 5, 17, 6, 1, 11, 16, 19, 3, 7, 2, 10],
 [15, 8, 12, 16, 13, 2, 6, 19, 18, 14, 10, 5, 11, 9, 7, 1, 3, 17, 4],
 [15, 6, 17, 7, 5, 3, 1, 9, 19, 12, 10, 11, 16, 14, 18, 8, 2, 13, 4],
 [6, 11, 10, 14, 2, 13, 16, 1, 9, 15, 8, 19, 17, 3, 5, 18, 7, 4, 12]] 

O meu resultado tá diferente do caso de teste do site.

Mas, quando eu mando ordenar as linhas ele me mostra uma matriz de 19 colunas por 19 linhas. Com todos os números em cada linha. 
O que eu estou fazendo errado?

matriz_ordenada = [
 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19],                     
 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19],                     
 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19],                     
 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19],                     
 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19],                     
 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19],                     
 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19],                     
 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19],                     
 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19],                     
 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19],                     
 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19],                     
 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19],                     
 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19],                     
 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19],                     
 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19],
 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19],
 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19],
 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19],
 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]] 

P.S.: @Gustavo, não rola colocar sintaxe pra Ruby, não, né?

@Abra ruby acho q já tentei mas a formatação não ficou boa, vou ver de novo e te aviso se conseguir

Nesse desafio eu passo... rs

estou igual bastter race.  "Nasceu Ontem"

@Abra Já entendi. É o lance da COLUNA não ter todos os números. Eu tava focado só na LINHA.
Obrigado a todos.
@Gustavo muuuuito obrigado.

postado por @Abra em 08/02/2023 10:55

Queridos,
Queria pedir uma ajuda nesse desafio.
Dado a matriz abaixo, qual o resultado esperado? Ela é válida ou não?

Caso ela não seja válida, qual o critério que invalida ela?

matrix = [
 [15, 7, 18, 11, 19, 10, 14, 16, 8, 2, 3, 6, 5, 1, 17, 12, 9, 4, 13],                      
 [17, 15, 9, 8, 11, 13, 7, 6, 5, 1, 3, 16, 12, 19, 10, 2, 4, 14, 18],                      
 [19, 14, 12, 10, 8, 9, 17, 16, 4, 3, 13, 18, 1, 5, 7, 11, 2, 15, 6],                      
 [4, 2, 10, 15, 19, 16, 8, 9, 5, 3, 1, 11, 13, 14, 6, 18, 12, 17, 7],                      
 [13, 19, 9, 16, 5, 8, 6, 12, 14, 11, 18, 10, 7, 2, 3, 4, 15, 17, 1],                      
 [4, 7, 18, 11, 17, 16, 5, 12, 10, 1, 15, 13, 14, 6, 19, 2, 3, 9, 8],                      
 [14, 5, 15, 1, 18, 6, 12, 7, 8, 9, 3, 13, 2, 10, 19, 4, 11, 16, 17],                      
 [10, 3, 1, 8, 14, 19, 11, 18, 15, 13, 9, 12, 16, 17, 7, 4, 5, 2, 6],                      
 [14, 13, 19, 18, 7, 2, 4, 8, 10, 17, 12, 5, 15, 1, 6, 9, 11, 3, 16],                      
 [19, 8, 10, 18, 16, 12, 11, 17, 4, 9, 7, 2, 5, 13, 15, 3, 6, 1, 14],                      
 [1, 10, 6, 14, 7, 18, 3, 9, 4, 16, 5, 11, 13, 17, 15, 8, 19, 2, 12],                      
 [13, 10, 5, 16, 1, 19, 17, 3, 9, 11, 7, 8, 12, 6, 4, 2, 14, 15, 18],                      
 [17, 2, 1, 6, 9, 19, 18, 14, 4, 11, 12, 13, 16, 5, 8, 7, 3, 10, 15],                      
 [1, 4, 10, 5, 13, 6, 18, 11, 3, 2, 15, 14, 16, 12, 17, 19, 8, 9, 7],                      
 [2, 14, 3, 12, 16, 17, 11, 9, 1, 6, 5, 19, 10, 13, 4, 18, 7, 15, 8],
 [15, 9, 8, 18, 14, 13, 4, 12, 5, 17, 6, 1, 11, 16, 19, 3, 7, 2, 10],
 [15, 8, 12, 16, 13, 2, 6, 19, 18, 14, 10, 5, 11, 9, 7, 1, 3, 17, 4],
 [15, 6, 17, 7, 5, 3, 1, 9, 19, 12, 10, 11, 16, 14, 18, 8, 2, 13, 4],
 [6, 11, 10, 14, 2, 13, 16, 1, 9, 15, 8, 19, 17, 3, 5, 18, 7, 4, 12]] 

O meu resultado tá diferente do caso de teste do site.

Mas, quando eu mando ordenar as linhas ele me mostra uma matriz de 19 colunas por 19 linhas. Com todos os números em cada linha. 
O que eu estou fazendo errado?

matriz_ordenada = [
 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19],                     
 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19],                     
 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19],                     
 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19],                     
 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19],                     
 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19],                     
 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19],                     
 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19],                     
 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19],                     
 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19],                     
 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19],                     
 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19],                     
 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19],                     
 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19],                     
 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19],
 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19],
 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19],
 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19],
 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]] 

P.S.: @Gustavo, não rola colocar sintaxe pra Ruby, não, né?

Batendo o olho rapidamente, vi que na 1a coluna tem o 14 e o 1 repetidos, então terá número faltante pelo menos na 1a coluna.

postado por @Abra em 08/02/2023 11:17

Abra Já entendi. É o lance da COLUNA não ter todos os números. Eu tava focado só na LINHA.
Obrigado a todos.
Gustavo muuuuito obrigado.

@Abra
Até aí eu consegui fazer rsrs Problema agora é na coluna..
Se vc tiver uma luz para mim
Valeu!
 

Tentei ser pytônico

Ver mais

Pronto... Já posso mostrar minha versão Ruby não me deixa brincar...
Primeiro a linha de raciocínio:

1. Preciso ver se uma lista tem todos os números entre 1 e o tamanho da lista.

1.1 Cria uma lista com todos os números

expected_line = (1..linha.size).to_a

1.2 Quando eu subtraio uma lista de outra eu recebo uma lista com a diferença. Então, remover a linha a ser validada da linha esperada(a que contem todos os números) vai retornar uma lista vazia para linhas validas.

expected_line - line_to_be_validated == [] # Is equal to [], empty list, for valid lines

1.3 Agora eu preciso aplicar essa função para todas as linhas na matriz. Daí entra o método #reduce que transforma uma lista em um valor. E, eu quero transformar uma lista em um valor true(quando todas as linhas são validas) ou false(quando qualquer uma dessas linhas for inválida).
Maaaas, como fazer para inicializar um acumulador booleano? Aí entra uma maracutaia do Ruby. O método presente nas listas chamado #compact. Ele funciona removendo valores nulos de uma lista.

> [nil, 1, nil, 2, nil, nil, 3].compact
=> [1, 2, 3]

 

E, como o #compact vai ajudar, aqui? Simples: eu inicializo o acumulador do #reduce como nulo. Daí eu coloco a resposta(que começa nula) e a validação da linha em um array. Chamo o compact(pra remover o valor inicial nulo) e chamo um reduce com & que vai fazer uma operação AND nos elementos do array.

matrix.reduce(nil) do |answer, line|
  [answer, (expected_line - line).empty?].compact.reduce(:&)
end

Parece complicado escrevendo. Mas, a execução é algo assim:

[1, 2, 3] # A lista que está sendo testada

# O que acontece em cada elemento nesse reduce:
# Primeiro elemento da lista: 1 o acumulador está nulo.
[nil, true].compact => [true].reduce(:&) => true 

# Segundo elemento da lista: 2. O acumulador está como true.
[true, true].compact => [true, true].reduce(:&) => true & true => true 

# Terceiro elemento da lista: 3. O acumulador está como true.
[true, true].compact => [true, true].reduce(:&) => true & true => true 

 

Nesse ponto eu tenho a validação para as linhas da matriz.
Agora eu preciso da validação das colunas. Eu não tenho idéia de como validar as colunas. Mas, já sei validar as linhas. Então, lembrei das aulas de matemática da 8a série, onde aprendi que tu pode virar uma matriz para que as colunas passem a ser linhas. Com isso eu posso usar a validação que já tenho.
E, mais uma vez o Ruby me deu essa moral de já ter um método para transposição de matriz. Então, foi só aplicar o mesmo validador na matriz. E, na matriz transposta.
Código Final

def check_valid(matrix)
  expected_line = (1..matrix.size).to_a

  validator = ->(m) do
    m.reduce(nil) do |answer, line|
      [answer, (expected_line - line).empty?].compact.reduce(:&)
    end
  end

  [matrix, matrix.transpose].map(&validator).reduce(:&)
end

Observa que eu extrai o código que faz o reduce nas linhas para uma variável chamada validator. Essas seta é pra criar uma bloco executável de código conhecido como lambda.



Daí que eu crio uma lista com a matriz original e a versão transposta dela. Faço um map usando o validador. E, o mesmo reduce entre valores booleanos(feito na validação da linha) pra ter a resposta final.
Resultado Final

@Abra   Você implementou metade.

O problema quer que todas as linhas e todas as colunas tenham 1..n

Então

1 2 3
1 2 3
1 2 3   tá errado. Todas as linhas estão certas, mas na coluna 1 estão faltando 2 e 3, na coluna 2 estão faltando 1 e 3 e na coluna 3 estão faltando 1 e 2.
1 3 2
2 1 3
3 2 1   tá correto

@Padfoot
Explicação:

cada int no dart possui 64 bits.

Daí eu pego cada bit dentro do int para representar um valor de n.

por ex,

n = 1  [ 0000000000000000000000000000000000000000000000000000000000000001]
n = 2  [ 0000000000000000000000000000000000000000000000000000000000000011]
n = 3  [ 0000000000000000000000000000000000000000000000000000000000000111]
...
n = 7  [ 0000000000000000000000000000000000000000000000000000000001111111]

Até o n = 50  [ 00000000000000111111111111111111111111111111111111111111111111111111111]

Se n > 50 aí não vai caber em 1 int só... então eu tenho outro int pra guardar do 51 em diante...

Isso gera um valor que eu chamei de chkSum1 (<= 50) e chkSum2 (>50)

Depois eu faço a mesma conta nas linhas e colunas. Se bater o mesmo chkSum1 e chkSum2, então é pq tem todos os números.

ex: n = 3

chkSum1 = [ ...0000000111]
chkSum2 =  0

1 3 2  =  [ ...0000000111] == chkSum1
2 1 3  =  [ ...0000000111] == chkSum1
3 2 1  =  [ ...0000000111] == chkSum1

Válido.

1 3 3  =  [ ...0000000101] != chkSum1   Inválido
2 1 3  
3 2 1  

postado por @Abra em 08/02/2023 11:17

Abra Já entendi. É o lance da COLUNA não ter todos os números. Eu tava focado só na LINHA.
Obrigado a todos.
Gustavo muuuuito obrigado.

Também fiquei empacado nisso, até entender que tinha me atentado somente para análise das linhas, mas não das colunas.

Solução ineficiente, mas que funciona. Se conseguir melhorar (sem olhar a solução dos colegas), posto outra aqui:

Ver mais

postado por @adicionado em 08/02/2023 20:26

Ver mais

@adicionado Obrigado por postar a solução. Estava tentando em JS, mas me faltava compreensão da lógica.

Tentativa de solução minimalista:

Eu comecei a participar dos desafios para me divertir aprendendo uma coisa nova e, cara, tô adorando! 

Até agora, minha percepção é de que programar é tipo resolver puzzles. Tipo, você tem os objetivos e as regras do jogo, existem muitos caminhos para você alcançar os objetivos seguindo as regras. Você pode tentar diferentes caminhos, pode, por exemplo, tentar fazer da forma mais rápida ou mais criativa, ou com o código mais eficiente ou mais elegante.

Nesse sentido, parece bastante com matemática, que é uma área que gosto muito. Talvez por isso eu esteja gostando tanto

O desafio dessa semana me tomou um tempo enorme! Eu comecei a resolver assim que Giovanni postou aqui e logo no começo pensei "cara, será que não dá pra resolver usando matemática isso aqui?".

Cara, demorei um tempão pra descobrir um jeito que eu conseguisse provar que funcionava. Eu não queria só que rodasse porque podia ter algum erro nos test cases deles, queria provar que o jeito estava matematicamente correto.

Hoje eu finalmente consegui! Passei quase 5 horas só hoje nisso, fora as muitas horas no resto da semana.

Fazia muito tempo que eu não me divertia tanto!

Versão final do meu código:

postado por @oxe em 09/02/2023 20:29

Eu comecei a participar dos desafios para me divertir aprendendo uma coisa nova e, cara, tô adorando! 

Até agora, minha percepção é de que programar é tipo resolver puzzles. Tipo, você tem os objetivos e as regras do jogo, existem muitos caminhos para você alcançar os objetivos seguindo as regras. Você pode tentar diferentes caminhos, pode, por exemplo, tentar fazer da forma mais rápida ou mais criativa, ou com o código mais eficiente ou mais elegante.

Nesse sentido, parece bastante com matemática, que é uma área que gosto muito. Talvez por isso eu esteja gostando tanto
[...]
Fazia muito tempo que eu não me divertia tanto!

@oxe a melhor definição que eu já consegui chegar para "o que é programar?":

"Programar é descrever um objetivo mensurável de forma precisa o suficiente ao ponto de se tornar quase pedante.

Isso é feito, algumas vezes descrevendo o resultado e o programa acha o caminho. E, algumas vezes você descreve o caminho pra chegar no resultado.

Mas, o ato de PROGRAMAR é a primeira frase."

postado por @oxe em 09/02/2023 20:29

Eu comecei a participar dos desafios para me divertir aprendendo uma coisa nova e, cara, tô adorando! 

Até agora, minha percepção é de que programar é tipo resolver puzzles. Tipo, você tem os objetivos e as regras do jogo, existem muitos caminhos para você alcançar os objetivos seguindo as regras. Você pode tentar diferentes caminhos, pode, por exemplo, tentar fazer da forma mais rápida ou mais criativa, ou com o código mais eficiente ou mais elegante.

Nesse sentido, parece bastante com matemática, que é uma área que gosto muito. Talvez por isso eu esteja gostando tanto

O desafio dessa semana me tomou um tempo enorme! Eu comecei a resolver assim que Giovanni postou aqui e logo no começo pensei "cara, será que não dá pra resolver usando matemática isso aqui?".

Cara, demorei um tempão pra descobrir um jeito que eu conseguisse provar que funcionava. Eu não queria só que rodasse porque podia ter algum erro nos test cases deles, queria provar que o jeito estava matematicamente correto.

Hoje eu finalmente consegui! Passei quase 5 horas só hoje nisso, fora as muitas horas no resto da semana.

Fazia muito tempo que eu não me divertia tanto!

 
É matemática sim. 

Todo código é respaldado por teoremas matemáticos que estudamos na disciplina Teoria da Computação.

O computador é essencialmente um modelo matemático chamado máquina de Turing. 

Dei uma ajustada. Consegui provar que a segunda condição era suficiente para o problema, então consegui eliminar duas variáveis e um condicional do código. 

essa tive que recorrer ao chat para conseguir completar, demorei demais pra entender que tinha que verificar tanto a linha quanto a coluna em variáveis diferentes. Estava lendo algumas dicas em java, porém eu estava escrevendo em c#, a diferença de sintaxe das duas é discretamente diferente, demorei um tempo pra corrigir os errinhos bobos. Mas no final deu tudo certo!

postado por @oxe em 09/02/2023 23:35

Dei uma ajustada. Consegui provar que a segunda condição era suficiente para o problema, então consegui eliminar duas variáveis e um condicional do código. 

 Matematicamente elegante. Apenas 1 for para cobrir N^2 elementos da matriz. Confere a somatória dos quadrados dos elementos de cada linha/ coluna. O que me leva a pergunta: será que conferir N! seria condição suficiente?

@Rod100

A primeira abordagem que eu tentei foi por fatorial. Mas, dentro dos parâmetros da questão, existem sequências com elementos repetidos cujo produtório é igual ao fatorial de n. Por exemplo:

1, 2, 3, 4, 5, 6 e
1, 1, 4, 5, 6, 6

Eu pensei em usar duas condições, a soma dos n primeiros inteiros positivos e o fatorial.

Mas não cheguei a investigar mais a fundo se essas duas condições seriam suficientes porque, quando tentei implementar o fatorial, as variáveis estouraram. Tive que usar um tipo que nem sabia que existia, acho que era unsigned long long int, e o programa ficou lento pra caramba.

Aí abandonei a linha do fatorial e tentei outro ângulo de ataque. Aproveitei o gancho da soma dos n primeiros inteiros positivos e pensei em como complementar com uma segunda condição. 

Só ontem consegui demonstrar que a soma do quadrado dos n primeiros inteiros positivos seria suficiente. Mas a argumentação é longa e agora to no celular, fica ruim de digitar. Depois eu posto aqui. 

A ideia de usar um for só foi a de economizar código e ganhar eficiência, pois me permitiu testar linhas e colunas ao mesmo tempo. Eu demorei um tempo nisso também, até que tive a ideia de brincar com os índices, aproveitando o operador modulo e que o inteiro é truncado pelo C++.

Foi um desafio bem legal, ontem de noite eu tava com a mente exausta. 

@Rod100


Aí vai a explicação longa. Aviso logo que ficou gigante!

Os parâmetros do problema são os seguintes:

1- o input é uma matriz quadrada de ordem "n". Ou seja, a matriz tem linhas e colunas todas com o mesmo número "n" de elementos;

2- os elementos que compõem a matriz são todos inteiros positivos menores ou iguais a "n". Ou seja, são números naturais entre 1 e "n";

3- a função deve retornar verdadeiro se todas as linhas e todas as colunas contiverem todos os números naturais entre 1 e "n", e falso em qualquer outra situação.

Como há apenas "n" naturais entre 1 e "n" e como todas as linhas e todas as colunas têm "n" elementos, então a única forma de haver algum número natural entre 1 e "n" faltando em qualquer linha ou coluna é se houver outro número entre 1 e "n" repetido. Além disso, não pode haver elementos repetidos se estiverem presentes todos os números entre 1 e "n" (não cabe mais nada).

Inicialmente, eu pensei em testar a soma dos elementos de cada linha/coluna. Como eu sei (do ensino médio) que a soma dos "n" primeiros números naturais é dada por:

Sn = n*(n+1)/2 = (n^2 + n)/2

então, se a soma em alguma linha ou coluna for diferente desse valor, certamente não estão presentes todos os naturais entre 1 e "n" nela.

Só que existem sequências com números repetidos que dão a mesma soma Sn. Por exemplo:

1,1,4,4 tem a mesma soma que 1,2,3,4

Logo, a coincidência entre a soma e Sn não é condição suficiente, apenas necessária.

Aí eu pensei em testar uma segunda condição que, junto dessa primeira, fosse suficiente.

Pra tentar achar essa segunda condição, comecei a brincar com as sequências. Eventualmente cheguei na sequência do quadrado das somas:

Sq = 1^2 + 2^2 + 3^2 + ... + (n-1)^2 + n^2

Consegui provar que Sq pode ser dado pela fórmula:

Sq = n*(n+1)*(2*n+1)/6

A prova pode ser feita por indução finita. Ou seja, eu verifico se é válida para n = 1, depois assumo que é válida para n e provo que, sendo válida para n, necessariamente será válida para n+1. Isso gera um efeito dominó: como é válida para 1, se n = 1, então é válida para n+1 = 2 e, se n = 2, vale para n+1 = 3, assim sucessivamente. Ou seja, vale para qualquer n.

Aí tentei encontrar uma relação entre Sn e Sq.

Peguei Sn^2 e provei que é igual a Sq + 2*(a1*a2 + a1*a3 + ... + a1*an + a2*a3 + ... + a2*an + .... + an-1*an)

Isso me mostrou que, se Sn for par, Sq é par, e vice-versa, da mesma forma que, se uma for ímpar, a outra também será ímpar.

Aí tentei mostrar que a repetição dos termos da sequência da soma (condição para a função do programa retornar falso) gera alguma contradição. Mas essa linha de ataque também não deu resultado.

Continuei insistindo. Depois de muito tentar, comecei a brincar com Sn e os termos de Sq (ou seja, 1^2 .... até n^2).

Notei o seguinte:

n^2 - Sn = n^2 - (n^2 + n)/2 = (2n^2 - n^2 -n)/2 = (n^2 - n)/2 = ((n^2 + n) - 2n)/2 = (n^2 +n)/2 - n = Sn - n

Logo,

n^2 - Sn = Sn - n --> n^2 = 2Sn - n

O raciocínio é válido para qualquer n, ou seja, vale também para n-1, n-2, ..., 3, 2, 1

Ou seja:

n^2 = 2Sn - n
(n-1)^2 = 2S(n-1) - (n-1)
...
2^2 = 2S(2) - 2
1^2 = 2S(1) - 1

Como as sequências são finitas e os inteiros são fechados sob adição e multiplicação (ou seja, a soma ou o produto de dois inteiros também são inteiros), então dá pra somar essas equações todas. Fica assim:

n^2 + (n-1)^2 + ... + 2^2 + 1^2 = 2Sn-n + 2S(n-1) - (n-1) + 2S(2) - 2 + 2S(1) - 1

Só que isso do lado esquerdo é justamente Sq. Então fica:

Sq = 2*(Sn + S(n-1) + ... + S(2) + S(1)) - (n + (n-1) + ... + 2 + 1)

Esse último parênteses do lado direito é justamente Sn. Então fica:

Sq = 2* (Sn + ... + S(1)) - Sn

Sq = 2Sn - Sn + 2*(S(n-1) + ... + S(1))

Sq = Sn + 2*(S(n-1) + ... + S(1))

Ou seja, a soma do quadrado dos n primeiros números naturais é igual à soma dos n primeiros números naturais mais duas vezes a soma das somas parciais (ou seja, das somas para o primeiro elemento, para os dois primeiros, para os três primeiros, assim por diante até para os n-1 primeiros elementos).

Essa relação foi que me mostrou que calcular a soma do quadrado dos termos de cada linha/coluna e comparar com Sq seria suficiente.

Isso porque, para a sequência do programa ser falsa, tem que haver termos repetidos nela.

Vamos pegar uma sequência falsa qualquer e ordenar os termos dela do menor para o maior (mesmo que os termos não estejam ordenados na linha/coluna, estamos tirando a soma e a ordem dos fatores não vai alterar o resultado).

Ficaria algo como, por exemplo:

1,2,2,3,4,5,6

Observe que, antes da primeira repetição, todos os termos dessa sequência coincidem com o da sequência verdadeira (sem repetição):

1,2,3,4,5,6,7

Logo, as somas parciais até a primeira repetição vão coincidir entre a sequência verdadeira e a falsa. No caso, como a repetição só acontece no terceiro termo, então S(1) e S(2) são iguais em ambas as sequências.

A partir da primeira repetição, no entanto, a sequência falsa vai necessariamente ter somas parciais menores do que a sequência verdadeira. Isso porque a repetição de um número natural implica na ausência de um número natural maior que deveria estar naquela "posição".

Essa redução das somas parciais é cumulativa. Ou seja, nesse exemplo, S(3) da sequência falsa é uma unidade menor que S(3) da sequência verdadeira. Da mesma forma, S(4) é menor por uma unidade e assim por diante. Como estamos somando as somas parciais, então a redução em cada uma dessas somas parciais se acumula para gerar uma redução maior no resultado final.

Mesmo que a sequência falsa "compense" posteriormente essa perda com o aumento em outro termo repetido, esse ajuste só terá efeito nas somas parciais a partir dessa segunda repetição. Por exemplo:

1,2,2,5,5,6,7

Houve um aumento no quarto termo (que deveria ser 4 e no exemplo é 5), que compensou a redução no terceiro termo (que deveria ser 3 e no exemplo é 2). Isso significa que as somas parciais a partir do quarto termo, ou seja, S(4), S(5), S(6) e S(7) coincidem com as da sequência verdadeira.

Mas a S(3) da sequência falsa não foi corrigida, continua sendo uma unidade menor que S(3) da sequência verdadeira. Ou seja, a soma das somas parciais continuaria sendo menor. A única forma de compensar essa redução em S(3) seria com o aumento em alguma soma parcial posterior em exatamente uma unidade a mais.

Mas qualquer termo da sequência faz parte de todas as somas parciais posteriores ao termo. Ou seja, o quarto termo da sequência faz parte não apenas de S(4), como também de S(5), S(6) e S(7). Isso significa que, se o quarto termo for aumentado de ainda mais uma unidade, esse aumento vai se refletir nas somas parciais posteriores, de maneira que o resultado final, da soma das somas parciais, vai ser maior do que deveria ser na sequência verdadeira.

O único termo que só participa de uma soma parcial é o último, de valor n. Mas ele não pode ter valor n+1 porque os parâmetros da questão determinam que todos os elementos da matriz são no máximo igual a n.

Logo, é impossível que, nos parâmetros dessa questão, essa sequência falsa tenha uma soma das somas parciais igual à da sequência verdadeira.

O raciocínio pode ser generalizado para qualquer sequência falsa. A redução em uma soma parcial precisa ser compensada em uma soma parcial subsequente, que, como não pode ser a última soma parcial (cujo termo é limitado a n), vai refletir essa compensação em todas as somas parciais posteriores, resultando em uma soma das somas parciais diferentes.

Logo, é impossível que, nos parâmetros dessa questão, uma sequência falsa em qualquer linha/coluna tenha uma soma das somas parciais igual à da sequência verdadeira.

Consequentemente, por contraposição, se a soma das somas parciais é diferente, então a soma do quadrado dos termos também será diferente de Sq.

Logo, a soma do quadrado dos termos ser diferente de Sq é condição suficiente para a sequência ser falsa, dentro dos parâmetros da questão.

Sensacional, melhor post de todos nesta série de desafios até agora.

Do ponto de vista programação, possivelmente é uma solução eficiente. Os mais versados saberão dizer, mas até onde lembro, os processadores são mais eficientes em fazer somas e multiplicações do que usando if statements, operadores in, ou aplicado métodos como sort(). Alguém pode comentar?

fico impressionado nas respostas, e como a gente já evoluiu em 1 mês

Gastei mais umas horas para medir tempo entre a rotina puramente matemática do @Oxe e a minha rotina tosca de ficar procurando os números dentro da matriz.

Para matriz 3 x 3 verdadeira, que tem que verificar todas linhas e colunas:

Iniciando método Tosco
matriz verdadeira
Tempo decorrido em Tosco foi 9595 microsegundos
Iniciando método Oxe
matriz é true
Tempo decorrido em Oxe foi 38 microsegundos

Chutando uma matriz maior, de 8x8 e verdadeira:

Iniciando método Tosco
matriz verdadeira
Tempo decorrido em Tosco foi 9996 microsegundos
Iniciando método Oxe
matriz é true
Tempo decorrido em Oxe foi 51 microsegundos

Interessante que o tempo não subiu exponencialmente...

Aproveitei o exercício para aprender mais um pouco sobre classes, métodos em classe, calcular tempo de funções, simplificações de sintaxe e etc... Quem quiser olhar o código e rodá-lo no Kotlin Playground:
Kotlin Playground: Edit, Run, Share Kotlin Code Online

Método tosco é cúbico, melhor método é quadradico. A diferença não será  exponencial. 3 e 8 é igualmente pequeno, pra linguagem mais alto nível vai ser muito Overhead pra pouco tempo variável. Só aparece divergência no tempo pra número grande mesmo (1 milhão).

@oxe, sua solução é linda, parabéns.

postado por @Rod100 em 11/02/2023 11:58

Gastei mais umas horas para medir tempo entre a rotina puramente matemática do Oxe e a minha rotina tosca de ficar procurando os números dentro da matriz.

Para matriz 3 x 3 verdadeira, que tem que verificar todas linhas e colunas:

Iniciando método Tosco
matriz verdadeira
Tempo decorrido em Tosco foi 9595 microsegundos
Iniciando método Oxe
matriz é true
Tempo decorrido em Oxe foi 38 microsegundos

Chutando uma matriz maior, de 8x8 e verdadeira:

Iniciando método Tosco
matriz verdadeira
Tempo decorrido em Tosco foi 9996 microsegundos
Iniciando método Oxe
matriz é true
Tempo decorrido em Oxe foi 51 microsegundos

Interessante que o tempo não subiu exponencialmente...

Aproveitei o exercício para aprender mais um pouco sobre classes, métodos em classe, calcular tempo de funções, simplificações de sintaxe e etc... Quem quiser olhar o código e rodá-lo no Kotlin Playground:
Kotlin Playground: Edit, Run, Share Kotlin Code Online

postado por @FlyCavok em 07/02/2023 23:33

Ver mais

Solução usando bitwise operation

Beats 100% em CPU e 100% em consumo de memória também

O(n²) CPU
O(1) memory
Linguagem: Dart

Rock'n'roll baby

Cara, que beleza. Contar usando bits explodiu minha mente aqui, abriu a cabeça pra um mundo novo de possibilidades. Muito legal mesmo, obrigado!

Sensação que criei um monstro kkk, mas consegui resolver. Tomou bem mais tempo que o anterior, vou ver se consigo voltar na semana para melhorar alguma coisa vendo as respostas dos colegas.

postado por @Depi em 08/02/2023 11:12

Nesse desafio eu passo... rs

estou igual bastter race.  "Nasceu Ontem"

parece complicado, mas dá uma olhada nas soluções
por exemplo eu tenho mais familiaridade com JS/TS, então a solução do @adicionado me ajudou a organizar os pensamentos
tem vídeos de indianos explicando no YouTube também

é normal não entender no começo, esse tipo de resolução de problema primeiro você aprende copiando depois começa a ficar intuitivo!

exceto se você for alguém fora de série como o Oxe, Abra, PMH, maxete e outros mitos ou o encantador de elétrons @FlyCavok

@rod100 @miwan obrigado por colocar código bem comentado, ajuda bastante quem tá tentando resolver!

Não conhecia os Sets em JS/TS, obrigado @adicionado

const checkValid = (matrix: number[][]): boolean => {
  // Checks for our matrix size 
  const n = matrix.length;

  for (let i = 0; i < n; i++) {
    // Sets are used to store unique values inside a list
    // it's usually a faster method than using "array.includes"

    let columnItems = new Set();
    let rowItems = new Set();

    for (let j = 0; j < n; j++) {
      // Row check
      let rowItem = matrix[i][j];

      // We already have this number, break for loop and return false
      if (rowItems.has(rowItem)) return false;

      // We didn't see this number before, add it to our set
      rowItems.add(rowItem)
      // Column check
      let columItem = matrix[j][i];

      // We already have this number, break for loop and return false
      if (columnItems.has(columItem)) return false;

      // We didn't see this number before, add it to our set
      columnItems.add(columItem)
    }
  }
  return true;
}

BastterCode semana 6 - HashMaps - Word Pattern (290) - Tecnologia - Bastter.com

Dado o sucesso desse, coloquei como sugestão fazer o primeiro desafio de dificuldade média com matrizes, comentem lá