206 views

Skip to first unread message

Mar 11, 2004, 11:37:46 AM3/11/04

to

Witam!

Dwie i pol godziny temu zakonczyla sie 30-ta edycja polskiego perlgolfa.

Wyniki:

1 Ton Hospel (thospel) 60.60

2 Piotr Fusik (0xF) 63.55

Michal Szafranski (stalker) 63.55

3 Maciej Misiak (grizzley) 67.53

4 Mateusz Matuszek (magus) 68.48

5 Maciej Jastrzębski (pedro) 72 48

6 Krzysztof Kościuszkiewicz (kokr) 88.60

7 Przemysław Kowalczyk (szeryf) 96.60

8 Tomek Machalski (toomyem) 109.60

9 Mariusz Czulada (ManieQ) 128.59

10 Wawrzyniec Żurowski (Vava) 135.65

Gratuluje wszystkim 11 zwyciezcom!

Zgodnie z nowymi zasadami czestotliwosci masterowania, zaszczyt

prowadzenia 31 "okraglej" edycji przypada Stalkerowi.

Pozdrawiam,

0xF

PS. Gdy zobaczylem rozwiazanie Tona, to spadlem z krzesla i lezalem na

podlodze tak dlugo, az zmarzlem. No sami powiedzcie, co myslicie. :-)

Mar 11, 2004, 12:21:25 PM3/11/04

to

Nic nie rozumiem, co te programy robia i jak je mozna bylo wymyslic

8-)

8-)

MJ

Mar 11, 2004, 1:46:38 PM3/11/04

to

> Nic nie rozumiem, co te programy robia i jak je mozna bylo wymyslic

> 8-)

>

> MJ

> 8-)

>

> MJ

To tak dla wyjasnienia z grubsza. Wezme nie najlepsze rozwiazanie, zeby idea

byla jasna. Np.

#!perl -lp

map{$c=~y/IXCVL/XCMLD/;$_='I'x$_;s/I

{9}/IX/;s/IIII/IV/;s/IVI/V/;$\c.=$_}/./g;$_=$c

$c=~y/IXCVL/XCMLD/

to nic innego jak mnozenie liczby rzymskiej przez 10, czyli dodanie zera na

koncu :)

$_='I'x$_;

tutaj stworz ciag III...I, I ma byc tyle razy co cyfra.

s/I{9}/IX/;s/IIII/IV/;s/IVI/V/;

a potem odpowiednio pozamieniaj:

IIIIIIIII -> IX

IIIIIIII -> IVIIII -> VIII

IIIIIII -> IVIII -> VII

IIIIII -> IVII -> VI

IIIII -> IVI -> V

IIII -> IV

i wynikowy lancuch dodaj do wyniku.

A reszta to obudowanie petla for, ktora dzieli liczbe wejsciowa na cyfry.

Dokladniejszy opis przedstawi z pewnoscia zwyciezca

Pozdrawiam

Grizzley

PS. Jak to jest ze banalne zadania zawsze wzbudza tyle emocji i radochy... :-)

--

Wysłano z serwisu OnetNiusy: http://niusy.onet.pl

Mar 12, 2004, 6:23:22 AM3/12/04

to

Maciej Misiak wrote:

> i wynikowy lancuch dodaj do wyniku.

> A reszta to obudowanie petla for, ktora dzieli liczbe wejsciowa na cyfry.

> Dokladniejszy opis przedstawi z pewnoscia zwyciezca

> i wynikowy lancuch dodaj do wyniku.

> A reszta to obudowanie petla for, ktora dzieli liczbe wejsciowa na cyfry.

> Dokladniejszy opis przedstawi z pewnoscia zwyciezca

Ale coś nie przedstawia... Może mi ktoś wyjaśnić

co to robi: for$I.=4x$&%1859^7 w rozwiazaniu Tona?

dopisuje do zmiennej $I coś... tylko co? ;)

--

pozdrawiam . . . . . . . . . . .

Piotr Maj .:. kernelpanic.pl .:.

.:. Stuff for geeks .:.

Registered Linux user #231121. . . . . . . . . . . . . . . . .

Mar 12, 2004, 6:39:15 AM3/12/04

to

If I understood correctly, the next golf should be prepared by

Michal Szafranski, not by me ? Is the rule now "prepare at most

one in 4" ?

Michal Szafranski, not by me ? Is the rule now "prepare at most

one in 4" ?

Anyways, the obligatory explanation of the winning solution.

(Very long, but I actually enjoyed this a lot, even though you saw

almost no activity from me on the scoreboard, because I happened to

hit on a nice solution very early).

The basic idea was pretty obvious: convert one digit to it's normal

roman form. Then go to the next one while "multiplying" the last one

by 10 by transforming I -> X -> C -> M and V -> L -> D -> (impossible)

The obvious way to do that is:

s#.#$a=~y/IVXLCDM/XLCDM/;$a.=single_digit($&)#eg;$_=$a

(As other solutions show it's shorter to not introduce a help variable

like $a, and work directly in $_, distinguishing the fact that the

unprocessed piece of $_ are digits and the processed pieces are letters.

But in my solution that doesn't work since I will go through digits for

the result too).

But how to map 0..9 to "", I, ...., IX ?

A table lookup is possible, but long:

s#.#$a.=($a!~y/IVXLC/XLCDM/,I,II,III,IV,V,VI,VII,VIII,IX)[$&]#eg;$_=$a (74)

You can do a quite a few clever things (as seen in other solution), but

the conversion step tends to remain long. There's just no sane

regularity in this thing. But in "random" mappings with a very small

result set like this, the shortest solution is often to make up some

magic formula that has no particular meaning, but just happens to give

the wanted result. So I started considering $a.= magic_formula($&) where

then I add a mapping from the result digits of magic formula in the y///.

A little bit of thinking showed me there was not much chance of this

working as a perfect direct mapping (only 3 different digits in the

result, for I V and X), nor for a many to one mapping (some of I, V, X

represented by many digits). So there would also be extra digits to

be gotten rid of, which fortunately still works quite well with y///

if you use the d option.

The next step was searching for such a magic formula. Doing this by

hand is way too much work, so I needed a classic backtracking program

that given 10 numbers would try to find an assignment of each of

the digits to I, V, X and "nothing", so that in the end you'd get

"", I, II, ..., IX respectively.

I first did that as perl code, but it still got annoyingly long with

all the special cases and early tests so it didn't need to try ALL

possible combination. And even so all that checking is SLOW, so I

wanted the code in C really. So I decided to write a program that

would generate the C program that would generate the parameters to use

in the golf solution :-)

The perl code generating the C program can be found at

http://www.xs4all.nl/~thospel/golf/romanc.pl

In the code that generates, you need to add the C equivalent of the

perl "magic formula" that you want to try, and a loop to try this one

for all kinds of parameter values. The resulting code with such a

formula filled in for $m x $& % $n ^ $x can be found at:

http://www.xs4all.nl/~thospel/golf/romangen.c

Running this will output:

a b cd efg hi j kl mno pqrs tu => a I II III IV V VI VII VIII IX I=[bcdefghlnoqrst] V=[ijkmp] X=[u]

0=0

7 3 43 443 721 1680 136 1437 1332 298 => 7 I II III 7IV V680 VI6 VII7 VIII IX8 I=[234] V=[1] X=[9]

m=4,n=1859,x=7

1 6 76 776 1749 5428 37 366 3676 602 => 1 I II III 1I4V V428 VI VII VIII IX2 I=[67] V=[359] X=[0]

1 6 76 776 1749 5428 37 366 3676 602 => 1 I II III 1IV9 5V28 VI VII VIII IX2 I=[67] V=[34] X=[0]

1 6 76 776 1749 5428 37 366 3676 602 => 1 I II III 1I4V 542V VI VII VIII IX2 I=[67] V=[389] X=[0]

m=7,n=6029,x=1

That is a list of solutions, each time all working assignments, followed by

the parameter values used to get that one. The first two lines are a sanity

check so I know the assigner works.

e.g. the third and fourth line say that for the parameters m=4,n=1859,x=7

the values 0, 1,..9 map to 7 3 43 443 721 1680 136 1437 1332 298

and if you then map 2 3 and 4 to I, 1 to V and 9 to X, you get the strings:

7 I II III 7IV V680 VI6 VII7 VIII IX8

Next suppress 7, 6, 8 and 0 and you get the wanted result.

The next step is to write this as a good y///d thing with a nice use of

ranges so it gets short. That also turned out to be a boring task, so I

wrote a program to solve that. The post-processor for that is found at:

http://www.xs4all.nl/~thospel/golf/rangegen.pl

(A very interesting problem to do efficiently in fact, but this text is

already long enough so I'll skip the explanation of the method here).

Piping the previous set through that you get:

a I II III IV V VI VII VIII IX I=[bcdefghlnoqrst] V=[ijkmp] X=[u] y/b-ua/IIIIIIIVVVIVIIVIIIIX/d 0=0

7 I II III 7IV V680 VI6 VII7 VIII IX8 I=[234] V=[1] X=[9] y/91-80/XVIII/d m=4,n=1859,x=7

1 I II III 1I4V V428 VI VII VIII IX2 I=[67] V=[359] X=[0] y/035-791-8/XVVIIV/d m=7,n=6029,x=1

1 I II III 1IV9 5V28 VI VII VIII IX2 I=[67] V=[34] X=[0] y/034671-9/XVVII/d m=7,n=6029,x=1

1 I II III 1I4V 542V VI VII VIII IX2 I=[67] V=[389] X=[0] y/036-91-5/XVIIVV/d m=7,n=6029,x=1

Which summarizes things in such a way that the shortest line in the

result is the best solution. In this case that's:

y/91-80/XVIII/d m=4,n=1859,x=7

Combining all pieces then gives:

-lp s/./y!IVCXL91-80!XLMCDXVIII!d for $a.=4x$&%1859^7/eg;$_=$a

and dropping spaces and choosing all places where you have choice to be

chars that repeat as often as possible, you get:

-lp s;.;y$IVCXL91-I0$XLMCDXVIII$dfor$I.=4x$&%1859^7;eg;$_=$I

I tried many magic formulas, but this happens to be one of the first

ones I tried since the $m x $& tends to multiply the result by 10 each

time, so getting a result that's one longer each time, about the only

somewhat regular pattern in roman numerals. The modulo makes the result

shorter (so there's more chance for an assignment existing), but we must

allow the result to grow to at least 4 digits so we can get VIII. The

$x allows the mapping of 0 to move around, otherwise the fact that 0

can never be assigned to I,V or X tends to be a too severe constraint.

The only other good one was $m x $& * $x % $n, which has the same sort

of properties. That one also has a nice solution leading to a 60, but

with a worse tie:

-lp s;.;y$IVCXL426.-X$XLMCDIVX$dfor$X.=5x$&*8%29628;eg;$_=$X

All other formulas I tried tended to be longer to much longer (if they

had solutions at all).

Mar 12, 2004, 9:56:04 AM3/12/04

to

> If I understood correctly, the next golf should be prepared by

> Michal Szafranski, not by me ? Is the rule now "prepare at most

> one in 4" ?

Yes, I think you are right.> Michal Szafranski, not by me ? Is the rule now "prepare at most

> one in 4" ?

> Anyway, the obligatory explanation of the winning solution.

I must print it for myself and read twice while sitting in the armchair,

because even after reading I still don't get some parts :-) You should see some

of Golfers after reading your explanation... eyes big like cups of tea, heart

attacks, etc.

> (Very long, but I actually enjoyed this a lot, even though you saw

> almost no activity from me on the scoreboard, because I happened to

> hit on a nice solution very early).

It seems that there is more fun with writing help tools which write the program

for you as with finding manually best solution :-))) I enjoyed it a lot too.

Anyway, congratulations and I hope next edition starts as soon as possible

(next friday maybe?)

Grizzley

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu