3
\$\begingroup\$

EDIT It is not clear how answers to the question of compressing a long text, without cumulative properties are relevant to golfing a short cumulative strong, any more than general Lempel Ziv techniques are relevant to code-golfing. Take note that the complexity of 99 bottles of beer is not O(Sqrt(n))

Knuth suggested the notion of theoretical complexity of songs (Knuth, Donald E. "The complexity of songs." Communications of the ACM 27.4 (1984): 344-346.‏), noting that most cumulative songs are O(sqrt(n)).

Cumulative songs never showed up in PPCG. The challenge this time is Chad Gadya, a famous cumulative song in Aramaic and Hebrew, sung in cumulation of the seder. The lyrics can be found, e.g., here (blue text). (There are slight variations, so use this one, copied below).

To state the obvious, Chad Gadya belongs in the complexity class of the famous "Läuschen und Flöhchen" tale by the Grimm brothers, and some other more or less famous English songs, i.e., O(sqrt n).

The challenge is to write a program, in any programming language, that produces the song, each verse in its own line. The program takes no input, and cannot cheat by using, e.g., wget. A greater challenge is to make the solution so small that it can fit in a twitter message. (I bet no one here would be able to meet this challenge)

A short such program could be useful for twitter/sms holiday greetings. Please minimize the number of bytes (not characters). Output should be in UTF8.

Why is this interesting?

  • Knuth paper on the the complexity of cumulative songs
  • Song is very short; standard tricks would not help.
  • Space savings in Niqqud is an extra challenge.
  • Repetitions are not only due to the cumulative nature of the song.
  • The twitter objective seems impossible.
  • The song itself is quite short, much shorter than other songs that have been posted here. Compression of short text is more challenging than that of long text.

Output 

חַד גַּדְיָא, חַד גַּדְיָא דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא שׁוּנְרָא, וְאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא כַלְבָּא, וְנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא חוּטְרָא, וְהִכָּה לְכַלְבָּא, דְּנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא נוּרָא, וְשָׂרַף לְחוּטְרָא, דְּהִכָּה לְכַלְבָּא, דְּנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא מַיָּא, וְכָבָה לְנוּרָא, דְּשָׂרַף לְחוּטְרָא, דְּהִכָּה לְכַלְבָּא, דְּנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא תוֹרָא, וְשָׁתָה לְמַיָּא, דְּכָבָה לְנוּרָא, דְּשָׂרַף לְחוּטְרָא, דְּהִכָּה לְכַלְבָּא, דְּנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא הַשּׁוֹחֵט, וְשָׁחַט לְתוֹרָא, דְּשָׁתָה לְמַיָּא, דְּכָבָה לְנוּרָא, דְּשָׂרַף לְחוּטְרָא, דְּהִכָּה לְכַלְבָּא, דְּנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא מַלְאַךְ הַמָּוֶת, וְשָׁחַט לְשׁוֹחֵט, דְּשָׁחַט לְתוֹרָא, דְּשָׁתָה לְמַיָּא, דְּכָבָה לְנוּרָא, דְּשָׂרַף לְחוּטְרָא, דְּהִכָּה לְכַלְבָּא, דְּנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא הַקָּדוֹשׁ בָּרוּךְ הוּא, וְשָׁחַט לְמַלְאַךְ הַמָּוֶת, דְּשָׁחַט לְשׁוֹחֵט, דְּשָׁחַט לְתוֹרָא, דְּשָׁתָה לְמַיָּא, דְּכָבָה לְנוּרָא, דְּשָׂרַף לְחוּטְרָא, דְּהִכָּה לְכַלְבָּא, דְּנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא

If you find it hard to deal with Hebrew and Aramaic (tough luck...), try first getting your hands dirty with Läuschen und Flöhchen, and then proceed to the real challenge.

A related, but different question is that of "99 Bottles of Beer". If you care about complexity, you would notice that the theoretical complexity of bottles of beers is different from that of the two farthing kid.

Improve this question
\$\endgroup\$
13
  • 6
    \$\begingroup\$ You should include the full text of the song in your post. That said, I don't see why this isn't a dupe of this kgc question. The different character set shouldn't change the types of compression people use, and there doesn't seem to be substantial usable symmetry in the song not present in other challenges. \$\endgroup\$ – FryAmTheEggman Apr 21 '16 at 13:39
  • 2
    \$\begingroup\$ Relevant meta discussion about song text kolmogorov complexity challenges. \$\endgroup\$ – Martin Ender Apr 21 '16 at 13:41
  • 2
    \$\begingroup\$ Not every song is a duplicate of the rickroll. Where the song is short and the structure follows a strong pattern (here 'cumulative') golfing techniques other than straight text compression are applicable. See my meta post on work it harder, make it better (linked by Martin above.) Opinion is divided but the majority agreed with me. If we start closing questions like this, by the same logic we should close many ASCII art kolmogorov complexity questions, which would clearly be detrimental to the site. Voted to reopen, Did not upvote as I dislike Unicode challenges \$\endgroup\$ – Level River St Apr 21 '16 at 21:46
  • 1
    \$\begingroup\$ This reads like a long excuse (meaning, an answer to "Why is this on topic?") and a very brief description of the challenge. I think it needs more of the latter (and more prominently, viz first) and perhaps less of the former. \$\endgroup\$ – msh210 Apr 26 '16 at 12:30
  • 2
    \$\begingroup\$ I still think it's a duplicate. It may not be clear to you why the grammar-based techniques used in earlier song compression questions are equally applicable to this particular song, but it's perfectly clear to those of us who use them. \$\endgroup\$ – Peter Taylor Apr 26 '16 at 20:49
2
\$\begingroup\$

Python 2, 633 603 589 584 bytes (384 chars)

Note: the file must begin with a 3-byte “UTF-8 BOM” (EF BB BF), which Stack Exchange does not seem to preserve.

v="נָשַׁךְ הִכָּה שָׂרַף כָבָה שָׁתָה".split()+["שָׁחַט"]*4
c=', '.join(["חַד גַּדְיָא"]*2)
b=" דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. "+c
print c+b
e='אָכְלָה לְגַדְיָא,'+b
for i,t in enumerate("שׁוּנְרָא|כַלְבָּא|חוּטְרָא|נוּרָא|מַיָּא|תוֹרָא|שׁוֹחֵט|מַלְאַךְ הַמָּוֶת|הַקָּדוֹשׁ בָּרוּךְ הוּא".split('|')):
 print'וַאֲתָא '+(t if i!=7else'הַשּׁ'+t[4:])+' וְ'+e
 e=v[i]+' לְ'+t+', דְּ'+e

Output:

חַד גַּדְיָא, חַד גַּדְיָא דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא שׁוּנְרָא וְאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא כַלְבָּא וְנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא חוּטְרָא וְהִכָּה לְכַלְבָּא, דְּנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא נוּרָא וְשָׂרַף לְחוּטְרָא, דְּהִכָּה לְכַלְבָּא, דְּנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא מַיָּא וְכָבָה לְנוּרָא, דְּשָׂרַף לְחוּטְרָא, דְּהִכָּה לְכַלְבָּא, דְּנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא תוֹרָא וְשָׁתָה לְמַיָּא, דְּכָבָה לְנוּרָא, דְּשָׂרַף לְחוּטְרָא, דְּהִכָּה לְכַלְבָּא, דְּנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא הַשּׁוֹחֵט וְשָׁחַט לְתוֹרָא, דְּשָׁתָה לְמַיָּא, דְּכָבָה לְנוּרָא, דְּשָׂרַף לְחוּטְרָא, דְּהִכָּה לְכַלְבָּא, דְּנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא מַלְאַךְ הַמָּוֶת וְשָׁחַט לְשׁוֹחֵט, דְּשָׁחַט לְתוֹרָא, דְּשָׁתָה לְמַיָּא, דְּכָבָה לְנוּרָא, דְּשָׂרַף לְחוּטְרָא, דְּהִכָּה לְכַלְבָּא, דְּנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא הַקָּדוֹשׁ בָּרוּךְ הוּא וְשָׁחַט לְמַלְאַךְ הַמָּוֶת, דְּשָׁחַט לְשׁוֹחֵט, דְּשָׁחַט לְתוֹרָא, דְּשָׁתָה לְמַיָּא, דְּכָבָה לְנוּרָא, דְּשָׂרַף לְחוּטְרָא, דְּהִכָּה לְכַלְבָּא, דְּנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא

How it works:

I first create a list of all the nouns and verbs. It's in a string with a separator because that's a lot cheaper, byte-wise. I also have the ending piece in a variable.

The first part of the first line (חד גדיא, חד גדיא) is already contained at the end, so i just slice it and prepend.

Each of the next lines follows the same format, so i keep a running variable e (for end) of the part that gets copied, and just print the part that changes.

The line of השוחט needs to be special-cased.

Code shortened to use BOM by suggestion of Anders Kaseorg and msh210, and optimized with some tricks from msh210's answer.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ You can’t leave off the encoding header, but you can replace it with a 3-byte “UTF-8 BOM” (EF BB BF). \$\endgroup\$ – Anders Kaseorg Apr 26 '16 at 20:07
2
\$\begingroup\$

Perl 5, 632 bytes

$g="חַד גַּדְיָא";$g.=", $g";$\="דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. $g";@a=split b,"שׁוּנְרָאbכַלְבָּאbחוּטְרָאbנוּרָאbמַיָּאbתוֹרָאbשׁוֹחֵטbמַלְאַךְ הַמָּוֶתbהַקָּדוֹשׁ בָּרוּךְ הוּאbגַדְיָא";@c{@a}=@a;$c{'שׁוֹחֵט'}="הַשּׁוֹחֵט";@d=qw/אָכְלָה נָשַׁךְ הִכָּה שָׂרַף כָבָה שָׁתָה/;push@d,('שָׁחַט')x3;print$g.$";for$i(0..8){$/="\nוַאֲתָא $c{$a[$i]}, וְ$d[$i] לְ$a[$i-1], ";$/.="דְּ$d[$i-$_] לְ$a[$i-$_-1], "for 1..$i;print$/}
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Good job. Can the trick in this one help you? "g=(["חד גדיא"]*2).join ", " k = "שונרא1אכלה1כלבא1נשך1חוטרא1הכה1נורא1שרף1מיא1כבה1תורא1שתה1השוחט1שחט1מלאך המוות1שחט1הקדוש ברוך הוא1שחט" base = " דזבן אבא בתרי זוזי. " + g old = "גדיא" puts g + base k.scan(/(\D+)\d(\D+)/){ puts "ואתא #{$1}, ו#{$2} ל#{old}," + base base = " ד#{$2} ל#{old}," + base old = $1.delete("ה") } (Credit goes to G. A.) \$\endgroup\$ – Yossi Gil Apr 28 '16 at 21:59
  • \$\begingroup\$ @YossiGil, dunno, I don't speak (or even recognize) that language. \$\endgroup\$ – msh210 May 1 '16 at 2:15
1
\$\begingroup\$

Python 2, 331 bytes

(This source contains non-printable bytes, so it is presented as a hexdump that can be decoded with xxd -r.)

00000000: efbb bf70 7269 6e74 2278 01ed 54b5 6145  ...print"x..T.aE
00000010: 310c ec33 85fb c08e 3f0b 7c66 6668 c2ec  1..3....?.|ffh..
00000020: 39a4 7572 3917 8630 932b 4ba6 23bf a74d  9.ur9..0.+K.#..M
00000030: b9d0 aad1 8ad8 bb42 0eb5 2d97 5ada 318f  .......B..-.Z.1.
00000040: 2c18 9456 4eb5 8189 3216 8646 4b18 ca62  ,..VN...2..FK..b
00000050: dd6a 99ab 1bac aee4 4cdb 461b 5a17 8bed  .j......L.F.Z...
00000060: 68f6 cc6b d1b6 70f8 025c 30c7 ba71 d7af  h..k..p..\0..q..
00000070: b5c0 fb46 0470 47eb a84b a8bb 187b 186b  ...F.pG..K...{.k
00000080: 467b 282b 09c2 b7f2 eea2 0529 c278 d623  F{(+.......).x.#
00000090: d450 84b5 8e1c 9275 2cd0 33ff 0512 9bbc  .P.....u,.3.....
000000a0: ad95 0453 0364 57ac e79c 3a41 d67f cd8b  ...S.dW...:A....
000000b0: 116f 0b7d 58eb 3eba 15b6 4d1d dfd4 2e32  .o.}X.>...M....2
000000c0: feb7 865c 72d0 b6a3 6fa3 8bba ecd9 468e  ...\r...o.....F.
000000d0: 92eb 339e 664f 3798 b84a 1e61 01dd c6f3  ..3.fO7..J.a....
000000e0: 8d6c 27db f71b 9f8d afa1 5d8b 25ff 2b1c  .l'.......].%.+.
000000f0: 3ad3 5618 5c30 af69 9177 9211 e5e5 94be  :.V.\0.i.w......
00000100: ee97 d323 4f27 87b1 5c72 085e 9773 dd3c  ...#O'..\r.^.s.<
00000110: 16d9 3ac9 956a 7f58 b2f9 fb5b 12ab ca10  ..:..j.X...[....
00000120: a0c4 61c2 3302 b9b8 5996 1e89 f9f9 e741  ..a.3...Y......A
00000130: 91bf e181 e407 720b 7329 ec60 222e 6465  ......r.s).`".de
00000140: 636f 6465 2827 7a69 7027 29              code('zip')
Improve this answer
\$\endgroup\$
3
1
+50
\$\begingroup\$

GolfScript, 577 bytes

"חַד גַּדְיָא, חַד גַּדְיָא. ":d"דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. "d+"\n"+:c"גַדְיָא,שׁוּנְרָא,כַלְבָּא,חוּטְרָא,נוּרָא,מַיָּא,תוֹרָא,שׁוֹחֵט,מַלְאַךְ הַמָּוֶת,הַקָּדוֹשׁ בָּרוּךְ הוּא"","/:y;"אָכְלָה,נָשַׁךְ,הִכָּה,שָׂרַף,כָבָה,שָׁתָה,שָׁחַט,שָׁחַט,שָׁחַט"","/:x;9,{"וַאֲתָא "\.6="הַ"""if\.y\1+=\", וְ"\.x\=\" לְ"\.y\=\,-1%{", דְּ"\.x\=\" לְ"\.y\=\;}%". "c}%

Store the nouns and actions in variables by splitting strings. Using a list of lists of increasing sizes, each in descending order - [[1],[2,1],[3,2,1]...] - print the first and subsequent lines of each stanza using those index values.

Improve this answer
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.