Xah Talk Show 2022-12-17 Advent of Code Day 5, in WolframLang, Live Coding
sample input:
[R] [J] [W] [R] [N] [T] [T] [C] [R] [P] [G] [J] [P] [T] [Q] [C] [M] [V] [F] [F] [H] [G] [P] [M] [S] [Z] [Z] [C] [Q] [P] [C] [P] [Q] [J] [J] [P] [H] [Z] [C] [T] [H] [T] [H] [P] [G] [L] [V] [F] [W] [B] [L] [P] [D] [L] [N] [G] 1 2 3 4 5 6 7 8 9 move 1 from 2 to 1 move 3 from 1 to 3 move 2 from 2 to 1 move 1 from 1 to 2
- the problem requires implementing the stack data structure.
- it requires multiple number of stacks.
- stacks, is not a good data structure in functional programing languages, such as WolframLang, because it requires change of data/variable
example of stack push pop in python
# for example in python # move p (number of times) from m to n stackList = [[], [], []] for x in range(1, p): stackList[n].push(stackList[m].pop())
push and pop in WolframLang
there is not direct analog of push
and pop
and WolframLang, but:
- WolframLang has
First
,Drop
,Set
, that together they are likepop
in most langs. - WolframLang has
Prepend
andPrependTo
, that are like push in most langs.
ways to implement a stack in a functional programing language
- the standard way, to implement stack, in a efficient way, in functional programing languages, is by linked list (nested list) of 2 things, aka lisp con.
- by fixed length array, with 0 or other to indicate empty slot.
- in term rewriting system, use symbol sequence to stand for stack and its items.
implementing a stack by fixed array
- alternatively, we can implement stack by a fixed array, with a fixed length. and with 0 or other element to indicate empty slot. the problem here, is when you want to push or pop, you need to find where the real item begin. so, For example, you can keep a index.
- For example, pop means, replace the first non-zero value by 0, and return that value
- push means, replace the last 0, by a new value.
- so, insteaf of searching for the first non-zero, you can search it once, save it as index.
implementing stack in WolframLang using term rewriting
another way, in a term rewriting system, is to use a symbolic sequence, to stand for the stack. e.g.
(* stackIndex[name] = 0 *) (* example stack *) xstack[1] = "A" xstack[2] = "B" xstack[3] = "C" (* example of push *) xstack[index+1] = "D" (* example of drop *) xstack[index] = 0
- in this problem, we need multiple stacks.
idea of using a fix array to represent multiple stacks with fixed total count of elements.
instead of many stacks, we realize that the total number of crates never change. we simply move their position. so, the problem can be implemented by a fixed vector, with a special element to separate the “stacks”. e.g.
{n , z, 0, d , c, m, 0, p}
however, WolframLang list is like a smart array, like python and ruby. so it's not efficient, if you have to change the list length thousands of times.
bad. incomplete.