Hunting in Von Neumann Universe

Define V i V_i such that V 0 = V_0 = \emptyset and V n = P ( V n 1 ) V_n = \mathcal{P} (V_{n - 1}) when n > 0 n > 0 .
Given any set K K , S ( K ) S (K) is the smallest integer m m such that K V m K \in V_m .

Compute the value of S S for this set.

Details and Assumptions:

  • P ( A ) \mathcal{P}(A) denotes the power set of A A ( ( set of all subsets of A ) A) . So V 1 = { } V 2 = { , { } } V 3 = { , { } , { { } } , { , { } } } . \begin{aligned} V_1 &= \{\emptyset\} \\ V_2 &= \{\emptyset, \{\emptyset\}\} \\ V_3 &= \{\emptyset, \{\emptyset\}, \{\{\emptyset\}\}, \{\emptyset, \{\emptyset\}\}\}. \end{aligned}
  • Empty set is denoted by { } \{ \} .
  • There are 113280 characters in the file.
  • No spaces or commas are used. So { , { } } \{\emptyset, \{\emptyset\}\} is denoted by { { } { { } } } \{\{\} \{\{\}\}\} .
  • S ( { { } { { } } } ) = 3 \text{S } ( \{\{\}\{\{\}\}\} ) = 3 .


The answer is 263.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

Arulx Z
Dec 20, 2016

To make the hunt easier, consider a set B = { a 1 , a 2 , , a n } B = \{a_1, a_2, \dots, a_n\} . I claim that S ( B ) = max ( S ( a i ) ) + 1 S(B) = \max\left(S(a_i) \right) + 1 for 1 i n 1 \leq i \leq n . This is true because if a V i a \in V_i and b V j b\in V_j where j i j \geq i . Then a V j a \in V_j .

So now the problem is reduced to parsing and recursion.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <stdio.h>
#include <string.h>

int findDepth(char A[], int p, int q);

int main(void)
{
  char set[] = "THAT STRING";
  printf("%d\n", findDepth(set, 0, strlen(set) - 1));
  return 0;
}

int findDepth(char A[], int p, int q)
{
  if(q - p == 1)
  {
    return 1;
  }

  int maxDepth = 0;
  int curDepth = 0;

  int start = p + 1;
  int cur   = p + 1;

  while(cur < q)
  {
    switch(A[cur])
    {
      case '{':
        curDepth++;
        break;
      case '}':
        curDepth--;
        break;
    }

    if(curDepth == 0)
    {
      int sectionDepth = findDepth(A, start, cur) + 1;
      if(sectionDepth > maxDepth) maxDepth = sectionDepth;

      start = cur + 1;
    }

    cur++;
  }

  return maxDepth;
}

Time taken is 0.05s. Complexity of my code is O ( n 2 ) \mathcal{O}(n^2) . However, as Zach pointed out, my code is just finding the maximum depth so the code can be written in Θ ( n ) \Theta(n) time quite easily (check Zach's answer).

Nice solution, @Arulx Z ! I really liked the one liner SSmin B = max ( ( SSmin a i ) + 1 \text{SSmin } B = \text{max}((\text{SSmin } a_i) + 1 .

I've added syntax highlighting for your code by changing 'C' to 'c'.

Christopher Boo - 4 years, 5 months ago

Why do you think it is O ( n 2 ) O(n^2) ? There is only one linear pass

Agnishom Chattopadhyay - 4 years, 5 months ago

Log in to reply

There's a recursive call, line 40. Now the question is why recursion was necessary at all.

Zach Bian - 4 years, 5 months ago

Consider this set { { { } } } \{\{\dots\{\}\dots\}\} . Here I first over it's only member set, then it's member set and so on so time required is c ( n 2 ) + c ( n 4 ) + c(n-2) + c(n-4)+\dots (code is badly written). I thought that this would be easier to write but as Zach said, the recursion isn't really that necessary and this code can be written just as well without it.

Arulx Z - 4 years, 5 months ago
Zach Bian
Dec 24, 2016

Here's some GNU x86_64 code that'll do the trick. In the spirit of the other solution, it only scans the file once (that's O(n)). I figure I can assume the string is constructed correctly (or else the problem would be unsolvable). So, really, all I did was count the max depth of the braces. As running time depends on hardware and other factors, it's really not super important (but if you must know, it was too small to be measured by my zsh's time function).

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
// compile with `gcc -nostdlib <assmblyfile.sx>`
// Run with: `./a.out <textfile with all the braces>`
// Make sure you pass the text file name as the command line argument! Otherwise, it won't read the file.
#define SYS_WRITE   $1
#define SYS_OPEN    $2
#define SYS_CLOSE   $3
#define SYS_FSTAT   $5
#define SYS_MMAP    $9
#define SYS_MUNMAP  $11
#define SYS_EXIT    $60

// From experiments:
#define FSIZEOFF    48
#define STATSIZE    144

// From Linux source:
#define RDONLY      $00     
#define PROT_READ   $0x1
#define MAP_PRIVATE $0x02
#define STDIN       $0
#define STDOUT      $1

.global _start
.text

.macro ERRCHECK code
    cmpq    $\code, %rax
    je      fs_error
.endm

.macro WRITE
    movq    STDOUT, %rdi
    movq    SYS_WRITE, %rax
    syscall
.endm

/* void* itoa(long, char *) 
                0q     8q
   - char * points to the *back* of the string. itoa writes from ls digit.
   - returns pointer to beginning of string as rax
*/
itoa:
    pushq   %rbp
    movq    %rsp, %rbp

    movq    16(%rsp), %rdi
    movq    24(%rsp), %rax

    cycledigits:
        xorq    %rdx, %rdx
        divq    decimal
        addq    $48, %rdx       // Add 48 to remainder, store digit
        movb    %dl, (%rdi)     // Copy char
        decq    %rdi            // Next digit
        cmpq    $0, %rax
        jg      cycledigits     // No more digits?

    leaq    1(%rdi), %rax       // return value

    popq    %rbp
    ret


/* Local stack notes: 
    0: int fd
    4: void* vmemptr
    12: void* head
    20: NOTHING
    28: void* end
*/
_start:
    // Open:
    movq    RDONLY, %rsi
    // Filename ptr is on stack currently as argv[1]:
    cmpq    $1, (%rsp)          // if argc is 1, default to stdin
    jnz     open_file
    subq    $36, %rsp           // local stack
    movl    STDIN, (%rsp)
    jmp     fstat

    open_file:
    movq    16(%rsp), %rdi      // argc(8), argv0(8) => rsp+16. filename
    movq    SYS_OPEN, %rax
    syscall
    ERRCHECK    -1
    subq    $36, %rsp           // local stack
    movl    %eax, (%rsp)        // int fd = open(argv[1], RDONLY)

    // fstat to get filesize
    fstat:
    movq    $statstruct, %rsi
    movl    (%rsp), %edi        // fd
    movq    SYS_FSTAT, %rax
    syscall                     // fstat(fd, statstruct)
    ERRCHECK    -1

    // mmap - don't forget to munmap.
    mmap:
    movq    $0, %r9             // offset
    movq    (%rsp), %r8         // fd
    movq    MAP_PRIVATE, %r10
    movq    PROT_READ, %rdx
    movq    filesize, %rsi
    movq    (%rsp), %rdi        // vmemptr
    movq    SYS_MMAP, %rax
    syscall
    ERRCHECK    -1
    movq    %rax, 4(%rsp)       // void* vmemptr = mmap(vmemptr, fsize, PROT_READ, MAP_PRIVATE, fd, 0)

    /* Read mmaped file */ 
    movq    %rax, 12(%rsp)  // head = vmemptr
    addq    filesize, %rax
    decq    %rax
    movq    %rax, 28(%rsp)  // end = vmemptr+filesize-1
    scan_outer:
        movq    12(%rsp), %rax
        cmpq    28(%rsp), %rax
        jge     cleanup         // if head >= end, done
        xorq    %rbx, %rbx      // Use rbx as counter
        loop1:
        cmpq    max, %rbx
        jle     donereplace
        movq    %rbx, max
        donereplace:
        cmpq    28(%rsp), %rax
        jge     writenum
        cmpb    $'{, (%rax)     
        jz      addcounter      // if leftbrace == *head
        decq    %rbx
        incq    %rax
        jmp     loop1
        addcounter:
        incq    %rbx
        incq    %rax
        jmp     loop1

    writenum:
    movq        max, %rbx
    pushq       %rbx
    movq        $maxend, %rbx
    pushq       %rbx
    call        itoa
    movq        %rax, %rsi
    subq        $maxend, %rax
    decq        %rax
    negq        %rax
    movq        %rax, %rdx      // Print number to screen
    WRITE

    cleanup: 
    // munmap
    movq    filesize, %rsi
    movq    4(%rsp), %rdi
    movq    SYS_MUNMAP, %rax
    syscall                     // munmap(vmemptr, filesize)
    cmpq    $-1, %rax
    je      fs_error
    // close
    movl    (%rsp), %edi
    movq    SYS_CLOSE, %rax
    syscall                     // close(fd)
    ERRCHECK    -1

exit:
    movq    SYS_EXIT, %rax
    xorq    %rdi, %rdi              // The exit code.
    syscall

fs_error:
    movq    SYS_EXIT, %rax
    movq    $-1, %rdi
    syscall                         // exit(-1)

.data
statstruct:     // This struct is 144 bytes. Only want size (+48)
    .zero FSIZEOFF
    filesize:  // 8 bytes.
    .quad   0
.zero STATSIZE-FSIZEOFF+8

decimal:
.quad       10    
max:
.quad       0
maxstr:
.ascii   "\000\000\000\000\000"
maxend:
.zero

Example run:

1
2
3
% gcc -nostdlib sets.sx
% ./a.out tmp.txt
263

Here's the same algorithm in Python (auto grabs the internet file):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
# Get the webpage
from urllib3 import PoolManager
parseString = PoolManager().request("GET", "http://pastebin.com/raw/gCC8dE4h").data.decode('utf-8')

# Or, offline (if you donwloaded the file first)
# parseString = open("tmp.txt", "r").read()

counter = 0
maxcounter = 0
for i in range(len(parseString)):
    cur = parseString[i]
    if cur == "{":
        counter += 1
    else:
        counter -= 1
    if counter > maxcounter:
        maxcounter = counter

print(maxcounter)

Just curious, why did you choose to use assembly?

Agnishom Chattopadhyay - 4 years, 5 months ago

It's a hobby. I kind of just repurposed a file reader program I wrote some time ago, though. I think it's on Rosetta Code.

Zach Bian - 4 years, 5 months ago

And the solution was easy enough, so I felt like getting a little practice.

Zach Bian - 4 years, 5 months ago
You Kad
Jan 4, 2017
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
from urllib.request import urlopen

depth = 0
max_depth = 0

with urlopen('http://pastebin.com/raw/gCC8dE4h') as f:
    L = list(f.readline().strip())
    print(L)
    for brace in L:
        if brace == 123:
            depth+=1
            if depth > max_depth:
                max_depth = depth
        elif brace == 125:
            depth-=1


print(max_depth)

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...