gmane.comp.lang.perl.qotw.discuss

[QUIZ] Perl 'Hard' Quiz of the Whatever #2008-03-28 - Solving Kakuro

Shlomi Fish — 2008-03-27T22:38:08

IMPORTANT: Please do not post solutions, hints, or other spoilers until at least 60 hours after the date of this message. Thanks. Kakuro (a.k.a Cross-sums) is a kind of puzzle game: http://en.wikipedia.org/wiki/Kakuro In it, one fills in squares in a crossword-like grid that sum to their sums. One can fill in the digits from 1 to 9, and no digit can be repeated twice. Your object is that given a Kakuro board in a text format described below, then output the final solution. You can find some sample layouts from kakuro.com here: http://www.shlomifish.org/Files/files/text/kakuro.com-layouts/ and there's a new daily puzzle everyday there. (Requires Flash) There are also some more layouts googleable or on the wikipedia page. The layout has the following format: 1. It consists of $Height lines. 2. Each line has $Width squares. Whitespace inside each line is ignored. 3. Each square starts with [ and ends with ]. 4. A square that contains a \ is a blocked square (i.e: a square that cannot have any

[QUIZ] Perl 'Hard' Quiz of the Whatever #2008-12-28 - Symmetric Sokoban

Shlomi Fish — 2007-12-28T11:31:02

IMPORTANT: Please do not post solutions, hints, or other spoilers until at least 60 hours after the date of this message. Thanks. I was told the "What does this code do?" quizzes were not as good as a new programming task, so here's a more traditional QOTW that I came up with. In this quiz you'll try to solve the following Sokoban ( http://en.wikipedia.org/wiki/Sokoban ) puzzle using Perl: {{{{{{{{{{{{{{ #### # # # #### ###$.$ # # .< at >. # # $.$### #### # # # #### }}}}}}}}}}}}}} If you're not familiar with the notation, then "#" are walls, "$" are the initial positions of the boxes to be moved, "." are the destinations and "< at >" is the initial position of the player. This level is the Microban level No. 142 in the levels collection of KSokoban. You may want to solve it yourself before using Perl to do so. You can load it into a Sokoban clone by saving it into a file and then using the "load" command. Good luck and happy new year! Regards, Shlomi Fish -------------------------

[QUIZ] Perl 'What does this code do?' Quiz

Shlomi Fish — 2007-10-28T17:06:31

Hi all! Here's another "What does this code do?" Quiz. I obfuscated the names of the variable names to prevent hinting their purpose, but the code itself is not obfuscated. You have to guess what the "m2()" function does. Good luck! Please post spoilers as response to this post with "SPOILER". Regards, Shlomi Fish <<<<<<<<<<<<<<<<<<<<< use strict; use warnings; sub m2 { my $c = shift; my $d = sub { my $e = shift; return +(ref($e) eq "ARRAY") ? $e->[1] : $e; }; my $f = sub { my $e = shift; return +(ref($e) eq "ARRAY") ? $e->[0] : 1; }; my $g; $g = sub { my ($h, $i, $j) = < at >_; if (($h == < at >$c) && ($j == 0)) { return (); } elsif ($j == 0) { return $g->($h+1, $d->($c->[$h]), $f->($c->[$h]) ); } else { return ($i, $g->($h, $i, $j-1)); } }; return [ $g->(0, 0, 0) ]; } 1;

[QUIZ] Perl 'What does this code do?' Quiz

Shlomi Fish — 2007-06-27T19:05:53

Hi all! Here's another "What does this code do?" Quiz. I obfuscated the names of the variable names to provide hinting on their purpose, but the code itself is not obfuscated. You have to guess what the "z()" function does. Good luck! Please post spoilers as response to this post with "SPOILER". Regards, Shlomi Fish <<<<<<<<<<<<<<<<<<<<< use strict; use warnings; use List::MoreUtils (qw(uniq)); our %_t = (); sub t { my $c = shift; if (exists($_t{$c})) { return $_t{$c}; } no strict 'refs'; my < at >h = $c; my < at >d = < at >{$c. '::ISA'}; while (my $p = shift(< at >d)) { push < at >h, $p; push < at >d, < at >{$p. '::ISA'}; } my < at >u = uniq(< at >h); return $_t{$c} = [ sort { $a->isa($b) ? -1 : $b->isa($a) ? +1 : 0 } < at >u ]; } sub z { my ($self, $args) = < at >_; my $mn = $args->{mn}; my $c = ((ref($self) eq "") ? $self : ref($

mini-quiz

Yitzchak Scott-Thoennes — 2007-06-18T18:18:00

Things have been pretty quiet on this list, so I'm bringing up a question I thought would interest you all. Ovid, on perlmonks, asks[1] if this code is doing too much on one line: my $country = $card->country; $country = $country eq 'gbr' ? '' : uc "[$country]" if $country; How would you write it? Feel free to respond here or in the perlmonks thread. No need to wait 60 hours. [1] Ovid's question, without the (already quite a few) replies: http://perlmonks.org/?displaytype=print;node_id=621769

[QUIZ] Perl 'Medium' Quiz: Graph Connected Components (#2006-12-29)

Shlomi Fish — 2006-12-29T19:41:15

Hi all and Happy New Year! Here's a quiz for the new year. My sister received this challenge for her college homework, and had to write some Standard ML code to solve it, a task which I helped her with. I hope you enjoy it too. ======================================= IMPORTANT: Please do not post solutions, hints, or other spoilers until at least 60 hours after the date of this message. Thanks. We can represent a non-directed graph[1] (in the computer science sense) by the following representation: 1. Every node (or vertex) will have an integer assinged to it. 2. Every link (or edge) will be represented as a pair of two integers - those that were assigned to the the nodes it connects. Their order doesn't matter, but as you see below should be preserved. 3. The entire graph will be represented as a list of such pairs representing all the links of the graph. So for example the following graph: A--B--F D--C | / |/ E Can be represnted by the following array ref: [[$A

rejects to me?

Charles Abney — 2006-12-13T22:26:56

I'm getting failed sends of my list submissions. Methinks those should stay with the list maintainer, or?

New Quiz: "What does this code do?" (1-December-2006)

Shlomi Fish — 2006-12-01T14:35:44

Hi all! Well, it's been a while since we had a quiz so here's another what does this code do quiz: {{{{{{ my (< at >list) = ( grep { $cgi->param("$prefix$_") } map { /^${prefix}(\d+)$/ ? ($1) : () } $cgi->param() ); }}}}}} $cgi is a CGI.pm instance. (in case you couldn't guess.) A friend of mine whose perl is quite rusty had problems understanding this code. What does this code do? And can you guess in what context it was used? I'll reveal the solution after a 60 hours quota, and until then please send them to me in private. Regards, Shlomi Fish --------------------------------------------------------------------- Shlomi Fish shlomif-ik1l9ssToec+JF/nGntIXQ< at >public.gmane.org Homepage: http://www.shlomifish.org/ Chuck Norris wrote a complete Perl 6 implementation in a day but then destroyed all evidence with his bare hands, so no one will know his secrets.

[SPOILER] expert quiz #14

Daniel Wesenberg — 2006-07-12T16:52:39

Hi, I read your quiz solution and can see how this program could apply to a problem I have. How might I modify this program so that I can get results for the longest repeated substring in 1.5 million "random" digits? And print right within the program. Thanks in advance, Dan #!C:/Perl/bin/perl.exe -w sub repeated_substring { my $size = length $_[0]; my $maxsize = int ($size / 2); my ($f_index, $f_offset) = (0,0); OUTER: for (my $index=0; $index < $size; $index++) { # The big optimizer # (added a bounds check to keep us from going beyond the # end of the data) if ($f_offset > 20 && $index + $f_offset <= $size) { for (my $t_index = $index + $f_offset - 15; $t_index >= $index; $t_index = $t_index - 15) { if (index($_[0], substr($_[0], $t_index, $index+$f_offset-$t_index),

[QUIZ] Perl 'Easy' Quiz of the Week #2006-04-02 - Rounded Fractions

Yitzchak Scott-Thoennes — 2006-04-02T20:21:17

IMPORTANT: Please do not post solutions, hints, or other spoilers until at least 60 hours after the date of this message. Thanks. Cooking often involves multiplication and rounding of fractions, at least for those of us stuck under the tyranny of U.S. customary units. For instance, to make oatmeal, I use 7 parts water to 4 parts thick-cut rolled oats. If I have 1 2/3 cups oats, about how much water should I use? 5/3 * 7/4 = 35/12 = ~3 cups. Your task: create a script that prompts for a ratio of two integers and a quantity given as a whole number and/or a fraction (e.g. "1 3/5", "12", "3/7") and print out a rounded result of multiplying the quantity by the ratio in the same format. The result should be rounded to the nearest half, third, or fourth, whichever is most accurate (in cases exactly between two quantities, using the lowest denominator). You may assume none of the integers are overly large.

New Quiz: "What does this code do?" (3-Jan-2006)

Shlomi Fish — 2006-01-03T12:36:39

In the Israeli Perl Mongers mailing list we used to hold quizzes in which I would paste Perl code snippets and people needed to understand what they did, and possibly guess for what purpose they served. I am going to import this tradition here, and have a "What does this code do?" quiz. You are given the following Perl program, and have to understand what it does, and why was it written. Here goes: <<<< #!/usr/bin/perl use strict; use warnings; my $string = shift; foreach (< at >ARGV) { if (/^([^=]+)=(.*)$/) { my ($v, $s) = ($1,$2); if (substr($string, 0, length($s)) eq $s) { if ((length($string) > length($s)) ? (substr($string,length($s), 1) eq "/") : 1 ) { print $v . substr($string, length($s)); exit(0); } } } else { die "Bad"; } } print $string; Before the 60 hours quota is over, you can send your solutions to me in person

[QUIZ] Perl 'Medium' Quiz of the Week #2005-05-06 - Ranges' Lookup

Shlomi Fish — 2005-05-06T20:16:36

IMPORTANT: Please do not post solutions, hints, or other spoilers until at least 60 hours after the date of this message. Thanks. Well, the previous quiz did not seem to be very popular. Even I started writing it, and then abandoned. I also reached the conclusion that I'd be better off adapting Template Toolkit or whatever for this. In any case here's a fresh new quiz inspired by a question someone asked on the IRC. (Freenode #perl's channel today) You are given a large number of ranges (A[i],B[i]) where B[i] > A[i] for every i, and A[i] and B[i] are real. The ranges are not supplied in any particular order. You are then given a sequence of real numbers X[0], X[1], X[2] one by one. For each number, you have to determine whether it falls inside at least one of the ranges. For bonus points, you need to supply the user with a set of the indices of matching ranges. Phrasing it Perlishly: Write the following functions: 1. my $handle = prepare_ranges_handle($array_ref);

[QUIZ] Perl 'Hard' Quiz of the Week #2005-04-26 - A Preprocessor for CSS Files

Shlomi Fish — 2005-04-26T19:30:10

IMPORTANT: Please do not post solutions, hints, or other spoilers until at least 60 hours after the date of this message. Thanks. First of all a note: MJD is alive and kicking. He has been quite active in the mailing list dedicated to discussions of his newly published book "Higher Order Perl". Hopefully he can play a more active role here as well in the future. (Hi Mark!) In any case, for today's quiz, you will write a preprocessor for Cascading Style Sheets. Cascading Style Sheets (or CSS) are a W3C standard for controlling the look of HTML and other XML standards (like SVG). You can find more information on CSS here: http://www.htmlhelp.com/reference/css/ - an excellent introduction to CSS, albeit somewhat dated by now. http://www.w3.org/Style/CSS/ - the W3C's CSS Home. http://www.w3.org/TR/REC-CSS2/ - the W3C's CSS 2 Recommendation. http://www.w3schools.com/css/default.asp - CSS in W3Schools. More up-to-date information and resources than htmlhelp.com. (Note just

[SPOILER] My Solution to Perl 'Hard' Quiz of the Week #2005-03-22

Shlomi Fish — 2005-03-28T18:10:38

Hi all! Attached is: 1. DivideFsm.pm - a file that implements the aforementioned function. 2. Test.t - a fiel that tests it. Enjoy! Regards, Shlomi Fish --------------------------------------------------------------------- Shlomi Fish shlomif-ik1l9ssToec+JF/nGntIXQ< at >public.gmane.org Homepage: http://www.shlomifish.org/ Hacker sees bug. Hacker fixes bug.

[SPOILER] Solution to Perl 'Hard' Quiz of the Week #2005-03-22

Colin Rafferty — 2005-03-28T15:29:04

Since I was completely unable to solve the "hard" qotw as described, I solved the "easy" version instead, which MSB first. The solution is that each state $_ is the remainder ($_ % $N), so the transition is to left shift the state and add the input (modulo $N). Of course, the start state is 0 (0 % $N). sub gen_is_divisible_fsm { my ($N) = < at >_; return (0, [ map { { ret => $_, next_states => [ ((2 * $_) + 0) % $N, ((2 * $_) + 1) % $N ] } } (0 .. $N - 1) ]); } # Colin

[SPOILER] Solution to Perl 'Hard' Quiz of the Week #2005-03-22

Ronald J Kimball — 2005-03-25T17:20:34

I also initially solved the problem for MSB first, rather than LSB. Part of the confusion, I think, stems from the fact that the example state machine for $N=3 works in both cases! Anyway, there's an obvious pattern for the MSB FSM, because it's easy to track the remainder. For the LSB FSM, you can't track the remainder anymore, but there's still a pattern. As Greg said, when $N is odd the LSB FSM is simply the MSB FSM with the transitions reversed. So, here's my solution: sub gen_is_divisible_fsm { my($n) = < at >_; my < at >states; foreach (0 .. $n - 1) { push < at >states, { ret => $_, next_states => [( $_ * ($n+1) / 2) % $n, (($_ + $n-1) * ($n+1) / 2) % $n], }; } return(0, \< at >states); } Here's a script that dumps the FSM and tests it on the supplied input. This one also supports MSB-first and even numbers. #!/usr/local/bin/perl -w use strict; use Data::Dump qw/ dump /; my $n = shift or die "Must specify number to generate FSM.\n"; my $

[SPOILER] Solution to Perl 'Hard' Quiz of the Week #2005-03-22

Frank Fischer — 2005-03-25T10:58:37

At first: sorry for my bad english and my bad perl ;) I solved the problem for the LSB-FSM and I must say it was really a hard task. The main problem was not to write the generator-function but to design the FSM itself. My first solution was an FSM with about O(n^2) ("n" is that FSM-number) states. It's a straightforward solution from the theory. Then i tried to minimize the FSM with a standard minimization-algorithm (i.e. I wrote an algorithm replacing equivalent states by a new one). This leads to my first real solution. This one is written in ruby because it was too hard for me to translate it into good perl. The main problem of this solution is that it has a complexity of O(n^4) because the minimization algorithm has a complexity of O(n^2), too. But I made an observation leading to my final solution which is pretty small. The minimized FSM for "n" has alwasy n states. So I tried to find a way to create the equivalent states and their connections directly without using the minimization algorith