« Bloggareträff uti Malmö, söndagen 4 maj (2008), klockan 13:00 på Kin Long | Main | Mitt OpenOffice Calc-/Excel-skov »

april 26, 2008

Ett litet april-pyssel

För tre år sedan (2005) publicerades ett Aprilpyssel. Det är dags att åter ta upp denna tradition.

Naturligtvis är nedanstående pyssel - på något sätt - kopplat till det jag kollar in just nu, dvs constraint programming/integer programming/MiniZinc.


Denna typ av pyssel har ett specifikt namn - som jag inte avslöjar just nu - och tillhör en grupp mer generella problem (som vad jag vet inte har något speciellt namn, dock med åtminstone ett undantag).


Problem


Inledning

Betänk följande binära matris (dvs endast 0 och 1 förekommer) där summorna för respektive rader och kolumner visas i fetstil.


1 010
1 010
0 000
  020

Vi sammanfattar respektive summor i två vektorer:

- radsummor: [1,1,0]

- kolumnsummor: [0,2,0].


Dagens pyssel går nu ut på, att givet en radsummavektor och en kolumnsummavektor, lista ut vilken matris som ligger som grund för dessa summor.


Delproblem

Det är två stycken delproblem som vardera på något vis kan ge ledtråd till lösningen av det andra delproblemet.

Delproblem a

radsummor= [0,2,2,2,2,2,8,8,4,4,4,4,4,0]
kolumnsummor = [0,0,0,12,12,2,2,2,2,7,7,0,0,0]

Delproblem b

radsummor = [0,0,8,2,6,4,5,3,7,0,0]
kolumnsummor = [0,0,7,1,6,3,4,5,2,7,0,0]


Ett av dessa problem har jag snott ("kopierat" är en mer korrekt term för detta förfarande) från någonstans, det andra har jag hittat på själv. Ordningen mellan delproblemen, liksom presentationen av dess härlednad i föregående mening, är faktiskt slumpad med ett slumptalsprogram, nämligen R.


Vinnerier etc

Vinnaren i detta pyssel anses den vara som först till pysselledningen:

- p) ger korrekt svar på båda delproblem

- q) samt redogör för hur problemet löstes.

"Till pysselledningen" definieras här som antingen en kommentar i denna blogganteckning, eller ett mail till hakank@bonetmail.com.

Vinnaren erhåller i kommentarerna till denna blogganteckning eller i en separat blogganteckning ett "Bra gjort, X!", där X ersätts av vinnarens namn/handle/smeknamn etc. Möjligen kommer "Bra gjort" att ersättas av synonymiserade uttryck och/eller kompletteras med kraftfullare attribut (såsom "Mycket") då i kombination med erforderliga ändringar av resten av uttrycket för att det ska bli så korrekt svenska som möjligt (byte av stor till liten bokstav etc).

Pysselledningen förbehåller sig att dela ut noll (0) eller flera stilprogram till förslag som ej är korrekt lösta, inkompletta men på något sätt (subjektivt bedömt) förtjänar ett stilpoäng, men även till korrekta lösningar som förtjänar sådan stilpoäng. Negativa stilpoäng kommer inte att delas inte, åtminstone inte officiellt. Eventuella felaktigheter som eventuellt påpekas för eventualla lösningsförslag definieras inte som negativa stilpoäng i detta sammanhang.

Till allt detta kommer vinnaren även att erhålla en av följande vid nästa eller någon (dock endast en) efterföljande IRL-träff (den virtuella glassen är än så länge alldeles för blaskig för att bjuda på):

- glass
- öl
- kaffe
- te
- eller annan motsvarande dryck

Not: Glass/öl/etc kan delas ut av den person som råkar utgöra pysselledningen i helt andra sammanhang och av helt andra skäl. Detta ska då ses som något som är hetl frikopplat från denna pysseltävling.


Lösningens presenterande etc


Det är planerat att presentera den av pysselledningen ansedda korrekta lösningen (inklusive några kommentarer samt åtminstone en vidarelänk) efter en viss tid har s.a.s. runnit, inklusive en MiniZinc-modell. Exakt när detta sker beror på.

Slutord

En av de saker som intresserar mig är hur man går till väga för att lösa slika problem. Därför är punkt q) viktig i lösningen. Det behöver inte vara (men kan vara) speciellt långt svar, men ange gärna metod, systemstöd samt - vilket är lika intressant - eventuella felskär.

Slutligen: Förutom "Lycka till!" kan noteras (vilket säkert redan gjorts av den observante läsaren) att ovanstående pysselformulering kunde - om omständigheterna vore annorlunda - göras mycket kortare. Men det är de inte så det gjordes inte.

Posted by hakank at april 26, 2008 10:25 FM Posted to Constraint Programming | Pyssel

Comments

a
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 0 0 0 1 1 0 0 0 0 0 0 0 0 0
2 0 0 0 1 1 0 0 0 0 0 0 0 0 0
2 0 0 0 1 1 0 0 0 0 0 0 0 0 0
2 0 0 0 1 1 0 0 0 0 0 0 0 0 0
2 0 0 0 1 1 0 0 0 0 0 0 0 0 0
8 0 0 0 1 1 1 1 1 1 1 1 0 0 0
8 0 0 0 1 1 1 1 1 1 1 1 0 0 0
4 0 0 0 1 1 0 0 0 0 1 1 0 0 0
4 0 0 0 1 1 0 0 0 0 1 1 0 0 0
4 0 0 0 1 1 0 0 0 0 1 1 0 0 0
4 0 0 0 1 1 0 0 0 0 1 1 0 0 0
4 0 0 0 1 1 0 0 0 0 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
x 0 0 0 12 12 2 2 2 2 7 7 0 0 0

==============
b
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
8 0 0 1 1 1 1 1 1 1 1 0 0
2 0 0 1 0 0 0 0 0 0 1 0 0
6 0 0 1 0 1 1 1 1 0 1 0 0
4 0 0 1 0 1 0 0 1 0 1 0 0
5 0 0 1 0 1 0 1 1 0 1 0 0
3 0 0 1 0 1 0 0 0 0 1 0 0
7 0 0 1 0 1 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
x 0 0 7 1 6 3 4 5 2 7 0 0


Vektorerna matades in i excel. De rader som summerade till noll, fylldes med nollor. Motsvarande för kolumner. Sedan fanns det vissa rader eller kolumner, där rad- eller kolumnsumman motsvarade antalet lediga platser. Dessa fylldes med ettor osv. Och så gav det sig.

Posted by: Mattias at april 26, 2008 04:54 EM

Och vi har en vinnare!

Bra gjort Mattias!

Fyllde du i 0 respektive 1 manuellt eller använde du Solver/Problemlösaren för detta?

Posted by: hakank [TypeKey Profile Page] at april 26, 2008 07:19 EM

Jag provade att använda funktioner i Google Documents för första gången. Jag använde bara summeringsfunktionen (SUM, SUMMA) för att se hur många som återstod i övrigt fyllde jag i manuellt.
http://spreadsheets.google.com/pub?key=p1YJutnFICUIRiXHBkAX3Ig

Där rader/kolumner hade noll återstående fyllde jag med nollor, i övrigt började jag med den rad/kolumn som hade högst differens mellan uppnådd summa och önskad summa. Fick samma h och spiral(@?) som Mattias.

Posted by: David Hall at april 26, 2008 08:35 EM

David: Helt rätt, du också.

Kul att du använde Google Document. Jag kikade på det för ett tag sedan under mitt OpenOffice Calc/Excel-skov. Tyvärr saknades några saker som jag just då höll på att kolla in (bl.a. den "intelligenta" versionen av SUMPRODUCT/PRODUKTSUMMA).

Någon som använt andra anfallsvinklar, med eller utan kalkylark?

Posted by: hakank [TypeKey Profile Page] at april 26, 2008 08:51 EM

Jag gjorde ett nytt försök med Googles kalkylark. För varje element så gav jag formeln =IF(($D4/14)*(E$18/14)>$A$4;1;0) där $D4 anger radsumman och E$18 kolumnsumman. $A$4 innehåller brytpunkten (1/14).

Posted by: David Hall at april 27, 2008 12:10 EM

Under vilka förutsättningar går det att entydigt bestämma matrisen utifrån rad- och kolonnsummorna? Generellt går det ju inte: informationsmängden i matrisen är n^2 bitar, och i summorna bara 2n log_2 n.

Posted by: ctail at april 29, 2008 08:56 FM

ctail: En mycket bra fråga. Tyvärr vet jag inte exakt förutsättningarna för entydighet (dvs unika lösningar).

Ett exempel på icke-entydighet är följande problem

radsummor = [11,5,4]
kolumnsummor = [3,2,3,1,1,1,1,2,3,2,1]

som har tre snarlika men olika lösningar.

A)
     3 2 3 1 1 1 1 2 3 2 1
11  1 1 1 1 1 1 1 1 1 1 1
 5  1 0 1 0 0 0 0 1 1 1 0
 4  1 1 1 0 0 0 0 0 1 0 0

B)
    3 2 3 1 1 1 1 2 3 2 1
11  1 1 1 1 1 1 1 1 1 1 1
 5  1 1 1 0 0 0 0 0 1 1 0
 4  1 0 1 0 0 0 0 1 1 0 0

C)
    3 2 3 1 1 1 1 2 3 2 1
11 1 1 1 1 1 1 1 1 1 1 1
 5  1 1 1 0 0 0 0 1 1 0 0
 4  1 0 1 0 0 0 0 0 1 1 0


Posted by: hakank [TypeKey Profile Page] at april 29, 2008 05:28 EM

David: Nu har jag kollat in din alternativa lösning. Kul approach!


Posted by: hakank [TypeKey Profile Page] at april 29, 2008 09:21 EM