Nickolas's blog

By Nickolas, 10 years ago, translation, In English

470A - Crystal Ball Sequence

As usual, the first problem tests competitors' ability to do basic math, and in this case it is even easier than the sample — without any loops.

^'0-
$ 1+*3*1+.

470B - Hexakosioihexekontahexaphobia

This problem uses more advanced language concepts — loop, conditional execution and even named variables! Variables are convenient to use as loop counters and result accumulators, so as to avoid stack manipulations for the same purpose. An if-then-else in FALSE looks like this:

(true/false condition on top of stack) $ 
    [(then statements)] ?
  ~ [(else statements)] ?

Solution:

0n:    {number of 6s found uninterrupted so far}
0r:    {true, if 666 found}
[^$ 1_=~]
[ '6= $ [n; 1+ n:] ?
      ~ [0n:] ?
  n; 2 > r; | r: 
]
#
%
r; $ ["YES"] ?
   ~ ["NO"] ?

470C - Eval

This problem can be solved in two ways. You could read numbers, store them to named variables and depending on the operator use one of the operations on them. Or else you could do the other way around, store necessary operation as a function into a named variable (FALSE allows to store functions as variables) and apply it to numbers stored in stack. Here is the code of the second approach:

[0[^ $$ 47> \58\> &]['0- \ 10*+]#]
r:

r;!

$'+=[[+]f:]?
$'-=[[-]f:]?
$'*=[[*]f:]?
$'/=[[/]f:]?
$'%=[[\$@$@\/*-]f:]?
%

r;!
%
f;!.

470D - Caesar Cipher

This problem combines elements of previous problems: reading long int, reading a string and doing modulo operation (could be replaced with conditional subtraction).

0[^ $$ 47> \58\> &]['0- \ 10*+]#% k:   {read the key}

[^$ 10=~]
[ 'A- k;+ $ 25> [26-] ? 'A+ ,]
#%

470E - Chessboard

All of a sudden this problem turned out to be easier than C and D; probably a double-for loop is more simple than reading till end of line, especially with all the confusion with ends of line :-)

0[^ $$ 47> \58\> &]['0- \ 10*+]#%
n:

[\ $ @ $ @\/*-]
p:

0i:
[n;i;>]
[0j:
 [n;j;>]
 [j;i;+ 2p;!
  11* 46 \- ,
  j;1+j:]
 #
"
"
i;1+i:]
#

470F - Pairwise Sums

Next two problems use a new language construct — operator ø (a.k.a. O, not to be confused with 0), which allows random read access to stack elements. To calculate pairwise sums, one had to first read all array elements into the stak, then calculate indices of necessary elements, read them and add them up.

[0[^ $$ 47> \58\> &]['0- \ 10*+]#%] r:

r;! n:   {read the number of elements in array}

0i:
[n;i;>]
[r;! i;1+i:]
#        {read the elements of the array}

0i:
[n;i;>]
[$ n;O + . " " n;1-O i;1+i:]
#

0i:
[n;2*i;>]
[% i;1+i:]
#

470G - Hamming Distance

Same principle as in the previous problem — read characters of two strings into the stack (store the length of the strings into a named variable), then extract pairs of corresponding characters from it and accumulate the result in another named variable.

0n:
[^ $ 10=~]
[n;1+n:]
#%

[^ $ 1_=~]
[]
#%

0i:
0d:
[n;i;>]
[n;i;-1- O
 n;n;+i;- O
 =~ [d;1+d:] ?
 i;1+i:]
#

0i:
[n;2*i;>]
[% i;1+i:]
#

d;. 

470H - Array Sorting

Same as the regular sorting task, this problem can be solved in many ways.

You could write a "simple counting sort", as recommended by Egor: do an outer loop from 1 to 100, in the inner loop iterate over all array elements and print each element that equals the counter of the outer loop. Here is the code.

Or you could store array elements in named variables (since there are very few of them) and generate a code which would compare pairs of variables and swap them if needed. Thus, instead of a[0] you use variable a, instead of a[1] — b etc. The first such solution I've seen was nab's: the code.

I chose yet another approach: read array elements into a stack and use selection sort, but each time you need a swap, copy the whole array (with elements swapped already) onto the top of the stack. After at most n swaps the top of the stack will hold a sorted array. Unfortunately, stack size is limited, and with n around 20 it overflows. So I reduced array size a lot, which also allowed other approaches :-)

[0[^ $$ 47> \58\> &]['0- \ 10*+]#%] r:

r;! n:   {read the number of elements in array}

0i:
[n;i;>]
[r;! i;1+i:]
#        {read the elements of the array}

1s:      {# of array copies stored in memory}

0i:
[n;1-i;>]
[ i;m:          {index of min element between i and n-1, inclusive}
  i;1+j:
  [n;j;>]
  [ n;m;-1- O   {extract a[m]}
    n;j;- O     {extract a[j], knowing that a[m] is on top}
    >
    [j;m:] ?    {if a[j] > a[m], m := j}
    j;1+j:
  ]#

  i;m;=~
  [ 0k:
    [n;k;>]
    [ k;e:     {index of element we're extracting now}
      k;i;=
         [m;e:] ?
      k;m;=
         [i;e:] ?
      n;k;+e;-1- O
      k;1+k:
    ]#
    s;1+s:      {+1 copy of array in memory}
  ] ?           {if i != m, copy all elements, while swapping a[i] and a[m]}
   
  i;1+i:]
#

0i:
[n;i;>]
[n;i;-1- O . " "
 i;1+i:]
#

0i:
[n;s;*i;>]
[% i;1+i:]
#
  • Vote: I like it
  • +55
  • Vote: I do not like it

»
10 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

For problem D, I am confused by the answer checker. If you will look at My Submission here, you will see that the output matches exactly. Many other contestants had the same problem. What happened?

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

    Probably some mix-up with end-of-line characters. You read string to be encrypted till end-of-file, but end-of-file is preceded by end-of-line, so your output probably has some invisible characters.

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

missed it :(

»
10 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

470H has a couple of other easier approaches than selection sort (now that I'm somewhat familiar with the language).

I wrote a bubble sort in 103B (code). The logic is pretty simple, we repeat N times (copy array, but swap top two if needed).

I also came up with a solution in 95B (code) that at most has about maybe n+3 elements on the stack, but takes O(sum(a)) instruction stack size and O(sum(a)*n) time. Again we use a bubble sort, but we temporarily hide portions of the stack (storing the values in the instruction stack) and only do swaps at the top of the stack. This was actually super easy to get right, since all of the logic was "local" (i.e. operating on the top few stack values).

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

    That’s pretty damn awesome.

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

    I didn't participate in the contest, but my solution was similar to what was described as the counting sort, except I didn't iterate over all possible values — instead, I found the smallest number that I haven't printed yet (in other words, it is greater than the lasts number I printed), and how many of them are in the array. Then I printed that number several times and looped. The complexity is O(n^2) and uses linear stack size. Its quite a bit longer than yours but I'm sure its possible to shorten with some tricks I see you using: 7804834

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

This type of contest is so interesting. O(∩_∩)O~

»
10 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

My solution for problem B: click :D

»
9 years ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

i had addicted to this... and wrote a simple interpreter to solve C~H besides, i thought this this resolution is better by using a placeholder and persistent insertion sort.