[Vari] Contest12: Il muro

[gugoXX]

Sia abbia una disponibilita' infinita di mattoni, ciscuno dei quali di dimensioni (trascurando la profondita', assunta ininfluente per il problema) 2X1 e 3X1.

Si voglia costruire ad esempio un muro di dimensioni 9x3, completamente riempito, utilizzando tali mattoni.
Si potrebbe pensare di mettere i mattoni in questo modo

Ebbene, questo modo non va bene.
come si puo' vedere ci sono 2 mattoni che terminano in verticale, e il muro risulterebbe debole, e prima o poi creperebbe, causando un crack.
La domanda e': Quante diverse combinazioni dei mattoni dati possono riempire il muro 9x3, senza incorrere nel problema del crack, ovvero per cui non esitano nemmeno 2 mattoni verticalmente adiacenti che finiscano (o comincino) alla stessa con la stessa coordinata?
La risposta e' 8

Ebbene, Ma quante sono invece per un muro 32X10?

1) Trovare una funzione Wall(DX,DY) che restituisca, dati in ingresso le dimensioni rispettivamente orizzontale e verticale del muro target, il numero di combinazioni possibili che non diano adito al problema dei crack.

2) Valutare questa funzione in Wall(32,10)

3) Valutare questa funzione in Wall(100,50)

(Ehm... lo dico... non vale precalcolare i due risultati e poi stamparli, il punto fondamentale e' il primo...)

4) Esporre idee per scalare a 3D, ovvero considerando una tassellazione del piano date mattonelle di dimensione diversa (es. 3x2, 4x3), in modo tale da costruire un parallelepipedo pieno esente da crack.

Esercizio originale
http://projecteuler.net/index.php?se...roblems&id=215
Su questo sito l'unica cosa che conta e' il risultato finale, il valore
Per noi invece quello che conta di piu' e' la compelssita' algoritmica, oltre ovviamente l'esattezza del valore.

[ercand]

Interessante, ma non so da che parte inziare

[bio82]

io ho un'idea su come cominciare, ma non riesco a finire :P



in parole povere, calcolo tutte le combinazioni possibili del muro eeeee ora vado a dormire, domani penso a come calcolarmi un muro sopra l'altro

piccolo appunto..dato che al momento so fare solo cose di forza (bruta), questo codicillo è buono (a questo punto) solo per calcolare dx=32...quando si va oltre iniziano i problemi....

ma per questo ci state voi programmatori

bio

edit: rimosso codice, stronzata detected..

[cionci]

Edit: sbagliato

[bio82]

Module Module1

    Function ricercacombinazioni(ByVal lunghezza)
        Dim combinazionivalide(0) As String
        Dim binario As String = ""
        Dim zerimancanti As String = ""
        Dim maxlunghezza As Integer = (lunghezza / 2 + 1)
        Dim contatore As Integer = 0
        Dim limitebinario As Long = 0
        Dim tempsomma As Integer = 0
        Dim combinazione As String = ""

        For i = 1 To maxlunghezza
            zerimancanti = zerimancanti & "0"
        Next
        limitebinario = ((2 ^ maxlunghezza) / 2) - 1 'ATTENZIONE A QUESTO DIVISO 2

        For i = 0 To limitebinario
            tempsomma = 0
            combinazione = ""
            binario = Right(zerimancanti & Convert.ToString(i, 2), maxlunghezza)

            For o = 0 To binario.Length - 1
                binario = Replace(binario, "0", "2")
                binario = Replace(binario, "1", "3")
                combinazione = combinazione & Mid(binario, binario.Length - o, 1)
                tempsomma = tempsomma + Int(Mid(binario, binario.Length - o, 1))
                If tempsomma = lunghezza Then
                    combinazionivalide(contatore) = combinazione
                    contatore = contatore + 1
                    ReDim Preserve combinazionivalide(contatore)
                    Exit For
                ElseIf tempsomma > lunghezza Then
                    Exit For
                End If
            Next
        Next

        Return combinazionivalide
    End Function
    Function ricercavalorimuro(ByVal valorimuro)

        Dim posizionemuro(valorimuro.length) As String
        Dim tempcalcolovalori As Integer = 1

        posizionemuro(0) = 1

        For o = 1 To valorimuro.Length
            tempcalcolovalori = (tempcalcolovalori + Int(Mid(valorimuro, o, 1)))
            posizionemuro(o) = tempcalcolovalori
        Next

        ReDim Preserve posizionemuro(valorimuro.length - 1)

        Return posizionemuro
    End Function



    Sub Main()
        Dim watch As New System.Diagnostics.Stopwatch()
        Dim lunghezza As Integer = 10
        Dim altezza As Integer = 3
        Dim combinazionivalide() As String
        Dim combinazionimuro(1000, altezza) As String

        watch.Start()
        combinazionivalide = ricercacombinazioni(lunghezza)
        watch.Stop()
        Console.WriteLine("Le combinazioni accettabili per la singola riga sono:")
        For i = 0 To combinazionivalide.Length - 1
            Console.Write(combinazionivalide(i) & vbCrLf)
        Next
        Console.WriteLine("Tempo ricerca combinazioni: " & watch.ElapsedMilliseconds & " ms, combinazioni trovate: " & combinazionivalide.Length - 1 & vbCrLf)

        watch.Reset()

        Console.ReadLine()


    End Sub

End Module

al momento arrivo qua...sto pensando come fare il confronto fra le varie righe...

al momento genero tutte le righe possibili (22222,3322,3232, etc nel caso 10x3) e la funzione ricercavalori muro ritorna le posizioni di un muro (quindi nel caso valido 22222 mi torna 1,3,5,7,9)...

a questo punto dovrei confrontare le varie righe per vedere se sono compatibili, ma per questo ci sto ancora pensando

bio

[bio82]

Module Module1
    Function ricercacombinazioni(ByVal lunghezza)
        Dim combinazionivalide(0) As String
        Dim binario As String = ""
        Dim zerimancanti As String = ""
        Dim maxlunghezza As Integer = (lunghezza / 2 + 1)
        Dim contatore As Integer = 0
        Dim limitebinario As Long = 0
        Dim tempsomma As Integer = 0
        Dim combinazione As String = ""
        For i = 1 To maxlunghezza
            zerimancanti = zerimancanti & "0"
        Next
        limitebinario = ((2 ^ maxlunghezza) / 2) - 1 'ATTENZIONE A QUESTO DIVISO 2
        For i = 0 To limitebinario
            tempsomma = 0
            combinazione = ""
            binario = Right(zerimancanti & Convert.ToString(i, 2), maxlunghezza)
            For o = 0 To binario.Length - 1
                binario = Replace(binario, "0", "2")
                binario = Replace(binario, "1", "3")
                combinazione = combinazione & Mid(binario, binario.Length - o, 1)
                tempsomma = tempsomma + Int(Mid(binario, binario.Length - o, 1))
                If tempsomma = lunghezza Then
                    combinazionivalide(contatore) = combinazione
                    contatore = contatore + 1
                    ReDim Preserve combinazionivalide(contatore)
                    Exit For
                ElseIf tempsomma > lunghezza Then
                    Exit For
                End If
            Next
        Next
        Return combinazionivalide
    End Function

    Function ricercavalorimuro(ByVal valorimuro)
        Dim posizionemuro(valorimuro.length) As String
        Dim tempcalcolovalori As Integer = 1
        posizionemuro(0) = 1
        For o = 1 To valorimuro.Length
            tempcalcolovalori = (tempcalcolovalori + Int(Mid(valorimuro, o, 1)))
            posizionemuro(o) = tempcalcolovalori
        Next
        ReDim Preserve posizionemuro(valorimuro.length - 1)
        Return posizionemuro
    End Function
    Function confrontablocchi(ByVal confronto, ByVal temp)
        Dim uguale As Boolean = False
        For item = 1 To confronto.length - 1
            For ops = 1 To temp.length - 1
                If temp(ops) = confronto(item) Then
                    uguale = True
                    Exit For
                End If
            Next
            If uguale = True Then Exit For
        Next
        Return uguale
    End Function

    Function convertistringa(ByVal array)
        Dim stringa As String = ""
        For i = 1 To array.length - 1
            stringa = stringa & array(i) & ", "
        Next
        Return stringa
    End Function

    Function ricercacombinazionimuro(ByVal lunghezza, ByVal altezza)
        Dim combinazioni As String() = ricercacombinazioni(lunghezza)
        Dim valide(5000) As String
        Dim contavalide As Integer = 0
        Dim conta(altezza) As Integer
        Dim tempvalide(altezza) As String
        Dim temp() As String
        Dim corretto As Boolean
        Do
            Dim tempbase() As String = ricercavalorimuro(combinazioni(conta(1)))
            Dim confronto() As String = tempbase
            For i = 2 To altezza
                Do
                    temp = ricercavalorimuro(combinazioni(conta(i)))
                    corretto = confrontablocchi(confronto, temp)
                    If corretto = False Then
                        tempvalide(i - 1) = convertistringa(confronto)
                        tempvalide(i) = convertistringa(temp)
                        Exit Do
                    Else
                        conta(i) = conta(i) + 1
                    End If
                Loop Until conta(i) = combinazioni.Length - 1
                confronto = temp
            Next
            If tempvalide(altezza) <> "" Then
                For i = 1 To altezza
                    valide(contavalide) = valide(contavalide) & tempvalide(i) & vbCrLf
                Next
                contavalide = contavalide + 1
            End If
            conta(1) = conta(1) + 1
            For i = 2 To altezza
                conta(i) = 0
            Next
        Loop Until conta(1) = combinazioni.Length - 1
        ReDim Preserve valide(contavalide)
        Return valide
    End Function

    Sub Main()
        Dim watch As New System.Diagnostics.Stopwatch()
        Dim lunghezza As Integer = 20
        Dim altezza As Integer = 10
        Dim combinazionivalide() As String
        watch.Start()
        combinazionivalide = ricercacombinazionimuro(lunghezza, altezza)
        watch.Stop()
        Console.WriteLine("Le combinazioni accettabili sono:")
        For i = 0 To combinazionivalide.Length - 1
            Console.Write(combinazionivalide(i) & vbCrLf)
        Next
        Console.WriteLine("Tempo ricerca combinazioni: " & watch.ElapsedMilliseconds & " ms, combinazioni trovate: " & combinazionivalide.Length - 1 & vbCrLf)
        watch.Reset()
        Console.ReadLine()
    End Sub
End Module

visto che sono l'unico che la notte di natale ha provato a scrivere qualche riga di codice (morosa al lavoro->io a casa al pc) ho trovato il metodo per quasi risolvere il problema...

l'errore al momento è nel confronto delle stringhe, dove non tiene a mente la posizione in cui si trova quando una stringa è ok, lo risolverò quando il pranzo di natale verrà completamente assimilato (dopodomani almeno)...

il problema con il mio codice (come al solito) è che non è efficace e per fare un muro di 20x10 impiega 18 secondi...un muro di 32x10 non è umanamente concepibile con questo codice...

per questo hanno inventato i programmatori

bio

edit: due esempi, il primo di un muro 20x10 e il secondo 10x3, ovviamente il risultato è sballato dal ciclo che non ripete giusto, ma la tecnica è buona :P

[VICIUS]

Originariamente inviato da bio82

al momento arrivo qua...sto pensando come fare il confronto fra le varie righe...

al momento genero tutte le righe possibili (22222,3322,3232, etc nel caso 10x3) e la funzione ricercavalori muro ritorna le posizioni di un muro (quindi nel caso valido 22222 mi torna 1,3,5,7,9)...

a questo punto dovrei confrontare le varie righe per vedere se sono compatibili, ma per questo ci sto ancora pensando

bio

Non ti conviene generare direttamente le liste con i valori incrementali? Qualcosa tipo questo:

def find_all_possible_rows(briks, row, list, target)
  briks.each do |b|
    r = row.dup
    r.push r.last + b
    if r.last == target
      list.push r
    elsif r.last < target
      find_all_possible_rows(briks, r, list, target)
    end
  end
end

list = []
briks = [3,2]
row = [0]
find_all_possible_rows(briks, row, list, 9)

[marco.r]

Prima implementazione non troppo banale in Haskell.
Sostanzialmente enumera i vari modi di comporre i mattoni, i possibili passaggi,
e poi costruisce man mano le combinazioni alle varie altezze partendo da 1
Funziona bene fintanto che la dimensione orizzontale non e' troppo alta

module Main where

import Data.Map(Map,elems,fromList,(!))
import System.Environment(getArgs)


type BrickLine = [Integer]
type BrickSize = Integer

allLines :: [BrickSize] -> Integer -> [BrickLine]
allLines bricks lineSize
 = do allLines' [] 0 bricks lineSize

allLines' :: BrickLine -> Integer -> [BrickSize] -> Integer -> [BrickLine]
allLines' partialLine partialSize bricks lineSize
 = case compare partialSize lineSize of
     EQ -> return partialLine
     LT -> do nextBrick <- bricks
              allLines' (nextBrick:partialLine) (nextBrick+partialSize) bricks lineSize
     GT -> fail ""


haveCommonElement [] _ = False
haveCommonElement _ [] = False
haveCommonElement (x:xs) (y:ys)
 = case compare x y of
     EQ -> True
     GT -> haveCommonElement xs (y:ys)
     LT -> haveCommonElement (x:xs) ys


compatibleLines :: BrickLine -> BrickLine -> Bool
compatibleLines l1 l2
 = let
    l1sums = tail $ scanr1 (+) l1
    l2sums = tail $ scanr1 (+) l2
   in
     not $ haveCommonElement l1sums l2sums

     
possibleCombinations :: Map BrickLine [BrickLine] -> [BrickLine] -> Integer -> Map BrickLine Integer
possibleCombinations _ choices 1 = fromList [ (x,1) | x <- choices ]
possibleCombinations succs choices n
 = let
    prev = possibleCombinations succs choices (n-1)
   in
     fromList [ (x,sum [ prev ! y | y <- succs ! x ]) | x <- choices ]

solve :: [BrickSize] -> Integer -> Integer -> Integer
solve bricks lineLength lines
 = let 
    choices = allLines bricks lineLength
    sums = {-# SCC "sums" #-} fromList [ (x, tail $ scanr1 (+) x) | x <- choices ]
    compatible l1 l2 = {-# SCC "compatible" #-} not $ haveCommonElement (sums ! l1) (sums ! l2)
    succsList = {-# SCC "succsList" #-}  [ (x,filter (compatible x) choices) | x <- choices ]
    allSuccessors = {-# SCC "allSuccessors" #-} fromList succsList
   in
     sum $ elems $ possibleCombinations allSuccessors choices lines


main :: IO ()
main 
 = do args <- getArgs
      let lineLength = read $ args !! 0
          lines = read $ args !! 1
          sizes = map read $ tail $ tail args
      print $ solve sizes lineLength lines

Una volta compilato (consiglio 'ghc -O3' ... ) il programma si esegue con
Main <dimH> <dimV> <dim1> <dim2> ...
dove dim1 dim2, ... sono le dimensioni dei mattoni. Ad esempio per Wall(9,3)
Main 9 3 2 3

[VICIUS]

Soluzione in ruby ultra lenta:

def find_all_possible_rows_r(briks, width, rows, row)
  briks.each do |brik|
    temp = row.dup
    temp.push temp.last + brik
    if temp.last == width
      rows.push temp
    elsif temp.last < width
      find_all_possible_rows_r(briks, width, rows, temp)
    end
  end
end

def find_all_possible_rows(briks, width)
  rows = Array.new
  find_all_possible_rows_r(briks, width, rows, [0])
  rows
end

def check_for_cracks(a, b)
  return false if a.nil?
  for i in 1 ... (a.size-1)
    return true if b.include? a[i]
  end
  false
end

def find_all_possible_walls_r(rows, width, height, walls, wall)
  rows.each do |row|
    temp = wall.dup
    if check_for_cracks(temp.last, row)
      next
    else
      temp.push row
    end
    if temp.size == height
      walls.push temp
    elsif temp.size < height
      find_all_possible_walls_r(rows, width, height, walls, temp)
    end
  end
end

def find_all_possible_walls(briks, width, height)
  rows = find_all_possible_rows(briks, width)
  walls = Array.new
  find_all_possible_walls_r(rows, width, height, walls, [])
  walls
end

puts find_all_possible_walls([3, 2], 9, 3).size

Già con 32, 10 è impraticabile. Se poi si aggiungono anche altri pezzi il numero di soluzioni esplode. Ci deve essere di sicuro una soluzione più furba e visto che si tratta solo di "contare" ho il sospetto che ci sia sotto il calcolo combinatoria e le fattorizzazioni dei numeri.

[gugoXX]

Ecco il mio risultato corrente, e non ho ovviamente idea di come testarne la validita', se solo qualcuno potesse confermare...
Data l'ampiezza di questo risultato, immagino che il questito successivo sia impraticabile... Ste maledette disposizioni appena le stimoli un po' salgono piu' in fretta degli atomi dell'universo.

Wall(32, 10) = 806844323190414 disposizioni possibili
6174ms

L'unico test a disposizione e' che
Wall(9,3) = 8 e' confermato.

class Program
{
    static void Main(string[] args)
    {
        Stopwatch sw = new Stopwatch();
        sw.Start();
        Wall wl = new Wall();
        long poss = wl.GetDim(32, 10);                
        //long poss = wl.GetDim(9, 3);            

        sw.Stop();
        Console.WriteLine("Wall({0}, {1}) = {2} disposizioni possibili", wl.CurDx, wl.CurDy, poss);
        Console.WriteLine("{0}ms", sw.ElapsedMilliseconds);

        Console.ReadKey();
    }
}

public class Wall
{
    List<int[]> Papabili = null;

    public Wall()
    {
       
    }

    private void CreatePapabili(int dx)
    {
        int enm2 = dx / 2;
        int enm3 = dx / 3;            

        Papabili = new List<int[]>();            
        int qd3 = dx % 2;
        int qd2 = (dx-(qd3*3)) / 2;
        for (;qd2>=0;qd2-=3,qd3+=2)
        {
            Papabili.AddRange(Enumerate(qd2, qd3));
        }            
    }

    private IEnumerable<int[]> Enumerate(int qd2, int qd3)
    {
        if ((qd2 == 1) && (qd3 == 0))
        {
            int[] ret=new int[1];
            ret[0] = 2;
            yield return ret;
        }
        else if ((qd2 == 0) && (qd3 == 1))
        {
            int[] ret = new int[1];
            ret[0] = 3;
            yield return ret;
        }
        else
        {
            if (qd2 != 0)
            {                   
                foreach (int[] right in Enumerate(qd2 - 1, qd3))
                {
                    List<int> ret = new List<int>();
                    ret.Add(2);
                    ret.AddRange(right);
                    yield return ret.ToArray();
                }                    
            }
            if (qd3 != 0)
            {
                foreach (int[] right in Enumerate(qd2, qd3 - 1))
                {
                    List<int> ret = new List<int>();
                    ret.Add(3);
                    ret.AddRange(right);
                    yield return ret.ToArray();
                }
            }
        }
    }

    private int[][] Integrali;

    private void CalcolaIntegrali()
    {
        //Ottengo l'integrale (sommatoria comulativa) di ciascuna delle righe
        int ln = Papabili.Count;
        Integrali = new int[ln][];
        for (int t = 0; t < ln; t++)
        {
            Integrali[t] = Integrale(Papabili[t]);
        }
    }

    private int[] Integrale(int[] Line)
    {
        int flen = Line.Length-1;
        int[] FIntegr = new int[flen];

        int parsum = 0;
        for (int t = 0; t < flen; t++)
        {
            parsum += Line[t];
            FIntegr[t] = parsum;
        }
        return FIntegr;
    }
   
    private bool Check2Crack(int FirstLine, int SecondLine)
    {
        //Ottengo l'integrale (sommatoria comulativa) di ciascun valore di First e Second
        int[] Fintegr = Integrali[FirstLine];
        int[] Sintegr = Integrali[SecondLine];
        
        //Se anche solo uno dei valori e' uguale, allora crack.
        return Fintegr.Any(t => Sintegr.Contains(t));
    }

    List<int>[] PossibilePapabili;

    private void BuildNextPapabili()
    {            
        int paplen = Papabili.Count;
        PossibilePapabili = new List<int>[paplen+1];            

        for (int t = 0; t < paplen; t++)
        {
            PossibilePapabili[t] = new List<int>();
        }

        CalcolaIntegrali();

        for (int y = 0; y < paplen; y++)
        {                
            List<int> thisnext = PossibilePapabili[y];
            for (int z = y+1; z < paplen; z++)
            {             
                if (!Check2Crack(y, z))
                {                        
                    thisnext.Add(z);
                    // Se la prima puo' stare sotto la seconda, allora anche il viceversa.
                    PossibilePapabili[z].Add(y);
                }
            }
        }

        PossibilePapabili[paplen] = Enumerable.Range(0, paplen).ToList();
    }

    private long[,] RecursiveStorage;

    private long GetNextPartsOfWall(int parent, int hmlines)
    {
        long FromStor = RecursiveStorage[parent,hmlines];           
        if (FromStor == 0)
        {                                
            foreach (int qfi in PossibilePapabili[parent])
            {
                FromStor += GetNextPartsOfWall(qfi, hmlines - 1);
            }
            RecursiveStorage[parent, hmlines] = FromStor;                
        }
        return FromStor;
    }

    private long EnumerateWalls(int lines)
    {
        int lnpap = Papabili.Count;
        RecursiveStorage = new long[lnpap+1, lines+1];

        for (int t = 0; t < lnpap; t++)
            RecursiveStorage[t, 1] = PossibilePapabili[t].Count;

        return GetNextPartsOfWall(lnpap, lines);            
    }

    public int CurDx { get; protected set; }
    public int CurDy { get; protected set; }

    public long GetDim(int dx, int dy)
    {
        CurDx = dx;
        CurDy = dy;
        // Creo tutti i possibili tipi di linea larghi DX
        CreatePapabili(dx);
        // Per ciascuna Linea, calcolo i possibili successori
        BuildNextPapabili();
        // Calcolo il numero di possibili muri diversi
        return EnumerateWalls(dy);            
    }
}

[marco.r]

Originariamente inviato da gugoXX

Ecco il mio risultato corrente, e non ho ovviamente idea di come testarne la validita', se solo qualcuno potesse confermare...
Data l'ampiezza di questo risultato, immagino che il questito successivo sia impraticabile... Ste maledette disposizioni appena le stimoli un po' salgono piu' in fretta degli atomi dell'universo.

Wall(32, 10) = 806844323190414 disposizioni possibili
6174ms

E' il valore che risulta pure a me e sono "ragionevolmente convinto" che sia quello corretto

[marco.r]

Originariamente inviato da VICIUS

Già con 32, 10 è impraticabile. Se poi si aggiungono anche altri pezzi il numero di soluzioni esplode. Ci deve essere di sicuro una soluzione più furba e visto che si tratta solo di "contare" ho il sospetto che ci sia sotto il calcolo combinatoria e le fattorizzazioni dei numeri.

Limitarsi a contare le combinazioni non e' difficile... il problema e' contare la quantita' di successori. Ho una mezza idea e se funziona la soluzione dovrebbe scalare molto bene.

[malocchio]

Sto pensanso ad un algoritmo... devo dire che avendo solo 2 lunghezze disponibili il problema è molto più semplice che averne tante.. immaginate di dover scrivere una funzione che calcola le possibili combinazioni di mattoni per un muro X*Y ed avendo a disposizione mattoni con lunghezze uguali ai primi N numeri primi... quello sarebbe gran duro.!