[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
http://projecteuler.net/project/images/p_215_crackfree.gif
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?section=problems&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 :fagiano:

[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 :D

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 :fagiano:

bio

edit: rimosso codice, stronzata detected..

[cionci]

Edit: sbagliato :D

[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 :D

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:D) è 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 :D

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

http://bio.gbservicesnc.it/public/thumbs/contest12_01.JPG (http://bio.gbservicesnc.it/?filename=contest12_01.JPG)

http://bio.gbservicesnc.it/public/thumbs/contest12_02.JPG (http://bio.gbservicesnc.it/?filename=contest12_02.JPG)

[VICIUS]

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 :D

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]

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" :p che sia quello corretto

[marco.r]

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.! :muro: