Day 22 Notebook

Part 1

input<-read_lines("../../AoCData/AOC2019/Day22.txt")

For part 1, I’m manipulating the deck

This reverses the deck:

newstack<-function(d){
  rev(d)}

This cuts it (both pos & neg work)

cutdeck<-function(d,n){
  n<-n%%length(d)
  outdeck<-d
  outdeck<-c(d[-c(1:n)],d[c(1:n)])
  outdeck}

This does the “deal with increment” shuffle

dwi<-function(d,n){
  outdeck<-c()
  for(i in 1:length(d)){
    x<-((i-1)*n+1)%%length(d)
    if(x==0){x<-length(d)}
    outdeck[x]<-d[i]}
  outdeck}

This function reads in the instructions, does them all and returns a shuffled, manipulated deck

shufflepart1<-function(d,instructions){
  i<-1
  while(i<=length(instructions)){
    inst<-unlist(str_split(instructions[i]," "))
    ### if the first word is cut, cut
    if(inst[1]=="cut"){
      d<-cutdeck(d,as.numeric(inst[2]))
    ### otherwise if the second word is "into" reverse the deck
    }else if(inst[2]=="into"){
      d<-newstack(d)
    ### otherwise if the second word is "with" then deal with increment
    }else if(inst[2]=="with"){
      d<-dwi(d,as.numeric(inst[4]))
    }else{cat("Someting went wrong\n")}
    i<-i+1}
  d}

Part 1 - run this against my input & get the answer

p1<-shufflepart1(0:10006,input)
part1<-which(p1==2019)-1
part1

[1] 2604

p1<-0:10006
x<-2019
for(i in 1:10){
  p1<-shufflepart1(p1,input)
  x<-which(p1==2019)-1
  cat(x,"\n")
}

2604 
1911 
9198 
6262 
6507 
5447 
9012 
940 
7885 
5816 

Part 2 -

My attempt to use modular arithmetic:

This takes the decksize & the instructions and returns with the coefficients of the equation that would solve it in one go:

modtransform<-function(decksize,instructions){
  a<-1
  b<-0
  m<-decksize
  i<-1
  while(i<=length(instructions)){
    inst<-unlist(str_split(instructions[i]," "))
    
    ### cut
    if(inst[1]=="cut"){
      c<-1
      d<- -as.numeric(inst[2])
    ### reverse
    }else if(inst[2]=="into"){
      c<- -1
      d<- -1
    ### deal with increment
    }else if(inst[2]=="with"){
      c<- as.numeric(inst[4])
      d<- 0
    }else{cat("Someting went wrong\n")}
    a<-(a*c)%%m
    b<-(b*c+d)%%m
    i<-i+1}
  c(a,b)}

For a deck size of 10007, this is the answer:

modtransform(10007,input)

[1] 9390 7459

###

The A is 9390. The B is 7459.

For a sanity check - this is what the old method gives for the position of card 2019 the first 10 shuffles of a 10007 card deck

p1<-0:10006
x<-2019
oldmethod<-c()
for(i in 1:10){
  p1<-shufflepart1(p1,input)
  x<-which(p1==2019)-1
  oldmethod<-c(oldmethod,x)
}
oldmethod

 [1] 2604 1911 9198 6262 6507 5447 9012  940 7885 5816

And this is what the new method gives

crd<-2019
newmethod<-c()
for(i in 1:10){
crd<-(9390*crd+7459)%%10007
newmethod<-c(newmethod,crd)}
newmethod

 [1] 2604 1911 9198 6262 6507 5447 9012  940 7885 5816

cat("compare old method and new method: ", oldmethod==newmethod,"\n")

compare old method and new method:  TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE 

They are the same - so I think that the modular is working.

This is just the function for composing Ax+B onto Cx+D mod M

cmps<-function(a,b,c,d,m){
  a<-(a*c)%%m
  b<-((b*c)+d)%%m
  c(a,b)}

This takes the function Ax+B and raises it to the k (shuffles multiple times)

multishuffle<-function(a,b,k,decksize,t){
  c<-1
  d<-0
  while(k>0){
    if(k%%2==1){
      g<-cmps(a,b,c,d,decksize)
      c<-g[1]
      d<-g[2]}
    k<-k%/%2
  f<-cmps(a,b,a,b,decksize)
  a<-f[1]
  b<-f[2]}
  (c*t+d)%%decksize}

And again, using 10007 and card 2019 - this is where it goes for the first 10 shuffles

multishuffleversion<-c()
for(i in 1:10){multishuffleversion<-c(multishuffleversion,multishuffle(9390,7459,i,10007,2019))}

multishuffleversion

 [1] 2604 1911 9198 6262 6507 5447 9012  940 7885 5816

cat("compare new method & multishuffle: ", multishuffleversion==newmethod,"\n")

compare new method & multishuffle:  TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE 

So this gives the same answer

BUT!!!!!!!!!!

The question asks for the card in position 2020, not where 2020 ends up. So, it needs the inverse function

And to find that, you find the inverse of A for that deck size

### A
modinv(9390,10007)

[1] 519

### B
(modinv(9390,10007)*-7459)%%10007

[1] 1488

So, to find what card was in that position, you can use 519 & 8519 (with these instructions on a deck of 10007) To show that makes sense, try it on the first 10 shuffle positions - all of them should return 2019:

sapply(1:10,function(x){multishuffle(519,1488,x,10007,multishuffleversion[x])})

 [1] 2019 2019 2019 2019 2019 2019 2019 2019 2019 2019

multishuffle(519,1488,10,10007,2020)

[1] 9248

Exactly as expected.

---

So trying this with a really, really, really big deck and a lot of shuffles:

largedeck<-as.bigz("119315717514047")
largeshuffle<-as.bigz("101741582076661")

AB<-modtransform(largedeck,input)
A<-as.bigz(AB[1])
B<-as.bigz(AB[2])
A

Big Integer ('bigz') :
[1] 28480444974763

B

Big Integer ('bigz') :
[1] 104343029082553

A=28480444974763 B=104343029082553

Invert the A & B:

### A
#iA<-modinv(A,largedeck)
### B
#iB<-(modinv(A,largedeck)*-B)%%largeDeck

Using wolfram alpha - iA = 82675948719931 iB = 403183578768

iA<-as.bigz("82675948719931")
iB<-as.bigz("403183578768")

And run that through multishuffle:

multishuffle(iA,iB,largeshuffle,largedeck,2020)

Big Integer ('bigz') :
[1] 79608410258462

---

So, trying this backwards:

This function does the reverse of everything. It cuts backwards, it reverses (which is the same either way), it deals into backwards.

inverstrans<-function(decksize,instructions){
  a<-1
  b<-0
  m<-decksize
  i<-1
  while(i<=length(instructions)){
    inst<-unlist(str_split(instructions[i]," "))
    if(inst[1]=="cut"){
      c<-1
      d<- -as.numeric(inst[2])
    }else if(inst[2]=="into"){
      c<- -1
      d<- -1
    }else if(inst[2]=="with"){
      c<- as.numeric(inst[4])
      d<- 0
    }else{cat("Someting went wrong\n")}
    ### invert it
    invc<-modinv(c,m)%%m
    invd<- (-d*modinv(c,m))%%m
    ###
    a<-(a*invc)%%m
    b<-(b*invc+invd)%%m
    i<-i+1}
  ### realigns to be 0 indexed
  c(a,b)}

Again showing that it works with 10007

inverstrans(10007,rev(input))

[1]  519 1488

And those numbers may look familiar - because they’re the same as above. And so it’s clear that this should work

This doesn’t work on the really big deck - because I can’t run bigz through modinv