Nickolas's blog

By Nickolas, 10 years ago, translation, In English

So here goes the editorial. Note that Factor allows pretty random codes, feel free to put all words in one line, but all words must be separated by at least one space, don't try to skip a space between a bracket and a word or something like that.

162A - Pentagonal numbers

This problem was almost the same as 130A - Hexagonal numbers from Befunge round. Data input and output is done exactly as in the sample code, and besides them the program needs only basic stack operations.

USING: io kernel math math.parser ;

readln string>number
dup 3 * 1 - * 2 /
number>string print

Factor has a very system of built-in libraries which liberate the programmer from solving a lot of basic routine tasks. So after the first (trivial) probllem I gave several one-liners which needed only to find a proper library for the task.

162B - Binary notation

This problem can be solved in several ways; the shortest one is to use >bin word from math.parser dictionary which does exactly what we need.

USING: io kernel math math.parser ;

readln string>number 2 >base print

162C - Prime factorization

Looks like here I misestimated the complexity of the problem; D and E turned out to be easier. Actually, another library function, factors from math.primes.factors, performs all primes decomposition and even returns them as a sequence in a correct order. The second line converts a sequence of numbers into a sequence of strings (map combinator applies operations in square brackets to every element of the sequence). Finally, join concatenates elements of a sequence and inserts * between them.

USING: io kernel math math.parser math.primes.factors sequences ;

readln string>number factors 
[ number>string ] map
"*" join print ;

162D - Remove digits

This is yet another problem with multiple approaches possible — for example, one could find non-digits using a regular expression and concatenate them. My solution used replace word:

USING: math math.parser peg peg.parsers io kernel ;

readln 'integer' [ drop "" ] action replace print

162E - HQ9+

Now this is a match for regular expression. Word matches? checks whether the given string matches the given regular expression and pushes a boolean result on the stack. Word if checks this result and prints YES or NO depending on its value.

USING: io kernel regexp ;

readln R/ \S*[HQ9]\S*/ matches?
[ "YES" ]
[ "NO" ]

The problems from the second part of the match required not only googling but also learning some deeper aspects of the language.

162F - Factorial zeros

The quantity of tailing zeros of factorial is defined by the number of 5s this factorial is divisible by (matching 2s are more numerous, there will be enough of them). This number, in turn, can be calculated as n / 5 + n / 25 + n / 125 + ... + n / 390625. Note that here we need to use integer division (/i) or round each division result down using truncate, otherwise the leftovers might add up and produce a couple of extra zeros.

The reference solution contained elements of precalculation (to avoid the loop to calculate the powers of 5) and a named variable n (to avoid remembering the order of things on the top of the stack).

USING: io formatting kernel locals math math.parser math.functions sequences ;
IN: trailing-zeros

:: trailing-zeros ( -- )
   readln string>number :> n
   { 5 25 125 625 3125 15625 78125 390625 }
   [ n swap / truncate + ] reduce
   "%d" printf ;


162G - Non-decimal sum

This problem turned to be the hardest in the contest, and this surprised me a lot. It could be solved in a way similar to "42" example program, with minor modifications: after reading the quantity of numbers we had to read radix and store it to a named variable (for convenience only), and in the loop body strings had to be converted to numbers using base> word instead of string>number. Finally, the result had to be printed using >base instead of number>string.

USING: io kernel locals math math.parser sequences ;
IN: basesum

:: basesum ( -- )
   readln string>number iota
   readln string>number :> base
   [ drop readln base base> + ] reduce
   base >base >upper print ;


Update The docs for the language say that words >base and base> work for radixes only up to 16; actually they work with larger radixes as well, but this lessens my surprise at the complexity of this problem.

162H - Alternating case

In this problem I finally needed a real while loop! The first square brackets contain the continuation condition, the second ones — the loop body. I used it to slice the string in two-character pieces (and a leftover), convert each of them into title case (first letter is uppercase, the rest are lowercase) and print it without newline after it. The same process was applied to the leftover piece 1 or 2 characters long.

USING: io formatting kernel math sequences ;

[ dup length 2 > ]
[ 2 cut swap >title "%s" printf ]
>title print

Skiminok suggested a shorter and cleaner code:

USING: io kernel math sequences ascii ;
readln [ odd? [ ch>lower ] [ ch>upper ] if ] map-index print

162I - Truncatable primes

The second hardest problem, based on OEIS sequence A024785. One can use a library word prime? for primality testing, so the main part of the solution is another while-loop which checks whether the string contains a prime and removes its leftmost character. Note that the value of answer is not final at its first assignment, it will be modified later so you have to add ! to its name whenever assigning to it.

USING: io formatting locals kernel math math.parser math.primes sequences ;
IN: truncatable-primes

:: trancatable ( str -- )
   "YES" :> answer!
   [ dup length 0 > ]
   [ dup string>number prime? [ "NO" answer! ] unless
     1 cut swap drop
   answer print ;


162J - Brackets

Judging by the number of solutions submitted, I misestimated this problem as the hardest one. My solution was based on counting the brackets which stay open.

USING: io formatting locals kernel math sequences ;
IN: balanced-brackets 

:: balanced ( str -- )
   0 :> counter!
   1 :> ok!
   [ dup length 0 > ]
   [ 1 cut swap
     "(" = [ counter 1 + counter! ] [ counter 1 - counter! ] if
     counter 0 < [ 0 ok! ] when
   ok 0 =
   [ "NO" ]
   [ counter 0 > [ "NO" ] [ "YES" ] if ]
   print ;


Check out another editorial by wjomlex which relies heavily on recursion. Evidently, recursion is a natural response of a high-rated contestant to a functional language — well, I used none :-)

  • Vote: I like it
  • +42
  • Vote: I do not like it

10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The described approach for problem G does not work. For test 5 with radix 26 the following error is produced:

No suitable arithmetic method
left    8942709
right   f
generic +

I tried a couple more examples and the results are a bit odd:

"OO" 25 base>  -> works
"PP" 26 base>  -> error!
"QQ" 27 base>  -> works
"P" 26 base>  -> works
  • »
    10 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Using base> for radix over 16 is undocumented option, so sometimes it doesn't work; for possible workarounds see Russian discussion in this topic or passing submissions in the contest.

    • »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ah, thanks! I looked at passing submissions earlier but was curious about why the letter "P" was causing problems.

      • »
        10 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        It is treated as an exponent character, and the value after it must be a valid decimal number, so whenever P is followed by some letter, parsing the number fails.