[golf] XXX - finito

186 views
Skip to first unread message

Piotr Fusik

unread,
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. :-)

Michal Jankowski

unread,
Mar 11, 2004, 12:21:25 PM3/11/04
to
Nic nie rozumiem, co te programy robia i jak je mozna bylo wymyslic
8-)

MJ

Maciej Misiak

unread,
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

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

Piotr Maj

unread,
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

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. . . . . . . . . . . . . . . . .

Ton Hospel

unread,
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" ?

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).

Maciej Misiak

unread,
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.

> 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